[tyndur-devel] [PATCH libext2 5/8] testlib: CDI-Cache aktualisiert
Kevin Wolf ·
Aktuelle Version aus tyndur zurückkopiert. Signed-off-by: Kevin Wolf <kevin at tyndur.org> --- 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