aboutsummaryrefslogtreecommitdiffstats
path: root/src/iter.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/iter.c')
-rw-r--r--src/iter.c239
1 files changed, 239 insertions, 0 deletions
diff --git a/src/iter.c b/src/iter.c
new file mode 100644
index 00000000..eaa6de2c
--- /dev/null
+++ b/src/iter.c
@@ -0,0 +1,239 @@
+/*
+ Copyright 2011-2018 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 "iter.h"
+
+#include "log.h"
+#include "model.h"
+#include "statement.h"
+#include "world.h"
+
+#include "serd/serd.h"
+#include "zix/btree.h"
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+static bool
+serd_iter_pattern_matches(const SerdIter* iter, const SerdQuad pat)
+{
+ const SerdStatement* key = (const SerdStatement*)zix_btree_get(iter->cur);
+ for (int i = 0; i < iter->n_prefix; ++i) {
+ const int idx = orderings[iter->order][i];
+ if (!serd_node_pattern_match(key->nodes[idx], pat[idx])) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/**
+ Seek forward as necessary until `iter` points at a matching statement.
+
+ @return true iff iterator reached end of valid range.
+*/
+static bool
+serd_iter_seek_match(SerdIter* iter, const SerdQuad pat)
+{
+ for (; !zix_btree_iter_is_end(iter->cur);
+ zix_btree_iter_increment(iter->cur)) {
+ const SerdStatement* s = (const SerdStatement*)zix_btree_get(iter->cur);
+ if (serd_statement_matches_quad(s, pat)) {
+ return false; // Found match
+ } else if (iter->mode == FILTER_RANGE &&
+ !serd_iter_pattern_matches(iter, pat)) {
+ zix_btree_iter_free(iter->cur);
+ iter->cur = NULL;
+ return true; // Reached end of range
+ }
+ }
+
+ assert(zix_btree_iter_is_end(iter->cur));
+ return true; // Reached end of index
+}
+
+static bool
+check_version(const SerdIter* const iter)
+{
+ if (iter->version != iter->model->version) {
+ serd_world_errorf(iter->model->world,
+ SERD_ERR_BAD_ITER,
+ "attempt to use invalidated iterator\n");
+ return false;
+ }
+ return true;
+}
+
+SerdIter*
+serd_iter_new(const SerdModel* model,
+ ZixBTreeIter* cur,
+ const SerdQuad pat,
+ SerdOrder order,
+ SearchMode mode,
+ int n_prefix)
+{
+ SerdIter* iter = (SerdIter*)calloc(1, sizeof(SerdIter));
+ iter->model = model;
+ iter->cur = cur;
+ iter->order = order;
+ iter->mode = mode;
+ iter->n_prefix = n_prefix;
+ iter->version = model->version;
+
+ switch (iter->mode) {
+ case ALL:
+ case RANGE:
+ assert(zix_btree_iter_is_end(iter->cur) ||
+ serd_statement_matches_quad(
+ ((const SerdStatement*)zix_btree_get(iter->cur)), pat));
+ break;
+ case FILTER_RANGE:
+ case FILTER_ALL:
+ serd_iter_seek_match(iter, pat);
+ break;
+ }
+
+ // Replace (possibly temporary) nodes in pattern with nodes from the model
+ if (!zix_btree_iter_is_end(iter->cur)) {
+ const SerdStatement* s = (const SerdStatement*)zix_btree_get(iter->cur);
+ for (int i = 0; i < TUP_LEN; ++i) {
+ if (pat[i]) {
+ iter->pat[i] = s->nodes[i];
+ }
+ }
+ }
+
+#ifdef SERD_DEBUG_ITER
+ if (!zix_btree_iter_is_end(iter->cur)) {
+ const SerdStatement* statement = serd_iter_get(iter);
+ SERD_ITER_LOG("New %p pat=" TUP_FMT " realpat=" TUP_FMT
+ " order=%d prefix=%d mode=%d cur=" TUP_FMT "\n",
+ (void*)iter,
+ TUP_FMT_ARGS(pat),
+ TUP_FMT_ARGS(iter->pat),
+ iter->order,
+ iter->n_prefix,
+ iter->mode,
+ TUP_FMT_ARGS(statement->nodes));
+ } else {
+ SERD_ITER_LOG("New %p pat=" TUP_FMT " mode=%d at end\n",
+ (void*)iter,
+ TUP_FMT_ARGS(pat),
+ iter->mode);
+ }
+#endif
+
+ return iter;
+}
+
+SerdIter*
+serd_iter_copy(const SerdIter* iter)
+{
+ if (!iter) {
+ return NULL;
+ }
+
+ SerdIter* copy = (SerdIter*)malloc(sizeof(SerdIter));
+ memcpy(copy, iter, sizeof(SerdIter));
+ copy->cur = zix_btree_iter_copy(iter->cur);
+ return copy;
+}
+
+const SerdStatement*
+serd_iter_get(const SerdIter* iter)
+{
+ return check_version(iter) ? (const SerdStatement*)zix_btree_get(iter->cur)
+ : NULL;
+}
+
+bool
+serd_iter_scan_next(SerdIter* iter)
+{
+ if (zix_btree_iter_is_end(iter->cur)) {
+ return true;
+ }
+
+ switch (iter->mode) {
+ case ALL:
+ // At the end if the cursor is (assigned above)
+ break;
+ case RANGE:
+ SERD_ITER_LOG("%p range next\n", (void*)iter);
+ // At the end if the MSNs no longer match
+ if (!serd_iter_pattern_matches(iter, iter->pat)) {
+ zix_btree_iter_free(iter->cur);
+ iter->cur = NULL;
+ SERD_ITER_LOG("%p reached non-match end\n", (void*)iter);
+ }
+ break;
+ case FILTER_RANGE:
+ case FILTER_ALL:
+ // Seek forward to next match
+ serd_iter_seek_match(iter, iter->pat);
+ break;
+ }
+
+ if (zix_btree_iter_is_end(iter->cur)) {
+ SERD_ITER_LOG("%p reached end\n", (void*)iter);
+ return true;
+ } else {
+#ifdef SERD_DEBUG_ITER
+ SERD_ITER_LOG("%p reached " TUP_FMT "\n",
+ (void*)iter,
+ TUP_FMT_ARGS(serd_iter_get(iter)->nodes));
+#endif
+ return false;
+ }
+}
+
+bool
+serd_iter_next(SerdIter* iter)
+{
+ if (zix_btree_iter_is_end(iter->cur) || !check_version(iter)) {
+ return true;
+ }
+
+ zix_btree_iter_increment(iter->cur);
+ return serd_iter_scan_next(iter);
+}
+
+bool
+serd_iter_equals(const SerdIter* lhs, const SerdIter* rhs)
+{
+ if (!lhs && !rhs) {
+ return true;
+ }
+
+ return (lhs && rhs && lhs->model == rhs->model &&
+ zix_btree_iter_equals(lhs->cur, rhs->cur) &&
+ serd_node_pattern_match(lhs->pat[0], rhs->pat[0]) &&
+ serd_node_pattern_match(lhs->pat[1], rhs->pat[1]) &&
+ serd_node_pattern_match(lhs->pat[2], rhs->pat[2]) &&
+ serd_node_pattern_match(lhs->pat[3], rhs->pat[3]) &&
+ lhs->order == rhs->order && lhs->mode == rhs->mode &&
+ lhs->n_prefix == rhs->n_prefix);
+}
+
+void
+serd_iter_free(SerdIter* iter)
+{
+ if (iter) {
+ zix_btree_iter_free(iter->cur);
+ free(iter);
+ }
+}
generated by cgit v1.2.1 (git 2.18.0) at 2024-04-28 10:03:46 +0000