[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