diff options
author | David Robillard <d@drobilla.net> | 2011-09-28 21:31:44 +0000 |
---|---|---|
committer | David Robillard <d@drobilla.net> | 2011-09-28 21:31:44 +0000 |
commit | db7df61c02f28a86ebf496436d34a2d327c3ae30 (patch) | |
tree | 961b0f00f87155c03e50ff78ccc6518676fabaed /src/zix | |
parent | 84ad1bf1317992127aac405feedbfd68c7be6697 (diff) | |
download | sord-db7df61c02f28a86ebf496436d34a2d327c3ae30.tar.gz sord-db7df61c02f28a86ebf496436d34a2d327c3ae30.tar.bz2 sord-db7df61c02f28a86ebf496436d34a2d327c3ae30.zip |
Remove glib dependency
git-svn-id: http://svn.drobilla.net/sord/trunk@163 3d64ff67-21c5-427c-a301-fe4f08042e5a
Diffstat (limited to 'src/zix')
-rw-r--r-- | src/zix/common.h | 67 | ||||
-rw-r--r-- | src/zix/hash.c | 226 | ||||
-rw-r--r-- | src/zix/hash.h | 75 | ||||
-rw-r--r-- | src/zix/tree.c | 590 | ||||
-rw-r--r-- | src/zix/tree.h | 121 |
5 files changed, 1079 insertions, 0 deletions
diff --git a/src/zix/common.h b/src/zix/common.h new file mode 100644 index 0000000..a7edf76 --- /dev/null +++ b/src/zix/common.h @@ -0,0 +1,67 @@ +/* + 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_COMMON_H +#define ZIX_COMMON_H + +#include <stdbool.h> + +/** + @addtogroup zix + @{ +*/ + +/** @cond */ +#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 +/** @endcond */ + +typedef enum { + ZIX_STATUS_SUCCESS, + ZIX_STATUS_ERROR, + ZIX_STATUS_NO_MEM, + ZIX_STATUS_NOT_FOUND, + ZIX_STATUS_EXISTS, +} ZixStatus; + +/** + Function for comparing two elements. +*/ +typedef int (*ZixComparator)(const void* a, const void* b, void* user_data); + +/** + Function for testing equality of two elements. +*/ +typedef bool (*ZixEqualFunc)(const void* a, const void* b); + +/**@} +*/ + +#endif /* ZIX_COMMON_H */ diff --git a/src/zix/hash.c b/src/zix/hash.c new file mode 100644 index 0000000..c267757 --- /dev/null +++ b/src/zix/hash.c @@ -0,0 +1,226 @@ +/* + 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 <stdlib.h> +#include <string.h> + +#include "zix/hash.h" + +/** + Primes, each slightly less than twice its predecessor, and as far away + from powers of two as possible. +*/ +static const unsigned sizes[] = { + 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, + 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, + 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 0 +}; + +typedef struct _Entry { + const void* key; ///< Hash key + void* data; ///< Value + struct _Entry* next; ///< Next entry in bucket + unsigned hash; ///< Non-modulo hash value (for cheap rehash) +} Entry; + +struct ZixHashImpl { + ZixHashFunc hash_func; + ZixEqualFunc key_equal_func; + Entry** buckets; + const unsigned* n_buckets; + unsigned count; +}; + +ZixHash* +zix_hash_new(ZixHashFunc hash_func, + ZixEqualFunc key_equal_func) + +{ + ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash)); + hash->hash_func = hash_func; + hash->key_equal_func = key_equal_func; + hash->count = 0; + hash->n_buckets = &sizes[0]; + hash->buckets = malloc(*hash->n_buckets * sizeof(Entry*)); + memset(hash->buckets, 0, *hash->n_buckets * sizeof(Entry*)); + + return hash; +} + +void +zix_hash_free(ZixHash* hash) +{ + for (unsigned b = 0; b < *hash->n_buckets; ++b) { + Entry* bucket = hash->buckets[b]; + for (Entry* e = bucket; e;) { + Entry* next = e->next; + free(e); + e = next; + } + } + + free(hash->buckets); + free(hash); +} + +unsigned +zix_string_hash(const void* key) +{ + // Trusty old DJB hash + const char* str = (const char*)key; + unsigned h = 5381; + for (const char* s = str; *s != '\0'; ++s) { + h = (h << 5) + h + *s; // h = h * 33 + c + } + return h; +} + +bool +zix_string_equal(const void* a, const void* b) +{ + return !strcmp((const char*)a, (const char*)b); +} + +static void +insert_entry(Entry** bucket, + Entry* entry) +{ + entry->next = *bucket; + *bucket = entry; +} + +static ZixStatus +rehash(ZixHash* hash, unsigned new_n_buckets) +{ + Entry** new_buckets = (Entry**)malloc(new_n_buckets * sizeof(Entry*)); + if (!new_buckets) { + return ZIX_STATUS_NO_MEM; + } + + memset(new_buckets, 0, new_n_buckets * sizeof(Entry*)); + + for (unsigned b = 0; b < *hash->n_buckets; ++b) { + for (Entry* e = hash->buckets[b]; e;) { + Entry* const next = e->next; + const unsigned h = e->hash % new_n_buckets; + insert_entry(&new_buckets[h], e); + e = next; + } + } + + free(hash->buckets); + hash->buckets = new_buckets; + + return ZIX_STATUS_SUCCESS; +} + +static Entry* +find_entry(const ZixHash* hash, + const void* key, + unsigned h) +{ + for (Entry* e = hash->buckets[h]; e; e = e->next) { + if (hash->key_equal_func(e->key, key)) { + return e; + } + } + + return NULL; +} + +void* +zix_hash_find(const ZixHash* hash, const void* key) +{ + const unsigned h = hash->hash_func(key) % *hash->n_buckets; + Entry* const entry = find_entry(hash, key, h); + return entry ? entry->data : 0; +} + +ZixStatus +zix_hash_insert(ZixHash* hash, const void* key, void* data) +{ + unsigned h_nomod = hash->hash_func(key); + unsigned h = h_nomod % *hash->n_buckets; + + Entry* elem = find_entry(hash, key, h); + if (elem) { + assert(elem->hash == h_nomod); + return ZIX_STATUS_EXISTS; + } + + elem = (Entry*)malloc(sizeof(Entry)); + if (!elem) { + return ZIX_STATUS_NO_MEM; + } + elem->key = key; + elem->data = data; + elem->next = NULL; + elem->hash = h_nomod; + const unsigned next_n_buckets = *(hash->n_buckets + 1); + if (next_n_buckets != 0 && (hash->count + 1) >= next_n_buckets) { + if (!rehash(hash, next_n_buckets)) { + h = h_nomod % *(++hash->n_buckets); + } + } + + insert_entry(&hash->buckets[h], elem); + ++hash->count; + return ZIX_STATUS_SUCCESS; +} + +ZixStatus +zix_hash_remove(ZixHash* hash, const void* key) +{ + unsigned h = hash->hash_func(key) % *hash->n_buckets; + + Entry** next_ptr = &hash->buckets[h]; + for (Entry* e = hash->buckets[h]; e; e = e->next) { + if (hash->key_equal_func(e->key, key)) { + *next_ptr = e->next; + free(e); + return ZIX_STATUS_SUCCESS; + } + next_ptr = &e->next; + } + + if (hash->n_buckets != sizes) { + const unsigned prev_n_buckets = *(hash->n_buckets - 1); + if (hash->count - 1 <= prev_n_buckets) { + if (!rehash(hash, prev_n_buckets)) { + --hash->n_buckets; + } + } + } + + --hash->count; + return ZIX_STATUS_NOT_FOUND; +} + +ZIX_API +void +zix_hash_foreach(const ZixHash* hash, + void (*f)(const void* key, void* value, void* user_data), + void* user_data) +{ + for (unsigned b = 0; b < *hash->n_buckets; ++b) { + Entry* bucket = hash->buckets[b]; + for (Entry* e = bucket; e; e = e->next) { + f(e->key, e->data, user_data); + } + } +} + diff --git a/src/zix/hash.h b/src/zix/hash.h new file mode 100644 index 0000000..44521f1 --- /dev/null +++ b/src/zix/hash.h @@ -0,0 +1,75 @@ +/* + 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_HASH_H +#define ZIX_HASH_H + +#include "zix/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct ZixHashImpl ZixHash; + +/** + Function for computing the hash of an element. +*/ +typedef unsigned (*ZixHashFunc)(const void* key); + +ZIX_API +ZixHash* +zix_hash_new(ZixHashFunc hash_func, + ZixEqualFunc key_equal_func); + +ZIX_API +void +zix_hash_free(ZixHash* hash); + +ZIX_API +unsigned +zix_string_hash(const void* key); + +ZIX_API +bool +zix_string_equal(const void* a, const void* b); + +ZIX_API +ZixStatus +zix_hash_insert(ZixHash* hash, + const void* key, + void* data); + +ZIX_API +ZixStatus +zix_hash_remove(ZixHash* hash, const void* key); + +ZIX_API +void* +zix_hash_find(const ZixHash* hash, + const void* key); + +ZIX_API +void +zix_hash_foreach(const ZixHash* hash, + void (*f)(const void* key, void* value, void* user_data), + void* user_data); + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ZIX_HASH_H */ diff --git a/src/zix/tree.c b/src/zix/tree.c new file mode 100644 index 0000000..30ac3e2 --- /dev/null +++ b/src/zix/tree.c @@ -0,0 +1,590 @@ +/* + 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/common.h" +#include "zix/tree.h" + +typedef struct ZixTreeNodeImpl ZixTreeNode; + +struct ZixTreeImpl { + ZixTreeNode* root; + ZixComparator cmp; + void* cmp_data; + bool allow_duplicates; +}; + +struct ZixTreeNodeImpl { + void* data; + struct ZixTreeNodeImpl* left; + struct ZixTreeNodeImpl* right; + struct ZixTreeNodeImpl* parent; + int_fast8_t balance; +}; + +#define MIN(a, b) (((a) < (b)) ? (a) : (b)) +#define MAX(a, b) (((a) > (b)) ? (a) : (b)) + +ZIX_API +ZixTree* +zix_tree_new(bool allow_duplicates, ZixComparator cmp, void* cmp_data) +{ + ZixTree* t = malloc(sizeof(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); +} + +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; + + assert(p->balance == 2); + assert(q->balance == 0 || q->balance == 1); + + rotate(p, q); + + --q->balance; + p->balance = -(q->balance); + + 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; + + assert(p->balance == -2); + assert(q->balance == 0 || q->balance == -1); + + rotate(p, q); + + ++q->balance; + p->balance = -(q->balance); + + 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); + + 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 = 0; + + *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); + + 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 = 0; + + *height_change = -1; + + return r; +} + +static ZixTreeNode* +zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) +{ + *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; + } + + return replacement; +} + +ZIX_API +ZixStatus +zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) +{ + 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 { + if (ti) { + *ti = n; + } + 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; + if (ti) { + *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; + } + } + + // 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; + } + } + } + + return ZIX_STATUS_SUCCESS; +} + +ZIX_API +ZixStatus +zix_tree_remove(ZixTree* t, ZixTreeIter* ti) +{ + ZixTreeNode* const n = ti; + ZixTreeNode** pp = NULL; // parent pointer + ZixTreeNode* to_balance = n->parent; // lowest node to balance + int8_t d_balance = 0; // delta(balance) for n->parent + + if ((n == t->root) && !n->left && !n->right) { + t->root = NULL; + free(n); + 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; + } + } + } + + free(n); + + return ZIX_STATUS_SUCCESS; +} + +ZIX_API +ZixStatus +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 +void* +zix_tree_get(ZixTreeIter* ti) +{ + return ti->data; +} + +ZIX_API +ZixTreeIter* +zix_tree_begin(ZixTree* t) +{ + if (!t->root) { + return NULL; + } + + ZixTreeNode* n = t->root; + while (n->left) { + n = n->left; + } + return n; +} + +ZIX_API +ZixTreeIter* +zix_tree_end(ZixTree* t) +{ + return NULL; +} + +ZIX_API +bool +zix_tree_iter_is_end(ZixTreeIter* i) +{ + return !i; +} + +ZIX_API +ZixTreeIter* +zix_tree_iter_next(ZixTreeIter* i) +{ + if (!i) { + return NULL; + } + + if (i->right) { + i = i->right; + while (i->left) { + i = i->left; + } + } else { + while (i->parent && i->parent->right == i) { // i is a right child + i = i->parent; + } + + i = i->parent; + } + + return i; +} + +ZIX_API +ZixTreeIter* +zix_tree_iter_prev(ZixTreeIter* i) +{ + if (!i) { + return NULL; + } + + if (i->left) { + i = i->left; + while (i->right) { + i = i->right; + } + } else { + while (i->parent && i->parent->left == i) { // i is a left child + i = i->parent; + } + + i = i->parent; + } + + return i; +} diff --git a/src/zix/tree.h b/src/zix/tree.h new file mode 100644 index 0000000..670c437 --- /dev/null +++ b/src/zix/tree.h @@ -0,0 +1,121 @@ +/* + 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_TREE_H +#define ZIX_TREE_H + +#include <stdbool.h> + +#include "zix/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + @addtogroup zix + @{ + @name Tree + @{ +*/ + +/** + A balanced binary search tree. +*/ +typedef struct ZixTreeImpl ZixTree; + +/** + An iterator over a @ref ZixTree. +*/ +typedef struct ZixTreeNodeImpl 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. +*/ +ZixStatus +zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti); + +/** + Remove the item pointed at by @a ti from @a t. +*/ +ZixStatus +zix_tree_remove(ZixTree* t, ZixTreeIter* ti); + +/** + Set @a ti to an element equal to @a e in @a t. + If no such item exists, @a ti is set to NULL. +*/ +ZixStatus +zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti); + +/** + Return the data associated with the given tree item. +*/ +void* +zix_tree_get(ZixTreeIter* ti); + +/** + Return an iterator to the first (smallest) element in @a t. +*/ +ZixTreeIter* +zix_tree_begin(ZixTree* t); + +/** + Return an iterator the the element one past the last element in @a t. +*/ +ZixTreeIter* +zix_tree_end(ZixTree* t); + +/** + Return true iff @a i is an iterator to the end of its tree. +*/ +bool +zix_tree_iter_is_end(ZixTreeIter* i); + +/** + Return an iterator that points to the element one past @a i. +*/ +ZixTreeIter* +zix_tree_iter_next(ZixTreeIter* i); + +/** + Return an iterator that points to the element one before @a i. +*/ +ZixTreeIter* +zix_tree_iter_prev(ZixTreeIter* i); + +/** + @} + @} +*/ + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ZIX_TREE_H */ |