WIP: Add model

1 files changed, 234 insertions, 0 deletions

diff --git a/src/iter.c b/src/iter.c
new file mode 100644
index 00000000..904f2562
--- /dev/null
+++ b/src/iter.c
@@ -0,0 +1,234 @@
+/*
+  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>
+
+static inline bool
+serd_iter_forward(SerdIter* iter)
+{
+	zix_btree_iter_increment(iter->cur);
+	return zix_btree_iter_is_end(iter->cur);
+}
+
+/**
+   Seek forward as necessary until `iter` points at a match.
+   @return true iff iterator reached end of valid range.
+*/
+static inline bool
+serd_iter_seek_match(SerdIter* iter)
+{
+	for (iter->end = true; !zix_btree_iter_is_end(iter->cur);
+	     serd_iter_forward(iter)) {
+		const SerdStatement* s = (const SerdStatement*)zix_btree_get(iter->cur);
+		if (serd_statement_matches_quad(s, iter->pat)) {
+			return (iter->end = false);
+		}
+	}
+	return true;
+}
+
+/**
+   Seek forward as necessary until `iter` points at a match, or the prefix
+   no longer matches iter->pat.
+   @return true iff iterator reached end of valid range.
+*/
+static inline bool
+serd_iter_seek_match_range(SerdIter* iter)
+{
+	assert(!iter->end);
+
+	do {
+		const SerdStatement* key = (const SerdStatement*)zix_btree_get(iter->cur);
+
+		if (serd_statement_matches_quad(key, iter->pat)) {
+			return false;  // Found match
+		}
+
+		for (int i = 0; i < iter->n_prefix; ++i) {
+			const int idx = orderings[iter->order][i];
+			if (!serd_node_pattern_match(key->nodes[idx], iter->pat[idx])) {
+				iter->end = true;  // Reached end of valid range
+				return true;
+			}
+		}
+	} while (!serd_iter_forward(iter));
+
+	return (iter->end = true);  // Reached end
+}
+
+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*)malloc(sizeof(SerdIter));
+	iter->model       = model;
+	iter->cur         = cur;
+	iter->order       = order;
+	iter->mode        = mode;
+	iter->n_prefix    = n_prefix;
+	iter->version     = model->version;
+	iter->end         = false;
+	for (int i = 0; i < TUP_LEN; ++i) {
+		iter->pat[i] = pat[i];
+	}
+
+	switch (iter->mode) {
+	case ALL:
+	case SINGLE:
+	case RANGE:
+		assert(serd_statement_matches_quad(
+			       ((const SerdStatement*)zix_btree_get(iter->cur)),
+			       iter->pat));
+		break;
+	case FILTER_RANGE: serd_iter_seek_match_range(iter); break;
+	case FILTER_ALL: serd_iter_seek_match(iter); break;
+	}
+
+#ifdef SERD_DEBUG_ITER
+	const SerdStatement* statement = serd_iter_get(iter);
+	SERD_ITER_LOG("New %p pat=" TUP_FMT " cur=" TUP_FMT " end=%d\n",
+	              (void*)iter,
+	              TUP_FMT_ARGS(pat),
+	              TUP_FMT_ARGS(statement->nodes),
+	              iter->end);
+#endif
+
+	return iter;
+}
+
+const SerdModel*
+serd_iter_get_model(const SerdIter* iter)
+{
+	return iter->model;
+}
+
+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 (iter->end) {
+		return true;
+	}
+
+	const SerdStatement* key = NULL;
+	if (!iter->end) {
+		switch (iter->mode) {
+		case ALL:
+			// At the end if the cursor is (assigned above)
+			break;
+		case SINGLE:
+			iter->end = true;
+			SERD_ITER_LOG("%p reached single end\n", (void*)iter);
+			break;
+		case RANGE:
+			SERD_ITER_LOG("%p range next\n", (void*)iter);
+			// At the end if the MSNs no longer match
+			key = (const SerdStatement*)zix_btree_get(iter->cur);
+			assert(key);
+			for (int i = 0; i < iter->n_prefix; ++i) {
+				const int idx = orderings[iter->order][i];
+				if (!serd_node_pattern_match(key->nodes[idx], iter->pat[idx])) {
+					iter->end = true;
+					SERD_ITER_LOG("%p reached non-match end\n", (void*)iter);
+					break;
+				}
+			}
+			break;
+		case FILTER_RANGE:
+			// Seek forward to next match, stopping if prefix changes
+			serd_iter_seek_match_range(iter);
+			break;
+		case FILTER_ALL:
+			// Seek forward to next match
+			serd_iter_seek_match(iter);
+			break;
+		}
+	} else {
+		SERD_ITER_LOG("%p reached index end\n", (void*)iter);
+	}
+
+	if (iter->end) {
+		SERD_ITER_LOG("%p Reached end\n", (void*)iter);
+		return true;
+	} else {
+#ifdef SERD_DEBUG_ITER
+		SERD_ITER_LOG("%p Increment to " TUP_FMT "\n",
+		              (void*)iter,
+		              TUP_FMT_ARGS(serd_iter_get(iter)->nodes));
+#endif
+		return false;
+	}
+}
+
+bool
+serd_iter_next(SerdIter* iter)
+{
+	if (iter->end || !check_version(iter)) {
+		return true;
+	}
+
+	iter->end = serd_iter_forward(iter);
+	return serd_iter_scan_next(iter);
+}
+
+bool
+serd_iter_end(const SerdIter* iter)
+{
+	return !iter || iter->end;
+}
+
+void
+serd_iter_free(SerdIter* iter)
+{
+	SERD_ITER_LOG("%p Free\n", (void*)iter);
+	if (iter) {
+		zix_btree_iter_free(iter->cur);
+		free(iter);
+	}
+}