From: Rusty Russell Date: Wed, 20 Oct 2010 05:40:16 +0000 (+1030) Subject: avl: new module X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=700aea923d8fb6cb1c82333d4c11e2bd8bbed3c5 avl: new module --- diff --git a/ccan/avl/_info b/ccan/avl/_info new file mode 100644 index 00000000..0f1d89a4 --- /dev/null +++ b/ccan/avl/_info @@ -0,0 +1,81 @@ +#include +#include "config.h" + +/** + * avl - Key-value dictionary based on AVL trees + * + * A simple, well-tested implementation of AVL trees for mapping + * unique keys to values. This implementation supports insertion, + * removal, lookup, and traversal. + * + * An AVL tree is a self-balancing binary tree that performs + * insertion, removal, and lookup in O(log n) time per operation. + * + * Example: + * #include + * + * #include + * #include + * #include + * + * struct tally { + * long count; + * }; + * #define new_tally() calloc(1, sizeof(struct tally)) + * + * static void chomp(char *str) + * { + * char *end = strchr(str, 0); + * if (end > str && end[-1] == '\n') + * end[-1] = 0; + * } + * + * int main(void) + * { + * AVL *avl = avl_new((AvlCompare) strcmp); + * AvlIter i; + * struct tally *tally; + * char line[256]; + * + * while (fgets(line, sizeof(line), stdin)) + * { + * chomp(line); + * + * tally = avl_lookup(avl, line); + * if (tally == NULL) + * avl_insert(avl, strdup(line), tally = new_tally()); + * + * tally->count++; + * } + * + * avl_foreach(i, avl) { + * char *line = i.key; + * struct tally *tally = i.value; + * + * printf("% 5ld: %s\n", tally->count, line); + * + * free(line); + * free(tally); + * } + * + * avl_free(avl); + * + * return 0; + * } + * + * Licence: ISC + * Author: Joey Adams + */ +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/avl/avl.c b/ccan/avl/avl.c new file mode 100644 index 00000000..ccecda7e --- /dev/null +++ b/ccan/avl/avl.c @@ -0,0 +1,442 @@ +/* + * Copyright (c) 2010 Joseph Adams + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "avl.h" + +#include +#include + +static AvlNode *mkNode(const void *key, const void *value); +static void freeNode(AvlNode *node); + +static AvlNode *lookup(const AVL *avl, AvlNode *node, const void *key); + +static bool insert(AVL *avl, AvlNode **p, const void *key, const void *value); +static bool remove(AVL *avl, AvlNode **p, const void *key, AvlNode **ret); +static bool removeExtremum(AvlNode **p, int side, AvlNode **ret); + +static int sway(AvlNode **p, int sway); +static void balance(AvlNode **p, int side); + +static bool checkBalances(AvlNode *node, int *height); +static bool checkOrder(AVL *avl); +static size_t countNode(AvlNode *node); + +/* + * Utility macros for converting between + * "balance" values (-1 or 1) and "side" values (0 or 1). + * + * bal(0) == -1 + * bal(1) == +1 + * side(-1) == 0 + * side(+1) == 1 + */ +#define bal(side) ((side) == 0 ? -1 : 1) +#define side(bal) ((bal) == 1 ? 1 : 0) + +static int sign(int cmp) +{ + if (cmp < 0) + return -1; + if (cmp == 0) + return 0; + return 1; +} + +AVL *avl_new(AvlCompare compare) +{ + AVL *avl = malloc(sizeof(*avl)); + + assert(avl != NULL); + + avl->compare = compare; + avl->root = NULL; + avl->count = 0; + return avl; +} + +void avl_free(AVL *avl) +{ + freeNode(avl->root); + free(avl); +} + +void *avl_lookup(const AVL *avl, const void *key) +{ + AvlNode *found = lookup(avl, avl->root, key); + return found ? (void*) found->value : NULL; +} + +AvlNode *avl_lookup_node(const AVL *avl, const void *key) +{ + return lookup(avl, avl->root, key); +} + +size_t avl_count(const AVL *avl) +{ + return avl->count; +} + +bool avl_insert(AVL *avl, const void *key, const void *value) +{ + size_t old_count = avl->count; + insert(avl, &avl->root, key, value); + return avl->count != old_count; +} + +bool avl_remove(AVL *avl, const void *key) +{ + AvlNode *node = NULL; + + remove(avl, &avl->root, key, &node); + + if (node == NULL) { + return false; + } else { + free(node); + return true; + } +} + +static AvlNode *mkNode(const void *key, const void *value) +{ + AvlNode *node = malloc(sizeof(*node)); + + assert(node != NULL); + + node->key = key; + node->value = value; + node->lr[0] = NULL; + node->lr[1] = NULL; + node->balance = 0; + return node; +} + +static void freeNode(AvlNode *node) +{ + if (node) { + freeNode(node->lr[0]); + freeNode(node->lr[1]); + free(node); + } +} + +static AvlNode *lookup(const AVL *avl, AvlNode *node, const void *key) +{ + int cmp; + + if (node == NULL) + return NULL; + + cmp = avl->compare(key, node->key); + + if (cmp < 0) + return lookup(avl, node->lr[0], key); + if (cmp > 0) + return lookup(avl, node->lr[1], key); + return node; +} + +/* + * Insert a key/value into a subtree, rebalancing if necessary. + * + * Return true if the subtree's height increased. + */ +static bool insert(AVL *avl, AvlNode **p, const void *key, const void *value) +{ + if (*p == NULL) { + *p = mkNode(key, value); + avl->count++; + return true; + } else { + AvlNode *node = *p; + int cmp = sign(avl->compare(key, node->key)); + + if (cmp == 0) { + node->key = key; + node->value = value; + return false; + } + + if (!insert(avl, &node->lr[side(cmp)], key, value)) + return false; + + /* If tree's balance became -1 or 1, it means the tree's height grew due to insertion. */ + return sway(p, cmp) != 0; + } +} + +/* + * Remove the node matching the given key. + * If present, return the removed node through *ret . + * The returned node's lr and balance are meaningless. + * + * Return true if the subtree's height decreased. + */ +static bool remove(AVL *avl, AvlNode **p, const void *key, AvlNode **ret) +{ + if (*p == NULL) { + return false; + } else { + AvlNode *node = *p; + int cmp = sign(avl->compare(key, node->key)); + + if (cmp == 0) { + *ret = node; + avl->count--; + + if (node->lr[0] != NULL && node->lr[1] != NULL) { + AvlNode *replacement; + int side; + bool shrunk; + + /* Pick a subtree to pull the replacement from such that + * this node doesn't have to be rebalanced. */ + side = node->balance <= 0 ? 0 : 1; + + shrunk = removeExtremum(&node->lr[side], 1 - side, &replacement); + + replacement->lr[0] = node->lr[0]; + replacement->lr[1] = node->lr[1]; + replacement->balance = node->balance; + *p = replacement; + + if (!shrunk) + return false; + + replacement->balance -= bal(side); + + /* If tree's balance became 0, it means the tree's height shrank due to removal. */ + return replacement->balance == 0; + } + + if (node->lr[0] != NULL) + *p = node->lr[0]; + else + *p = node->lr[1]; + + return true; + + } else { + if (!remove(avl, &node->lr[side(cmp)], key, ret)) + return false; + + /* If tree's balance became 0, it means the tree's height shrank due to removal. */ + return sway(p, -cmp) == 0; + } + } +} + +/* + * Remove either the left-most (if side == 0) or right-most (if side == 1) + * node in a subtree, returning the removed node through *ret . + * The returned node's lr and balance are meaningless. + * + * The subtree must not be empty (i.e. *p must not be NULL). + * + * Return true if the subtree's height decreased. + */ +static bool removeExtremum(AvlNode **p, int side, AvlNode **ret) +{ + AvlNode *node = *p; + + if (node->lr[side] == NULL) { + *ret = node; + *p = node->lr[1 - side]; + return true; + } + + if (!removeExtremum(&node->lr[side], side, ret)) + return false; + + /* If tree's balance became 0, it means the tree's height shrank due to removal. */ + return sway(p, -bal(side)) == 0; +} + +/* + * Rebalance a node if necessary. Think of this function + * as a higher-level interface to balance(). + * + * sway must be either -1 or 1, and indicates what was added to + * the balance of this node by a prior operation. + * + * Return the new balance of the subtree. + */ +static int sway(AvlNode **p, int sway) +{ + if ((*p)->balance != sway) + (*p)->balance += sway; + else + balance(p, side(sway)); + + return (*p)->balance; +} + +/* + * Perform tree rotations on an unbalanced node. + * + * side == 0 means the node's balance is -2 . + * side == 1 means the node's balance is +2 . + */ +static void balance(AvlNode **p, int side) +{ + AvlNode *node = *p, + *child = node->lr[side]; + int opposite = 1 - side; + int bal = bal(side); + + if (child->balance != -bal) { + /* Left-left (side == 0) or right-right (side == 1) */ + node->lr[side] = child->lr[opposite]; + child->lr[opposite] = node; + *p = child; + + child->balance -= bal; + node->balance = -child->balance; + + } else { + /* Left-right (side == 0) or right-left (side == 1) */ + AvlNode *grandchild = child->lr[opposite]; + + node->lr[side] = grandchild->lr[opposite]; + child->lr[opposite] = grandchild->lr[side]; + grandchild->lr[side] = child; + grandchild->lr[opposite] = node; + *p = grandchild; + + node->balance = 0; + child->balance = 0; + + if (grandchild->balance == bal) + node->balance = -bal; + else if (grandchild->balance == -bal) + child->balance = bal; + + grandchild->balance = 0; + } +} + + +/************************* avl_check_invariants() *************************/ + +bool avl_check_invariants(AVL *avl) +{ + int dummy; + + return checkBalances(avl->root, &dummy) + && checkOrder(avl) + && countNode(avl->root) == avl->count; +} + +static bool checkBalances(AvlNode *node, int *height) +{ + if (node) { + int h0, h1; + + if (!checkBalances(node->lr[0], &h0)) + return false; + if (!checkBalances(node->lr[1], &h1)) + return false; + + if (node->balance != h1 - h0 || node->balance < -1 || node->balance > 1) + return false; + + *height = (h0 > h1 ? h0 : h1) + 1; + return true; + } else { + *height = 0; + return true; + } +} + +static bool checkOrder(AVL *avl) +{ + AvlIter i; + const void *last = NULL; + bool last_set = false; + + avl_foreach(i, avl) { + if (last_set && avl->compare(last, i.key) >= 0) + return false; + last = i.key; + last_set = true; + } + + return true; +} + +static size_t countNode(AvlNode *node) +{ + if (node) + return 1 + countNode(node->lr[0]) + countNode(node->lr[1]); + else + return 0; +} + + +/************************* Traversal *************************/ + +void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir) +{ + AvlNode *node = avl->root; + + iter->stack_index = 0; + iter->direction = dir; + + if (node == NULL) { + iter->key = NULL; + iter->value = NULL; + iter->node = NULL; + return; + } + + while (node->lr[dir] != NULL) { + iter->stack[iter->stack_index++] = node; + node = node->lr[dir]; + } + + iter->key = (void*) node->key; + iter->value = (void*) node->value; + iter->node = node; +} + +void avl_iter_next(AvlIter *iter) +{ + AvlNode *node = iter->node; + AvlDirection dir = iter->direction; + + if (node == NULL) + return; + + node = node->lr[1 - dir]; + if (node != NULL) { + while (node->lr[dir] != NULL) { + iter->stack[iter->stack_index++] = node; + node = node->lr[dir]; + } + } else if (iter->stack_index > 0) { + node = iter->stack[--iter->stack_index]; + } else { + iter->key = NULL; + iter->value = NULL; + iter->node = NULL; + return; + } + + iter->node = node; + iter->key = (void*) node->key; + iter->value = (void*) node->value; +} diff --git a/ccan/avl/avl.h b/ccan/avl/avl.h new file mode 100644 index 00000000..c78e8df8 --- /dev/null +++ b/ccan/avl/avl.h @@ -0,0 +1,119 @@ +/* + * Copyright (c) 2010 Joseph Adams + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef CCAN_AVL_H +#define CCAN_AVL_H + +#include +#include + +typedef struct AVL AVL; +typedef struct AvlNode AvlNode; +typedef struct AvlIter AvlIter; + +typedef int (*AvlCompare)(const void *, const void *); + +AVL *avl_new(AvlCompare compare); + /* Create a new AVL tree sorted with the given comparison function. */ + +void avl_free(AVL *avl); + /* Free an AVL tree. */ + +void *avl_lookup(const AVL *avl, const void *key); + /* O(log n). Lookup a value at a key. Return NULL if the key is not present. */ + +#define avl_member(avl, key) (!!avl_lookup_node(avl, key)) + /* O(log n). See if a key is present. */ + +size_t avl_count(const AVL *avl); + /* O(1). Return the number of elements in the tree. */ + +bool avl_insert(AVL *avl, const void *key, const void *value); + /* + * O(log n). Insert a key/value pair, or replace it if already present. + * + * Return false if the insertion replaced an existing key/value. + */ + +bool avl_remove(AVL *avl, const void *key); + /* + * O(log n). Remove a key/value pair (if present). + * + * Return true if it was removed. + */ + +bool avl_check_invariants(AVL *avl); + /* For testing purposes. This function will always return true :-) */ + + +/************************* Traversal *************************/ + +#define avl_foreach(iter, avl) avl_traverse(iter, avl, FORWARD) + /* + * O(n). Traverse an AVL tree in order. + * + * Example: + * + * AvlIter i; + * + * avl_foreach(i, avl) + * printf("%s -> %s\n", i.key, i.value); + */ + +#define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD) + /* O(n). Traverse an AVL tree in reverse order. */ + +typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection; + +struct AvlIter { + void *key; + void *value; + AvlNode *node; + + /* private */ + AvlNode *stack[100]; + int stack_index; + AvlDirection direction; +}; + +void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir); +void avl_iter_next(AvlIter *iter); +#define avl_traverse(iter, avl, direction) \ + for (avl_iter_begin(&(iter), avl, direction); \ + (iter).node != NULL; \ + avl_iter_next(&iter)) + + +/***************** Internal data structures ******************/ + +struct AVL { + AvlCompare compare; + AvlNode *root; + size_t count; +}; + +struct AvlNode { + const void *key; + const void *value; + + AvlNode *lr[2]; + int balance; /* -1, 0, or 1 */ +}; + +AvlNode *avl_lookup_node(const AVL *avl, const void *key); + /* O(log n). Lookup an AVL node by key. Return NULL if not present. */ + +#endif diff --git a/ccan/avl/test/run.c b/ccan/avl/test/run.c new file mode 100644 index 00000000..99764658 --- /dev/null +++ b/ccan/avl/test/run.c @@ -0,0 +1,487 @@ +/* + * Copyright (c) 2010 Joseph Adams + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include + +#define remove remove_ +#include +#undef remove + +#include + +#include +#include +#include +#include + +#define ANIMATE_RANDOM_ACCESS 0 + +#if ANIMATE_RANDOM_ACCESS + +#include + +typedef int64_t msec_t; + +static msec_t time_ms(void) +{ + struct timeval tv; + gettimeofday(&tv, NULL); + return (msec_t)tv.tv_sec * 1000 + tv.tv_usec / 1000; +} + +#endif + +uint32_t rand32_state = 0; + +/* + * Finds a pseudorandom 32-bit number from 0 to 2^32-1 . + * Uses the BCPL linear congruential generator method. + * + * Note: this method (or maybe just this implementation) seems to + * go back and forth between odd and even exactly, which can + * affect low-cardinality testing if the cardinality given is even. + */ +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; + } + } +} + +static struct { + size_t success; + size_t passed_invariants_checks; + + size_t excess; + size_t duplicate; + size_t missing; + size_t incorrect; + size_t failed; + size_t failed_invariants_checks; +} stats; + +static void clear_stats(void) +{ + memset(&stats, 0, sizeof(stats)); +} + +static bool 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.passed_invariants_checks) + printf(" Passed invariants checks: %zu\n", stats.passed_invariants_checks); + + 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.failed_invariants_checks) + failed = 1, printf(" Failed invariants checks: %zu\n", stats.failed_invariants_checks); + + return !failed; +} + +struct test_item { + uint32_t key; + uint32_t value; + size_t insert_id; /* needed because qsort is not a stable sort */ +}; + +static int compare_uint32_t(const void *ap, const void *bp) +{ + uint32_t a = *(const uint32_t *)ap; + uint32_t b = *(const uint32_t *)bp; + + if (a < b) + return -1; + if (a > b) + return 1; + return 0; +} + +static int compare_test_item(const void *ap, const void *bp) +{ + const struct test_item *a = *(void**)ap, *b = *(void**)bp; + + if (a->key < b->key) + return -1; + if (a->key > b->key) + return 1; + + if (a->insert_id < b->insert_id) + return -1; + if (a->insert_id > b->insert_id) + return 1; + + return 0; +} + +static bool test_insert_item(AVL *avl, struct test_item *item) +{ + avl_insert(avl, &item->key, &item->value); + return true; +} + +static bool test_lookup_item(const AVL *avl, const struct test_item *item) +{ + return avl_member(avl, &item->key) && avl_lookup(avl, &item->key) == &item->value; +} + +static bool test_remove_item(AVL *avl, struct test_item *item) +{ + return avl_remove(avl, &item->key); +} + +static void test_foreach(AVL *avl, struct test_item **test_items, int count) +{ + AvlIter iter; + int i; + + i = 0; + avl_foreach(iter, avl) { + if (i >= count) { + stats.excess++; + continue; + } + if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value) + stats.success++; + else + stats.incorrect++; + i++; + } +} + +static void test_foreach_reverse(AVL *avl, struct test_item **test_items, int count) +{ + AvlIter iter; + int i; + + i = count - 1; + avl_foreach_reverse(iter, avl) { + if (i < 0) { + stats.excess++; + continue; + } + if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value) + stats.success++; + else + stats.incorrect++; + i--; + } +} + +static void benchmark(size_t max_per_trial, size_t round_count, bool random_counts, int cardinality) +{ + struct test_item **test_item; + struct test_item *test_item_array; + size_t i, o, 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 = rand32(); + test_item[i]->value = rand32(); + + if (cardinality) + test_item[i]->key %= cardinality; + } + scramble(test_item, count, sizeof(*test_item)); + + avl = avl_new(compare_uint32_t); + + clear_stats(); + printf(" Inserting %zu items...\n", count); + for (i=0; iinsert_id = i; + } else { + printf("invariants check failed at insertion %zu\n", i); + stats.failed++; + } + + /* Periodically do an invariants check */ + if (count / 10 > 0 && i % (count / 10) == 0) { + if (avl_check_invariants(avl)) + stats.passed_invariants_checks++; + else + stats.failed_invariants_checks++; + } + } + ok1(print_stats("Inserted", count)); + ok1(avl_check_invariants(avl)); + + /* remove early duplicates, as they are shadowed in insertions. */ + qsort(test_item, count, sizeof(*test_item), compare_test_item); + for (i = 0, o = 0; i < count;) { + uint32_t k = test_item[i]->key; + do i++; while (i < count && test_item[i]->key == k); + test_item[o++] = test_item[i-1]; + } + count = o; + ok1(avl_count(avl) == count); + + scramble(test_item, count, sizeof(*test_item)); + + printf(" Finding %zu items...\n", count); + clear_stats(); + for (i=0; i 0 && i % (count / 10) == 0) { + if (avl_check_invariants(avl)) + stats.passed_invariants_checks++; + else + stats.failed_invariants_checks++; + } + } + ok1(print_stats("Deleted", count)); + ok1(avl_count(avl) == 0); + ok1(avl_check_invariants(avl)); + + avl_free(avl); + } + + free(test_item); + free(test_item_array); +} + +static int compare_ptr(const void *a, const void *b) +{ + if (a < b) + return -1; + if (a > b) + return 1; + return 0; +} + +struct fail_total { + int64_t fail; + int64_t total; +}; + +static bool print_pass_fail(struct fail_total *pf, const char *label) +{ + long long fail = pf->fail, + total = pf->total; + + printf("%s:\t%lld / %lld\n", label, total - fail, total); + + return fail == 0; +} + +static void test_random_access(uint32_t max, int64_t ops) +{ + char *in_tree; + AVL *avl; + int64_t i; + struct { + struct fail_total + inserts, lookups, removes, checks; + } s; + + #if ANIMATE_RANDOM_ACCESS + msec_t last_update, now; + msec_t interval = 100; + #endif + + memset(&s, 0, sizeof(s)); + + in_tree = malloc(max); + memset(in_tree, 0, max); + + avl = avl_new(compare_ptr); + + #if ANIMATE_RANDOM_ACCESS + now = time_ms(); + last_update = now - interval; + #endif + + for (i = 0; i < ops; i++) { + char *item = &in_tree[rand32() % max]; + char *found; + bool inserted, removed; + + #if ANIMATE_RANDOM_ACCESS + now = time_ms(); + if (now >= last_update + interval) { + last_update = now; + printf("\r%.2f%%\t%zu / %zu\033[K", (double)i * 100 / ops, avl_count(avl), max); + fflush(stdout); + } + #endif + + switch (rand32() % 3) { + case 0: + inserted = avl_insert(avl, item, item); + + if ((*item == 0 && !inserted) || + (*item == 1 && inserted)) + s.inserts.fail++; + + if (inserted) + *item = 1; + + s.inserts.total++; + break; + + case 1: + found = avl_lookup(avl, item); + + if ((*item == 0 && found != NULL) || + (*item == 1 && found != item) || + (avl_member(avl, item) != !!found)) + s.lookups.fail++; + + s.lookups.total++; + break; + + case 2: + removed = avl_remove(avl, item); + + if ((*item == 0 && removed) || + (*item == 1 && !removed)) + s.removes.fail++; + + if (removed) + *item = 0; + + s.removes.total++; + break; + } + + /* Periodically do an invariants check */ + if (ops / 10 > 0 && i % (ops / 10) == 0) { + if (!avl_check_invariants(avl)) + s.checks.fail++; + s.checks.total++; + } + } + + #if ANIMATE_RANDOM_ACCESS + printf("\r\033[K"); + #endif + + avl_free(avl); + free(in_tree); + + ok1(print_pass_fail(&s.inserts, "Inserts")); + ok1(print_pass_fail(&s.lookups, "Lookups")); + ok1(print_pass_fail(&s.removes, "Removes")); + ok1(print_pass_fail(&s.checks, "Invariants checks")); +} + +int main(void) +{ + plan_tests(18 * 3 + 4); + + benchmark(100000, 2, false, 0); + benchmark(100000, 2, false, 12345); + benchmark(100000, 2, false, 100001); + + printf("Running random access test\n"); + test_random_access(12345, 1234567); + + return exit_status(); +}