lsup_rdf/src/graph.c

#include "store_htable.h"
#include "store_mdb.h"
#include "graph.h"

// Initial size of lookup graph. It will double each time capacity is reached.
#define LOOKUP_GR_INIT_SIZE 64

// Expand hash table memory by this factor to keep a good load factor.
#define PREALLOC_FACTOR 1.4

// Assume VERY coarsly that the number of unique terms will be in general
// 1.7 times the number of triples. This is conservative to maintain load
// factor low.
#define IDX_SIZE_RATIO 1.7

typedef enum KSetFlag {
    LSUP_KS_NONE        = 0,
    LSUP_KS_CHECK_CAP   = 1 << 0,
    LSUP_KS_CHECK_DUP   = 1 << 1,
} KSetFlag;


typedef struct Graph {
    const LSUP_Env *        env;            // LSUP environment.
    LSUP_store_type         store_type;     // Back end type: in-memory or MDB.
    LSUP_Term               *uri;           // Graph "name" (URI)
    union {                                 // Back end, defined by store_type.
        LSUP_HTStore *      ht_store;
        LSUP_MDBStore *     mdb_store;
    };
    LSUP_NSMap *        nsm;            // Namespace map.
} Graph;


typedef struct GraphIterator {
    const Graph *           graph;      // Parent graph.
    union {                             // Internal store iterator.
        LSUP_HTIterator *   ht_iter;
        LSUP_MDBIterator *  mdb_iter;
    };
    size_t                  ct;         // Total matches.
} GraphIterator;


/**
 * Extern inline functions.
 */
size_t LSUP_graph_size (const LSUP_Graph *gr);


/* * * Post-lookup callback prototypes * * */

int match_add_fn(
        LSUP_Graph *src, LSUP_Graph *dest, const LSUP_TripleKey *spok,
        void *ctx);


int match_rm_fn(
        LSUP_Graph *src, LSUP_Graph *dest, const LSUP_TripleKey *spok,
        void *ctx);

static LSUP_rc
graph_iter_next_buffer (GraphIterator *it, LSUP_SerTriple *sspo);


static inline bool is_null_trp (const LSUP_TripleKey *trp)
{
    return (
            *trp[0] == NULL_KEY &&
            *trp[1] == NULL_KEY &&
            *trp[2] == NULL_KEY);
}

#define ENTRY(a, b) (be) == (LSUP_STORE_##a) ||
static inline bool
check_backend (LSUP_store_type be)
{ return (BACKEND_TBL false); }
#undef ENTRY


/* * * GRAPH * * */

Graph *
LSUP_graph_new_env (const LSUP_Env *env, const LSUP_store_type store_type)
{
    if (UNLIKELY (!env)) return NULL;
    if (UNLIKELY (!check_backend (store_type))) return NULL;

    LSUP_Graph *gr;
    MALLOC_GUARD (gr, NULL);

    gr->uri = LSUP_uri_new (NULL);
    gr->store_type = store_type;
    gr->env = env;
    gr->nsm = env->nsm;

    if (gr->store_type == LSUP_STORE_MEM) {
        gr->ht_store = LSUP_htstore_new();
        if (UNLIKELY (!gr->ht_store)) return NULL;

    } else if (gr->store_type == LSUP_STORE_MDB) {
        gr->mdb_store = env->mdbstore;

    } else { // LSUP_STORE_MDB_TMP
        gr->mdb_store = env->mdbstore_ramdisk;
    }

    log_debug ("Graph created.");
    return gr;
}


/**
 * Copy triples from a source graph into a destination one.
 *
 * The destination graph is not initialized here, so the copy is cumulative.
 */
static LSUP_rc
graph_copy_contents (const LSUP_Graph *src, LSUP_Graph *dest)
{
    LSUP_rc rc = LSUP_NOACTION;

    GraphIterator *it = LSUP_graph_lookup (src, NULL, NULL, NULL, NULL);

    LSUP_SerTriple sspo;

    LSUP_GraphIterator *add_it = LSUP_graph_add_init (dest);
    while (graph_iter_next_buffer (it, &sspo) != LSUP_END) {
        log_debug ("Inserting triple #%lu", LSUP_graph_iter_cur (it));
        LSUP_rc add_rc = LSUP_graph_add_iter (add_it, &sspo);
        if (LIKELY (add_rc == LSUP_OK)) rc = LSUP_OK;
        else if (add_rc < 0) return add_rc;
    }
    LSUP_graph_add_done (it);

    return rc;
}


LSUP_Graph *
LSUP_graph_copy (const Graph *src)
{
    LSUP_Graph *dest = LSUP_graph_new_env (src->env, src->store_type);
    if (UNLIKELY (!dest)) return NULL;

    LSUP_rc rc = graph_copy_contents (src, dest);
    if (UNLIKELY (rc != LSUP_OK)) return NULL;

    return dest;
}


// TODO support boolean ops between any types of graphs.
Graph *
LSUP_graph_bool_op(
        const LSUP_bool_op op, const Graph *gr1, const Graph *gr2)
{
    if (UNLIKELY (gr1->store_type != LSUP_STORE_MEM)) {
        fprintf(
                stderr,
                "First operand %s is not an in-memory graph. "
                "Cannot perform boolean operation.",
                gr1->uri->data);
        return NULL;
    }
    if (UNLIKELY (gr2->store_type != LSUP_STORE_MEM)) {
        fprintf(
                stderr,
                "Second operand %s is not an in-memory graph. "
                "Cannot perform boolean operation.",
                gr2->uri->data);
        return NULL;
    }

    LSUP_Graph *res = LSUP_graph_new (LSUP_STORE_MEM);
    res->ht_store = LSUP_htstore_bool_op (op, gr1->ht_store, gr2->ht_store);

    return res;
}


void
LSUP_graph_free (LSUP_Graph *gr)
{
    if (LIKELY (gr != NULL)) {
        LSUP_term_free (gr->uri);

        if (gr->store_type == LSUP_STORE_MEM)
            LSUP_htstore_free (gr->ht_store);
        /*
        // NOTE This is not required bacause MDB store is only one for now,
        // cleared at exit.
        else
            LSUP_mdbstore_free (gr->mdb_store);
        */

        free (gr);
    }
}


LSUP_Term *
LSUP_graph_uri (const LSUP_Graph *gr) { return gr->uri; }


LSUP_rc
LSUP_graph_set_uri (LSUP_Graph *gr, const char *uri)
{ return LSUP_uri_init (gr->uri, uri); }


LSUP_NSMap *
LSUP_graph_namespace (const Graph *gr)
{ return gr->nsm; }


void
LSUP_graph_set_namespace (Graph *gr, LSUP_NSMap *nsm)
{ if (gr->store_type == LSUP_STORE_MEM) gr->nsm = nsm; }


size_t
LSUP_graph_size (const Graph *gr)
{
    if (gr->store_type == LSUP_STORE_MEM)
        return LSUP_htstore_size (gr->ht_store);
    else {
        size_t ct;
        LSUP_GraphIterator *it = LSUP_graph_lookup (gr, NULL, NULL, NULL, &ct);

        LSUP_graph_iter_free (it);

        return ct;
    }
}


bool
LSUP_graph_equals (const Graph *gr1, const Graph *gr2)
{
    LSUP_Graph *res = LSUP_graph_bool_op (LSUP_BOOL_XOR, gr1, gr2);

    return (LSUP_graph_size (res) == 0);
}


GraphIterator *
LSUP_graph_add_init (LSUP_Graph *gr)
{
    GraphIterator *it;
    CALLOC_GUARD (it, NULL);

    if (gr->store_type == LSUP_STORE_MEM) {
        it->ht_iter = LSUP_htstore_add_init (gr->ht_store);
    } else {
        LSUP_Buffer *sc = LSUP_buffer_new_from_term (gr->uri);
        it->mdb_iter = LSUP_mdbstore_add_init (gr->mdb_store, sc);
        LSUP_buffer_free (sc);
    }

    it->graph = gr;

    return it;
}


LSUP_rc
LSUP_graph_add_iter (LSUP_GraphIterator *it, const LSUP_SerTriple *sspo)
{
    if (it->graph->store_type == LSUP_STORE_MEM) {
        return LSUP_htstore_add_iter (it->ht_iter, sspo);
    } else {
        return LSUP_mdbstore_add_iter (it->mdb_iter, sspo);
    }
}


void
LSUP_graph_add_done (LSUP_GraphIterator *it)
{
    if (it->graph->store_type == LSUP_STORE_MEM) {
        LSUP_htstore_add_done (it->ht_iter);
    } else {
        LSUP_mdbstore_add_done (it->mdb_iter);
    }

    free (it);
    log_trace ("Done adding.");
}


LSUP_rc
LSUP_graph_add (
        Graph *gr, const LSUP_Triple trp[],
        const LSUP_SerTriple strp[], size_t *inserted)
{
    /*
     * NOTE It is possible to pass both sets of RDF triples and buffer triples.
     */

    LSUP_rc rc = LSUP_NOACTION;

    // Initialize iterator.
    LSUP_GraphIterator *it = LSUP_graph_add_init (gr);

    // Serialize and insert RDF triples.
    LSUP_SerTriple *sspo = LSUP_striple_new (BUF_DUMMY, BUF_DUMMY, BUF_DUMMY);
    if (UNLIKELY (!sspo)) return LSUP_MEM_ERR;

    if (trp) {
        for (size_t i = 0; trp[i].s != NULL; i++) {
            log_trace ("Inserting triple #%lu", i);

            LSUP_triple_serialize (trp + i, sspo);
            LSUP_rc db_rc = LSUP_graph_add_iter (it, sspo);

            if (db_rc == LSUP_OK) rc = LSUP_OK;
            if (UNLIKELY (db_rc < 0)) return db_rc;
        }
    }
    LSUP_striple_free (sspo);

    // Insert serialized triples.
    if (strp) {
        for (size_t i = 0; strp[i].s != NULL; i++) {
            log_trace ("Inserting serialized triple #%lu", i);
            LSUP_rc db_rc = LSUP_graph_add_iter (it, strp + i);

            if (db_rc == LSUP_OK) rc = LSUP_OK;
            if (UNLIKELY (db_rc < 0)) return db_rc;
        }
    }

    if (inserted) {
        if (gr->store_type == LSUP_STORE_MEM) {
            *inserted = LSUP_htiter_cur (it->ht_iter);
        } else {
            *inserted = LSUP_mdbiter_cur (it->mdb_iter);
        }
    }

    LSUP_graph_add_done (it);

    return rc;
}


LSUP_rc
LSUP_graph_remove (
        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_buffer_new_from_term (s);
    LSUP_Buffer *sp = LSUP_buffer_new_from_term (p);
    LSUP_Buffer *so = LSUP_buffer_new_from_term (o);
    LSUP_Buffer *sc = LSUP_buffer_new_from_term (gr->uri);

    if (gr->store_type == LSUP_STORE_MEM)
        rc = LSUP_htstore_remove (gr->ht_store, ss, sp, so, ct);
    else
        rc = LSUP_mdbstore_remove (gr->mdb_store, ss, sp, so, sc, ct);

    LSUP_buffer_free (ss);
    LSUP_buffer_free (sp);
    LSUP_buffer_free (so);
    LSUP_buffer_free (sc);

    return rc;
}


GraphIterator *
LSUP_graph_lookup (const Graph *gr, const LSUP_Term *s, const LSUP_Term *p,
        const LSUP_Term *o, size_t *ct)
{
    GraphIterator *it;
    MALLOC_GUARD (it, NULL);

    it->graph = gr;

    LSUP_Buffer *ss = LSUP_buffer_new_from_term (s);
    LSUP_Buffer *sp = LSUP_buffer_new_from_term (p);
    LSUP_Buffer *so = LSUP_buffer_new_from_term (o);
    LSUP_Buffer *sc = LSUP_buffer_new_from_term (gr->uri);

    if (it->graph->store_type == LSUP_STORE_MEM) {
        it->ht_iter = LSUP_htstore_lookup (it->graph->ht_store, ss, sp, so);
        if (ct) *ct = it->ct;

    } else it->mdb_iter = LSUP_mdbstore_lookup (
            it->graph->mdb_store, ss, sp, so, sc, ct);

    LSUP_buffer_free (ss);
    LSUP_buffer_free (sp);
    LSUP_buffer_free (so);
    LSUP_buffer_free (sc);

    return it;
}


/** @brief Advance iterator and return serialized triple.
 *
 * This is an internal function to pass raw buffers between higher-level
 * functions without serializing and deserializing triples.
 */
inline static LSUP_rc
graph_iter_next_buffer (GraphIterator *it, LSUP_SerTriple *sspo)
{
    LSUP_rc rc;

    if (it->graph->store_type == LSUP_STORE_MEM)
        rc = LSUP_htiter_next (it->ht_iter, sspo);
    else rc = LSUP_mdbiter_next (it->mdb_iter, sspo);

    return rc;
}


LSUP_rc
LSUP_graph_iter_next (GraphIterator *it, LSUP_Triple *spo)
{
    /*
     * NOTE: Memory and MDB back ends treat sspo differently, whereas the
     * memory one owns the whole buffer structure, while the MDB one owns only
     * the data. Therefore they must be initialized and freed differently.
     */

    LSUP_SerTriple *sspo;
    LSUP_Buffer *ss, *sp, *so;

    if (it->graph->store_type == LSUP_STORE_MEM) {
        ss = sp = so = NULL;
    } else {
        // Craft buffers manually so that their addresses are NULL and need not
        // be freed.
        CALLOC_GUARD (ss, LSUP_MEM_ERR);
        CALLOC_GUARD (sp, LSUP_MEM_ERR);
        CALLOC_GUARD (so, LSUP_MEM_ERR);
    }
    sspo = LSUP_striple_new (ss, sp, so);

    LSUP_rc rc = graph_iter_next_buffer (it, sspo);

    if (rc == LSUP_OK) {
        spo->s = LSUP_term_new_from_buffer (sspo->s);
        spo->p = LSUP_term_new_from_buffer (sspo->p);
        spo->o = LSUP_term_new_from_buffer (sspo->o);

    }

    if (it->graph->store_type == LSUP_STORE_MEM) free (sspo);
    else LSUP_striple_free_shallow (sspo);

    return rc;
}


void
LSUP_graph_iter_free (GraphIterator *it)
{
    if (it->graph->store_type == LSUP_STORE_MEM)
        LSUP_htiter_free (it->ht_iter);
    else
        LSUP_mdbiter_free (it->mdb_iter);

    free (it);
}


size_t
LSUP_graph_iter_cur (GraphIterator *it)
{ return LSUP_mdbiter_cur (it->mdb_iter); }


bool
LSUP_graph_contains (const LSUP_Graph *gr, const LSUP_Triple *spo)
{
    GraphIterator *it = LSUP_graph_lookup (
            gr, spo->s, spo->p, spo->o, NULL);
    LSUP_Triple *tmp_spo = LSUP_triple_new (TERM_DUMMY, TERM_DUMMY, TERM_DUMMY);
    bool rc = LSUP_graph_iter_next (it, tmp_spo) != LSUP_END;

    LSUP_triple_free (tmp_spo);
    LSUP_graph_iter_free (it);

    return rc;
}


/* * * Static functions * * */