diff options
| -rw-r--r-- | NEWS | 6 | ||||
| -rw-r--r-- | src/sord.c | 120 | ||||
| -rw-r--r-- | src/sord_test.c | 2 | ||||
| -rw-r--r-- | src/sord_validate.c | 4 | ||||
| -rw-r--r-- | src/zix/btree.c | 702 | ||||
| -rw-r--r-- | src/zix/btree.h | 144 | ||||
| -rw-r--r-- | src/zix/hash.c | 22 | ||||
| -rw-r--r-- | src/zix/tree.c | 716 | ||||
| -rw-r--r-- | src/zix/tree.h | 148 | ||||
| -rw-r--r-- | wscript | 2 |
10 files changed, 911 insertions, 955 deletions
@@ -1,3 +1,9 @@ +sord (0.12.3) unstable; + + * Reduce memory usage and increase performance with a better data structure + + -- David Robillard <d@drobilla.net> Tue, 23 Sep 2014 00:27:22 -0400 + sord (0.12.2) stable; * Fix iteration over an entire graph (* * * graph) @@ -25,7 +25,7 @@ #define ZIX_INLINE #include "zix/digest.c" #include "zix/hash.c" -#include "zix/tree.c" +#include "zix/btree.c" #include "sord_config.h" #include "sord_internal.h" @@ -116,7 +116,7 @@ struct SordModelImpl { /** Index for each possible triple ordering (may or may not exist). * Each index is a tree of SordQuad with the appropriate ordering. */ - ZixTree* indices[NUM_ORDERS]; + ZixBTree* indices[NUM_ORDERS]; size_t n_quads; }; @@ -133,7 +133,7 @@ typedef enum { /** Iterator over some range of a store */ struct SordIterImpl { const SordModel* sord; ///< Model being iterated over - ZixTreeIter* cur; ///< Current DB cursor + ZixBTreeIter* cur; ///< Current DB cursor SordQuad pat; ///< Pattern (in ordering order) int ordering[TUP_LEN]; ///< Store ordering SearchMode mode; ///< Iteration mode @@ -316,18 +316,18 @@ static inline bool sord_iter_forward(SordIter* iter) { if (!iter->skip_graphs) { - iter->cur = zix_tree_iter_next(iter->cur); - return zix_tree_iter_is_end(iter->cur); + zix_btree_iter_increment(iter->cur); + return zix_btree_iter_is_end(iter->cur); } - SordNode** key = (SordNode**)zix_tree_get(iter->cur); + SordNode** key = (SordNode**)zix_btree_get(iter->cur); const SordQuad initial = { key[0], key[1], key[2], key[3] }; while (true) { - iter->cur = zix_tree_iter_next(iter->cur); - if (zix_tree_iter_is_end(iter->cur)) + zix_btree_iter_increment(iter->cur); + if (zix_btree_iter_is_end(iter->cur)) return true; - key = (SordNode**)zix_tree_get(iter->cur); + key = (SordNode**)zix_btree_get(iter->cur); for (int i = 0; i < 3; ++i) if (key[i] != initial[i]) return false; @@ -343,9 +343,9 @@ static inline bool sord_iter_seek_match(SordIter* iter) { for (iter->end = true; - !zix_tree_iter_is_end(iter->cur); + !zix_btree_iter_is_end(iter->cur); sord_iter_forward(iter)) { - const SordNode** const key = (const SordNode**)zix_tree_get(iter->cur); + const SordNode** const key = (const SordNode**)zix_btree_get(iter->cur); if (sord_quad_match_inline(key, iter->pat)) return (iter->end = false); } @@ -364,7 +364,7 @@ sord_iter_seek_match_range(SordIter* iter) return true; do { - const SordNode** key = (const SordNode**)zix_tree_get(iter->cur); + const SordNode** key = (const SordNode**)zix_btree_get(iter->cur); if (sord_quad_match_inline(key, iter->pat)) return false; // Found match @@ -382,7 +382,7 @@ sord_iter_seek_match_range(SordIter* iter) } static SordIter* -sord_iter_new(const SordModel* sord, ZixTreeIter* cur, const SordQuad pat, +sord_iter_new(const SordModel* sord, ZixBTreeIter* cur, const SordQuad pat, SordOrder order, SearchMode mode, int n_prefix) { const int* ordering = orderings[order]; @@ -404,7 +404,7 @@ sord_iter_new(const SordModel* sord, ZixTreeIter* cur, const SordQuad pat, case SINGLE: case RANGE: assert( - sord_quad_match_inline((const SordNode**)zix_tree_get(iter->cur), + sord_quad_match_inline((const SordNode**)zix_btree_get(iter->cur), iter->pat)); break; case FILTER_RANGE: @@ -434,7 +434,7 @@ sord_iter_get_model(SordIter* iter) void sord_iter_get(const SordIter* iter, SordQuad id) { - SordNode** key = (SordNode**)zix_tree_get(iter->cur); + SordNode** key = (SordNode**)zix_btree_get(iter->cur); for (int i = 0; i < TUP_LEN; ++i) { id[i] = key[i]; } @@ -443,7 +443,7 @@ sord_iter_get(const SordIter* iter, SordQuad id) const SordNode* sord_iter_get_node(const SordIter* iter, SordQuadIndex index) { - return iter ? ((SordNode**)zix_tree_get(iter->cur))[index] : NULL; + return iter ? ((SordNode**)zix_btree_get(iter->cur))[index] : NULL; } bool @@ -466,7 +466,7 @@ sord_iter_next(SordIter* iter) case RANGE: SORD_ITER_LOG("%p range next\n", (void*)iter); // At the end if the MSNs no longer match - key = (const SordNode**)zix_tree_get(iter->cur); + key = (const SordNode**)zix_btree_get(iter->cur); assert(key); for (int i = 0; i < iter->n_prefix; ++i) { const int idx = iter->ordering[i]; @@ -515,6 +515,7 @@ sord_iter_free(SordIter* iter) { SORD_ITER_LOG("%p Free\n", (void*)iter); if (iter) { + zix_btree_iter_free(iter->cur); free(iter); } } @@ -637,11 +638,11 @@ sord_new(SordWorld* world, unsigned indices, bool graphs) const int* const g_ordering = orderings[i + (NUM_ORDERS / 2)]; if (indices & (1 << i)) { - sord->indices[i] = zix_tree_new( - false, sord_quad_compare, (void*)ordering, NULL); + sord->indices[i] = zix_btree_new( + sord_quad_compare, (void*)ordering, NULL); if (graphs) { - sord->indices[i + (NUM_ORDERS / 2)] = zix_tree_new( - false, sord_quad_compare, (void*)g_ordering, NULL); + sord->indices[i + (NUM_ORDERS / 2)] = zix_btree_new( + sord_quad_compare, (void*)g_ordering, NULL); } else { sord->indices[i + (NUM_ORDERS / 2)] = NULL; } @@ -652,12 +653,12 @@ sord_new(SordWorld* world, unsigned indices, bool graphs) } if (!sord->indices[DEFAULT_ORDER]) { - sord->indices[DEFAULT_ORDER] = zix_tree_new( - false, sord_quad_compare, (void*)orderings[DEFAULT_ORDER], NULL); + sord->indices[DEFAULT_ORDER] = zix_btree_new( + sord_quad_compare, (void*)orderings[DEFAULT_ORDER], NULL); } if (graphs && !sord->indices[DEFAULT_GRAPH_ORDER]) { - sord->indices[DEFAULT_GRAPH_ORDER] = zix_tree_new( - false, sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER], NULL); + sord->indices[DEFAULT_GRAPH_ORDER] = zix_btree_new( + sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER], NULL); } return sord; @@ -727,16 +728,16 @@ sord_free(SordModel* sord) sord_iter_free(i); // Free quads - for (ZixTreeIter* t = zix_tree_begin(sord->indices[DEFAULT_ORDER]); - !zix_tree_iter_is_end(t); - t = zix_tree_iter_next(t)) { - free(zix_tree_get(t)); + ZixBTreeIter* t = zix_btree_begin(sord->indices[DEFAULT_ORDER]); + for (; !zix_btree_iter_is_end(t); zix_btree_iter_increment(t)) { + free(zix_btree_get(t)); } + zix_btree_iter_free(t); // Free indices for (unsigned o = 0; o < NUM_ORDERS; ++o) if (sord->indices[o]) - zix_tree_free(sord->indices[o]); + zix_btree_free(sord->indices[o]); free(sord); } @@ -765,46 +766,12 @@ sord_begin(const SordModel* sord) if (sord_num_quads(sord) == 0) { return NULL; } else { - ZixTreeIter* cur = zix_tree_begin(sord->indices[DEFAULT_ORDER]); + ZixBTreeIter* cur = zix_btree_begin(sord->indices[DEFAULT_ORDER]); SordQuad pat = { 0, 0, 0, 0 }; return sord_iter_new(sord, cur, pat, DEFAULT_ORDER, ALL, 0); } } -static inline ZixTreeIter* -index_search(ZixTree* db, const SordQuad search_key) -{ - ZixTreeIter* iter = NULL; - zix_tree_find(db, (const void*)search_key, &iter); - return iter; -} - -static inline ZixTreeIter* -index_lower_bound(ZixTree* db, const SordQuad search_key) -{ - ZixTreeIter* iter = NULL; - zix_tree_find(db, (const void*)search_key, &iter); - if (!iter) { - return NULL; - } - - ZixTreeIter* prev = NULL; - while ((prev = zix_tree_iter_prev(iter))) { - if (!prev) { - return iter; - } - - const SordNode** const key = (const SordNode**)zix_tree_get(prev); - if (!sord_quad_match_inline(key, search_key)) { - return iter; - } - - iter = prev; - } - - return iter; -} - SordIter* sord_find(SordModel* sord, const SordQuad pat) { @@ -821,16 +788,19 @@ sord_find(SordModel* sord, const SordQuad pat) if (pat[0] && pat[1] && pat[2] && pat[3]) mode = SINGLE; // No duplicate quads (Sord is a set) - ZixTree* const db = sord->indices[index_order]; - ZixTreeIter* const cur = index_lower_bound(db, pat); - if (zix_tree_iter_is_end(cur)) { + ZixBTree* const db = sord->indices[index_order]; + ZixBTreeIter* cur = NULL; + zix_btree_lower_bound(db, pat, &cur); + if (zix_btree_iter_is_end(cur)) { SORD_FIND_LOG("No match found\n"); + zix_btree_iter_free(cur); return NULL; } - const SordNode** const key = (const SordNode**)zix_tree_get(cur); + const SordNode** const key = (const SordNode**)zix_btree_get(cur); if (!key || ( (mode == RANGE || mode == SINGLE) && !sord_quad_match_inline(pat, key) )) { SORD_FIND_LOG("No match found\n"); + zix_btree_iter_free(cur); return NULL; } @@ -1202,7 +1172,7 @@ sord_node_copy(const SordNode* node) static inline bool sord_add_to_index(SordModel* sord, const SordNode** tup, SordOrder order) { - return !zix_tree_insert(sord->indices[order], tup, NULL); + return !zix_btree_insert(sord->indices[order], tup); } bool @@ -1240,16 +1210,10 @@ sord_remove(SordModel* sord, const SordQuad tup) { SORD_WRITE_LOG("Remove " TUP_FMT "\n", TUP_FMT_ARGS(tup)); - SordNode** quad = NULL; + SordNode* quad = NULL; for (unsigned i = 0; i < NUM_ORDERS; ++i) { if (sord->indices[i]) { - ZixTreeIter* const cur = index_search(sord->indices[i], tup); - if (!zix_tree_iter_is_end(cur)) { - if (!quad) { - quad = (SordNode**)zix_tree_get(cur); - } - zix_tree_remove(sord->indices[i], cur); - } else { + if (zix_btree_remove(sord->indices[i], tup, (void**)&quad)) { assert(i == 0); // Assuming index coherency return; // Quad not found, do nothing } diff --git a/src/sord_test.c b/src/sord_test.c index b0cee35..a845c9e 100644 --- a/src/sord_test.c +++ b/src/sord_test.c @@ -533,7 +533,7 @@ main(int argc, char** argv) sord_add(sord, tup); sord_remove(sord, tup); if (sord_num_quads(sord) != 1) { - fprintf(stderr, "Removed failed (%zu quads, expected 1)\n", + fprintf(stderr, "Remove failed (%zu quads, expected 1)\n", sord_num_quads(sord)); goto fail; } diff --git a/src/sord_validate.c b/src/sord_validate.c index 8b5f04b..7c44941 100644 --- a/src/sord_validate.c +++ b/src/sord_validate.c @@ -242,7 +242,7 @@ check_restriction(SordModel* model, sord_node_get_string(type), sord_node_get_string(lower)); } - + sord_iter_free(l); return good; } @@ -267,7 +267,7 @@ check_restriction(SordModel* model, sord_node_get_string(type), sord_node_get_string(upper)); } - + sord_iter_free(u); return good; } diff --git a/src/zix/btree.c b/src/zix/btree.c new file mode 100644 index 0000000..26885e2 --- /dev/null +++ b/src/zix/btree.c @@ -0,0 +1,702 @@ +/* + Copyright 2011-2014 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 <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "zix/btree.h" + +// #define ZIX_BTREE_DEBUG 1 + +#define ZIX_BTREE_PAGE_SIZE 4096 +#define ZIX_BTREE_NODE_SPACE (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint32_t)) +#define ZIX_BTREE_LEAF_VALS (ZIX_BTREE_NODE_SPACE / sizeof(void*)) +#define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2) + +struct ZixBTreeImpl { + ZixBTreeNode* root; + ZixDestroyFunc destroy; + ZixComparator cmp; + void* cmp_data; + size_t size; + unsigned height; ///< Number of levels, i.e. root only has height 1 +}; + +struct ZixBTreeNodeImpl { + uint32_t is_leaf; + uint32_t n_vals; + void* vals[ZIX_BTREE_INODE_VALS]; // ZIX_BTREE_LEAF_VALS for leaves + ZixBTreeNode* children[ZIX_BTREE_INODE_VALS + 1]; // Nonexistent for leaves +}; + +typedef struct { + ZixBTreeNode* node; + unsigned index; +} ZixBTreeIterFrame; + +struct ZixBTreeIterImpl { + unsigned level; ///< Current level in pos + ZixBTreeIterFrame stack[]; ///< Position stack +}; + +#ifdef ZIX_BTREE_DEBUG + +ZIX_PRIVATE void +print_node(const ZixBTreeNode* n, const char* prefix) +{ + printf("%s[", prefix); + for (unsigned v = 0; v < n->n_vals; ++v) { + printf(" %lu", (uintptr_t)n->vals[v]); + } + printf(" ]\n"); +} + +ZIX_PRIVATE void +print_tree(const ZixBTreeNode* parent, const ZixBTreeNode* node, int level) +{ + if (node) { + if (!parent) { + printf("TREE {\n"); + } + for (int i = 0; i < level + 1; ++i) { + printf(" "); + } + print_node(node, ""); + if (!node->is_leaf) { + for (unsigned i = 0; i < node->n_vals + 1; ++i) { + print_tree(node, node->children[i], level + 1); + } + } + if (!parent) { + printf("}\n"); + } + } +} + +#endif // ZIX_BTREE_DEBUG + +ZIX_PRIVATE ZixBTreeNode* +zix_btree_node_new(const bool leaf) +{ + assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE); + ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode)); + if (node) { + node->is_leaf = leaf; + node->n_vals = 0; + } + return node; +} + +ZIX_API ZixBTree* +zix_btree_new(const ZixComparator cmp, + void* const cmp_data, + const ZixDestroyFunc destroy) +{ + ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree)); + if (t) { + t->root = zix_btree_node_new(true); + t->destroy = destroy; + t->cmp = cmp; + t->cmp_data = cmp_data; + t->size = 0; + t->height = 1; + if (!t->root) { + free(t); + return NULL; + } + } + return t; +} + +ZIX_PRIVATE void +zix_btree_free_rec(ZixBTree* const t, ZixBTreeNode* const n) +{ + if (n) { + if (t->destroy) { + for (unsigned i = 0; i < n->n_vals; ++i) { + t->destroy(n->vals[i]); + } + } + if (!n->is_leaf) { + for (unsigned i = 0; i < n->n_vals + 1; ++i) { + zix_btree_free_rec(t, n->children[i]); + } + } + free(n); + } +} + +ZIX_API void +zix_btree_free(ZixBTree* const t) +{ + if (t) { + zix_btree_free_rec(t, t->root); + free(t); + } +} + +ZIX_API size_t +zix_btree_size(const ZixBTree* const t) +{ + return t->size; +} + +ZIX_PRIVATE unsigned +zix_btree_max_vals(const ZixBTreeNode* const node) +{ + return node->is_leaf ? ZIX_BTREE_LEAF_VALS : ZIX_BTREE_INODE_VALS; +} + +ZIX_PRIVATE unsigned +zix_btree_min_vals(const ZixBTreeNode* const node) +{ + return ((zix_btree_max_vals(node) + 1) / 2) - 1; +} + +/** Shift pointers in `array` of length `n` right starting at `i`. */ +ZIX_PRIVATE void +zix_btree_ainsert(void** const array, + const unsigned n, + const unsigned i, + void* const e) +{ + memmove(array + i + 1, array + i, (n - i) * sizeof(e)); + array[i] = e; +} + +/** Erase element `i` in `array` of length `n` and return erased element. */ +ZIX_PRIVATE void* +zix_btree_aerase(void** const array, const unsigned n, const unsigned i) +{ + void* const ret = array[i]; + memmove(array + i, array + i + 1, (n - i) * sizeof(ret)); + return ret; +} + +/** Split lhs, the i'th child of `n`, into two nodes. */ +ZIX_PRIVATE ZixBTreeNode* +zix_btree_split_child(ZixBTreeNode* const n, + const uint32_t i, + ZixBTreeNode* const lhs) +{ + assert(lhs->n_vals == zix_btree_max_vals(lhs)); + assert(n->n_vals < ZIX_BTREE_INODE_VALS); + assert(i < n->n_vals + 1); + assert(n->children[i] == lhs); + + const unsigned max_n_vals = zix_btree_max_vals(lhs); + ZixBTreeNode* rhs = zix_btree_node_new(lhs->is_leaf); + if (!rhs) { + return NULL; + } + + // LHS and RHS get roughly half, less the middle value which moves up + lhs->n_vals = max_n_vals / 2; + rhs->n_vals = max_n_vals - lhs->n_vals - 1; + + // Copy large half of values from LHS to new RHS node + memcpy(rhs->vals, + lhs->vals + lhs->n_vals + 1, + rhs->n_vals * sizeof(void*)); + + // Copy large half of children from LHS to new RHS node + if (!lhs->is_leaf) { + memcpy(rhs->children, + lhs->children + lhs->n_vals + 1, + (rhs->n_vals + 1) * sizeof(ZixBTreeNode*)); + } + + // Move middle value up to parent + zix_btree_ainsert(n->vals, n->n_vals, i, lhs->vals[lhs->n_vals]); + + // Insert new RHS node in parent at position i + zix_btree_ainsert((void**)n->children, ++n->n_vals, i + 1, rhs); + + return rhs; +} + +/** Find the first value in `n` that is not less than `e` (lower bound). */ +ZIX_PRIVATE unsigned +zix_btree_node_find(const ZixBTree* const t, + const ZixBTreeNode* const n, + const void* const e, + bool* const equal) +{ + unsigned first = 0; + unsigned len = n->n_vals; + while (len > 0) { + const unsigned half = len >> 1; + const unsigned i = first + half; + const int cmp = t->cmp(n->vals[i], e, t->cmp_data); + if (cmp == 0) { + *equal = true; + len = half; // Keep searching for wildcard matches + } else if (cmp < 0) { + const unsigned chop = half + 1; + first += chop; + len -= chop; + } else { + len = half; + } + } + assert(!*equal || t->cmp(n->vals[first], e, t->cmp_data) == 0); + return first; +} + +ZIX_API ZixStatus +zix_btree_insert(ZixBTree* const t, void* const e) +{ + ZixBTreeNode* parent = NULL; // Parent of n + ZixBTreeNode* n = t->root; // Current node + unsigned i = 0; // Index of n in parent + while (n) { + if (n->n_vals == zix_btree_max_vals(n)) { + // Node is full, split to ensure there is space for a leaf split + if (!parent) { + // Root is full, grow tree upwards + if (!(parent = zix_btree_node_new(false))) { + return ZIX_STATUS_NO_MEM; + } + t->root = parent; + parent->children[0] = n; + ++t->height; + } + + ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n); + if (!rhs) { + return ZIX_STATUS_NO_MEM; + } + + const int cmp = t->cmp(parent->vals[i], e, t->cmp_data); + if (cmp == 0) { + return ZIX_STATUS_EXISTS; + } else if (cmp < 0) { + // Move to new RHS + n = rhs; + ++i; + } + } + + assert(!parent || parent->children[i] == n); + + bool equal = false; + i = zix_btree_node_find(t, n, e, &equal); + if (equal) { + return ZIX_STATUS_EXISTS; + } else if (!n->is_leaf) { + // Descend to child node left of value + parent = n; + n = n->children[i]; + } else { + // Insert into internal node + zix_btree_ainsert(n->vals, n->n_vals, i, e); + break; + } + } + + ++n->n_vals; + ++t->size; + + return ZIX_STATUS_SUCCESS; +} + +ZIX_PRIVATE bool +zix_btree_node_is_minimal(ZixBTreeNode* const n) +{ + assert(n->n_vals >= zix_btree_min_vals(n)); + return n->n_vals == zix_btree_min_vals(n); +} + +/** Enlarge left child by stealing a value from its right sibling. */ +ZIX_PRIVATE ZixBTreeNode* +zix_btree_rotate_left(ZixBTreeNode* const parent, const unsigned i) +{ + ZixBTreeNode* const lhs = parent->children[i]; + ZixBTreeNode* const rhs = parent->children[i + 1]; + + // Move parent value to end of LHS + lhs->vals[lhs->n_vals++] = parent->vals[i]; + + // Move first child pointer from RHS to end of LHS + if (!lhs->is_leaf) { + lhs->children[lhs->n_vals] = zix_btree_aerase( + (void**)rhs->children, rhs->n_vals, 0); + } + + // Move first value in RHS to parent + parent->vals[i] = zix_btree_aerase(rhs->vals, --rhs->n_vals, 0); + + return lhs; +} + +/** Enlarge right child by stealing a value from its left sibling. */ +ZIX_PRIVATE ZixBTreeNode* +zix_btree_rotate_right(ZixBTreeNode* const parent, const unsigned i) +{ + ZixBTreeNode* const lhs = parent->children[i - 1]; + ZixBTreeNode* const rhs = parent->children[i]; + + // Prepend parent value to RHS + zix_btree_ainsert(rhs->vals, rhs->n_vals++, 0, parent->vals[i - 1]); + + // Move last child pointer from LHS and prepend to RHS + if (!lhs->is_leaf) { + zix_btree_ainsert((void**)rhs->children, + rhs->n_vals, + 0, + lhs->children[lhs->n_vals]); + } + + // Move last value from LHS to parent + parent->vals[i - 1] = lhs->vals[--lhs->n_vals]; + + return rhs; +} + +/** Move n[i] down, merge the left and right child, return the merged node. */ +ZIX_PRIVATE ZixBTreeNode* +zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const unsigned i) +{ + ZixBTreeNode* const lhs = n->children[i]; + ZixBTreeNode* const rhs = n->children[i + 1]; + + assert(zix_btree_node_is_minimal(n->children[i])); + assert(lhs->n_vals + rhs->n_vals < zix_btree_max_vals(lhs)); + + // Move parent value to end of LHS + lhs->vals[lhs->n_vals++] = zix_btree_aerase(n->vals, n->n_vals, i); + + // Erase corresponding child pointer (to RHS) in parent + zix_btree_aerase((void**)n->children, n->n_vals, i + 1); + + // Add everything from RHS to end of LHS + memcpy(lhs->vals + lhs->n_vals, rhs->vals, rhs->n_vals * sizeof(void*)); + if (!lhs->is_leaf) { + memcpy(lhs->children + lhs->n_vals, + rhs->children, + (rhs->n_vals + 1) * sizeof(void*)); + } + lhs->n_vals += rhs->n_vals; + + if (--n->n_vals == 0) { + // Root is now empty, replace it with its only child + assert(n == t->root); + t->root = lhs; + free(n); + } + + free(rhs); + return lhs; +} + +/** Remove and return the min value from the subtree rooted at `n`. */ +ZIX_PRIVATE void* +zix_btree_remove_min(ZixBTree* const t, ZixBTreeNode* n) +{ + while (!n->is_leaf) { + if (zix_btree_node_is_minimal(n->children[0])) { + // Leftmost child is minimal, must expand + if (!zix_btree_node_is_minimal(n->children[1])) { + // Child's right sibling has at least one key to steal + n = zix_btree_rotate_left(n, 0); + } else { + // Both child and right sibling are minimal, merge + n = zix_btree_merge(t, n, 0); + } + } else { + n = n->children[0]; + } + } + + return zix_btree_aerase(n->vals, --n->n_vals, 0); +} + +/** Remove and return the max value from the subtree rooted at `n`. */ +ZIX_PRIVATE void* +zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n) +{ + while (!n->is_leaf) { + if (zix_btree_node_is_minimal(n->children[n->n_vals])) { + // Leftmost child is minimal, must expand + if (!zix_btree_node_is_minimal(n->children[n->n_vals - 1])) { + // Child's left sibling has at least one key to steal + n = zix_btree_rotate_right(n, n->n_vals); + } else { + // Both child and left sibling are minimal, merge + n = zix_btree_merge(t, n, n->n_vals - 1); + } + } else { + n = n->children[n->n_vals]; + } + } + + return n->vals[--n->n_vals]; +} + +ZIX_PRIVATE ZixStatus +zix_btree_remove_rec(ZixBTree* const t, + ZixBTreeNode* const n, + const void* const e, + void** const removed) +{ + /* To remove in a single walk down, the tree is adjusted along the way so + that the current node always has at least one more value than the + minimum required in general. Thus, there is always room to remove + without adjusting on the way back up. */ + assert(n == t->root || !zix_btree_node_is_minimal(n)); + + bool equal = false; + const unsigned i = zix_btree_node_find(t, n, e, &equal); + + if (n->is_leaf) { + if (equal) { + // Found in leaf node + *removed = zix_btree_aerase(n->vals, --n->n_vals, i); + return ZIX_STATUS_SUCCESS; + } else { + // Not found in leaf node, or tree + return ZIX_STATUS_NOT_FOUND; + } + } else if (equal) { + // Found in internal node + if (!zix_btree_node_is_minimal(n->children[i])) { + // Left child can remove without merge + *removed = n->vals[i]; + n->vals[i] = zix_btree_remove_max(t, n->children[i]); + return ZIX_STATUS_SUCCESS; + } else if (!zix_btree_node_is_minimal(n->children[i + 1])) { + // Right child can remove without merge + *removed = n->vals[i]; + n->vals[i] = zix_btree_remove_min(t, n->children[i + 1]); + return ZIX_STATUS_SUCCESS; + } else { + // Both preceding and succeeding child are minimal + ZixBTreeNode* const merged = zix_btree_merge(t, n, i); + return zix_btree_remove_rec(t, merged, e, removed); + } + } else { + // Not found in internal node, key is in/under children[i] + if (zix_btree_node_is_minimal(n->children[i])) { + if (i > 0 && !zix_btree_node_is_minimal(n->children[i - 1])) { + // Child's left sibling has at least one key to steal + ZixBTreeNode* const rhs = zix_btree_rotate_right(n, i); + return zix_btree_remove_rec(t, rhs, e, removed); + } else if (i < n->n_vals && + !zix_btree_node_is_minimal(n->children[i + 1])) { + // Child's right sibling has at least one key to steal + ZixBTreeNode* const lhs = zix_btree_rotate_left(n, i); + return zix_btree_remove_rec(t, lhs, e, removed); + } else { + // Both child's siblings are minimal, merge them + const unsigned m = (i < n->n_vals) ? i : i - 1; + ZixBTreeNode* const merged = zix_btree_merge(t, n, m); + return zix_btree_remove_rec(t, merged, e, removed); + } + } else { + return zix_btree_remove_rec(t, n->children[i], e, removed); + } + } + + assert(false); // Not reached + return ZIX_STATUS_ERROR; +} + +ZIX_API ZixStatus +zix_btree_remove(ZixBTree* const t, const void* const e, void** const removed) +{ + const ZixStatus st = zix_btree_remove_rec(t, t->root, e, removed); + if (!st) { + --t->size; + } + return st; +} + +ZIX_PRIVATE ZixBTreeIter* +zix_btree_iter_new(const ZixBTree* const t) +{ + const size_t s = t->height * sizeof(ZixBTreeIterFrame); + ZixBTreeIter* const i = (ZixBTreeIter*)malloc(sizeof(ZixBTreeIter) + s); + if (i) { + i->level = 0; + } + return i; +} + +ZIX_API ZixStatus +zix_btree_find(const ZixBTree* const t, + const void* const e, + ZixBTreeIter** const ti) +{ + ZixBTreeNode* n = t->root; + if (!(*ti = zix_btree_iter_new(t))) { + return ZIX_STATUS_NO_MEM; + } + + while (n) { + bool equal = false; + const unsigned i = zix_btree_node_find(t, n, e, &equal); + + // Update iterator stack + (*ti)->stack[(*ti)->level].node = n; + (*ti)->stack[(*ti)->level].index = i; + + if (equal) { + return ZIX_STATUS_SUCCESS; + } else if (n->is_leaf) { + break; + } else { + ++(*ti)->level; + n = n->children[i]; + } + } + + zix_btree_iter_free(*ti); + *ti = NULL; + return ZIX_STATUS_NOT_FOUND; +} + +ZIX_API ZixStatus +zix_btree_lower_bound(const ZixBTree* const t, + const void* const e, + ZixBTreeIter** const ti) +{ + ZixBTreeNode* n = t->root; + bool found = false; + unsigned found_level = 0; + if (!(*ti = zix_btree_iter_new(t))) { + return ZIX_STATUS_NO_MEM; + } + + while (n) { + bool equal = false; + const unsigned i = zix_btree_node_find(t, n, e, &equal); + + // Update iterator stack + (*ti)->stack[(*ti)->level].node = n; + (*ti)->stack[(*ti)->level].index = i; + + if (equal) { + found_level = (*ti)->level; + found = true; + } + + if (n->is_leaf) { + break; + } else { + ++(*ti)->level; + n = n->children[i]; + } + } + + const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level]; + if (frame->index == frame->node->n_vals) { + if (found) { + // Found on a previous level but went too far + (*ti)->level = found_level; + } else { + // Reached end (key is greater than everything in tree) + (*ti)->stack[0].node = NULL; + } + } + + return ZIX_STATUS_SUCCESS; +} + +ZIX_API void* +zix_btree_get(const ZixBTreeIter* const ti) +{ + const ZixBTreeIterFrame* const frame = &ti->stack[ti->level]; + assert(frame->index < frame->node->n_vals); + return frame->node->vals[frame->index]; +} + +ZIX_API ZixBTreeIter* +zix_btree_begin(const ZixBTree* const t) +{ + ZixBTreeIter* const i = zix_btree_iter_new(t); + if (!i) { + return NULL; + } else if (t->size == 0) { + i->stack[0].node = NULL; + } else { + ZixBTreeNode* n = t->root; + i->stack[0].node = n; + i->stack[0].index = 0; + while (!n->is_leaf) { + n = n->children[0]; + ++i->level; + i->stack[i->level].node = n; + i->stack[i->level].index = 0; + } + } + return i; +} + +ZIX_API bool +zix_btree_iter_is_end(const ZixBTreeIter* const i) +{ + return !i || i->stack[0].node == NULL; +} + +ZIX_API void +zix_btree_iter_increment(ZixBTreeIter* const i) +{ + ZixBTreeIterFrame* f = &i->stack[i->level]; + if (f->node->is_leaf) { + // Leaf, move right + assert(f->index < f->node->n_vals); + if (++f->index == f->node->n_vals) { + // Reached end of leaf, move up + f = &i->stack[i->level]; + while (i->level > 0 && f->index == f->node->n_vals) { + f = &i->stack[--i->level]; + assert(f->index <= f->node->n_vals); + } + + if (f->index == f->node->n_vals) { + // Reached end of tree + assert(i->level == 0); + f->node = NULL; + f->index = 0; + } + } + } else { + // Internal node, move down to next child + assert(f->index < f->node->n_vals); + ZixBTreeNode* child = f->node->children[++f->index]; + + f = &i->stack[++i->level]; + f->node = child; + f->index = 0; + + // Move down and left until we hit a leaf + while (!f->node->is_leaf) { + child = f->node->children[0]; + f = &i->stack[++i->level]; + f->node = child; + f->index = 0; + } + } +} + +ZIX_API void +zix_btree_iter_free(ZixBTreeIter* const i) +{ + free(i); +} diff --git a/src/zix/btree.h b/src/zix/btree.h new file mode 100644 index 0000000..0cd549a --- /dev/null +++ b/src/zix/btree.h @@ -0,0 +1,144 @@ +/* + Copyright 2011-2014 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_BTREE_H +#define ZIX_BTREE_H + +#include <stdbool.h> +#include <stddef.h> + +#include "zix/common.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + @addtogroup zix + @{ + @name BTree + @{ +*/ + +/** + A B-Tree. +*/ +typedef struct ZixBTreeImpl ZixBTree; + +/** + A B-Tree node (opaque). +*/ +typedef struct ZixBTreeNodeImpl ZixBTreeNode; + +/** + An iterator over a B-Tree. + + Note that modifying the trees invalidates all iterators, so all iterators + are const iterators. +*/ +typedef struct ZixBTreeIterImpl ZixBTreeIter; + +/** + Create a new (empty) B-Tree. +*/ +ZIX_API ZixBTree* +zix_btree_new(ZixComparator cmp, + void* cmp_data, + ZixDestroyFunc destroy); + +/** + Free `t`. +*/ +ZIX_API void +zix_btree_free(ZixBTree* t); + +/** + Return the number of elements in `t`. +*/ +ZIX_API size_t +zix_btree_size(const ZixBTree* t); + +/** + Insert the element `e` into `t`. +*/ +ZIX_API ZixStatus +zix_btree_insert(ZixBTree* t, void* e); + +/** + Remove the value `e` from `t`, set `removed` to the removed pointer. +*/ +ZIX_API ZixStatus +zix_btree_remove(ZixBTree* t, const void* e, void** removed); + +/** + Set `ti` to an element equal to `e` in `t`. + If no such item exists, `ti` is set to NULL. +*/ +ZIX_API ZixStatus +zix_btree_find(const ZixBTree* t, const void* e, ZixBTreeIter** ti); + +/** + Set `ti` to the smallest element in `t` that is not less than `e`. + + Wildcards are supported, so if the search key `e` compares equal to many + values in the tree, `ti` will be set to the least such element. The search + key `e` is always passed as the second argument to the comparator. +*/ +ZIX_API ZixStatus +zix_btree_lower_bound(const ZixBTree* t, const void* e, ZixBTreeIter** ti); + +/** + Return the data associated with the given tree item. +*/ +ZIX_API void* +zix_btree_get(const ZixBTreeIter* ti); + +/** + Return an iterator to the first (smallest) element in `t`. + + The returned iterator must be freed with zix_btree_iter_free(). +*/ +ZIX_API ZixBTreeIter* +zix_btree_begin(const ZixBTree* t); + +/** + Return true iff `i` is an iterator to the end of its tree. +*/ +ZIX_API bool +zix_btree_iter_is_end(const ZixBTreeIter* i); + +/** + Increment `i` to point to the next element in the tree. +*/ +ZIX_API void +zix_btree_iter_increment(ZixBTreeIter* i); + +/** + Free `i`. +*/ +ZIX_API void +zix_btree_iter_free(ZixBTreeIter* i); + +/** + @} + @} +*/ + +#ifdef __cplusplus +} /* extern "C" */ +#endif + +#endif /* ZIX_BTREE_H */ diff --git a/src/zix/hash.c b/src/zix/hash.c index 655c5df..f633e16 100644 --- a/src/zix/hash.c +++ b/src/zix/hash.c @@ -1,5 +1,5 @@ /* - Copyright 2011 David Robillard <http://drobilla.net> + Copyright 2011-2014 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 @@ -58,13 +58,18 @@ zix_hash_new(ZixHashFunc hash_func, size_t value_size) { ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash)); - hash->hash_func = hash_func; - hash->equal_func = equal_func; - hash->n_buckets = &sizes[0]; - hash->value_size = value_size; - hash->count = 0; - hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets, - sizeof(ZixHashEntry*)); + if (hash) { + hash->hash_func = hash_func; + hash->equal_func = equal_func; + hash->n_buckets = &sizes[0]; + hash->value_size = value_size; + hash->count = 0; + if (!(hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets, + sizeof(ZixHashEntry*)))) { + free(hash); + return NULL; + } + } return hash; } @@ -225,4 +230,3 @@ zix_hash_foreach(ZixHash* hash, } } } - diff --git a/src/zix/tree.c b/src/zix/tree.c deleted file mode 100644 index 23a7e8c..0000000 --- a/src/zix/tree.c +++ /dev/null @@ -1,716 +0,0 @@ -/* - Copyright 2011-2014 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 <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; - ZixDestroyFunc destroy; - ZixComparator cmp; - void* cmp_data; - size_t size; - 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)) - -// Uncomment these for debugging features -// #define ZIX_TREE_DUMP 1 -// #define ZIX_TREE_VERIFY 1 -// #define ZIX_TREE_HYPER_VERIFY 1 - -#if defined(ZIX_TREE_VERIFY) || defined(ZIX_TREE_HYPER_VERIFY) -# include "tree_debug.h" -# define ASSERT_BALANCE(n) assert(verify_balance(n)) -#else -# define ASSERT_BALANCE(n) -#endif - -#ifdef ZIX_TREE_DUMP -# include "tree_debug.h" -# define DUMP(t) zix_tree_print(t->root, 0) -# define DEBUG_PRINTF(fmt, ...) printf(fmt, __VA_ARGS__) -#else -# define DUMP(t) -# define DEBUG_PRINTF(fmt, ...) -#endif - -ZIX_API ZixTree* -zix_tree_new(bool allow_duplicates, - ZixComparator cmp, - void* cmp_data, - ZixDestroyFunc destroy) -{ - ZixTree* t = (ZixTree*)malloc(sizeof(ZixTree)); - t->root = NULL; - t->destroy = destroy; - t->cmp = cmp; - t->cmp_data = cmp_data; - t->size = 0; - t->allow_duplicates = allow_duplicates; - return t; -} - -ZIX_PRIVATE void -zix_tree_free_rec(ZixTree* t, ZixTreeNode* n) -{ - if (n) { - zix_tree_free_rec(t, n->left); - zix_tree_free_rec(t, n->right); - if (t->destroy) { - t->destroy(n->data); - } - free(n); - } -} - -ZIX_API void -zix_tree_free(ZixTree* t) -{ - if (t) { - zix_tree_free_rec(t, t->root); - free(t); - } -} - -ZIX_API size_t -zix_tree_size(const ZixTree* t) -{ - return t->size; -} - -ZIX_PRIVATE 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 `p`. - * - * p q - * / \ / \ - * A q => p C - * / \ / \ - * B C A B - */ -ZIX_PRIVATE ZixTreeNode* -rotate_left(ZixTreeNode* p, int* height_change) -{ - ZixTreeNode* const q = p->right; - *height_change = (q->balance == 0) ? 0 : -1; - - DEBUG_PRINTF("LL %ld\n", (intptr_t)p->data); - - 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_BALANCE(p); - ASSERT_BALANCE(q); - return q; -} - -/** - * Rotate right about `p`. - * - * p q - * / \ / \ - * q C => A p - * / \ / \ - * A B B C - * - */ -ZIX_PRIVATE ZixTreeNode* -rotate_right(ZixTreeNode* p, int* height_change) -{ - ZixTreeNode* const q = p->left; - *height_change = (q->balance == 0) ? 0 : -1; - - DEBUG_PRINTF("RR %ld\n", (intptr_t)p->data); - - 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_BALANCE(p); - ASSERT_BALANCE(q); - return q; -} - -/** - * Rotate left about `p->left` then right about `p`. - * - * p r - * / \ / \ - * q D => q p - * / \ / \ / \ - * A r A B C D - * / \ - * B C - * - */ -ZIX_PRIVATE 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); - - DEBUG_PRINTF("LR %ld P: %2d Q: %2d R: %2d\n", - (intptr_t)p->data, p->balance, q->balance, r->balance); - - 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; - - *height_change = -1; - - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - ASSERT_BALANCE(r); - return r; -} - -/** - * Rotate right about `p->right` then right about `p`. - * - * p r - * / \ / \ - * A q => p q - * / \ / \ / \ - * r D A B C D - * / \ - * B C - * - */ -ZIX_PRIVATE 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); - - DEBUG_PRINTF("RL %ld P: %2d Q: %2d R: %2d\n", - (intptr_t)p->data, p->balance, q->balance, r->balance); - - 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); - - *height_change = -1; - - ASSERT_BALANCE(p); - ASSERT_BALANCE(q); - ASSERT_BALANCE(r); - return r; -} - -ZIX_PRIVATE ZixTreeNode* -zix_tree_rebalance(ZixTree* t, ZixTreeNode* node, int* height_change) -{ -#ifdef ZIX_TREE_HYPER_VERIFY - const size_t old_height = height(node); -#endif - DEBUG_PRINTF("REBALANCE %ld (%d)\n", (intptr_t)node->data, node->balance); - *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 ZixStatus -zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti) -{ - DEBUG_PRINTF("**** INSERT %ld\n", (intptr_t)e); - 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; - } - DEBUG_PRINTF("%ld EXISTS!\n", (intptr_t)e); - return ZIX_STATUS_EXISTS; - } - } - - // Allocate a new node n - if (!(n = (ZixTreeNode*)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; - } - } - - 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); - - ++t->size; - -#ifdef ZIX_TREE_VERIFY - if (!verify(t, t->root)) { - return ZIX_STATUS_ERROR; - } -#endif - - 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 - - DEBUG_PRINTF("*** REMOVE %ld\n", (intptr_t)n->data); - - if ((n == t->root) && !n->left && !n->right) { - t->root = NULL; - if (t->destroy) { - t->destroy(n->data); - } - free(n); - --t->size; - assert(t->size == 0); - 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); - - if (t->destroy) { - t->destroy(n->data); - } - free(n); - - --t->size; - -#ifdef ZIX_TREE_VERIFY - if (!verify(t, t->root)) { - return ZIX_STATUS_ERROR; - } -#endif - - 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 ? ti->data : NULL; -} - -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 ZixTreeIter* -zix_tree_rbegin(ZixTree* t) -{ - if (!t->root) { - return NULL; - } - - ZixTreeNode* n = t->root; - while (n->right) { - n = n->right; - } - return n; -} - -ZIX_API ZixTreeIter* -zix_tree_rend(ZixTree* t) -{ - return NULL; -} - -ZIX_API bool -zix_tree_iter_is_end(ZixTreeIter* i) -{ - return !i; -} - -ZIX_API bool -zix_tree_iter_is_rend(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 deleted file mode 100644 index 8474b1c..0000000 --- a/src/zix/tree.h +++ /dev/null @@ -1,148 +0,0 @@ -/* - Copyright 2011-2014 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 <stddef.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 ZixTree. -*/ -typedef struct ZixTreeNodeImpl ZixTreeIter; - -/** - Create a new (empty) tree. -*/ -ZIX_API ZixTree* -zix_tree_new(bool allow_duplicates, - ZixComparator cmp, - void* cmp_data, - ZixDestroyFunc destroy); - -/** - Free `t`. -*/ -ZIX_API void -zix_tree_free(ZixTree* t); - -/** - Return the number of elements in `t`. -*/ -ZIX_API size_t -zix_tree_size(const ZixTree* t); - -/** - Insert the element `e` into `t` and point `ti` at the new element. -*/ -ZIX_API ZixStatus -zix_tree_insert(ZixTree* t, void* e, ZixTreeIter** ti); - -/** - Remove the item pointed at by `ti` from `t`. -*/ -ZIX_API ZixStatus -zix_tree_remove(ZixTree* t, ZixTreeIter* ti); - -/** - Set `ti` to an element equal to `e` in `t`. - If no such item exists, `ti` is set to NULL. -*/ -ZIX_API ZixStatus -zix_tree_find(const ZixTree* t, const void* e, ZixTreeIter** ti); - -/** - Return the data associated with the given tree item. -*/ -ZIX_API void* -zix_tree_get(ZixTreeIter* ti); - -/** - Return an iterator to the first (smallest) element in `t`. -*/ -ZIX_API ZixTreeIter* -zix_tree_begin(ZixTree* t); - -/** - Return an iterator the the element one past the last element in `t`. -*/ -ZIX_API ZixTreeIter* -zix_tree_end(ZixTree* t); - -/** - Return true iff `i` is an iterator to the end of its tree. -*/ -ZIX_API bool -zix_tree_iter_is_end(ZixTreeIter* i); - -/** - Return an iterator to the last (largest) element in `t`. -*/ -ZIX_API ZixTreeIter* -zix_tree_rbegin(ZixTree* t); - -/** - Return an iterator the the element one before the first element in `t`. -*/ -ZIX_API ZixTreeIter* -zix_tree_rend(ZixTree* t); - -/** - Return true iff `i` is an iterator to the reverse end of its tree. -*/ -ZIX_API bool -zix_tree_iter_is_rend(ZixTreeIter* i); - -/** - Return an iterator that points to the element one past `i`. -*/ -ZIX_API ZixTreeIter* -zix_tree_iter_next(ZixTreeIter* i); - -/** - Return an iterator that points to the element one before `i`. -*/ -ZIX_API ZixTreeIter* -zix_tree_iter_prev(ZixTreeIter* i); - -/** - @} - @} -*/ - -#ifdef __cplusplus -} /* extern "C" */ -#endif - -#endif /* ZIX_TREE_H */ @@ -10,7 +10,7 @@ import waflib.extras.autowaf as autowaf # major increment <=> incompatible changes # minor increment <=> compatible changes (additions) # micro increment <=> no interface changes -SORD_VERSION = '0.12.2' +SORD_VERSION = '0.12.3' SORD_MAJOR_VERSION = '0' # Mandatory waf variables |