123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494 |
- #include "hashmap.h"
- #include "store_htable.h"
- /**
- * Callback type for key comparison.
- */
- typedef bool (*LSUP_key_eq_fn_t)(
- const LSUP_Key spok[], const LSUP_Key luk[]);
- typedef struct idx_entry_t {
- LSUP_Key key; ///< Serialized term key.
- void * data; ///< Serialized term data.
- size_t size; ///< Serialized term size.
- } IndexEntry;
- typedef struct ht_store_t {
- struct hashmap * keys; ///< Triple keys (set).
- struct hashmap * idx; ///< Map of keys to serialized terms.
- } HTStore;
- typedef struct ht_iterator_t {
- HTStore * store; ///< Store being iterated.
- size_t cur; ///< Internal hash table cursor.
- LSUP_Key luk[3]; ///< 0÷3 lookup keys.
- LSUP_key_eq_fn_t eq_fn; ///< Equality function to test triples.
- int rc; ///< Return code for *next* result.
- ///< When the end of results is reached,
- ///< this is set to LSUP_END.
- LSUP_TripleKey * entry; ///< Retrieved SPO key.
- } HTIterator;
- /**
- * Dummy callback for queries with all parameters unbound. Returns true.
- */
- static bool lookup_none_eq_fn (
- const LSUP_Key spok[], const LSUP_Key luk[])
- { return true; }
- /**
- * Keyset lookup for S key.
- */
- static bool lookup_sk_eq_fn (
- const LSUP_Key spok[], const LSUP_Key luk[])
- { return spok[0] == luk[0]; }
- /**
- * Keyset lookup for P key.
- */
- static bool lookup_pk_eq_fn (
- const LSUP_Key spok[], const LSUP_Key luk[])
- { return spok[1] == luk[1]; }
- /**
- * Keyset lookup for O key.
- */
- static bool lookup_ok_eq_fn (
- const LSUP_Key spok[], const LSUP_Key luk[])
- { return spok[2] == luk[2]; }
- /**
- * Keyset lookup for S and P keys.
- */
- static bool lookup_spk_eq_fn (
- const LSUP_Key spok[], const LSUP_Key luk[])
- { return spok[0] == luk[0] && spok[1] == luk[1]; }
- /**
- * Keyset lookup for S and O keys.
- */
- static bool lookup_sok_eq_fn (
- const LSUP_Key spok[], const LSUP_Key luk[])
- { return spok[0] == luk[0] && spok[2] == luk[2]; }
- /**
- * Keyset lookup for P and O keys.
- */
- static bool lookup_pok_eq_fn (
- const LSUP_Key spok[], const LSUP_Key luk[])
- { return spok[1] == luk[1] && spok[2] == luk[2]; }
- /**
- * Keyset lookup for S, P and O keys.
- */
- static bool lookup_spok_eq_fn (
- const LSUP_Key spok[], const LSUP_Key luk[])
- { return spok[0] == luk[0] && spok[1] == luk[1] && spok[2] == luk[2]; }
- /* * * CALLBACKS * * */
- uint64_t trp_key_hash_fn (
- const void *item, uint64_t seed0, uint64_t seed1)
- { return (uint64_t) (LSUP_HASH (item, TRP_KLEN, seed0)); }
- int trp_key_cmp_fn (const void *a, const void *b, void *udata)
- { return memcmp (a, b, TRP_KLEN); }
- /**
- * Hash callback function for index hashmap.
- */
- static uint64_t htstore_idx_hash_fn (
- const void *item, uint64_t seed0, uint64_t seed1)
- { return ((IndexEntry *) item)->key; }
- /**
- * Compare callback function for index hashmap.
- */
- static int htstore_idx_cmp_fn (const void *a, const void *b, void *udata)
- { return ((const IndexEntry *) a)->key - ((const IndexEntry *) b)->key; }
- /**
- * Delete callback function for hashmap.
- */
- static void htstore_idx_free_fn (void *item)
- { free (((IndexEntry *) item)->data); }
- /* * * Other prototypes. * * */
- inline static LSUP_rc
- tkey_to_strp (
- const HTStore *store, const LSUP_Key *spok, LSUP_BufferTriple *sspo);
- static LSUP_rc
- htstore_add_key_iter (HTIterator *it, const LSUP_Key *spok);
- /** @brief Advance iterator by next key.
- *
- * Result is stored in it->entry.
- */
- static LSUP_rc
- htiter_next_key (HTIterator *it);
- /*
- * Interface members.
- */
- /** @brief Create a store for an individual graph.
- *
- * @param[in] id Graph identifier. This may or may not be set. The store does
- * not use this value internally, and does not check for duplicates.
- *
- * @param[in] size Initial size of the store (in number of triples to
- * preallocate). It may be 0.
- *
- * @return New graph store.
- */
- static void *
- htstore_new (const char *id, size_t size)
- {
- HTStore *ht;
- CALLOC_GUARD (ht, NULL);
- ht->idx = hashmap_new (
- sizeof (IndexEntry), 0, LSUP_HASH_SEED, 0,
- htstore_idx_hash_fn, htstore_idx_cmp_fn, htstore_idx_free_fn,
- NULL);
- ht->keys = hashmap_new (
- sizeof (LSUP_TripleKey), size, LSUP_HASH_SEED, 0,
- trp_key_hash_fn, trp_key_cmp_fn, NULL,
- NULL);
- return ht;
- }
- #if 0
- static LSUP_rc
- htstore_copy_contents (HTStore *dest, const HTStore *src)
- {
- size_t i = 0;
- LSUP_TripleKey *spok;
- IndexEntry *entry;
- while (hashmap_iter (src->keys, &i, (void **) &spok)) {
- hashmap_set (dest->keys, spok);
- if (UNLIKELY (hashmap_oom (dest->keys))) return LSUP_MEM_ERR;
- }
- i = 0;
- while (hashmap_iter (src->idx, &i, (void **) &entry)) {
- hashmap_set (dest->idx, entry);
- if (UNLIKELY (hashmap_oom (dest->idx))) return LSUP_MEM_ERR;
- }
- return LSUP_OK;
- }
- #endif
- static void
- htstore_free (void *h)
- {
- HTStore *store = h;
- hashmap_free (store->idx);
- hashmap_free (store->keys);
- free (store);
- }
- static size_t
- htstore_size (const void *h)
- {
- const HTStore *store = h;
- return hashmap_count (store->keys);
- }
- static LSUP_rc
- htstore_add_term (void *h, const LSUP_Buffer *sterm, void *_unused)
- {
- (void) _unused;
- HTStore *store = h;
- IndexEntry entry_s = {
- .key = LSUP_buffer_hash (sterm),
- };
- if (hashmap_get (store->idx, &entry_s)) return LSUP_NOACTION;
- entry_s.data = malloc (sterm->size);
- memcpy (entry_s.data, sterm->addr, sterm->size);
- entry_s.size = sterm->size;
- log_trace ("Adding term key: %lx", entry_s.key);
- hashmap_set (store->idx, &entry_s);
- //log_trace ("Term index size: %lu", hashmap_count (store->idx));
- return LSUP_OK;
- }
- static void *
- htstore_add_init (void *h, const LSUP_Buffer *_unused, void *_unused2)
- {
- (void) _unused;
- (void) _unused2;
- HTIterator *it;
- MALLOC_GUARD (it, NULL);
- it->store = h;
- return it;
- }
- static LSUP_rc
- htstore_add_iter (void *h, const LSUP_BufferTriple *sspo)
- {
- HTIterator *it = h;
- LSUP_TripleKey spok = {
- LSUP_buffer_hash (sspo->s),
- LSUP_buffer_hash (sspo->p),
- LSUP_buffer_hash (sspo->o),
- };
- LSUP_rc rc = htstore_add_key_iter (it, spok);
- if (rc != LSUP_OK) return rc;
- for (int i = 0; i < 3; i++)
- htstore_add_term (it->store, LSUP_btriple_pos (sspo, i), NULL);
- return rc;
- }
- static LSUP_rc
- htstore_add_done (void *h)
- {
- free (h);
- return LSUP_OK;
- }
- static void *
- htstore_lookup (
- void *h,
- const LSUP_Buffer *ss, const LSUP_Buffer *sp, const LSUP_Buffer *so,
- const LSUP_Buffer *sc, void *_unused, size_t *ct)
- {
- (void) _unused;
- HTStore *store = h;
- HTIterator *it;
- CALLOC_GUARD (it, NULL);
- it->store = store;
- it->rc = LSUP_END;
- if (hashmap_count (store->keys) == 0) return it;
- if (ct) *ct = 0;
- it->luk[0] = LSUP_buffer_hash (ss);
- it->luk[1] = LSUP_buffer_hash (sp);
- it->luk[2] = LSUP_buffer_hash (so);
- // s p o
- if (ss && sp && so) {
- it->eq_fn = lookup_spok_eq_fn;
- } else if (ss) {
- // s p ?
- if (sp) {
- it->eq_fn = lookup_spk_eq_fn;
- // s ? o
- } else if (so) {
- it->eq_fn = lookup_sok_eq_fn;
- // s ? ?
- } else {
- it->eq_fn = lookup_sk_eq_fn;
- }
- } else if (sp) {
- // ? p o
- if (so) {
- it->eq_fn = lookup_pok_eq_fn;
- // ? p ?
- } else it->eq_fn = lookup_pk_eq_fn;
- // ? ? o
- } else if (so) {
- it->eq_fn = lookup_ok_eq_fn;
- // ? ? ?
- } else it->eq_fn = lookup_none_eq_fn;
- log_trace ("LUK: {%lx, %lx, %lx}", it->luk[0], it->luk[1], it->luk[2]);
- if (ct) {
- // Loop over results to determine count.
- while (htiter_next_key (it) == LSUP_OK) (*ct)++;
- // Reposition cursor to the hashtable beginning.
- it->cur = 0;
- it->rc = LSUP_OK;
- }
- return it;
- }
- static LSUP_rc
- htstore_remove(
- void *h, const LSUP_Buffer *ss, const LSUP_Buffer *sp,
- const LSUP_Buffer *so, const LSUP_Buffer *_unused,
- void *_unused2, size_t *ct_p)
- {
- (void) _unused;
- (void) _unused2;
- HTStore *store = h;
- size_t ct;
- HTIterator *it = htstore_lookup (store, ss, sp, so, NULL, NULL, &ct);
- if (UNLIKELY (!it)) return LSUP_DB_ERR;
- LSUP_rc rc;
- if (ct == 0) {
- rc = LSUP_NOACTION;
- goto finally;
- }
- while (htiter_next_key (it) == LSUP_OK) {
- log_trace (
- "Deleting {%lx, %lx, %lx}.",
- it->entry[0][0], it->entry[0][1], it->entry[0][2]);
- hashmap_delete (store->keys, it->entry);
- rc = LSUP_OK;
- it->cur = 0; // Reset cursor, buckets are rearranged after deletion.
- }
- finally:
- free (it);
- if (ct_p) *ct_p = ct;
- return rc;
- }
- static LSUP_rc
- htiter_next_key (HTIterator *it)
- {
- if (UNLIKELY (!it)) return LSUP_VALUE_ERR;
- // This value is for internal looping only. It shall never be returned.
- it->rc = LSUP_NORESULT;
- do {
- // Loop through all triples until a match is found, or end is reached.
- if (hashmap_iter (it->store->keys, &it->cur, (void **) &it->entry)) {
- //log_trace("it->cur: %lu", it->cur);
- if (it->eq_fn (*it->entry, it->luk)) {
- log_trace (
- "Found spok: {%lx, %lx, %lx}",
- it->entry[0][0], it->entry[0][1], it->entry[0][2]
- );
- it->rc = LSUP_OK;
- }
- }
- else it->rc = LSUP_END;
- } while (it->rc == LSUP_NORESULT);
- return it->rc;
- }
- static LSUP_rc
- htiter_next (void *h, LSUP_BufferTriple *sspo, LSUP_Buffer **_unused)
- {
- (void) _unused;
- HTIterator *it = h;
- LSUP_rc rc = htiter_next_key (it);
- if (rc != LSUP_OK) return rc;
- return tkey_to_strp (it->store, *it->entry, sspo);
- }
- const LSUP_StoreInt htstore_int = {
- .name = "Hash Table Store",
- .features = LSUP_STORE_COW,
- .setup_fn = NULL,
- .new_fn = htstore_new,
- .free_fn = htstore_free,
- .size_fn = htstore_size,
- .add_init_fn = htstore_add_init,
- .add_iter_fn = htstore_add_iter,
- .add_done_fn = htstore_add_done,
- .add_term_fn = htstore_add_term,
- .lookup_fn = htstore_lookup,
- .lu_next_fn = htiter_next,
- .lu_free_fn = free,
- .remove_fn = htstore_remove,
- };
- /*
- * Other statics.
- */
- inline static LSUP_rc
- tkey_to_strp (
- const HTStore *store, const LSUP_Key *spok, LSUP_BufferTriple *sspo)
- {
- // Data owned by the store.
- IndexEntry *tmp;
- for (int i = 0; i < 3; i++) {
- tmp = hashmap_get (store->idx, spok + i);
- if (UNLIKELY (!tmp)) return LSUP_DB_ERR;
- LSUP_btriple_pos(sspo, i)->addr = tmp->data;
- LSUP_btriple_pos(sspo, i)->size = tmp->size;
- }
- return LSUP_OK;
- }
- static LSUP_rc
- htstore_add_key_iter (HTIterator *it, const LSUP_Key *spok)
- {
- // Add triple.
- log_trace ("Inserting spok: {%lx, %lx, %lx}", spok[0], spok[1], spok[2]);
- if (hashmap_get (it->store->keys, spok)) {
- log_trace ("Triple found. Not adding.");
- return LSUP_NOACTION;
- }
- log_trace ("Triple not found, inserting.");
- hashmap_set (it->store->keys, (void *)spok);
- if (hashmap_oom(it->store->keys)) return LSUP_MEM_ERR;
- return LSUP_OK;
- }
|