aboutsummaryrefslogtreecommitdiffstats
path: root/src/iter.c
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-05-12 13:28:47 +0200
committerDavid Robillard <d@drobilla.net>2021-03-08 23:34:52 -0500
commit677d85c7f3df3563e990f41964f6ae7d560567a0 (patch)
tree9b5113cb7c2b2cc7ae8a07ab5a21e5a55d579559 /src/iter.c
parent15485f61df8cbd922907db39fcc864abb002eea3 (diff)
downloadserd-677d85c7f3df3563e990f41964f6ae7d560567a0.tar.gz
serd-677d85c7f3df3563e990f41964f6ae7d560567a0.tar.bz2
serd-677d85c7f3df3563e990f41964f6ae7d560567a0.zip
Add model
Diffstat (limited to 'src/iter.c')
-rw-r--r--src/iter.c211
1 files changed, 211 insertions, 0 deletions
diff --git a/src/iter.c b/src/iter.c
new file mode 100644
index 00000000..62c3ef4f
--- /dev/null
+++ b/src/iter.c
@@ -0,0 +1,211 @@
+/*
+ Copyright 2011-2020 David Robillard <d@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 "model.h"
+#include "node.h"
+#include "world.h"
+
+#include "serd/serd.h"
+#include "zix/btree.h"
+
+#include <assert.h>
+#include <stdbool.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
+ }
+
+ 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 || iter->version != iter->model->version) {
+ SERD_LOG_ERROR(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];
+ }
+ }
+ }
+
+ 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) && !zix_btree_iter_is_end(iter->cur))
+ ? (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;
+ }
+
+ bool is_end = false;
+ switch (iter->mode) {
+ case ALL:
+ // At the end if the cursor is (assigned above)
+ break;
+ case RANGE:
+ // 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;
+ is_end = true;
+ }
+ break;
+ case FILTER_RANGE:
+ case FILTER_ALL:
+ // Seek forward to next match
+ is_end = serd_iter_seek_match(iter, iter->pat);
+ break;
+ }
+
+ return is_end;
+}
+
+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);
+ }
+}