| 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 |
} |