Objekt C - Mangrove Manager 3.0 (4)

Speicherverwaltungsbibliotheken für Organisationsformen wie B-Trees und DLLs gibt es zu genüge.

Eine universelle Speicherverwaltung für diverse Vernetzungsformen wie Arrays, Ringe, DLLs, sortierte und unsortierte Bäume, gepaart mit einem Parser und leistungsfähigen Bearbeitungsfunktionen und komplexen Relationsdeskriptoren, ist dagegen schon etwas Besonderes. Vor allem, wenn gleich 11 Systemplattformen unterstützt werden, und das Speichern und Laden der Daten von der Festplatte möglich ist.

Viele C/C++ Bibliotheken werden nur für Windows oder DOS angeboten oder sind als Freeware-Quellcode nicht kommerziell nutzbar. Andere kommerzielle Bibliotheken werden zwar für verschiedene Plattformen angeboten, je Plattform werden hier aber jeweils mehrere hundert Mark fällig, und an die Unterstützung von TOS ist meist gar nicht zu denken. Die etwa 90 KB schlanke Bibliothek wird im Paket für folgende Plattformen angeboten: ATARI TOS, Windows 3.X/95/NT, OS/2, MS-DOS, Solaris/SUNOS (SPARC), LINUX a.out/ELF (x86), BSD/FreeBSD, AmigaOS & MacOS (68K & PPC).

Weil derzeit keine C-Compilerhersteller mehr ihre Produkte für TOS anbieten, wurde die C-Bibliothek als Übergangslösung vorerst mit GNU GCC 1.5.4 übersetzt (im Lieferumfang enthalten). Sobald der neue MagicMac kompatible GCC 2.7 Release verfügbar ist (wahrscheinlich schon mit Erscheinen dieser Ausgabe), erhalten registrierte Anwender kostenlos eine entsprechend übersetzte Bibliothek nachgeliefert.

Mangroven sind Pflanzen, denen es möglich ist, in verschiedene Richtungen zu wachsen. Man findet sie beispielsweise in den Sümpfen Floridas.

Das elektronische Gegenstück läßt sich vielleicht am besten mit ungerichteten Graphen vergleichen, die in der Lage sind, Teilbäume zu speichern, zu laden und die Daten beim Laden geordnet einzufügen. Zu den besonderen Eigenschaften der C-Bibliothek zählen Zufallsauswahl von Elementen eines definierten Bereiches, Parser, Garbage Collection, leistungsfähige Verknüpfungs-, Navigations- und Suchfunktionen und ein Plattform übergreifend portables Dateiformat der gespeicherten Mangroven.

Man könnte jetzt argumentieren, C-Bibliotheken wären C++ Bibliotheken wie etwa den Booch Components unterlegen, weil keine automatische hierarchische Aufteilung einzelner Speicherpools (z.B. Arrays) in einzelne Klassen erfolgt. Diese Argumentation ließe einige wichtige Dinge unberücksichtigt.

C++ ist nämlich nicht in der Lage, Objekte (wie etwa Object C) universell zu behandeln und muß deshalb für jede zu verwaltende Klasse eine eigene Kopie von Bibliotheksfunktionen erzeugen. Bei zu speichernden Objekten von 30 verschiedenen Klassen und 30 unterschiedlichen Bibliotheksfunktionen würden vom C++ Compiler also 900 Funktionen erzeugt werden (die bei Änderung von Klassenattributen auch immer neu übersetzt werden müssen). Das wären also 870 Funktionen zuviel! Die Speicherplatzverschwendung derartiger C++ Programme beträgt also je nach Projekt etwa 1-10 MB und ist deshalb für Netzwerkbetrieb, NoteBooks und vor allem ATARI STs unzumutbar und erhöht die Linkzeiten leistungsschwacher Rechner je nach Projektgröße um Wartezeiten zwischen einigen Minuten bis zu mehreren Stunden.

Hinzu kommt, daß Mangroven beliebig in alle Richtungen wachsen können und ihnen der jeweils gespeicherte Datentyp jedes Knotens bzw. Elementes egal ist.

Anwendung von Mangroven

Jedes Programm kann beliebig viele Mangroven erzeugen. Eine Mangrove wird durch „MANGROVE root = mml-nit();“ erzeugt und durch „mm-Kill(root);“ wieder gelöscht. Den Bibliotheksfunktionen wird als erstes Argument der Handle der Mangrove, auf die sich die Operation beziehen soll (also „root“), übergeben.

Wollen wir nun neue Speicherbereiche in eine Mangrove einsortieren, so geschieht das immer relativ zu einem bereits in der Mangrove vorhandenem Element. Im Falle einer leeren Mangrove müssen wir uns zunächst ein solches Basis-Element schaffen: „mmRinsert(root, „root-node“, 10, NEIGHBOUR);“. Das soeben eingefügte „root-node“ Element ist dann unser sogenanntes CURRENT (aktuelles) Element. Neben dem CURRENT Element gibt es noch zwei weitere ausgezeichnete Positionen: das RECENT (zuletzt zugegriffene) und MARKED (vom Anwender markierte) Element. Die meisten Bibliotheksfunktionen beziehen die so gekennzeichneten Elemente. Der einfachste Einfügebefehl ist „mmInsert(root, data, size);“. „mmInsert“ fügt immer ganz rechts (rechts eben dem RECENT Element) unterhalb des CURRENT Elementes einen neuen Eintrag der Größe „size“ an und füllt ihn mit den unter „data“ gespeicherten Daten. Das bedeutet, wenn wir 36 mal „mmInsert(root, „A“, 2);“ aufrufen und jeweils den zu speichernden Buchstaben „A“ inkrementieren, dann erhalten wir unterhalb des „root-node“ ein Array mit den Buchstaben des Alphabets.

Beispiel 1:

Speicherung des Alphabets

#include "mangrove.h"

int main (int argc, char** argv)
{
    MANGROVE root = mmInit(); 
    char data[2];

    (void) mmRinsert(root, "root-node", 10, NEIGHBOUR);

    for (*data = 'A', data[1] = '\0'; *data <= 'Z'; *data++)
    (void) mmInsert(root, data, 2);
    mmKill(root);

    exit(0);
}

Wie bereits beschrieben, setzt mmInsert() wie viele andere Bibliotheksfunktionen an dem CURRENT Element an. Mit Funktionen wie "data = mmPos(root, rel);" ist es möglich, die CURRENT Position auf ein anderes Element zu setzen. Das Referenzhandbuch definiert die möglichen Relationsdeskriptoren "rel" wie folgt:

rel := [mCrR] | [mCrR]?[(<multiplier>?[bcefNP])0]+

Der gewünschte Pfad kann durch zusammengesetzte Relationsdeskriptoren (einzelne Buchstaben) oder Basis-Relationsdeskriptoren (MARKED, ROOT, etc.) gebildet werden. Vor "N" (NEIGHBOUR) und T (FATHER) kann eine Zahl zur Wiederholung der Anweisung gesetzt werden. So springt beispielsweise "3N" um 3 Schritte nach rechts. BELOW und ABOVE können nur als Ziel für eine Insert- bzw. Search- & Insert-Funktion verwendet werden.

Navigation durch Relationen

ABOVE "A"

ABOVE beschreibt alle physikalisch einen Level über dem Bezugselement liegenden Elemente. Das Ergebnis wird anschließend mit der FATHER Klasse verbunden.

BELOW "B"

BELOW beschreibt alle physikalisch einen Level unter dem Bezugselement liegenden Elemente. Das Ergebnis wird anschließend mit der CHILD Klasse verbunden, jedoch nicht mit jeder existierenden BROTHERS Liste unterhalb des Bezugsobjektes.

BROTHER "b"

Die BROTHERS müssen nicht dem gleichen physikalischen Level angehören und bilden im Gegensatz zu NEIGHBOURS keine Liste, sondern einen Ring.

CHILD "c"

Alle hierarchisch unterliegenden Elemente bzw. das erste unterliegende Element. Ein Element dieser Klasse wird zusätzlich in die Liste der BROTHERS des zuletzt bezüglich des Bezugselements erzeugten CHILDs eingetragen.

CURRENT "C"

Das aktuelle Element (default)

ELDER "e"

Mit ELDER wird die Gegenrichtung zu BROTHER definiert.

FATHER "f"

Alle hierarchisch überliegenden Elemente bzw. das erste überliegende Element

MARKED "m"

Das vom Anwender markierte Element

NEIGHBOUR "N"

Das nächste Element rechts neben dem aktuellen Element bzw. Elemente gleichen Levels

ORIGIN "O"

Der oberste direkte Vater in einer hierarchischen Substruktur

PREVIOUS "P"

Die Gegenrichtung zu NEIGHBOUR definiert

RECENT "r"

Das zuletzt zugegriffene Element

ROOT "R"

Das oberste Element links

SINGLECHILD "s"

Dieser spezielle Fall der CHILD Klasse kann nur als Ziel für eine Insert- bzw. Search- & Insert-Funktion verwendet werden. Im Gegensatz zu CHILD wird eine neue BROTHERS Liste für das erzeugte SINGLECHILD angelegt und das nächste angelegte CHILD in diese Liste eingefügt.

Datenzugriff

Wollten wir nun auf eines dieser Elemente zugreifen, dann stehen uns neben den üblichen First/Next-Funktionen jeder üblichen Speicherverwaltung auch mächtigere Funktionen zur Verfügung. Eine davon ist "mmSelect(root, rel, spec);". "mmSelect()" liefert den Zeiger auf einen der gespeicherten Datenblöcke. Hierbei sind folgende Variationen möglich:

a) data = mmSelect(root, rel, 3);
Liefert "C" (spec gibt den Index des Elementes an)

b) data = mmSelect(root, rel, BACKWARDS(2))
Liefert "Y" (der Makro BACKWARDS indiziert ab dem letzten Element)

c) data = mmSelect(root, rel, ANY)
Liefert eine gleichmäßig gewichtete Zufallsauswahl zwischen "A" und "Z"

d) data = mmSelect(root, rel, HEAD)
Arbeitet wie ANY, aber gewichtet die erste Hälfte stärker.

e) data = mmSelect(root, rel, TAIL)
Arbeitet wie ANY, aber gewichtet die zweite Hälfte stärker.

Neben solchen Navigationen ist auch automatisiertes Suchen möglich, "data = mmRfind(root, empdata, cfn, rel);" durchsucht den mit "rel" beschriebenen Datenpool nach den Vergleichsdaten "empdata". "cfn" ist die Adresse der Vergleichsfunktion. In vielen Fällen reicht hier die Übergabe von "strcmp". Erlaubte Relationen für mmRfind() sind:

rel := [mCrR]?[(<multiplier>?[bcefNP])0]*[bcfABN].

Weil der Mangroven Manager nichts über die Art der gespeicherten Daten wissen kann, muß vom Anwender eine Vergleichsfunktion ähnlich der UNIX Funktion "strcmp()" bereitgestellt werden. Man sollte also eine Haupt-Vergleichsfunktion entwickeln, die anhand einer universellen Anfangsstruktur den Typ der Daten erkennt und einen entsprechenden Vergleich durchführt.

Beispiel einer Haupt-Vergleichsfunktion:

typedef struct
{
    int type;
}MyCompareHeader;

int mycompare (char * a, char * b)
{
    switch (((MyCompareHeader *)a)->type)
    {
        case 1: return (mycompare_l(a, b)); break;
        case 2: return (mycompare_2(a, b)); break;
        /* U.S.W. */
    }
}

Vergleichsfunktionen werden auch von einigen der Kopierfunktionen der Bibliothek benötigt, "data = mmCo-py(troot, cmpdata, cfn, trel, sroot, srel);" kopiert innerhalb einer oder unterschiedlicher Mangroven von "sroot/srel" nach "troot/trel". Wird keine Vergleichsfunktion "cfn" angegeben, dann wird das Element "sroot/srel" und alle untergeordneten Elemente in der Zielklasse "troot/trel" eingefügt.

Wird allerdings "cfn" und "cmpdata" definiert, dann wird in der Zielklasse nach dem Element "cmpdata" gesucht und das Element und dessen untergeordnete Elemente durch "sroot/srel" ersetzt. Hierbei bleiben die absteigenden Verknüpfungen des Quellbaumes im Zielbereich erhalten. "mmRscopy()" arbeitet wie "mmScopy()", sortiert jedoch unterliegende Elemente innerhalb der einzelnen Level.

Verknüpfungen

Einer der großen Vorteile von Mangroven besteht darin, Elemente variabel verknüpfen und somit komplizierte Sachverhalte der wirklichen Welt besser repräsentieren zu können.

Mit "mmLink(root, trel, srel);" ist es möglich, Verknüpfungen zwischen einer Gruppe von Elementen "srel" und einem Element "trel" zu erzeugen. Entweder "srel" oder "trel" müssen dabei der Klasse CHILD zugeordnet werden.

Die andere Relation kennzeichnet das oder die FATHER Elemente.

Bezugsquelle:

Cross Platform Research bietet die 10 Jahre erprobte Mangrove Manager Bibliothek nun standardmäßig im kommerziellen Object C Paket (0C2 - 798,- DM) sowie auf der Mangrove Manager CD (MM 3.0 -398,- DM) an, mit jeweils einschließlich einem kostenlosem Update.

Die komplette Dokumentation und Windows/MacOS Probe-Versionen des Paketes sind auf der CPR Homepage unter

http://ourworld.compuserve.com/homepages/CPR_ObjectC

aus dem WWW zu laden.

Ein Upgrade von MM 3.0 auf 0C2 zum Differenzpreis ist ebenfalls möglich.


Andreas Guthke
Aus: ST-Computer 11 / 1997, Seite 40

Links

Copyright-Bestimmungen: siehe Über diese Seite