include/tree.h

   1 /*
   2  * Copyright (c) 2006-2008 The LOST Project. All rights reserved.
   3  *
   4  * This code is derived from software contributed to the LOST Project
   5  * by Kevin Wolf.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. All advertising materials mentioning features or use of this software
  16  *    must display the following acknowledgement:
  17  *     This product includes software developed by the LOST Project
  18  *     and its contributors.
  19  * 4. Neither the name of the LOST Project nor the names of its
  20  *    contributors may be used to endorse or promote products derived
  21  *    from this software without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  25  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  26  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
  27  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  28  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  29  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  30  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  31  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  32  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  33  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 #ifndef _TREE_H_
  37 #define _TREE_H_
  38
  39 //#include <sys/types.h>
  40 #include <stdint.h>
  41 #include <stddef.h>
  42
  43 /**
  44  * Repraesentiert einen Knoten und bestimmt seine Position im Baum.
  45  *
  46  * Diese Struktur muss in jedem Typ, der in Baeumen verwendet werden soll,
  47  * als Teil enthalten sein. Durch den Offset, den das tree_item in dem
  48  * jeweiligen Typ hat, kann ein Pointer auf den Anfang des Objekts berechnet
  49  * werden.
  50  */
  51 struct tree_item {
  52     struct tree_item* parent;
  53     struct tree_item* left;
  54     struct tree_item* right;
  55     int balance;
  56 };
  57
  58 /**
  59  * Repraesentiert den Baum und erlaubt den Zugriff auf seine Elemente.
  60  *
  61  * Ein Baum besteht aus Objekten eines einheitlichen Datentyps. Die Objekte
  62  * enthalten jeweils mindestens ein tree_item, das Vater und Kinder sowie den
  63  * AVL-Balancewert ihres Knotens beschreibt und einen Schluessel, nach dem der
  64  * Baum sortiert wird. Der Schluessel muss vom Typ uint64_t sein.
  65  */
  66 typedef struct {
  67     struct tree_item*   root;
  68     size_t              tree_item_offset;
  69     size_t              sort_key_offset;
  70 } tree_t;
  71
  72 /**
  73  * Erzeugt einen neuen AVL-Baum
  74  *
  75  * @param type Datentyp der Objekte im Baum
  76  * @param tree_item Name des tree_item-Felds in der Struktur der Objekte
  77  * @param sort_key Name des Schluessels in der Struktur der Objekte
  78  */
  79 #define tree_create(type, tree_item, sort_key) \
  80     tree_do_create(offsetof(type, tree_item), offsetof(type, sort_key))
  81
  82 /**
  83  * Erzeugt einen neuen AVL-Baum. Nicht direkt verwenden, tree_create ist das
  84  * Mittel der Wahl.
  85  */
  86 tree_t* tree_do_create(size_t tree_item_offset, size_t sort_key_offset);
  87
  88 /**
  89  * Gibt einen AVL-Baum frei. Zu beachten ist, dass keiner seiner Knoten
  90  * freigegeben wird, da ein Knoten immer noch ueber eine andere Datenstruktur
  91  * erreichbar sein koennte.
  92  */
  93 void tree_destroy(tree_t* tree);
  94
  95 /**
  96  * Sucht nach dem Objekt mit einem gegebenen Schluessel in einem AVL-Baum
  97  *
  98  * @return Objekt mit dem gesuchten Schluessel oder NULL, wenn kein Objekt mit
  99  * dem gesuchten Schluessel im Baum enthalten ist.
 100  */
 101 void* tree_search(tree_t* tree, uint64_t key);
 102
 103 /**
 104  * Fuegt ein neues Objekt in den AVL-Baum ein.
 105  *
 106  * @param node Einzufuegendes Objekt. Muss den in tree_create angegebenen
 107  * Datentyp haben, ansonsten ist das Ergebnis undefiniert.
 108  */
 109 tree_t* tree_insert(tree_t* tree, void* node);
 110
 111 /**
 112  * Entfernt ein Objekt aus dem AVL-Baum. Das uebergebene Objekt muss im Baum
 113  * enthalten sein.
 114  *
 115  * @return Das zu entfernende Objekt
 116  */
 117 void* tree_remove(tree_t* tree, void* node);
 118
 119 /**
 120  * Sucht zu einem gegebenen Objekt den Vorgaenger.
 121  *
 122  * Der Vorgaenger ist das Objekt mit dem naechstkleineren Schluessel. Der
 123  * Vorgaenger von NULL ist das Objekt mit dem groessten Schluessel.
 124  *
 125  * @return Das Vorgaengerobjekt oder NULL, wenn das uebergebene Objekt das
 126  * Objekt mit dem kleinsten Schluessel war.
 127  */
 128 void* tree_prev(tree_t* tree, void* node);
 129
 130 /**
 131  * Sucht zu einem gegebenen Objekt den Nachfolger
 132  *
 133  * Der Nachfolger ist das Objekt mit dem naechstgroesseren Schluessel. Der
 134  * Nachfolger von NULL ist das Objekt mit dem kleinsten Schluessel.
 135  *
 136  * @return Das Nachfolgerobjekt oder NULL, wenn das uebergebene Objekt das
 137  * Objekt mit dem groessten Schluessel war.
 138  */
 139 void* tree_next(tree_t* tree, void* node);
 140
 141 #endif