From 21382932fd8df75884c3e21917d9dbd4527d78ac Mon Sep 17 00:00:00 2001 From: David Robillard Date: Tue, 23 Sep 2014 04:33:24 +0000 Subject: Reduce memory usage and increase performance with a better data structure. git-svn-id: http://svn.drobilla.net/sord/trunk@307 3d64ff67-21c5-427c-a301-fe4f08042e5a --- src/sord.c | 120 ++++++++++++++++++++++--------------------------------------- 1 file changed, 42 insertions(+), 78 deletions(-) (limited to 'src/sord.c') diff --git a/src/sord.c b/src/sord.c index cdfef62..9b4a11a 100644 --- a/src/sord.c +++ b/src/sord.c @@ -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 } -- cgit v1.2.1