cannam@226: /*
cannam@226: Copyright 2011-2016 David Robillard <http://drobilla.net>
cannam@226:
cannam@226: Permission to use, copy, modify, and/or distribute this software for any
cannam@226: purpose with or without fee is hereby granted, provided that the above
cannam@226: copyright notice and this permission notice appear in all copies.
cannam@226:
cannam@226: THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
cannam@226: WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
cannam@226: MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
cannam@226: ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
cannam@226: WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
cannam@226: ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
cannam@226: OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
cannam@226: */
cannam@226:
cannam@226: // C99
cannam@226: #include <assert.h>
cannam@226: #include <errno.h>
cannam@226: #include <stdint.h>
cannam@226: #include <stdio.h>
cannam@226: #include <stdlib.h>
cannam@226: #include <string.h>
cannam@226:
cannam@226: #define ZIX_INLINE
cannam@226: #include "zix/digest.c"
cannam@226: #include "zix/hash.c"
cannam@226: #include "zix/btree.c"
cannam@226:
cannam@226: #include "sord_config.h"
cannam@226: #include "sord_internal.h"
cannam@226:
cannam@226: #define SORD_LOG(prefix, ...) fprintf(stderr, "[Sord::" prefix "] " __VA_ARGS__)
cannam@226:
cannam@226: #ifdef SORD_DEBUG_ITER
cannam@226: # define SORD_ITER_LOG(...) SORD_LOG("iter", __VA_ARGS__)
cannam@226: #else
cannam@226: # define SORD_ITER_LOG(...)
cannam@226: #endif
cannam@226: #ifdef SORD_DEBUG_SEARCH
cannam@226: # define SORD_FIND_LOG(...) SORD_LOG("search", __VA_ARGS__)
cannam@226: #else
cannam@226: # define SORD_FIND_LOG(...)
cannam@226: #endif
cannam@226: #ifdef SORD_DEBUG_WRITE
cannam@226: # define SORD_WRITE_LOG(...) SORD_LOG("write", __VA_ARGS__)
cannam@226: #else
cannam@226: # define SORD_WRITE_LOG(...)
cannam@226: #endif
cannam@226:
cannam@226: #define NUM_ORDERS 12
cannam@226: #define STATEMENT_LEN 3
cannam@226: #define TUP_LEN STATEMENT_LEN + 1
cannam@226: #define DEFAULT_ORDER SPO
cannam@226: #define DEFAULT_GRAPH_ORDER GSPO
cannam@226:
cannam@226: #define TUP_FMT "(%s %s %s %s)"
cannam@226: #define TUP_FMT_ELEM(e) ((e) ? sord_node_get_string(e) : (const uint8_t*)"*")
cannam@226: #define TUP_FMT_ARGS(t) \
cannam@226: TUP_FMT_ELEM((t)[0]), \
cannam@226: TUP_FMT_ELEM((t)[1]), \
cannam@226: TUP_FMT_ELEM((t)[2]), \
cannam@226: TUP_FMT_ELEM((t)[3])
cannam@226:
cannam@226: #define TUP_S 0
cannam@226: #define TUP_P 1
cannam@226: #define TUP_O 2
cannam@226: #define TUP_G 3
cannam@226:
cannam@226: /** Triple ordering */
cannam@226: typedef enum {
cannam@226: SPO, ///< Subject, Predicate, Object
cannam@226: SOP, ///< Subject, Object, Predicate
cannam@226: OPS, ///< Object, Predicate, Subject
cannam@226: OSP, ///< Object, Subject, Predicate
cannam@226: PSO, ///< Predicate, Subject, Object
cannam@226: POS, ///< Predicate, Object, Subject
cannam@226: GSPO, ///< Graph, Subject, Predicate, Object
cannam@226: GSOP, ///< Graph, Subject, Object, Predicate
cannam@226: GOPS, ///< Graph, Object, Predicate, Subject
cannam@226: GOSP, ///< Graph, Object, Subject, Predicate
cannam@226: GPSO, ///< Graph, Predicate, Subject, Object
cannam@226: GPOS ///< Graph, Predicate, Object, Subject
cannam@226: } SordOrder;
cannam@226:
cannam@226: #ifdef SORD_DEBUG_SEARCH
cannam@226: /** String name of each ordering (array indexed by SordOrder) */
cannam@226: static const char* const order_names[NUM_ORDERS] = {
cannam@226: "spo", "sop", "ops", "osp", "pso", "pos",
cannam@226: "gspo", "gsop", "gops", "gosp", "gpso", "gpos"
cannam@226: };
cannam@226: #endif
cannam@226:
cannam@226: /**
cannam@226: Quads of indices for each order, from most to least significant
cannam@226: (array indexed by SordOrder)
cannam@226: */
cannam@226: static const int orderings[NUM_ORDERS][TUP_LEN] = {
cannam@226: { 0, 1, 2, 3 }, { 0, 2, 1, 3 }, // SPO, SOP
cannam@226: { 2, 1, 0, 3 }, { 2, 0, 1, 3 }, // OPS, OSP
cannam@226: { 1, 0, 2, 3 }, { 1, 2, 0, 3 }, // PSO, POS
cannam@226: { 3, 0, 1, 2 }, { 3, 0, 2, 1 }, // GSPO, GSOP
cannam@226: { 3, 2, 1, 0 }, { 3, 2, 0, 1 }, // GOPS, GOSP
cannam@226: { 3, 1, 0, 2 }, { 3, 1, 2, 0 } // GPSO, GPOS
cannam@226: };
cannam@226:
cannam@226: /** World */
cannam@226: struct SordWorldImpl {
cannam@226: ZixHash* nodes;
cannam@226: SerdErrorSink error_sink;
cannam@226: void* error_handle;
cannam@226: };
cannam@226:
cannam@226: /** Store */
cannam@226: struct SordModelImpl {
cannam@226: SordWorld* world;
cannam@226:
cannam@226: /** Index for each possible triple ordering (may or may not exist).
cannam@226: * Each index is a tree of SordQuad with the appropriate ordering.
cannam@226: */
cannam@226: ZixBTree* indices[NUM_ORDERS];
cannam@226:
cannam@226: size_t n_quads;
cannam@226: size_t n_iters;
cannam@226: };
cannam@226:
cannam@226: /** Mode for searching or iteration */
cannam@226: typedef enum {
cannam@226: ALL, ///< Iterate over entire store
cannam@226: SINGLE, ///< Iteration over a single element (exact search)
cannam@226: RANGE, ///< Iterate over range with equal prefix
cannam@226: FILTER_RANGE, ///< Iterate over range with equal prefix, filtering
cannam@226: FILTER_ALL ///< Iterate to end of store, filtering
cannam@226: } SearchMode;
cannam@226:
cannam@226: /** Iterator over some range of a store */
cannam@226: struct SordIterImpl {
cannam@226: const SordModel* sord; ///< Model being iterated over
cannam@226: ZixBTreeIter* cur; ///< Current DB cursor
cannam@226: SordQuad pat; ///< Pattern (in ordering order)
cannam@226: SordOrder order; ///< Store order (which index)
cannam@226: SearchMode mode; ///< Iteration mode
cannam@226: int n_prefix; ///< Prefix for RANGE and FILTER_RANGE
cannam@226: bool end; ///< True iff reached end
cannam@226: bool skip_graphs; ///< Iteration should ignore graphs
cannam@226: };
cannam@226:
cannam@226: static uint32_t
cannam@226: sord_node_hash(const void* n)
cannam@226: {
cannam@226: const SordNode* node = (const SordNode*)n;
cannam@226: uint32_t hash = zix_digest_start();
cannam@226: hash = zix_digest_add(hash, node->node.buf, node->node.n_bytes);
cannam@226: hash = zix_digest_add(hash, &node->node.type, sizeof(node->node.type));
cannam@226: if (node->node.type == SERD_LITERAL) {
cannam@226: hash = zix_digest_add(hash, &node->meta.lit, sizeof(node->meta.lit));
cannam@226: }
cannam@226: return hash;
cannam@226: }
cannam@226:
cannam@226: static bool
cannam@226: sord_node_hash_equal(const void* a, const void* b)
cannam@226: {
cannam@226: const SordNode* a_node = (const SordNode*)a;
cannam@226: const SordNode* b_node = (const SordNode*)b;
cannam@226: return (a_node == b_node)
cannam@226: || ((a_node->node.type == b_node->node.type) &&
cannam@226: (a_node->node.type != SERD_LITERAL ||
cannam@226: (a_node->meta.lit.datatype == b_node->meta.lit.datatype &&
cannam@226: !strncmp(a_node->meta.lit.lang,
cannam@226: b_node->meta.lit.lang,
cannam@226: sizeof(a_node->meta.lit.lang)))) &&
cannam@226: (serd_node_equals(&a_node->node, &b_node->node)));
cannam@226: }
cannam@226:
cannam@226: static void
cannam@226: error(SordWorld* world, SerdStatus st, const char* fmt, ...)
cannam@226: {
cannam@226: va_list args;
cannam@226: va_start(args, fmt);
cannam@226: const SerdError e = { st, NULL, 0, 0, fmt, &args };
cannam@226: if (world->error_sink) {
cannam@226: world->error_sink(world->error_handle, &e);
cannam@226: } else {
cannam@226: fprintf(stderr, "error: ");
cannam@226: vfprintf(stderr, fmt, args);
cannam@226: }
cannam@226: va_end(args);
cannam@226: }
cannam@226:
cannam@226: SordWorld*
cannam@226: sord_world_new(void)
cannam@226: {
cannam@226: SordWorld* world = (SordWorld*)malloc(sizeof(SordWorld));
cannam@226: world->error_sink = NULL;
cannam@226: world->error_handle = NULL;
cannam@226:
cannam@226: world->nodes = zix_hash_new(
cannam@226: sord_node_hash, sord_node_hash_equal, sizeof(SordNode));
cannam@226:
cannam@226: return world;
cannam@226: }
cannam@226:
cannam@226: static void
cannam@226: free_node_entry(void* value, void* user_data)
cannam@226: {
cannam@226: SordNode* node = (SordNode*)value;
cannam@226: if (node->node.type == SERD_LITERAL) {
cannam@226: sord_node_free((SordWorld*)user_data, node->meta.lit.datatype);
cannam@226: }
cannam@226: free((uint8_t*)node->node.buf);
cannam@226: }
cannam@226:
cannam@226: void
cannam@226: sord_world_free(SordWorld* world)
cannam@226: {
cannam@226: zix_hash_foreach(world->nodes, free_node_entry, world);
cannam@226: zix_hash_free(world->nodes);
cannam@226: free(world);
cannam@226: }
cannam@226:
cannam@226: void
cannam@226: sord_world_set_error_sink(SordWorld* world,
cannam@226: SerdErrorSink error_sink,
cannam@226: void* handle)
cannam@226: {
cannam@226: world->error_sink = error_sink;
cannam@226: world->error_handle = handle;
cannam@226: }
cannam@226:
cannam@226: /** Compare nodes, considering NULL a wildcard match. */
cannam@226: static inline int
cannam@226: sord_node_compare(const SordNode* a, const SordNode* b)
cannam@226: {
cannam@226: if (a == b || !a || !b) {
cannam@226: return 0; // Exact or wildcard match
cannam@226: } else if (a->node.type != b->node.type) {
cannam@226: return a->node.type - b->node.type;
cannam@226: }
cannam@226:
cannam@226: int cmp = 0;
cannam@226: switch (a->node.type) {
cannam@226: case SERD_URI:
cannam@226: case SERD_BLANK:
cannam@226: return strcmp((const char*)a->node.buf, (const char*)b->node.buf);
cannam@226: case SERD_LITERAL:
cannam@226: cmp = strcmp((const char*)sord_node_get_string(a),
cannam@226: (const char*)sord_node_get_string(b));
cannam@226: if (cmp == 0) {
cannam@226: // Note: Can't use sord_node_compare here since it does wildcards
cannam@226: if (!a->meta.lit.datatype || !b->meta.lit.datatype) {
cannam@226: cmp = a->meta.lit.datatype - b->meta.lit.datatype;
cannam@226: } else {
cannam@226: cmp = strcmp((const char*)a->meta.lit.datatype->node.buf,
cannam@226: (const char*)b->meta.lit.datatype->node.buf);
cannam@226: }
cannam@226: }
cannam@226: if (cmp == 0) {
cannam@226: cmp = strcmp(a->meta.lit.lang, b->meta.lit.lang);
cannam@226: }
cannam@226: default:
cannam@226: break;
cannam@226: }
cannam@226: return cmp;
cannam@226: }
cannam@226:
cannam@226: bool
cannam@226: sord_node_equals(const SordNode* a, const SordNode* b)
cannam@226: {
cannam@226: return a == b; // Nodes are interned
cannam@226: }
cannam@226:
cannam@226: /** Return true iff IDs are equivalent, or one is a wildcard */
cannam@226: static inline bool
cannam@226: sord_id_match(const SordNode* a, const SordNode* b)
cannam@226: {
cannam@226: return !a || !b || (a == b);
cannam@226: }
cannam@226:
cannam@226: static inline bool
cannam@226: sord_quad_match_inline(const SordQuad x, const SordQuad y)
cannam@226: {
cannam@226: return sord_id_match(x[0], y[0])
cannam@226: && sord_id_match(x[1], y[1])
cannam@226: && sord_id_match(x[2], y[2])
cannam@226: && sord_id_match(x[3], y[3]);
cannam@226: }
cannam@226:
cannam@226: bool
cannam@226: sord_quad_match(const SordQuad x, const SordQuad y)
cannam@226: {
cannam@226: return sord_quad_match_inline(x, y);
cannam@226: }
cannam@226:
cannam@226: /**
cannam@226: Compare two quad IDs lexicographically.
cannam@226: NULL IDs (equal to 0) are treated as wildcards, always less than every
cannam@226: other possible ID, except itself.
cannam@226: */
cannam@226: static int
cannam@226: sord_quad_compare(const void* x_ptr, const void* y_ptr, void* user_data)
cannam@226: {
cannam@226: const int* const ordering = (const int*)user_data;
cannam@226: const SordNode*const*const x = (const SordNode*const*)x_ptr;
cannam@226: const SordNode*const*const y = (const SordNode*const*)y_ptr;
cannam@226:
cannam@226: for (int i = 0; i < TUP_LEN; ++i) {
cannam@226: const int idx = ordering[i];
cannam@226: const int cmp = sord_node_compare(x[idx], y[idx]);
cannam@226: if (cmp) {
cannam@226: return cmp;
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: return 0;
cannam@226: }
cannam@226:
cannam@226: static inline bool
cannam@226: sord_iter_forward(SordIter* iter)
cannam@226: {
cannam@226: if (!iter->skip_graphs) {
cannam@226: zix_btree_iter_increment(iter->cur);
cannam@226: return zix_btree_iter_is_end(iter->cur);
cannam@226: }
cannam@226:
cannam@226: SordNode** key = (SordNode**)zix_btree_get(iter->cur);
cannam@226: const SordQuad initial = { key[0], key[1], key[2], key[3] };
cannam@226: zix_btree_iter_increment(iter->cur);
cannam@226: while (!zix_btree_iter_is_end(iter->cur)) {
cannam@226: key = (SordNode**)zix_btree_get(iter->cur);
cannam@226: for (int i = 0; i < 3; ++i)
cannam@226: if (key[i] != initial[i])
cannam@226: return false;
cannam@226:
cannam@226: zix_btree_iter_increment(iter->cur);
cannam@226: }
cannam@226:
cannam@226: return true;
cannam@226: }
cannam@226:
cannam@226: /**
cannam@226: Seek forward as necessary until `iter` points at a match.
cannam@226: @return true iff iterator reached end of valid range.
cannam@226: */
cannam@226: static inline bool
cannam@226: sord_iter_seek_match(SordIter* iter)
cannam@226: {
cannam@226: for (iter->end = true;
cannam@226: !zix_btree_iter_is_end(iter->cur);
cannam@226: sord_iter_forward(iter)) {
cannam@226: const SordNode** const key = (const SordNode**)zix_btree_get(iter->cur);
cannam@226: if (sord_quad_match_inline(key, iter->pat))
cannam@226: return (iter->end = false);
cannam@226: }
cannam@226: return true;
cannam@226: }
cannam@226:
cannam@226: /**
cannam@226: Seek forward as necessary until `iter` points at a match, or the prefix
cannam@226: no longer matches iter->pat.
cannam@226: @return true iff iterator reached end of valid range.
cannam@226: */
cannam@226: static inline bool
cannam@226: sord_iter_seek_match_range(SordIter* iter)
cannam@226: {
cannam@226: assert(!iter->end);
cannam@226:
cannam@226: do {
cannam@226: const SordNode** key = (const SordNode**)zix_btree_get(iter->cur);
cannam@226:
cannam@226: if (sord_quad_match_inline(key, iter->pat))
cannam@226: return false; // Found match
cannam@226:
cannam@226: for (int i = 0; i < iter->n_prefix; ++i) {
cannam@226: const int idx = orderings[iter->order][i];
cannam@226: if (!sord_id_match(key[idx], iter->pat[idx])) {
cannam@226: iter->end = true; // Reached end of valid range
cannam@226: return true;
cannam@226: }
cannam@226: }
cannam@226: } while (!sord_iter_forward(iter));
cannam@226:
cannam@226: return (iter->end = true); // Reached end
cannam@226: }
cannam@226:
cannam@226: static SordIter*
cannam@226: sord_iter_new(const SordModel* sord, ZixBTreeIter* cur, const SordQuad pat,
cannam@226: SordOrder order, SearchMode mode, int n_prefix)
cannam@226: {
cannam@226: SordIter* iter = (SordIter*)malloc(sizeof(SordIter));
cannam@226: iter->sord = sord;
cannam@226: iter->cur = cur;
cannam@226: iter->order = order;
cannam@226: iter->mode = mode;
cannam@226: iter->n_prefix = n_prefix;
cannam@226: iter->end = false;
cannam@226: iter->skip_graphs = order < GSPO;
cannam@226: for (int i = 0; i < TUP_LEN; ++i) {
cannam@226: iter->pat[i] = pat[i];
cannam@226: }
cannam@226:
cannam@226: switch (iter->mode) {
cannam@226: case ALL:
cannam@226: case SINGLE:
cannam@226: case RANGE:
cannam@226: assert(
cannam@226: sord_quad_match_inline((const SordNode**)zix_btree_get(iter->cur),
cannam@226: iter->pat));
cannam@226: break;
cannam@226: case FILTER_RANGE:
cannam@226: sord_iter_seek_match_range(iter);
cannam@226: break;
cannam@226: case FILTER_ALL:
cannam@226: sord_iter_seek_match(iter);
cannam@226: break;
cannam@226: }
cannam@226:
cannam@226: #ifdef SORD_DEBUG_ITER
cannam@226: SordQuad value;
cannam@226: sord_iter_get(iter, value);
cannam@226: SORD_ITER_LOG("New %p pat=" TUP_FMT " cur=" TUP_FMT " end=%d skip=%d\n",
cannam@226: (void*)iter, TUP_FMT_ARGS(pat), TUP_FMT_ARGS(value),
cannam@226: iter->end, iter->skip_graphs);
cannam@226: #endif
cannam@226:
cannam@226: ++((SordModel*)sord)->n_iters;
cannam@226: return iter;
cannam@226: }
cannam@226:
cannam@226: const SordModel*
cannam@226: sord_iter_get_model(SordIter* iter)
cannam@226: {
cannam@226: return iter->sord;
cannam@226: }
cannam@226:
cannam@226: void
cannam@226: sord_iter_get(const SordIter* iter, SordQuad id)
cannam@226: {
cannam@226: SordNode** key = (SordNode**)zix_btree_get(iter->cur);
cannam@226: for (int i = 0; i < TUP_LEN; ++i) {
cannam@226: id[i] = key[i];
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: const SordNode*
cannam@226: sord_iter_get_node(const SordIter* iter, SordQuadIndex index)
cannam@226: {
cannam@226: return (!sord_iter_end(iter)
cannam@226: ? ((SordNode**)zix_btree_get(iter->cur))[index]
cannam@226: : NULL);
cannam@226: }
cannam@226:
cannam@226: static bool
cannam@226: sord_iter_scan_next(SordIter* iter)
cannam@226: {
cannam@226: if (iter->end) {
cannam@226: return true;
cannam@226: }
cannam@226:
cannam@226: const SordNode** key;
cannam@226: if (!iter->end) {
cannam@226: switch (iter->mode) {
cannam@226: case ALL:
cannam@226: // At the end if the cursor is (assigned above)
cannam@226: break;
cannam@226: case SINGLE:
cannam@226: iter->end = true;
cannam@226: SORD_ITER_LOG("%p reached single end\n", (void*)iter);
cannam@226: break;
cannam@226: case RANGE:
cannam@226: SORD_ITER_LOG("%p range next\n", (void*)iter);
cannam@226: // At the end if the MSNs no longer match
cannam@226: key = (const SordNode**)zix_btree_get(iter->cur);
cannam@226: assert(key);
cannam@226: for (int i = 0; i < iter->n_prefix; ++i) {
cannam@226: const int idx = orderings[iter->order][i];
cannam@226: if (!sord_id_match(key[idx], iter->pat[idx])) {
cannam@226: iter->end = true;
cannam@226: SORD_ITER_LOG("%p reached non-match end\n", (void*)iter);
cannam@226: break;
cannam@226: }
cannam@226: }
cannam@226: break;
cannam@226: case FILTER_RANGE:
cannam@226: // Seek forward to next match, stopping if prefix changes
cannam@226: sord_iter_seek_match_range(iter);
cannam@226: break;
cannam@226: case FILTER_ALL:
cannam@226: // Seek forward to next match
cannam@226: sord_iter_seek_match(iter);
cannam@226: break;
cannam@226: }
cannam@226: } else {
cannam@226: SORD_ITER_LOG("%p reached index end\n", (void*)iter);
cannam@226: }
cannam@226:
cannam@226: if (iter->end) {
cannam@226: SORD_ITER_LOG("%p Reached end\n", (void*)iter);
cannam@226: return true;
cannam@226: } else {
cannam@226: #ifdef SORD_DEBUG_ITER
cannam@226: SordQuad tup;
cannam@226: sord_iter_get(iter, tup);
cannam@226: SORD_ITER_LOG("%p Increment to " TUP_FMT "\n",
cannam@226: (void*)iter, TUP_FMT_ARGS(tup));
cannam@226: #endif
cannam@226: return false;
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: bool
cannam@226: sord_iter_next(SordIter* iter)
cannam@226: {
cannam@226: if (iter->end) {
cannam@226: return true;
cannam@226: }
cannam@226:
cannam@226: iter->end = sord_iter_forward(iter);
cannam@226: return sord_iter_scan_next(iter);
cannam@226: }
cannam@226:
cannam@226: bool
cannam@226: sord_iter_end(const SordIter* iter)
cannam@226: {
cannam@226: return !iter || iter->end;
cannam@226: }
cannam@226:
cannam@226: void
cannam@226: sord_iter_free(SordIter* iter)
cannam@226: {
cannam@226: SORD_ITER_LOG("%p Free\n", (void*)iter);
cannam@226: if (iter) {
cannam@226: --((SordModel*)iter->sord)->n_iters;
cannam@226: zix_btree_iter_free(iter->cur);
cannam@226: free(iter);
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: /**
cannam@226: Return true iff `sord` has an index for `order`.
cannam@226: If `graphs` is true, `order` will be modified to be the
cannam@226: corresponding order with a G prepended (so G will be the MSN).
cannam@226: */
cannam@226: static inline bool
cannam@226: sord_has_index(SordModel* sord, SordOrder* order, int* n_prefix, bool graphs)
cannam@226: {
cannam@226: if (graphs) {
cannam@226: *order = (SordOrder)(*order + GSPO);
cannam@226: *n_prefix += 1;
cannam@226: }
cannam@226:
cannam@226: return sord->indices[*order];
cannam@226: }
cannam@226:
cannam@226: /**
cannam@226: Return the best available index for a pattern.
cannam@226: @param pat Pattern in standard (S P O G) order
cannam@226: @param mode Set to the (best) iteration mode for iterating over results
cannam@226: @param n_prefix Set to the length of the range prefix
cannam@226: (for `mode` == RANGE and `mode` == FILTER_RANGE)
cannam@226: */
cannam@226: static inline SordOrder
cannam@226: sord_best_index(SordModel* sord,
cannam@226: const SordQuad pat,
cannam@226: SearchMode* mode,
cannam@226: int* n_prefix)
cannam@226: {
cannam@226: const bool graph_search = (pat[TUP_G] != 0);
cannam@226:
cannam@226: const unsigned sig
cannam@226: = (pat[0] ? 1 : 0) * 0x100
cannam@226: + (pat[1] ? 1 : 0) * 0x010
cannam@226: + (pat[2] ? 1 : 0) * 0x001;
cannam@226:
cannam@226: SordOrder good[2] = { (SordOrder)-1, (SordOrder)-1 };
cannam@226:
cannam@226: #define PAT_CASE(sig, m, g0, g1, np) \
cannam@226: case sig: \
cannam@226: *mode = m; \
cannam@226: good[0] = g0; \
cannam@226: good[1] = g1; \
cannam@226: *n_prefix = np; \
cannam@226: break
cannam@226:
cannam@226: // Good orderings that don't require filtering
cannam@226: *mode = RANGE;
cannam@226: *n_prefix = 0;
cannam@226: switch (sig) {
cannam@226: case 0x000:
cannam@226: assert(graph_search);
cannam@226: *mode = RANGE;
cannam@226: *n_prefix = 1;
cannam@226: return DEFAULT_GRAPH_ORDER;
cannam@226: case 0x111:
cannam@226: *mode = SINGLE;
cannam@226: return graph_search ? DEFAULT_GRAPH_ORDER : DEFAULT_ORDER;
cannam@226:
cannam@226: PAT_CASE(0x001, RANGE, OPS, OSP, 1);
cannam@226: PAT_CASE(0x010, RANGE, POS, PSO, 1);
cannam@226: PAT_CASE(0x011, RANGE, OPS, POS, 2);
cannam@226: PAT_CASE(0x100, RANGE, SPO, SOP, 1);
cannam@226: PAT_CASE(0x101, RANGE, SOP, OSP, 2);
cannam@226: PAT_CASE(0x110, RANGE, SPO, PSO, 2);
cannam@226: }
cannam@226:
cannam@226: if (*mode == RANGE) {
cannam@226: if (sord_has_index(sord, &good[0], n_prefix, graph_search)) {
cannam@226: return good[0];
cannam@226: } else if (sord_has_index(sord, &good[1], n_prefix, graph_search)) {
cannam@226: return good[1];
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: // Not so good orderings that require filtering, but can
cannam@226: // still be constrained to a range
cannam@226: switch (sig) {
cannam@226: PAT_CASE(0x011, FILTER_RANGE, OSP, PSO, 1);
cannam@226: PAT_CASE(0x101, FILTER_RANGE, SPO, OPS, 1);
cannam@226: // SPO is always present, so 0x110 is never reached here
cannam@226: default: break;
cannam@226: }
cannam@226:
cannam@226: if (*mode == FILTER_RANGE) {
cannam@226: if (sord_has_index(sord, &good[0], n_prefix, graph_search)) {
cannam@226: return good[0];
cannam@226: } else if (sord_has_index(sord, &good[1], n_prefix, graph_search)) {
cannam@226: return good[1];
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: if (graph_search) {
cannam@226: *mode = FILTER_RANGE;
cannam@226: *n_prefix = 1;
cannam@226: return DEFAULT_GRAPH_ORDER;
cannam@226: } else {
cannam@226: *mode = FILTER_ALL;
cannam@226: return DEFAULT_ORDER;
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: SordModel*
cannam@226: sord_new(SordWorld* world, unsigned indices, bool graphs)
cannam@226: {
cannam@226: SordModel* sord = (SordModel*)malloc(sizeof(struct SordModelImpl));
cannam@226: sord->world = world;
cannam@226: sord->n_quads = 0;
cannam@226: sord->n_iters = 0;
cannam@226:
cannam@226: for (unsigned i = 0; i < (NUM_ORDERS / 2); ++i) {
cannam@226: const int* const ordering = orderings[i];
cannam@226: const int* const g_ordering = orderings[i + (NUM_ORDERS / 2)];
cannam@226:
cannam@226: if (indices & (1 << i)) {
cannam@226: sord->indices[i] = zix_btree_new(
cannam@226: sord_quad_compare, (void*)ordering, NULL);
cannam@226: if (graphs) {
cannam@226: sord->indices[i + (NUM_ORDERS / 2)] = zix_btree_new(
cannam@226: sord_quad_compare, (void*)g_ordering, NULL);
cannam@226: } else {
cannam@226: sord->indices[i + (NUM_ORDERS / 2)] = NULL;
cannam@226: }
cannam@226: } else {
cannam@226: sord->indices[i] = NULL;
cannam@226: sord->indices[i + (NUM_ORDERS / 2)] = NULL;
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: if (!sord->indices[DEFAULT_ORDER]) {
cannam@226: sord->indices[DEFAULT_ORDER] = zix_btree_new(
cannam@226: sord_quad_compare, (void*)orderings[DEFAULT_ORDER], NULL);
cannam@226: }
cannam@226: if (graphs && !sord->indices[DEFAULT_GRAPH_ORDER]) {
cannam@226: sord->indices[DEFAULT_GRAPH_ORDER] = zix_btree_new(
cannam@226: sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER], NULL);
cannam@226: }
cannam@226:
cannam@226: return sord;
cannam@226: }
cannam@226:
cannam@226: static void
cannam@226: sord_node_free_internal(SordWorld* world, SordNode* node)
cannam@226: {
cannam@226: assert(node->refs == 0);
cannam@226:
cannam@226: // Cache pointer to buffer to free after node removal and destruction
cannam@226: const uint8_t* const buf = node->node.buf;
cannam@226:
cannam@226: // Remove node from hash (which frees the node)
cannam@226: if (zix_hash_remove(world->nodes, node)) {
cannam@226: error(world, SERD_ERR_INTERNAL, "failed to remove node from hash\n");
cannam@226: }
cannam@226:
cannam@226: // Free buffer
cannam@226: free((uint8_t*)buf);
cannam@226: }
cannam@226:
cannam@226: static void
cannam@226: sord_add_quad_ref(SordModel* sord, const SordNode* node, SordQuadIndex i)
cannam@226: {
cannam@226: if (node) {
cannam@226: assert(node->refs > 0);
cannam@226: ++((SordNode*)node)->refs;
cannam@226: if (node->node.type != SERD_LITERAL && i == SORD_OBJECT) {
cannam@226: ++((SordNode*)node)->meta.res.refs_as_obj;
cannam@226: }
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: static void
cannam@226: sord_drop_quad_ref(SordModel* sord, const SordNode* node, SordQuadIndex i)
cannam@226: {
cannam@226: if (!node) {
cannam@226: return;
cannam@226: }
cannam@226:
cannam@226: assert(node->refs > 0);
cannam@226: if (node->node.type != SERD_LITERAL && i == SORD_OBJECT) {
cannam@226: assert(node->meta.res.refs_as_obj > 0);
cannam@226: --((SordNode*)node)->meta.res.refs_as_obj;
cannam@226: }
cannam@226: if (--((SordNode*)node)->refs == 0) {
cannam@226: sord_node_free_internal(sord_get_world(sord), (SordNode*)node);
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: void
cannam@226: sord_free(SordModel* sord)
cannam@226: {
cannam@226: if (!sord)
cannam@226: return;
cannam@226:
cannam@226: // Free nodes
cannam@226: SordQuad tup;
cannam@226: SordIter* i = sord_begin(sord);
cannam@226: for (; !sord_iter_end(i); sord_iter_next(i)) {
cannam@226: sord_iter_get(i, tup);
cannam@226: for (int t = 0; t < TUP_LEN; ++t) {
cannam@226: sord_drop_quad_ref(sord, tup[t], (SordQuadIndex)t);
cannam@226: }
cannam@226: }
cannam@226: sord_iter_free(i);
cannam@226:
cannam@226: // Free quads
cannam@226: ZixBTreeIter* t = zix_btree_begin(sord->indices[DEFAULT_ORDER]);
cannam@226: for (; !zix_btree_iter_is_end(t); zix_btree_iter_increment(t)) {
cannam@226: free(zix_btree_get(t));
cannam@226: }
cannam@226: zix_btree_iter_free(t);
cannam@226:
cannam@226: // Free indices
cannam@226: for (unsigned o = 0; o < NUM_ORDERS; ++o)
cannam@226: if (sord->indices[o])
cannam@226: zix_btree_free(sord->indices[o]);
cannam@226:
cannam@226: free(sord);
cannam@226: }
cannam@226:
cannam@226: SordWorld*
cannam@226: sord_get_world(SordModel* sord)
cannam@226: {
cannam@226: return sord->world;
cannam@226: }
cannam@226:
cannam@226: size_t
cannam@226: sord_num_quads(const SordModel* sord)
cannam@226: {
cannam@226: return sord->n_quads;
cannam@226: }
cannam@226:
cannam@226: size_t
cannam@226: sord_num_nodes(const SordWorld* world)
cannam@226: {
cannam@226: return zix_hash_size(world->nodes);
cannam@226: }
cannam@226:
cannam@226: SordIter*
cannam@226: sord_begin(const SordModel* sord)
cannam@226: {
cannam@226: if (sord_num_quads(sord) == 0) {
cannam@226: return NULL;
cannam@226: } else {
cannam@226: ZixBTreeIter* cur = zix_btree_begin(sord->indices[DEFAULT_ORDER]);
cannam@226: SordQuad pat = { 0, 0, 0, 0 };
cannam@226: return sord_iter_new(sord, cur, pat, DEFAULT_ORDER, ALL, 0);
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: SordIter*
cannam@226: sord_find(SordModel* sord, const SordQuad pat)
cannam@226: {
cannam@226: if (!pat[0] && !pat[1] && !pat[2] && !pat[3])
cannam@226: return sord_begin(sord);
cannam@226:
cannam@226: SearchMode mode;
cannam@226: int n_prefix;
cannam@226: const SordOrder index_order = sord_best_index(sord, pat, &mode, &n_prefix);
cannam@226:
cannam@226: SORD_FIND_LOG("Find " TUP_FMT " index=%s mode=%d n_prefix=%d\n",
cannam@226: TUP_FMT_ARGS(pat), order_names[index_order], mode, n_prefix);
cannam@226:
cannam@226: if (pat[0] && pat[1] && pat[2] && pat[3])
cannam@226: mode = SINGLE; // No duplicate quads (Sord is a set)
cannam@226:
cannam@226: ZixBTree* const db = sord->indices[index_order];
cannam@226: ZixBTreeIter* cur = NULL;
cannam@226: zix_btree_lower_bound(db, pat, &cur);
cannam@226: if (zix_btree_iter_is_end(cur)) {
cannam@226: SORD_FIND_LOG("No match found\n");
cannam@226: zix_btree_iter_free(cur);
cannam@226: return NULL;
cannam@226: }
cannam@226: const SordNode** const key = (const SordNode**)zix_btree_get(cur);
cannam@226: if (!key || ( (mode == RANGE || mode == SINGLE)
cannam@226: && !sord_quad_match_inline(pat, key) )) {
cannam@226: SORD_FIND_LOG("No match found\n");
cannam@226: zix_btree_iter_free(cur);
cannam@226: return NULL;
cannam@226: }
cannam@226:
cannam@226: return sord_iter_new(sord, cur, pat, index_order, mode, n_prefix);
cannam@226: }
cannam@226:
cannam@226: SordIter*
cannam@226: sord_search(SordModel* model,
cannam@226: const SordNode* s,
cannam@226: const SordNode* p,
cannam@226: const SordNode* o,
cannam@226: const SordNode* g)
cannam@226: {
cannam@226: SordQuad pat = { s, p, o, g };
cannam@226: return sord_find(model, pat);
cannam@226: }
cannam@226:
cannam@226: SordNode*
cannam@226: sord_get(SordModel* model,
cannam@226: const SordNode* s,
cannam@226: const SordNode* p,
cannam@226: const SordNode* o,
cannam@226: const SordNode* g)
cannam@226: {
cannam@226: if ((bool)s + (bool)p + (bool)o != 2) {
cannam@226: return NULL;
cannam@226: }
cannam@226:
cannam@226: SordIter* i = sord_search(model, s, p, o, g);
cannam@226: SordNode* ret = NULL;
cannam@226: if (!s) {
cannam@226: ret = sord_node_copy(sord_iter_get_node(i, SORD_SUBJECT));
cannam@226: } else if (!p) {
cannam@226: ret = sord_node_copy(sord_iter_get_node(i, SORD_PREDICATE));
cannam@226: } else if (!o) {
cannam@226: ret = sord_node_copy(sord_iter_get_node(i, SORD_OBJECT));
cannam@226: }
cannam@226:
cannam@226: sord_iter_free(i);
cannam@226: return ret;
cannam@226: }
cannam@226:
cannam@226: bool
cannam@226: sord_ask(SordModel* model,
cannam@226: const SordNode* s,
cannam@226: const SordNode* p,
cannam@226: const SordNode* o,
cannam@226: const SordNode* g)
cannam@226: {
cannam@226: SordQuad pat = { s, p, o, g };
cannam@226: return sord_contains(model, pat);
cannam@226: }
cannam@226:
cannam@226: uint64_t
cannam@226: sord_count(SordModel* model,
cannam@226: const SordNode* s,
cannam@226: const SordNode* p,
cannam@226: const SordNode* o,
cannam@226: const SordNode* g)
cannam@226: {
cannam@226: SordIter* i = sord_search(model, s, p, o, g);
cannam@226: uint64_t n = 0;
cannam@226: for (; !sord_iter_end(i); sord_iter_next(i)) {
cannam@226: ++n;
cannam@226: }
cannam@226: sord_iter_free(i);
cannam@226: return n;
cannam@226: }
cannam@226:
cannam@226: bool
cannam@226: sord_contains(SordModel* sord, const SordQuad pat)
cannam@226: {
cannam@226: SordIter* iter = sord_find(sord, pat);
cannam@226: bool ret = (iter != NULL);
cannam@226: sord_iter_free(iter);
cannam@226: return ret;
cannam@226: }
cannam@226:
cannam@226: static uint8_t*
cannam@226: sord_strndup(const uint8_t* str, size_t len)
cannam@226: {
cannam@226: uint8_t* dup = (uint8_t*)malloc(len + 1);
cannam@226: memcpy(dup, str, len + 1);
cannam@226: return dup;
cannam@226: }
cannam@226:
cannam@226: SordNodeType
cannam@226: sord_node_get_type(const SordNode* node)
cannam@226: {
cannam@226: switch (node->node.type) {
cannam@226: case SERD_URI:
cannam@226: return SORD_URI;
cannam@226: case SERD_BLANK:
cannam@226: return SORD_BLANK;
cannam@226: default:
cannam@226: return SORD_LITERAL;
cannam@226: }
cannam@226: SORD_UNREACHABLE();
cannam@226: }
cannam@226:
cannam@226: const uint8_t*
cannam@226: sord_node_get_string(const SordNode* node)
cannam@226: {
cannam@226: return node->node.buf;
cannam@226: }
cannam@226:
cannam@226: const uint8_t*
cannam@226: sord_node_get_string_counted(const SordNode* node, size_t* bytes)
cannam@226: {
cannam@226: *bytes = node->node.n_bytes;
cannam@226: return node->node.buf;
cannam@226: }
cannam@226:
cannam@226: const uint8_t*
cannam@226: sord_node_get_string_measured(const SordNode* node,
cannam@226: size_t* bytes,
cannam@226: size_t* chars)
cannam@226: {
cannam@226: *bytes = node->node.n_bytes;
cannam@226: *chars = node->node.n_chars;
cannam@226: return node->node.buf;
cannam@226: }
cannam@226:
cannam@226: const char*
cannam@226: sord_node_get_language(const SordNode* node)
cannam@226: {
cannam@226: if (node->node.type != SERD_LITERAL || !node->meta.lit.lang[0]) {
cannam@226: return NULL;
cannam@226: }
cannam@226: return node->meta.lit.lang;
cannam@226: }
cannam@226:
cannam@226: SordNode*
cannam@226: sord_node_get_datatype(const SordNode* node)
cannam@226: {
cannam@226: return (node->node.type == SERD_LITERAL) ? node->meta.lit.datatype : NULL;
cannam@226: }
cannam@226:
cannam@226: SerdNodeFlags
cannam@226: sord_node_get_flags(const SordNode* node)
cannam@226: {
cannam@226: return node->node.flags;
cannam@226: }
cannam@226:
cannam@226: bool
cannam@226: sord_node_is_inline_object(const SordNode* node)
cannam@226: {
cannam@226: return (node->node.type == SERD_BLANK) && (node->meta.res.refs_as_obj == 1);
cannam@226: }
cannam@226:
cannam@226: static SordNode*
cannam@226: sord_insert_node(SordWorld* world, const SordNode* key, bool copy)
cannam@226: {
cannam@226: SordNode* node = NULL;
cannam@226: ZixStatus st = zix_hash_insert(world->nodes, key, (const void**)&node);
cannam@226: switch (st) {
cannam@226: case ZIX_STATUS_EXISTS:
cannam@226: ++node->refs;
cannam@226: break;
cannam@226: case ZIX_STATUS_SUCCESS:
cannam@226: assert(node->refs == 1);
cannam@226: if (copy) {
cannam@226: node->node.buf = sord_strndup(node->node.buf, node->node.n_bytes);
cannam@226: }
cannam@226: if (node->node.type == SERD_LITERAL) {
cannam@226: node->meta.lit.datatype = sord_node_copy(node->meta.lit.datatype);
cannam@226: }
cannam@226: return node;
cannam@226: default:
cannam@226: error(world, SERD_ERR_INTERNAL,
cannam@226: "error inserting node `%s'\n", key->node.buf);
cannam@226: }
cannam@226:
cannam@226: if (!copy) {
cannam@226: // Free the buffer we would have copied if a new node was created
cannam@226: free((uint8_t*)key->node.buf);
cannam@226: }
cannam@226:
cannam@226: return node;
cannam@226: }
cannam@226:
cannam@226: static SordNode*
cannam@226: sord_new_uri_counted(SordWorld* world, const uint8_t* str,
cannam@226: size_t n_bytes, size_t n_chars, bool copy)
cannam@226: {
cannam@226: if (!serd_uri_string_has_scheme(str)) {
cannam@226: error(world, SERD_ERR_BAD_ARG,
cannam@226: "attempt to map invalid URI `%s'\n", str);
cannam@226: return NULL; // Can't intern relative URIs
cannam@226: }
cannam@226:
cannam@226: const SordNode key = {
cannam@226: { str, n_bytes, n_chars, 0, SERD_URI }, 1, { { 0 } }
cannam@226: };
cannam@226:
cannam@226: return sord_insert_node(world, &key, copy);
cannam@226: }
cannam@226:
cannam@226: SordNode*
cannam@226: sord_new_uri(SordWorld* world, const uint8_t* str)
cannam@226: {
cannam@226: const SerdNode node = serd_node_from_string(SERD_URI, str);
cannam@226: return sord_new_uri_counted(world, str, node.n_bytes, node.n_chars, true);
cannam@226: }
cannam@226:
cannam@226: SordNode*
cannam@226: sord_new_relative_uri(SordWorld* world,
cannam@226: const uint8_t* str,
cannam@226: const uint8_t* base_str)
cannam@226: {
cannam@226: if (serd_uri_string_has_scheme(str)) {
cannam@226: return sord_new_uri(world, str);
cannam@226: }
cannam@226: SerdURI buri = SERD_URI_NULL;
cannam@226: SerdNode base = serd_node_new_uri_from_string(base_str, NULL, &buri);
cannam@226: SerdNode node = serd_node_new_uri_from_string(str, &buri, NULL);
cannam@226:
cannam@226: SordNode* ret = sord_new_uri_counted(
cannam@226: world, node.buf, node.n_bytes, node.n_chars, false);
cannam@226:
cannam@226: serd_node_free(&base);
cannam@226: return ret;
cannam@226: }
cannam@226:
cannam@226: static SordNode*
cannam@226: sord_new_blank_counted(SordWorld* world, const uint8_t* str,
cannam@226: size_t n_bytes, size_t n_chars)
cannam@226: {
cannam@226: const SordNode key = {
cannam@226: { str, n_bytes, n_chars, 0, SERD_BLANK }, 1, { { 0 } }
cannam@226: };
cannam@226:
cannam@226: return sord_insert_node(world, &key, true);
cannam@226: }
cannam@226:
cannam@226: SordNode*
cannam@226: sord_new_blank(SordWorld* world, const uint8_t* str)
cannam@226: {
cannam@226: const SerdNode node = serd_node_from_string(SERD_URI, str);
cannam@226: return sord_new_blank_counted(world, str, node.n_bytes, node.n_chars);
cannam@226: }
cannam@226:
cannam@226: static SordNode*
cannam@226: sord_new_literal_counted(SordWorld* world,
cannam@226: SordNode* datatype,
cannam@226: const uint8_t* str,
cannam@226: size_t n_bytes,
cannam@226: size_t n_chars,
cannam@226: SerdNodeFlags flags,
cannam@226: const char* lang)
cannam@226: {
cannam@226: SordNode key = {
cannam@226: { str, n_bytes, n_chars, flags, SERD_LITERAL }, 1, { { 0 } }
cannam@226: };
cannam@226: key.meta.lit.datatype = sord_node_copy(datatype);
cannam@226: memset(key.meta.lit.lang, 0, sizeof(key.meta.lit.lang));
cannam@226: if (lang) {
cannam@226: strncpy(key.meta.lit.lang, lang, sizeof(key.meta.lit.lang));
cannam@226: }
cannam@226:
cannam@226: return sord_insert_node(world, &key, true);
cannam@226: }
cannam@226:
cannam@226: SordNode*
cannam@226: sord_new_literal(SordWorld* world, SordNode* datatype,
cannam@226: const uint8_t* str, const char* lang)
cannam@226: {
cannam@226: SerdNodeFlags flags = 0;
cannam@226: size_t n_bytes = 0;
cannam@226: size_t n_chars = serd_strlen(str, &n_bytes, &flags);
cannam@226: return sord_new_literal_counted(world, datatype,
cannam@226: str, n_bytes, n_chars, flags,
cannam@226: lang);
cannam@226: }
cannam@226:
cannam@226: SordNode*
cannam@226: sord_node_from_serd_node(SordWorld* world,
cannam@226: SerdEnv* env,
cannam@226: const SerdNode* sn,
cannam@226: const SerdNode* datatype,
cannam@226: const SerdNode* lang)
cannam@226: {
cannam@226: if (!sn) {
cannam@226: return NULL;
cannam@226: }
cannam@226:
cannam@226: SordNode* datatype_node = NULL;
cannam@226: SordNode* ret = NULL;
cannam@226: switch (sn->type) {
cannam@226: case SERD_NOTHING:
cannam@226: return NULL;
cannam@226: case SERD_LITERAL:
cannam@226: datatype_node = sord_node_from_serd_node(
cannam@226: world, env, datatype, NULL, NULL),
cannam@226: ret = sord_new_literal_counted(
cannam@226: world,
cannam@226: datatype_node,
cannam@226: sn->buf,
cannam@226: sn->n_bytes,
cannam@226: sn->n_chars,
cannam@226: sn->flags,
cannam@226: lang ? (const char*)lang->buf : NULL);
cannam@226: sord_node_free(world, datatype_node);
cannam@226: return ret;
cannam@226: case SERD_URI:
cannam@226: if (serd_uri_string_has_scheme(sn->buf)) {
cannam@226: return sord_new_uri_counted(
cannam@226: world, sn->buf, sn->n_bytes, sn->n_chars, true);
cannam@226: } else {
cannam@226: SerdURI base_uri;
cannam@226: serd_env_get_base_uri(env, &base_uri);
cannam@226: SerdURI abs_uri;
cannam@226: SerdNode abs_uri_node = serd_node_new_uri_from_node(
cannam@226: sn, &base_uri, &abs_uri);
cannam@226: ret = sord_new_uri_counted(world,
cannam@226: abs_uri_node.buf,
cannam@226: abs_uri_node.n_bytes,
cannam@226: abs_uri_node.n_chars,
cannam@226: true);
cannam@226: serd_node_free(&abs_uri_node);
cannam@226: return ret;
cannam@226: }
cannam@226: case SERD_CURIE: {
cannam@226: SerdChunk uri_prefix;
cannam@226: SerdChunk uri_suffix;
cannam@226: if (serd_env_expand(env, sn, &uri_prefix, &uri_suffix)) {
cannam@226: error(world, SERD_ERR_BAD_CURIE,
cannam@226: "failed to expand CURIE `%s'\n", sn->buf);
cannam@226: return NULL;
cannam@226: }
cannam@226: const size_t uri_len = uri_prefix.len + uri_suffix.len;
cannam@226: uint8_t* buf = (uint8_t*)malloc(uri_len + 1);
cannam@226: memcpy(buf, uri_prefix.buf, uri_prefix.len);
cannam@226: memcpy(buf + uri_prefix.len, uri_suffix.buf, uri_suffix.len);
cannam@226: buf[uri_len] = '\0';
cannam@226: ret = sord_new_uri_counted(
cannam@226: world, buf, uri_len, serd_strlen(buf, NULL, NULL), false);
cannam@226: return ret;
cannam@226: }
cannam@226: case SERD_BLANK:
cannam@226: return sord_new_blank_counted(world, sn->buf, sn->n_bytes, sn->n_chars);
cannam@226: }
cannam@226: return NULL;
cannam@226: }
cannam@226:
cannam@226: const SerdNode*
cannam@226: sord_node_to_serd_node(const SordNode* node)
cannam@226: {
cannam@226: return node ? &node->node : &SERD_NODE_NULL;
cannam@226: }
cannam@226:
cannam@226: void
cannam@226: sord_node_free(SordWorld* world, SordNode* node)
cannam@226: {
cannam@226: if (!node) {
cannam@226: return;
cannam@226: } else if (node->refs == 0) {
cannam@226: error(world, SERD_ERR_BAD_ARG, "attempt to free garbage node\n");
cannam@226: } else if (--node->refs == 0) {
cannam@226: sord_node_free_internal(world, node);
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: SordNode*
cannam@226: sord_node_copy(const SordNode* node)
cannam@226: {
cannam@226: SordNode* copy = (SordNode*)node;
cannam@226: if (copy) {
cannam@226: ++copy->refs;
cannam@226: }
cannam@226: return copy;
cannam@226: }
cannam@226:
cannam@226: static inline bool
cannam@226: sord_add_to_index(SordModel* sord, const SordNode** tup, SordOrder order)
cannam@226: {
cannam@226: return !zix_btree_insert(sord->indices[order], tup);
cannam@226: }
cannam@226:
cannam@226: bool
cannam@226: sord_add(SordModel* sord, const SordQuad tup)
cannam@226: {
cannam@226: SORD_WRITE_LOG("Add " TUP_FMT "\n", TUP_FMT_ARGS(tup));
cannam@226: if (!tup[0] || !tup[1] || !tup[2]) {
cannam@226: error(sord->world, SERD_ERR_BAD_ARG,
cannam@226: "attempt to add quad with NULL field\n");
cannam@226: return false;
cannam@226: } else if (sord->n_iters > 0) {
cannam@226: error(sord->world, SERD_ERR_BAD_ARG, "added tuple during iteration\n");
cannam@226: }
cannam@226:
cannam@226: const SordNode** quad = (const SordNode**)malloc(sizeof(SordQuad));
cannam@226: memcpy(quad, tup, sizeof(SordQuad));
cannam@226:
cannam@226: for (unsigned i = 0; i < NUM_ORDERS; ++i) {
cannam@226: if (sord->indices[i] && (i < GSPO || tup[3])) {
cannam@226: if (!sord_add_to_index(sord, quad, (SordOrder)i)) {
cannam@226: assert(i == 0); // Assuming index coherency
cannam@226: free(quad);
cannam@226: return false; // Quad already stored, do nothing
cannam@226: }
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: for (int i = 0; i < TUP_LEN; ++i)
cannam@226: sord_add_quad_ref(sord, tup[i], (SordQuadIndex)i);
cannam@226:
cannam@226: ++sord->n_quads;
cannam@226: return true;
cannam@226: }
cannam@226:
cannam@226: void
cannam@226: sord_remove(SordModel* sord, const SordQuad tup)
cannam@226: {
cannam@226: SORD_WRITE_LOG("Remove " TUP_FMT "\n", TUP_FMT_ARGS(tup));
cannam@226: if (sord->n_iters > 0) {
cannam@226: error(sord->world, SERD_ERR_BAD_ARG, "remove with iterator\n");
cannam@226: }
cannam@226:
cannam@226: SordNode* quad = NULL;
cannam@226: for (unsigned i = 0; i < NUM_ORDERS; ++i) {
cannam@226: if (sord->indices[i] && (i < GSPO || tup[3])) {
cannam@226: if (zix_btree_remove(sord->indices[i], tup, (void**)&quad, NULL)) {
cannam@226: assert(i == 0); // Assuming index coherency
cannam@226: return; // Quad not found, do nothing
cannam@226: }
cannam@226: }
cannam@226: }
cannam@226:
cannam@226: free(quad);
cannam@226:
cannam@226: for (int i = 0; i < TUP_LEN; ++i)
cannam@226: sord_drop_quad_ref(sord, tup[i], (SordQuadIndex)i);
cannam@226:
cannam@226: --sord->n_quads;
cannam@226: }
cannam@226:
cannam@226: SerdStatus
cannam@226: sord_erase(SordModel* sord, SordIter* iter)
cannam@226: {
cannam@226: if (sord->n_iters > 1) {
cannam@226: error(sord->world, SERD_ERR_BAD_ARG, "erased with many iterators\n");
cannam@226: return SERD_ERR_BAD_ARG;
cannam@226: }
cannam@226:
cannam@226: SordQuad tup;
cannam@226: sord_iter_get(iter, tup);
cannam@226:
cannam@226: SORD_WRITE_LOG("Remove " TUP_FMT "\n", TUP_FMT_ARGS(tup));
cannam@226:
cannam@226: SordNode* quad = NULL;
cannam@226: for (unsigned i = 0; i < NUM_ORDERS; ++i) {
cannam@226: if (sord->indices[i] && (i < GSPO || tup[3])) {
cannam@226: if (zix_btree_remove(sord->indices[i], tup, (void**)&quad,
cannam@226: i == iter->order ? &iter->cur : NULL)) {
cannam@226: return (i == 0) ? SERD_ERR_NOT_FOUND : SERD_ERR_INTERNAL;
cannam@226: }
cannam@226: }
cannam@226: }
cannam@226: iter->end = zix_btree_iter_is_end(iter->cur);
cannam@226: sord_iter_scan_next(iter);
cannam@226:
cannam@226: free(quad);
cannam@226:
cannam@226: for (int i = 0; i < TUP_LEN; ++i)
cannam@226: sord_drop_quad_ref(sord, tup[i], (SordQuadIndex)i);
cannam@226:
cannam@226: --sord->n_quads;
cannam@226: return SERD_SUCCESS;
cannam@226: }