Cleanup
[carla.git] / source / modules / lilv / sord-0.16.0 / src / sord.c
blob218234b7bb7ba4f4e3f0215742e5119b376ba846
1 /*
2 Copyright 2011-2016 David Robillard <http://drobilla.net>
4 Permission to use, copy, modify, and/or distribute this software for any
5 purpose with or without fee is hereby granted, provided that the above
6 copyright notice and this permission notice appear in all copies.
8 THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 // C99
18 #include <assert.h>
19 #include <errno.h>
20 #include <stdint.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
25 #define ZIX_INLINE
26 #include "zix/digest.c"
27 #include "zix/hash.c"
28 #include "zix/btree.c"
30 #include "sord_config.h"
31 #include "sord_internal.h"
33 #define SORD_LOG(prefix, ...) fprintf(stderr, "[Sord::" prefix "] " __VA_ARGS__)
35 #ifdef SORD_DEBUG_ITER
36 # define SORD_ITER_LOG(...) SORD_LOG("iter", __VA_ARGS__)
37 #else
38 # define SORD_ITER_LOG(...)
39 #endif
40 #ifdef SORD_DEBUG_SEARCH
41 # define SORD_FIND_LOG(...) SORD_LOG("search", __VA_ARGS__)
42 #else
43 # define SORD_FIND_LOG(...)
44 #endif
45 #ifdef SORD_DEBUG_WRITE
46 # define SORD_WRITE_LOG(...) SORD_LOG("write", __VA_ARGS__)
47 #else
48 # define SORD_WRITE_LOG(...)
49 #endif
51 #define NUM_ORDERS 12
52 #define STATEMENT_LEN 3
53 #define TUP_LEN STATEMENT_LEN + 1
54 #define DEFAULT_ORDER SPO
55 #define DEFAULT_GRAPH_ORDER GSPO
57 #define TUP_FMT "(%s %s %s %s)"
58 #define TUP_FMT_ELEM(e) ((e) ? sord_node_get_string(e) : (const uint8_t*)"*")
59 #define TUP_FMT_ARGS(t) \
60 TUP_FMT_ELEM((t)[0]), \
61 TUP_FMT_ELEM((t)[1]), \
62 TUP_FMT_ELEM((t)[2]), \
63 TUP_FMT_ELEM((t)[3])
65 #define TUP_S 0
66 #define TUP_P 1
67 #define TUP_O 2
68 #define TUP_G 3
70 /** Triple ordering */
71 typedef enum {
72 SPO, ///< Subject, Predicate, Object
73 SOP, ///< Subject, Object, Predicate
74 OPS, ///< Object, Predicate, Subject
75 OSP, ///< Object, Subject, Predicate
76 PSO, ///< Predicate, Subject, Object
77 POS, ///< Predicate, Object, Subject
78 GSPO, ///< Graph, Subject, Predicate, Object
79 GSOP, ///< Graph, Subject, Object, Predicate
80 GOPS, ///< Graph, Object, Predicate, Subject
81 GOSP, ///< Graph, Object, Subject, Predicate
82 GPSO, ///< Graph, Predicate, Subject, Object
83 GPOS ///< Graph, Predicate, Object, Subject
84 } SordOrder;
86 #ifdef SORD_DEBUG_SEARCH
87 /** String name of each ordering (array indexed by SordOrder) */
88 static const char* const order_names[NUM_ORDERS] = {
89 "spo", "sop", "ops", "osp", "pso", "pos",
90 "gspo", "gsop", "gops", "gosp", "gpso", "gpos"
92 #endif
94 /**
95 Quads of indices for each order, from most to least significant
96 (array indexed by SordOrder)
98 static const int orderings[NUM_ORDERS][TUP_LEN] = {
99 { 0, 1, 2, 3 }, { 0, 2, 1, 3 }, // SPO, SOP
100 { 2, 1, 0, 3 }, { 2, 0, 1, 3 }, // OPS, OSP
101 { 1, 0, 2, 3 }, { 1, 2, 0, 3 }, // PSO, POS
102 { 3, 0, 1, 2 }, { 3, 0, 2, 1 }, // GSPO, GSOP
103 { 3, 2, 1, 0 }, { 3, 2, 0, 1 }, // GOPS, GOSP
104 { 3, 1, 0, 2 }, { 3, 1, 2, 0 } // GPSO, GPOS
107 /** World */
108 struct SordWorldImpl {
109 ZixHash* nodes;
110 SerdErrorSink error_sink;
111 void* error_handle;
114 /** Store */
115 struct SordModelImpl {
116 SordWorld* world;
118 /** Index for each possible triple ordering (may or may not exist).
119 * Each index is a tree of SordQuad with the appropriate ordering.
121 ZixBTree* indices[NUM_ORDERS];
123 size_t n_quads;
124 size_t n_iters;
127 /** Mode for searching or iteration */
128 typedef enum {
129 ALL, ///< Iterate over entire store
130 SINGLE, ///< Iteration over a single element (exact search)
131 RANGE, ///< Iterate over range with equal prefix
132 FILTER_RANGE, ///< Iterate over range with equal prefix, filtering
133 FILTER_ALL ///< Iterate to end of store, filtering
134 } SearchMode;
136 /** Iterator over some range of a store */
137 struct SordIterImpl {
138 const SordModel* sord; ///< Model being iterated over
139 ZixBTreeIter* cur; ///< Current DB cursor
140 SordQuad pat; ///< Pattern (in ordering order)
141 SordOrder order; ///< Store order (which index)
142 SearchMode mode; ///< Iteration mode
143 int n_prefix; ///< Prefix for RANGE and FILTER_RANGE
144 bool end; ///< True iff reached end
145 bool skip_graphs; ///< Iteration should ignore graphs
148 static uint32_t
149 sord_node_hash(const void* n)
151 const SordNode* node = (const SordNode*)n;
152 uint32_t hash = zix_digest_start();
153 hash = zix_digest_add(hash, node->node.buf, node->node.n_bytes);
154 hash = zix_digest_add(hash, &node->node.type, sizeof(node->node.type));
155 if (node->node.type == SERD_LITERAL) {
156 hash = zix_digest_add(hash, &node->meta.lit, sizeof(node->meta.lit));
158 return hash;
161 static bool
162 sord_node_hash_equal(const void* a, const void* b)
164 const SordNode* a_node = (const SordNode*)a;
165 const SordNode* b_node = (const SordNode*)b;
166 return (a_node == b_node)
167 || ((a_node->node.type == b_node->node.type) &&
168 (a_node->node.type != SERD_LITERAL ||
169 (a_node->meta.lit.datatype == b_node->meta.lit.datatype &&
170 !strncmp(a_node->meta.lit.lang,
171 b_node->meta.lit.lang,
172 sizeof(a_node->meta.lit.lang)))) &&
173 (serd_node_equals(&a_node->node, &b_node->node)));
176 static void
177 error(SordWorld* world, SerdStatus st, const char* fmt, ...)
179 va_list args;
180 va_start(args, fmt);
181 const SerdError e = { st, NULL, 0, 0, fmt, &args };
182 if (world->error_sink) {
183 world->error_sink(world->error_handle, &e);
184 } else {
185 fprintf(stderr, "error: ");
186 vfprintf(stderr, fmt, args);
188 va_end(args);
191 SordWorld*
192 sord_world_new(void)
194 SordWorld* world = (SordWorld*)malloc(sizeof(SordWorld));
195 world->error_sink = NULL;
196 world->error_handle = NULL;
198 world->nodes = zix_hash_new(
199 sord_node_hash, sord_node_hash_equal, sizeof(SordNode));
201 return world;
204 static void
205 free_node_entry(void* value, void* user_data)
207 SordNode* node = (SordNode*)value;
208 if (node->node.type == SERD_LITERAL) {
209 sord_node_free((SordWorld*)user_data, node->meta.lit.datatype);
211 free((uint8_t*)node->node.buf);
214 void
215 sord_world_free(SordWorld* world)
217 zix_hash_foreach(world->nodes, free_node_entry, world);
218 zix_hash_free(world->nodes);
219 free(world);
222 void
223 sord_world_set_error_sink(SordWorld* world,
224 SerdErrorSink error_sink,
225 void* handle)
227 world->error_sink = error_sink;
228 world->error_handle = handle;
231 /** Compare nodes, considering NULL a wildcard match. */
232 static inline int
233 sord_node_compare(const SordNode* a, const SordNode* b)
235 if (a == b || !a || !b) {
236 return 0; // Exact or wildcard match
237 } else if (a->node.type != b->node.type) {
238 return a->node.type - b->node.type;
241 int cmp = 0;
242 switch (a->node.type) {
243 case SERD_URI:
244 case SERD_BLANK:
245 return strcmp((const char*)a->node.buf, (const char*)b->node.buf);
246 case SERD_LITERAL:
247 cmp = strcmp((const char*)sord_node_get_string(a),
248 (const char*)sord_node_get_string(b));
249 if (cmp == 0) {
250 // Note: Can't use sord_node_compare here since it does wildcards
251 if (!a->meta.lit.datatype || !b->meta.lit.datatype) {
252 cmp = a->meta.lit.datatype - b->meta.lit.datatype;
253 } else {
254 cmp = strcmp((const char*)a->meta.lit.datatype->node.buf,
255 (const char*)b->meta.lit.datatype->node.buf);
258 if (cmp == 0) {
259 cmp = strcmp(a->meta.lit.lang, b->meta.lit.lang);
261 default:
262 break;
264 return cmp;
267 bool
268 sord_node_equals(const SordNode* a, const SordNode* b)
270 return a == b; // Nodes are interned
273 /** Return true iff IDs are equivalent, or one is a wildcard */
274 static inline bool
275 sord_id_match(const SordNode* a, const SordNode* b)
277 return !a || !b || (a == b);
280 static inline bool
281 sord_quad_match_inline(const SordQuad x, const SordQuad y)
283 return sord_id_match(x[0], y[0])
284 && sord_id_match(x[1], y[1])
285 && sord_id_match(x[2], y[2])
286 && sord_id_match(x[3], y[3]);
289 bool
290 sord_quad_match(const SordQuad x, const SordQuad y)
292 return sord_quad_match_inline(x, y);
296 Compare two quad IDs lexicographically.
297 NULL IDs (equal to 0) are treated as wildcards, always less than every
298 other possible ID, except itself.
300 static int
301 sord_quad_compare(const void* x_ptr, const void* y_ptr, void* user_data)
303 const int* const ordering = (const int*)user_data;
304 const SordNode*const*const x = (const SordNode*const*)x_ptr;
305 const SordNode*const*const y = (const SordNode*const*)y_ptr;
307 for (int i = 0; i < TUP_LEN; ++i) {
308 const int idx = ordering[i];
309 const int cmp = sord_node_compare(x[idx], y[idx]);
310 if (cmp) {
311 return cmp;
315 return 0;
318 static inline bool
319 sord_iter_forward(SordIter* iter)
321 if (!iter->skip_graphs) {
322 zix_btree_iter_increment(iter->cur);
323 return zix_btree_iter_is_end(iter->cur);
326 SordNode** key = (SordNode**)zix_btree_get(iter->cur);
327 const SordQuad initial = { key[0], key[1], key[2], key[3] };
328 zix_btree_iter_increment(iter->cur);
329 while (!zix_btree_iter_is_end(iter->cur)) {
330 key = (SordNode**)zix_btree_get(iter->cur);
331 for (int i = 0; i < 3; ++i)
332 if (key[i] != initial[i])
333 return false;
335 zix_btree_iter_increment(iter->cur);
338 return true;
342 Seek forward as necessary until `iter` points at a match.
343 @return true iff iterator reached end of valid range.
345 static inline bool
346 sord_iter_seek_match(SordIter* iter)
348 for (iter->end = true;
349 !zix_btree_iter_is_end(iter->cur);
350 sord_iter_forward(iter)) {
351 const SordNode** const key = (const SordNode**)zix_btree_get(iter->cur);
352 if (sord_quad_match_inline(key, iter->pat))
353 return (iter->end = false);
355 return true;
359 Seek forward as necessary until `iter` points at a match, or the prefix
360 no longer matches iter->pat.
361 @return true iff iterator reached end of valid range.
363 static inline bool
364 sord_iter_seek_match_range(SordIter* iter)
366 assert(!iter->end);
368 do {
369 const SordNode** key = (const SordNode**)zix_btree_get(iter->cur);
371 if (sord_quad_match_inline(key, iter->pat))
372 return false; // Found match
374 for (int i = 0; i < iter->n_prefix; ++i) {
375 const int idx = orderings[iter->order][i];
376 if (!sord_id_match(key[idx], iter->pat[idx])) {
377 iter->end = true; // Reached end of valid range
378 return true;
381 } while (!sord_iter_forward(iter));
383 return (iter->end = true); // Reached end
386 static SordIter*
387 sord_iter_new(const SordModel* sord, ZixBTreeIter* cur, const SordQuad pat,
388 SordOrder order, SearchMode mode, int n_prefix)
390 SordIter* iter = (SordIter*)malloc(sizeof(SordIter));
391 iter->sord = sord;
392 iter->cur = cur;
393 iter->order = order;
394 iter->mode = mode;
395 iter->n_prefix = n_prefix;
396 iter->end = false;
397 iter->skip_graphs = order < GSPO;
398 for (int i = 0; i < TUP_LEN; ++i) {
399 iter->pat[i] = pat[i];
402 switch (iter->mode) {
403 case ALL:
404 case SINGLE:
405 case RANGE:
406 assert(
407 sord_quad_match_inline((const SordNode**)zix_btree_get(iter->cur),
408 iter->pat));
409 break;
410 case FILTER_RANGE:
411 sord_iter_seek_match_range(iter);
412 break;
413 case FILTER_ALL:
414 sord_iter_seek_match(iter);
415 break;
418 #ifdef SORD_DEBUG_ITER
419 SordQuad value;
420 sord_iter_get(iter, value);
421 SORD_ITER_LOG("New %p pat=" TUP_FMT " cur=" TUP_FMT " end=%d skip=%d\n",
422 (void*)iter, TUP_FMT_ARGS(pat), TUP_FMT_ARGS(value),
423 iter->end, iter->skip_graphs);
424 #endif
426 ++((SordModel*)sord)->n_iters;
427 return iter;
430 const SordModel*
431 sord_iter_get_model(SordIter* iter)
433 return iter->sord;
436 void
437 sord_iter_get(const SordIter* iter, SordQuad id)
439 SordNode** key = (SordNode**)zix_btree_get(iter->cur);
440 for (int i = 0; i < TUP_LEN; ++i) {
441 id[i] = key[i];
445 const SordNode*
446 sord_iter_get_node(const SordIter* iter, SordQuadIndex index)
448 return (!sord_iter_end(iter)
449 ? ((SordNode**)zix_btree_get(iter->cur))[index]
450 : NULL);
453 static bool
454 sord_iter_scan_next(SordIter* iter)
456 if (iter->end) {
457 return true;
460 const SordNode** key;
461 if (!iter->end) {
462 switch (iter->mode) {
463 case ALL:
464 // At the end if the cursor is (assigned above)
465 break;
466 case SINGLE:
467 iter->end = true;
468 SORD_ITER_LOG("%p reached single end\n", (void*)iter);
469 break;
470 case RANGE:
471 SORD_ITER_LOG("%p range next\n", (void*)iter);
472 // At the end if the MSNs no longer match
473 key = (const SordNode**)zix_btree_get(iter->cur);
474 assert(key);
475 for (int i = 0; i < iter->n_prefix; ++i) {
476 const int idx = orderings[iter->order][i];
477 if (!sord_id_match(key[idx], iter->pat[idx])) {
478 iter->end = true;
479 SORD_ITER_LOG("%p reached non-match end\n", (void*)iter);
480 break;
483 break;
484 case FILTER_RANGE:
485 // Seek forward to next match, stopping if prefix changes
486 sord_iter_seek_match_range(iter);
487 break;
488 case FILTER_ALL:
489 // Seek forward to next match
490 sord_iter_seek_match(iter);
491 break;
493 } else {
494 SORD_ITER_LOG("%p reached index end\n", (void*)iter);
497 if (iter->end) {
498 SORD_ITER_LOG("%p Reached end\n", (void*)iter);
499 return true;
500 } else {
501 #ifdef SORD_DEBUG_ITER
502 SordQuad tup;
503 sord_iter_get(iter, tup);
504 SORD_ITER_LOG("%p Increment to " TUP_FMT "\n",
505 (void*)iter, TUP_FMT_ARGS(tup));
506 #endif
507 return false;
511 bool
512 sord_iter_next(SordIter* iter)
514 if (iter->end) {
515 return true;
518 iter->end = sord_iter_forward(iter);
519 return sord_iter_scan_next(iter);
522 bool
523 sord_iter_end(const SordIter* iter)
525 return !iter || iter->end;
528 void
529 sord_iter_free(SordIter* iter)
531 SORD_ITER_LOG("%p Free\n", (void*)iter);
532 if (iter) {
533 --((SordModel*)iter->sord)->n_iters;
534 zix_btree_iter_free(iter->cur);
535 free(iter);
540 Return true iff `sord` has an index for `order`.
541 If `graphs` is true, `order` will be modified to be the
542 corresponding order with a G prepended (so G will be the MSN).
544 static inline bool
545 sord_has_index(SordModel* sord, SordOrder* order, int* n_prefix, bool graphs)
547 if (graphs) {
548 *order = (SordOrder)(*order + GSPO);
549 *n_prefix += 1;
552 return sord->indices[*order];
556 Return the best available index for a pattern.
557 @param pat Pattern in standard (S P O G) order
558 @param mode Set to the (best) iteration mode for iterating over results
559 @param n_prefix Set to the length of the range prefix
560 (for `mode` == RANGE and `mode` == FILTER_RANGE)
562 static inline SordOrder
563 sord_best_index(SordModel* sord,
564 const SordQuad pat,
565 SearchMode* mode,
566 int* n_prefix)
568 const bool graph_search = (pat[TUP_G] != 0);
570 const unsigned sig
571 = (pat[0] ? 1 : 0) * 0x100
572 + (pat[1] ? 1 : 0) * 0x010
573 + (pat[2] ? 1 : 0) * 0x001;
575 SordOrder good[2] = { (SordOrder)-1, (SordOrder)-1 };
577 #define PAT_CASE(sig, m, g0, g1, np) \
578 case sig: \
579 *mode = m; \
580 good[0] = g0; \
581 good[1] = g1; \
582 *n_prefix = np; \
583 break
585 // Good orderings that don't require filtering
586 *mode = RANGE;
587 *n_prefix = 0;
588 switch (sig) {
589 case 0x000:
590 assert(graph_search);
591 *mode = RANGE;
592 *n_prefix = 1;
593 return DEFAULT_GRAPH_ORDER;
594 case 0x111:
595 *mode = SINGLE;
596 return graph_search ? DEFAULT_GRAPH_ORDER : DEFAULT_ORDER;
598 PAT_CASE(0x001, RANGE, OPS, OSP, 1);
599 PAT_CASE(0x010, RANGE, POS, PSO, 1);
600 PAT_CASE(0x011, RANGE, OPS, POS, 2);
601 PAT_CASE(0x100, RANGE, SPO, SOP, 1);
602 PAT_CASE(0x101, RANGE, SOP, OSP, 2);
603 PAT_CASE(0x110, RANGE, SPO, PSO, 2);
606 if (*mode == RANGE) {
607 if (sord_has_index(sord, &good[0], n_prefix, graph_search)) {
608 return good[0];
609 } else if (sord_has_index(sord, &good[1], n_prefix, graph_search)) {
610 return good[1];
614 // Not so good orderings that require filtering, but can
615 // still be constrained to a range
616 switch (sig) {
617 PAT_CASE(0x011, FILTER_RANGE, OSP, PSO, 1);
618 PAT_CASE(0x101, FILTER_RANGE, SPO, OPS, 1);
619 // SPO is always present, so 0x110 is never reached here
620 default: break;
623 if (*mode == FILTER_RANGE) {
624 if (sord_has_index(sord, &good[0], n_prefix, graph_search)) {
625 return good[0];
626 } else if (sord_has_index(sord, &good[1], n_prefix, graph_search)) {
627 return good[1];
631 if (graph_search) {
632 *mode = FILTER_RANGE;
633 *n_prefix = 1;
634 return DEFAULT_GRAPH_ORDER;
635 } else {
636 *mode = FILTER_ALL;
637 return DEFAULT_ORDER;
641 SordModel*
642 sord_new(SordWorld* world, unsigned indices, bool graphs)
644 SordModel* sord = (SordModel*)malloc(sizeof(struct SordModelImpl));
645 sord->world = world;
646 sord->n_quads = 0;
647 sord->n_iters = 0;
649 for (unsigned i = 0; i < (NUM_ORDERS / 2); ++i) {
650 const int* const ordering = orderings[i];
651 const int* const g_ordering = orderings[i + (NUM_ORDERS / 2)];
653 if (indices & (1 << i)) {
654 sord->indices[i] = zix_btree_new(
655 sord_quad_compare, (void*)ordering, NULL);
656 if (graphs) {
657 sord->indices[i + (NUM_ORDERS / 2)] = zix_btree_new(
658 sord_quad_compare, (void*)g_ordering, NULL);
659 } else {
660 sord->indices[i + (NUM_ORDERS / 2)] = NULL;
662 } else {
663 sord->indices[i] = NULL;
664 sord->indices[i + (NUM_ORDERS / 2)] = NULL;
668 if (!sord->indices[DEFAULT_ORDER]) {
669 sord->indices[DEFAULT_ORDER] = zix_btree_new(
670 sord_quad_compare, (void*)orderings[DEFAULT_ORDER], NULL);
672 if (graphs && !sord->indices[DEFAULT_GRAPH_ORDER]) {
673 sord->indices[DEFAULT_GRAPH_ORDER] = zix_btree_new(
674 sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER], NULL);
677 return sord;
680 static void
681 sord_node_free_internal(SordWorld* world, SordNode* node)
683 assert(node->refs == 0);
685 // Cache pointer to buffer to free after node removal and destruction
686 const uint8_t* const buf = node->node.buf;
688 // Remove node from hash (which frees the node)
689 if (zix_hash_remove(world->nodes, node)) {
690 error(world, SERD_ERR_INTERNAL, "failed to remove node from hash\n");
693 // Free buffer
694 free((uint8_t*)buf);
697 static void
698 sord_add_quad_ref(SordModel* sord, const SordNode* node, SordQuadIndex i)
700 if (node) {
701 assert(node->refs > 0);
702 ++((SordNode*)node)->refs;
703 if (node->node.type != SERD_LITERAL && i == SORD_OBJECT) {
704 ++((SordNode*)node)->meta.res.refs_as_obj;
709 static void
710 sord_drop_quad_ref(SordModel* sord, const SordNode* node, SordQuadIndex i)
712 if (!node) {
713 return;
716 assert(node->refs > 0);
717 if (node->node.type != SERD_LITERAL && i == SORD_OBJECT) {
718 assert(node->meta.res.refs_as_obj > 0);
719 --((SordNode*)node)->meta.res.refs_as_obj;
721 if (--((SordNode*)node)->refs == 0) {
722 sord_node_free_internal(sord_get_world(sord), (SordNode*)node);
726 void
727 sord_free(SordModel* sord)
729 if (!sord)
730 return;
732 // Free nodes
733 SordQuad tup;
734 SordIter* i = sord_begin(sord);
735 for (; !sord_iter_end(i); sord_iter_next(i)) {
736 sord_iter_get(i, tup);
737 for (int t = 0; t < TUP_LEN; ++t) {
738 sord_drop_quad_ref(sord, tup[t], (SordQuadIndex)t);
741 sord_iter_free(i);
743 // Free quads
744 ZixBTreeIter* t = zix_btree_begin(sord->indices[DEFAULT_ORDER]);
745 for (; !zix_btree_iter_is_end(t); zix_btree_iter_increment(t)) {
746 free(zix_btree_get(t));
748 zix_btree_iter_free(t);
750 // Free indices
751 for (unsigned o = 0; o < NUM_ORDERS; ++o)
752 if (sord->indices[o])
753 zix_btree_free(sord->indices[o]);
755 free(sord);
758 SordWorld*
759 sord_get_world(SordModel* sord)
761 return sord->world;
764 size_t
765 sord_num_quads(const SordModel* sord)
767 return sord->n_quads;
770 size_t
771 sord_num_nodes(const SordWorld* world)
773 return zix_hash_size(world->nodes);
776 SordIter*
777 sord_begin(const SordModel* sord)
779 if (sord_num_quads(sord) == 0) {
780 return NULL;
781 } else {
782 ZixBTreeIter* cur = zix_btree_begin(sord->indices[DEFAULT_ORDER]);
783 SordQuad pat = { 0, 0, 0, 0 };
784 return sord_iter_new(sord, cur, pat, DEFAULT_ORDER, ALL, 0);
788 SordIter*
789 sord_find(SordModel* sord, const SordQuad pat)
791 if (!pat[0] && !pat[1] && !pat[2] && !pat[3])
792 return sord_begin(sord);
794 SearchMode mode;
795 int n_prefix;
796 const SordOrder index_order = sord_best_index(sord, pat, &mode, &n_prefix);
798 SORD_FIND_LOG("Find " TUP_FMT " index=%s mode=%d n_prefix=%d\n",
799 TUP_FMT_ARGS(pat), order_names[index_order], mode, n_prefix);
801 if (pat[0] && pat[1] && pat[2] && pat[3])
802 mode = SINGLE; // No duplicate quads (Sord is a set)
804 ZixBTree* const db = sord->indices[index_order];
805 ZixBTreeIter* cur = NULL;
806 zix_btree_lower_bound(db, pat, &cur);
807 if (zix_btree_iter_is_end(cur)) {
808 SORD_FIND_LOG("No match found\n");
809 zix_btree_iter_free(cur);
810 return NULL;
812 const SordNode** const key = (const SordNode**)zix_btree_get(cur);
813 if (!key || ( (mode == RANGE || mode == SINGLE)
814 && !sord_quad_match_inline(pat, key) )) {
815 SORD_FIND_LOG("No match found\n");
816 zix_btree_iter_free(cur);
817 return NULL;
820 return sord_iter_new(sord, cur, pat, index_order, mode, n_prefix);
823 SordIter*
824 sord_search(SordModel* model,
825 const SordNode* s,
826 const SordNode* p,
827 const SordNode* o,
828 const SordNode* g)
830 SordQuad pat = { s, p, o, g };
831 return sord_find(model, pat);
834 SordNode*
835 sord_get(SordModel* model,
836 const SordNode* s,
837 const SordNode* p,
838 const SordNode* o,
839 const SordNode* g)
841 if ((bool)s + (bool)p + (bool)o != 2) {
842 return NULL;
845 SordIter* i = sord_search(model, s, p, o, g);
846 SordNode* ret = NULL;
847 if (!s) {
848 ret = sord_node_copy(sord_iter_get_node(i, SORD_SUBJECT));
849 } else if (!p) {
850 ret = sord_node_copy(sord_iter_get_node(i, SORD_PREDICATE));
851 } else if (!o) {
852 ret = sord_node_copy(sord_iter_get_node(i, SORD_OBJECT));
855 sord_iter_free(i);
856 return ret;
859 bool
860 sord_ask(SordModel* model,
861 const SordNode* s,
862 const SordNode* p,
863 const SordNode* o,
864 const SordNode* g)
866 SordQuad pat = { s, p, o, g };
867 return sord_contains(model, pat);
870 uint64_t
871 sord_count(SordModel* model,
872 const SordNode* s,
873 const SordNode* p,
874 const SordNode* o,
875 const SordNode* g)
877 SordIter* i = sord_search(model, s, p, o, g);
878 uint64_t n = 0;
879 for (; !sord_iter_end(i); sord_iter_next(i)) {
880 ++n;
882 sord_iter_free(i);
883 return n;
886 bool
887 sord_contains(SordModel* sord, const SordQuad pat)
889 SordIter* iter = sord_find(sord, pat);
890 bool ret = (iter != NULL);
891 sord_iter_free(iter);
892 return ret;
895 static uint8_t*
896 sord_strndup(const uint8_t* str, size_t len)
898 uint8_t* dup = (uint8_t*)malloc(len + 1);
899 memcpy(dup, str, len + 1);
900 return dup;
903 SordNodeType
904 sord_node_get_type(const SordNode* node)
906 switch (node->node.type) {
907 case SERD_URI:
908 return SORD_URI;
909 case SERD_BLANK:
910 return SORD_BLANK;
911 default:
912 return SORD_LITERAL;
914 SORD_UNREACHABLE();
917 const uint8_t*
918 sord_node_get_string(const SordNode* node)
920 return node->node.buf;
923 const uint8_t*
924 sord_node_get_string_counted(const SordNode* node, size_t* bytes)
926 *bytes = node->node.n_bytes;
927 return node->node.buf;
930 const uint8_t*
931 sord_node_get_string_measured(const SordNode* node,
932 size_t* bytes,
933 size_t* chars)
935 *bytes = node->node.n_bytes;
936 *chars = node->node.n_chars;
937 return node->node.buf;
940 const char*
941 sord_node_get_language(const SordNode* node)
943 if (node->node.type != SERD_LITERAL || !node->meta.lit.lang[0]) {
944 return NULL;
946 return node->meta.lit.lang;
949 SordNode*
950 sord_node_get_datatype(const SordNode* node)
952 return (node->node.type == SERD_LITERAL) ? node->meta.lit.datatype : NULL;
955 SerdNodeFlags
956 sord_node_get_flags(const SordNode* node)
958 return node->node.flags;
961 bool
962 sord_node_is_inline_object(const SordNode* node)
964 return (node->node.type == SERD_BLANK) && (node->meta.res.refs_as_obj == 1);
967 static SordNode*
968 sord_insert_node(SordWorld* world, const SordNode* key, bool copy)
970 SordNode* node = NULL;
971 ZixStatus st = zix_hash_insert(world->nodes, key, (const void**)&node);
972 switch (st) {
973 case ZIX_STATUS_EXISTS:
974 ++node->refs;
975 break;
976 case ZIX_STATUS_SUCCESS:
977 assert(node->refs == 1);
978 if (copy) {
979 node->node.buf = sord_strndup(node->node.buf, node->node.n_bytes);
981 if (node->node.type == SERD_LITERAL) {
982 node->meta.lit.datatype = sord_node_copy(node->meta.lit.datatype);
984 return node;
985 default:
986 error(world, SERD_ERR_INTERNAL,
987 "error inserting node `%s'\n", key->node.buf);
990 if (!copy) {
991 // Free the buffer we would have copied if a new node was created
992 free((uint8_t*)key->node.buf);
995 return node;
998 static SordNode*
999 sord_new_uri_counted(SordWorld* world, const uint8_t* str,
1000 size_t n_bytes, size_t n_chars, bool copy)
1002 if (!serd_uri_string_has_scheme(str)) {
1003 error(world, SERD_ERR_BAD_ARG,
1004 "attempt to map invalid URI `%s'\n", str);
1005 return NULL; // Can't intern relative URIs
1008 const SordNode key = {
1009 { str, n_bytes, n_chars, 0, SERD_URI }, 1, { { 0 } }
1012 return sord_insert_node(world, &key, copy);
1015 SordNode*
1016 sord_new_uri(SordWorld* world, const uint8_t* str)
1018 const SerdNode node = serd_node_from_string(SERD_URI, str);
1019 return sord_new_uri_counted(world, str, node.n_bytes, node.n_chars, true);
1022 SordNode*
1023 sord_new_relative_uri(SordWorld* world,
1024 const uint8_t* str,
1025 const uint8_t* base_str)
1027 if (serd_uri_string_has_scheme(str)) {
1028 return sord_new_uri(world, str);
1030 SerdURI buri = SERD_URI_NULL;
1031 SerdNode base = serd_node_new_uri_from_string(base_str, NULL, &buri);
1032 SerdNode node = serd_node_new_uri_from_string(str, &buri, NULL);
1034 SordNode* ret = sord_new_uri_counted(
1035 world, node.buf, node.n_bytes, node.n_chars, false);
1037 serd_node_free(&base);
1038 return ret;
1041 static SordNode*
1042 sord_new_blank_counted(SordWorld* world, const uint8_t* str,
1043 size_t n_bytes, size_t n_chars)
1045 const SordNode key = {
1046 { str, n_bytes, n_chars, 0, SERD_BLANK }, 1, { { 0 } }
1049 return sord_insert_node(world, &key, true);
1052 SordNode*
1053 sord_new_blank(SordWorld* world, const uint8_t* str)
1055 const SerdNode node = serd_node_from_string(SERD_URI, str);
1056 return sord_new_blank_counted(world, str, node.n_bytes, node.n_chars);
1059 static SordNode*
1060 sord_new_literal_counted(SordWorld* world,
1061 SordNode* datatype,
1062 const uint8_t* str,
1063 size_t n_bytes,
1064 size_t n_chars,
1065 SerdNodeFlags flags,
1066 const char* lang)
1068 SordNode key = {
1069 { str, n_bytes, n_chars, flags, SERD_LITERAL }, 1, { { 0 } }
1071 key.meta.lit.datatype = sord_node_copy(datatype);
1072 memset(key.meta.lit.lang, 0, sizeof(key.meta.lit.lang));
1073 if (lang) {
1074 strncpy(key.meta.lit.lang, lang, sizeof(key.meta.lit.lang));
1077 return sord_insert_node(world, &key, true);
1080 SordNode*
1081 sord_new_literal(SordWorld* world, SordNode* datatype,
1082 const uint8_t* str, const char* lang)
1084 SerdNodeFlags flags = 0;
1085 size_t n_bytes = 0;
1086 size_t n_chars = serd_strlen(str, &n_bytes, &flags);
1087 return sord_new_literal_counted(world, datatype,
1088 str, n_bytes, n_chars, flags,
1089 lang);
1092 SordNode*
1093 sord_node_from_serd_node(SordWorld* world,
1094 SerdEnv* env,
1095 const SerdNode* sn,
1096 const SerdNode* datatype,
1097 const SerdNode* lang)
1099 if (!sn) {
1100 return NULL;
1103 SordNode* datatype_node = NULL;
1104 SordNode* ret = NULL;
1105 switch (sn->type) {
1106 case SERD_NOTHING:
1107 return NULL;
1108 case SERD_LITERAL:
1109 datatype_node = sord_node_from_serd_node(
1110 world, env, datatype, NULL, NULL),
1111 ret = sord_new_literal_counted(
1112 world,
1113 datatype_node,
1114 sn->buf,
1115 sn->n_bytes,
1116 sn->n_chars,
1117 sn->flags,
1118 lang ? (const char*)lang->buf : NULL);
1119 sord_node_free(world, datatype_node);
1120 return ret;
1121 case SERD_URI:
1122 if (serd_uri_string_has_scheme(sn->buf)) {
1123 return sord_new_uri_counted(
1124 world, sn->buf, sn->n_bytes, sn->n_chars, true);
1125 } else {
1126 SerdURI base_uri;
1127 serd_env_get_base_uri(env, &base_uri);
1128 SerdURI abs_uri;
1129 SerdNode abs_uri_node = serd_node_new_uri_from_node(
1130 sn, &base_uri, &abs_uri);
1131 ret = sord_new_uri_counted(world,
1132 abs_uri_node.buf,
1133 abs_uri_node.n_bytes,
1134 abs_uri_node.n_chars,
1135 true);
1136 serd_node_free(&abs_uri_node);
1137 return ret;
1139 case SERD_CURIE: {
1140 SerdChunk uri_prefix;
1141 SerdChunk uri_suffix;
1142 if (serd_env_expand(env, sn, &uri_prefix, &uri_suffix)) {
1143 error(world, SERD_ERR_BAD_CURIE,
1144 "failed to expand CURIE `%s'\n", sn->buf);
1145 return NULL;
1147 const size_t uri_len = uri_prefix.len + uri_suffix.len;
1148 uint8_t* buf = (uint8_t*)malloc(uri_len + 1);
1149 memcpy(buf, uri_prefix.buf, uri_prefix.len);
1150 memcpy(buf + uri_prefix.len, uri_suffix.buf, uri_suffix.len);
1151 buf[uri_len] = '\0';
1152 ret = sord_new_uri_counted(
1153 world, buf, uri_len, serd_strlen(buf, NULL, NULL), false);
1154 return ret;
1156 case SERD_BLANK:
1157 return sord_new_blank_counted(world, sn->buf, sn->n_bytes, sn->n_chars);
1159 return NULL;
1162 const SerdNode*
1163 sord_node_to_serd_node(const SordNode* node)
1165 return node ? &node->node : &SERD_NODE_NULL;
1168 void
1169 sord_node_free(SordWorld* world, SordNode* node)
1171 if (!node) {
1172 return;
1173 } else if (node->refs == 0) {
1174 error(world, SERD_ERR_BAD_ARG, "attempt to free garbage node\n");
1175 } else if (--node->refs == 0) {
1176 sord_node_free_internal(world, node);
1180 SordNode*
1181 sord_node_copy(const SordNode* node)
1183 SordNode* copy = (SordNode*)node;
1184 if (copy) {
1185 ++copy->refs;
1187 return copy;
1190 static inline bool
1191 sord_add_to_index(SordModel* sord, const SordNode** tup, SordOrder order)
1193 return !zix_btree_insert(sord->indices[order], tup);
1196 bool
1197 sord_add(SordModel* sord, const SordQuad tup)
1199 SORD_WRITE_LOG("Add " TUP_FMT "\n", TUP_FMT_ARGS(tup));
1200 if (!tup[0] || !tup[1] || !tup[2]) {
1201 error(sord->world, SERD_ERR_BAD_ARG,
1202 "attempt to add quad with NULL field\n");
1203 return false;
1204 } else if (sord->n_iters > 0) {
1205 error(sord->world, SERD_ERR_BAD_ARG, "added tuple during iteration\n");
1208 const SordNode** quad = (const SordNode**)malloc(sizeof(SordQuad));
1209 memcpy(quad, tup, sizeof(SordQuad));
1211 for (unsigned i = 0; i < NUM_ORDERS; ++i) {
1212 if (sord->indices[i] && (i < GSPO || tup[3])) {
1213 if (!sord_add_to_index(sord, quad, (SordOrder)i)) {
1214 assert(i == 0); // Assuming index coherency
1215 free(quad);
1216 return false; // Quad already stored, do nothing
1221 for (int i = 0; i < TUP_LEN; ++i)
1222 sord_add_quad_ref(sord, tup[i], (SordQuadIndex)i);
1224 ++sord->n_quads;
1225 return true;
1228 void
1229 sord_remove(SordModel* sord, const SordQuad tup)
1231 SORD_WRITE_LOG("Remove " TUP_FMT "\n", TUP_FMT_ARGS(tup));
1232 if (sord->n_iters > 0) {
1233 error(sord->world, SERD_ERR_BAD_ARG, "remove with iterator\n");
1236 SordNode* quad = NULL;
1237 for (unsigned i = 0; i < NUM_ORDERS; ++i) {
1238 if (sord->indices[i] && (i < GSPO || tup[3])) {
1239 if (zix_btree_remove(sord->indices[i], tup, (void**)&quad, NULL)) {
1240 assert(i == 0); // Assuming index coherency
1241 return; // Quad not found, do nothing
1246 free(quad);
1248 for (int i = 0; i < TUP_LEN; ++i)
1249 sord_drop_quad_ref(sord, tup[i], (SordQuadIndex)i);
1251 --sord->n_quads;
1254 SerdStatus
1255 sord_erase(SordModel* sord, SordIter* iter)
1257 if (sord->n_iters > 1) {
1258 error(sord->world, SERD_ERR_BAD_ARG, "erased with many iterators\n");
1259 return SERD_ERR_BAD_ARG;
1262 SordQuad tup;
1263 sord_iter_get(iter, tup);
1265 SORD_WRITE_LOG("Remove " TUP_FMT "\n", TUP_FMT_ARGS(tup));
1267 SordNode* quad = NULL;
1268 for (unsigned i = 0; i < NUM_ORDERS; ++i) {
1269 if (sord->indices[i] && (i < GSPO || tup[3])) {
1270 if (zix_btree_remove(sord->indices[i], tup, (void**)&quad,
1271 i == iter->order ? &iter->cur : NULL)) {
1272 return (i == 0) ? SERD_ERR_NOT_FOUND : SERD_ERR_INTERNAL;
1276 iter->end = zix_btree_iter_is_end(iter->cur);
1277 sord_iter_scan_next(iter);
1279 free(quad);
1281 for (int i = 0; i < TUP_LEN; ++i)
1282 sord_drop_quad_ref(sord, tup[i], (SordQuadIndex)i);
1284 --sord->n_quads;
1285 return SERD_SUCCESS;