From cbd0da24a96c79eafed994e694a5c7ae94135591 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Fri, 13 May 2011 19:14:06 +0000 Subject: Save space by storing a single quad in each index and passing ordering to comparator function rather than permuting the actual quads. git-svn-id: http://svn.drobilla.net/sord/trunk@116 3d64ff67-21c5-427c-a301-fe4f08042e5a --- src/sord.c | 105 +++++++++++++++++++++++++++++++------------------------------ 1 file changed, 53 insertions(+), 52 deletions(-) (limited to 'src') diff --git a/src/sord.c b/src/sord.c index fdd7b84..0a72f86 100644 --- a/src/sord.c +++ b/src/sord.c @@ -254,11 +254,13 @@ sord_quad_match(const SordQuad x, const SordQuad y) static int sord_quad_compare(const void* x_ptr, const void* y_ptr, void* user_data) { - SordNode** const x = (SordNode**)x_ptr; - SordNode** const y = (SordNode**)y_ptr; + const int* const ordering = (const int*)user_data; + SordNode** const x = (SordNode**)x_ptr; + SordNode** const y = (SordNode**)y_ptr; for (int i = 0; i < TUP_LEN; ++i) { - const int cmp = sord_node_compare(x[i], y[i]); + const int idx = ordering[i]; + const int cmp = sord_node_compare(x[idx], y[idx]); if (cmp) return cmp; } @@ -324,7 +326,8 @@ sord_iter_seek_match_range(SordIter* iter) return false; // Found match for (int i = 0; i < iter->n_prefix; ++i) { - if (!sord_id_match(key[i], iter->pat[i])) { + const int idx = iter->ordering[i]; + if (!sord_id_match(key[idx], iter->pat[idx])) { iter->end = true; // Reached end of valid range return true; } @@ -348,7 +351,7 @@ sord_iter_new(const SordModel* sord, GSequenceIter* cur, const SordQuad pat, iter->end = false; iter->skip_graphs = order < GSPO; for (int i = 0; i < TUP_LEN; ++i) { - iter->pat[i] = pat[ordering[i]]; + iter->pat[i] = pat[i]; iter->ordering[i] = ordering[i]; } @@ -388,10 +391,9 @@ void sord_iter_get(const SordIter* iter, SordQuad id) { SordNode** key = (SordNode**)g_sequence_get(iter->cur); - id[iter->ordering[0]] = key[0]; - id[iter->ordering[1]] = key[1]; - id[iter->ordering[2]] = key[2]; - id[iter->ordering[3]] = key[3]; + for (int i = 0; i < TUP_LEN; ++i) { + id[i] = key[i]; + } } bool @@ -417,7 +419,8 @@ sord_iter_next(SordIter* iter) key = (const SordNode**)g_sequence_get(iter->cur); assert(key); for (int i = 0; i < iter->n_prefix; ++i) { - if (!sord_id_match(key[i], iter->pat[i])) { + const int idx = iter->ordering[i]; + if (!sord_id_match(key[idx], iter->pat[idx])) { iter->end = true; SORD_ITER_LOG("%p reached non-match end\n", (void*)iter); break; @@ -556,9 +559,9 @@ sord_new(SordWorld* world, unsigned indices, bool graphs) for (unsigned i = 0; i < (NUM_ORDERS / 2); ++i) { if (indices & (1 << i)) { - sord->indices[i] = g_sequence_new(free); + sord->indices[i] = g_sequence_new(NULL); if (graphs) { - sord->indices[i + (NUM_ORDERS / 2)] = g_sequence_new(free); + sord->indices[i + (NUM_ORDERS / 2)] = g_sequence_new(NULL); } else { sord->indices[i + (NUM_ORDERS / 2)] = NULL; } @@ -569,7 +572,7 @@ sord_new(SordWorld* world, unsigned indices, bool graphs) } if (!sord->indices[DEFAULT_ORDER]) { - sord->indices[DEFAULT_ORDER] = g_sequence_new(free); + sord->indices[DEFAULT_ORDER] = g_sequence_new(NULL); } return sord; @@ -641,6 +644,14 @@ sord_free(SordModel* sord) } sord_iter_free(i); + // Free quads + for (GSequenceIter* i = g_sequence_get_begin_iter(sord->indices[DEFAULT_ORDER]); + !g_sequence_iter_is_end(i); + i = g_sequence_iter_next(i)) { + free(g_sequence_get(i)); + } + + // Free indices for (unsigned i = 0; i < NUM_ORDERS; ++i) if (sord->indices[i]) g_sequence_free(sord->indices[i]); @@ -679,14 +690,14 @@ sord_begin(const SordModel* sord) } static inline GSequenceIter* -index_search(SordModel* sord, GSequence* db, const SordQuad search_key) +index_search(GSequence* db, const SordQuad search_key, const int* ordering) { return g_sequence_search( - db, (void*)search_key, sord_quad_compare, sord); + db, (void*)search_key, sord_quad_compare, (void*)ordering); } static inline GSequenceIter* -index_lower_bound_iter(SordModel* sord, GSequenceIter* i, const SordQuad search_key) +index_lower_bound_iter(GSequenceIter* i, const SordQuad search_key) { /* i is now at the position where search_key would be inserted, but this is not necessarily a match, and we need the leftmost... @@ -728,11 +739,11 @@ index_lower_bound_iter(SordModel* sord, GSequenceIter* i, const SordQuad search_ } static inline GSequenceIter* -index_lower_bound(SordModel* sord, GSequence* db, const SordQuad search_key) +index_lower_bound(GSequence* db, const SordQuad search_key, const int* ordering) { GSequenceIter* i = g_sequence_search( - db, (void*)search_key, sord_quad_compare, sord); - return index_lower_bound_iter(sord, i, search_key); + db, (void*)search_key, sord_quad_compare, (void*)ordering); + return index_lower_bound_iter(i, search_key); } SordIter* @@ -750,28 +761,18 @@ sord_find(SordModel* sord, const SordQuad pat) TUP_FMT_ARGS(pat), order_names[index_order], mode, prefix_len, ordering[0], ordering[1], ordering[2], ordering[3]); - /* It's easiest to think about this algorithm in terms of (S P O) ordering, - assuming (A B C) == (S P O). For other orderings this is not actually - the case, but it works the same way. - */ - const SordNode* a = pat[ordering[0]]; // Most Significant Node (MSN) - const SordNode* b = pat[ordering[1]]; // ... - const SordNode* c = pat[ordering[2]]; // ... - const SordNode* d = pat[ordering[3]]; // Least Significant Node (LSN) - - if (a && b && c && d) + if (pat[0] && pat[1] && pat[2] && pat[3]) mode = SINGLE; // No duplicate quads (Sord is a set) - SordQuad search_key = { a, b, c, d }; - GSequence* const db = sord->indices[index_order]; - GSequenceIter* const cur = index_lower_bound(sord, db, search_key); + GSequence* const db = sord->indices[index_order]; + GSequenceIter* const cur = index_lower_bound(db, pat, ordering); if (g_sequence_iter_is_end(cur)) { SORD_FIND_LOG("No match found\n"); return NULL; } const SordNode** const key = (const SordNode**)g_sequence_get(cur); if (!key || ( (mode == RANGE || mode == SINGLE) - && !sord_quad_match_inline(search_key, key) )) { + && !sord_quad_match_inline(pat, key) )) { SORD_FIND_LOG("No match found\n"); return NULL; } @@ -1078,25 +1079,18 @@ sord_node_copy(const SordNode* node) } static inline bool -sord_add_to_index(SordModel* sord, const SordQuad tup, SordOrder order) +sord_add_to_index(SordModel* sord, const SordNode** tup, SordOrder order) { assert(sord->indices[order]); - const int* const ordering = orderings[order]; - const SordQuad key = { - tup[ordering[0]], tup[ordering[1]], tup[ordering[2]], tup[ordering[3]] - }; - GSequenceIter* const cur = index_search(sord, sord->indices[order], key); - GSequenceIter* const match = index_lower_bound_iter(sord, cur, key); + const int* const ordering = orderings[order]; + GSequenceIter* const cur = index_search(sord->indices[order], tup, ordering); + GSequenceIter* const match = index_lower_bound_iter(cur, tup); if (!g_sequence_iter_is_end(match) - && !sord_quad_compare(g_sequence_get(match), key, sord)) { + && !sord_quad_compare(g_sequence_get(match), tup, (void*)ordering)) { return false; // Quad already stored in this index } - // FIXME: would be nice to share quads and just use a different comparator - // for each index (save significant space overhead per quad) - SordNode** key_copy = malloc(sizeof(SordQuad)); - memcpy(key_copy, key, sizeof(SordQuad)); - g_sequence_insert_before(cur, key_copy); + g_sequence_insert_before(cur, tup); return true; } @@ -1109,10 +1103,14 @@ sord_add(SordModel* sord, const SordQuad tup) return false; } + const SordNode** quad = malloc(sizeof(SordQuad)); + memcpy(quad, tup, sizeof(SordQuad)); + for (unsigned i = 0; i < NUM_ORDERS; ++i) { if (sord->indices[i]) { - if (!sord_add_to_index(sord, tup, i)) { + if (!sord_add_to_index(sord, quad, i)) { assert(i == 0); // Assuming index coherency + free(quad); return false; // Quad already stored, do nothing } } @@ -1131,14 +1129,15 @@ sord_remove(SordModel* sord, const SordQuad tup) { SORD_WRITE_LOG("Remove " TUP_FMT "\n", TUP_FMT_ARGS(tup)); + SordNode** quad = NULL; for (unsigned i = 0; i < NUM_ORDERS; ++i) { if (sord->indices[i]) { - const int* const ordering = orderings[i]; - const SordQuad key = { - tup[ordering[0]], tup[ordering[1]], tup[ordering[2]], tup[ordering[3]] - }; - GSequenceIter* const cur = index_search(sord, sord->indices[i], key); + const int* const ordering = orderings[i]; + GSequenceIter* const cur = index_search(sord->indices[i], tup, ordering); if (!g_sequence_iter_is_end(cur)) { + if (!quad) { + quad = g_sequence_get(cur); + } g_sequence_remove(cur); } else { assert(i == 0); // Assuming index coherency @@ -1147,6 +1146,8 @@ sord_remove(SordModel* sord, const SordQuad tup) } } + free(quad); + for (SordQuadIndex i = 0; i < TUP_LEN; ++i) sord_drop_quad_ref(sord, tup[i], i); -- cgit v1.2.1