123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689 |
- #include "graph.h"
- /*
- * Data types.
- */
- struct graph_t {
- LSUP_Term *uri; ///< Graph "name" (URI).
- LSUP_Store * store; ///< Store handle.
- LSUP_NSMap * nsm; /**< Namespace map.
- *
- * NOTE: This is
- * NULL for permanent stores.
- */
- };
- struct graph_iter_t {
- const LSUP_Graph * graph; ///< Parent graph.
- void * data; ///< Iterator state.
- size_t ct; ///< Total lookup matches.
- LSUP_BufferTriple * sspo; ///< Buffer triple for temp values.
- };
- /*
- * Static prototypes.
- */
- inline static LSUP_rc
- graph_iter_next_buffer (LSUP_GraphIterator *it);
- inline static LSUP_rc
- graph_iter_alloc_buffers (LSUP_GraphIterator *it);
- #define ENTRY(a, b) (be) == (LSUP_STORE_##a) ||
- static inline bool
- check_backend (LSUP_StoreType be)
- { return (BACKEND_TBL false); }
- #undef ENTRY
- /*
- * Graph API.
- */
- LSUP_Graph *
- LSUP_graph_new (LSUP_Store *store, LSUP_Term *uri, LSUP_NSMap *nsm)
- {
- // Create a HTable graph by default.
- if (!store) store = LSUP_store_new (LSUP_STORE_HTABLE, NULL, 0);
- LSUP_Graph *gr;
- MALLOC_GUARD (gr, NULL);
- if (!uri) uri = LSUP_iriref_new (NULL, NULL);
- gr->uri = uri;
- gr->store = store;
- if (gr->store->sif->features & LSUP_STORE_PERM) gr->nsm = NULL;
- else gr->nsm = nsm ? nsm : LSUP_default_nsm;
- log_debug ("Graph created.");
- return gr;
- }
- LSUP_rc
- LSUP_graph_bool_op_txn (
- void *txn, const LSUP_bool_op op,
- const LSUP_Graph *gr1, const LSUP_Graph *gr2, LSUP_Graph *res)
- {
- LSUP_rc rc = LSUP_NOACTION;
- if (UNLIKELY (
- op != LSUP_BOOL_UNION
- && op != LSUP_BOOL_SUBTRACTION
- && op != LSUP_BOOL_INTERSECTION
- && op != LSUP_BOOL_XOR)) {
- log_error ("Invalid boolean operation: %d.", op);
- return LSUP_VALUE_ERR;
- }
- if (op == LSUP_BOOL_UNION) {
- rc = LSUP_graph_copy_contents (gr1, res);
- PCHECK (rc, fail);
- rc = LSUP_graph_copy_contents (gr2, res);
- PCHECK (rc, fail);
- return LSUP_OK;
- }
- LSUP_Buffer
- *res_sc = LSUP_term_serialize (res->uri),
- *gr1_sc = LSUP_term_serialize (gr1->uri),
- *gr2_sc = LSUP_term_serialize (gr2->uri);
- void *lu1_it, *lu2_it, *add_it;
- LSUP_BufferTriple *sspo = BTRP_DUMMY;
- size_t ct;
- add_it = res->store->sif->add_init_fn (res->store->data, res_sc, txn);
- if (op == LSUP_BOOL_XOR) {
- // Add triples from gr2 if not found in gr1.
- lu2_it = gr2->store->sif->lookup_fn (
- gr2->store->data, NULL, NULL, NULL, gr2_sc, NULL, txn);
- while (gr2->store->sif->lu_next_fn (lu2_it, sspo, NULL) == LSUP_OK) {
- lu1_it = gr1->store->sif->lookup_fn (
- gr1->store->data, sspo->s, sspo->p, sspo->o, gr1_sc,
- txn, &ct);
- if (ct > 0)
- res->store->sif->add_iter_fn (add_it, sspo);
- gr1->store->sif->lu_free_fn (lu1_it);
- }
- gr2->store->sif->lu_free_fn (lu2_it);
- }
- lu1_it = gr1->store->sif->lookup_fn (
- gr1->store->data, NULL, NULL, NULL, gr1_sc, txn, NULL);
- while (gr1->store->sif->lu_next_fn (lu1_it, sspo, NULL) == LSUP_OK) {
- lu2_it = gr2->store->sif->lookup_fn (
- gr2->store->data, sspo->s, sspo->p, sspo->o, gr2_sc,
- txn, &ct);
- // For XOR and subtraction, add if not found.
- // For intersection, add if found.
- if ((ct == 0) ^ (op == LSUP_BOOL_INTERSECTION))
- res->store->sif->add_iter_fn (add_it, sspo);
- gr2->store->sif->lu_free_fn (lu2_it);
- }
- gr1->store->sif->lu_free_fn (lu1_it);
- res->store->sif->add_done_fn (add_it);
- LSUP_buffer_free (res_sc);
- LSUP_buffer_free (gr1_sc);
- LSUP_buffer_free (gr2_sc);
- return rc;
- fail:
- LSUP_graph_free (res);
- return rc;
- }
- void
- LSUP_graph_free (LSUP_Graph *gr)
- {
- if (UNLIKELY (!gr)) return;
- LSUP_term_free (gr->uri);
- free (gr->store->id);
- // If the store is a HTable, it means it has been created with the graph
- // and must go with it.
- if (gr->store->type == LSUP_STORE_HTABLE) {
- gr->store->sif->free_fn (gr->store->data);
- free (gr->store);
- }
- free (gr);
- }
- LSUP_Term *
- LSUP_graph_uri (const LSUP_Graph *gr) { return gr->uri; }
- LSUP_Store *
- LSUP_graph_store (const LSUP_Graph *gr)
- { return gr->store; }
- LSUP_rc
- LSUP_graph_set_uri (LSUP_Graph *gr, LSUP_Term *uri)
- {
- if (!LSUP_IS_IRI (uri)) {
- log_error ("Term provided is not a IRI.");
- return LSUP_VALUE_ERR;
- }
- LSUP_term_free (gr->uri);
- gr->uri = uri;
- return LSUP_OK;
- }
- LSUP_NSMap *
- LSUP_graph_namespace (const LSUP_Graph *gr)
- {
- // If nsm_get_fn is not defined, the store has no own NS map.
- if (!gr->store->sif->nsm_get_fn) return gr->nsm;
- return gr->store->sif->nsm_get_fn (gr->store->data);
- }
- void
- LSUP_graph_set_namespace (LSUP_Graph *gr, LSUP_NSMap *nsm)
- {
- if (!gr->store->sif->nsm_get_fn) gr->nsm = nsm;
- else log_warn ("Graph back end has a stored NS map.");
- }
- size_t
- LSUP_graph_size (const LSUP_Graph *gr)
- { return gr->store->sif->size_fn (gr->store->data); }
- bool
- LSUP_graph_equals (const LSUP_Graph *gr1, const LSUP_Graph *gr2)
- {
- LSUP_Graph *res = LSUP_graph_new (NULL, NULL, NULL);
- LSUP_graph_bool_op (LSUP_BOOL_XOR, gr1, gr2, res);
- bool ret = (LSUP_graph_size (res) == 0);
- LSUP_graph_free (res);
- return ret;
- }
- LSUP_GraphIterator *
- LSUP_graph_add_init_txn (void *txn, LSUP_Graph *gr)
- {
- LSUP_GraphIterator *it;
- CALLOC_GUARD (it, NULL);
- LSUP_Buffer *sc = LSUP_term_serialize (gr->uri);
- it->data = gr->store->sif->add_init_fn (gr->store->data, sc, txn);
- LSUP_buffer_free (sc);
- it->graph = gr;
- return it;
- }
- LSUP_rc
- LSUP_graph_add_iter (LSUP_GraphIterator *it, const LSUP_Triple *spo)
- {
- log_trace (
- "Adding triple: {%s, %s, %s}",
- spo->s->data, spo->p->data, spo->o->data);
- LSUP_BufferTriple *sspo = LSUP_triple_serialize (spo);
- if (UNLIKELY (!sspo)) return LSUP_MEM_ERR;
- const LSUP_StoreInt *sif = it->graph->store->sif;
- LSUP_rc rc;
- PCHECK (rc = sif->add_iter_fn (it->data, sspo), finally);
- // Store datatype term permanently.
- if (rc == LSUP_OK && sif->add_term_fn) {
- for (int i = 0; i < 3; i++) {
- LSUP_Term *term = LSUP_triple_pos (spo, i);
- if (term->type == LSUP_TERM_LITERAL) {
- LSUP_Buffer *ser_dtype = LSUP_term_serialize (term->datatype);
- LSUP_rc term_rc = sif->add_term_fn (
- it->graph->store->data, ser_dtype, it->data);
- PCHECK (term_rc, finally);
- LSUP_buffer_free (ser_dtype);
- }
- }
- }
- finally:
- LSUP_btriple_free (sspo);
- return rc;
- }
- void
- LSUP_graph_add_done (LSUP_GraphIterator *it)
- {
- it->graph->store->sif->add_done_fn (it->data);
- free (it);
- }
- LSUP_rc
- LSUP_graph_add_txn (
- void *txn, LSUP_Graph *gr, const LSUP_Triple trp[], size_t *ct)
- {
- LSUP_rc rc = LSUP_NOACTION;
- // Initialize iterator.
- LSUP_GraphIterator *it = LSUP_graph_add_init_txn (txn, gr);
- if (ct) *ct = 0;
- // Serialize and insert RDF triples.
- for (size_t i = 0; trp[i].s != NULL; i++) {
- log_trace ("Inserting triple #%lu", i);
- LSUP_rc db_rc = LSUP_graph_add_iter (it, trp + i);
- if (db_rc == LSUP_OK) {
- rc = LSUP_OK;
- if (ct) (*ct)++;
- // A duplicate will return LSUP_NOACTION and not increment the
- // counter.
- }
- if (UNLIKELY (db_rc < 0)) {
- rc = db_rc;
- goto finally;
- }
- log_trace ("Graph size at end of add iter: %lu", LSUP_graph_size (gr));
- }
- finally:
- LSUP_graph_add_done (it);
- return rc;
- }
- LSUP_rc
- LSUP_graph_remove_txn (
- void *txn, LSUP_Graph *gr,
- const LSUP_Term *s, const LSUP_Term *p, const LSUP_Term *o,
- size_t *ct)
- {
- LSUP_rc rc;
- LSUP_Buffer
- *ss = LSUP_term_serialize (s),
- *sp = LSUP_term_serialize (p),
- *so = LSUP_term_serialize (o),
- *sc = LSUP_term_serialize (gr->uri);
- rc = gr->store->sif->remove_fn (
- gr->store->data, ss, sp, so, sc, txn, ct);
- LSUP_buffer_free (ss);
- LSUP_buffer_free (sp);
- LSUP_buffer_free (so);
- LSUP_buffer_free (sc);
- return rc;
- }
- /**
- * Copy triples from a source graph into a destination one.
- *
- * The destination graph is not initialized here, so the copy is cumulative.
- */
- LSUP_rc
- LSUP_graph_copy_contents_txn (
- void *txn, const LSUP_Graph *src, LSUP_Graph *dest)
- {
- LSUP_rc rc = LSUP_NOACTION;
- LSUP_GraphIterator *it = LSUP_graph_lookup_txn (
- txn, src, NULL, NULL, NULL, NULL);
- LSUP_Triple *spo = NULL;
- LSUP_GraphIterator *add_it = LSUP_graph_add_init_txn (txn, dest);
- while (LSUP_graph_iter_next (it, &spo) != LSUP_END) {
- LSUP_rc add_rc = LSUP_graph_add_iter (add_it, spo);
- LSUP_triple_free (spo);
- if (LIKELY (add_rc == LSUP_OK)) rc = LSUP_OK;
- else if (add_rc < 0) {
- rc = add_rc;
- break;
- }
- }
- LSUP_graph_add_done (add_it);
- LSUP_graph_iter_free (it);
- return rc;
- }
- LSUP_GraphIterator *
- LSUP_graph_lookup_txn (
- void *txn, const LSUP_Graph *gr,
- const LSUP_Term *s, const LSUP_Term *p, const LSUP_Term *o,
- size_t *ct)
- {
- LSUP_GraphIterator *it;
- MALLOC_GUARD (it, NULL);
- LSUP_Buffer
- *ss = LSUP_term_serialize (s),
- *sp = LSUP_term_serialize (p),
- *so = LSUP_term_serialize (o),
- *sc = LSUP_term_serialize (gr->uri);
- it->data = gr->store->sif->lookup_fn (
- gr->store->data, ss, sp, so, sc, txn, ct);
- LSUP_buffer_free (ss);
- LSUP_buffer_free (sp);
- LSUP_buffer_free (so);
- LSUP_buffer_free (sc);
- if (UNLIKELY (!it->data)) {
- free (it);
- return NULL;
- }
- it->graph = gr;
- RCNL (graph_iter_alloc_buffers (it));
- return it;
- }
- LSUP_rc
- LSUP_graph_iter_next (LSUP_GraphIterator *it, LSUP_Triple **spo_p)
- {
- LSUP_rc rc = graph_iter_next_buffer (it);
- PRCCK (rc);
- if (rc != LSUP_OK) return rc;
- LSUP_Triple *spo = LSUP_triple_new (
- LSUP_term_new_from_buffer (it->sspo->s),
- LSUP_term_new_from_buffer (it->sspo->p),
- LSUP_term_new_from_buffer (it->sspo->o)
- );
- if (UNLIKELY (!spo)) return LSUP_MEM_ERR;
- *spo_p = spo;
- return LSUP_OK;
- }
- const LSUP_Graph *
- LSUP_graph_iter_graph (LSUP_GraphIterator *it)
- { return it->graph; }
- void
- LSUP_graph_iter_free (LSUP_GraphIterator *it)
- {
- it->graph->store->sif->lu_free_fn (it->data);
- /*
- * This deallocates resources properly by preserving borrowed pointers from
- * the store in case of LSUP_STORE_COW stores.
- */
- if (it->graph->store->sif->features & LSUP_STORE_COW) {
- LSUP_btriple_free_shallow (it->sspo);
- } else {
- // TODO copy-on-retrieval stores. None yet.
- }
- free (it);
- }
- bool
- LSUP_graph_contains (const LSUP_Graph *gr, const LSUP_Triple *spo)
- {
- LSUP_GraphIterator *it = LSUP_graph_lookup (
- gr, spo->s, spo->p, spo->o, NULL);
- LSUP_Triple *tmp_spo = NULL;
- bool rc = LSUP_graph_iter_next (it, &tmp_spo) != LSUP_END;
- LSUP_triple_free (tmp_spo);
- LSUP_graph_iter_free (it);
- return rc;
- }
- LSUP_LinkMap *
- LSUP_graph_connections (
- const LSUP_Graph *gr, LSUP_Term *t, LSUP_LinkType type)
- {
- LSUP_Term
- *s = NULL,
- *p = NULL,
- *o = NULL;
- // Position of passed term and link terms, respectively.
- LSUP_TriplePos pos1, pos2;
- if (type == LSUP_LINK_INBOUND) {
- o = t;
- pos1 = TRP_POS_O;
- pos2 = TRP_POS_P;
- } else if (type == LSUP_LINK_OUTBOUND) {
- s = t;
- pos1 = TRP_POS_S;
- pos2 = TRP_POS_P;
- } else if (type == LSUP_LINK_EDGE) {
- p = t;
- pos1 = TRP_POS_P;
- pos2 = TRP_POS_S;
- } else {
- // Very unlikely.
- log_error ("Invalid connection type: %d", type);
- return NULL;
- }
- // Gather all linking terms in a set first.
- LSUP_GraphIterator *it = LSUP_graph_lookup (gr, s, p, o, NULL);
- LSUP_TermSet *lts = LSUP_term_set_new();
- while (graph_iter_next_buffer (it) != LSUP_END) {
- LSUP_Term
- *ex = NULL,
- *ins = LSUP_term_new_from_buffer (
- LSUP_btriple_pos (it->sspo, pos2));
- LSUP_term_set_add (lts, ins, &ex);
- if (ex) LSUP_term_free (ins);
- }
- LSUP_graph_iter_free(it);
- LSUP_LinkMap *ret = LSUP_link_map_new (type);
- size_t i = 0;
- LSUP_Term *lt;
- while (LSUP_term_set_next (lts, &i, <) != LSUP_END) {
- LSUP_link_map_add (
- ret, LSUP_term_copy (lt),
- LSUP_graph_term_set (gr, t, pos1, lt, pos2));
- }
- LSUP_term_set_free (lts);
- return ret;
- }
- LSUP_TermSet *
- LSUP_graph_term_set (
- const LSUP_Graph *gr, LSUP_Term *t1, LSUP_TriplePos t1_pos,
- LSUP_Term *t2, LSUP_TriplePos t2_pos)
- {
- if (t1_pos == t2_pos) {
- log_error ("Term 1 and 2 positions cannot be the same!");
- return NULL;
- }
- LSUP_Term *spo_l[3] = {NULL};
- spo_l[t1_pos] = t1;
- spo_l[t2_pos] = t2;
- LSUP_TriplePos rpos = 0; // Position of term to be added to results.
- for (unsigned i = 0; i < 3; i++)
- if (t1_pos != i && t2_pos != i) rpos = i;
- LSUP_GraphIterator *it = LSUP_graph_lookup (
- gr, spo_l[0], spo_l[1], spo_l[2], NULL);
- LSUP_TermSet *ts = LSUP_term_set_new();
- while (graph_iter_next_buffer (it) != LSUP_END) {
- // There cannot be duplicates in a 2-bound lookup.
- LSUP_term_set_add (
- ts,
- LSUP_term_new_from_buffer (LSUP_btriple_pos (it->sspo, rpos)),
- NULL);
- }
- LSUP_graph_iter_free (it);
- return ts;
- }
- LSUP_TermSet *
- LSUP_graph_unique_terms (const LSUP_Graph *gr, LSUP_TriplePos pos)
- {
- // TODO We should use spo indices for stores that have them...
- LSUP_GraphIterator *it = LSUP_graph_lookup (gr, NULL, NULL, NULL, NULL);
- LSUP_TermSet *ts = LSUP_term_set_new();
- while (graph_iter_next_buffer (it) != LSUP_END) {
- LSUP_Term
- *ex = NULL,
- *ins = LSUP_term_new_from_buffer (LSUP_btriple_pos (it->sspo, pos));
- LSUP_term_set_add (ts, ins, &ex);
- if (ex) LSUP_term_free (ins);
- }
- LSUP_graph_iter_free(it);
- return ts;
- }
- size_t
- LSUP_graph_add_link_map (
- LSUP_GraphIterator *it, LSUP_Term *t, LSUP_LinkMap *lmap)
- {
- LSUP_Triple *spo = TRP_DUMMY;
- size_t ct = 0;
- LSUP_LinkMapIterator *lmit = LSUP_link_map_iter_new (lmap, t);
- while (LSUP_link_map_triples (lmit, spo) != LSUP_END) {
- LSUP_rc rc = LSUP_graph_add_iter (it, spo);
- if (rc >= 0) ct++;
- PRCCK (rc);
- }
- LSUP_link_map_iter_free (lmit);
- free (spo);
- return ct;
- }
- LSUP_Term *
- LSUP_bnode_add_collection (LSUP_GraphIterator *it, LSUP_TermSet *ts)
- {
- LSUP_NSMap *nsm = LSUP_graph_namespace (LSUP_graph_iter_graph (it));
- LSUP_Term
- *s = LSUP_term_new (LSUP_TERM_BNODE, NULL, NULL),
- *rdf_first = LSUP_iriref_new ("rdf:first", nsm),
- *rdf_rest = LSUP_iriref_new ("rdf:rest", nsm),
- *rdf_nil = LSUP_iriref_new ("rdf:nil", nsm),
- *link;
- LSUP_Triple *spo = TRP_DUMMY;
- link = s;
- size_t i = 0;
- LSUP_Term *t;
- while (LSUP_term_set_next (ts, &i, &t) != LSUP_END) {
- spo->s = link;
- spo->p = rdf_first;
- spo->o = t;
- PRCNL (LSUP_graph_add_iter (it, spo));
- spo->p = rdf_rest;
- size_t save_i = i; // Save iterator position to restore it after peek.
- spo->o = (
- // Peek into the next result.
- LSUP_term_set_next (ts, &i, NULL) != LSUP_END ?
- LSUP_term_new (LSUP_TERM_BNODE, NULL, NULL)
- : rdf_nil);
- i = save_i; // Restore the iterator that advanced when peeking.
- PRCNL (LSUP_graph_add_iter (it, spo));
- if (link != s) LSUP_term_free (link);
- // Current object becomes next subject. Irrelevant for last item.
- link = spo->o;
- }
- LSUP_term_free (rdf_first);
- LSUP_term_free (rdf_rest);
- LSUP_term_free (rdf_nil);
- free (spo);
- return s;
- }
- /*
- * Static functions.
- */
- /** @brief Advance an iterator and return a serialized triple.
- *
- * This is an internal function to pass raw buffers between higher-level
- * functions without serializing and deserializing triples.
- *
- * The results are stored in it->sspo.
- */
- inline static LSUP_rc
- graph_iter_next_buffer (LSUP_GraphIterator *it)
- { return it->graph->store->sif->lu_next_fn (it->data, it->sspo, NULL); }
- /** @brief Properly allocate temporary byte buffers in advance of iteration.
- */
- inline LSUP_rc
- graph_iter_alloc_buffers (LSUP_GraphIterator *it)
- {
- if (it->graph->store->sif->features & LSUP_STORE_COW) {
- it->sspo = BTRP_DUMMY;
- CALLOC_GUARD (it->sspo->s, LSUP_MEM_ERR);
- CALLOC_GUARD (it->sspo->p, LSUP_MEM_ERR);
- CALLOC_GUARD (it->sspo->o, LSUP_MEM_ERR);
- } else {
- // TODO copy-on-retrieval stores. None yet.
- }
- return LSUP_OK;
- }
- /**
- * Extern inline definitions.
- */
- size_t LSUP_graph_size (const LSUP_Graph *gr);
|