linlist.h

X-tree的C++源码

    void check();               // ueberprueft die Konsistenz der Liste
};

template <class DATA> 
SortedLinList<DATA>::SortedLinList()
    : LinList<DATA>()
{ 
    increasing = TRUE; 
}


template <class DATA> 
void SortedLinList<DATA>::set_sorting(bool _increasing)
{
    increasing = _increasing;
}

template <class DATA> 
void SortedLinList<DATA>::check()
{
    SLink<DATA> *sd;
    DATA old;
    bool valid;          // falls TRUE, ist old mit einem Wert besetzt

    // Verkettung konsistent ?
    LinList<DATA>::check(); 

    // Sortierung korrekt ?
    valid = FALSE; 
    for (sd = first; sd != NULL; sd = sd->next)
    {
	 if (valid && (sd->d->distanz) < old.distanz)
         {
	     error("LinList::check: Liste unsortiert", FALSE);
	     return;
         }
	 valid = TRUE;
	 old = *(sd->d);
    }
    
}

template <class DATA> 
void SortedLinList<DATA>::insert(DATA *f)
{
    SLink<DATA> *sd;

    // Rahmen fuer neues Datenelement erzeugen
    sd = new SLink<DATA>;
    sd->d = f;

    // Liste leer?
    if (first == NULL)
    {
	first = sd;
	last = sd;
	anz = 1;
	sd->next = sd->prev = NULL;

	return;
    }

    // Einfuegestelle bestimmen
    if (increasing)
	for (akt = first; akt != NULL && (akt->d->distanz) < f->distanz;
				 akt = akt->next)
	    ;
    else
	for (akt = first; akt != NULL && akt->d->distanz > f->distanz; akt = akt->next)
	    ;

    // neues Element muss vor akt eingefuegt werden --> Zeiger umbiegen
    if (akt != NULL)
    {
	if (akt == first)
	    first = sd;
	else
	    (akt->prev)->next = sd;
	sd->next = akt;
	sd->prev = akt->prev;
	akt->prev = sd;
    }
    else
    // neues Element muss als letztes Element eingefuegt werden --> 
    // Zeiger umbiegen
    {
	sd->prev = last;
	sd->next = NULL;
	last->next = sd;
	last = sd;
    }

    // Gesamtanzahl erhoehen
    anz ++;
    akt_index = -1;
}


template <class DATA> 
void SortedLinList<DATA>::sort(bool _increasing)
// Bubblesort der ganzen Liste
{
    SLink<DATA> *old_akt;
    DATA *s;
    bool any, swap;

    set_sorting(_increasing);

    any = TRUE;
    while (any)
    {
	any = FALSE;
	old_akt = NULL;
	for (akt = first; akt != NULL; akt = akt->next)
	{
	    // beim ersten Element gibts nichts zu vergleichen
	    if (old_akt != NULL)
	    {
		swap = FALSE;
		if (_increasing)
		{
		    if ((akt->d->distanz) > (old_akt->d->distanz))
			swap = TRUE;
		}
		else
		{
		    if ((akt->d->distanz) < (old_akt->d->distanz))
			swap = TRUE;
		}

		if (swap)
		{
		    // es muessen nur die Datenpointer umgehaengt werden !
		    s = akt->d;
		    akt->d = old_akt->d;
		    old_akt->d = s;

		    // in diesem Durchlauf hat sich was getan --> 
		    // neuer Durchlauf
		    any = TRUE;
		}
	    }
	    old_akt = akt;
	}    
    }

    akt_index = -1;
}


////////////////////////////////////////////////////////////////////////
// PersistentList
////////////////////////////////////////////////////////////////////////
// fuegt zur Klasse LinList noch Funktionen hinzu, die es erlauben,
// die Hauptspeicherliste auf Platte zu speichern und wieder zu lesen.
// Hierzu muss das Listenelement die Funktionen:
// 
// read_from_buffer 
// write_to_buffer 
// write_data_header
// 
// zur Verfuegung stellen. Diese Funktionen braucht die Liste, da sie
// ja keinerlei Informationen ueber die innere Struktur der Datenelemente
// hat. Ein einfaches Speichern des gesamten Speicherbereichs des Elements
// auf Platte ist wegen des VTable-Pointers nicht moeglich und wegen der 
// Moeglichkeit, dass im Objekt Verweise auf andere Objekte gespeichert 
// sind, die bei einem erneuten Programmlauf und dem Laden der Liste
// keinen Sinn mehr machen wuerden. Um das Element beim Laden richtig 
// erzeugen zu koennen, steht vor jedem Element im File ein Header, 
// dessen Laenge ueber die virtuelle Funktion "get_data_header_size" 
// gesetzt werden kann. Ebenso steht am Anfang des Files ein 
// Header, der beliebig beschrieben werden kann. Um diese Features
// nutzen zu koennen, muss eine von PersistentList abgeleitete Klasse
// die folgenden Funktionen zur Verfuegung stellen:
// 
// get_header_size 
// get_data_header_size
// read_header
// write_header
// 
// Beim Lesen und Schreiben der Liste von Platte ruft PersistentList 
// die Funktion read/write_header mit einem Zeiger auf einen Puffer 
// auf. Die abgeleitete Klasse muss dann aus diesem Puffer ihre Daten 
// lesen bzw. schreiben. 
// Alle Objekte, die in diesem Container gespeichert werden, muessen
// einen Konstruktor KONSTRUKTOR(void *) zur Verfuegung stellen.
// Diesem werden die Headerdaten des einzelnen Elements uebergeben.
// Das File hat damit folgendes Format:
//
//  Byte           Bezeichnung             Inhalt
//  sizeof(int)    Headergroesse             h
//  sizeof(int)    Anzahl d. Elemente        n   
//  sizeof(int)    Datenheadergroesse       dh    
//  h              Header
//
//  n-mal 
//        sizeof(int)    Datengroesse             d
//        dh             Datenheader    
//        d              Daten
////////////////////////////////////////////////////////////////////////

template <class DATA> 
class PersistentList : public LinList<DATA>
{
protected:
    virtual int get_header_size()            // liefert Groesse des Headers
    { return 0;}
    virtual int get_data_header_size()       // liefert Groesse des Elementheaders
    { return 0;}
    virtual void read_header(void *buffer)   // liest Header in Objekt ein
    { }
    virtual void write_header(void *buffer)  // liest Header in Objekt ein
    { }
public:
    void save(char *name);      // speichert ganze Liste auf Platte
    void load(char *name);      // liest ganze Liste von Platte
};


template <class DATA> 
int PersistentList<DATA>::get_header_size()
{
    return 0;
}

template <class DATA> 
int PersistentList<DATA>::get_data_header_size()
{
    return 0;
}

template <class DATA> 
void PersistentList<DATA>::read_header(void *buffer)
{
}

template <class DATA> 
void PersistentList<DATA>::write_header(void *buffer)
{
}

template <class DATA> 
void PersistentList<DATA>::load(char *name)
{
    FILE *fp;
    DATA *d;
    void *buffer, *d_buffer, *header, *d_header;
    int header_size, num_elem, d_header_size, d_size;
    int i;

    // File oeffnen
    fp = fopen(name, "rb");
    if (!fp)
	return;

    // Headergroesse lesen
    if (fread(&header_size, sizeof(int), 1, fp) != 1)
	error("PersistentList::load: cannot read size of header from file", TRUE);

    // Elementzahl lesen
    if (fread(&num_elem, sizeof(int), 1, fp) != 1)
	error("PersistentList::load: cannot read number of elements from file", 
	      TRUE);

    // Datenheadergroesse lesen
    if (fread(&d_header_size, sizeof(int), 1, fp) != 1)
	error("PersistentList::load: cannot read size of data header from file", 
	      TRUE);

    // Header allokieren und einlesen
    header = new char[header_size];
    if (header_size > 0 && fread(header, header_size, 1, fp) != 1)
	error("PersistentList::save: cannot read  header from  file", 
              TRUE);
    read_header(header);

    // Datenheader allokieren
    d_header = new char[d_header_size];

    for (i = 0; i < num_elem; i++)
    {
	// Laenge des Elements einlesen
	if (fread(&d_size, sizeof(int), 1, fp) != 1)
	    error("PersistentList::load: cannot read element size from file", 
		  TRUE);

	// Datenheader einlesen
	if (d_header_size > 0 && fread(d_header, d_header_size, 1, fp) != 1)
	    error("PersistentList::load: cannot read data header from file", 
		  TRUE);

	// neues Element erzeugen
	d = new DATA(d_header);

	// Daten einlesen
	buffer = new char[d_size];
	if (d_size > 0 && fread(buffer, d_size, 1, fp) != 1)
	    error("PersistentList::load: cannot read data from file", 
		  TRUE);
	d->read_from_buffer(buffer);
	delete [] buffer;

	// Element in die Liste einfuegen
	insert(d);
    }

    // Puffer freigeben
    delete [] header;
    delete [] d_header;

    // File schliessen
    fclose(fp);
}

template <class DATA> 
void PersistentList<DATA>::save(char *name)
{
    FILE *fp;
    DATA *d;
    void *buffer, *d_buffer, *header, *d_header;
    int header_size, num_elem, d_header_size, d_size;
    int i;

    // File oeffnen
    fp = fopen(name, "wb");
    if (!fp)
	error("PersistentList::save: cannot open file for writing", TRUE);

    // Headergroesse schreiben
    header_size = get_header_size();
    if (fwrite(&header_size, sizeof(int), 1, fp) != 1)
	error("PersistentList::save: cannot write size of header to file", TRUE);

    // Elementzahl schreiben
    num_elem = get_num();
    if (fwrite(&num_elem, sizeof(int), 1, fp) != 1)
	error("PersistentList::save: cannot write number of elements to file", 
              TRUE);

    // Datenheadergroesse schreiben
    d_header_size = get_data_header_size();
    if (fwrite(&d_header_size, sizeof(int), 1, fp) != 1)
	error("PersistentList::save: cannot write size of data header to  file", 
              TRUE);

    // Header allokieren schreiben
    header = new char[header_size];
    write_header(header);
    if (header_size > 0 && fwrite(header, header_size, 1, fp) != 1)
	error("PersistentList::save: cannot write header to  file", 
              TRUE);

    // Datenheader allokieren
    d_header = new char[d_header_size];

    for (d = get_first(); d != NULL; d = get_next())
    {
	// Laenge des Elements schreiben
	d_size = d->get_size();
	if (fwrite(&d_size, sizeof(int), 1, fp) != 1)
	    error("PersistentList::save: cannot write element size to file", 
                  TRUE);

	// Datenheader schreiben
	d->write_data_header(d_header);
	if (d_header_size > 0 && fwrite(d_header, d_header_size, 1, fp) != 1)
	    error("PersistentList::save: cannot write data header to file", 
		  TRUE);

	// Daten schreiben
	buffer = new char[d_size];
	d->write_to_buffer(buffer);
	if (d_size > 0 && fwrite(buffer, d_size, 1, fp) != 1)
	    error("PersistentList::save: cannot read data from file", 
		  TRUE);
	delete [] buffer;
    }

    // Puffer freigeben
    delete [] header;
    delete [] d_header;

    // File schliessen
    fclose(fp);
}


#endif  // __LINLIST