summaryrefslogtreecommitdiffstats
path: root/src/sord.c
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2020-11-11 21:04:17 +0100
committerDavid Robillard <d@drobilla.net>2020-11-11 21:04:17 +0100
commit272eb488547638125f1ccce47f6273dc8309bcc7 (patch)
tree04c7e1ca17c85530467652ac64c5c27690f5e037 /src/sord.c
parent5e3efed788f4b184ed02d147588ff53c20c244f5 (diff)
downloadsord-272eb488547638125f1ccce47f6273dc8309bcc7.tar.gz
sord-272eb488547638125f1ccce47f6273dc8309bcc7.tar.bz2
sord-272eb488547638125f1ccce47f6273dc8309bcc7.zip
Fix filtering query modes
These were incorrect before because the tree was not ordered with respect to the search key. Enabling ZIX_BTREE_SORTED_CHECK (which should probably have a configure option) catches this.
Diffstat (limited to 'src/sord.c')
-rw-r--r--src/sord.c19
1 files changed, 18 insertions, 1 deletions
diff --git a/src/sord.c b/src/sord.c
index 5a759c0..557e11d 100644
--- a/src/sord.c
+++ b/src/sord.c
@@ -840,7 +840,24 @@ sord_find(SordModel* model, const SordQuad pat)
ZixBTree* const db = model->indices[index_order];
ZixBTreeIter* cur = NULL;
- zix_btree_lower_bound(db, pat, &cur);
+
+ if (mode == FILTER_ALL) {
+ // No prefix shared with an index at all, linear search (worst case)
+ cur = zix_btree_begin(db);
+ } else if (mode == FILTER_RANGE) {
+ /* Some prefix, but filtering still required. Build a search pattern
+ with only the prefix to find the lower bound in log time. */
+ SordQuad prefix_pat = { NULL, NULL, NULL, NULL };
+ const int* const ordering = orderings[index_order];
+ for (int i = 0; i < n_prefix; ++i) {
+ prefix_pat[ordering[i]] = pat[ordering[i]];
+ }
+ zix_btree_lower_bound(db, prefix_pat, &cur);
+ } else {
+ // Ideal case, pattern matches an index with no filtering required
+ 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);