diff options
| -rw-r--r-- | COPYING | 13 | ||||
| -rwxr-xr-x | plot.py | 34 | ||||
| -rw-r--r-- | src/tree.c | 724 | ||||
| -rw-r--r-- | test/tree_bench.c | 205 | ||||
| -rw-r--r-- | test/tree_test.c | 158 | ||||
| -rwxr-xr-x | waf | bin | 0 -> 86496 bytes | |||
| -rw-r--r-- | wscript | 143 | ||||
| -rw-r--r-- | zix.pc.in | 10 | ||||
| -rw-r--r-- | zix/zix.h | 122 |
9 files changed, 1409 insertions, 0 deletions
@@ -0,0 +1,13 @@ +Copyright 2011 David Robillard <http://drobilla.net> + +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. + +THIS 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. @@ -0,0 +1,34 @@ +#!/usr/bin/env python + +import sys +import os + +from matplotlib import pyplot +from matplotlib.pyplot import * + +for i in range(len(sys.argv) - 1): + filename = sys.argv[i+1] + file = open(filename, 'r') + + pyplot.subplot(2, 1, i + 1) + pyplot.xlabel('Number of Elements') + pyplot.ylabel('Time (s)') + + ns = [] + zix_times = [] + glib_times = [] + for line in file: + if line[0] == '#': + continue; + (n, zix, glib) = line.split() + ns.append(int(n)) + zix_times.append(float(zix)) + glib_times.append(float(glib)) + file.close() + + matplotlib.pyplot.plot(ns, zix_times, '-o', label='ZixTree') + matplotlib.pyplot.plot(ns, glib_times, '-x', label='GSequence') + pyplot.legend(loc='upper left') + pyplot.title(os.path.splitext(os.path.basename(filename))[0].title()) + +matplotlib.pyplot.show() diff --git a/src/tree.c b/src/tree.c new file mode 100644 index 0000000..5d09680 --- /dev/null +++ b/src/tree.c @@ -0,0 +1,724 @@ +/* + Copyright 2011 David Robillard <http://drobilla.net> + + 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. + + THIS 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 <assert.h> +#include <inttypes.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "zix/zix.h" + +// #define ZIX_TREE_DUMP 1 +// #define ZIX_TREE_VERIFY 1 +// #define ZIX_TREE_HYPER_VERIFY 1 + +#define MIN(a, b) (((a) < (b)) ? (a) : (b)) +#define MAX(a, b) (((a) > (b)) ? (a) : (b)) + +struct _ZixTree { + ZixTreeNode* root; + ZixComparator cmp; + void* cmp_data; + bool allow_duplicates; +}; + +struct _ZixTreeNode { + struct _ZixTreeNode* parent; + struct _ZixTreeNode* left; + struct _ZixTreeNode* right; + const void* data; + int8_t balance; +}; + + +#ifdef ZIX_TREE_DUMP +static void +zix_tree_print(ZixTreeNode* node, int level) +{ + if (node) { + if (!node->parent) { + printf("{{{\n"); + } + zix_tree_print(node->right, level + 1); + for (int i = 0; i < level; i++) { + printf(" "); + } + printf("%ld.%d\n", (intptr_t)node->data, node->balance); + zix_tree_print(node->left, level + 1); + if (!node->parent) { + printf("}}}\n"); + } + } +} +# define DUMP(t) zix_tree_print(t->root, 0) +#else +# define DUMP(t) +#endif + +ZIX_API +ZixTree* +zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data) +{ + ZixTree* t = malloc(sizeof(struct _ZixTree)); + t->root = NULL; + t->cmp = cmp; + t->cmp_data = cmp_data; + t->allow_duplicates = allow_duplicates; + return t; +} + +static void +zix_tree_free_rec(ZixTreeNode* n) +{ + if (n) { + zix_tree_free_rec(n->left); + zix_tree_free_rec(n->right); + free(n); + } +} + +ZIX_API +void +zix_tree_free(ZixTree* t) +{ + zix_tree_free_rec(t->root); + + free(t); +} + +#ifdef ZIX_TREE_HYPER_VERIFY +static size_t +height(ZixTreeNode* n) +{ + if (!n) { + return 0; + } else { + return 1 + MAX(height(n->left), height(n->right)); + } +} +#endif + +#if defined(ZIX_TREE_VERIFY) || !defined(NDEBUG) +static bool +verify_balance(ZixTreeNode* n) +{ + if (!n) { + return true; + } + + if (n->balance < -2 || n->balance > 2) { + fprintf(stderr, "Balance out of range : %ld (balance %d)\n", + (intptr_t)n->data, n->balance); + return false; + } + + if (n->balance < 0 && !n->left) { + fprintf(stderr, "Bad balance : %ld (balance %d) has no left child\n", + (intptr_t)n->data, n->balance); + return false; + } + + if (n->balance > 0 && !n->right) { + fprintf(stderr, "Bad balance : %ld (balance %d) has no right child\n", + (intptr_t)n->data, n->balance); + return false; + } + + if (n->balance != 0 && !n->left && !n->right) { + fprintf(stderr, "Bad balance : %ld (balance %d) has no children\n", + (intptr_t)n->data, n->balance); + return false; + } + +#ifdef ZIX_TREE_HYPER_VERIFY + const intptr_t left_height = (intptr_t)height(n->left); + const intptr_t right_height = (intptr_t)height(n->right); + if (n->balance != right_height - left_height) { + fprintf(stderr, "Bad balance at %ld: h_r (%zu) - l_h (%zu) != %d\n", + (intptr_t)n->data, right_height, left_height, n->balance); + assert(false); + return false; + } +#endif + + return true; +} +#endif + +#ifdef ZIX_TREE_VERIFY +static bool +verify(ZixTree* t, ZixTreeNode* n) +{ + if (!n) { + return true; + } + + if (n->parent) { + if ((n->parent->left != n) && (n->parent->right != n)) { + fprintf(stderr, "Corrupt child/parent pointers\n"); + return false; + } + } + + if (n->left) { + if (t->cmp(n->left->data, n->data, t->cmp_data) > 0) { + fprintf(stderr, "Bad order: %zu with left child\n", + (intptr_t)n->data); + fprintf(stderr, "%p ? %p\n", (void*)n, (void*)n->left); + fprintf(stderr, "%" PRIdPTR " ? %" PRIdPTR "\n", (intptr_t)n->data, + (intptr_t)n->left->data); + return false; + } + if (!verify(t, n->left)) { + return false; + } + } + + if (n->right) { + if (t->cmp(n->right->data, n->data, t->cmp_data) < 0) { + fprintf(stderr, "Bad order: %zu with right child\n", + (intptr_t)n->data); + return false; + } + if (!verify(t, n->right)) { + return false; + } + } + + if (!verify_balance(n)) { + return false; + } + + if (n->balance <= -2 || n->balance >= 2) { + fprintf(stderr, "Imbalance: %p (balance %d)\n", + (void*)n, n->balance); + return false; + } + + return true; +} +#endif + +static void +rotate(ZixTreeNode* p, ZixTreeNode* q) +{ + assert(q->parent == p); + assert(p->left == q || p->right == q); + + q->parent = p->parent; + if (q->parent) { + if (q->parent->left == p) { + q->parent->left = q; + } else { + q->parent->right = q; + } + } + + if (p->right == q) { + // Rotate left + p->right = q->left; + q->left = p; + if (p->right) { + p->right->parent = p; + } + } else { + // Rotate right + assert(p->left == q); + p->left = q->right; + q->right = p; + if (p->left) { + p->left->parent = p; + } + } + + p->parent = q; +} + +/** + * Rotate left about @a p. + * + * p q + * / \ / \ + * A q => p C + * / \ / \ + * B C A B + */ +static ZixTreeNode* +rotate_left(ZixTreeNode* p, int* height_change) +{ + ZixTreeNode* const q = p->right; + *height_change = (q->balance == 0) ? 0 : -1; + +#ifdef ZIX_TREE_DUMP + printf("LL %ld\n", (intptr_t)p->data); +#endif + + assert(p->balance == 2); + assert(q->balance == 0 || q->balance == 1); + + rotate(p, q); + + // p->balance -= 1 + MAX(0, q->balance); + // q->balance -= 1 - MIN(0, p->balance); + --q->balance; + p->balance = -(q->balance); + + assert(verify_balance(p)); + assert(verify_balance(q)); + return q; +} + +/** + * Rotate right about @a p. + * + * p q + * / \ / \ + * q C => A p + * / \ / \ + * A B B C + * + */ +static ZixTreeNode* +rotate_right(ZixTreeNode* p, int* height_change) +{ + ZixTreeNode* const q = p->left; + *height_change = (q->balance == 0) ? 0 : -1; + +#ifdef ZIX_TREE_DUMP + printf("RR %ld\n", (intptr_t)p->data); +#endif + + assert(p->balance == -2); + assert(q->balance == 0 || q->balance == -1); + + rotate(p, q); + + // p->balance += 1 - MIN(0, q->balance); + // q->balance += 1 + MAX(0, p->balance); + ++q->balance; + p->balance = -(q->balance); + + assert(verify_balance(p)); + assert(verify_balance(q)); + + return q; +} + +/** + * Rotate left about @a p->left then right about @a p. + * + * p r + * / \ / \ + * q D => q p + * / \ / \ / \ + * A r A B C D + * / \ + * B C + * + */ +static ZixTreeNode* +rotate_left_right(ZixTreeNode* p, int* height_change) +{ + ZixTreeNode* const q = p->left; + ZixTreeNode* const r = q->right; + + assert(p->balance == -2); + assert(q->balance == 1); + assert(r->balance == -1 || r->balance == 0 || r->balance == 1); + +#ifdef ZIX_TREE_DUMP + printf("LR %ld P: %2d Q: %2d R: %2d\n", + (intptr_t)p->data, p->balance, q->balance, r->balance); +#endif + + rotate(q, r); + rotate(p, r); + + q->balance -= 1 + MAX(0, r->balance); + p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance); + // r->balance += MAX(0, p->balance) + MIN(0, q->balance); + + // p->balance = (p->left && p->right) ? -MIN(r->balance, 0) : 0; + // q->balance = - MAX(r->balance, 0); + r->balance = 0; + + assert(verify_balance(p)); + assert(verify_balance(q)); + assert(verify_balance(r)); + + *height_change = -1; + return r; +} + +/** + * Rotate right about @a p->right then right about @a p. + * + * p r + * / \ / \ + * A q => p q + * / \ / \ / \ + * r D A B C D + * / \ + * B C + * + */ +static ZixTreeNode* +rotate_right_left(ZixTreeNode* p, int* height_change) +{ + ZixTreeNode* const q = p->right; + ZixTreeNode* const r = q->left; + + assert(p->balance == 2); + assert(q->balance == -1); + assert(r->balance == -1 || r->balance == 0 || r->balance == 1); + +#ifdef ZIX_TREE_DUMP + printf("RL %ld P: %2d Q: %2d R: %2d\n", + (intptr_t)p->data, p->balance, q->balance, r->balance); +#endif + + rotate(q, r); + rotate(p, r); + + q->balance += 1 - MIN(0, r->balance); + p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance); + // r->balance += MAX(0, q->balance) + MIN(0, p->balance); + + // p->balance = (p->left && p->right) ? -MAX(r->balance, 0) : 0; + // q->balance = - MIN(r->balance, 0); + r->balance = 0; + // assert(r->balance == 0); + + assert(verify_balance(p)); + assert(verify_balance(q)); + assert(verify_balance(r)); + + *height_change = -1; + return r; +} + +static ZixTreeNode* +zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) +{ +#ifdef ZIX_TREE_HYPER_VERIFY + const size_t old_height = height(node); +#endif +#ifdef ZIX_TREE_DUMP + printf("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance); +#endif + *height_change = 0; + const bool is_root = !node->parent; + assert((is_root && t->root == node) || (!is_root && t->root != node)); + ZixTreeNode* replacement = node; + if (node->balance == -2) { + assert(node->left); + if (node->left->balance == 1) { + replacement = rotate_left_right(node, height_change); + } else { + replacement = rotate_right(node, height_change); + } + } else if (node->balance == 2) { + assert(node->right); + if (node->right->balance == -1) { + replacement = rotate_right_left(node, height_change); + } else { + replacement = rotate_left(node, height_change); + } + } + if (is_root) { + assert(!replacement->parent); + t->root = replacement; + } + DUMP(t); +#ifdef ZIX_TREE_HYPER_VERIFY + assert(old_height + *height_change == height(replacement)); +#endif + return replacement; +} + +ZIX_API +int +zix_tree_insert(ZixTree* t, const void* e, ZixTreeIter* ti) +{ +#ifdef ZIX_TREE_DUMP + printf("**** INSERT %ld\n", (intptr_t)e); +#endif + int cmp = 0; + ZixTreeNode* n = t->root; + ZixTreeNode* p = NULL; + + // Find the parent p of e + while (n) { + p = n; + cmp = t->cmp(e, n->data, t->cmp_data); + if (cmp < 0) { + n = n->left; + } else if (cmp > 0) { + n = n->right; + } else if (t->allow_duplicates) { + n = n->right; + } else { + *ti = n; +#ifdef ZIX_TREE_DUMP + printf("EXISTS!\n"); +#endif + return ZIX_STATUS_EXISTS; + } + } + + // Allocate a new node n + if (!(n = malloc(sizeof(ZixTreeNode)))) { + return ZIX_STATUS_NO_MEM; + } + memset(n, '\0', sizeof(ZixTreeNode)); + n->data = e; + n->balance = 0; + *ti = n; + + bool p_height_increased = false; + + // Make p the parent of n + n->parent = p; + if (!p) { + t->root = n; + } else { + if (cmp < 0) { + assert(!p->left); + assert(p->balance == 0 || p->balance == 1); + p->left = n; + --p->balance; + p_height_increased = !p->right; + } else { + assert(!p->right); + assert(p->balance == 0 || p->balance == -1); + p->right = n; + ++p->balance; + p_height_increased = !p->left; + } + } + + DUMP(t); + + // Rebalance if necessary (at most 1 rotation) + assert(!p || p->balance == -1 || p->balance == 0 || p->balance == 1); + if (p && p_height_increased) { + int height_change = 0; + for (ZixTreeNode* i = p; i && i->parent; i = i->parent) { + if (i == i->parent->left) { + if (--i->parent->balance == -2) { + zix_tree_rebalance(t, i->parent, &height_change); + break; + } + } else { + assert(i == i->parent->right); + if (++i->parent->balance == 2) { + zix_tree_rebalance(t, i->parent, &height_change); + break; + } + } + + if (i->parent->balance == 0) { + break; + } + } + } + + DUMP(t); + +#ifdef ZIX_TREE_VERIFY + if (!verify(t, t->root)) { + return ZIX_STATUS_ERROR; + } +#endif + + return ZIX_STATUS_SUCCESS; +} + +ZIX_API +int +zix_tree_remove(ZixTree* t, ZixTreeIter ti) +{ + ZixTreeNode* n = ti; + ZixTreeNode** pp = NULL; // parent pointer + ZixTreeNode* to_balance = n->parent; // lowest node to start rebalace at + int8_t d_balance = 0; // delta(balance) for n->parent + +#ifdef ZIX_TREE_DUMP + printf("*** REMOVE %ld\n", (intptr_t)n->data); +#endif + + if ((n == t->root) && !n->left && !n->right) { + t->root = NULL; + return ZIX_STATUS_SUCCESS; + } + + // Set pp to the parent pointer to n, if applicable + if (n->parent) { + assert(n->parent->left == n || n->parent->right == n); + if (n->parent->left == n) { // n is left child + pp = &n->parent->left; + d_balance = 1; + } else { // n is right child + assert(n->parent->right == n); + pp = &n->parent->right; + d_balance = -1; + } + } + + assert(!pp || *pp == n); + + int height_change = 0; + if (!n->left && !n->right) { + // n is a leaf, just remove it + if (pp) { + *pp = NULL; + to_balance = n->parent; + height_change = (!n->parent->left && !n->parent->right) ? -1 : 0; + } + } else if (!n->left) { + // Replace n with right (only) child + if (pp) { + *pp = n->right; + to_balance = n->parent; + } else { + t->root = n->right; + } + n->right->parent = n->parent; + height_change = -1; + } else if (!n->right) { + // Replace n with left (only) child + if (pp) { + *pp = n->left; + to_balance = n->parent; + } else { + t->root = n->left; + } + n->left->parent = n->parent; + height_change = -1; + } else { + // Replace n with in-order successor (leftmost child of right subtree) + ZixTreeNode* replace = n->right; + while (replace->left) { + assert(replace->left->parent == replace); + replace = replace->left; + } + + // Remove replace from parent (replace_p) + if (replace->parent->left == replace) { + height_change = replace->parent->right ? 0 : -1; + d_balance = 1; + to_balance = replace->parent; + replace->parent->left = replace->right; + } else { + assert(replace->parent == n); + height_change = replace->parent->left ? 0 : -1; + d_balance = -1; + to_balance = replace->parent; + replace->parent->right = replace->right; + } + + if (to_balance == n) { + to_balance = replace; + } + + if (replace->right) { + replace->right->parent = replace->parent; + } + + replace->balance = n->balance; + + // Swap node to delete with replace + if (pp) { + *pp = replace; + } else { + assert(t->root == n); + t->root = replace; + } + replace->parent = n->parent; + replace->left = n->left; + n->left->parent = replace; + replace->right = n->right; + if (n->right) { + n->right->parent = replace; + } + + assert(!replace->parent + || replace->parent->left == replace + || replace->parent->right == replace); + } + + // Rebalance starting at to_balance upwards. + for (ZixTreeNode* i = to_balance; i; i = i->parent) { + i->balance += d_balance; + if (d_balance == 0 || i->balance == -1 || i->balance == 1) { + break; + } + + assert(i != n); + i = zix_tree_rebalance(t, i, &height_change); + if (i->balance == 0) { + height_change = -1; + } + + if (i->parent) { + if (i == i->parent->left) { + d_balance = height_change * -1; + } else { + assert(i == i->parent->right); + d_balance = height_change; + } + } + } + + DUMP(t); + +#ifdef ZIX_TREE_VERIFY + if (!verify(t, t->root)) { + return ZIX_STATUS_ERROR; + } +#endif + + return ZIX_STATUS_SUCCESS; +} + +ZIX_API +int +zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter* ti) +{ + ZixTreeNode* n = t->root; + while (n) { + const int cmp = t->cmp(e, n->data, t->cmp_data); + if (cmp == 0) { + break; + } else if (cmp < 0) { + n = n->left; + } else { + n = n->right; + } + } + + *ti = n; + return (n) ? ZIX_STATUS_SUCCESS : ZIX_STATUS_NOT_FOUND; +} + +ZIX_API +const void* +zix_tree_get_data(ZixTreeIter ti) +{ + return ti->data; +} diff --git a/test/tree_bench.c b/test/tree_bench.c new file mode 100644 index 0000000..48d5935 --- /dev/null +++ b/test/tree_bench.c @@ -0,0 +1,205 @@ +/* + Copyright 2011 David Robillard <http://drobilla.net> + + 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. + + THIS 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. +*/ + +#define _POSIX_C_SOURCE 199309L + +#include <time.h> +#include <sys/time.h> + +#include <inttypes.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <limits.h> + +#include <glib.h> + +#include "zix/zix.h" + +const unsigned seed = 1; + +static int +int_cmp(const void* a, const void* b, void* user_data) +{ + const intptr_t ia = (intptr_t)a; + const intptr_t ib = (intptr_t)b; + return ia - ib; +} + +static int +test_fail() +{ + fprintf(stderr, "ERROR\n"); + return EXIT_FAILURE; +} + +static inline double +elapsed_s(const struct timespec* start, const struct timespec* end) +{ + return ( (end->tv_sec - start->tv_sec) + + ((end->tv_nsec - start->tv_nsec) * 0.000000001) ); +} + +static inline struct timespec +bench_start() +{ + struct timespec start_t; + clock_gettime(CLOCK_REALTIME, &start_t); + return start_t; +} + +static inline double +bench_end(const struct timespec* start_t) +{ + struct timespec end_t; + clock_gettime(CLOCK_REALTIME, &end_t); + return elapsed_s(start_t, &end_t); +} + +static int +bench_zix(size_t n_elems, FILE* insert_dat, FILE* search_dat) +{ + intptr_t r; + ZixTreeIter ti; + + ZixTree* t = zix_tree_new(true, int_cmp, NULL); + + srand(seed); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + int status = zix_tree_insert(t, (void*)r, &ti); + if (status && status != ZIX_STATUS_EXISTS) { + return test_fail(); + } + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + srand(seed); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + if (zix_tree_find(t, (void*)r, &ti)) { + return test_fail(); + } + if ((intptr_t)zix_tree_get_data(ti) != r) { + return test_fail(); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + + srand(seed); + + // Delete all elements + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + ZixTreeIter item; + if (zix_tree_find(t, (void*)r, &item)) { + return test_fail(); + } + if (zix_tree_remove(t, item)) { + return test_fail(); + } + } + + zix_tree_free(t); + + return EXIT_SUCCESS; +} + +static int +bench_glib(size_t n_elems, FILE* insert_dat, FILE* search_dat) +{ + intptr_t r; + GSequence* t = g_sequence_new(NULL); + + srand(seed); + + // Insert n_elems elements + struct timespec insert_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + g_sequence_insert_sorted(t, (void*)r, int_cmp, NULL); + } + fprintf(insert_dat, "\t%lf", bench_end(&insert_start)); + + srand(seed); + + // Search for all elements + struct timespec search_start = bench_start(); + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + if (!g_sequence_search(t, (void*)r, int_cmp, NULL)) { + return test_fail(); + } + } + fprintf(search_dat, "\t%lf", bench_end(&search_start)); + +#if 0 + srand(seed); + + // Delete all elements + for (size_t i = 0; i < n_elems; i++) { + r = rand(); + GSequenceIter item; + if (g_sequence_find(t, (void*)r, &item)) { + return test_fail(); + } + if (g_sequence_remove(t, item)) { + return test_fail(); + } + } +#endif + + g_sequence_free(t); + + return EXIT_SUCCESS; +} + +int +main(int argc, char** argv) +{ + if (argc != 3) { + fprintf(stderr, "USAGE: %s MIN_N MAX_N\n", argv[0]); + return 1; + } + + const size_t min_n = atol(argv[1]); + const size_t max_n = atol(argv[2]); + + fprintf(stderr, "Benchmarking %zu .. %zu elements\n", min_n, max_n); + + FILE* insert_dat = fopen("insert.dat", "w"); + FILE* search_dat = fopen("search.dat", "w"); + fprintf(insert_dat, "# n\tZixTree\tGSequence\n"); + fprintf(search_dat, "# n\tZixTree\tGSequence\n"); + for (size_t n = min_n; n <= max_n; n *= 2) { + fprintf(insert_dat, "%zu", n); + fprintf(search_dat, "%zu", n); + bench_zix(n, insert_dat, search_dat); + bench_glib(n, insert_dat, search_dat); + fprintf(insert_dat, "\n"); + fprintf(search_dat, "\n"); + } + fclose(insert_dat); + fclose(search_dat); + + return EXIT_SUCCESS; +} diff --git a/test/tree_test.c b/test/tree_test.c new file mode 100644 index 0000000..d4fb283 --- /dev/null +++ b/test/tree_test.c @@ -0,0 +1,158 @@ +/* + Copyright 2011 David Robillard <http://drobilla.net> + + 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. + + THIS 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 <inttypes.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <limits.h> + +#include <sys/time.h> + +#include "zix/zix.h" + +unsigned seed = 1; + +static int +int_cmp(const void* a, const void* b, void* user_data) +{ + const intptr_t ia = (intptr_t)a; + const intptr_t ib = (intptr_t)b; + return ia - ib; +} + +static int +ith_elem(int test_num, size_t n_elems, int i) +{ + switch (test_num % 3) { + case 0: + return i; // Increasing (worst case) + case 1: + return n_elems - i; // Decreasing (worse case) + case 2: + default: + return rand() % 100; // Random + } +} + +static int +test_fail() +{ + return EXIT_FAILURE; +} + +static int +stress(int test_num, size_t n_elems) +{ + intptr_t r; + ZixTreeIter ti; + + ZixTree* t = zix_tree_new(true, int_cmp, NULL); + + srand(seed); + + // Insert n_elems elements + for (size_t i = 0; i < n_elems; i++) { + r = ith_elem(test_num, n_elems, i); + int status = zix_tree_insert(t, (void*)r, &ti); + if (status == ZIX_STATUS_EXISTS) { + continue; + } else if (status != ZIX_STATUS_SUCCESS) { + fprintf(stderr, "Insert failed\n"); + return test_fail(); + } + if ((intptr_t)zix_tree_get_data(ti) != r) { + fprintf(stderr, "Data is corrupted! Saw %" PRIdPTR ", expected %zu\n", + (intptr_t)zix_tree_get_data(ti), i); + return test_fail(); + } + } + + srand(seed); + + // Search for all elements + for (size_t i = 0; i < n_elems; i++) { + r = ith_elem(test_num, n_elems, i); + if (zix_tree_find(t, (void*)r, &ti)) { + fprintf(stderr, "Find failed\n"); + return test_fail(); + } + if ((intptr_t)zix_tree_get_data(ti) != r) { + fprintf(stderr, "Data corrupted (saw %" PRIdPTR ", expected %zu\n", + (intptr_t)zix_tree_get_data(ti), i); + return test_fail(); + } + } + + srand(seed); + + // Delete all elements + for (size_t i = 0; i < n_elems; i++) { + r = ith_elem(test_num, n_elems, i); + ZixTreeIter item; + if (zix_tree_find(t, (void*)r, &item) != ZIX_STATUS_SUCCESS) { + fprintf(stderr, "Failed to find item to remove\n"); + return test_fail(); + } + if (zix_tree_remove(t, item)) { + fprintf(stderr, "Error removing item\n"); + } + } + + zix_tree_free(t); + + return EXIT_SUCCESS; +} + +int +main(int argc, char** argv) +{ + const size_t n_tests = 3; + size_t n_elems = 0; + + struct timeval time; + gettimeofday(&time, NULL); + + if (argc == 1) { + n_elems = 4096; + } else { + n_elems = atol(argv[1]); + if (argc > 2) { + seed = atol(argv[2]); + } else { + seed = time.tv_sec + time.tv_usec; + } + } + + if (n_elems == 0) { + fprintf(stderr, "USAGE: %s [N_ELEMS]\n", argv[0]); + return 1; + } + + printf("Running %zu tests with %zu elements (seed %d)", + n_tests, n_elems, seed); + + for (size_t i = 0; i < n_tests; ++i) { + printf("."); + fflush(stdout); + if (stress(i, n_elems)) { + fprintf(stderr, "FAIL: Random seed %u\n", seed); + return test_fail(); + } + } + printf("\n"); + return EXIT_SUCCESS; +} Binary files differ@@ -0,0 +1,143 @@ +#!/usr/bin/env python +import filecmp +import glob +import os +import shutil +import subprocess + +from waflib.extras import autowaf as autowaf +import waflib.Logs as Logs, waflib.Options as Options + +# Version of this package (even if built as a child) +ZIX_VERSION = '0.0.2' + +# Library version (UNIX style major, minor, micro) +# major increment <=> incompatible changes +# minor increment <=> compatible changes (additions) +# micro increment <=> no interface changes +# Zix uses the same version number for both library and package +ZIX_LIB_VERSION = ZIX_VERSION + +# Variables for 'waf dist' +APPNAME = 'zix' +VERSION = ZIX_VERSION + +# Mandatory variables +top = '.' +out = 'build' + +def options(opt): + autowaf.set_options(opt) + opt.load('compiler_c') + opt.add_option('--test', action='store_true', default=False, dest='build_tests', + help="Build unit tests") + opt.add_option('--bench', action='store_true', default=False, dest='build_bench', + help="Build benchmarks") + +def configure(conf): + conf.line_just = max(conf.line_just, 59) + autowaf.configure(conf) + autowaf.display_header('Zix Configuration') + + conf.load('compiler_c') + conf.env.append_value('CFLAGS', '-std=c99') + + autowaf.check_pkg(conf, 'glib-2.0', uselib_store='GLIB', + atleast_version='2.0.0', mandatory=False) + + conf.env['BUILD_TESTS'] = Options.options.build_tests + if conf.is_defined('HAVE_GLIB'): + conf.env['BUILD_BENCH'] = Options.options.build_bench + + autowaf.define(conf, 'ZIX_VERSION', ZIX_VERSION) + conf.write_config_header('zix-config.h', remove=False) + + autowaf.display_msg(conf, "Unit tests", str(conf.env['BUILD_TESTS'])) + autowaf.display_msg(conf, "Benchmarks", str(conf.env['BUILD_BENCHx'])) + print('') + +def build(bld): + # C Headers + bld.install_files('${INCLUDEDIR}/zix', bld.path.ant_glob('zix/*.h')) + + # Pkgconfig file + autowaf.build_pc(bld, 'ZIX', ZIX_VERSION, []) + + lib_source = ''' + src/tree.c + src/strindex.c + ''' + + # Library + obj = bld(features = 'c cshlib') + obj.export_includes = ['.'] + obj.source = lib_source + obj.includes = ['.', './src'] + obj.name = 'libzix' + obj.target = 'zix' + obj.vnum = ZIX_LIB_VERSION + obj.install_path = '${LIBDIR}' + obj.cflags = [ '-fvisibility=hidden', '-DZIX_SHARED', '-DZIX_INTERNAL' ] + + if bld.env['BUILD_TESTS']: + # Static library (for unit test code coverage) + obj = bld(features = 'c cstlib') + obj.source = lib_source + obj.includes = ['.', './src'] + obj.name = 'libzix_static' + obj.target = 'zix_static' + obj.install_path = '' + obj.cflags = [ '-fprofile-arcs', '-ftest-coverage' ] + + # Unit test programs + for i in ['tree_test']: + obj = bld(features = 'c cprogram') + obj.source = 'test/%s.c' % i + obj.includes = ['.'] + obj.use = 'libzix_static' + obj.linkflags = '-lgcov' + obj.target = 'test/%s' % i + obj.install_path = '' + obj.cflags = [ '-fprofile-arcs', '-ftest-coverage' ] + + if bld.env['BUILD_BENCH']: + # Benchmark programs + for i in ['tree_bench']: + obj = bld(features = 'c cprogram') + obj.source = 'test/%s.c' % i + obj.includes = ['.'] + obj.use = 'libzix' + obj.uselib = 'GLIB' + obj.linkflags = '-lrt' + obj.target = 'test/%s' % i + obj.install_path = '' + + # Documentation + #autowaf.build_dox(bld, 'ZIX', ZIX_VERSION, top, out) + + # Man page + #bld.install_files('${MANDIR}/man1', 'doc/zixi.1') + + bld.add_post_fun(autowaf.run_ldconfig) + +def lint(ctx): + subprocess.call('cpplint.py --filter=-whitespace/tab,-whitespace/braces,-build/header_guard,-readability/casting,-readability/todo src/* zix/*', shell=True) + +def fix_docs(ctx): + try: + os.chdir('build/doc/html') + os.system("sed -i 's/ZIX_API //' group__zix.html") + os.system("sed -i 's/ZIX_DEPRECATED //' group__zix.html") + os.remove('index.html') + os.symlink('group__zix.html', + 'index.html') + except Exception as e: + Logs.error("Failed to fix up Doxygen documentation (%s)\n" % e) + +def upload_docs(ctx): + os.system("rsync -avz --delete -e ssh build/doc/html/* drobilla@drobilla.net:~/drobilla.net/docs/zix") + +def test(ctx): + autowaf.pre_test(ctx, APPNAME) + autowaf.run_tests(ctx, APPNAME, ['test/tree_test'], dirs=['./src','./test']) + autowaf.post_test(ctx, APPNAME) diff --git a/zix.pc.in b/zix.pc.in new file mode 100644 index 0000000..65f3905 --- /dev/null +++ b/zix.pc.in @@ -0,0 +1,10 @@ +prefix=@prefix@ +exec_prefix=@exec_prefix@ +libdir=@libdir@ +includedir=@includedir@ + +Name: libzix +Version: @ZIX_VERSION@ +Description: Lightweight portability library +Libs: -L${libdir} -lzix +Cflags: -I${includedir} diff --git a/zix/zix.h b/zix/zix.h new file mode 100644 index 0000000..a264b43 --- /dev/null +++ b/zix/zix.h @@ -0,0 +1,122 @@ +/* + Copyright 2011 David Robillard <http://drobilla.net> + + 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. + + THIS 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 ZIX_ZIX_H +#define ZIX_ZIX_H + +#include <stdbool.h> + +#ifdef ZIX_SHARED +# ifdef __WIN32__ +# define ZIX_LIB_IMPORT __declspec(dllimport) +# define ZIX_LIB_EXPORT __declspec(dllexport) +# else +# define ZIX_LIB_IMPORT __attribute__((visibility("default"))) +# define ZIX_LIB_EXPORT __attribute__((visibility("default"))) +# endif +# ifdef ZIX_INTERNAL +# define ZIX_API ZIX_LIB_EXPORT +# else +# define ZIX_API ZIX_LIB_IMPORT +# endif +#else +# define ZIX_API +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +/** + @defgroup zix Zix + A lightweight portability library. + @{ +*/ + +/** + @name Tree + @{ +*/ + +#define ZIX_STATUS_SUCCESS 0 +#define ZIX_STATUS_ERROR 1 +#define ZIX_STATUS_NO_MEM 2 +#define ZIX_STATUS_NOT_FOUND 3 +#define ZIX_STATUS_EXISTS 4 + +/** + Function for comparing two elements. +*/ +typedef int (*ZixComparator)(const void* a, const void* b, void* user_data); + +/** + A balanced binary search tree. +*/ +typedef struct _ZixTree ZixTree; + +/** + A node in a @ref ZixTree. +*/ +typedef struct _ZixTreeNode ZixTreeNode; + +/** + An iterator over a @ref ZixTree. +*/ +typedef ZixTreeNode* ZixTreeIter; + +/** + Create a new (empty) tree. +*/ +ZixTree* +zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data); + +/** + Free @a t. +*/ +void +zix_tree_free(ZixTree* t); + +/** + Insert the element @a e into @a t and point @a ti at the new element. +*/ +int +zix_tree_insert(ZixTree* t, const void* e, ZixTreeIter* ti); + +/** + Remove the item pointed at by @a ti from @a t. +*/ +int +zix_tree_remove(ZixTree* t, ZixTreeIter ti); + +/** + Set @a ti to be the largest element <= @a e in @a t. + If no such item exists, @a ti is set to NULL. +*/ +int +zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter* ti); + +/** + Return the data associated with the given avltree item. +*/ +const void* +zix_tree_get_data(ZixTreeIter ti); + +/** + @} + @} +*/ + +#endif /* ZIX_ZIX_H */ |