lsup_rdf/src/store_htable.c

#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.
    LSUP_Buffer *       sterm;      ///> Serialized term.
} 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)
{ LSUP_buffer_free (((IndexEntry *) item)->sterm); }


/* * * 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);


/* * * API * * */

HTStore *
LSUP_htstore_new (const 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;
}


HTStore *
LSUP_htstore_copy (const HTStore *src)
{
    HTStore *dest = LSUP_htstore_new (LSUP_htstore_size (src));
    if (UNLIKELY (!dest)) return NULL;

    if (UNLIKELY (LSUP_htstore_copy_contents (dest, src) < 0)) {
        LSUP_htstore_free (dest);
        return NULL;
    }

    return dest;
}


LSUP_rc
LSUP_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;
}


HTStore *
LSUP_htstore_bool_op(
        const LSUP_bool_op op, const HTStore *s1, const HTStore *s2)
{
    if (UNLIKELY (
            op != LSUP_BOOL_UNION
            && op != LSUP_BOOL_SUBTRACTION
            && op != LSUP_BOOL_INTERSECTION
            && op != LSUP_BOOL_XOR)) {
        log_error ("Invalid boolean operation.");

        return NULL;
    }

    HTStore *dest = LSUP_htstore_new (0);

    if (op == LSUP_BOOL_UNION) {
        dest = LSUP_htstore_copy (s1);
        if (UNLIKELY (!dest) || LSUP_htstore_copy_contents (dest, s2) < 0)
            goto fail;

        return dest;
    }

    LSUP_TripleKey *src_tkey;

    LSUP_HTIterator *it = LSUP_htstore_add_init(dest);

    size_t i = 0;
    if (op == LSUP_BOOL_XOR) {
        // Add triples from s2 if not found in s1.
        while (hashmap_iter (s2->keys, &i, (void **) &src_tkey)) {
            if (!hashmap_get (s1->keys, src_tkey))
                htstore_add_key_iter (it, *src_tkey);
        }
    }

    i = 0;
    while (hashmap_iter (s1->keys, &i, (void **) &src_tkey)) {
        // For XOR and subtraction, add if not found.
        // For intersection, add if found.
        if (
            (op == LSUP_BOOL_INTERSECTION)
            ^ (hashmap_get (s2->keys, src_tkey) == NULL)
        )
            htstore_add_key_iter (it, *src_tkey);
    }
    LSUP_htstore_add_done (it);

    return dest;

fail:
    LSUP_htstore_free (dest);
    return NULL;
}


void
LSUP_htstore_free (HTStore *ht)
{
    hashmap_free (ht->idx);
    hashmap_free (ht->keys);
    free (ht);
}


size_t
LSUP_htstore_size (const LSUP_HTStore *ht)
{ return hashmap_count (ht->keys); }


LSUP_rc
LSUP_htstore_add_term (HTStore *store, const LSUP_Buffer *sterm)
{
    if (hashmap_get (store->idx, sterm)) return LSUP_NOACTION;

    LSUP_Key tk = LSUP_buffer_hash (sterm);
    log_trace ("Adding term key: %lx", tk);

    hashmap_set (
            store->idx, &(IndexEntry){
                .key = tk,
                // This shall be freed with the index hashmap.
                .sterm = LSUP_buffer_new (sterm->size, sterm->addr)
            });

    return LSUP_OK;
}


LSUP_HTIterator *
LSUP_htstore_add_init (HTStore *store)
{
    HTIterator *it;
    MALLOC_GUARD (it, NULL);

    it->store = store;

    return it;
}


LSUP_rc
LSUP_htstore_add_iter (HTIterator *it, const LSUP_BufferTriple *sspo)
{
    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++) {
        rc = LSUP_htstore_add_term (it->store, LSUP_btriple_pos (sspo, i));
        if (rc != LSUP_OK) return rc;
    }

    return rc;
}


void
LSUP_htstore_add_done (HTIterator *it)
{ LSUP_htiter_free (it); }


LSUP_rc
LSUP_htstore_remove(
        LSUP_HTStore *store, const LSUP_Buffer *ss, const LSUP_Buffer *sp,
        const LSUP_Buffer *so,  size_t *ct)
{
    LSUP_rc rc = LSUP_NOACTION;

    LSUP_HTIterator *it = LSUP_htstore_lookup (store, ss, sp, so, ct);
    if (UNLIKELY (!it)) return LSUP_DB_ERR;

    while (htiter_next_key (it)) {
        if (it->rc == LSUP_OK) {
            LSUP_TripleKey *del = hashmap_delete (store->keys, it->entry);
            free (del);
            rc = LSUP_OK;
        }
    }

    LSUP_htiter_free (it);

    return rc;
}


HTIterator *
LSUP_htstore_lookup (HTStore *store, const LSUP_Buffer *ss,
        const LSUP_Buffer *sp, const LSUP_Buffer *so, size_t *ct)
{
    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)++;
            log_trace ("ct: %lu", *ct);
        }
        // Reposition cursor to the hashtable beginning.
        it->cur = 0;
        it->rc = LSUP_OK;
    }

    return it;
}


void
LSUP_htiter_free (LSUP_HTIterator *it)
{ free (it); }

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


LSUP_rc
LSUP_htiter_next (HTIterator *it, LSUP_BufferTriple *sspo)
{
    LSUP_rc rc = htiter_next_key (it);
    if (rc != LSUP_OK) return rc;

    return tkey_to_strp (it->store, *it->entry, sspo);
}


/* * * 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;

    tmp = hashmap_get (store->idx, spok + 0);
    if (UNLIKELY (!tmp)) return LSUP_DB_ERR;
    sspo->s = tmp->sterm;

    tmp = hashmap_get (store->idx, spok + 1);
    if (UNLIKELY (!tmp)) return LSUP_DB_ERR;
    sspo->p = tmp->sterm;

    tmp = hashmap_get (store->idx, spok + 2);
    if (UNLIKELY (!tmp)) return LSUP_DB_ERR;
    sspo->o = tmp->sterm;

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