Verketten ist „in“

In letzter Zeit ist es immer wichtiger geworden, Programme dynamischer zu machen, d.h. sich nur dann Speicher zu reservieren, wenn man ihn auch wirklich benötigt. Ein Hilfsmittel dazu sind die sogenannten verketteten Listen. Zum Umgang mit eben diesen soll hier ein kleines Modul vorgestellt werden.

Sinn und Zweck dieses Moduls ist der folgende: Nehmen wir an, ich benötige mehrere Speicherblöcke, zum Beispiel für jedes in meinem Programm zu bearbeitende Dokument einen. Wieviele Blöcke und in welcher Größe ich diese benötige, weiß ich leider beim Programmstart noch nicht. Also muß ich mir bei Bedarf während der Laufzeit Speicher holen. Damit ich nicht die Übersicht über alle meine Speicherblöcke verliere, verkette ich sie untereinander.

Verketten

So, nun zur Verkettung. Sie hat folgenden Sinn: Erstens finde ich alle meine Speicherblöcke ohne Probleme wieder, und zweitens brauche ich mir nicht alle Anfangsadressen der Blöcke zu merken, sondern nur die des ersten Blocks. Von dort aus kann ich mich dann bis zum gewünschten Block durchhangeln.

Zur Funktionsweise: Um eine feste Bindung der Blöcke aufzubauen, befinden sich in jedem Block zwei Pointer, die die ersten acht Bytes des Blocks belegen. Der erste Pointer, der sogenannte pre(/-Pointer, zeigt auf den vorigen Block, und der zweite, der sogenannte nexf-Pointer, zeigt auf den folgenden Block. Durch diese Verbindungen entsteht eine sogenannte Kette.

Bild 1: Eine Kette von Clutchs

Null-Pointer

Eine solche Kette hat auch einen Anfang und ein Ende. Der Anfang wird dadurch gekennzeichnet, daß der prev-Pointer im ersten Element ein Null-Pointer ist. Analog wird das Ende dadurch gekennzeichnet, daß der next-Pointer im letzten Element ein Null-Pointer ist. Um einmal an die Kette ranzukommen, wird noch ein Pointer deklariert, der auf das erste Element der Kette zeigt. Damit ist der Zugang zu der Kette geschaffen. Bild 1 soll nochmal schematisch den Aufbau dieser Kette darstellen. Gut zu erkennen ist der eine Pointer auf das erste Element, der als einzige Variable zu deklarieren ist. Ist dieser Pointer von außerhalb ein Null-Pointer, befinden sich überhaupt keine Elemente in der Liste.

Eins, zwei, viele ...

Damit das Modul nicht nur eine Kette verwalten kann, sondern mehrere, wurden die beiden Pointer, die für eine Kette nötig sind (der auf das erste Element und der Nachfrage-Pointer für die Auskunftsfunktionen - dazu später), in eine Struktur namens CLUTCH gepackt. Ein Array von diesen Strukturen sorgt dafür, daß die Pointer für CL_CHAINS-Ketten von Speicherblöcken (den Clutchs) gespeichert werden können.

Ich habe schon erwähnt, daß die ersten acht Bytes jedes Blocks für zwei Pointer reserviert sind. Sinnvollerweise hat der Anwender dieses Moduls damit aber gar nichts zu tun. Von den Auskunftsfunktionen (siehe unten) wird immer der Datenbereich zurückgeliefert, der dem Programmierer zur Verfügung steht. Auch beim Anmelden eines neuen Clutchs via CLAddClutch braucht für clutchsize nur die Größe des vom Programmierer benötigten Speichers angegeben zu werden. Die Verwaltung aller Pointer-Arbeit sowie der internen Vergrößerung jedes Blocks um acht Bytes wird automatisch erledigt. Die Anzahl der Bytes am Clutch-Anfang, die für die Verkettung notwendig sind, ist mit CL_HDRSIZE auf acht Bytes eingestellt.

Der Aufruf

Zuerst muß zu Anfang des Programms CLInitClutch aufgerufen werden. Das geschieht am besten während der Initialisierungsphase des eigenen Programs. Der Aufruf bewirkt nur, daß interne Variablen des CLUTCH-Moduls Default-Werte zugewiesen bekommen (es wird die Anzahl der angemeldeten Ketten auf Null gesetzt).

Möchte man eine Kette auf bauen, muß zuerst CLInitChain aufgerufen werden. Die Funktion setzt Default-Werte in die für die Kette zuständige CLUTCH-Struktur ein und liefert eine Ketten-ID zurück, die im Fehlerfall -1 ist. Diese ID braucht man, um sich die Clutchs anzumelden, da diese ja auch in die richtige Kette kommen sollen. Hier sieht man, daß mehrere Ketten über die verschiedenen IDs parallel benutzt werden können. Intern entspricht diese ID übrigens dem Index für den Zugriff auf die passende CLUTCH-Struktur.

Bild 3: Das Löschen eines Clutches aus dem Inneren der Kette

Hat man sich eine Kette angemeldet, kann man munter Clutchs anmelden. Dabei passiert folgendes: Zuerst wird der letzte Clutch in der Kette ermittelt. Daraufhin wird Speicher für den neuen Clutch reserviert. Dann werden die prev- und nexf-Pointer des neuen und des nun vorletzten Clutchs so gesetzt, daß der neue in die Kette integriert wird (siehe Bild 2). Zur Vereinfachung der Syntax existieren für den Zugriff auf diese Pointer die Makros CL_PREV und CL_NEXT.

Genauso einfach lassen sich auch Clutchs wieder löschen. Hierbei braucht beim Aufruf von CLClearClutch nicht die Kette übergeben zu werden. Es reicht der Clutch. Es werden alle Ketten nach diesem Clutch durchsucht. Sollte er gefunden werden, so wird er aus der Kette ausgeklinkt und der Speicher freigegeben (siehe Bild 3). Das war’s.

Nachfrage

Doch interessant wird das ganze System erst durch die zwei Auskunftsfunktionen CLGetFirstClutch und CLGetNext-Clutch. Um später zum Beispiel alle bisher angeforderten Speicherblöcke nach etwas Bestimmten zu durchsuchen, gibt es diese Funktionen. Mit einem Aufruf von CLGetFirstClutch erhält man die Adresse des ersten Speicherblocks der Liste. Ruft man dann CLGetNextClutch auf, erhält man den folgenden und so weiter. Ist das Ergebnis dieser Funktionen ein Null-Pointer, konnte kein Element gefunden werden.

Die Auskunftsfunktionen arbeiten mit einem zweiten Pointer, der auf das zu erfragende Element zeigt. Das ist genau der zweite Pointer aus der CLUTCH-Struktur. Damit man auch wirklich beim Aufruf von CLGetNextClutch immer den nächsten Block zurückbekommt, wird dieser Pointer immer ein Element weiter gesetzt. Beim Aufruf von CLGetFirst-Clutch wird dieser Pointer wieder auf den ersten Clutch gesetzt, so daß dieser erste Clutch zurückgegeben wird. Bevor man CLGetNextClutch aufruft, muß man sich immer zuerst den ersten Clutch mittels CLGetFirstClutch holen, sonst erhält man einen Fehlercode zurück.

Die Implementation

Zur Veranschaulichung liegt ein Demoprogramm bei, das CLUTCH. O über die Projektdatei mit einbindet. Man erzeugt also zuerst aus C_CLUTCH.C mittels CLUTCH.PRJ das passende Objekt-File CLUTCH.O, das dann in den Library-Ordner von PURE C kopiert wird. Analog kopiert man die Datei CLUTCH.H noch in den Header-Ordner von PURE C. Dann compiliert und linkt man mittels DEMO.PRJ das File DEMO.C und CLUTCH.O zu DEMO.TOS und startet das Programm. Fertig ist die Demo. Hier zeigt sich der Vorteil der unabhängigen Programmierung von CLUTCH. Da es als Objekt-File vorliegt, ist es kein Problem, CLUTCH auch in andere Projekte einzubinden. Außerdem ist das Prinzip so einfach, daß selbst die Übertragung in andere Sprachen keine Hürde für den Programmierer darstellt.

Vorsicht

Ein kleiner Punkt ist noch zu beachten. Bei der Compilierung von CLUTCH legt man über die Definition von CL_CHAINS die Anzahl der maximal verfügbaren Ketten von Clutchs fest. Aber damit läßt’s sich - glaub’ ich - leben. Es sei auch noch angemerkt, daß man CLUTCH nicht dazu mißbrauchen sollte, seine komplette Speicherverwaltung in den Müll zu schmeißen. Man sollte sich trotzdem noch immer Gedanken darüber machen, welchen Speicher man alloziert. Eine ständige Allozierung kleiner Speicherblöcke führt schnell zur Fragmentierung des Speichers.


/* CLUTCH.H */

#ifndef __CLUTCH

# define __CLUTCH

# include "portab.h"


/* Das Clutchmodul initialisieren */

BOOLEAN CLInitClutch( VOID );


/* Eine Clutchliste initialisieren. Ergebnis: Eine ID <> -1 */
WORD CLInitChain( VOID ) ;

/* Einen Clutch der Größe 'clutchsize' anhängen */
VOID *CLAddClutch( WORD chain, LONG clutchsize );

/* Einen Clutch löschen */
BOOLEAN CLClearClutch( VOID *clutch );

/* Alle Clutches löschen */
VOID CLClearAllClutches( VOID );

/* Den ersten Clutch erfragen */
VOID *CLGetFirstClutch( WORD chain );

/* Den folgenden Clutch erfragen */
VOID *CLGetNextClutch( WORD chain );

/**********************************************»*/
/* C_CLUTCH.C   (c) 1992 MAXON Computer         */
/*                                              */
/* Aufbau eines Clutchs:                        */
/* - 4 Bytes für 'prev'-Pointer                 */
/* - 4 Bytes für 'next'-Pointer                 */
/* - Übrige Datenbytes                          */
/* ('clutchsize' sind nur die Datenbytes!!)     */
/* Zurückgegeben wird der Datenbereich!!        */
/**********************************************»*/

#include <tos.h>

#include "clutch.h"

#define CL_PREV( a ) ( (VOID*)(((LONG*)a)[0]) )
#define CL_NEXT( a ) ( (VOID*)(((LONG*)a)[1]) )
#define CL_HDRSIZE  8L
#define CL_CHAINS   10

typedef struct 
{
    VOID *first,
         *query;
} CLUTCH;

WORD _clchains;

CLUTCH _clchain[CL_CHAINS];

MLOCAL VOID *_CLLastClutch( WORD chain );

70

1/1993

/************************************************/
/* Das Clutchmodul initialisieren               */
/************************************************/

BOOLEAN CLInitClutch( VOID )
{
    _clchains = 0; 

    return( TRUE );
}

/************************************************/
/* Eine Clutchliste initialisieren              */
/* Ergebnis: Eine ID <> -1                      */
/************************************************/

WORD CLInitChain( VOID )
{
    if( _clchains >= CL_CHAINS ) 
        return( -1 );

    _clchain[_clchain].first =
    _clchain[_clchain].query = 0L;

    ++_clchains;

    return( _clchains - 1 );
}

/************************************************/
/* Einen Clutch der Große 'clutchsize'          */
/* anhängen                                     */
/************************************************/

VOID *CLAddClutch( WORD chain, LONG clutchsize )
{
    VOID *prev, *new;

    /* Die Bytes für die Pointer addieren */ 
    clutchsize += 2 * sizeof( LONG ) + 1L;

    /* Den letzten Clutch bestimmen */ 
    prev = _CLLastClutch( chain );

    /* Speicher holen */
    new = Malloc( clutchsize );
    if( !new )
        return( 0L );

    /* Auf gerader Adresse anfangen lassen */ 
    if( (LONG)new % 2L )
        (LONG)new += 1L;

    /* Verketten */ 
    if( prev )
        CL_NEXT( prev ) = new;

    CL_PREV( new ) = prev;
    CL_NEXT( new ) = 0L;

    if( !prev )
        _clchain[chain].first = new;

    return( (VOID*)((LONG)new + CL_HDRSIZE) );
}



/************************************************/
/* Einen Clutch löschen */
/************************************************/

BOOLEAN CLClearClutch( VOID *clutch )
{
    WORD chain;
    VOID *c;

    /* Den wirklichen Beginn des Clutchs ermitteln */
    (LONG)clutch -= CL_HDRSIZE;



    for( chain = 0; chain < _clchains; chain++ )
        /* Wenn kein Clutch da ist, dann nächste Kette */ 
        if( (c = clchain[chain].first) != 0L )
        {
            /* Den Clutch suchen */
            while( CL_NEXT( c ) && ( c != clutch ) ) 
                c = CL_NEXT( c );

            if( c == clutch )
            {
                /* Jetzt die Verkettung lösen */ 
                if( c == _clchain[chain].first ) 
                    _clchain[chain].first = CL_NEXT( c );

                if( CL_NEXT( c ) )
                    CL_PREV( CL_NEXT( C ) ) = CL_PREV( c );

                if( CL_PREV( c ) )
                    CL_NEXT( CL_PREV( c ) ) = CL_NEXT( c );

                /* Und den Speicher freigeben */

                Mfree( c );

                return( TRUE );
            }
        }
    return( FALSE );
}

/************************************************/
/* Alle Clutches löschen */
/************************************************/
VOID CLClearAllClutches( VOID )
{
    WORD chain;
    VOID *c, *d;

    for( chain = 0; chain < _clchains; chain++ )
    {
        c = _clchain[chain].first;

        while( c )
        {
            d = CL_NEXT ( C ) ;
            Mfree( c );
            c = d;
        }
    }
}

/************************************************/
/* Den ersten Clutch erfragen                   */
/************************************************/

VOID *CLGetFirstClutch( WORD chain )
{
    VOID *query;


    query                 =
    _clchain[chain].query =
        _clchain[chain].first;

    if( query )
        return((VOID*)((LONG)query+CL_HDRSIZE)); 
    else
        return( 0L );
}

/************************************************/
/* Den folgenden Clutch erfragen                */
/************************************************/

VOID *CLGetNextClutch( WORD chain )
{
    VOID **query, *c;


    query = &_clchain[chain].query;

    if( !(*query) ) 
        return( 0L );

    c = CL_NEXT( *query );

    if ( c )
        *query = c;

    if ( c )
        return( (VOID*)((LONG)c + CL_HDRSIZE) ); 
    else
        return( 0L );
}

/************************************************/
/* Lokale Funktion */
/************************************************/

VOID *_CLLastClutch( WORD chain )
{
    VOID *c;

    c = _clchain[chain].first;

    /* Die Liste durchgehen */ 
    if ( c )
        while( CL_NEXT( c ) ) 
            c = CL_NEXT( c );

    return( c );

/* CLUTCH.PRJ */

CLUTCH.O

.L[-G]
.L[-L]
•L[-Y]
•L[-F]
.L[-J]

.C[-C]
.C[-Y]
.C[-K]
.C[-M]
.C[-P]

=

PCSTART.O

C_CLUTCH.C 

; Die Librarys 

PCSTDLIB.LIB 

PCEXTLIB.LIB
PCTOSLIB.LIB


/************************************************/
/* DEMO.C                                       */
/* Eine Demo für CLUTCH                         */
/* (c) 1992 MAXON Computer                      */
/************************************************/

#include <stdio.h>

#include "clutch.h"

WORD main()
{
    WORD id;
    VOID *c[3], *d;

    if( !CLInitClutch() ) 
        return( 0 );

    if ( (id = CLInitChain()) == -1 ) 
        return( 0 );

    /* Clutches anlegen */ 
    c[0] = CLAddClutch( id, 100L ); 
    c[1] = CLAddClutch( id, 100L ); 
    c[2] = CLAddClutch( id, 100L );

    /* Adresen ausgeben */ 
    printf( "%1d\n%1d\n%1d\ n\n\n", (LONG)c[0], (LONG)c[1], (LONG)c[2] );

    /* Adressen erfragen und ausgeben */ 
    d = CLGetPirstClutch( id );
    printf ( "%1d\n", (LONG) d );

    d = CLGetNextClutch( id ); 
    printf( "%1d\n", (LONG)d );

    d = CLGetNextClutch( id ); 
    printf( "%1d\n", (LONG)d );

    d = CLGetNextClutch( id ); 
    printf( "%1d\n", (LONG)d );

    d = CLGetNextClutch( id ); 
    printf( "%1d\n", (LONG)d );

    /* Und wieder löschen
       (auch mit 'CLClearAllClutches()' möglich) */ 
       CLClearClutch( c[1] );
       CLClearClutch( c[2] );
       CLClearClutch( c[0) );

        return( 0 );

/* DEMO.PRJ */

DEMO.TOS

.L[-G]
.L[-L]
.L[-Y]
.L[-F]

.C[-C]
.C[-Y]
.C[-K]
.C[-M]
.C[-P]

=

PCSTART.O 

DEMO.C

; Die Librarys 

CLUTCH.O

PCSTDLIB.LIB
PCEXTLIB.LIB 
PCTOSLIB.LIB

Marc René Gardeya
Aus: ST-Computer 01 / 1993, Seite 70

Links

Copyright-Bestimmungen: siehe Über diese Seite