Debian Codegraph @

src/sord.c

raw
1 // Copyright 2011-2026 David Robillard <[email protected]>
2 // SPDX-License-Identifier: ISC
3
4 #include "sord_internal.h"
5
6 #include <serd/serd.h>
7 #include <sord/sord.h>
8
9 #define ZIX_HASH_KEY_TYPE SordNode
10 #define ZIX_HASH_RECORD_TYPE SordNode
11 #define ZIX_HASH_SEARCH_DATA_TYPE SordWorld
12 #include <zix/btree.h>
13 #include <zix/digest.h>
14 #include <zix/hash.h>
15 #include <zix/status.h>
16
17 #include <assert.h>
18 #include <stdarg.h>
19 #include <stdbool.h>
20 #include <stdint.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24
25 #ifdef __GNUC__
26 # define SORD_LOG_FUNC(fmt, arg1) __attribute__((format(printf, fmt, arg1)))
27 #else
28 # define SORD_LOG_FUNC(fmt, arg1)
29 #endif
30
31 #define SORD_LOG(prefix, ...) fprintf(stderr, "[Sord::" prefix "] " __VA_ARGS__)
32
33 #ifdef SORD_DEBUG_ITER
34 # define SORD_ITER_LOG(...) SORD_LOG("iter", __VA_ARGS__)
35 #else
36 # define SORD_ITER_LOG(...)
37 #endif
38 #ifdef SORD_DEBUG_SEARCH
39 # define SORD_FIND_LOG(...) SORD_LOG("search", __VA_ARGS__)
40 #else
41 # define SORD_FIND_LOG(...)
42 #endif
43 #ifdef SORD_DEBUG_WRITE
44 # define SORD_WRITE_LOG(...) SORD_LOG("write", __VA_ARGS__)
45 #else
46 # define SORD_WRITE_LOG(...)
47 #endif
48
49 #define NUM_ORDERS 12U
50 #define TUP_LEN 4U
51 #define DEFAULT_ORDER SPO
52 #define DEFAULT_GRAPH_ORDER GSPO
53
54 #define TUP_FMT "(%s %s %s %s)"
55 #define TUP_FMT_ELEM(e) ((e) ? sord_node_get_string(e) : (const uint8_t*)"*")
56 #define TUP_FMT_ARGS(t) \
57 TUP_FMT_ELEM((t)[0]), TUP_FMT_ELEM((t)[1]), TUP_FMT_ELEM((t)[2]), \
58 TUP_FMT_ELEM((t)[3])
59
60 #define TUP_G 3U
61
62 /** Triple ordering */
63 typedef enum {
64 SPO, ///< Subject, Predicate, Object
65 SOP, ///< Subject, Object, Predicate
66 OPS, ///< Object, Predicate, Subject
67 OSP, ///< Object, Subject, Predicate
68 PSO, ///< Predicate, Subject, Object
69 POS, ///< Predicate, Object, Subject
70 GSPO, ///< Graph, Subject, Predicate, Object
71 GSOP, ///< Graph, Subject, Object, Predicate
72 GOPS, ///< Graph, Object, Predicate, Subject
73 GOSP, ///< Graph, Object, Subject, Predicate
74 GPSO, ///< Graph, Predicate, Subject, Object
75 GPOS ///< Graph, Predicate, Object, Subject
76 } SordOrder;
77
78 #ifdef SORD_DEBUG_SEARCH
79 /** String name of each ordering (array indexed by SordOrder) */
80 static const char* const order_names[NUM_ORDERS] = {"spo",
81 "sop",
82 "ops",
83 "osp",
84 "pso",
85 "pos",
86 "gspo",
87 "gsop",
88 "gops",
89 "gosp",
90 "gpso",
91 "gpos"};
92 #endif
93
94 /**
95 Quads of indices for each order, from most to least significant
96 (array indexed by SordOrder)
97 */
98 static const uint8_t orderings[NUM_ORDERS][TUP_LEN] = {
99 {0, 1, 2, 3}, // SPO
100 {0, 2, 1, 3}, // SOP
101 {2, 1, 0, 3}, // OPS
102 {2, 0, 1, 3}, // OSP
103 {1, 0, 2, 3}, // PSO
104 {1, 2, 0, 3}, // POS
105 {3, 0, 1, 2}, // GSPO
106 {3, 0, 2, 1}, // GSOP
107 {3, 2, 1, 0}, // GOPS
108 {3, 2, 0, 1}, // GOSP
109 {3, 1, 0, 2}, // GPSO
110 {3, 1, 2, 0} // GPOS
111 };
112
113 /** World */
114 struct SordWorldImpl {
115 ZixHash* nodes;
116 SerdErrorSink error_sink;
117 void* error_handle;
118 };
119
120 /** Store */
121 struct SordModelImpl {
122 SordWorld* world;
123
124 /** Index for each possible triple ordering (may or may not exist).
125 * Each index is a tree of SordQuad with the appropriate ordering.
126 */
127 ZixBTree* indices[NUM_ORDERS];
128
129 size_t n_quads;
130 size_t n_iters;
131 };
132
133 /** Mode for searching or iteration */
134 typedef enum {
135 ALL, ///< Iterate over entire store
136 SINGLE, ///< Iteration over a single element (exact search)
137 RANGE, ///< Iterate over range with equal prefix
138 FILTER_RANGE, ///< Iterate over range with equal prefix, filtering
139 FILTER_ALL ///< Iterate to end of store, filtering
140 } SearchMode;
141
142 /** Iterator over some range of a store */
143 struct SordIterImpl {
144 const SordModel* sord; ///< Model being iterated over
145 ZixBTreeIter cur; ///< Current DB cursor
146 SordQuad pat; ///< Pattern (in ordering order)
147 SordOrder order; ///< Store order (which index)
148 SearchMode mode; ///< Iteration mode
149 uint8_t n_prefix; ///< Prefix for RANGE and FILTER_RANGE
150 bool end; ///< True iff reached end
151 bool skip_graphs; ///< Iteration should ignore graphs
152 };
153
154 static uint8_t*
155 sord_strndup(const uint8_t* str, size_t len)
156 {
157 uint8_t* dup = (uint8_t*)malloc(len + 1);
158 memcpy(dup, str, len + 1);
159 return dup;
160 }
161
162 static const SordNode*
163 sord_node_record_key(const SordNode* n)
164 {
165 return n;
166 }
167
168 static size_t
169 sord_node_hash(const SordNode* const node)
170 {
171 const size_t head = node->node.type;
172
173 size_t hash = 0U;
174
175 hash = zix_digest(hash, (const uint8_t*)node->node.buf, node->node.n_bytes);
176 hash = zix_digest(hash, &head, sizeof(head));
177 if (node->node.type == SERD_LITERAL) {
178 hash = zix_digest(hash, &node->meta.lit, sizeof(node->meta.lit));
179 }
180
181 return hash;
182 }
183
184 static bool
185 sord_node_hash_equal(const SordNode* const a, const SordNode* const b)
186 {
187 return ((a == b) || ((a->node.type == b->node.type) &&
188 (a->node.type != SERD_LITERAL ||
189 (a->meta.lit.datatype == b->meta.lit.datatype &&
190 !strncmp(a->meta.lit.lang,
191 b->meta.lit.lang,
192 sizeof(a->meta.lit.lang)))) &&
193 (serd_node_equals(&a->node, &b->node))));
194 }
195
196 static SordNode*
197 sord_node_create(const SordNode* const node)
198 {
199 SordNode* const copy = node ? (SordNode*)malloc(sizeof(SordNode)) : NULL;
200
201 if (copy) {
202 memcpy(copy, node, sizeof(SordNode));
203 copy->node.buf = sord_strndup(copy->node.buf, copy->node.n_bytes);
204 if (copy->node.type == SERD_LITERAL) {
205 copy->meta.lit.datatype = sord_node_copy(copy->meta.lit.datatype);
206 }
207 }
208
209 return copy;
210 }
211
212 SORD_LOG_FUNC(3, 4) static void
213 error(SordWorld* world, SerdStatus st, const char* fmt, ...)
214 {
215 va_list args;
216 va_start(args, fmt);
217 const SerdError e = {st, NULL, 0, 0, fmt, &args};
218 if (world->error_sink) {
219 world->error_sink(world->error_handle, &e);
220 } else {
221 fprintf(stderr, "error: ");
222 vfprintf(stderr, fmt, args);
223 }
224 va_end(args);
225 }
226
227 SordWorld*
228 sord_world_new(void)
229 {
230 SordWorld* world = (SordWorld*)malloc(sizeof(SordWorld));
231 world->error_sink = NULL;
232 world->error_handle = NULL;
233
234 world->nodes = zix_hash_new(
235 NULL, sord_node_record_key, sord_node_hash, sord_node_hash_equal);
236
237 return world;
238 }
239
240 static void
241 free_node_entry(SordNode* const node)
242 {
243 free((uint8_t*)node->node.buf);
244 free(node);
245 }
246
247 void
248 sord_world_free(SordWorld* world)
249 {
250 if (!world) {
251 return;
252 }
253
254 for (ZixHashIter i = zix_hash_begin(world->nodes);
255 i != zix_hash_end(world->nodes);
256 i = zix_hash_next(world->nodes, i)) {
257 free_node_entry(zix_hash_get(world->nodes, i));
258 }
259
260 zix_hash_free(world->nodes);
261 free(world);
262 }
263
264 void
265 sord_world_set_error_sink(SordWorld* world,
266 SerdErrorSink error_sink,
267 void* handle)
268 {
269 world->error_sink = error_sink;
270 world->error_handle = handle;
271 }
272
273 static inline int
274 sord_node_compare_literal(const SordNode* a, const SordNode* b)
275 {
276 const int cmp = strcmp((const char*)sord_node_get_string(a),
277 (const char*)sord_node_get_string(b));
278 if (cmp != 0) {
279 return cmp;
280 }
281
282 const bool a_has_lang = a->meta.lit.lang[0];
283 const bool b_has_lang = b->meta.lit.lang[0];
284 const bool a_has_datatype = a->meta.lit.datatype;
285 const bool b_has_datatype = b->meta.lit.datatype;
286 const bool a_has_meta = a_has_lang || a_has_datatype;
287 const bool b_has_meta = b_has_lang || b_has_datatype;
288
289 assert(!(a_has_lang && a_has_datatype));
290 assert(!(b_has_lang && b_has_datatype));
291
292 if (!a_has_meta && !b_has_meta) {
293 return 0;
294 } else if (!a_has_meta || (a_has_lang && b_has_datatype)) {
295 return -1;
296 } else if (!b_has_meta || (a_has_datatype && b_has_lang)) {
297 return 1;
298 } else if (a_has_lang) {
299 assert(b_has_lang);
300 return strcmp(a->meta.lit.lang, b->meta.lit.lang);
301 }
302
303 assert(a_has_datatype);
304 assert(b_has_datatype);
305 return strcmp((const char*)a->meta.lit.datatype->node.buf,
306 (const char*)b->meta.lit.datatype->node.buf);
307 }
308
309 /** Compare nodes, considering NULL a wildcard match. */
310 static inline int
311 sord_node_compare(const SordNode* a, const SordNode* b)
312 {
313 if (a == b || !a || !b) {
314 return 0; // Exact or wildcard match
315 } else if (a->node.type != b->node.type) {
316 return (a->node.type < b->node.type) ? -1 : 1;
317 }
318
319 int cmp = 0;
320 switch (a->node.type) {
321 case SERD_URI:
322 case SERD_BLANK:
323 return strcmp((const char*)a->node.buf, (const char*)b->node.buf);
324 case SERD_LITERAL:
325 cmp = sord_node_compare_literal(a, b);
326 break;
327 default:
328 break;
329 }
330 return cmp;
331 }
332
333 bool
334 sord_node_equals(const SordNode* a, const SordNode* b)
335 {
336 return a == b; // Nodes are interned
337 }
338
339 /** Return true iff IDs are equivalent, or one is a wildcard */
340 static inline bool
341 sord_id_match(const SordNode* a, const SordNode* b)
342 {
343 return !a || !b || (a == b);
344 }
345
346 static inline bool
347 sord_quad_match_inline(const SordQuad x, const SordQuad y)
348 {
349 return (sord_id_match(x[0], y[0]) && //
350 sord_id_match(x[1], y[1]) && //
351 sord_id_match(x[2], y[2]) && //
352 sord_id_match(x[3], y[3]));
353 }
354
355 bool
356 sord_quad_match(const SordQuad x, const SordQuad y)
357 {
358 return sord_quad_match_inline(x, y);
359 }
360
361 /**
362 Compare two quad IDs lexicographically.
363 NULL IDs (equal to 0) are treated as wildcards, always less than every
364 other possible ID, except itself.
365 */
366 static int
367 sord_quad_compare(const void* x_ptr, const void* y_ptr, const void* user_data)
368 {
369 const uint8_t* const ordering = (const uint8_t*)user_data;
370 const SordNode* const* const x = (const SordNode* const*)x_ptr;
371 const SordNode* const* const y = (const SordNode* const*)y_ptr;
372
373 for (uint8_t i = 0U; i < TUP_LEN; ++i) {
374 const uint8_t idx = ordering[i];
375 const int cmp = sord_node_compare(x[idx], y[idx]);
376 if (cmp) {
377 return cmp;
378 }
379 }
380
381 return 0;
382 }
383
384 static inline bool
385 sord_iter_forward(SordIter* iter)
386 {
387 if (!iter->skip_graphs) {
388 zix_btree_iter_increment(&iter->cur);
389 return zix_btree_iter_is_end(iter->cur);
390 }
391
392 SordNode** key = (SordNode**)zix_btree_get(iter->cur);
393 const SordQuad initial = {key[0], key[1], key[2], key[3]};
394 zix_btree_iter_increment(&iter->cur);
395 while (!zix_btree_iter_is_end(iter->cur)) {
396 key = (SordNode**)zix_btree_get(iter->cur);
397 for (int i = 0; i < 3; ++i) {
398 if (key[i] != initial[i]) {
399 return false;
400 }
401 }
402
403 zix_btree_iter_increment(&iter->cur);
404 }
405
406 return true;
407 }
408
409 /**
410 Seek forward as necessary until `iter` points at a match.
411 @return true iff iterator reached end of valid range.
412 */
413 static inline bool
414 sord_iter_seek_match(SordIter* iter)
415 {
416 for (iter->end = true; !zix_btree_iter_is_end(iter->cur);
417 sord_iter_forward(iter)) {
418 const SordNode** const key = (const SordNode**)zix_btree_get(iter->cur);
419 if (key && sord_quad_match_inline(key, iter->pat)) {
420 return (iter->end = false);
421 }
422 }
423 return true;
424 }
425
426 /**
427 Seek forward as necessary until `iter` points at a match, or the prefix
428 no longer matches iter->pat.
429 @return true iff iterator reached end of valid range.
430 */
431 static inline bool
432 sord_iter_seek_match_range(SordIter* iter)
433 {
434 assert(!iter->end);
435
436 do {
437 const SordNode** key = (const SordNode**)zix_btree_get(iter->cur);
438
439 if (sord_quad_match_inline(key, iter->pat)) {
440 return false; // Found match
441 }
442
443 for (uint8_t i = 0U; i < iter->n_prefix; ++i) {
444 const uint8_t idx = orderings[iter->order][i];
445 if (!sord_id_match(key[idx], iter->pat[idx])) {
446 iter->end = true; // Reached end of valid range
447 return true;
448 }
449 }
450 } while (!sord_iter_forward(iter));
451
452 return (iter->end = true); // Reached end
453 }
454
455 static SordIter*
456 sord_iter_new(const SordModel* sord,
457 const ZixBTreeIter cur,
458 const SordQuad pat,
459 SordOrder order,
460 SearchMode mode,
461 uint8_t n_prefix)
462 {
463 SordIter* iter = (SordIter*)malloc(sizeof(SordIter));
464 iter->sord = sord;
465 iter->cur = cur;
466 iter->order = order;
467 iter->mode = mode;
468 iter->n_prefix = n_prefix;
469 iter->end = false;
470 iter->skip_graphs = order < GSPO;
471 for (uint8_t i = 0U; i < TUP_LEN; ++i) {
472 iter->pat[i] = pat[i];
473 }
474
475 switch (iter->mode) {
476 case ALL:
477 case SINGLE:
478 case RANGE:
479 assert(sord_quad_match_inline((const SordNode**)zix_btree_get(iter->cur),
480 iter->pat));
481 break;
482 case FILTER_RANGE:
483 sord_iter_seek_match_range(iter);
484 break;
485 case FILTER_ALL:
486 sord_iter_seek_match(iter);
487 break;
488 }
489
490 #ifdef SORD_DEBUG_ITER
491 SordQuad value;
492 sord_iter_get(iter, value);
493 SORD_ITER_LOG("New %p pat=" TUP_FMT " cur=" TUP_FMT " end=%d skip=%d\n",
494 (void*)iter,
495 TUP_FMT_ARGS(pat),
496 TUP_FMT_ARGS(value),
497 iter->end,
498 iter->skip_graphs);
499 #endif
500
501 ++((SordModel*)sord)->n_iters;
502 return iter;
503 }
504
505 const SordModel*
506 sord_iter_get_model(SordIter* iter)
507 {
508 return iter ? iter->sord : NULL;
509 }
510
511 void
512 sord_iter_get(const SordIter* iter, SordQuad tup)
513 {
514 SordNode** key = (SordNode**)zix_btree_get(iter->cur);
515 for (uint8_t i = 0U; i < TUP_LEN; ++i) {
516 tup[i] = key[i];
517 }
518 }
519
520 const SordNode*
521 sord_iter_get_node(const SordIter* iter, SordQuadIndex index)
522 {
523 return (!sord_iter_end(iter) ? ((SordNode**)zix_btree_get(iter->cur))[index]
524 : NULL);
525 }
526
527 static bool
528 sord_iter_scan_next(SordIter* iter)
529 {
530 if (iter->end) {
531 return true;
532 }
533
534 const SordNode** key = NULL;
535 if (!iter->end) {
536 switch (iter->mode) {
537 case ALL:
538 // At the end if the cursor is (assigned above)
539 break;
540 case SINGLE:
541 iter->end = true;
542 SORD_ITER_LOG("%p reached single end\n", (void*)iter);
543 break;
544 case RANGE:
545 SORD_ITER_LOG("%p range next\n", (void*)iter);
546 // At the end if the MSNs no longer match
547 key = (const SordNode**)zix_btree_get(iter->cur);
548 assert(key);
549 for (uint8_t i = 0U; i < iter->n_prefix; ++i) {
550 const uint8_t idx = orderings[iter->order][i];
551 if (!sord_id_match(key[idx], iter->pat[idx])) {
552 iter->end = true;
553 SORD_ITER_LOG("%p reached non-match end\n", (void*)iter);
554 break;
555 }
556 }
557 break;
558 case FILTER_RANGE:
559 // Seek forward to next match, stopping if prefix changes
560 sord_iter_seek_match_range(iter);
561 break;
562 case FILTER_ALL:
563 // Seek forward to next match
564 sord_iter_seek_match(iter);
565 break;
566 }
567 } else {
568 SORD_ITER_LOG("%p reached index end\n", (void*)iter);
569 }
570
571 if (iter->end) {
572 SORD_ITER_LOG("%p Reached end\n", (void*)iter);
573 return true;
574 } else {
575 #ifdef SORD_DEBUG_ITER
576 SordQuad tup;
577 sord_iter_get(iter, tup);
578 SORD_ITER_LOG(
579 "%p Increment to " TUP_FMT "\n", (void*)iter, TUP_FMT_ARGS(tup));
580 #endif
581 return false;
582 }
583 }
584
585 bool
586 sord_iter_next(SordIter* iter)
587 {
588 if (!iter || iter->end) {
589 return true;
590 }
591
592 iter->end = sord_iter_forward(iter);
593 return sord_iter_scan_next(iter);
594 }
595
596 bool
597 sord_iter_end(const SordIter* iter)
598 {
599 return !iter || iter->end;
600 }
601
602 void
603 sord_iter_free(SordIter* iter)
604 {
605 SORD_ITER_LOG("%p Free\n", (void*)iter);
606 if (iter) {
607 --((SordModel*)iter->sord)->n_iters;
608 free(iter);
609 }
610 }
611
612 /**
613 Return true iff `sord` has an index for `order`.
614 If `graphs` is true, `order` will be modified to be the
615 corresponding order with a G prepended (so G will be the MSN).
616 */
617 static inline bool
618 sord_has_index(const SordModel* model,
619 SordOrder* order,
620 uint8_t* n_prefix,
621 bool graphs)
622 {
623 if (graphs) {
624 *order = (SordOrder)(*order + GSPO);
625 ++*n_prefix;
626 }
627
628 return model->indices[*order];
629 }
630
631 /**
632 Return the best available index for a pattern.
633 @param pat Pattern in standard (S P O G) order
634 @param mode Set to the (best) iteration mode for iterating over results
635 @param n_prefix Set to the length of the range prefix
636 (for `mode` == RANGE and `mode` == FILTER_RANGE)
637 */
638 static inline SordOrder
639 sord_best_index(const SordModel* sord,
640 const SordQuad pat,
641 SearchMode* mode,
642 uint8_t* n_prefix)
643 {
644 const bool graph_search = (pat[TUP_G] != 0);
645
646 const unsigned sig = (((pat[0] ? 1U : 0U) * 0x100U) + //
647 ((pat[1] ? 1U : 0U) * 0x010U) + //
648 ((pat[2] ? 1U : 0U) * 0x001U));
649
650 SordOrder good[2] = {(SordOrder)-1, (SordOrder)-1};
651
652 #define PAT_CASE(sig, m, g0, g1, np) \
653 case sig: \
654 *mode = m; \
655 good[0] = g0; \
656 good[1] = g1; \
657 *n_prefix = np; \
658 break
659
660 // Good orderings that don't require filtering
661 *mode = RANGE;
662 *n_prefix = 0U;
663 switch (sig) {
664 case 0x000:
665 assert(graph_search);
666 *mode = RANGE;
667 *n_prefix = 1U;
668 return DEFAULT_GRAPH_ORDER;
669 case 0x111:
670 *mode = SINGLE;
671 return graph_search ? DEFAULT_GRAPH_ORDER : DEFAULT_ORDER;
672
673 PAT_CASE(0x001, RANGE, OPS, OSP, 1);
674 PAT_CASE(0x010, RANGE, POS, PSO, 1);
675 PAT_CASE(0x011, RANGE, OPS, POS, 2);
676 PAT_CASE(0x100, RANGE, SPO, SOP, 1);
677 PAT_CASE(0x101, RANGE, SOP, OSP, 2);
678 PAT_CASE(0x110, RANGE, SPO, PSO, 2);
679 }
680
681 if (*mode == RANGE) {
682 if (sord_has_index(sord, &good[0], n_prefix, graph_search)) {
683 return good[0];
684 } else if (sord_has_index(sord, &good[1], n_prefix, graph_search)) {
685 return good[1];
686 }
687 }
688
689 // Not so good orderings that require filtering, but can
690 // still be constrained to a range
691 switch (sig) {
692 PAT_CASE(0x011, FILTER_RANGE, OSP, PSO, 1);
693 PAT_CASE(0x101, FILTER_RANGE, SPO, OPS, 1);
694 // SPO is always present, so 0x110 is never reached here
695 default:
696 break;
697 }
698
699 if (*mode == FILTER_RANGE) {
700 if (sord_has_index(sord, &good[0], n_prefix, graph_search)) {
701 return good[0];
702 } else if (sord_has_index(sord, &good[1], n_prefix, graph_search)) {
703 return good[1];
704 }
705 }
706
707 if (graph_search) {
708 *mode = FILTER_RANGE;
709 *n_prefix = 1U;
710 return DEFAULT_GRAPH_ORDER;
711 } else {
712 *mode = FILTER_ALL;
713 return DEFAULT_ORDER;
714 }
715 }
716
717 SordModel*
718 sord_new(SordWorld* world, unsigned indices, bool graphs)
719 {
720 static const unsigned half = (NUM_ORDERS >> 1U);
721
722 SordModel* model = (SordModel*)malloc(sizeof(struct SordModelImpl));
723 model->world = world;
724 model->n_quads = 0;
725 model->n_iters = 0;
726
727 for (unsigned i = 0; i < half; ++i) {
728 if (indices & (1U << i)) {
729 model->indices[i] =
730 zix_btree_new(NULL, sord_quad_compare, (void*)orderings[i]);
731 if (graphs) {
732 model->indices[i + half] =
733 zix_btree_new(NULL, sord_quad_compare, (void*)orderings[i + half]);
734 } else {
735 model->indices[i + half] = NULL;
736 }
737 } else {
738 model->indices[i] = NULL;
739 model->indices[i + half] = NULL;
740 }
741 }
742
743 if (!model->indices[DEFAULT_ORDER]) {
744 model->indices[DEFAULT_ORDER] =
745 zix_btree_new(NULL, sord_quad_compare, (void*)orderings[DEFAULT_ORDER]);
746 }
747 if (graphs && !model->indices[DEFAULT_GRAPH_ORDER]) {
748 model->indices[DEFAULT_GRAPH_ORDER] = zix_btree_new(
749 NULL, sord_quad_compare, (void*)orderings[DEFAULT_GRAPH_ORDER]);
750 }
751
752 return model;
753 }
754
755 static void
756 sord_node_free_internal(SordWorld* world, SordNode* node)
757 {
758 assert(node->refs == 0);
759
760 // If you hit this, the world has probably been destroyed too early
761 assert(world);
762
763 // Remove node from the hash table
764 ZixHashRecord* removed = NULL;
765 if (!zix_hash_remove(world->nodes, node, &removed)) {
766 free((uint8_t*)removed->node.buf);
767 if (removed->node.type == SERD_LITERAL) {
768 sord_node_free(world, removed->meta.lit.datatype);
769 }
770 free(removed);
771 } else {
772 error(world, SERD_ERR_INTERNAL, "failed to remove node from hash\n");
773 }
774 }
775
776 static void
777 sord_add_quad_ref(SordModel* model, const SordNode* node, SordQuadIndex i)
778 {
779 (void)model;
780
781 if (node) {
782 assert(node->refs > 0);
783 ++((SordNode*)node)->refs;
784 if (node->node.type != SERD_LITERAL && i == SORD_OBJECT) {
785 ++((SordNode*)node)->meta.res.refs_as_obj;
786 }
787 }
788 }
789
790 static void
791 sord_drop_quad_ref(SordModel* model, const SordNode* node, SordQuadIndex i)
792 {
793 if (!node) {
794 return;
795 }
796
797 assert(node->refs > 0);
798 if (node->node.type != SERD_LITERAL && i == SORD_OBJECT) {
799 assert(node->meta.res.refs_as_obj > 0);
800 --((SordNode*)node)->meta.res.refs_as_obj;
801 }
802 if (--((SordNode*)node)->refs == 0) {
803 sord_node_free_internal(sord_get_world(model), (SordNode*)node);
804 }
805 }
806
807 void
808 sord_free(SordModel* model)
809 {
810 if (!model) {
811 return;
812 }
813
814 // Free nodes
815 SordQuad tup;
816 SordIter* i = sord_begin(model);
817 for (; !sord_iter_end(i); sord_iter_next(i)) {
818 sord_iter_get(i, tup);
819 for (uint8_t t = 0U; t < TUP_LEN; ++t) {
820 sord_drop_quad_ref(model, tup[t], (SordQuadIndex)t);
821 }
822 }
823 sord_iter_free(i);
824
825 // Free quads
826 ZixBTreeIter t = zix_btree_begin(model->indices[DEFAULT_ORDER]);
827 for (; !zix_btree_iter_is_end(t); zix_btree_iter_increment(&t)) {
828 free(zix_btree_get(t));
829 }
830
831 // Free indices
832 for (unsigned o = 0; o < NUM_ORDERS; ++o) {
833 if (model->indices[o]) {
834 zix_btree_free(model->indices[o], NULL, NULL);
835 }
836 }
837
838 free(model);
839 }
840
841 SordWorld*
842 sord_get_world(SordModel* model)
843 {
844 return model->world;
845 }
846
847 size_t
848 sord_num_quads(const SordModel* model)
849 {
850 return model ? model->n_quads : 0U;
851 }
852
853 size_t
854 sord_num_nodes(const SordWorld* world)
855 {
856 return world ? zix_hash_size(world->nodes) : 0U;
857 }
858
859 SordIter*
860 sord_begin(const SordModel* model)
861 {
862 if (sord_num_quads(model) == 0) {
863 return NULL;
864 } else {
865 const ZixBTreeIter cur = zix_btree_begin(model->indices[DEFAULT_ORDER]);
866 SordQuad pat = {0, 0, 0, 0};
867 return sord_iter_new(model, cur, pat, DEFAULT_ORDER, ALL, 0);
868 }
869 }
870
871 SordIter*
872 sord_find(const SordModel* model, const SordQuad pat)
873 {
874 if (!model || (!pat[0] && !pat[1] && !pat[2] && !pat[3])) {
875 return sord_begin(model);
876 }
877
878 SearchMode mode = ALL;
879 uint8_t n_prefix = 0U;
880 const SordOrder index_order = sord_best_index(model, pat, &mode, &n_prefix);
881
882 SORD_FIND_LOG("Find " TUP_FMT " index=%s mode=%u n_prefix=%u\n",
883 TUP_FMT_ARGS(pat),
884 order_names[index_order],
885 mode,
886 n_prefix);
887
888 if (pat[0] && pat[1] && pat[2] && pat[3]) {
889 mode = SINGLE; // No duplicate quads (Sord is a set)
890 }
891
892 const uint8_t* const ordering = orderings[index_order];
893 ZixBTree* const db = model->indices[index_order];
894 ZixBTreeIter cur = zix_btree_end(db);
895
896 if (mode == FILTER_ALL) {
897 // No prefix shared with an index at all, linear search (worst case)
898 cur = zix_btree_begin(db);
899 } else if (mode == FILTER_RANGE) {
900 /* Some prefix, but filtering still required. Build a search pattern
901 with only the prefix to find the lower bound in log time. */
902 SordQuad prefix_pat = {NULL, NULL, NULL, NULL};
903 for (uint8_t i = 0U; i < n_prefix; ++i) {
904 prefix_pat[ordering[i]] = pat[ordering[i]];
905 }
906
907 zix_btree_lower_bound(db, sord_quad_compare, ordering, prefix_pat, &cur);
908 } else {
909 // Ideal case, pattern matches an index with no filtering required
910 zix_btree_lower_bound(db, sord_quad_compare, ordering, pat, &cur);
911 }
912
913 if (zix_btree_iter_is_end(cur)) {
914 SORD_FIND_LOG("No match found\n");
915 return NULL;
916 }
917
918 const SordNode** const key = (const SordNode**)zix_btree_get(cur);
919 if (!key || ((mode == RANGE || mode == SINGLE) &&
920 !sord_quad_match_inline(pat, key))) {
921 SORD_FIND_LOG("No match found\n");
922 return NULL;
923 }
924
925 return sord_iter_new(model, cur, pat, index_order, mode, n_prefix);
926 }
927
928 SordIter*
929 sord_search(const SordModel* model,
930 const SordNode* s,
931 const SordNode* p,
932 const SordNode* o,
933 const SordNode* g)
934 {
935 SordQuad pat = {s, p, o, g};
936 return sord_find(model, pat);
937 }
938
939 SordNode*
940 sord_get(const SordModel* model,
941 const SordNode* s,
942 const SordNode* p,
943 const SordNode* o,
944 const SordNode* g)
945 {
946 if (!!s + !!p + !!o != 2) {
947 return NULL;
948 }
949
950 SordIter* i = sord_search(model, s, p, o, g);
951 SordNode* ret = NULL;
952 if (!s) {
953 ret = sord_node_copy(sord_iter_get_node(i, SORD_SUBJECT));
954 } else if (!p) {
955 ret = sord_node_copy(sord_iter_get_node(i, SORD_PREDICATE));
956 } else if (!o) {
957 ret = sord_node_copy(sord_iter_get_node(i, SORD_OBJECT));
958 }
959
960 sord_iter_free(i);
961 return ret;
962 }
963
964 bool
965 sord_ask(const SordModel* model,
966 const SordNode* s,
967 const SordNode* p,
968 const SordNode* o,
969 const SordNode* g)
970 {
971 SordQuad pat = {s, p, o, g};
972 return sord_contains(model, pat);
973 }
974
975 uint64_t
976 sord_count(const SordModel* model,
977 const SordNode* s,
978 const SordNode* p,
979 const SordNode* o,
980 const SordNode* g)
981 {
982 SordIter* i = sord_search(model, s, p, o, g);
983 uint64_t n = 0;
984 for (; !sord_iter_end(i); sord_iter_next(i)) {
985 ++n;
986 }
987 sord_iter_free(i);
988 return n;
989 }
990
991 bool
992 sord_contains(const SordModel* model, const SordQuad pat)
993 {
994 SordIter* iter = sord_find(model, pat);
995 bool ret = (iter != NULL);
996 sord_iter_free(iter);
997 return ret;
998 }
999
1000 SordNodeType
1001 sord_node_get_type(const SordNode* node)
1002 {
1003 switch (node->node.type) {
1004 case SERD_URI:
1005 return SORD_URI;
1006 case SERD_BLANK:
1007 return SORD_BLANK;
1008 default:
1009 return SORD_LITERAL;
1010 }
1011 SORD_UNREACHABLE();
1012 }
1013
1014 const uint8_t*
1015 sord_node_get_string(const SordNode* node)
1016 {
1017 const uint8_t* const string = node->node.buf;
1018 assert(string);
1019 return string;
1020 }
1021
1022 const uint8_t*
1023 sord_node_get_string_counted(const SordNode* node, size_t* bytes)
1024 {
1025 *bytes = node->node.n_bytes;
1026 return sord_node_get_string(node);
1027 }
1028
1029 const uint8_t*
1030 sord_node_get_string_measured(const SordNode* node,
1031 size_t* bytes,
1032 size_t* chars)
1033 {
1034 *bytes = node->node.n_bytes;
1035 *chars = node->node.n_chars;
1036 return sord_node_get_string(node);
1037 }
1038
1039 const char*
1040 sord_node_get_language(const SordNode* node)
1041 {
1042 if (node->node.type != SERD_LITERAL || !node->meta.lit.lang[0]) {
1043 return NULL;
1044 }
1045 return node->meta.lit.lang;
1046 }
1047
1048 SordNode*
1049 sord_node_get_datatype(const SordNode* node)
1050 {
1051 return (node->node.type == SERD_LITERAL) ? node->meta.lit.datatype : NULL;
1052 }
1053
1054 SerdNodeFlags
1055 sord_node_get_flags(const SordNode* node)
1056 {
1057 return node->node.flags;
1058 }
1059
1060 bool
1061 sord_node_is_inline_object(const SordNode* node)
1062 {
1063 return (node->node.type == SERD_BLANK) && (node->meta.res.refs_as_obj == 1);
1064 }
1065
1066 static SordNode*
1067 sord_insert_node(SordWorld* world, const SordNode* key)
1068 {
1069 // "Plan" the insertion (that is, search) with the given constant key
1070 const ZixHashInsertPlan plan = zix_hash_plan_insert(world->nodes, key);
1071 SordNode* const existing = zix_hash_record_at(world->nodes, plan);
1072 if (existing) {
1073 ++existing->refs;
1074 return existing;
1075 }
1076
1077 // Insert a new node into hash table, transferring ownership
1078 SordNode* const node = sord_node_create(key);
1079 const ZixStatus st = zix_hash_insert_at(world->nodes, plan, node);
1080 if (st) {
1081 free((uint8_t*)node->node.buf);
1082 free(node);
1083 error(
1084 world, SERD_ERR_INTERNAL, "error inserting node `%s'\n", key->node.buf);
1085 return NULL;
1086 }
1087
1088 return node;
1089 }
1090
1091 static SordNode*
1092 sord_new_uri_counted(SordWorld* world,
1093 const uint8_t* str,
1094 size_t n_bytes,
1095 size_t n_chars)
1096 {
1097 if (!serd_uri_string_has_scheme(str)) {
1098 error(world, SERD_ERR_BAD_ARG, "attempt to map invalid URI `%s'\n", str);
1099 return NULL; // Can't intern relative URIs
1100 }
1101
1102 const SordNode key = {{str, n_bytes, n_chars, 0, SERD_URI}, 1, {{0}}};
1103
1104 return sord_insert_node(world, &key);
1105 }
1106
1107 SordNode*
1108 sord_new_uri(SordWorld* world, const uint8_t* uri)
1109 {
1110 const SerdNode node = serd_node_from_string(SERD_URI, uri);
1111 return sord_new_uri_counted(world, uri, node.n_bytes, node.n_chars);
1112 }
1113
1114 SordNode*
1115 sord_new_relative_uri(SordWorld* world,
1116 const uint8_t* uri,
1117 const uint8_t* base_uri)
1118 {
1119 if (serd_uri_string_has_scheme(uri)) {
1120 return sord_new_uri(world, uri);
1121 }
1122
1123 SerdURI buri = SERD_URI_NULL;
1124 SerdNode base = serd_node_new_uri_from_string(base_uri, NULL, &buri);
1125 SerdNode node = serd_node_new_uri_from_string(uri, &buri, NULL);
1126
1127 SordNode* ret =
1128 sord_new_uri_counted(world, node.buf, node.n_bytes, node.n_chars);
1129
1130 serd_node_free(&node);
1131 serd_node_free(&base);
1132 return ret;
1133 }
1134
1135 static SordNode*
1136 sord_new_blank_counted(SordWorld* world,
1137 const uint8_t* str,
1138 size_t n_bytes,
1139 size_t n_chars)
1140 {
1141 const SordNode key = {{str, n_bytes, n_chars, 0, SERD_BLANK}, 1, {{0}}};
1142
1143 return sord_insert_node(world, &key);
1144 }
1145
1146 SordNode*
1147 sord_new_blank(SordWorld* world, const uint8_t* str)
1148 {
1149 const SerdNode node = serd_node_from_string(SERD_URI, str);
1150 return sord_new_blank_counted(world, str, node.n_bytes, node.n_chars);
1151 }
1152
1153 static SordNode*
1154 sord_new_literal_counted(SordWorld* world,
1155 SordNode* datatype,
1156 const uint8_t* str,
1157 size_t n_bytes,
1158 size_t n_chars,
1159 SerdNodeFlags flags,
1160 const char* lang)
1161 {
1162 SordNode key = {{str, n_bytes, n_chars, flags, SERD_LITERAL}, 1, {{0}}};
1163 key.meta.lit.datatype = sord_node_copy(datatype);
1164 memset(key.meta.lit.lang, 0, sizeof(key.meta.lit.lang));
1165 if (lang) {
1166 strncpy(key.meta.lit.lang, lang, sizeof(key.meta.lit.lang) - 1);
1167 }
1168
1169 return sord_insert_node(world, &key);
1170 }
1171
1172 SordNode*
1173 sord_new_literal(SordWorld* world,
1174 SordNode* datatype,
1175 const uint8_t* str,
1176 const char* lang)
1177 {
1178 SerdNodeFlags flags = 0;
1179 size_t n_bytes = 0;
1180 size_t n_chars = serd_strlen(str, &n_bytes, &flags);
1181 return sord_new_literal_counted(
1182 world, datatype, str, n_bytes, n_chars, flags, lang);
1183 }
1184
1185 static SordNode*
1186 sord_node_from_serd_node_internal(SordWorld* world,
1187 SerdEnv* env,
1188 const SerdNode* node,
1189 const SerdNode* datatype,
1190 const SerdNode* lang)
1191 {
1192 SordNode* datatype_node = NULL;
1193 SordNode* ret = NULL;
1194 switch (node->type) {
1195 case SERD_NOTHING:
1196 return NULL;
1197 case SERD_LITERAL:
1198 datatype_node = sord_node_from_serd_node(world, env, datatype, NULL, NULL);
1199
1200 ret = sord_new_literal_counted(world,
1201 datatype_node,
1202 node->buf,
1203 node->n_bytes,
1204 node->n_chars,
1205 node->flags,
1206 lang ? (const char*)lang->buf : NULL);
1207
1208 sord_node_free(world, datatype_node);
1209 return ret;
1210 case SERD_URI:
1211 if (serd_uri_string_has_scheme(node->buf)) {
1212 return sord_new_uri_counted(
1213 world, node->buf, node->n_bytes, node->n_chars);
1214 } else {
1215 SerdURI base_uri;
1216 serd_env_get_base_uri(env, &base_uri);
1217 SerdURI abs_uri;
1218 SerdNode abs_uri_node =
1219 serd_node_new_uri_from_node(node, &base_uri, &abs_uri);
1220
1221 ret = sord_new_uri_counted(
1222 world, abs_uri_node.buf, abs_uri_node.n_bytes, abs_uri_node.n_chars);
1223
1224 serd_node_free(&abs_uri_node);
1225 return ret;
1226 }
1227 case SERD_CURIE: {
1228 SerdChunk uri_prefix;
1229 SerdChunk uri_suffix;
1230 if (serd_env_expand(env, node, &uri_prefix, &uri_suffix)) {
1231 error(
1232 world, SERD_ERR_BAD_CURIE, "failed to expand CURIE `%s'\n", node->buf);
1233 return NULL;
1234 }
1235 const size_t uri_len = uri_prefix.len + uri_suffix.len;
1236 uint8_t* buf = (uint8_t*)malloc(uri_len + 1);
1237 memcpy(buf, uri_prefix.buf, uri_prefix.len);
1238 memcpy(buf + uri_prefix.len, uri_suffix.buf, uri_suffix.len);
1239 buf[uri_len] = '\0';
1240
1241 ret =
1242 sord_new_uri_counted(world, buf, uri_len, serd_strlen(buf, NULL, NULL));
1243
1244 free(buf);
1245 return ret;
1246 }
1247 case SERD_BLANK:
1248 return sord_new_blank_counted(
1249 world, node->buf, node->n_bytes, node->n_chars);
1250 }
1251 return NULL;
1252 }
1253
1254 SordNode*
1255 sord_node_from_serd_node(SordWorld* world,
1256 SerdEnv* env,
1257 const SerdNode* node,
1258 const SerdNode* datatype,
1259 const SerdNode* lang)
1260 {
1261 return (node && env)
1262 ? sord_node_from_serd_node_internal(world, env, node, datatype, lang)
1263 : NULL;
1264 }
1265
1266 const SerdNode*
1267 sord_node_to_serd_node(const SordNode* node)
1268 {
1269 return node ? &node->node : &SERD_NODE_NULL;
1270 }
1271
1272 void
1273 sord_node_free(SordWorld* world, SordNode* node)
1274 {
1275 if (!node) {
1276 return;
1277 } else if (node->refs == 0) {
1278 error(world, SERD_ERR_BAD_ARG, "attempt to free garbage node\n");
1279 } else if (--node->refs == 0) {
1280 sord_node_free_internal(world, node);
1281 }
1282 }
1283
1284 SordNode*
1285 sord_node_copy(const SordNode* node)
1286 {
1287 SordNode* copy = (SordNode*)node;
1288 if (copy) {
1289 ++copy->refs;
1290 }
1291 return copy;
1292 }
1293
1294 static inline bool
1295 sord_add_to_index(SordModel* model, const SordNode** tup, SordOrder order)
1296 {
1297 return !zix_btree_insert(model->indices[order], tup);
1298 }
1299
1300 bool
1301 sord_add(SordModel* model, const SordQuad tup)
1302 {
1303 SORD_WRITE_LOG("Add " TUP_FMT "\n", TUP_FMT_ARGS(tup));
1304 if (!tup[0] || !tup[1] || !tup[2]) {
1305 error(
1306 model->world, SERD_ERR_BAD_ARG, "attempt to add quad with NULL field\n");
1307 return false;
1308 } else if (model->n_iters > 0) {
1309 error(model->world, SERD_ERR_BAD_ARG, "added tuple during iteration\n");
1310 }
1311
1312 const SordNode** quad = (const SordNode**)malloc(sizeof(SordQuad));
1313 memcpy(quad, tup, sizeof(SordQuad));
1314
1315 for (unsigned i = 0; i < NUM_ORDERS; ++i) {
1316 if (model->indices[i] && (i < GSPO || tup[3])) {
1317 if (!sord_add_to_index(model, quad, (SordOrder)i)) {
1318 assert(i == 0); // Assuming index coherency
1319 free(quad);
1320 return false; // Quad already stored, do nothing
1321 }
1322 }
1323 }
1324
1325 for (uint8_t i = 0U; i < TUP_LEN; ++i) {
1326 sord_add_quad_ref(model, tup[i], (SordQuadIndex)i);
1327 }
1328
1329 ++model->n_quads;
1330 return true;
1331 }
1332
1333 void
1334 sord_remove(SordModel* model, const SordQuad tup)
1335 {
1336 SORD_WRITE_LOG("Remove " TUP_FMT "\n", TUP_FMT_ARGS(tup));
1337 if (model->n_iters > 0) {
1338 error(model->world, SERD_ERR_BAD_ARG, "remove with iterator\n");
1339 }
1340
1341 SordNode* quad = NULL;
1342 for (unsigned i = 0; i < NUM_ORDERS; ++i) {
1343 if (model->indices[i] && (i < GSPO || tup[3])) {
1344 ZixBTreeIter r = zix_btree_end_iter;
1345 if (zix_btree_remove(model->indices[i], tup, (void**)&quad, &r)) {
1346 assert(i == 0); // Assuming index coherency
1347 return; // Quad not found, do nothing
1348 }
1349 }
1350 }
1351
1352 free(quad);
1353
1354 for (uint8_t i = 0U; i < TUP_LEN; ++i) {
1355 sord_drop_quad_ref(model, tup[i], (SordQuadIndex)i);
1356 }
1357
1358 --model->n_quads;
1359 }
1360
1361 SerdStatus
1362 sord_erase(SordModel* model, SordIter* iter)
1363 {
1364 if (!iter) {
1365 return SERD_SUCCESS;
1366 }
1367
1368 if (model->n_iters > 1) {
1369 error(model->world, SERD_ERR_BAD_ARG, "erased with many iterators\n");
1370 return SERD_ERR_BAD_ARG;
1371 }
1372
1373 SordQuad tup;
1374 sord_iter_get(iter, tup);
1375
1376 SORD_WRITE_LOG("Remove " TUP_FMT "\n", TUP_FMT_ARGS(tup));
1377
1378 SordNode* quad = NULL;
1379 for (unsigned i = 0; i < NUM_ORDERS; ++i) {
1380 if (model->indices[i] && (i < GSPO || tup[3])) {
1381 ZixBTreeIter r = zix_btree_end_iter;
1382 if (zix_btree_remove(model->indices[i],
1383 tup,
1384 (void**)&quad,
1385 (SordOrder)i == iter->order ? &iter->cur : &r)) {
1386 return (i == 0) ? SERD_ERR_NOT_FOUND : SERD_ERR_INTERNAL;
1387 }
1388 }
1389 }
1390 iter->end = zix_btree_iter_is_end(iter->cur);
1391 sord_iter_scan_next(iter);
1392
1393 free(quad);
1394
1395 for (uint8_t i = 0U; i < TUP_LEN; ++i) {
1396 sord_drop_quad_ref(model, tup[i], (SordQuadIndex)i);
1397 }
1398
1399 --model->n_quads;
1400 return SERD_SUCCESS;
1401 }