[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[tyndur-devel] [PATCH libext2 5/8] testlib: CDI-Cache aktualisiert



Aktuelle Version aus tyndur zurückkopiert.

Signed-off-by: Kevin Wolf <kevin@xxxxxxxxxx>
---
 testlib/cache.c     |   2 +-
 testlib/cdi_cache.c | 836 ++++++++++++----------------------------------------
 testlib/cdi_cache.h | 100 +------
 testlib/tree.c      | 599 +++++++++++++++++++++++++++++++++++++
 testlib/tree.h      | 165 +++++++++++
 5 files changed, 967 insertions(+), 735 deletions(-)
 create mode 100644 testlib/tree.c
 create mode 100644 testlib/tree.h

diff --git a/testlib/cache.c b/testlib/cache.c
index 0f172c5..f22cc8e 100644
--- a/testlib/cache.c
+++ b/testlib/cache.c
@@ -116,7 +116,7 @@ ext2_cache_block_t* cache_block(void* handle, uint64_t block, int noread)
     struct cdi_cache_block* cdi_b;
     ext2_cache_block_t* b;
 
-    if (!(cdi_b = cdi_cache_block_get(c, block))) {
+    if (!(cdi_b = cdi_cache_block_get(c, block, noread))) {
         return NULL;
     }
 
diff --git a/testlib/cdi_cache.c b/testlib/cdi_cache.c
index 2b9361b..919cf61 100644
--- a/testlib/cdi_cache.c
+++ b/testlib/cdi_cache.c
@@ -12,38 +12,27 @@
 #include <stdlib.h>
 #include <string.h>
 
-#define __LOST__
+//#define __LOST__
 #undef __LOST__
 
 #ifdef __LOST__
     #include "cdi.h"
     #include "cdi/misc.h"
-    #include "cdi/cache.h"
+    #include <collections.h>
 #else
-    #include "cdi_cache.h"
+    #include "tree.h"
 #endif
-
+#include "cdi_cache.h"
 
 #define INVBLKNUM (~0L)
 #define READBUF_SZ 128
+#define HINTCNT 8
 
-static uint64_t cache_time = 0;
 #ifdef __LOST__
     static cdi_list_t cache_list = NULL;
 #endif
 
 /**
- * Hints fuer die Suche im Cache
- */
-struct hint {
-    /** Index */
-    size_t      index;
-
-    /** Block der dort gefunden werden kann */
-    uint64_t    block;
-};
-
-/**
  * Block im Cache
  */
 struct block {
@@ -56,8 +45,15 @@ struct block {
     /** Wird auf 1 gesetzt, wenn die Daten veraendert wurden */
     uint16_t                dirty;
 
-    /** Zeit der letzten Benutzung */
-    uint64_t                access_time;
+    /** Zeiger auf das naechste Element in der nach der letzten Benutzung
+        sortierten Liste. */
+    struct block*           lru_next;
+
+    /** Zeiger auf das naechste Element in der nach der letzten Benutzung
+        sortierten Liste. */
+    struct block*           lru_prev;
+
+    struct tree_item        tree_item;
 };
 
 /**
@@ -67,18 +63,15 @@ struct cache {
     /** Eigentliches Cache-Handle */
     struct cdi_cache    cache;
 
+    /** Groesse der Privaten Daten pro Block */
+    size_t              private_len;
+
     /** Anzahl der Blocks */
     size_t              block_count;
 
     /** Anzahl der benutzten Blocks */
     size_t              blocks_used;
 
-    /** Blockliste sortiert nach offset */
-    struct block**      blocks_ordered;
-
-    /** Blockliste */
-    struct block*       blocks;
-
 
     /** Callback zum Lesen eines Blocks */
     cdi_cache_read_block_t* read_block;
@@ -90,48 +83,36 @@ struct cache {
     void*               prv_data;
 
 
-    /** Lesepuffer */
-    uint8_t*            read_buffer;
+    /** Baum mit den Blocks */
+    tree_t*             tree;
 
-    /** Erster Block im Lesepuffer oder INVBLKNUM wenn keiner */
-    uint64_t            read_buffer_block;
 
-    /** Anzahl Blocks die im Puffer sind */
-    size_t              read_buffer_cnt;
+    /** Der am laengsten nicht mehr benutzte Block */
+    struct block*       lru_first;
 
+    /** Der zuletzt benutzte Block */
+    struct block*       lru_last;
 
-    /** Hints fuer Positionen */
-    struct hint         hints[8];
 
-    /** Zuletzt geschriebener hint-index */
-    uint16_t            prev_hint;
-};
 
-/**
- * Cache-eintrag
- */
-struct entry {
-    /** Eigentlicher CDI-Cache-Eintrag */
-    struct cdi_cache_entry  entry;
+    /** Lesepuffer */
+    uint8_t*            read_buffer;
 
-    /** Offset */
-    uint64_t                offset;
+    /** Erster Block im Lesepuffer oder INVBLKNUM wenn keiner */
+    uint64_t            read_buffer_block;
 
-    /** Groesse des Bereichs */
-    size_t                  size;
+    /** Anzahl Blocks die im Puffer sind */
+    size_t              read_buffer_cnt;
 
-    /** Anzahl der Blocks */
-    size_t                  block_count;
 
-    /** Pointer auf ein Array mit Blockpointern */
-    struct block**          blocks;
+    /** Hints */
+    struct block*        hints[HINTCNT];
 
-    /** Gesperrt */
-    int                     locked;
+    /** Letzter abgefragter Hint */
+    uint8_t             prev_hint;
 };
 
 
-
 /**
  * Cache erstellen
  *
@@ -153,7 +134,7 @@ struct cdi_cache* cdi_cache_create(size_t block_size, size_t blkpriv_len,
     void* prv_data)
 {
     struct cache* cache = malloc(sizeof(*cache));
-    size_t i;
+    int i;
 
     cache->read_block = read_block;
     cache->write_block = write_block;
@@ -161,34 +142,28 @@ struct cdi_cache* cdi_cache_create(size_t block_size, size_t blkpriv_len,
 
     // FIXME
     cache->cache.block_size = block_size;
-    cache->block_count = 1 * 1024 * 1024 / cache->cache.block_size;
+    cache->block_count = 256;
     cache->blocks_used = 0;
+    cache->private_len = blkpriv_len;
 
     cache->read_buffer = malloc(cache->cache.block_size * READBUF_SZ);
     cache->read_buffer_block = INVBLKNUM;
     cache->read_buffer_cnt = 0;
 
-    memset(cache->hints, 0, sizeof(cache->hints));
-    cache->prev_hint = 0;
-
+    cache->lru_first = NULL;
+    cache->lru_last = NULL;
 
-    cache->blocks = malloc(sizeof(struct block) * cache->block_count);
-    cache->blocks_ordered = malloc(sizeof(struct block*) * cache->block_count);
-    for (i = 0; i < cache->block_count; i++) {
-        struct block* block = cache->blocks + i;
-        cache->blocks_ordered[i] = block;
+    cache->tree = tree_create(struct block, tree_item, cdi.number);
 
-        block->cdi.number = INVBLKNUM;
-        block->cdi.data = malloc(cache->cache.block_size);
-        block->cdi.private = malloc(blkpriv_len);
-
-        block->ref_count = 0;
-        block->dirty = 0;
+    // Hints initialisieren
+    cache->prev_hint = 0;
+    for (i = 0; i < HINTCNT; i++) {
+        cache->hints[i] = NULL;
     }
 
-    // Cache in die Liste eintragen damit er Synchronisiert wird
 #ifdef __LOST__
-    if (cache_list == NULL) {
+    // Cache in Liste eintragen damit er gesynct wird
+    if (!cache_list) {
         cache_list = cdi_list_create();
     }
     cdi_list_push(cache_list, cache);
@@ -203,21 +178,20 @@ struct cdi_cache* cdi_cache_create(size_t block_size, size_t blkpriv_len,
 void cdi_cache_destroy(struct cdi_cache* cache)
 {
     struct cache* c = (struct cache*) cache;
-    struct block* b;
-    int i;
+    struct block* b = NULL;
 
     if (!cdi_cache_sync(cache)) {
         puts("cdi_cache: Sync fehlgeschlagen vor dem Zerstoeren!");
     }
 
     // Einzelne Blocks freigeben
-    for (i = 0; i < c->block_count; i++) {
-        b = c->blocks + i;
+    while ((b = tree_next(c->tree, NULL))) {
 
+        tree_remove(c->tree, b);
         if (b->ref_count) {
             printf("cdi_cache: Beim Zerstoeren des Caches wurde ein Block "
-                "gefunden, der einen Referenzzaehler != 0 hat (%lld)\n",
-                (unsigned long long) b->cdi.number);
+                "gefunden, der einen Referenzzaehler != 0 hat (%lld  %d)\n",
+                (unsigned long long) b->cdi.number, b->ref_count);
         }
 
         if (b->dirty) {
@@ -228,11 +202,9 @@ void cdi_cache_destroy(struct cdi_cache* cache)
 
         free(b->cdi.data);
         free(b->cdi.private);
+        free(b);
     }
 
-    free(c->blocks);
-    free(c->blocks_ordered);
-    free(c->read_buffer);
     free(c);
 }
 
@@ -284,18 +256,9 @@ static inline int cache_sync_block(struct cache* c, struct block* b)
 int cdi_cache_sync(struct cdi_cache* cache)
 {
     struct cache* c = (struct cache*) cache;;
-    struct block* b;
-    size_t i;
-
-    for (i = 0; i < c->block_count; i++) {
-        b = c->blocks_ordered[i];
-
-        // Sobald ein Eintrag mit INVBLKNUM erreicht wird, ist das Durchsuchen
-        // beendet
-        if (b->cdi.number == INVBLKNUM) {
-            return 1;
-        }
+    struct block* b = NULL;
 
+    while ((b = tree_prev(c->tree, b))) {
         cache_sync_block(c, b);
     }
 
@@ -306,7 +269,7 @@ int cdi_cache_sync(struct cdi_cache* cache)
 /**
  * Caches Synchronisieren
  */
-void caches_sync_all()
+void caches_sync_all(void)
 {
     size_t i;
     struct cache* c;
@@ -323,63 +286,27 @@ void caches_sync_all()
 }
 #endif
 
+
 /**
- * Sucht das Element mit dem Enstprechenden Index, oder falls keines mit
- * diesem Index existiert, wird die Stelle angegeben an der es stehen muesste
- *
- * @param block Blocknummer des gesuchten Elements
- * @param dest  Pointer auf die Variable, in der der gefundene Index abgelegt
- *              werden soll.
- *
- * @return 1 bei Erfolg, 0 sonst
+ * Block finden der ersetzt werden kann. Dieser wird dabei aus der LRU-Liste
+ * geloescht.
  */
-static size_t search_position(struct cache* cache, uint64_t block,
-    size_t* dest)
+static struct block* find_replaceable(struct cache* c)
 {
-    size_t top = cache->blocks_used - 1;
-    size_t bottom = 0;
-    size_t pos;
+    struct block* b;
 
-    // Pruefen ob offset ueberhaupt im Array enthalten ist
-    if (block < cache->blocks_ordered[0]->cdi.number) {
-        *dest = 0;
-        return 0;
-    } else if (block > cache->blocks_ordered[top]->cdi.number) {
-        // Wenn noch freie Blocks im Cache existieren wird der Index auf den
-        // naechst freien gelegt
-        if (top < cache->block_count - 1) {
-            top++;
-        }
-        *dest = top;
-        return 0;
+    // Unbenutzten Block finden
+    b = c->lru_first;
+    while (b && (b->ref_count)) {
+        b = b->lru_prev;
     }
 
-    // Binaere Suche nach dem Element
-    do {
-        pos = bottom + (top - bottom) / 2;
-
-        if (cache->blocks_ordered[pos]->cdi.number == block) {
-            break;
-        } else if (cache->blocks_ordered[pos]->cdi.number > block) {
-            top = pos - 1;
-        } else {
-            bottom = pos + 1;
-            // Falls hier gleich abgebrochen wird, muss pos auf ein Element
-            // zeigen, das nicht groesser ist, als das Gesuchte
-            pos = bottom;
-        }
-    } while (top >= bottom);
-
-    if (pos >= cache->block_count) {
-        pos = cache->block_count - 1;
+    if (b && b->dirty) {
+        cdi_cache_sync((struct cdi_cache*) c);
     }
-
-    *dest = pos;
-
-    return (cache->blocks_ordered[pos]->cdi.number == block);
+    return b;
 }
 
-
 /**
  * Hint suchen fuer eine Blocknummer
  *
@@ -387,17 +314,17 @@ static size_t search_position(struct cache* cache, uint64_t block,
  *
  * @return Index oder (size_t) -1 im Fehlerfall
  */
-static inline size_t get_hint(struct cache* cache, uint64_t block)
+static inline struct block* get_hint(struct cache* cache, uint64_t block)
 {
     int i;
 
-    for (i = 0; i < sizeof(cache->hints) / sizeof(struct hint); i++) {
-        if (cache->hints[i].block == block) {
-            return cache->hints[i].index;
+    for (i = 0; i < HINTCNT; i++) {
+        if (cache->hints[i] && (cache->hints[i]->cdi.number == block)) {
+            return cache->hints[i];
         }
     }
 
-    return -1;
+    return NULL;
 }
 
 /**
@@ -406,290 +333,168 @@ static inline size_t get_hint(struct cache* cache, uint64_t block)
  * @param block Blocknummer
  * @param index Index an dem der Block gefunden werden kann
  */
-static inline void put_hint(struct cache* cache, uint64_t block, size_t index)
+static inline void put_hint(struct cache* cache, struct block* block)
 {
     cache->prev_hint++;
-    cache->prev_hint %= sizeof(cache->hints) / sizeof(struct hint);
-    cache->hints[cache->prev_hint].block = block;
-    cache->hints[cache->prev_hint].index = index;
-}
-
-/**
- * Block in der Liste finden
- *
- * @param cache Handle
- * @param block Blocknummer
- *
- * @return Pointer auf den Block oder NULL wenn er nicht in der Liste ist
- */
-static inline struct block* block_find(struct cache* cache, uint64_t block)
-{
-    size_t i;
-
-    i = get_hint(cache, block);
-    if ((i != -1) && (cache->blocks_ordered[i]->cdi.number == block)) {
-        return cache->blocks_ordered[i];
-    }
-
-    if (!search_position(cache, block, &i)) {
-        return NULL;
-    }
-
-    put_hint(cache, block, i);
-    return cache->blocks_ordered[i];
+    cache->prev_hint %= HINTCNT;
+    cache->hints[cache->prev_hint] = block;
 }
 
-
 /**
- * Cache-Element zum ersetzen finden
- *
- * @param blocknum Blocknummer des neuen Elements
- *
- * @return Array-Index des Elements das erstezt werden kann oder block_count
- * wenn keines gefunden wurde.
+ * Block von der Platte laden.
  */
-static inline size_t find_replaceable(struct cache* cache, uint64_t blocknum)
+static int load_block(struct cache* c, struct block* b)
 {
-    struct block* b = NULL;
-    size_t i;
-    size_t la_index = cache->block_count;
-
-    // Wenn noch unbenzte Blocks existieren, dann gehoert der letzte sicher dazu
-    if (cache->blocks_ordered[cache->block_count - 1]->cdi.number == INVBLKNUM)
+    size_t block_size = c->cache.block_size;
+    uint64_t rbbnum = c->read_buffer_block;
+    uint64_t block = b->cdi.number;
+
+    // Wenn der zu lesende Block nicht im Puffer ist, wird er in den Puffer
+    // eingelesen
+    if ((rbbnum == INVBLKNUM) || (rbbnum > block) || (block >= rbbnum +
+        c->read_buffer_cnt))
     {
-        return cache->block_count - 1;
-    }
+        size_t sync_size = READBUF_SZ;
+        size_t recyclable = 0;
 
-    for (i = 0; i < cache->blocks_used; i++) {
-        b = cache->blocks_ordered[i];
+        // Wenn der Block nur kurz vor dem Cache liegt, kann man auch einen
+        // Teil des Caches wiederverwenden
+        if ((block < rbbnum) && (block > rbbnum - READBUF_SZ)) {
+            sync_size = rbbnum - block;
+            recyclable = READBUF_SZ - sync_size;
 
-        // Solte nicht passieren
-        if (b->cdi.number == INVBLKNUM) {
-            puts("cdi_cache: Hier ist ein Element mit ungueltiger Blocknummer "
-                "mitten im Array!");
-            printf("%u\n", (unsigned int) i);
-            continue;
-        }
-
-        // Pruefen ob das Element prinzipiell ersetzt werden darf, wenn nicht,
-        // wird zum naechsten gesprungen
-        if (b->ref_count) {
-            continue;
+            memmove((uint8_t*) c->read_buffer + sync_size * block_size,
+                c->read_buffer, recyclable * block_size);
         }
 
-        // Wenn bis jetzt noch kein passendes Element gefunden wurde, dann muss
-        // es genommen werden. Andernfalls wird geprueft ob das element aelter
-        // ist
-        if ((la_index == cache->block_count) || (b->access_time <
-            cache->blocks_ordered[la_index]->access_time))
-        {
-            la_index = i;
-        }
-    }
-
-    // Falls das Element dirty ist, muss es gespeichert werden
-    if ((la_index != cache->block_count) &&
-        (cache->blocks_ordered[la_index]->dirty))
-    {
-        cache_sync_block(cache, cache->blocks_ordered[la_index]);
-    }
-    return la_index;
-}
-
-/**
- * Block im Cache allozieren und initialisieren
- *
- * @param cache     Handle
- * @param blocknum  Blocknummer des neuen Blocks
- * @param index     Pointer auf Speicherstelle, an der der Listenindex
- *                  abgespeichert werden soll.
- *
- * @return 1 wenn ein Element gefunden wurde, 0 sonst
- */
-static inline size_t block_allocate(struct cache* cache, uint64_t blocknum,
-    size_t* index)
-{
-    struct block* b;
-    //void* data;
-    //void* private;
-
-    // Index an dem der neue Block spaeter im Array liegt
-    size_t dest;
-
-    // Index des Blocks, der ersetzt werden soll
-    size_t i;
+        c->read_buffer_block = rbbnum = block;
 
+        c->read_buffer_cnt = c->read_block(
+            (struct cdi_cache*) c, block, sync_size,
+            c->read_buffer, c->prv_data);
 
-    // Position suchen an der der neue Block spaeter im Array liegen soll
-    if (search_position(cache, blocknum, &dest)) {
-        puts("cdi_cache: Warnung: Block, der bereits im Cache ist, soll"
-           " alloziert werden.");
-        *index = dest;
-        return 1;
-    }
-
-    // Element finden, das ersetzt werden soll
-    i = find_replaceable(cache, blocknum);
-    //printf("Replaceable: %d", i);
-    if (i == cache->block_count) {
-        return 0;
-    }
-
-    // Wenn der Block bisher nicht benutzt wurde, muss used Blocks erhoeht
-    // werden
-    if (cache->blocks_ordered[i]->cdi.number == INVBLKNUM) {
-        cache->blocks_used++;
-    }
-
-    // Pointer auf daten des zu ersetzenden Blocks speichern, da die
-    // ueberschrieben werden, beim memmove
-    /*data = cache->blocks[i].cdi.data;
-    private = cache->blocks[i].cdi.private;*/
-    b = cache->blocks_ordered[i];
-
-    // Jetzt muessen die Array-Elemente so verschoben werden, dass die stelle an
-    // mit dem index dest frei wird und dafuer die mit index i ueberschrieben
-    // wird
-    if (i < dest) {
-        // Wenn wir die Elemente nach unten verschieben, muss das zielelement
-        // kleiner sein, als das aktuelle
-        if ((cache->blocks[dest].cdi.number > blocknum) && (dest > 0)) {
-            dest--;
+        if (recyclable && (c->read_buffer_cnt < sync_size)) {
+            // Cache jetzt komplett einlesen, weil Lücken doof sind.
+            c->read_buffer_cnt = c->read_block(
+                (struct cdi_cache*) c, block, READBUF_SZ,
+                c->read_buffer, c->prv_data);
+        } else if (recyclable) {
+            c->read_buffer_cnt += recyclable;
         }
 
-        memmove(cache->blocks_ordered + i, cache->blocks_ordered + i + 1,
-            (dest - i) * sizeof(struct block*));
-    } else if (i > dest) {
-        // Wenn wird die Elemente nach oben verschieben, muss das zielelement
-        // groesser sein, als das aktuelle
-        if ((cache->blocks_ordered[dest]->cdi.number < blocknum) &&
-            (dest < cache->block_count - 1))
-        {
-            dest++;
+        if (c->read_buffer_cnt == 0) {
+            puts("cdi_cache Panic: Einlesen der Daten fehlgeschlagen");
+            return 0;
         }
-
-        memmove(cache->blocks_ordered + dest + 1, cache->blocks_ordered + dest,
-            (i - dest) * sizeof(struct block*));
     }
+    memcpy(b->cdi.data, c->read_buffer + (block - rbbnum) * block_size,
+        block_size);
 
-    cache->blocks_ordered[dest] = b;
-    // b->cdi.data = data;
-    b->cdi.number = blocknum;
-    // b->cdi.private = private;
-    b->access_time = ++cache_time;
-    b->dirty = 0;
-    b->ref_count = 0;
-    *index = dest;
     return 1;
 }
 
 /**
- * Neuen block laden, der noch nicht in der Liste ist
+ * Cache-Block holen. Dabei wird intern ein Referenzzaehler erhoeht, sodass der
+ * Block nicht freigegeben wird, solange er benutzt wird. Das heisst aber auch,
+ * dass der Block nach der Benutzung wieder freigegeben werden muss, da sonst
+ * die freien Blocks ausgehen.
  *
- * @param cache Handle
- * @param block Blocknummer
- * @param read  Wenn 1 dann muss der Block eingelesen werden, bei 0 wird nur
- *              ein freier Block herausgesucht (Wenn er eh ganz ueberschrieben
- *              wird)
+ * @param cache     Cache-Handle
+ * @param blocknum  Blocknummer
+ * @param noread    Wenn != 0 wird der Block nicht eingelesen falls er noch
+ *                  nicht im Speicher ist. Kann benutzt werden, wenn der Block
+ *                  vollstaendig ueberschrieben werden soll.
  *
- * @return Pointer auf den Block
+ * @return Pointer auf das Block-Handle oder NULL im Fehlerfall
  */
-static inline struct block* block_load(struct cache* cache, uint64_t block,
-    int read)
+struct cdi_cache_block* cdi_cache_block_get(struct cdi_cache* cache,
+    uint64_t blocknum, int noread)
 {
-    size_t index;
-    struct block* b;
-    size_t block_size = cache->cache.block_size;
+    struct cache* c = (struct cache*) cache;
+    struct block* b = get_hint(c, blocknum);
 
-    if (!block_allocate(cache, block, &index)) {
-        puts("cdi_cache Panic: Kein Unbenutztes Element gefunden");
-        return NULL;
+    // Wenn das mit dem Hint nichts war muss jetzt der Baum durchsucht werden
+    if (!b) {
+        b = tree_search(c->tree, blocknum);
     }
 
-    b = cache->blocks_ordered[index];
-
-    if (read) {
-        uint64_t bnum = cache->read_buffer_block;
-
-        // Wenn der zu lesende Block nicht im Puffer ist, wird er in den Puffer
-        // eingelesen
-        if ((bnum == INVBLKNUM) || (bnum > block) || (block >= bnum +
-            cache->read_buffer_cnt))
-        {
-            cache->read_buffer_block = bnum = block;
-
-            cache->read_buffer_cnt = cache->read_block(
-                (struct cdi_cache*) cache, block, READBUF_SZ,
-                cache->read_buffer, cache->prv_data);
-
-            if (cache->read_buffer_cnt == 0) {
-                puts("cdi_cache Panic: Einlesen der Daten fehlgeschlagen");
+    if (!b) {
+        int in_tree = 0;
+        if (c->blocks_used < c->block_count) {
+            // Wir duerfen noch mehr neue Blocks in den Cache legen
+            b = malloc(sizeof(*b));
+            memset(b, 0, sizeof(*b));
+            b->cdi.number = blocknum;
+            b->cdi.data = malloc(c->cache.block_size);
+            b->cdi.private = malloc(c->private_len);
+
+            tree_insert(c->tree, b);
+            c->blocks_used++;
+        } else {
+            // Wir muessen einen Block zum ersetzen suchen
+            b = find_replaceable(c);
+            if (!b) {
                 return NULL;
             }
-            //puts("nomatch");
-        } else {
-            //puts("match");
+            in_tree = 1;
+            tree_remove(c->tree, b);
+            b->cdi.number = blocknum;
+            tree_insert(c->tree, b);
         }
 
-        memcpy(b->cdi.data, cache->read_buffer + (block - bnum) * block_size,
-            block_size);
-    }
+        // Block einlesen
+        if (!noread && !load_block(c, b)) {
+            puts("cdi_cache: Einlesen des Blocks fehlgeschlagen.");
+
+            // Wenn der Knoten bis jetzt im Baum war, muss er rausgeworfen
+            // werden
+            if (in_tree) {
+                tree_remove(c->tree, b);
+
+                // Auch aus der LRU-Liste muss der Block ggf. entfernt werden
+                if (b->lru_next) {
+                    b->lru_next->lru_prev = b->lru_prev;
+                }
+                if (b->lru_prev) {
+                    b->lru_prev->lru_next = b->lru_next;
+                }
+            }
+            c->blocks_used--;
 
-    return b;
-}
+            free(b->cdi.data);
+            free(b->cdi.private);
+            free(b);
+            return NULL;
+        }
+    }
+    put_hint(c, b);
 
-/**
- * Block holen; Falls er noch nicht in der Liste ist, wird er geladen
- *
- * @param cache Handle
- * @param block Blocknummer
- * @param read  Wenn 1 dann muss der Block eingelesen werden, bei 0 wird nur
- *              ein freier Block herausgesucht (Wenn er eh ganz ueberschrieben
- *              wird)
- *
- *
- * @return Pointer auf den Block
- */
-static inline struct block* get_block(struct cache* cache, uint64_t block,
-    int read)
-{
-    struct block* b;
+    b->ref_count++;
 
-    if (!(b = block_find(cache, block))) {
-        b = block_load(cache, block, read);
+    // Wenn wir eh schon den juengsten Block in der Liste erwischt haben,
+    // muessen wir auch an der LRU-Liste nichts mehr aendern.
+    if (b == c->lru_last) {
+        return (struct cdi_cache_block*) b;
     }
 
-    if (b) {
-        b->access_time = ++cache_time;
+    // LRU-Liste aktualisieren
+    if (b->lru_next) {
+        b->lru_next->lru_prev = b->lru_prev;
     }
-
-
-    return b;
-}
-
-
-
-/**
- * Cache-Block holen. Dabei wird intern ein Referenzzaehler erhoeht, sodass der
- * Block nicht freigegeben wird, solange er benutzt wird. Das heisst aber auch,
- * dass der Block nach der Benutzung wieder freigegeben werden muss, da sonst
- * die freien Blocks ausgehen.
- *
- * @param cache     Cache-Handle
- * @param blocknum  Blocknummer
- *
- * @return Pointer auf das Block-Handle oder NULL im Fehlerfall
- */
-struct cdi_cache_block* cdi_cache_block_get(struct cdi_cache* cache,
-    uint64_t blocknum)
-{
-    struct block* b = get_block((struct cache*) cache, blocknum, 1);
-
-    if (!b) {
-        return NULL;
+    if (b->lru_prev) {
+        b->lru_prev->lru_next = b->lru_next;
     }
-
-    b->ref_count++;
+    if (c->lru_first == b) {
+        c->lru_first = b->lru_prev;
+    }
+    b->lru_next = c->lru_last;
+    b->lru_prev = NULL;
+    if (c->lru_last) {
+        c->lru_last->lru_prev = b;
+    } else {
+        c->lru_first = b;
+    }
+    c->lru_last = b;
 
     return (struct cdi_cache_block*) b;
 }
@@ -722,260 +527,3 @@ void cdi_cache_block_dirty(struct cdi_cache* cache,
 }
 
 
-
-
-/**
- * Cache-Eintrag erstellen
- *
- * @param offset    Position auf dem Datentraeger
- * @param size      Groesse des Bereichs
- *
- * @return Handle
- */
-struct cdi_cache_entry* cdi_cache_entry_new(struct cdi_cache* cache,
-    uint64_t offset, size_t size)
-{
-    struct entry* entry = malloc(sizeof(struct entry));
-    size_t block_size = cache->block_size;
-    uint64_t start_block = offset / block_size;
-    uint64_t end_block = (offset + size - 1) / block_size;
-
-    entry->entry.cache = cache;
-    entry->locked = 0;
-    entry->offset = offset;
-    entry->size = size;
-    entry->block_count = end_block - start_block + 1;
-    entry->blocks = calloc(sizeof(struct block*) * entry->block_count, 1);
-
-    return (struct cdi_cache_entry*) entry;
-}
-
-/**
- * Cache-Eintrag freigeben
- *
- * @param entry Handle
- */
-void    cdi_cache_entry_release(struct cdi_cache_entry* entry)
-{
-    struct entry* e = (struct entry*) entry;
-    size_t i;
-
-    if (e->locked) {
-        cdi_cache_entry_unlock(entry);
-    }
-
-    for (i = 0; i < e->block_count; i++) {
-        struct block* block = e->blocks[i];
-        if (block) {
-            block->ref_count--;
-        }
-    }
-
-    free(e);
-}
-
-/**
- * Cache-Eintrag sperren
- *
- * @param entry Handle
- */
-void    cdi_cache_entry_lock(struct cdi_cache_entry* entry)
-{
-    struct entry* e = (struct entry*) entry;
-    e->locked = 1;
-}
-
-/**
- * Cache-Eintrag entsperren
- *
- * @param entry Handle
- */
-void    cdi_cache_entry_unlock(struct cdi_cache_entry* entry)
-{
-    struct entry* e = (struct entry*) entry;
-    e->locked = 0;
-}
-
-/**
- * Cache-Eintrag als veraendert markieren
- *
- * @param entry Handle
- */
-void    cdi_cache_entry_dirty(struct cdi_cache_entry* entry)
-{
-    struct entry* e = (struct entry*) entry;
-    size_t i;
-
-    for (i = 0; i < e->block_count; i++) {
-        struct block* block = e->blocks[i];
-        block->dirty = 1;
-    }
-}
-
-
-
-/**
- * Pointer auf einen Block im Cache-Eintrag holen
- *
- * @param entry Handle
- * @param block Blocknummer relativ zum Eintrag (der Offset innerhalb des
- *              Eintrags wird nicht beruecksichtigt)
- *
- * @return Pointer auf den Block
- */
-void*   cdi_cache_entry_block(struct cdi_cache_entry* entry, size_t block)
-{
-    struct entry* e = (struct entry*) entry;
-    size_t block_size = entry->cache->block_size;
-    uint64_t dev_start_block = (e->offset) / block_size;
-
-    if (block >= e->block_count) {
-        return NULL;
-    }
-
-    if (e->blocks[block] == NULL) {
-        e->blocks[block] = get_block((struct cache*) entry->cache,
-            dev_start_block + block, 1);
-        e->blocks[block]->ref_count++;
-    }
-
-
-    return e->blocks[block]->cdi.data;
-}
-
-/**
- * Daten aus dem Cache-Eintrag lesen
- *
- * @param entry     Handle
- * @param offset    Offset relativ zum Cache-Eintrag
- * @param size      Groesse des zu lesenden Bereichs
- * @param buffer    Puffer in dem die Daten abgelegt werden sollen
- */
-int     cdi_cache_entry_read(struct cdi_cache_entry* entry, size_t offset,
-            size_t size, void* buffer)
-{
-    struct entry* e = (struct entry*) entry;
-    size_t block_size = entry->cache->block_size;
-    uint64_t dev_start_block = (e->offset + offset) / block_size;
-    size_t start_block = (e->offset + offset) / block_size - e->offset /
-        block_size;
-    size_t end_block = (e->offset + offset + size -1) / block_size - e->offset /
-        block_size;
-    size_t block_count = end_block - start_block + 1;
-    size_t i;
-    size_t bytes_done = 0;
-
-    // Nicht ueber den Eintragsrand hinauslesen
-    if ((offset + size) > e->size) {
-        return 0;
-    }
-
-    // Offset vom Block-Anfang im Cacheeintrag beruecksichtigen, falls vorhanden
-    offset += e->offset % block_size;
-
-    for (i = 0; i < block_count; i++) {
-        void* block;
-        size_t bytes = block_size;
-        size_t off = 0;
-
-        if (e->blocks[start_block + i] == NULL) {
-            e->blocks[start_block + i] = get_block((struct cache*) entry->cache,
-                dev_start_block + i, 1);
-            e->blocks[start_block + i]->ref_count++;
-        }
-
-        block = e->blocks[start_block + i]->cdi.data;
-        e->blocks[start_block + i]->access_time = ++cache_time;
-
-        // Beim ersten Durchlauf muss der Anfangsoffset beruecksichtigt werden
-        if (i == 0) {
-            off = offset % block_size;
-            bytes = block_size - off;
-        }
-
-        // Beim letzten Durchlauf muss unter umstaenden nicht mehr ein ganzer
-        // Block gelesen werden.
-        if (i == block_count - 1) {
-            bytes = size - bytes_done;
-        }
-
-        memcpy((void*) ((uintptr_t) buffer + bytes_done), (void*)
-            ((uintptr_t) block + off), bytes);
-        bytes_done += bytes;
-    }
-
-    return 1;
-}
-
-/**
- * Daten in den Cache-Eintrag schreiben
- *
- * @param entry     Handle
- * @param offset    Offset relativ zum Cache-Eintrag
- * @param size      Groesse des zu schreibenden Bereichs
- * @param buffer    Puffer aus dem die Daten gelesen werden
- */
-int     cdi_cache_entry_write(struct cdi_cache_entry* entry, size_t offset,
-            size_t size, const void* buffer)
-{
-    struct entry* e = (struct entry*) entry;
-    size_t block_size = entry->cache->block_size;
-    uint64_t dev_start_block = (e->offset + offset) / block_size;
-    size_t start_block = (e->offset + offset) / block_size - e->offset /
-        block_size;
-    size_t end_block = (e->offset + offset + size - 1) / block_size - e->offset /
-        block_size;
-    size_t block_count = end_block - start_block + 1;
-    size_t i;
-    size_t bytes_done = 0;
-
-    // Nicht ueber den Eintragsrand hinausschreiben
-    if ((offset + size) > e->size) {
-        return 0;
-    }
-
-    // Offset vom Block-Anfang im Cacheeintrag beruecksichtigen, falls vorhanden
-    offset += e->offset % block_size;
-
-    for (i = 0; i < block_count; i++) {
-        void* block;
-        size_t bytes = block_size;
-        size_t off = 0;
-
-        // Beim ersten Durchlauf muss der Anfangsoffset beruecksichtigt werden
-        if (i == 0) {
-            off = offset % block_size;
-            bytes = block_size - off;
-        }
-
-        if (i == block_count - 1) {
-            bytes = size - bytes_done;
-        }
-
-
-        if (e->blocks[start_block + i] == NULL) {
-            int read = 1;
-
-            if ((off == 0) && (bytes == block_size)) {
-                read = 0;
-            }
-
-            e->blocks[start_block + i] = get_block((struct cache*) entry->cache,
-                dev_start_block + i, read);
-            e->blocks[start_block + i]->ref_count++;
-        }
-
-        block = e->blocks[start_block + i]->cdi.data;
-        e->blocks[start_block + i]->access_time = ++cache_time;
-        e->blocks[start_block + i]->dirty = 1;
-
-
-        memcpy((void*) ((uintptr_t) block + off), (void*) ((uintptr_t) buffer +
-            bytes_done), bytes);
-        bytes_done += bytes;
-    }
-
-    return 1;
-}
-
-
diff --git a/testlib/cdi_cache.h b/testlib/cdi_cache.h
index fd43bca..d378599 100644
--- a/testlib/cdi_cache.h
+++ b/testlib/cdi_cache.h
@@ -32,13 +32,6 @@ struct cdi_cache_block {
     void*       private;
 };
 
-/** Cache-Bereiche fuer komfortablen, dafuer etwas langsameren, Zugriff */
-struct cdi_cache_entry {
-    struct cdi_cache* cache;
-
-    /* OS-Spezifische Daten folgen... */
-};
-
 /** Typ fuer Cache-Callback zum einlesen eines Blocks. */
 typedef int (cdi_cache_read_block_t)(struct cdi_cache* cache, uint64_t block,
     size_t count, void* dest, void* prv);
@@ -47,6 +40,9 @@ typedef int (cdi_cache_read_block_t)(struct cdi_cache* cache, uint64_t block,
 typedef int (cdi_cache_write_block_t)(struct cdi_cache* cache, uint64_t block,
     size_t count, const void* src, void* prv);
 
+#ifdef __cplusplus
+extern "C" {
+#endif
 
 /**
  * Cache erstellen
@@ -88,11 +84,14 @@ int cdi_cache_sync(struct cdi_cache* cache);
  *
  * @param cache     Cache-Handle
  * @param blocknum  Blocknummer
+ * @param noread    Wenn != 0 wird der Block nicht eingelesen falls er noch
+ *                  nicht im Speicher ist. Kann benutzt werden, wenn der Block
+ *                  vollstaendig ueberschrieben werden soll.
  *
  * @return Pointer auf das Block-Handle oder NULL im Fehlerfall
  */
 struct cdi_cache_block* cdi_cache_block_get(struct cdi_cache* cache,
-    uint64_t blocknum);
+    uint64_t blocknum, int noread);
 
 /**
  * Cache-Block freigeben
@@ -112,87 +111,8 @@ void cdi_cache_block_release(struct cdi_cache* cache,
 void cdi_cache_block_dirty(struct cdi_cache* cache,
     struct cdi_cache_block* block);
 
-/**
- * Cache-Eintrag erstellen
- *
- * @param offset    Position auf dem Datentraeger
- * @param size      Groesse des Bereichs
- *
- * @return Handle
- */
-struct cdi_cache_entry* cdi_cache_entry_new(struct cdi_cache* cache,
-    uint64_t offset, size_t size);
-
-/**
- * Cache-Eintrag freigeben
- *
- * @param entry Handle
- */
-void    cdi_cache_entry_release(struct cdi_cache_entry* entry);
-
-/**
- * Cache-Eintrag sperren
- *
- * @param entry Handle
- */
-void    cdi_cache_entry_lock(struct cdi_cache_entry* entry);
-
-/**
- * Cache-Eintrag entsperren
- *
- * @param entry Handle
- */
-void    cdi_cache_entry_unlock(struct cdi_cache_entry* entry);
-
-/**
- * Cache-Eintrag als veraendert markieren
- *
- * @param entry Handle
- */
-void    cdi_cache_entry_dirty(struct cdi_cache_entry* entry);
-
-/**
- * Einzelnen Block im Cache-Eintrag als veraendert markieren
- *
- * @param entry Handle
- * @param block Blocknummer (von 0 an)
- */
-void    cdi_cache_entry_blkdirty(struct cdi_cache_entry* entry, uint64_t block);
-
-
-
-/**
- * Pointer auf einen Block im Cache-Eintrag holen
- *
- * @param entry Handle
- * @param block Blocknummer relativ zum Eintrag (der Offset innerhalb des
- *              Eintrags wird nicht beruecksichtigt)
- *
- * @return Pointer auf den Block
- */
-void*   cdi_cache_entry_block(struct cdi_cache_entry* entry, size_t block);
-
-/**
- * Daten aus dem Cache-Eintrag lesen
- *
- * @param entry     Handle
- * @param offset    Offset relativ zum Cache-Eintrag
- * @param size      Groesse des zu lesenden Bereichs
- * @param buffer    Puffer in dem die Daten abgelegt werden sollen
- */
-int     cdi_cache_entry_read(struct cdi_cache_entry* entry, size_t offset,
-            size_t size, void* buffer);
-
-/**
- * Daten in den Cache-Eintrag schreiben
- *
- * @param entry     Handle
- * @param offset    Offset relativ zum Cache-Eintrag
- * @param size      Groesse des zu schreibenden Bereichs
- * @param buffer    Puffer aus dem die Daten gelesen werden
- */
-int     cdi_cache_entry_write(struct cdi_cache_entry* entry, size_t offset,
-            size_t size, const void* buffer);
-
+#ifdef __cplusplus
+}; // extern "C"
+#endif
 
 #endif
diff --git a/testlib/tree.c b/testlib/tree.c
new file mode 100644
index 0000000..46460db
--- /dev/null
+++ b/testlib/tree.c
@@ -0,0 +1,599 @@
+/*
+ * Copyright (c) 2008 The tyndur Project. All rights reserved.
+ *
+ * This code is derived from software contributed to the tyndur Project
+ * by Kevin Wolf.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
+ * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "tree.h"
+#include <stdlib.h>
+#include <string.h>
+
+#ifdef DEBUG_TREE
+#include <stdio.h>
+
+void tree_dump(tree_t* tree);
+#endif
+
+/**
+ * Gibt das Objekt zu einem tree_item zurueck
+ */
+static inline void* to_node(tree_t* tree, struct tree_item* item) {
+    return ((char*) item - tree->tree_item_offset);
+}
+
+/**
+ * Gibt das tree_item zu einem Objekt zurueck
+ */
+static inline struct tree_item* to_tree_item(tree_t* tree, void* node) {
+    return (struct tree_item*) ((char*) node + tree->tree_item_offset);
+}
+
+/**
+ * Gibt den Schluessel eines Objekts zurueck
+ */
+static inline uint64_t get_key(tree_t* tree, struct tree_item* item) {
+    uint64_t res;
+
+    res = *(uint64_t*)((char*) to_node(tree, item) + tree->sort_key_offset);
+    return res & tree->key_mask;
+}
+
+/**
+ * Initilaisiert einen neuen AVL-Baum. Nicht direkt verwenden, tree_create ist
+ * das Mittel der Wahl.
+ */
+void tree_do_init(tree_t* tree,
+    size_t tree_item_offset, size_t sort_key_offset)
+{
+    memset(tree, 0, sizeof(*tree));
+    tree->tree_item_offset = tree_item_offset;
+    tree->sort_key_offset = sort_key_offset;
+    tree->key_mask = (uint64_t) -1;
+}
+
+/**
+ * Erzeugt einen neuen AVL-Baum. Nicht direkt verwenden, tree_create ist das
+ * Mittel der Wahl.
+ */
+tree_t* tree_do_create(size_t tree_item_offset, size_t sort_key_offset)
+{
+    tree_t* tree = malloc(sizeof(*tree));
+    tree_do_init(tree, tree_item_offset, sort_key_offset);
+    return tree;
+}
+
+/**
+ * Gibt einen AVL-Baum frei. Zu beachten ist, dass keiner seiner Knoten
+ * freigegeben wird, da ein Knoten immer noch ueber eine andere Datenstruktur
+ * erreichbar sein koennte.
+ */
+void tree_destroy(tree_t* tree)
+{
+    free(tree);
+}
+
+/**
+ * Sucht das Objekt mit dem gegebenen Schluessel im Baum.
+ *
+ * @param tree Baum, in dem das Objekt gesucht werden soll
+ * @param key Schluessel, nach dem gesucht wird
+ * @param node Enthaelt das tree_item des gesuchten Objekts, wenn der
+ * Schluessel gefunden wird. Wenn nicht, enthaelt es das tree_item des Blatts,
+ * an das ein neuer Knoten mit dem gesuchten Schluessel angefuegt werden
+ * muesste.
+ *
+ * @return 0 wenn das Objekt nicht gefunden wurde, nicht 0 sonst
+ */
+static int do_search(tree_t* tree, uint64_t key, struct tree_item** node)
+{
+    struct tree_item* res = NULL;
+    struct tree_item* current = tree->root;
+    uint64_t current_key = key - 1;
+
+    while (current != NULL) {
+        res = current;
+        current_key = get_key(tree, current);
+        if (key == current_key) {
+            break;
+        } else if (key < current_key) {
+            current = current->left;
+        } else {
+            current = current->right;
+        }
+    }
+
+    *node = res;
+    return (key == current_key);
+}
+
+/**
+ * Sucht nach dem Objekt mit einem gegebenen Schluessel in einem AVL-Baum
+ *
+ * @return Objekt mit dem gesuchten Schluessel oder NULL, wenn kein Objekt mit
+ * dem gesuchten Schluessel im Baum enthalten ist.
+ */
+void* tree_search(tree_t* tree, uint64_t key)
+{
+    struct tree_item* ret;
+
+    if (do_search(tree, key, &ret)) {
+        return to_node(tree, ret);
+    } else {
+        return NULL;
+    }
+}
+
+/**
+ * Aendert die Balance eines Knotens und passt die Balance aller Knoten auf dem
+ * Weg zur Wurzel des Baums entsprechend an.
+ *
+ * @param item tree_item, dessen Balance geaendert werden soll
+ * @param value Wert, um den die Balance geaendert werden soll
+ */
+static inline void adjust_balance(struct tree_item* item, int value)
+{
+    int stop = 0;
+
+    while (item->parent && !stop) {
+        if (item->parent->left == item) {
+            // Wenn an einem rechtslastigen Knoten links etwas geaendert wird,
+            // aendert sich zwar seine eigenen Balance, aber nicht mehr die des
+            // Vaterknotens.
+            if (item->parent->balance > 0) {
+                stop = 1;
+            }
+            item->parent->balance -= value;
+            if (item->parent->balance > 0) {
+                stop = 1;
+            }
+        } else {
+            // Dasselbe gilt fuer die rechte Seite eines linkslastigen Knotens.
+            if (item->parent->balance < 0) {
+                stop = 1;
+            }
+            item->parent->balance += value;
+            if (item->parent->balance < 0) {
+                stop = 1;
+            }
+        }
+        item = item->parent;
+    }
+}
+
+/**
+ * Fuehrt eine Linksrotation durch. Balanceaenderungen werden nicht
+ * vorgenommen.
+ */
+static void rotate_left(struct tree_item** root)
+{
+    struct tree_item* item = *root;
+    struct tree_item* tmp = item->right;
+
+    tmp->parent = item->parent;
+    item->parent = tmp;
+    if (tmp->left) {
+        tmp->left->parent = item;
+    }
+
+    item->right = tmp->left;
+    tmp->left = item;
+    *root = tmp;
+}
+
+/**
+ * Fuehrt eine Rechsrotation durch. Balanceaenderungen werden nicht
+ * vorgenommen.
+ */
+static void rotate_right(struct tree_item** root)
+{
+    struct tree_item* item = *root;
+    struct tree_item* tmp = item->left;
+
+    tmp->parent = item->parent;
+    item->parent = tmp;
+    if (tmp->right) {
+        tmp->right->parent = item;
+    }
+
+    item->left = tmp->right;
+    tmp->right = item;
+    *root = tmp;
+}
+
+
+/**
+ * Gibt einen Zeiger auf den Zeiger des Vaterknotens auf den aktuellen Knoten
+ * zurueck. Dieser Zeiger kann genutzt werden, um den gegebenen Knoten durch
+ * einen anderen Knoten zu ersetzen.
+ *
+ * Im Fall, dass der gegebene Knoten die Wurzel ist, wird &tree->root
+ * zurueckgegeben, so dass in diesem Fall eine neue Wurzel gesetzt wird.
+ */
+static struct tree_item** link_from_parent(tree_t* tree,
+    struct tree_item* item)
+{
+    if (item->parent == NULL) {
+        return &tree->root;
+    } else if (item->parent->left == item) {
+        return &item->parent->left;
+    } else {
+        return &item->parent->right;
+    }
+}
+
+/**
+ * Fuehrt eine AVL-Rebalancierung durch, nachdem der Baum veraendert wurde.
+ */
+static void rebalance(tree_t* tree, struct tree_item* item)
+{
+    struct tree_item** pitem;
+    struct tree_item* tmp;
+
+    while (item) {
+
+        pitem = link_from_parent(tree, item);
+
+        if (item->balance >= 2) {
+
+            // Rechtslastiger Baum
+            tmp = item->right;
+
+            if (item->right->balance > 0) {
+                // Einfache Rotation
+                rotate_left(pitem);
+                item->balance = 0;
+                tmp->balance = 0;
+                adjust_balance(*pitem, -1);
+            } else if (item->right->balance == 0) {
+                // Einfache Rotation
+                rotate_left(pitem);
+                item->balance = 1;
+                tmp->balance = -1;
+            } else {
+                // Doppelrotation
+                rotate_right(&item->right);
+                rotate_left(pitem);
+                item->balance = ((*pitem)->balance ==  1 ? -1 : 0);
+                tmp->balance  = ((*pitem)->balance == -1 ?  1 : 0);
+                (*pitem)->balance = 0;
+                adjust_balance(*pitem, -1);
+            }
+
+
+        } else if (item->balance <= -2) {
+
+            // Linkslastiger Baum
+            tmp = item->left;
+
+            if (item->left->balance < 0) {
+                // Einfache Rotation
+                rotate_right(pitem);
+                item->balance = 0;
+                tmp->balance = 0;
+                adjust_balance(*pitem, -1);
+            } else if (item->left->balance == 0) {
+                // Einfache Rotation
+                rotate_right(pitem);
+                item->balance = -1;
+                tmp->balance = 1;
+            } else {
+                // Doppelrotation
+                rotate_left(&item->left);
+                rotate_right(pitem);
+                item->balance = ((*pitem)->balance == -1 ?  1 : 0);
+                tmp->balance  = ((*pitem)->balance ==  1 ? -1 : 0);
+                (*pitem)->balance = 0;
+                adjust_balance(*pitem, -1);
+            }
+        }
+
+        // Weiter Richtung Wurzel gehen
+        item = item->parent;
+
+    }
+}
+
+/**
+ * Fuegt ein neues Objekt in den AVL-Baum ein.
+ *
+ * @param node Einzufuegendes Objekt. Muss den in tree_create angegebenen
+ * Datentyp haben, ansonsten ist das Ergebnis undefiniert.
+ */
+tree_t* tree_insert(tree_t* tree, void* node)
+{
+    struct tree_item* new = to_tree_item(tree, node);
+    struct tree_item* parent;
+    uint64_t new_key = get_key(tree, new);
+
+    new->left = NULL;
+    new->right = NULL;
+    new->balance = 0;
+
+    // Wenn es noch keine Wurzel gibt, ist die Sache trivial
+    if (tree->root == NULL) {
+        new->parent = NULL;
+        tree->root = new;
+        return tree;
+    }
+
+    // Ansonsten erstmal einen nahegelegenen Knoten finden, an dem man den
+    // neuen Knoten einhaengen kann. Wenn ein Knoten mit derselben ID schon
+    // drin ist, machen wir gar nichts.
+    if (!do_search(tree, new_key, &parent)) {
+        new->parent = parent;
+
+        if (new_key < get_key(tree, parent)) {
+            parent->left = new;
+        } else {
+            parent->right = new;
+        }
+        adjust_balance(new, 1);
+        rebalance(tree, new);
+    }
+
+    return tree;
+}
+
+/**
+ * Entfernt ein Objekt aus dem AVL-Baum. Das uebergebene Objekt muss im Baum
+ * enthalten sein.
+ *
+ * @return Das zu entfernende Objekt
+ */
+void* tree_remove(tree_t* tree, void* node)
+{
+    struct tree_item* item = to_tree_item(tree, node);
+    struct tree_item** pitem = link_from_parent(tree, item);
+
+    // Wenn es ein Blatt war, einfach rausnehmen
+
+    if (!item->left && !item->right) {
+        adjust_balance(item, -1);
+        *pitem = NULL;
+        rebalance(tree, item->parent);
+        return node;
+    }
+
+    // Ansonsten muessen wir die Kinder irgendwo anders aufhaengen. Wenn nur
+    // eine Seite besetzt ist, uebernimmt einfach das Kind dort den Platz.
+
+    if (item->left && !item->right) {
+        adjust_balance(item, -1);
+        *pitem = item->left;
+        item->left->parent = item->parent;
+        rebalance(tree, item->parent);
+        return node;
+    }
+
+    if (!item->left && item->right) {
+        adjust_balance(item, -1);
+        *pitem = item->right;
+        item->right->parent = item->parent;
+        rebalance(tree, item->parent);
+        return node;
+    }
+
+    // Bleibt schliesslich noch der komplizierteste Fall, naemlich, dass beide
+    // Seiten besetzt sind. Dann nehmen wir einen vom Index her nahegelegenen
+    // Knoten als Ersatz fuer den geloeschten. Ein guter Kandidat dafuer ist
+    // der am weitesten rechts gelegene Knoten des linken Teilbaums.
+
+    struct tree_item* subst;
+    struct tree_item** psubst;
+
+    subst = item->left;
+    while (subst->right) {
+        subst = subst->right;
+    }
+
+    psubst = link_from_parent(tree, subst);
+
+    // Wir sind ganz nach rechts gegangen, aber moeglicherweise ist noch ein
+    // linker Teilbaum uebrig. Dieser wird dann vom bisherigen Elternknoten
+    // des Ersatzes geerbt.
+
+    struct tree_item* old_left = subst->left;
+    struct tree_item* old_parent = subst->parent;
+
+    subst->parent   = item->parent;
+    subst->right    = item->right;
+    subst->left     = item->left;
+    subst->balance  = item->balance;
+
+    if (subst->left == subst) {
+        subst->left = NULL;
+    }
+
+    if (subst->left) {
+        subst->left->parent = subst;
+    }
+    if (subst->right) {
+        subst->right->parent = subst;
+    }
+
+    *psubst = old_left;
+    *pitem = subst;
+
+    if (old_parent == item) {
+        subst->balance++;
+        subst->left = old_left;
+        if (subst->balance <= 0) {
+            adjust_balance(subst, -1);
+        }
+        rebalance(tree, subst);
+    } else {
+        if (old_left) {
+            old_left->parent = old_parent;
+        }
+
+        old_parent->balance--;
+        if (old_parent->balance >= 0) {
+            adjust_balance(old_parent, -1);
+        }
+        rebalance(tree, old_parent);
+    }
+
+    return node;
+}
+
+/**
+ * Sucht zu einem gegebenen Objekt den Vorgaenger.
+ *
+ * Der Vorgaenger ist das Objekt mit dem naechstkleineren Schluessel. Der
+ * Vorgaenger von NULL ist das Objekt mit dem groessten Schluessel.
+ *
+ * @return Das Vorgaengerobjekt oder NULL, wenn das uebergebene Objekt das
+ * Objekt mit dem kleinsten Schluessel war.
+ */
+void* tree_prev(tree_t* tree, void* node)
+{
+    struct tree_item* current = to_tree_item(tree, node);
+    struct tree_item* old;
+
+    if (node == NULL) {
+        current = tree->root;
+        if (current == NULL) {
+            return NULL;
+        }
+    } else {
+
+        // Irgendwo mitten im Baum ist es einfach, den Vorgaenger zu finden:
+        // Einmal nach links und dann so weit wie moeglich nach rechts.
+        //
+        // Wenn der Knoten keinen linken Kindknoten hat, muessen wir ein Stueck
+        // Richtung Wurzel zurueckgehen, und zwar so lange bis wir von der
+        // rechten Seite an einen Knoten kommen.
+
+        if (current->left == NULL) {
+            do {
+                old = current;
+                current = current->parent;
+            } while (current && (current->left == old));
+
+            return current ? to_node(tree, current) : NULL;
+        }
+
+        current = current->left;
+    }
+
+    while (current->right) {
+        current = current->right;
+    }
+
+    return to_node(tree, current);
+}
+
+/**
+ * Sucht zu einem gegebenen Objekt den Nachfolger
+ *
+ * Der Nachfolger ist das Objekt mit dem naechstgroesseren Schluessel. Der
+ * Nachfolger von NULL ist das Objekt mit dem kleinsten Schluessel.
+ *
+ * @return Das Nachfolgerobjekt oder NULL, wenn das uebergebene Objekt das
+ * Objekt mit dem groessten Schluessel war.
+ */
+void* tree_next(tree_t* tree, void* node)
+{
+    struct tree_item* current = to_tree_item(tree, node);
+    struct tree_item* old;
+
+    if (node == NULL) {
+        current = tree->root;
+        if (current == NULL) {
+            return NULL;
+        }
+    } else {
+        // Das ist im Prinzip ein tree_prev mit links und rechts vertauscht
+
+        if (current->right == NULL) {
+            do {
+                old = current;
+                current = current->parent;
+            } while (current && (current->right == old));
+
+            return current ? to_node(tree, current) : NULL;
+        }
+
+        current = current->right;
+    }
+
+    while (current->left) {
+        current = current->left;
+    }
+
+    return to_node(tree, current);
+}
+
+
+#ifdef DEBUG_TREE
+static void do_check(tree_t* tree, struct tree_item* item, struct tree_item* parent)
+{
+    if (item->parent != parent) {
+        printf("Oops, elternlink  stimmt nicht: %lld\n", (unsigned long long)
+            get_key(tree, item));
+    }
+
+    if (item->left) {
+        do_check(tree, item->left, item);
+    }
+    if (item->right) {
+        do_check(tree, item->right, item);
+    }
+}
+
+void tree_check(tree_t* tree)
+{
+    if (tree->root) {
+        do_check(tree, tree->root, NULL);
+    }
+}
+
+/**
+ * Gibt ein Element und alle Kindelemente aus
+ */
+static void do_dump(tree_t* tree, struct tree_item* current)
+{
+    if (!current) {
+        printf("-");
+    } else if (!current->left && !current->right) {
+        printf("%ld", get_key(tree, current));
+    } else {
+        printf("[%d] %ld (", current->balance, get_key(tree, current));
+        do_dump(tree, current->left),
+        printf(" ");
+        do_dump(tree, current->right);
+        printf(")");
+    }
+}
+
+/**
+ * Gibt einen Dump eines Baums auf stdout aus
+ */
+void tree_dump(tree_t* tree)
+{
+    do_dump(tree, tree->root);
+    puts("");
+}
+#endif
diff --git a/testlib/tree.h b/testlib/tree.h
new file mode 100644
index 0000000..d88d041
--- /dev/null
+++ b/testlib/tree.h
@@ -0,0 +1,165 @@
+/*
+ * Copyright (c) 2006-2008 The tyndur Project. All rights reserved.
+ *
+ * This code is derived from software contributed to the tyndur Project
+ * by Kevin Wolf.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
+ * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef COLLECTIONS_H
+#define COLLECTIONS_H
+
+#include <stdint.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+/**
+ * Repraesentiert einen Knoten und bestimmt seine Position im Baum.
+ *
+ * Diese Struktur muss in jedem Typ, der in Baeumen verwendet werden soll,
+ * als Teil enthalten sein. Durch den Offset, den das tree_item in dem
+ * jeweiligen Typ hat, kann ein Pointer auf den Anfang des Objekts berechnet
+ * werden.
+ */
+struct tree_item {
+    struct tree_item* parent;
+    struct tree_item* left;
+    struct tree_item* right;
+    int balance;
+};
+
+/**
+ * Repraesentiert den Baum und erlaubt den Zugriff auf seine Elemente.
+ *
+ * Ein Baum besteht aus Objekten eines einheitlichen Datentyps. Die Objekte
+ * enthalten jeweils mindestens ein tree_item, das Vater und Kinder sowie den
+ * AVL-Balancewert ihres Knotens beschreibt und einen Schluessel, nach dem der
+ * Baum sortiert wird. Der Schluessel muss vom Typ uint64_t sein.
+ */
+typedef struct {
+    struct tree_item*   root;
+    size_t              tree_item_offset;
+    size_t              sort_key_offset;
+
+    /**
+     * AND-Maske, die alle Bits des Schluessels auswaehlt, die zur
+     * Identifikation und Sortierung von Objekten benutzt werden sollen. Diese
+     * Maske darf nicht mehr veraendert werden, sobald der Baum Elemente
+     * enthaelt, da er ansonsten nicht mehr sortiert ist und falsche Ergebnisse
+     * liefert.
+     *
+     * Direkt nach dem Erzeugen eines Baums sind alle Bits gesetzt.
+     */
+    uint64_t            key_mask;
+} tree_t;
+
+/**
+ * Erzeugt einen neuen AVL-Baum
+ *
+ * @param type Datentyp der Objekte im Baum
+ * @param tree_item Name des tree_item-Felds in der Struktur der Objekte
+ * @param sort_key Name des Schluessels in der Struktur der Objekte
+ */
+#define tree_create(type, tree_item, sort_key) \
+    tree_do_create(offsetof(type, tree_item), offsetof(type, sort_key))
+
+/**
+ * Erzeugt einen neuen AVL-Baum. Nicht direkt verwenden, tree_create ist das
+ * Mittel der Wahl.
+ */
+tree_t* tree_do_create(size_t tree_item_offset, size_t sort_key_offset);
+
+/**
+ * Initialisiert einen neuen AVL-Baum. Dies ist eine Alternative zu
+ * tree_create, wenn der Baum nicht dynamisch alloziert werden soll, sondern
+ * z.B. fest in einer Struktur eingebettet ist.
+ *
+ * @param tree Baum, der initialisiert werden soll
+ * @param type Datentyp der Objekte im Baum
+ * @param tree_item Name des tree_item-Felds in der Struktur der Objekte
+ * @param sort_key Name des Schluessels in der Struktur der Objekte
+ */
+#define tree_init(tree, type, tree_item, sort_key) \
+    tree_do_init(tree, offsetof(type, tree_item), offsetof(type, sort_key))
+
+/**
+ * Initialisiert einen AVL-Baum. Nicht direkt verwenden, tree_init ist das
+ * Mittel der Wahl.
+ */
+void tree_do_init(tree_t* tree,
+    size_t tree_item_offset, size_t sort_key_offset);
+
+/**
+ * Gibt einen AVL-Baum frei. Zu beachten ist, dass keiner seiner Knoten
+ * freigegeben wird, da ein Knoten immer noch ueber eine andere Datenstruktur
+ * erreichbar sein koennte.
+ */
+void tree_destroy(tree_t* tree);
+
+/**
+ * Sucht nach dem Objekt mit einem gegebenen Schluessel in einem AVL-Baum
+ *
+ * @return Objekt mit dem gesuchten Schluessel oder NULL, wenn kein Objekt mit
+ * dem gesuchten Schluessel im Baum enthalten ist.
+ */
+void* tree_search(tree_t* tree, uint64_t key);
+
+/**
+ * Fuegt ein neues Objekt in den AVL-Baum ein.
+ *
+ * @param node Einzufuegendes Objekt. Muss den in tree_create angegebenen
+ * Datentyp haben, ansonsten ist das Ergebnis undefiniert.
+ */
+tree_t* tree_insert(tree_t* tree, void* node);
+
+/**
+ * Entfernt ein Objekt aus dem AVL-Baum. Das uebergebene Objekt muss im Baum
+ * enthalten sein.
+ *
+ * @return Das zu entfernende Objekt
+ */
+void* tree_remove(tree_t* tree, void* node);
+
+/**
+ * Sucht zu einem gegebenen Objekt den Vorgaenger.
+ *
+ * Der Vorgaenger ist das Objekt mit dem naechstkleineren Schluessel. Der
+ * Vorgaenger von NULL ist das Objekt mit dem groessten Schluessel.
+ *
+ * @return Das Vorgaengerobjekt oder NULL, wenn das uebergebene Objekt das
+ * Objekt mit dem kleinsten Schluessel war.
+ */
+void* tree_prev(tree_t* tree, void* node);
+
+/**
+ * Sucht zu einem gegebenen Objekt den Nachfolger
+ *
+ * Der Nachfolger ist das Objekt mit dem naechstgroesseren Schluessel. Der
+ * Nachfolger von NULL ist das Objekt mit dem kleinsten Schluessel.
+ *
+ * @return Das Nachfolgerobjekt oder NULL, wenn das uebergebene Objekt das
+ * Objekt mit dem groessten Schluessel war.
+ */
+void* tree_next(tree_t* tree, void* node);
+
+#endif
-- 
1.8.1.4