From 2be5c4870ebc6dc3f0562dcf53eda3c946981a1c Mon Sep 17 00:00:00 2001
From: David Robillard <d@drobilla.net>
Date: Sat, 12 May 2018 13:28:47 +0200
Subject: Add model
---
src/inserter.c | 117 ++++++++++
src/iter.c | 210 ++++++++++++++++++
src/iter.h | 89 ++++++++
src/model.c | 651 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
src/model.h | 42 ++++
src/node.h | 13 ++
src/range.c | 316 +++++++++++++++++++++++++++
src/range.h | 35 +++
src/serdi.c | 41 +++-
src/statement.c | 79 +++++++
src/statement.h | 6 +
src/string.c | 1 +
12 files changed, 1598 insertions(+), 2 deletions(-)
create mode 100644 src/inserter.c
create mode 100644 src/iter.c
create mode 100644 src/iter.h
create mode 100644 src/model.c
create mode 100644 src/model.h
create mode 100644 src/range.c
create mode 100644 src/range.h
(limited to 'src')
diff --git a/src/inserter.c b/src/inserter.c
new file mode 100644
index 00000000..e2f95896
--- /dev/null
+++ b/src/inserter.c
@@ -0,0 +1,117 @@
+/*
+ Copyright 2011-2020 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 "model.h"
+#include "statement.h"
+#include "world.h"
+
+#include "serd/serd.h"
+
+#include <stdlib.h>
+
+typedef struct {
+ SerdEnv* env;
+ SerdModel* model;
+ SerdNode* default_graph;
+} SerdInserterData;
+
+static const SerdNode*
+manage_or_intern(SerdNodes* nodes, SerdNode* manage, const SerdNode* intern)
+{
+ return manage ? serd_nodes_manage(nodes, manage)
+ : serd_nodes_intern(nodes, intern);
+}
+
+static SerdStatus
+serd_inserter_on_base(SerdInserterData* data, const SerdNode* uri)
+{
+ return serd_env_set_base_uri(data->env, uri);
+}
+
+static SerdStatus
+serd_inserter_on_prefix(SerdInserterData* data,
+ const SerdNode* name,
+ const SerdNode* uri)
+{
+ return serd_env_set_prefix(data->env, name, uri);
+}
+
+static SerdStatus
+serd_inserter_on_statement(SerdInserterData* data,
+ const SerdStatementFlags flags,
+ const SerdStatement* statement)
+{
+ (void)flags;
+
+ const SerdNode* const subject = serd_statement_subject(statement);
+ const SerdNode* const predicate = serd_statement_predicate(statement);
+ const SerdNode* const object = serd_statement_object(statement);
+ const SerdNode* const graph = serd_statement_graph(statement);
+
+ // Attempt to expand all nodes to eliminate CURIEs
+ SerdNode* const s = serd_env_expand(data->env, subject);
+ SerdNode* const p = serd_env_expand(data->env, predicate);
+ SerdNode* const o = serd_env_expand(data->env, object);
+ SerdNode* const g = serd_env_expand(data->env, graph);
+
+ SerdNodes* const nodes = data->model->world->nodes;
+ const SerdNode* model_graph = manage_or_intern(nodes, g, graph);
+ if (!model_graph) {
+ model_graph = serd_nodes_intern(nodes, data->default_graph);
+ }
+
+ const SerdStatus st = serd_model_add_internal(
+ data->model,
+ (data->model->flags & SERD_STORE_CURSORS) ? statement->cursor
+ : NULL,
+ manage_or_intern(nodes, s, subject),
+ manage_or_intern(nodes, p, predicate),
+ manage_or_intern(nodes, o, object),
+ model_graph);
+
+ return st > SERD_FAILURE ? st : SERD_SUCCESS;
+}
+
+static void
+free_data(void* handle)
+{
+ if (handle) {
+ SerdInserterData* data = (SerdInserterData*)handle;
+
+ serd_node_free(data->default_graph);
+ free(data);
+ }
+}
+
+SerdSink*
+serd_inserter_new(SerdModel* model, SerdEnv* env, const SerdNode* default_graph)
+{
+ SerdInserterData* const data =
+ (SerdInserterData*)calloc(1, sizeof(SerdInserterData));
+
+ data->env = env;
+ data->model = model;
+ data->default_graph = serd_node_copy(default_graph);
+
+ SerdSink* const sink = serd_sink_new(data, free_data);
+
+ serd_sink_set_base_func(sink, (SerdBaseFunc)serd_inserter_on_base);
+ serd_sink_set_prefix_func(sink, (SerdPrefixFunc)serd_inserter_on_prefix);
+ serd_sink_set_statement_func(sink,
+ (SerdStatementFunc)serd_inserter_on_statement);
+
+ return sink;
+}
diff --git a/src/iter.c b/src/iter.c
new file mode 100644
index 00000000..8fa063cd
--- /dev/null
+++ b/src/iter.c
@@ -0,0 +1,210 @@
+/*
+ Copyright 2011-2020 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 "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
+ } 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_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);
+ }
+}
diff --git a/src/iter.h b/src/iter.h
new file mode 100644
index 00000000..a2326dc1
--- /dev/null
+++ b/src/iter.h
@@ -0,0 +1,89 @@
+/*
+ Copyright 2011-2020 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.
+*/
+
+#ifndef SERD_ITER_H
+#define SERD_ITER_H
+
+#include "statement.h"
+
+#include "serd/serd.h"
+#include "zix/btree.h"
+
+#include <stdbool.h>
+#include <stdint.h>
+
+/** Triple ordering */
+typedef enum {
+ SPO, ///< Subject, Predicate, Object
+ SOP, ///< Subject, Object, Predicate
+ OPS, ///< Object, Predicate, Subject
+ OSP, ///< Object, Subject, Predicate
+ PSO, ///< Predicate, Subject, Object
+ POS, ///< Predicate, Object, Subject
+ GSPO, ///< Graph, Subject, Predicate, Object
+ GSOP, ///< Graph, Subject, Object, Predicate
+ GOPS, ///< Graph, Object, Predicate, Subject
+ GOSP, ///< Graph, Object, Subject, Predicate
+ GPSO, ///< Graph, Predicate, Subject, Object
+ GPOS ///< Graph, Predicate, Object, Subject
+} SerdOrder;
+
+/** Mode for searching or iteration */
+typedef enum {
+ ALL, ///< Iterate over entire store
+ RANGE, ///< Iterate over range with equal prefix
+ FILTER_RANGE, ///< Iterate over range with equal prefix, filtering
+ FILTER_ALL ///< Iterate to end of store, filtering
+} SearchMode;
+
+struct SerdIterImpl {
+ const SerdModel* model; ///< Model being iterated over
+ uint64_t version; ///< Model version when iterator was created
+ ZixBTreeIter* cur; ///< Current DB cursor
+ SerdQuad pat; ///< Pattern (in ordering order)
+ SerdOrder order; ///< Store order (which index)
+ SearchMode mode; ///< Iteration mode
+ int n_prefix; ///< Prefix for RANGE and FILTER_RANGE
+};
+
+#define NUM_ORDERS 12
+#define TUP_LEN 4
+
+/**
+ Quads of indices for each order, from most to least significant
+ (array indexed by SordOrder)
+*/
+static const int orderings[NUM_ORDERS][TUP_LEN] = {
+ { 0, 1, 2, 3 }, { 0, 2, 1, 3 }, // SPO, SOP
+ { 2, 1, 0, 3 }, { 2, 0, 1, 3 }, // OPS, OSP
+ { 1, 0, 2, 3 }, { 1, 2, 0, 3 }, // PSO, POS
+ { 3, 0, 1, 2 }, { 3, 0, 2, 1 }, // GSPO, GSOP
+ { 3, 2, 1, 0 }, { 3, 2, 0, 1 }, // GOPS, GOSP
+ { 3, 1, 0, 2 }, { 3, 1, 2, 0 } // GPSO, GPOS
+};
+
+SerdIter* serd_iter_new(const SerdModel* model,
+ ZixBTreeIter* cur,
+ const SerdQuad pat,
+ SerdOrder order,
+ SearchMode mode,
+ int n_prefix);
+
+bool serd_iter_scan_next(SerdIter* iter);
+
+bool serd_quad_match(const SerdQuad x, const SerdQuad y);
+
+#endif // SERD_ITER_H
diff --git a/src/model.c b/src/model.c
new file mode 100644
index 00000000..cdd44ac1
--- /dev/null
+++ b/src/model.c
@@ -0,0 +1,651 @@
+/*
+ Copyright 2011-2020 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 "model.h"
+
+#include "cursor.h"
+#include "iter.h"
+#include "node.h"
+#include "range.h"
+#include "statement.h"
+#include "world.h"
+
+#include "zix/btree.h"
+#include "zix/common.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdlib.h>
+
+#define DEFAULT_ORDER SPO
+#define DEFAULT_GRAPH_ORDER GSPO
+
+/**
+ Compare quads lexicographically, ignoring graph.
+
+ NULL IDs (equal to 0) are treated as wildcards, always less than every
+ other possible ID, except itself.
+*/
+static int
+serd_triple_compare(const void* x, const void* y, void* user_data)
+{
+ const int* const ordering = (const int*)user_data;
+ const SerdStatement* const s = (const SerdStatement*)x;
+ const SerdStatement* const t = (const SerdStatement*)y;
+
+ for (int i = 0; i < TUP_LEN; ++i) {
+ const int o = ordering[i];
+ if (o != SERD_GRAPH) {
+ const int c = serd_node_wildcard_compare(s->nodes[o], t->nodes[o]);
+ if (c) {
+ return c;
+ }
+ }
+ }
+
+ return 0;
+}
+
+/**
+ Compare quads lexicographically, with exact (non-wildcard) graph matching.
+*/
+static int
+serd_quad_compare(const void* x, const void* y, void* user_data)
+{
+ const SerdStatement* const s = (const SerdStatement*)x;
+ const SerdStatement* const t = (const SerdStatement*)y;
+
+ // Compare graph without wildcard matching
+ const int cmp = serd_node_compare(
+ s->nodes[SERD_GRAPH], t->nodes[SERD_GRAPH]);
+
+ return cmp ? cmp : serd_triple_compare(x, y, user_data);
+}
+
+/**
+ Return true iff `serd` has an index for `order`.
+ If `graphs` is true, `order` will be modified to be the
+ corresponding order with a G prepended (so G will be the MSN).
+*/
+static inline bool
+serd_model_has_index(const SerdModel* model,
+ SerdOrder* order,
+ int* n_prefix,
+ bool graphs)
+{
+ if (graphs) {
+ *order = (SerdOrder)(*order + GSPO);
+ *n_prefix += 1;
+ }
+
+ return model->indices[*order];
+}
+
+/**
+ Return the best available index for a pattern.
+ @param pat Pattern in standard (S P O G) order
+ @param mode Set to the (best) iteration mode for iterating over results
+ @param n_prefix Set to the length of the range prefix
+ (for `mode` == RANGE and `mode` == FILTER_RANGE)
+*/
+static SerdOrder
+serd_model_best_index(const SerdModel* model,
+ const SerdQuad pat,
+ SearchMode* mode,
+ int* n_prefix)
+{
+ const bool graph_search = (pat[SERD_GRAPH] != 0);
+
+ const unsigned sig = ((pat[0] ? 1 : 0) * 0x100 +
+ (pat[1] ? 1 : 0) * 0x010 +
+ (pat[2] ? 1 : 0) * 0x001);
+
+ SerdOrder good[2] = { (SerdOrder)-1, (SerdOrder)-1 };
+
+#define PAT_CASE(sig, m, g0, g1, np) \
+ case sig: \
+ *mode = m; \
+ good[0] = g0; \
+ good[1] = g1; \
+ *n_prefix = np; \
+ break
+
+ // Good orderings that don't require filtering
+ *mode = RANGE;
+ *n_prefix = 0;
+ switch (sig) {
+ case 0x000:
+ assert(graph_search);
+ *mode = RANGE;
+ *n_prefix = 1;
+ return DEFAULT_GRAPH_ORDER;
+ case 0x111:
+ *mode = RANGE;
+ *n_prefix = graph_search ? 4 : 3;
+ return graph_search ? DEFAULT_GRAPH_ORDER : DEFAULT_ORDER;
+
+ PAT_CASE(0x001, RANGE, OPS, OSP, 1);
+ PAT_CASE(0x010, RANGE, POS, PSO, 1);
+ PAT_CASE(0x011, RANGE, OPS, POS, 2);
+ PAT_CASE(0x100, RANGE, SPO, SOP, 1);
+ PAT_CASE(0x101, RANGE, SOP, OSP, 2);
+ PAT_CASE(0x110, RANGE, SPO, PSO, 2);
+ default:
+ break;
+ }
+
+ if (*mode == RANGE) {
+ if (serd_model_has_index(model, &good[0], n_prefix, graph_search)) {
+ return good[0];
+ } else if (serd_model_has_index(
+ model, &good[1], n_prefix, graph_search)) {
+ return good[1];
+ }
+ }
+
+ // Not so good orderings that require filtering, but can
+ // still be constrained to a range
+ switch (sig) {
+ PAT_CASE(0x011, FILTER_RANGE, OSP, PSO, 1);
+ PAT_CASE(0x101, FILTER_RANGE, SPO, OPS, 1);
+ // SPO is always present, so 0x110 is never reached here
+ default: break;
+ }
+
+ if (*mode == FILTER_RANGE) {
+ if (serd_model_has_index(model, &good[0], n_prefix, graph_search)) {
+ return good[0];
+ } else if (serd_model_has_index(
+ model, &good[1], n_prefix, graph_search)) {
+ return good[1];
+ }
+ }
+
+ if (graph_search) {
+ *mode = FILTER_RANGE;
+ *n_prefix = 1;
+ return DEFAULT_GRAPH_ORDER;
+ } else {
+ *mode = FILTER_ALL;
+ return DEFAULT_ORDER;
+ }
+}
+
+SerdModel*
+serd_model_new(SerdWorld* world, SerdModelFlags flags)
+{
+ SerdModel* model = (SerdModel*)calloc(1, sizeof(struct SerdModelImpl));
+
+ flags |= SERD_INDEX_SPO; // SPO index is mandatory
+
+ model->world = world;
+ model->flags = flags;
+
+ for (unsigned i = 0; i < (NUM_ORDERS / 2); ++i) {
+ const int* const ordering = orderings[i];
+ const int* const g_ordering = orderings[i + (NUM_ORDERS / 2)];
+
+ if (flags & (1u << i)) {
+ model->indices[i] =
+ zix_btree_new((ZixComparator)serd_triple_compare,
+ (const void*)ordering,
+ NULL);
+ if (flags & SERD_INDEX_GRAPHS) {
+ model->indices[i + (NUM_ORDERS / 2)] =
+ zix_btree_new((ZixComparator)serd_quad_compare,
+ (const void*)g_ordering,
+ NULL);
+ }
+ }
+ }
+
+ // Create end iterator
+ const SerdOrder order = model->indices[GSPO] ? GSPO : SPO;
+ ZixBTreeIter* cur = zix_btree_end(model->indices[order]);
+ const SerdQuad pat = { 0, 0, 0, 0 };
+
+ model->end = serd_iter_new(model, cur, pat, order, ALL, 0);
+
+ return model;
+}
+
+SerdModel*
+serd_model_copy(const SerdModel* model)
+{
+ if (!model) {
+ return NULL;
+ }
+
+ SerdModel* copy = serd_model_new(model->world, model->flags);
+
+ SerdRange* all = serd_model_all(model);
+ serd_model_add_range(copy, all);
+ serd_range_free(all);
+
+ assert(serd_model_size(model) == serd_model_size(copy));
+ return copy;
+}
+
+SERD_API
+bool
+serd_model_equals(const SerdModel* a, const SerdModel* b)
+{
+ if (!a && !b) {
+ return true;
+ } else if (!a || !b || serd_model_size(a) != serd_model_size(b)) {
+ return false;
+ }
+
+ SerdRange* ra = serd_model_all(a);
+ SerdRange* rb = serd_model_all(b);
+
+ bool result = true;
+ while (!serd_range_empty(ra) && !serd_range_empty(rb)) {
+ if (!serd_statement_equals(serd_range_front(ra),
+ serd_range_front(rb))) {
+ result = false;
+ break;
+ }
+
+ serd_range_next(ra);
+ serd_range_next(rb);
+ }
+
+ result = result && serd_range_empty(ra) && serd_range_empty(rb);
+
+ serd_range_free(ra);
+ serd_range_free(rb);
+ return result;
+}
+
+static void
+serd_model_drop_statement(SerdModel* model, SerdStatement* statement)
+
+{
+ for (int i = 0; i < TUP_LEN; ++i) {
+ if (statement->nodes[i]) {
+ serd_nodes_deref(model->world->nodes, statement->nodes[i]);
+ }
+ }
+
+ if (statement->cursor && statement->cursor->file) {
+ serd_nodes_deref(model->world->nodes, statement->cursor->file);
+ }
+
+ serd_statement_free(statement);
+}
+
+void
+serd_model_free(SerdModel* model)
+{
+ if (!model) {
+ return;
+ }
+
+ serd_iter_free(model->end);
+
+ ZixBTree* index = model->indices[model->indices[DEFAULT_GRAPH_ORDER]
+ ? DEFAULT_GRAPH_ORDER
+ : DEFAULT_ORDER];
+
+ // Free statements
+ ZixBTreeIter* t = zix_btree_begin(index);
+ for (; !zix_btree_iter_is_end(t); zix_btree_iter_increment(t)) {
+ serd_model_drop_statement(model, (SerdStatement*)zix_btree_get(t));
+ }
+ zix_btree_iter_free(t);
+
+ // Free indices
+ for (unsigned o = 0; o < NUM_ORDERS; ++o) {
+ if (model->indices[o]) {
+ zix_btree_free(model->indices[o]);
+ }
+ }
+
+ free(model);
+}
+
+SerdWorld*
+serd_model_world(SerdModel* model)
+{
+ return model->world;
+}
+
+SerdModelFlags
+serd_model_flags(const SerdModel* model)
+{
+ return model->flags;
+}
+
+size_t
+serd_model_size(const SerdModel* model)
+{
+ const SerdOrder order = model->indices[GSPO] ? GSPO : SPO;
+ return zix_btree_size(model->indices[order]);
+}
+
+bool
+serd_model_empty(const SerdModel* model)
+{
+ return serd_model_size(model) == 0;
+}
+
+SerdIter*
+serd_model_begin(const SerdModel* model)
+{
+ if (serd_model_size(model) == 0) {
+ return serd_iter_copy(serd_model_end(model));
+ } else {
+ const SerdOrder order = model->indices[GSPO] ? GSPO : SPO;
+ ZixBTreeIter* cur = zix_btree_begin(model->indices[order]);
+ const SerdQuad pat = { 0, 0, 0, 0 };
+ return serd_iter_new(model, cur, pat, order, ALL, 0);
+ }
+}
+
+const SerdIter*
+serd_model_end(const SerdModel* model)
+{
+ return model->end;
+}
+
+SerdRange*
+serd_model_all(const SerdModel* model)
+{
+ return serd_range_new(serd_model_begin(model),
+ serd_iter_copy(serd_model_end(model)));
+}
+
+SerdIter*
+serd_model_find(const SerdModel* model,
+ const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g)
+{
+ const SerdQuad pat = { s, p, o, g };
+ if (!pat[0] && !pat[1] && !pat[2] && !pat[3]) {
+ return serd_model_begin(model);
+ }
+
+ SearchMode mode = ALL;
+ int n_prefix = 0;
+ const SerdOrder index_order =
+ serd_model_best_index(model, pat, &mode, &n_prefix);
+
+ ZixBTree* const db = model->indices[index_order];
+ ZixBTreeIter* cur = NULL;
+
+ 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. */
+ SerdQuad 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)) {
+ zix_btree_iter_free(cur);
+ return NULL;
+ }
+
+ const SerdStatement* const key = (const SerdStatement*)zix_btree_get(cur);
+ if (!key || (mode == RANGE && !serd_statement_matches_quad(key, pat))) {
+ zix_btree_iter_free(cur);
+ return NULL;
+ }
+
+ return serd_iter_new(model, cur, pat, index_order, mode, n_prefix);
+}
+
+SerdRange*
+serd_model_range(const SerdModel* model,
+ const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g)
+{
+ if (!s && !p && !o && !g) {
+ return serd_range_new(serd_model_begin(model),
+ serd_iter_copy(serd_model_end(model)));
+ }
+
+ SerdIter* begin = serd_model_find(model, s, p, o, g);
+ SerdIter* end = begin ? serd_iter_new(model,
+ NULL,
+ begin->pat,
+ begin->order,
+ begin->mode,
+ begin->n_prefix)
+ : NULL;
+ return serd_range_new(begin, end);
+}
+
+const SerdNode*
+serd_model_get(const SerdModel* model,
+ const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g)
+{
+ const SerdStatement* statement =
+ serd_model_get_statement(model, s, p, o, g);
+
+ if (statement) {
+ if (!s) {
+ return serd_statement_subject(statement);
+ } else if (!p) {
+ return serd_statement_predicate(statement);
+ } else if (!o) {
+ return serd_statement_object(statement);
+ } else if (!g) {
+ return serd_statement_graph(statement);
+ }
+ }
+
+ return NULL;
+}
+
+const SerdStatement*
+serd_model_get_statement(const SerdModel* model,
+ const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g)
+{
+ if ((bool)s + (bool)p + (bool)o != 2 &&
+ (bool)s + (bool)p + (bool)o + (bool)g != 3) {
+ return NULL;
+ }
+
+ SerdIter* const i = serd_model_find(model, s, p, o, g);
+ if (i && i->cur) {
+ const SerdStatement* statement = serd_iter_get(i);
+ serd_iter_free(i);
+ return statement;
+ }
+
+ return NULL;
+}
+
+size_t
+serd_model_count(const SerdModel* model,
+ const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g)
+{
+ SerdRange* const range = serd_model_range(model, s, p, o, g);
+ size_t count = 0;
+
+ for (; !serd_range_empty(range); serd_range_next(range)) {
+ ++count;
+ }
+
+ serd_range_free(range);
+ return count;
+}
+
+bool
+serd_model_ask(const SerdModel* model,
+ const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g)
+{
+ SerdIter* iter = serd_model_find(model, s, p, o, g);
+ const bool ret = iter && !zix_btree_iter_is_end(iter->cur);
+ serd_iter_free(iter);
+ return ret;
+}
+
+static SerdCursor*
+serd_model_intern_cursor(SerdModel* model, const SerdCursor* cursor)
+{
+ if (cursor) {
+ SerdCursor* copy = (SerdCursor*)calloc(1, sizeof(SerdCursor));
+
+ copy->file = serd_nodes_intern(model->world->nodes, cursor->file);
+ copy->line = cursor->line;
+ copy->col = cursor->col;
+ return copy;
+ }
+
+ return NULL;
+}
+
+SerdStatus
+serd_model_add_internal(SerdModel* model,
+ const SerdCursor* cursor,
+ const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g)
+{
+ SerdStatement* statement = (SerdStatement*)calloc(1, sizeof(SerdStatement));
+
+ statement->nodes[0] = s;
+ statement->nodes[1] = p;
+ statement->nodes[2] = o;
+ statement->nodes[3] = g;
+ statement->cursor = serd_model_intern_cursor(model, cursor);
+
+ bool added = false;
+ for (unsigned i = 0; i < NUM_ORDERS; ++i) {
+ if (model->indices[i]) {
+ if (!zix_btree_insert(model->indices[i], statement)) {
+ added = true;
+ } else if (i == GSPO) {
+ break; // Statement already indexed
+ }
+ }
+ }
+
+ ++model->version;
+ if (added) {
+ return SERD_SUCCESS;
+ }
+
+ serd_model_drop_statement(model, statement);
+ return SERD_FAILURE;
+}
+
+SerdStatus
+serd_model_add(SerdModel* model,
+ const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g)
+{
+ if (!s || !p || !o) {
+ return SERD_LOG_ERROR(model->world,
+ SERD_ERR_BAD_ARG,
+ "attempt to add statement with NULL field\n");
+ }
+
+ return serd_model_add_internal(model,
+ NULL,
+ serd_nodes_intern(model->world->nodes, s),
+ serd_nodes_intern(model->world->nodes, p),
+ serd_nodes_intern(model->world->nodes, o),
+ serd_nodes_intern(model->world->nodes, g));
+}
+
+SerdStatus
+serd_model_insert(SerdModel* model, const SerdStatement* statement)
+{
+ SerdNodes* nodes = model->world->nodes;
+ return serd_model_add_internal(
+ model,
+ serd_statement_cursor(statement),
+ serd_nodes_intern(nodes, serd_statement_subject(statement)),
+ serd_nodes_intern(nodes, serd_statement_predicate(statement)),
+ serd_nodes_intern(nodes, serd_statement_object(statement)),
+ serd_nodes_intern(nodes, serd_statement_graph(statement)));
+}
+
+SerdStatus
+serd_model_add_range(SerdModel* model, SerdRange* range)
+{
+ SerdStatus st = SERD_SUCCESS;
+ for (; !st && !serd_range_empty(range); serd_range_next(range)) {
+ st = serd_model_insert(model, serd_range_front(range));
+ }
+
+ return st;
+}
+
+SerdStatus
+serd_model_erase(SerdModel* model, SerdIter* iter)
+{
+ const SerdStatement* statement = serd_iter_get(iter);
+
+ SerdStatement* removed = NULL;
+ for (int i = SPO; i <= GPOS; ++i) {
+ if (model->indices[i]) {
+ zix_btree_remove(model->indices[i],
+ statement,
+ (void**)&removed,
+ i == (int)iter->order ? &iter->cur : NULL);
+ }
+ }
+ serd_iter_scan_next(iter);
+
+ serd_model_drop_statement(model, removed);
+ iter->version = ++model->version;
+
+ return SERD_SUCCESS;
+}
+
+SerdStatus
+serd_model_erase_range(SerdModel* model, SerdRange* range)
+{
+ while (!serd_range_empty(range)) {
+ serd_model_erase(model, range->begin);
+ }
+
+ return SERD_SUCCESS;
+}
diff --git a/src/model.h b/src/model.h
new file mode 100644
index 00000000..6290147e
--- /dev/null
+++ b/src/model.h
@@ -0,0 +1,42 @@
+/*
+ Copyright 2011-2020 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.
+*/
+
+#ifndef SERD_MODEL_H
+#define SERD_MODEL_H
+
+#include "serd/serd.h"
+#include "zix/btree.h"
+
+#include <stdint.h>
+
+struct SerdModelImpl
+{
+ SerdWorld* world; ///< World this model is a part of
+ ZixBTree* indices[12]; ///< Trees of SordQuad
+ SerdIter* end; ///< End iterator (always the same)
+ uint64_t version; ///< Version incremented on every change
+ SerdModelFlags flags; ///< Active indices and features
+};
+
+SerdStatus
+serd_model_add_internal(SerdModel* model,
+ const SerdCursor* cursor,
+ const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g);
+
+#endif // SERD_MODEL_H
diff --git a/src/node.h b/src/node.h
index 3f8ec628..db5d25e2 100644
--- a/src/node.h
+++ b/src/node.h
@@ -19,6 +19,7 @@
#include "serd/serd.h"
+#include <stdbool.h>
#include <stddef.h>
struct SerdNodeImpl {
@@ -39,6 +40,18 @@ serd_node_buffer_c(const SerdNode* node)
return (const char*)(node + 1);
}
+static inline int
+serd_node_wildcard_compare(const SerdNode* a, const SerdNode* b)
+{
+ return (!a || !b) ? 0 : serd_node_compare(a, b);
+}
+
+static inline bool
+serd_node_pattern_match(const SerdNode* a, const SerdNode* b)
+{
+ return !a || !b || serd_node_equals(a, b);
+}
+
SerdNode*
serd_node_malloc(size_t n_bytes, SerdNodeFlags flags, SerdNodeType type);
diff --git a/src/range.c b/src/range.c
new file mode 100644
index 00000000..8e0dc12d
--- /dev/null
+++ b/src/range.c
@@ -0,0 +1,316 @@
+/*
+ Copyright 2011-2020 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 "range.h"
+
+#include "iter.h"
+#include "model.h"
+#include "world.h"
+
+#include "zix/common.h"
+#include "zix/digest.h"
+#include "zix/hash.h"
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef enum { NAMED, ANON_S, ANON_O, LIST_S, LIST_O } NodeStyle;
+
+static SerdStatus
+write_range_statement(const SerdSink* sink,
+ const SerdModel* model,
+ ZixHash* list_subjects,
+ unsigned depth,
+ SerdStatementFlags flags,
+ const SerdStatement* statement);
+
+SerdRange*
+serd_range_new(SerdIter* const begin, SerdIter* const end)
+{
+ SerdRange* range = (SerdRange*)malloc(sizeof(SerdRange));
+
+ range->begin = begin;
+ range->end = end;
+
+ return range;
+}
+
+SerdRange*
+serd_range_copy(const SerdRange* range)
+{
+ SerdRange* copy = (SerdRange*)malloc(sizeof(SerdRange));
+
+ memcpy(copy, range, sizeof(SerdRange));
+ copy->begin = serd_iter_copy(range->begin);
+ copy->end = serd_iter_copy(range->end);
+
+ return copy;
+}
+
+void
+serd_range_free(SerdRange* range)
+{
+ if (range) {
+ serd_iter_free(range->begin);
+ serd_iter_free(range->end);
+ free(range);
+ }
+}
+
+const SerdStatement*
+serd_range_front(const SerdRange* range)
+{
+ return serd_iter_get(range->begin);
+}
+
+bool
+serd_range_equals(const SerdRange* lhs, const SerdRange* rhs)
+{
+ return (!lhs && !rhs) ||
+ (lhs && rhs && serd_iter_equals(lhs->begin, rhs->begin) &&
+ serd_iter_equals(lhs->end, rhs->end));
+}
+
+bool
+serd_range_next(SerdRange* range)
+{
+ return serd_iter_next(range->begin);
+}
+
+bool
+serd_range_empty(const SerdRange* range)
+{
+ return !range || serd_iter_equals(range->begin, range->end);
+}
+
+const SerdIter*
+serd_range_cbegin(const SerdRange* range)
+{
+ return range->begin;
+}
+
+const SerdIter*
+serd_range_cend(const SerdRange* range)
+{
+ return range->end;
+}
+
+SerdIter*
+serd_range_begin(SerdRange* range)
+{
+ return range->begin;
+}
+
+SerdIter*
+serd_range_end(SerdRange* range)
+{
+ return range->end;
+}
+
+static NodeStyle
+get_node_style(const SerdModel* model, const SerdNode* node)
+{
+ if (serd_node_type(node) != SERD_BLANK) {
+ return NAMED; // Non-blank node can't be anonymous
+ }
+
+ size_t n_as_object = 0;
+ SerdRange* range = serd_model_range(model, NULL, NULL, node, NULL);
+ for (; !serd_range_empty(range); serd_range_next(range), ++n_as_object) {
+ if (n_as_object == 1) {
+ serd_range_free(range);
+ return NAMED; // Blank node referred to several times
+ }
+ }
+
+ serd_range_free(range);
+
+ if (serd_model_ask(model, node, model->world->rdf_first, NULL, NULL) &&
+ serd_model_ask(model, node, model->world->rdf_rest, NULL, NULL)) {
+ return n_as_object == 0 ? LIST_S : LIST_O;
+ }
+
+ return n_as_object == 0 ? ANON_S : ANON_O;
+}
+
+static uint32_t
+ptr_hash(const void* ptr)
+{
+ return zix_digest_add_ptr(zix_digest_start(), ptr);
+}
+
+static bool
+ptr_equals(const void* a, const void* b)
+{
+ return *(const void* const*)a == *(const void* const*)b;
+}
+
+static SerdStatus
+write_pretty_range(const SerdSink* sink,
+ const unsigned depth,
+ const SerdStatementFlags flags,
+ const SerdModel* model,
+ SerdRange* range)
+{
+ (void)flags;
+
+ ZixHash* list_subjects = zix_hash_new(ptr_hash, ptr_equals, sizeof(void*));
+
+ SerdStatus st = SERD_SUCCESS;
+ for (; !st && !serd_range_empty(range); serd_range_next(range)) {
+ st = write_range_statement(
+ sink, model, list_subjects, depth, 0, serd_range_front(range));
+ }
+
+ zix_hash_free(list_subjects);
+
+ return st;
+}
+
+static SerdStatus
+write_list(const SerdSink* sink,
+ const SerdModel* model,
+ ZixHash* list_subjects,
+ const unsigned depth,
+ SerdStatementFlags flags,
+ const SerdNode* object)
+{
+ SerdStatus st = SERD_SUCCESS;
+ const SerdWorld* world = model->world;
+ const SerdNode* first = world->rdf_first;
+ const SerdNode* rest = world->rdf_rest;
+ const SerdNode* nil = world->rdf_nil;
+
+ SerdIter* f = serd_model_find(model, object, first, NULL, NULL);
+ while (!st && f && !serd_node_equals(object, nil)) {
+ const SerdStatement* fs = serd_iter_get(f);
+
+ st = write_range_statement(
+ sink, model, list_subjects, depth + 1, flags, fs);
+
+ serd_iter_free(f);
+ f = NULL;
+ flags = 0;
+ if (st) {
+ break;
+ }
+
+ SerdIter* const r = serd_model_find(model, object, rest, NULL, NULL);
+ const SerdNode* next =
+ r ? serd_statement_object(serd_iter_get(r)) : NULL;
+
+ f = next ? serd_model_find(model, next, first, NULL, NULL) : NULL;
+ if (r && f) {
+ // This and next node are good, write rdf:next statement
+ st = serd_sink_write_statement(sink, 0, serd_iter_get(r));
+ object = next;
+ } else {
+ // Terminate malformed list
+ st = serd_sink_write(
+ sink, 0, object, rest, nil, serd_statement_graph(fs));
+ f = NULL;
+ }
+
+ serd_iter_free(r);
+ }
+
+ serd_iter_free(f);
+ return st;
+}
+
+static SerdStatus
+write_range_statement(const SerdSink* sink,
+ const SerdModel* model,
+ ZixHash* list_subjects,
+ const unsigned depth,
+ SerdStatementFlags flags,
+ const SerdStatement* statement)
+{
+ const SerdNode* subject = serd_statement_subject(statement);
+ const NodeStyle subject_style = get_node_style(model, subject);
+
+ if (depth == 0 && (subject_style == ANON_O || subject_style == LIST_O)) {
+ return SERD_SUCCESS; // Skip subject that will be inlined somewhere
+ } else if (subject_style == LIST_S && depth == 0 &&
+ (serd_node_equals(serd_statement_predicate(statement),
+ model->world->rdf_first) ||
+ (serd_node_equals(serd_statement_predicate(statement),
+ model->world->rdf_rest)))) {
+ return SERD_SUCCESS;
+ } else if (subject_style == ANON_S) {
+ flags |= SERD_EMPTY_S; // Write anonymous subjects in "[] p o" style
+ }
+
+ const SerdNode* object = serd_statement_object(statement);
+ const NodeStyle object_style = get_node_style(model, object);
+ SerdStatus st = SERD_SUCCESS;
+ if (subject_style == LIST_S && depth == 0) {
+ if (zix_hash_insert(list_subjects, &subject, NULL) !=
+ ZIX_STATUS_EXISTS) {
+ st = write_list(sink,
+ model,
+ list_subjects,
+ depth + 1,
+ SERD_LIST_S,
+ subject);
+ }
+ }
+
+ if (object_style == ANON_O) {
+ flags |= SERD_ANON_O;
+
+ SerdRange* range = serd_model_range(model, object, NULL, NULL, NULL);
+ st = st ? st : serd_sink_write_statement(sink, flags, statement);
+ st = st ? st : write_pretty_range(sink, depth + 1, 0, model, range);
+ st = st ? st : serd_sink_write_end(sink, object);
+ serd_range_free(range);
+
+ return st;
+ } else if (object_style == LIST_O) {
+ flags |= SERD_LIST_O;
+ st = st ? st : serd_sink_write_statement(sink, flags, statement);
+ st = st ? st
+ : write_list(sink, model, list_subjects, depth + 1, 0, object);
+ return st;
+ }
+
+ return serd_sink_write_statement(sink, flags, statement);
+}
+
+SerdStatus
+serd_range_serialise(const SerdRange* range,
+ const SerdSink* sink,
+ const SerdSerialisationFlags flags)
+{
+ SerdStatus st = SERD_SUCCESS;
+ if (serd_range_empty(range)) {
+ return st;
+ }
+
+ SerdRange* const copy = serd_range_copy(range);
+ if (flags & SERD_NO_INLINE_OBJECTS) {
+ for (; !st && !serd_range_empty(copy); serd_range_next(copy)) {
+ st = serd_sink_write_statement(sink, 0, serd_range_front(copy));
+ }
+ } else {
+ st = write_pretty_range(sink, 0, 0, range->begin->model, copy);
+ }
+
+ serd_range_free(copy);
+ return st;
+}
diff --git a/src/range.h b/src/range.h
new file mode 100644
index 00000000..97e33b5c
--- /dev/null
+++ b/src/range.h
@@ -0,0 +1,35 @@
+/*
+ Copyright 2011-2020 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.
+*/
+
+#ifndef SERD_RANGE_H
+#define SERD_RANGE_H
+
+#include "serd/serd.h"
+
+#include <stdbool.h>
+
+struct SerdRangeImpl {
+ SerdIter* begin; ///< Iterator to first statement in range
+ SerdIter* end; ///< Iterator to end of range
+};
+
+SerdRange*
+serd_range_new(SerdIter* begin, SerdIter* end);
+
+bool
+serd_range_scan_next(SerdRange* range);
+
+#endif // SERD_RANGE_H
diff --git a/src/serdi.c b/src/serdi.c
index de1a6efd..76496bac 100644
--- a/src/serdi.c
+++ b/src/serdi.c
@@ -59,10 +59,12 @@ print_usage(const char* name, bool error)
fprintf(os, " -i SYNTAX Input syntax: turtle/ntriples/trig/nquads.\n");
fprintf(os, " -k BYTES Parser stack size.\n");
fprintf(os, " -l Lax (non-strict) parsing.\n");
+ fprintf(os, " -m Build and serialise a model (no streaming).\n");
fprintf(os, " -o SYNTAX Output syntax: turtle/ntriples/nquads.\n");
fprintf(os, " -p PREFIX Add PREFIX to blank node IDs.\n");
fprintf(os, " -q Suppress all output except data.\n");
fprintf(os, " -r ROOT_URI Keep relative URIs within ROOT_URI.\n");
+ fprintf(os, " -S Stream model quickly without inlining.\n");
fprintf(os, " -s INPUT Parse INPUT as string (terminates options).\n");
fprintf(os, " -v Display version information and exit.\n");
return error ? 1 : 0;
@@ -90,7 +92,9 @@ main(int argc, char** argv)
bool bulk_read = true;
bool bulk_write = false;
bool full_uris = false;
+ bool no_inline = false;
bool lax = false;
+ bool use_model = false;
bool quiet = false;
size_t stack_size = 4194304;
const char* add_prefix = NULL;
@@ -113,10 +117,14 @@ main(int argc, char** argv)
return print_usage(argv[0], false);
} else if (argv[a][1] == 'l') {
lax = true;
+ } else if (argv[a][1] == 'm') {
+ use_model = true;
} else if (argv[a][1] == 'q') {
quiet = true;
} else if (argv[a][1] == 'v') {
return print_version();
+ } else if (argv[a][1] == 'S') {
+ no_inline = true;
} else if (argv[a][1] == 's') {
from_string = true;
++a;
@@ -201,6 +209,9 @@ main(int argc, char** argv)
((ascii ? SERD_STYLE_ASCII : 0) | //
(full_uris ? (SERD_STYLE_UNQUALIFIED | SERD_STYLE_UNRESOLVED) : 0));
+ const SerdSerialisationFlags serialisation_flags =
+ no_inline ? SERD_NO_INLINE_OBJECTS : 0;
+
SerdByteSink* byte_sink = serd_byte_sink_new(
(SerdWriteFunc)fwrite, out_fd, bulk_write ? 4096 : 1);
@@ -211,9 +222,22 @@ main(int argc, char** argv)
(SerdWriteFunc)serd_byte_sink_write,
byte_sink);
- SerdReader* reader = serd_reader_new(
- world, input_syntax, serd_writer_get_sink(writer), stack_size);
+ SerdReader* reader = NULL;
+ SerdModel* model = NULL;
+ SerdSink* inserter = NULL;
+ const SerdSink* sink = NULL;
+ if (use_model) {
+ const SerdModelFlags flags =
+ SERD_INDEX_SPO | (input_has_graphs ? SERD_INDEX_GRAPHS : 0) |
+ (no_inline ? 0 : SERD_INDEX_OPS);
+ model = serd_model_new(world, flags);
+ inserter = serd_inserter_new(model, env, NULL);
+ sink = inserter;
+ } else {
+ sink = serd_writer_get_sink(writer);
+ }
+ reader = serd_reader_new(world, input_syntax, sink, stack_size);
serd_reader_set_strict(reader, !lax);
if (quiet) {
serd_world_set_log_func(world, serd_quiet_error_func, NULL);
@@ -247,6 +271,19 @@ main(int argc, char** argv)
}
serd_reader_finish(reader);
+
+ if (st <= SERD_FAILURE && use_model) {
+ const SerdSink* wsink = serd_writer_get_sink(writer);
+ serd_env_write_prefixes(env, wsink);
+
+ SerdRange* range = serd_model_all(model);
+ st = serd_range_serialise(range, wsink, serialisation_flags);
+ serd_range_free(range);
+ }
+
+ serd_node_free(input_name);
+ serd_sink_free(inserter);
+ serd_model_free(model);
serd_reader_free(reader);
serd_writer_free(writer);
serd_byte_sink_free(byte_sink);
diff --git a/src/statement.c b/src/statement.c
index c9c9dca1..c7cd146f 100644
--- a/src/statement.c
+++ b/src/statement.c
@@ -16,6 +16,56 @@
#include "statement.h"
+#include "cursor.h"
+#include "node.h"
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+
+SerdStatement*
+serd_statement_new(const SerdNode* s,
+ const SerdNode* p,
+ const SerdNode* o,
+ const SerdNode* g,
+ const SerdCursor* cursor)
+{
+ SerdStatement* statement = (SerdStatement*)malloc(sizeof(SerdStatement));
+ if (statement) {
+ statement->nodes[0] = s;
+ statement->nodes[1] = p;
+ statement->nodes[2] = o;
+ statement->nodes[3] = g;
+ statement->cursor = serd_cursor_copy(cursor);
+ }
+ return statement;
+}
+
+SerdStatement*
+serd_statement_copy(const SerdStatement* statement)
+{
+ if (!statement) {
+ return NULL;
+ }
+
+ SerdStatement* copy = (SerdStatement*)malloc(sizeof(SerdStatement));
+ memcpy(copy, statement, sizeof(SerdStatement));
+ if (statement->cursor) {
+ copy->cursor = (SerdCursor*)malloc(sizeof(SerdCursor));
+ memcpy(copy->cursor, statement->cursor, sizeof(SerdCursor));
+ }
+ return copy;
+}
+
+void
+serd_statement_free(SerdStatement* statement)
+{
+ if (statement) {
+ free(statement->cursor);
+ free(statement);
+ }
+}
+
const SerdNode*
serd_statement_node(const SerdStatement* statement, SerdField field)
{
@@ -51,3 +101,32 @@ serd_statement_cursor(const SerdStatement* statement)
{
return statement->cursor;
}
+
+bool
+serd_statement_equals(const SerdStatement* a, const SerdStatement* b)
+{
+ return (a == b || (a && b && serd_node_equals(a->nodes[0], b->nodes[0]) &&
+ serd_node_equals(a->nodes[1], b->nodes[1]) &&
+ serd_node_equals(a->nodes[2], b->nodes[2]) &&
+ serd_node_equals(a->nodes[3], b->nodes[3])));
+}
+
+bool
+serd_statement_matches(const SerdStatement* statement,
+ const SerdNode* subject,
+ const SerdNode* predicate,
+ const SerdNode* object,
+ const SerdNode* graph)
+{
+ return (serd_node_pattern_match(statement->nodes[0], subject) &&
+ serd_node_pattern_match(statement->nodes[1], predicate) &&
+ serd_node_pattern_match(statement->nodes[2], object) &&
+ serd_node_pattern_match(statement->nodes[3], graph));
+}
+
+bool
+serd_statement_matches_quad(const SerdStatement* statement, const SerdQuad quad)
+{
+ return serd_statement_matches(
+ statement, quad[0], quad[1], quad[2], quad[3]);
+}
diff --git a/src/statement.h b/src/statement.h
index 1cb5345c..2c368219 100644
--- a/src/statement.h
+++ b/src/statement.h
@@ -19,6 +19,8 @@
#include "serd/serd.h"
+#include <stdbool.h>
+
/**
Quad of nodes (a statement), or a quad pattern.
@@ -31,4 +33,8 @@ struct SerdStatementImpl {
SerdCursor* cursor;
};
+bool
+serd_statement_matches_quad(const SerdStatement* statement,
+ const SerdQuad quad);
+
#endif // SERD_STATEMENT_H
diff --git a/src/string.c b/src/string.c
index c755ff97..106a68d7 100644
--- a/src/string.c
+++ b/src/string.c
@@ -38,6 +38,7 @@ serd_strerror(SerdStatus status)
case SERD_ERR_UNKNOWN: return "Unknown error";
case SERD_ERR_BAD_SYNTAX: return "Invalid syntax";
case SERD_ERR_BAD_ARG: return "Invalid argument";
+ case SERD_ERR_BAD_ITER: return "Invalid iterator";
case SERD_ERR_NOT_FOUND: return "Not found";
case SERD_ERR_ID_CLASH: return "Blank node ID clash";
case SERD_ERR_BAD_CURIE: return "Invalid CURIE";
--
cgit v1.2.1