From 8f7447e48f6405a083919f3d6b591eb7dfbc6a9f Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Sun, 17 Jan 2010 10:57:30 +1030 Subject: [PATCH] Joey's btree module. --- ccan/btree/_info | 250 +++++++++ ccan/btree/btree.c | 727 +++++++++++++++++++++++++ ccan/btree/btree.h | 238 ++++++++ ccan/btree/test/run-benchmark.c | 348 ++++++++++++ ccan/btree/test/run-random-access.c | 387 +++++++++++++ ccan/btree/test/run-search-implement.c | 161 ++++++ ccan/btree/test/run-trivial.c | 357 ++++++++++++ 7 files changed, 2468 insertions(+) create mode 100644 ccan/btree/_info create mode 100644 ccan/btree/btree.c create mode 100644 ccan/btree/btree.h create mode 100644 ccan/btree/test/run-benchmark.c create mode 100644 ccan/btree/test/run-random-access.c create mode 100644 ccan/btree/test/run-search-implement.c create mode 100644 ccan/btree/test/run-trivial.c diff --git a/ccan/btree/_info b/ccan/btree/_info new file mode 100644 index 00000000..2b81dafb --- /dev/null +++ b/ccan/btree/_info @@ -0,0 +1,250 @@ +#include +#include "config.h" + +/** + * btree - Efficient sorted associative container based on B-trees. + * + * This module provides an efficient in-memory lookup container that keeps a + * set of pointers sorted using a user-defined search function. + * + * This module supports insertion, removal, lookup, and traversal using an + * iterator system. Note that insertion and removal into/from a btree will + * invalidate all iterators pointing to it (including the one passed to the + * insertion or removal function). + * + * btree currently doesn't have convenience functions for the simple tasks of + * "look up by key", "insert a key", and "remove a key". To insert or remove, + * you first have use btree_find* to position an iterator on the + * insertion/removal point, then call btree_insert_at or btree_remove_at using + * that iterator. Since a btree can hold multiple items with the same key, + * it isn't clear how the convenience functions should work yet. I'm open to + * suggestions. + * + * A B-tree (not to be confused with a binary tree) is a data structure that + * performs insertion, removal, and lookup in O(log n) time per operation. + * Although B-trees are typically used for databases and filesystems, this is + * an in-memory implementation. + * + * Unlike functions like qsort, bsearch, and tsearch, btree does not take a + * comparison function. It takes a binary search function, which is + * theoretically equivalent but faster. Writing a binary search function + * is more difficult than writing a comparison function, so a macro is provided + * to make it much easier than doing either manually. + * + * Example: + * #include + * + * #include + * #include + * #include + * #include + * + * struct word { + * char *word; + * char *letter_set; + * }; + * + * //Define the ordering function order_by_letter_set + * btree_search_implement + * ( + * order_by_letter_set, + * struct word *, + * int c = strcmp(a->letter_set, b->letter_set), + * c == 0, + * c < 0 + * ) + * + * struct word *new_word(const char *line); + * char *chomp(char *str); + * char *make_letter_set(char *str); + * + * void insert_word(struct btree *btree, struct word *word) + * { + * btree_iterator iter; + * + * //Position iterator after existing words with this letter set. + * btree_find_last(btree, word, iter); + * + * //Insert new word at iterator position. + * btree_insert_at(iter, word); + * } + * + * void print_anagrams(struct btree *btree, char *line) + * { + * btree_iterator iter, end; + * struct word key = { + * NULL, + * make_letter_set(line) + * }; + * + * //Find first matching word. + * if (!btree_find_first(btree, &key, iter)) { + * printf("\t(none)\n"); + * return; + * } + * + * btree_find_last(btree, &key, end); + * + * //Traverse matching words. + * for (; btree_deref(iter) && btree_cmp_iters(iter, end) < 0; + * btree_next(iter)) + * { + * struct word *word = iter->item; + * printf("\t%s\n", word->word); + * } + * } + * + * int destroy_word(struct word *word, void *ctx) + * { + * (void) ctx; + * + * free(word->word); + * free(word->letter_set); + * free(word); + * + * return 1; + * } + * + * struct btree *read_dictionary(const char *filename) + * { + * FILE *f; + * char line[256]; + * + * //Construct new btree with the ordering function order_by_letter_set . + * struct btree *btree = btree_new(order_by_letter_set); + * + * f = fopen(filename, "r"); + * if (!f) + * goto fail; + * + * //Set the destroy callback so btree_free will automatically + * //free our items. Setting btree->destroy is optional. + * btree->destroy = (btree_action_t)destroy_word; + * + * while (fgets(line, sizeof(line), f)) { + * struct word *word = new_word(line); + * if (!word) + * continue; + * insert_word(btree, word); + * } + * + * if (ferror(f)) { + * fclose(f); + * goto fail; + * } + * if (fclose(f)) + * goto fail; + * + * return btree; + * + * fail: + * btree_delete(btree); + * fprintf(stderr, "%s: %s\n", filename, strerror(errno)); + * return NULL; + * } + * + * int main(int argc, char *argv[]) + * { + * struct btree *btree; + * char line[256]; + * + * if (argc != 2) { + * fprintf(stderr, + * "Usage: %s dictionary-file\n" + * "Example:\n" + * "\t%s /usr/share/dict/words\n" + * "\n" + * , argv[0], argv[0]); + * return 1; + * } + * + * printf("Indexing...\n"); + * btree = read_dictionary(argv[1]); + * printf("Dictionary has %ld words\n", (long)btree->count); + * + * for (;;) { + * printf("> "); + * if (!fgets(line, sizeof(line), stdin)) + * break; + * chomp(line); + * if (!*line) + * break; + * + * printf("Anagrams of \"%s\":\n", line); + * print_anagrams(btree, line); + * } + * + * printf("Cleaning up...\n"); + * btree_delete(btree); + * + * return 0; + * } + * + * struct word *new_word(const char *line) + * { + * struct word *word; + * char *letter_set = make_letter_set(strdup(line)); + * + * //Discard lines with no letters + * if (!*letter_set) { + * free(letter_set); + * return NULL; + * } + * + * word = malloc(sizeof(struct word)); + * word->word = chomp(strdup(line)); + * word->letter_set = letter_set; + * + * return word; + * } + * + * //Remove trailing newline (if present). + * char *chomp(char *str) + * { + * char *end = strchr(str, '\0') - 1; + * if (*str && *end == '\n') + * *end = 0; + * return str; + * } + * + * //Remove all characters but letters, make letters lowercase, and sort them. + * char *make_letter_set(char *str) + * { + * size_t count[26] = {0}; + * size_t i, j; + * char *o = str; + * + * for (i=0; str[i]; i++) { + * char c = str[i]; + * if (c >= 'A' && c <= 'Z') + * c += 'a'-'A'; + * if (c >= 'a' && c <= 'z') + * count[c - 'a']++; + * } + * + * for (i = 0; i < 26; i++) { + * for (j = 0; j < count[i]; j++) + * *o++ = 'a' + i; + * } + * *o = '\0'; + * + * return str; + * } + * + * Author: Joey Adams + * Version: 0.1.0 + * Licence: BSD + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + /* Nothing */ + return 0; + } + + return 1; +} diff --git a/ccan/btree/btree.c b/ccan/btree/btree.c new file mode 100644 index 00000000..31982ec8 --- /dev/null +++ b/ccan/btree/btree.c @@ -0,0 +1,727 @@ +/* + Copyright (c) 2010 Joseph A. Adams + All rights reserved. + + 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. + 3. The name of the author may not be used to endorse or promote products + derived from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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 "btree.h" + +#include +#include +#include + +#define MAX (BTREE_ITEM_MAX) +#define MIN (BTREE_ITEM_MAX >> 1) + +static struct btree_node *node_alloc(int internal); +static void node_delete(struct btree_node *node, struct btree *btree); + +static void branch_begin(btree_iterator iter); +static void branch_end(btree_iterator iter); +static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr); + +/* + * If iter->node has parent, returns 1 and ascends the iterator such that + * iter->node->branch[iter->k] will be what iter->node was. + * + * If iter->node does not have a parent (is a root), returns 0 and leaves the + * iterator untouched. + */ +#define ascend(iter) ((iter)->node->parent \ + ? (iter)->k = (iter)->node->k, (iter)->node = (iter)->node->parent, 1 \ + : 0) + +static void node_insert(const void *x, struct btree_node *xr, + struct btree_node *p, unsigned int k); +static void node_split(const void **x, struct btree_node **xr, + struct btree_node *p, unsigned int k); + +static void node_remove_leaf_item(struct btree_node *node, unsigned int k); +void node_restore(struct btree_node *node, unsigned int k); + +static int node_walk_backward(const struct btree_node *node, + btree_action_t action, void *ctx); +static int node_walk_forward(const struct btree_node *node, + btree_action_t action, void *ctx); + + +/************************* Public functions *************************/ + +struct btree *btree_new(btree_search_t search) +{ + struct btree *btree = calloc(1, sizeof(struct btree)); + struct btree_node *node = node_alloc(0); + node->parent = NULL; + node->count = 0; + node->depth = 0; + btree->root = node; + btree->search = search; + return btree; +} + +void btree_delete(struct btree *btree) +{ + node_delete(btree->root, btree); + free(btree); +} + +int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr) +{ + struct btree_node *node; + + iter->btree = (struct btree *)btree; + begin_end_lr(iter, btree->root, lr); + + /* Set iter->item if any items exist. */ + node = iter->node; + if (node->count) { + iter->item = (void*)node->item[iter->k - lr]; + return 1; + } + + return 0; +} + +int btree_deref(btree_iterator iter) +{ + if (iter->k >= iter->node->count) { + struct btree_iterator_s tmp = *iter; + do { + if (!ascend(iter)) { + *iter = tmp; + return 0; + } + } while (iter->k >= iter->node->count); + } + + iter->item = (void*)iter->node->item[iter->k]; + return 1; +} + +int btree_prev(btree_iterator iter) +{ + if (iter->node->depth) { + branch_end(iter); + } else if (iter->k == 0) { + struct btree_iterator_s tmp = *iter; + do { + if (!ascend(iter)) { + *iter = tmp; + return 0; + } + } while (iter->k == 0); + } + + iter->item = (void*)iter->node->item[--iter->k]; + return 1; +} + +int btree_next(btree_iterator iter) +{ + int ret = btree_deref(iter); + if (ret) { + iter->k++; + if (iter->node->depth) + branch_begin(iter); + } + return ret; +} + +int btree_find_lr(const struct btree *btree, const void *key, + btree_iterator iter, int lr) +{ + struct btree_node *node = btree->root; + unsigned int k; + unsigned int depth; + int found = 0; + + iter->btree = (struct btree *)btree; + iter->item = NULL; + + depth = node->depth; + for (;;) { + int f = 0; + k = btree->search(key, node->item, node->count, lr, &f); + + if (f) { + iter->item = (void*)node->item[k - lr]; + found = 1; + } + if (!depth--) + break; + + node = node->branch[k]; + } + + iter->node = node; + iter->k = k; + + return found; +} + +int btree_walk_backward(const struct btree *btree, + btree_action_t action, void *ctx) +{ + return node_walk_backward(btree->root, action, ctx); +} + +int btree_walk_forward(const struct btree *btree, + btree_action_t action, void *ctx) +{ + return node_walk_forward(btree->root, action, ctx); +} + +void btree_insert_at(btree_iterator iter, const void *item) +{ + const void *x = item; + struct btree_node *xr = NULL; + struct btree_node *p; + struct btree *btree = iter->btree; + + /* btree_insert_at always sets iter->item to item. */ + iter->item = (void*)item; + + /* + * If node is not a leaf, fall to the end of the left branch of item[k] + * so that it will be a leaf. This does not modify the iterator's logical + * position. + */ + if (iter->node->depth) + branch_end(iter); + + /* + * First try inserting item into this node. + * If it's too big, split it, and repeat by + * trying to insert the median and right subtree into parent. + */ + if (iter->node->count < MAX) { + node_insert(x, xr, iter->node, iter->k); + goto finished; + } else { + for (;;) { + node_split(&x, &xr, iter->node, iter->k); + + if (!ascend(iter)) + break; + + if (iter->node->count < MAX) { + node_insert(x, xr, iter->node, iter->k); + goto finished; + } + } + + /* + * If splitting came all the way up to the root, create a new root whose + * left branch is the current root, median is x, and right branch is the + * half split off from the root. + */ + assert(iter->node == btree->root); + p = node_alloc(1); + p->parent = NULL; + p->count = 1; + p->depth = btree->root->depth + 1; + p->item[0] = x; + p->branch[0] = btree->root; + btree->root->parent = p; + btree->root->k = 0; + p->branch[1] = xr; + xr->parent = p; + xr->k = 1; + btree->root = p; + } + +finished: + btree->count++; + iter->node = NULL; +} + +int btree_remove_at(btree_iterator iter) +{ + struct btree *btree = iter->btree; + struct btree_node *root; + + if (!btree_deref(iter)) + return 0; + + if (!iter->node->depth) { + node_remove_leaf_item(iter->node, iter->k); + if (iter->node->count >= MIN || !iter->node->parent) + goto finished; + } else { + /* + * We can't remove an item from an internal node, so we'll replace it + * with its successor (which will always be in a leaf), then remove + * the original copy of the successor. + */ + + /* Save pointer to condemned item. */ + const void **x = &iter->node->item[iter->k]; + + /* Descend to successor. */ + iter->k++; + branch_begin(iter); + + /* Replace condemned item with successor. */ + *x = iter->node->item[0]; + + /* Remove successor. */ + node_remove_leaf_item(iter->node, 0); + } + + /* + * Restore nodes that fall under their minimum count. This may + * propagate all the way up to the root. + */ + for (;;) { + if (iter->node->count >= MIN) + goto finished; + if (!ascend(iter)) + break; + node_restore(iter->node, iter->k); + } + + /* + * If combining came all the way up to the root, and it has no more + * dividers, delete it and make its only branch the root. + */ + root = iter->node; + assert(root == btree->root); + assert(root->depth > 0); + if (root->count == 0) { + btree->root = root->branch[0]; + btree->root->parent = NULL; + free(root); + } + +finished: + btree->count--; + iter->node = NULL; + return 1; +} + +/* + * ascends iterator a until it matches iterator b's depth. + * + * Returns -1 if they end up on the same k (meaning a < b). + * Returns 0 otherwise. + */ +static int elevate(btree_iterator a, btree_iterator b) +{ + while (a->node->depth < b->node->depth) + ascend(a); + + if (a->k == b->k) + return -1; + return 0; +} + +int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b) +{ + btree_iterator a = {*iter_a}, b = {*iter_b}; + int ad, bd; + + ad = btree_deref(a); + bd = btree_deref(b); + + /* Check cases where one or both iterators are at the end. */ + if (!ad) + return bd ? 1 : 0; + if (!bd) + return ad ? -1 : 0; + + /* Bring iterators to the same depth. */ + if (a->node->depth < b->node->depth) { + if (elevate(a, b)) + return -1; + } else if (a->node->depth > b->node->depth) { + if (elevate(b, a)) + return 1; + } + + /* Bring iterators to the same node. */ + while (a->node != b->node) { + ascend(a); + ascend(b); + } + + /* Now we can compare by k directly. */ + if (a->k < b->k) + return -1; + if (a->k > b->k) + return 1; + + return 0; +} + + +/************************* Private functions *************************/ + +static struct btree_node *node_alloc(int internal) +{ + struct btree_node *node; + size_t isize = internal + ? sizeof(struct btree_node*) * (BTREE_ITEM_MAX+1) + : 0; + node = malloc(sizeof(struct btree_node) + isize); + return node; +} + +static void node_delete(struct btree_node *node, struct btree *btree) +{ + unsigned int i, count = node->count; + + if (!node->depth) { + if (btree->destroy) { + for (i=0; idestroy((void*)node->item[i], btree->destroy_ctx); + } + } else { + for (i=0; ibranch[i], btree); + if (btree->destroy) + btree->destroy((void*)node->item[i], btree->destroy_ctx); + } + node_delete(node->branch[count], btree); + } + + free(node); +} + +/* Set iter to beginning of branch pointed to by iter. */ +static void branch_begin(btree_iterator iter) +{ + struct btree_node *node = iter->node->branch[iter->k]; + unsigned int depth = node->depth; + while (depth--) + node = node->branch[0]; + iter->node = node; + iter->k = 0; +} + +/* Set iter to end of branch pointed to by iter. */ +static void branch_end(btree_iterator iter) +{ + struct btree_node *node = iter->node->branch[iter->k]; + unsigned int depth = node->depth; + while (depth--) + node = node->branch[node->count]; + iter->node = node; + iter->k = node->count; +} + +/* Traverse to the beginning or end of node, depending on lr. */ +static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr) +{ + iter->node = node; + iter->k = lr ? node->count : 0; + if (node->depth) + (lr ? branch_end : branch_begin)(iter); +} + +/* + * Inserts item x and right branch xr into node p at position k. + * + * Assumes p exists and has enough room. + * Ignores xr if p is a leaf. + */ +static void node_insert(const void *x, struct btree_node *xr, + struct btree_node *p, unsigned int k) +{ + unsigned int i; + + for (i = p->count; i-- > k;) + p->item[i+1] = p->item[i]; + p->item[k] = x; + + if (p->depth) { + k++; + for (i = p->count+1; i-- > k;) { + p->branch[i+1] = p->branch[i]; + p->branch[i+1]->k = i+1; + } + p->branch[k] = xr; + xr->parent = p; + xr->k = k; + } + + p->count++; +} + +/* + * Inserts item *x and subtree *xr into node p at position k, splitting it into + * nodes p and *xr with median item *x. + * + * Assumes p->count == MAX. + * Ignores original *xr if p is a leaf, but always sets it. + */ +static void node_split(const void **x, struct btree_node **xr, + struct btree_node *p, unsigned int k) +{ + unsigned int i, split; + struct btree_node *l = p, *r; + + /* + * If k <= MIN, item will be inserted into left subtree, so give l + * fewer items initially. + * Otherwise, item will be inserted into right subtree, so give r + * fewer items initially. + */ + if (k <= MIN) + split = MIN; + else + split = MIN + 1; + + /* + * If l->depth is 0, allocate a leaf node. + * Otherwise, allocate an internal node. + */ + r = node_alloc(l->depth); + + /* l and r will be siblings, so they will have the same parent and depth. */ + r->parent = l->parent; + r->depth = l->depth; + + /* + * Initialize items/branches of right side. + * Do not initialize r's leftmost branch yet because we don't know + * whether it will be l's current rightmost branch or if *xr will + * take its place. + */ + for (i = split; i < MAX; i++) + r->item[i-split] = l->item[i]; + if (r->depth) { + for (i = split+1; i <= MAX; i++) { + r->branch[i-split] = l->branch[i]; + r->branch[i-split]->parent = r; + r->branch[i-split]->k = i-split; + } + } + + /* Update counts. */ + l->count = split; + r->count = MAX - split; + + /* + * The nodes are now split, but the key isn't inserted yet. + * + * Insert key into left or right half, + * depending on which side it fell on. + */ + if (k <= MIN) + node_insert(*x, *xr, l, k); + else + node_insert(*x, *xr, r, k - split); + + /* + * Give l's rightmost branch to r because l's rightmost item + * is going up to become the median. + */ + if (r->depth) { + r->branch[0] = l->branch[l->count]; + r->branch[0]->parent = r; + r->branch[0]->k = 0; + } + + /* + * Take up l's rightmost item to make it the median. + * That item's right branch is now r. + */ + *x = l->item[--l->count]; + *xr = r; +} + +/* + * Removes item k from node p, shifting successor items back and + * decrementing the count. + * + * Assumes node p has the item k and is a leaf. + */ +static void node_remove_leaf_item(struct btree_node *node, unsigned int k) +{ + unsigned int i; + for (i = k+1; i < node->count; i++) + node->item[i-1] = node->item[i]; + node->count--; +} + +static void move_left(struct btree_node *node, unsigned int k); +static void move_right(struct btree_node *node, unsigned int k); +static void combine(struct btree_node *node, unsigned int k); + +/* + * Fixes node->branch[k]'s problem of having one less than MIN items. + * May or may not cause node to fall below MIN items, depending on whether + * two branches are combined or not. + */ +void node_restore(struct btree_node *node, unsigned int k) +{ + if (k == 0) { + if (node->branch[1]->count > MIN) + move_left(node, 0); + else + combine(node, 0); + } else if (k == node->count) { + if (node->branch[k-1]->count > MIN) + move_right(node, k-1); + else + combine(node, k-1); + } else if (node->branch[k-1]->count > MIN) { + move_right(node, k-1); + } else if (node->branch[k+1]->count > MIN) { + move_left(node, k); + } else { + combine(node, k-1); + } +} + +static void move_left(struct btree_node *node, unsigned int k) +{ + struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv; + unsigned int i; + + l->item[l->count] = node->item[k]; + node->item[k] = r->item[0]; + for (i = 1; i < r->count; i++) + r->item[i-1] = r->item[i]; + + if (r->depth) { + mv = r->branch[0]; + l->branch[l->count+1] = mv; + mv->parent = l; + mv->k = l->count+1; + + for (i = 1; i <= r->count; i++) { + r->branch[i-1] = r->branch[i]; + r->branch[i-1]->k = i-1; + } + } + + l->count++; + r->count--; +} + +static void move_right(struct btree_node *node, unsigned int k) +{ + struct btree_node *l = node->branch[k], *r = node->branch[k+1]; + unsigned int i; + + for (i = r->count; i--;) + r->item[i+1] = r->item[i]; + r->item[0] = node->item[k]; + node->item[k] = l->item[l->count-1]; + + if (r->depth) { + for (i = r->count+1; i--;) { + r->branch[i+1] = r->branch[i]; + r->branch[i+1]->k = i+1; + } + r->branch[0] = l->branch[l->count]; + r->branch[0]->parent = r; + r->branch[0]->k = 0; + } + + l->count--; + r->count++; +} + +/* Combine node->branch[k] and node->branch[k+1]. */ +static void combine(struct btree_node *node, unsigned int k) +{ + struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv; + const void **o = &l->item[l->count]; + unsigned int i; + + //append node->item[k] followed by right node's items to left node + *o++ = node->item[k]; + for (i=0; icount; i++) + *o++ = r->item[i]; + + //if applicable, append right node's branches to left node + if (r->depth) { + for (i=0; i<=r->count; i++) { + mv = r->branch[i]; + l->branch[l->count + i + 1] = mv; + mv->parent = l; + mv->k = l->count + i + 1; + } + } + + //remove k and its right branch from parent node + for (i = k+1; i < node->count; i++) { + node->item[i-1] = node->item[i]; + node->branch[i] = node->branch[i+1]; + node->branch[i]->k = i; + } + + //don't forget to update the left and parent node's counts and to free the right node + l->count += r->count + 1; + node->count--; + free(r); +} + +static int node_walk_backward(const struct btree_node *node, + btree_action_t action, void *ctx) +{ + unsigned int i, count = node->count; + + if (!node->depth) { + for (i=count; i--;) + if (!action((void*)node->item[i], ctx)) + return 0; + } else { + if (!node_walk_backward(node->branch[count], action, ctx)) + return 0; + for (i=count; i--;) { + if (!action((void*)node->item[i], ctx)) + return 0; + if (!node_walk_backward(node->branch[i], action, ctx)) + return 0; + } + } + + return 1; +} + +static int node_walk_forward(const struct btree_node *node, + btree_action_t action, void *ctx) +{ + unsigned int i, count = node->count; + + if (!node->depth) { + for (i=0; iitem[i], ctx)) + return 0; + } else { + for (i=0; ibranch[i], action, ctx)) + return 0; + if (!action((void*)node->item[i], ctx)) + return 0; + } + if (!node_walk_forward(node->branch[count], action, ctx)) + return 0; + } + + return 1; +} diff --git a/ccan/btree/btree.h b/ccan/btree/btree.h new file mode 100644 index 00000000..babfea76 --- /dev/null +++ b/ccan/btree/btree.h @@ -0,0 +1,238 @@ +/* + Copyright (c) 2010 Joseph A. Adams + All rights reserved. + + 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. + 3. The name of the author may not be used to endorse or promote products + derived from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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 CCAN_BTREE_H +#define CCAN_BTREE_H + +/* +Note: The following should work but are not well-tested yet: + +btree_walk... +btree_cmp_iters +*/ + +#include +#include + +/* + * Maximum number of items per node. + * The maximum number of branches is BTREE_ITEM_MAX + 1. + */ +#define BTREE_ITEM_MAX 20 + +struct btree_node { + struct btree_node *parent; + + /* Number of items (rather than branches). */ + unsigned char count; + + /* 0 if node is a leaf, 1 if it has leaf children, etc. */ + unsigned char depth; + + /* node->parent->branch[node->k] == this */ + unsigned char k; + + const void *item[BTREE_ITEM_MAX]; + + /* + * Allocated to BTREE_ITEM_MAX+1 items if this is + * an internal node, 0 items if it is a leaf. + */ + struct btree_node *branch[]; +}; + +typedef struct btree_iterator_s { + struct btree *btree; + struct btree_node *node; + unsigned int k; + + /* + * The relationship between item and (node, k) depends on what function + * set it. It is mainly for convenience. + */ + void *item; +} btree_iterator[1]; + +/* + * Instead of a compare function, this library accepts a binary search function + * to know how to order the items. + */ +typedef unsigned int btree_search_proto( + const void *key, + const void * const *base, + unsigned int count, + int lr, + int *found +); +typedef btree_search_proto *btree_search_t; + +/* + * Callback used by btree_delete() and btree_walk...(). + * + * If it returns 0, it causes btree_walk...() to stop traversing and return 0. + * Thus, in normal circumstances, this callback should return 1. + * + * Callback shall not insert/remove items from the btree being traversed, + * nor shall anything modify it during a walk. + */ +typedef int (*btree_action_t)(void *item, void *ctx); + +struct btree { + struct btree_node *root; + size_t count; /* Total number of items in B-tree */ + + btree_search_t search; + + /* + * These are set to NULL by default. + * + * When destroy is not NULL, it is called on each item in order when + * btree_delete() is called. + * + * When destroy is NULL, btree_delete runs faster because it does not have + * to visit each and every item. + */ + btree_action_t destroy; + void *destroy_ctx; +}; + +struct btree *btree_new(btree_search_t search); +void btree_delete(struct btree *btree); + + +/* lr must be 0 or 1, nothing else. */ +int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr); +int btree_find_lr(const struct btree *btree, const void *key, + btree_iterator iter, int lr); + +int btree_walk_backward(const struct btree *btree, + btree_action_t action, void *ctx); +int btree_walk_forward(const struct btree *btree, + btree_action_t action, void *ctx); + +#define btree_begin(btree, iter) btree_begin_end_lr(btree, iter, 0) +#define btree_end(btree, iter) btree_begin_end_lr(btree, iter, 1) + +int btree_prev(btree_iterator iter); +int btree_next(btree_iterator iter); + +#define btree_walk(btree, action, ctx) btree_walk_forward(btree, action, ctx) + +/* + * If key was found, btree_find_first will return 1, iter->item will be the + * first matching item, and iter will point to the beginning of the matching + * items. + * + * If key was not found, btree_find_first will return 0, iter->item will be + * undefined, and iter will point to where the key should go if inserted. + */ +#define btree_find_first(btree, key, iter) btree_find_lr(btree, key, iter, 0) + +/* + * If key was found, btree_find_last will return 1, iter->item will be the + * last matching item, and iter will point to the end of the matching + * items. + * + * If key was not found, btree_find_last will return 0, iter->item will be + * undefined, and iter will point to where the key should go if inserted. + */ +#define btree_find_last(btree, key, iter) btree_find_lr(btree, key, iter, 1) + +/* btree_find is an alias of btree_find_first. */ +#define btree_find(btree, key, iter) btree_find_first(btree, key, iter) + +/* + * If iter points to an item, btree_deref returns 1 and sets iter->item to the + * item it points to. + * + * Otherwise (if iter points to the end of the btree), btree_deref returns 0 + * and leaves iter untouched. + */ +int btree_deref(btree_iterator iter); + +/* + * Inserts the item before the one pointed to by iter. + * + * Insertion invalidates all iterators to the btree, including the one + * passed to btree_insert_at. Nevertheless, iter->item will be set to + * the item inserted. + */ +void btree_insert_at(btree_iterator iter, const void *item); + +/* + * Removes the item pointed to by iter. Returns 1 if iter pointed + * to an item. Returns 0 if iter pointed to the end, in which case + * it leaves iter intact. + * + * Removal invalidates all iterators to the btree, including the one + * passed to btree_remove_at. Nevertheless, iter->item will be set to + * the item removed. + */ +int btree_remove_at(btree_iterator iter); + +/* + * Compares positions of two iterators. + * + * Returns -1 if a is before b, 0 if a is at the same position as b, + * and +1 if a is after b. + */ +int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b); + +#define btree_search_implement(name, type, setup, equals, lessthan) \ +unsigned int name(const void *__key, \ + const void * const *__base, unsigned int __count, \ + int __lr, int *__found) \ +{ \ + unsigned int __start = 0; \ + while (__count) { \ + unsigned int __middle = __count >> 1; \ + type a = (type)__key; \ + type b = (type)__base[__start + __middle]; \ + { \ + setup; \ + if (equals) \ + goto __equals; \ + if (lessthan) \ + goto __lessthan; \ + } \ + __greaterthan: \ + __start += __middle + 1; \ + __count -= __middle + 1; \ + continue; \ + __equals: \ + *__found = 1; \ + if (__lr) \ + goto __greaterthan; \ + /* else, fall through to __lessthan */ \ + __lessthan: \ + __count = __middle; \ + continue; \ + } \ + return __start; \ +} + +#endif /* #ifndef CCAN_BTREE_H */ diff --git a/ccan/btree/test/run-benchmark.c b/ccan/btree/test/run-benchmark.c new file mode 100644 index 00000000..62e59f80 --- /dev/null +++ b/ccan/btree/test/run-benchmark.c @@ -0,0 +1,348 @@ +/* Include the main header first, to test it works */ +#include +/* Include the C files directly. */ +#include +#include + +#include +#include +#include + +uint32_t rand32_state = 0; + +/* + * Finds a pseudorandom 32-bit number from 0 to 2^32-1 . + * Uses the BCPL linear congruential generator method. + */ +static uint32_t rand32(void) +{ + rand32_state *= (uint32_t)0x7FF8A3ED; + rand32_state += (uint32_t)0x2AA01D31; + return rand32_state; +} + +static void scramble(void *base, size_t nmemb, size_t size) +{ + char *i = base; + char *o; + size_t sd; + for (;nmemb>1;nmemb--) { + o = i + size*(rand32()%nmemb); + for (sd=size;sd--;) { + char tmp = *o; + *o++ = *i; + *i++ = tmp; + } + } +} + +struct test_item { + size_t key; + uint32_t value; +}; + +/* For ordering a btree of test_item pointers. */ +static btree_search_implement ( + order_by_key, + const struct test_item *, + , + a == b, + a < b +) + +/* For qsorting an array of test_item pointers. */ +static int compare_test_item(const void *ap, const void *bp) +{ + const struct test_item *a = *(const struct test_item * const*)ap; + const struct test_item *b = *(const struct test_item * const*)bp; + if (a == b) + return 0; + if (a < b) + return -1; + return 1; +} + +/* + * If lr == 0, make sure iter points to the item given. + * If lr == 1, make sure iter points to after the item given. + */ +static int check_iter(btree_iterator iter_orig, const void *item, int lr) +{ + btree_iterator iter = {*iter_orig}; + if (iter->item != item) + return 0; + if (lr) { + if (!btree_prev(iter)) + return 0; + } else { + if (!btree_deref(iter)) + return 0; + } + if (iter->item != item) + return 0; + if (iter->node->item[iter->k] != iter->item) + return 0; + + return 1; +} + +/* + * Returns 1 on insert, 0 on duplicate, + * -1 on bad iterator returned by find, and + * -2 on bad iterator returned by insert. + */ +static int insert_test_item(struct btree *btree, struct test_item *item) +{ + btree_iterator iter; + int lr; + + /* Find the first or last matching item, randomly choosing between the two. */ + lr = rand32() & 1; + if (btree_find_lr(btree, item, iter, lr)) { + if (!check_iter(iter, item, lr)) + return -1; + return 0; + } + + btree_insert_at(iter, item); + + if (iter->item != item) + return -2; + + return 1; +} + +/* + * Returns 1 on remove, 0 on missing, + * -1 on bad iterator returned by find, and + * -2 on bad iterator returned by remove. + */ +static int remove_test_item(struct btree *btree, struct test_item *item) +{ + btree_iterator iter; + + if (!btree_find(btree, item, iter)) + return 0; + + if (!check_iter(iter, item, 0)) + return -1; + + btree_remove_at(iter); + + if (iter->item != item) + return -2; + + return 1; +} + +static struct { + size_t success; + + size_t excess; + size_t duplicate; + size_t missing; + size_t incorrect; + size_t failed; + + size_t bad_iter_find; + size_t bad_iter_insert; + size_t bad_iter_remove; + size_t bad_iter_next; +} stats; + +static void clear_stats(void) { + memset(&stats, 0, sizeof(stats)); +} + +static int print_stats(const char *success_label, size_t expected_success) { + int failed = 0; + + printf(" %s: \t%zu\n", success_label, stats.success); + if (stats.success != expected_success) + failed = 1; + + if (stats.excess) + failed = 1, printf(" Excess: \t%zu\n", stats.excess); + if (stats.duplicate) + failed = 1, printf(" Duplicate: \t%zu\n", stats.duplicate); + if (stats.missing) + failed = 1, printf(" Missing: \t%zu\n", stats.missing); + if (stats.incorrect) + failed = 1, printf(" Incorrect: \t%zu\n", stats.incorrect); + if (stats.failed) + failed = 1, printf(" Failed: \t%zu\n", stats.failed); + + if (stats.bad_iter_find || stats.bad_iter_insert || + stats.bad_iter_remove || stats.bad_iter_next) { + failed = 1; + printf(" Bad iterators yielded by:\n"); + if (stats.bad_iter_find) + printf(" btree_find_lr(): %zu\n", stats.bad_iter_find); + if (stats.bad_iter_insert) + printf(" btree_insert_at(): %zu\n", stats.bad_iter_insert); + if (stats.bad_iter_remove) + printf(" btree_remove_at(): %zu\n", stats.bad_iter_remove); + if (stats.bad_iter_next) + printf(" btree_next(): %zu\n", stats.bad_iter_next); + } + + return !failed; +} + +static void benchmark(size_t max_per_trial, size_t round_count, int random_counts) +{ + struct test_item **test_item; + struct test_item *test_item_array; + size_t i, count; + size_t round = 0; + + test_item = malloc(max_per_trial * sizeof(*test_item)); + test_item_array = malloc(max_per_trial * sizeof(*test_item_array)); + + if (!test_item || !test_item_array) { + fail("Not enough memory for %zu keys per trial\n", + max_per_trial); + return; + } + + /* Initialize test_item pointers. */ + for (i=0; ikey = i; + test_item[i]->value = rand32(); + } + scramble(test_item, count, sizeof(*test_item)); + + btree = btree_new(order_by_key); + + clear_stats(); + printf(" Inserting %zu items...\n", count); + for (i=0; i= count) { + stats.excess++; + continue; + } + + if (iter->item == test_item[i]) + stats.success++; + else + stats.incorrect++; + + i++; + } + ok1(print_stats("Retrieved", count)); + + printf(" Traversing backward through %zu items...\n", count); + clear_stats(); + i = count; + for (btree_end(btree, iter); btree_prev(iter);) { + if (!i) { + stats.excess++; + continue; + } + i--; + + if (iter->item == test_item[i]) + stats.success++; + else + stats.incorrect++; + } + ok1(print_stats("Retrieved", count)); + + ok1(btree->count == count); + + //static int remove_test_item(struct btree *btree, struct test_item *item); + scramble(test_item, count, sizeof(*test_item)); + + printf(" Deleting %zu items...\n", count); + clear_stats(); + for (i=0; icount == 0); + ok1(print_stats("Deleted", count)); + ok1(btree->root->depth == 0 && btree->root->count == 0); + + btree_delete(btree); + } + + free(test_item); + free(test_item_array); +} + +int main(void) +{ + plan_tests(32); + + benchmark(300000, 4, 0); + + return exit_status(); +} diff --git a/ccan/btree/test/run-random-access.c b/ccan/btree/test/run-random-access.c new file mode 100644 index 00000000..ab9d33e5 --- /dev/null +++ b/ccan/btree/test/run-random-access.c @@ -0,0 +1,387 @@ +/* Include the main header first, to test it works */ +#include +/* Include the C files directly. */ +#include +#include + +#include +#include +#include +#include + +static uint32_t rand32_state = 0; + +/* + * Finds a pseudorandom 32-bit number from 0 to 2^32-1 . + * Uses the BCPL linear congruential generator method. + */ +static uint32_t rand32(void) +{ + rand32_state *= (uint32_t)0x7FF8A3ED; + rand32_state += (uint32_t)0x2AA01D31; + return rand32_state; +} + +/* + * Whether or not to add/remove multiple equal keys to the tree. + * + * Tests are run with multi set to 0 and 1. + */ +static int multi = 0; + +static struct { + struct { + size_t success; + size_t failure; + } insert, remove, find, traverse; +} stats; + +static int check_stats(void) { + return + stats.insert.failure == 0 && + stats.remove.failure == 0 && + stats.find.failure == 0 && + stats.traverse.failure == 0; +} + +static int print_stats(void) { + printf("Insert: %zu succeeded, %zu failed\n", + stats.insert.success, stats.insert.failure); + + printf("Remove: %zu succeeded, %zu failed\n", + stats.remove.success, stats.remove.failure); + + printf("Find: %zu succeeded, %zu failed\n", + stats.find.success, stats.find.failure); + + printf("Traverse: %zu succeeded, %zu failed\n", + stats.traverse.success, stats.traverse.failure); + + return check_stats(); +} + +static void clear_stats(void) +{ + memset(&stats, 0, sizeof(stats)); +} + +static int test_node_consistency(struct btree_node *node, struct btree_node *parent, size_t *count) +{ + unsigned int i, j, e = node->count; + + /* Verify parent, depth, and k */ + if (node->parent != parent) + return 0; + if (parent) { + if (node->depth != parent->depth - 1) + return 0; + if (node != parent->branch[node->k]) + return 0; + } + + /* Nodes must not be empty (unless the entire tree is empty). */ + if (e == 0) + return 0; + + if (node->depth) { + /* Make sure child branches aren't duplicated or NULL. */ + for (i=0; i<=e; i++) { + if (node->branch[i] == NULL) + return 0; + for (j=i+1; j<=e; j++) + if (node->branch[i] == node->branch[j]) + return 0; + } + + /* Recursively check children. */ + for (i=0; i<=e; i++) { + if (!test_node_consistency(node->branch[i], node, count)) + return 0; + } + } + + *count += node->count; + return 1; +} + +static int test_consistency(const struct btree *btree) +{ + size_t count = 0; + if (!btree->root) + return 0; + if (btree->root->count == 0) { + if (btree->count != 0) + return 0; + return 1; + } + if (btree->count == 0) + return 0; + if (!test_node_consistency(btree->root, NULL, &count)) + return 0; + if (btree->count != count) + return 0; + return 1; +} + +static int test_traverse(struct btree *btree, size_t key[], size_t count) +{ + btree_iterator iter; + size_t i, j; + + if (!test_consistency(btree)) + return 0; + + /* Forward */ + i = 0; + btree_begin(btree, iter); + for (;;) { + while (i < count && key[i] == 0) + i++; + if (i >= count) { + if (btree_next(iter)) + return 0; + break; + } + for (j = 0; j < key[i] && btree_next(iter); j++) { + if (iter->item != &key[i]) + return 0; + } + if (j != key[i]) + return 0; + i++; + } + + /* Backward */ + i = count; + btree_end(btree, iter); + for (;;) { + while (i > 0 && key[i-1] == 0) + i--; + if (i <= 0) { + if (btree_prev(iter)) + return 0; + break; + } + for (j = 0; j < key[i-1] && btree_prev(iter); j++) { + if (iter->item != &key[i-1]) + return 0; + } + if (j != key[i-1]) + return 0; + i--; + } + + return 1; +} + +/* + * Finds and counts items matching &key[k], then makes sure the count + * equals key[k]. Also verifies that btree_find_... work as advertised. + */ +static int find(struct btree *btree, size_t key[], size_t k) +{ + btree_iterator iter, tmp; + size_t count; + int found; + + memset(iter, 0, sizeof(iter)); + memset(tmp, 0, sizeof(tmp)); + + found = btree_find_first(btree, &key[k], iter); + if (iter->btree != btree) + return 0; + if (found != !!key[k]) + return 0; + if (key[k] && iter->item != &key[k]) + return 0; + + /* Make sure btree_find works exactly the same as btree_find_first. */ + if (btree_find(btree, &key[k], tmp) != found) + return 0; + if (memcmp(iter, tmp, sizeof(*iter))) + return 0; + + /* Make sure previous item doesn't match. */ + *tmp = *iter; + if (btree_prev(tmp)) { + if (tmp->item == &key[k]) + return 0; + } + + /* Count going forward. */ + for (count=0; btree_deref(iter) && iter->item == &key[k]; count++, btree_next(iter)) + {} + if (count != key[k]) + return 0; + + /* Make sure next item doesn't match. */ + *tmp = *iter; + if (btree_deref(tmp)) { + if (tmp->item == &key[k]) + return 0; + } + + /* Make sure iter is now equal to the end of matching items. */ + btree_find_last(btree, &key[k], tmp); + if (tmp->btree != btree) + return 0; + if (btree_cmp_iters(iter, tmp)) + return 0; + + /* Count going backward. */ + for (count=0; btree_prev(iter); count++) { + if (iter->item != &key[k]) { + btree_next(iter); + break; + } + } + if (count != key[k]) + return 0; + + /* Make sure iter is now equal to the beginning of matching items. */ + btree_find_first(btree, &key[k], tmp); + if (tmp->btree != btree) + return 0; + if (btree_cmp_iters(iter, tmp)) + return 0; + + return 1; +} + +static int test_find(struct btree *btree, size_t key[], size_t count) +{ + size_t k = rand32() % count; + return find(btree, key, k); +} + +static int test_remove(struct btree *btree, size_t key[], size_t count) +{ + size_t prev_count = btree->count; + size_t k = rand32() % count; + btree_iterator iter; + + if (!find(btree, key, k)) + return 0; + + btree_find(btree, &key[k], iter); + + //remove (if present), and make sure removal status is correct + if (key[k]) { + if (btree_remove_at(iter) != 1) + return 0; + if (btree->count != prev_count - 1) + return 0; + key[k]--; + + if (!find(btree, key, k)) + return 0; + } + + return 1; +} + +static int test_insert(struct btree *btree, size_t key[], size_t count) +{ + size_t k = rand32() % count; + btree_iterator iter; + size_t prev_count = btree->count; + int found; + + if (!find(btree, key, k)) + return 0; + + /* Make sure key's presense is consistent with our array. */ + found = btree_find_first(btree, &key[k], iter); + if (key[k]) { + if (!found || iter->item != &key[k]) + return 0; + if (!btree_deref(iter)) + return 0; + if (iter->k >= iter->node->count || iter->node->item[iter->k] != &key[k]) + return 0; + } else { + if (found) + return 0; + } + + /* Insert if item hasn't been yet (or if we're in multi mode). */ + if (!key[k] || multi) { + btree_insert_at(iter, &key[k]); + key[k]++; + if (btree->count != prev_count + 1) + return 0; + } + + /* Check result iterator's ->item field. */ + if (iter->item != &key[k]) + return 0; + + if (!find(btree, key, k)) + return 0; + + /* Make sure key is present and correct now. */ + found = btree_find_first(btree, &key[k], iter); + if (!found || iter->item != &key[k]) + return 0; + + return 1; +} + +static btree_search_implement(order_by_ptr, size_t*, , a == b, a < b) + +static void stress(size_t count, size_t trials) +{ + struct btree *btree = btree_new(order_by_ptr); + size_t *key = calloc(count, sizeof(*key)); + size_t i; + + clear_stats(); + + for (i=0; icount * 43688 / count; + //remove/insert boundary + if (n >= 65534) { + if (test_traverse(btree, key, count)) + stats.traverse.success++; + else + stats.traverse.failure++; + } else if (n >= 46388) { + if (test_find(btree, key, count)) + stats.find.success++; + else + stats.find.failure++; + } else if (n < rib) { + if (test_remove(btree, key, count)) + stats.remove.success++; + else + stats.remove.failure++; + } else { + if (test_insert(btree, key, count)) + stats.insert.success++; + else + stats.insert.failure++; + } + } + + free(key); + btree_delete(btree); + + print_stats(); + ok1(check_stats()); +} + +int main(void) +{ + plan_tests(2); + + multi = 0; + printf("Running with multi = %d\n", multi); + stress(100000, 500000); + + multi = 1; + printf("Running with multi = %d\n", multi); + stress(100000, 500000); + + return exit_status(); +} diff --git a/ccan/btree/test/run-search-implement.c b/ccan/btree/test/run-search-implement.c new file mode 100644 index 00000000..631e5bf7 --- /dev/null +++ b/ccan/btree/test/run-search-implement.c @@ -0,0 +1,161 @@ +/* Include the main header first, to test it works */ +#include +/* Include the C files directly. */ +#include +#include + +#include + +#ifndef ARRAY_SIZE +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(*(array))) +#endif + +struct foo { + const char *string; + int number; +}; + +struct foo foo_structs[] = { + {"apple", 1}, + {"banana", 2}, + {"banana", 4}, + {"cherry", 4}, + {"doughnut", 5}, +}; + +struct foo *foo_base[ARRAY_SIZE(foo_structs)]; +const unsigned int foo_count = ARRAY_SIZE(foo_structs); + +static void init_foo_pointers(void) +{ + unsigned int i; + + for (i = 0; i < foo_count; i++) + foo_base[i] = &foo_structs[i]; +} + +/* Make sure forward declarations work */ +btree_search_proto order_by_string, order_by_number; + +static void test_order_by_string(void) +{ + struct { + const char *key; + int lr; + unsigned int expect_offset; + int expect_found; + } test[] = { + {"anchovies", 0, 0, 0}, + {"anchovies", 1, 0, 0}, + {"apple", 0, 0, 1}, + {"apple", 1, 1, 1}, + {"banana", 0, 1, 1}, + {"banana", 1, 3, 1}, + {"blueberry", 0, 3, 0}, + {"blueberry", 1, 3, 0}, + {"doughnut", 0, 4, 1}, + {"doughnut", 1, 5, 1}, + }; + + size_t i; + for (i=0; istring, b->string), + c == 0, + c < 0 +) + +btree_search_implement ( + order_by_number, + const struct foo *, + , + a->number == b->number, + a->number < b->number +) diff --git a/ccan/btree/test/run-trivial.c b/ccan/btree/test/run-trivial.c new file mode 100644 index 00000000..6992bf61 --- /dev/null +++ b/ccan/btree/test/run-trivial.c @@ -0,0 +1,357 @@ +/* Include the main header first, to test it works */ +#include +/* Include the C files directly. */ +#include +#include + +#include + +struct test_item { + int key; + int value; +}; + +static btree_search_implement( + order_by_key, + struct test_item *, + , + a->key == b->key, + a->key < b->key +) + +static int insert_test_item(struct btree *btree, int key, int value) +{ + struct test_item key_item = {key, -101}; + struct test_item *item; + btree_iterator iter; + + if (btree_find_first(btree, &key_item, iter)) { + /* Don't insert new item, but do update its value. */ + item = iter->item; + item->value = value; + return 0; + } + + item = malloc(sizeof(*item)); + item->key = key; + item->value = value; + + btree_insert_at(iter, item); + + return 1; +} + +static int lookup_test_item(const struct btree *btree, int key) +{ + struct test_item key_item = {key, -102}; + struct test_item *item; + btree_iterator iter; + + if (!btree_find_first(btree, &key_item, iter)) + return -100; + + item = iter->item; + return item->value; +} + +static int destroy_test_item(void *item, void *ctx) { + (void) ctx; + free(item); + return 1; +} + +struct test_insert_entry { + int key; + int value; + int expected_return; +}; + +struct test_traverse_entry { + int key; + int value; +}; + +static void print_indent(unsigned int indent) { + while (indent--) + fputs("\t", stdout); +} + +static void btree_node_trace(struct btree_node *node, unsigned int indent) +{ + unsigned int i; + for (i=0; icount; i++) { + if (node->depth) + btree_node_trace(node->branch[i], indent+1); + print_indent(indent); + puts(node->item[i]); + } + if (node->depth) + btree_node_trace(node->branch[node->count], indent+1); +} + +static void btree_trace(struct btree *btree) +{ + btree_node_trace(btree->root, 0); +} + +static void test_insert(struct btree *btree) +{ + struct test_insert_entry ent[] = { + {3, 1, 1}, {4, 1, 1}, {5, 9, 1}, {2, 6, 1}, {5, 3, 0}, {5, 8, 0}, + {9, 7, 1}, {9, 3, 0}, {2, 3, 0}, {8, 4, 1}, {6, 2, 1}, {6, 4, 0}, + {3, 3, 0}, {8, 3, 0}, {2, 7, 0}, {9, 5, 0}, {0, 2, 1}, {8, 8, 0}, + {4, 1, 0}, {9, 7, 0}, {1, 6, 1}, {9, 3, 0}, {9, 9, 0}, {3, 7, 0}, + {5, 1, 0}, {0, 5, 0}, {8, 2, 0}, {0, 9, 0}, {7, 4, 1}, {9, 4, 0}, + {4, 5, 0}, {9, 2, 0} + }; + size_t i, count = sizeof(ent) / sizeof(*ent); + + for (i = 0; i < count; i++) { + int ret = insert_test_item(btree, ent[i].key, ent[i].value); + ok1(ret == ent[i].expected_return); + } +} + +static void test_find_traverse(struct btree *btree) +{ + struct test_traverse_entry ent[] = { + {0, 9}, {1, 6}, {2, 7}, {3, 7}, {4, 5}, + {5, 1}, {6, 4}, {7, 4}, {8, 2}, {9, 2} + }; + size_t i, count = sizeof(ent) / sizeof(*ent); + btree_iterator iter; + + i = 0; + for (btree_begin(btree, iter); btree_next(iter);) { + struct test_item *item = iter->item; + + if (i >= count) { + fail("Too many items in btree according to forward traversal"); + break; + } + + ok1(lookup_test_item(btree, item->key) == item->value); + ok1(item->key == ent[i].key && item->value == ent[i].value); + + i++; + } + + if (i != count) + fail("Not enough items in btree according to forward traversal"); + + i = count; + for (btree_end(btree, iter); btree_prev(iter);) { + struct test_item *item = iter->item; + + if (!i--) { + fail("Too many items in btree according to backward traversal"); + break; + } + + ok1(lookup_test_item(btree, item->key) == item->value); + ok1(item->key == ent[i].key && item->value == ent[i].value); + } + + if (i != 0) + fail("Not enough items in btree according to backward traversal"); +} + +static btree_search_proto order_by_string; + +static btree_search_implement( + order_by_string, //function name + const char*, //key type + int c = strcmp(a, b), //setup + c == 0, // a == b predicate + c < 0 // a < b predicate +) + +//used in the test case to sort the test strings +static int compare_by_string(const void *ap, const void *bp) +{ + const char * const *a = ap; + const char * const *b = bp; + return strcmp(*a, *b); +} + +static void test_traverse(struct btree *btree, const char *sorted[], size_t count) +{ + btree_iterator iter, iter2; + size_t i; + + i = 0; + for (btree_begin(btree, iter); btree_next(iter);) { + if (i >= count) { + fail("Too many items in btree according to forward traversal"); + break; + } + + ok1(iter->item == sorted[i]); + + btree_find_first(btree, sorted[i], iter2); + ok1(iter2->item == sorted[i]); + + i++; + } + + if (i != count) + fail("Not enough items in btree according to forward traversal"); + + i = count; + for (btree_end(btree, iter); btree_prev(iter);) { + if (!i--) { + fail("Too many items in btree according to backward traversal"); + break; + } + + ok1(iter->item == sorted[i]); + + btree_find_first(btree, sorted[i], iter2); + ok1(iter2->item == sorted[i]); + } + + if (i != 0) + fail("Not enough items in btree according to backward traversal"); +} + +#if 0 +//(tries to) remove the key from both the btree and the test array. Returns 1 on success, 0 on failure. +//success is when an item is removed from the btree and the array, or when none is removed from either +//failure is when an item is removed from the btree but not the array or vice versa +//after removing, it tries removing again to make sure that removal returns 0 +static int test_remove(struct btree *btree, struct btree_item items[], size_t *count, const char *key) +{ + size_t i; + + for (i = *count; i--;) { + if (!strcmp(items[i].key, key)) { + //item found in array + memmove(&items[i], &items[i+1], (*count-(i+1))*sizeof(*items)); + (*count)--; + + //puts("----------"); + //btree_trace(btree); + + //removal should succeed, as the key should be there + //this is not a contradiction; the test is performed twice + return btree_remove(btree, key) && !btree_remove(btree, key); + } + } + + //removal should fail, as the key should not be there + //this is not redundant; the test is performed twice + return !btree_remove(btree, key) && !btree_remove(btree, key); +} +#endif + +static void test_search_implement(void) +{ + struct btree *btree = btree_new(order_by_string); + size_t i; + + const char *unsorted[] = { + "md4", + "isaac", + "noerr", + "talloc_link", + "asearch", + "tap", + "crcsync", + "wwviaudio", + "array_size", + "alignof", + "str", + "read_write_all", + "grab_file", + "out", + "daemonize", + "array", + "crc", + "str_talloc", + "build_assert", + "talloc", + "alloc", + "endian", + "btree", + "typesafe_cb", + "check_type", + "list", + "ciniparser", + "ilog", + "ccan_tokenizer", + "tdb", + "block_pool", + "sparse_bsearch", + "container_of", + "stringmap", + "hash", + "short_types", + "ogg_to_pcm", + "antithread", + }; + size_t count = sizeof(unsorted) / sizeof(*unsorted); + const char *sorted[count]; + + memcpy(sorted, unsorted, sizeof(sorted)); + qsort(sorted, count, sizeof(*sorted), compare_by_string); + + for (i=0; iroot == NULL); + */ + + btree_delete(btree); +} + +int main(void) +{ + struct btree *btree; + + plan_tests(224); + + btree = btree_new(order_by_key); + btree->destroy = destroy_test_item; + test_insert(btree); + test_find_traverse(btree); + btree_delete(btree); + + test_search_implement(); + + return exit_status(); +} -- 2.39.2