store_mdb.c

Go to the documentation of this file.

#include "volksdata/store_mdb.h"

#define N_DB 9

#if (defined DEBUG || defined TESTING)
#define DEFAULT_MAPSIZE 1<<24 // 16Mb (limit for Valgrind)
#elif !(defined __LP64__ || defined __LLP64__) || \
        defined _WIN32 && !defined _WIN64
#define DEFAULT_MAPSIZE 1<<31 // 2Gb (limit for 32-bit systems)
#else
#define DEFAULT_MAPSIZE 1UL<<40 // 1Tb
#endif
 
#define ENV_DIR_MODE 0750
#define ENV_FILE_MODE 0640
 
/*
 * Data types.
 */
 
typedef char DbLabel[8];
typedef struct mdbstore_iter_t MDBIterator;

typedef enum {
    LSSTORE_OPEN         = 1<<0,                    
} StoreFlags;

typedef enum {
    ITER_OPEN_TXN       = 1<<0,         
                                         //<
                                         //< The iterator has begun a new
                                         //< transaction on initialization
                                         //< which needs to be closed.  If
                                         //< false, the iterator is using an
                                         //< existing transaction which will
                                         //< not be closed with
                                         //< #mdbiter_free().
} IterFlags;
 
typedef enum {
    OP_ADD,
    OP_REMOVE,
} StoreOp;
 
typedef struct mdbstore_t {
    MDB_env *           env;            
    MDB_dbi             dbi[N_DB];      
    StoreFlags          flags;          
} MDBStore;

typedef void (*iter_op_fn_t)(MDBIterator *it);
 

typedef struct mdbstore_iter_t {
    MDBStore *          store;      
    IterFlags           flags;      
    MDB_txn *           txn;        
    MDB_cursor *        cur;        
    MDB_cursor *        ctx_cur;    
    MDB_val             key;        
    MDB_val             data;       
    VOLK_TripleKey      spok;       
    VOLK_Key *          ck;         
    iter_op_fn_t        iter_op_fn; 
    const uint8_t *     term_order; 
    VOLK_Key            luk[3];     
    VOLK_Key            luc;        
    size_t              i;          
    size_t              ct;         
    int                 rc;         
} MDBIterator;
 
 
/*
 * Static variables.
 */
 
#define DUPFIXED_MASK       MDB_DUPSORT | MDB_DUPFIXED

#define MAIN_TABLE \
/*          #ID pfx #DB label   #Flags  */ \
    ENTRY(  T_ST,   "t:st",     0               )   /* Key to ser. term */  \
    ENTRY(  SPO_C,  "spo:c",    DUPFIXED_MASK   )   /* Triple to context */ \


#define LOOKUP_TABLE \
/*          #ID pfx  #DB label #Flags   */ \
    ENTRY(  S_PO,    "s:po",   DUPFIXED_MASK    )   /* 1-bound lookup */    \
    ENTRY(  P_SO,    "p:so",   DUPFIXED_MASK    )   /* 1-bound lookup */    \
    ENTRY(  O_SP,    "o:sp",   DUPFIXED_MASK    )   /* 1-bound lookup */    \
    ENTRY(  PO_S,    "po:s",   DUPFIXED_MASK    )   /* 2-bound lookup */    \
    ENTRY(  SO_P,    "so:p",   DUPFIXED_MASK    )   /* 2-bound lookup */    \
    ENTRY(  SP_O,    "sp:o",   DUPFIXED_MASK    )   /* 2-bound lookup */    \
    ENTRY(  C_SPO,   "c:spo",  DUPFIXED_MASK    )   /* Context lookup */    \


#define ENTRY(a, b, c) static const DbLabel DB_##a = b;
MAIN_TABLE
LOOKUP_TABLE
#undef ENTRY
 
/*
 * Numeric index of each DB. Prefixed with IDX_
 *
 * These index numbers are referred to in all the arrays defeined below. They
 * are independent from the LMDB dbi values which are considered opaque here.
 */
typedef enum {
#define ENTRY(a, b, c) IDX_##a,
    MAIN_TABLE
    LOOKUP_TABLE
#undef ENTRY
} DBIdx;

static const char *db_labels[N_DB] = {
#define ENTRY(a, b, c) DB_##a,
    MAIN_TABLE
    LOOKUP_TABLE
#undef ENTRY
};
 
/*
 * DB flags. These are aligned with the dbi_labels index.
 */
static const unsigned int db_flags[N_DB] = {
#define ENTRY(a, b, c) c,
    MAIN_TABLE
    LOOKUP_TABLE
#undef ENTRY
};
 
/*
 * 1-bound and 2-bound lookup indices.
 *
 * N.B. Only the first 6 (1-bound and 2-bound term lookup) are used.
 * The others are added just because they belong logically to the lookup table.
 */
static DBIdx lookup_indices[9] = {
#define ENTRY(a, b, c) IDX_##a,
    LOOKUP_TABLE
#undef ENTRY
};
 
static const uint8_t lookup_ordering_1bound[3][3] = {
    {0, 1, 2}, // s:po
    {1, 0, 2}, // p:so
    {2, 0, 1}, // o:sp
};
 
static const uint8_t lookup_ordering_2bound[3][3] = {
    {1, 2, 0}, // po:s
    {0, 2, 1}, // so:p
    {0, 1, 2}, // sp:o
};
 
 
/*
 * Static prototypes.
 */
static int index_triple(
        MDBStore *store, StoreOp op, VOLK_TripleKey spok, VOLK_Key ck,
        MDB_txn *txn);
static VOLK_rc mdbstore_add_term (void *h, const VOLK_Buffer *sterm, void *th);
 
inline static VOLK_rc lookup_0bound (MDBIterator *it, size_t *ct);
inline static VOLK_rc lookup_1bound (
        uint8_t idx0, MDBIterator *it, size_t *ct);
inline static VOLK_rc lookup_2bound (
        uint8_t idx0, uint8_t idx1, MDBIterator *it, size_t *ct);
inline static VOLK_rc lookup_3bound(MDBIterator *it, size_t *ct);
 
 
static const char *
mdbstore_path_from_id (const char *id)
{
    // Set environment path.
    if (!id) id = getenv ("VOLK_MDB_STORE_URN");
    if (!id) {
        id = VOLK_MDB_STORE_URN;
        log_info (
            "`VOLK_MDB_STORE_URN' environment variable is not "
            "set. The default URN %s has been set as the store ID.", id
        );
    } else if (strncmp ("file://", id, 7) != 0) {
        log_error ("MDB store ID must be in the `file://<abs_path>` format.");
 
        return NULL;
    }
 
    return id + 7;
}
 
 
/*
 * Inliners.
 */
 
static inline VOLK_rc
txn_begin (MDB_env *env, MDB_txn *p, unsigned int f, MDB_txn **tp) {
    RCCK (mdb_txn_begin (env, p, f, tp));
    const char *path;
    RCCK (mdb_env_get_path (env, &path));
    STRACE (
            "BEGIN %s transaction %p child of %p in env %s",
            f == 0 ? "RW" : "RO", *tp, p, path);
 
    return VOLK_OK;
}
 
 
static inline VOLK_rc
txn_commit (MDB_txn *t) {
    log_debug ("COMMIT transaction %p", t);
    return mdb_txn_commit (t);
}
 


static VOLK_rc
mdbstore_setup (const char *id, bool clear)
{
    if (!VOLK_env_is_init) return VOLK_ENV_ERR;
 
    const char *path = mdbstore_path_from_id (id);
    if (!path) return VOLK_VALUE_ERR;
 
    // If the directory exists (unless clear == true), do nothing.
    if (clear) rm_r (path);
    VOLK_rc rc = mkdir_p (path, ENV_DIR_MODE);
    log_debug ("Create dir rc: %s", VOLK_strerror (rc));
    PRCCK (rc);
 
    // Open a temporary environment and txn to create the DBs.
    MDB_env *env;
    RCCK (mdb_env_create (&env));
 
    RCCK (mdb_env_set_maxdbs (env, N_DB));
    RCCK (mdb_env_open (env, path, 0, ENV_FILE_MODE));
    log_debug ("Environment opened at %s.", path);
 
    MDB_txn *txn;
    RCCK (txn_begin (env, NULL, 0, &txn));
    MDB_dbi dbi;
    for (int i = 0; i < N_DB; i++) {
        log_trace ("Creating DB %s", db_labels[i]);
        RCCK (
            mdb_dbi_open (txn, db_labels[i], db_flags[i] | MDB_CREATE, &dbi)
        );
    }
 
    // Bootstrap the permanent store with initial data.
    MDB_stat stat;
    CHECK (mdb_dbi_open (
                txn, db_labels[IDX_T_ST], db_flags[IDX_T_ST], &dbi), fail);
    CHECK (mdb_stat (txn, dbi, &stat), fail);
 
    if (stat.ms_entries == 0) {
        log_debug ("Loading initial data into %s", path);
        // Index default context.
        MDB_cursor *cur;
        CHECK (mdb_cursor_open (txn, dbi, &cur), fail);
        VOLK_Key k = VOLK_buffer_hash (VOLK_default_ctx_buf);
        MDB_val key, data;
        key.mv_data = &k;
        key.mv_size = sizeof (k);
 
        data.mv_data = VOLK_default_ctx_buf->addr;
        data.mv_size = VOLK_default_ctx_buf->size;
 
        VOLK_rc db_rc = mdb_cursor_put (cur, &key, &data, 0);
        CHECK (db_rc, fail);
    }
 
    CHECK (txn_commit (txn), fail);
    mdb_env_close (env);
 
    return clear ? VOLK_OK : rc;
 
fail:
    if (rc >= 0) rc = VOLK_DB_ERR;
    mdb_txn_abort (txn);
    return rc;
}
 

static void *
mdbstore_new (const char *id, size_t _unused)
{
    if (!VOLK_env_is_init) {
        log_error (VOLK_strerror (VOLK_ENV_ERR));
        return NULL;
    }
 
    (void) _unused;
    const char *path = mdbstore_path_from_id (id);
    if (!path) return NULL;
 
    MDBStore *store;
    CALLOC_GUARD (store, NULL);
 
    RCNL (mdb_env_create (&store->env));
    MDB_txn *txn = NULL;
 
    // Set map size.
    size_t mapsize;
    char *env_mapsize = getenv ("VOLK_MDB_MAPSIZE");
    if (env_mapsize == NULL) mapsize = DEFAULT_MAPSIZE;
    else sscanf (env_mapsize, "%zu", &mapsize);
    log_debug (
            "Setting environment map size at %s to %zu Mb.",
            path, mapsize / 1024 / 1024);
    CHECK (mdb_env_set_mapsize (store->env, mapsize), fail);
    CHECK (mdb_env_set_maxdbs (store->env, N_DB), fail);
    CHECK (mdb_env_open (store->env, path, 0, ENV_FILE_MODE), fail);
 
    // Assign DB handles to store->dbi.
    CHECK (txn_begin (store->env, NULL, 0, &txn), fail);
    for (int i = 0; i < N_DB; i++)
        CHECK (mdb_dbi_open (
                txn, db_labels[i], db_flags[i], store->dbi + i), fail);
 
    store->flags |= LSSTORE_OPEN;
    CHECK (txn_commit(txn), fail);
    txn = NULL;
 
    log_info ("Created MDB environment at %s", path);
 
    return store;
 
fail:
    if (txn) mdb_txn_abort (txn);
    mdb_env_close (store->env);
 
    return NULL;
}
 
 
static void
mdbstore_free (void *h)
{
    MDBStore *store = h;
    if (store->flags & LSSTORE_OPEN) {
        const char *path;
        mdb_env_get_path (store->env, &path);
        log_info ("Closing MDB environment at %s.", path);
        mdb_env_close (store->env);
    }
 
    free (store);
}
 
 
static VOLK_rc
mdbstore_stat (const MDBStore *store, MDB_stat *stat)
{
    if (!(store->flags & LSSTORE_OPEN)) return 0;
 
    MDB_txn *txn;
    RCCK (txn_begin (store->env, NULL, MDB_RDONLY, &txn));
 
    if (mdb_stat (txn, store->dbi[IDX_SPO_C], stat) != MDB_SUCCESS)
        return VOLK_DB_ERR;
    mdb_txn_abort (txn);
 
    return VOLK_OK;
}
 
 
static size_t
mdbstore_size (const void *h)
{
    const MDBStore *store = h;
    // Size is calculated outside of any pending write txn.
 
    MDB_stat stat;
    if (mdbstore_stat (store, &stat) != VOLK_OK) return 0;
 
    return stat.ms_entries;
}
 
 
char *
mdbstore_id (const void *h)
{
    const MDBStore *store = h;
    const char *path;
 
    RCNL (mdb_env_get_path (store->env, &path));
 
    char *id = malloc (strlen (path) + 8);
    sprintf (id, "file://%s", path);
 
    return id;
}
 
 
static VOLK_rc
mdbstore_txn_begin (void *h, VOLK_StoreFlags flags, void **th)
{
    MDBStore *store = h;
    flags = flags & VOLK_STORE_TXN_RO ? MDB_RDONLY : 0;
 
    RCCK (txn_begin (store->env, NULL, flags, (MDB_txn **) th));
 
    return VOLK_OK;
}
 
 
static VOLK_rc
mdbstore_txn_commit (void *th)
{
    RCCK (txn_commit (th));
 
    return VOLK_OK;
}
 
 
static void
mdbstore_txn_abort (void *th)
{ mdb_txn_abort (th); }
 
 
static void *
mdbiter_txn (void *h)
{ return ((MDBIterator *) h)->txn; }
 

static void *
mdbstore_add_init (void *h, const VOLK_Buffer *sc, void *th)
{
    MDBStore *store = h;
    /* An iterator is used here. Some members are a bit misused but it does
     * its job without having to define a very similar struct.
     */
    MDBIterator *it = calloc (1, sizeof (*it));
    NLNL (it);
 
    it->store = store;
    if (th) it->txn = th;
    else {
        CHECK (txn_begin (store->env, th, 0, &it->txn), fail);
        it->flags |= ITER_OPEN_TXN;
    }
 
    if (sc) {
        // Store context if it's not the default one.
        it->luc = VOLK_buffer_hash (sc);
 
        // Insert t:st for context.
        //log_debug ("Adding context: %s", sc);
        it->key.mv_data = &it->luc;
        it->key.mv_size = KLEN;
        it->data.mv_data = sc->addr;
        it->data.mv_size = sc->size;
 
        int db_rc = mdb_put (
                it->txn, it->store->dbi[IDX_T_ST],
                &it->key, &it->data, MDB_NOOVERWRITE);
        if (db_rc != MDB_SUCCESS && db_rc != MDB_KEYEXIST) {
            log_error (VOLK_strerror (db_rc));
            mdb_txn_abort (it->txn);
            return NULL;
        }
    } else {
        log_debug ("No context passed to iterator, using default.");
        it->luc = VOLK_buffer_hash (VOLK_default_ctx_buf);
    }
 
    return it;
 
fail:
    free (it);
 
    return NULL;
}
 
 
/*
 * NOTE: at the moment #mdbstore_remove() or another
 * #mdbstore_init() cannot be called between #mdbstore_add_init and
 * #mdbstore_add_abort or #mdbstore_add_done. FIXME
 *
 */
static VOLK_rc
mdbstore_add_iter (void *h, const VOLK_BufferTriple *sspo)
{
    if (UNLIKELY (!h)) return VOLK_VALUE_ERR;
 
    MDBIterator *it = h;
    int db_rc = VOLK_NOACTION;
    VOLK_TripleKey spok = NULL_TRP;
 
    // Add triple terms.
    for (int i = 0; i < 3; i++) {
        VOLK_Buffer *st = VOLK_btriple_pos (sspo, i);
 
        spok[i] = VOLK_buffer_hash (st);
 
        it->key.mv_data = spok + i;
        it->key.mv_size = KLEN;
        it->data.mv_data = st->addr;
        it->data.mv_size = st->size;
 
        db_rc = mdb_put(
                it->txn, it->store->dbi[IDX_T_ST],
                &it->key, &it->data, MDB_NOOVERWRITE);
        if (db_rc != MDB_SUCCESS && db_rc != MDB_KEYEXIST) {
            LOG_RC (db_rc);
            return VOLK_DB_ERR;
        }
    }
 
    log_trace ("Inserting spok: {%x, %x, %x}", spok[0], spok[1], spok[2]);
    log_trace ("Into context: %x", it->luc);
 
    // Insert spo:c.
    it->key.mv_data = spok;
    it->key.mv_size = TRP_KLEN;
 
    // In triple mode, data is empty (= NULL_KEY).
    it->data.mv_data = &it->luc;
    it->data.mv_size = it->luc == NULL_KEY ? 0 : KLEN;
 
    db_rc = mdb_put(
            it->txn, it->store->dbi[IDX_SPO_C],
            &it->key, &it->data, MDB_NODUPDATA);
 
    if (db_rc == MDB_KEYEXIST) return VOLK_NOACTION;
    if (db_rc != MDB_SUCCESS) {
        log_error (
                "MDB error while inserting triple: %s", VOLK_strerror(db_rc));
        return VOLK_DB_ERR;
    }
 
    // Index.
    VOLK_rc rc = index_triple (it->store, OP_ADD, spok, it->luc, it->txn);
    if (rc == VOLK_OK) it->i++;
 
    return rc;
}
 
 
static VOLK_rc
mdbstore_add_done (void *h)
{
    MDBIterator *it = h;
 
    VOLK_rc rc = VOLK_OK;
    log_debug ("Committing add transaction.");
 
    if (it->flags & ITER_OPEN_TXN) {
        if (txn_commit (it->txn) != MDB_SUCCESS) {
            log_error ("Error committing transaction. Aborting instead.");
            mdb_txn_abort (it->txn);
            rc = VOLK_TXN_ERR;
        }
    }
 
    free (it);
 
    RCCK (rc);
    return rc;
}
 
 
static void
mdbstore_add_abort (void *h)
{
    MDBIterator *it = h;
    if (it->flags & ITER_OPEN_TXN) mdb_txn_abort (it->txn);
 
    free (it);
}
 
 
static VOLK_rc
key_to_sterm (
        MDBStore *store, MDB_txn *txn, const VOLK_Key key, VOLK_Buffer *sterm)
{
    VOLK_rc rc = VOLK_NORESULT;
    int db_rc;
 
    MDB_val key_v, data_v;
    key_v.mv_data = (void*)&key;
    key_v.mv_size = KLEN;
 
    db_rc = mdb_get (txn, store->dbi[IDX_T_ST], &key_v, &data_v);
 
    sterm->flags |= VOLK_BUF_BORROWED;
    if (db_rc == MDB_SUCCESS) {
        sterm->addr = data_v.mv_data;
        sterm->size = data_v.mv_size;
        rc = VOLK_OK;
    } else if (db_rc == MDB_NOTFOUND) {
        sterm->addr = NULL;
        sterm->size = 0;
    } else {
        LOG_RC (db_rc);
        rc = VOLK_DB_ERR;
    }
 
    return rc;
}
 
 
static void *
mdbstore_lookup (
        void *h, const VOLK_Buffer *ss, const VOLK_Buffer *sp,
        const VOLK_Buffer *so, const VOLK_Buffer *sc, void *th, size_t *ct)
{
    VOLK_TripleKey spok = {
        VOLK_buffer_hash (ss),
        VOLK_buffer_hash (sp),
        VOLK_buffer_hash (so),
    };
 
    MDBIterator *it;
    CALLOC_GUARD (it, NULL);
 
    it->store = h;
    it->luc = VOLK_buffer_hash (sc);
    log_debug ("Lookup context: %x", it->luc);
 
    if (ct) *ct = 0;
 
    uint8_t idx0, idx1;
 
    if (th) it->txn = th;
    else {
        RCNL (txn_begin (it->store->env, NULL, MDB_RDONLY, &it->txn));
        log_trace ("Opening new lookup transaction @%p", it->txn);
        it->flags |= ITER_OPEN_TXN;
    }
 
    // Context index loop.
    RCNL (mdb_cursor_open (
            it->txn, it->store->dbi[IDX_SPO_C], &it->ctx_cur));
 
    /*
     * Lookup decision tree.
     */
    // s p o (all terms bound)
    if (spok[0] != NULL_KEY && spok[1] != NULL_KEY && spok[2] != NULL_KEY) {
        it->luk[0] = spok[0];
        it->luk[1] = spok[1];
        it->luk[2] = spok[2];
        PRCNL (lookup_3bound (it, ct));
 
    } else if (spok[0] != NULL_KEY) {
        it->luk[0] = spok[0];
        idx0 = 0;
 
        // s p ?
        if (spok[1] != NULL_KEY) {
            it->luk[1] = spok[1];
            idx1 = 1;
            PRCNL (lookup_2bound (idx0, idx1, it, ct));
 
        // s ? o
        } else if (spok[2] != NULL_KEY) {
            it->luk[1] = spok[2];
            idx1 = 2;
            PRCNL (lookup_2bound (idx0, idx1, it, ct));
 
        // s ? ?
        } else PRCNL (lookup_1bound (idx0, it, ct));
 
    } else if (spok[1] != NULL_KEY) {
        it->luk[0] = spok[1];
        idx0 = 1;
 
        // ? p o
        if (spok[2] != NULL_KEY) {
            it->luk[1] = spok[2];
            idx1 = 2;
            PRCNL (lookup_2bound (idx0, idx1, it, ct));
 
        // ? p ?
        } else PRCNL (lookup_1bound (idx0, it, ct));
 
    // ? ? o
    } else if (spok[2] != NULL_KEY) {
        it->luk[0] = spok[2];
        idx0 = 2;
        PRCNL (lookup_1bound (idx0, it, ct));
 
    // ? ? ? (all terms unbound)
    } else PRCNL (lookup_0bound (it, ct));
 
    return it;
}
 

static VOLK_rc
mdbiter_next_key (MDBIterator *it)
{
    NLRCCK (it, VOLK_VALUE_ERR);
    // Only advance if the previous it->rc wasn't already at the end.
    if (it->rc == MDB_NOTFOUND) return VOLK_END;
    RCCK (it->rc);
 
    /* Retrieve current value and advance cursor to the next result.
     * it->rc is set to the result of the next iteration.
     */
    it->iter_op_fn (it);
    MDB_val key, data;
    int db_rc;
 
    key.mv_size = TRP_KLEN;
    data.mv_data = &it->luc;
    data.mv_size = KLEN;
 
    VOLK_rc rc;
    if (it->luc) {
        rc = VOLK_NORESULT;  // Flow control value, will never be returned.
        do {
            //log_debug ("begin ctx loop.");
            /* If ctx is specified, look if the matching triple is associated
             * with it. If not, move on to the next triple.
             * The loop normally exits when a triple with matching ctx is found
             * (VOLK_OK), if there are no more triples (VOLK_END), or if there
             * is an error (VOLK_DB_ERR).
             */
            log_trace (
                    "Found spok: {%x, %x, %x}",
                    it->spok[0], it->spok[1], it->spok[2]);
 
            key.mv_data = it->spok;
            db_rc = mdb_cursor_get (it->ctx_cur, &key, &data, MDB_GET_BOTH);
 
            if (db_rc == MDB_NOTFOUND) {
                log_trace ("Triple not found in context: %x", it->luc);
                // if the iterator is at the end, stop here.
                if (it->rc == MDB_NOTFOUND) rc = VOLK_END;
                // Otherwise, look up the next key.
                else it->iter_op_fn (it);
 
            } else {
                RCCK (db_rc);
                rc = VOLK_OK;
                log_trace ("Triple found in context: %x", it->luc);
            }
        } while (rc == VOLK_NORESULT);
 
    } else {
        log_trace (
                "Found spok in any context: {%x, %x, %x}",
                it->spok[0], it->spok[1], it->spok[2]);
        rc = VOLK_OK;
    }
 
    // Get all contexts for a triple.
    key.mv_data = it->spok;
    db_rc = mdb_cursor_get (it->ctx_cur, &key, &data, MDB_SET_KEY);
    if (db_rc != MDB_SUCCESS) {
        log_error ("No context found for triple!");
        return VOLK_DB_ERR;
    }
 
    size_t ct;
    db_rc = mdb_cursor_count (it->ctx_cur, &ct);
    if (db_rc != MDB_SUCCESS) return VOLK_DB_ERR;
    // 1 spare for sentinel. Always allocated even on zero matches.
    VOLK_Key *tmp_ck = realloc (it->ck, sizeof (*it->ck) * (ct + 1));
    NLRCCK (tmp_ck, VOLK_MEM_ERR);
    it->ck = tmp_ck;
 
    size_t i = 0;
    do {
        //log_trace ("Copying to slot #%lu @%p", i, it->ck + i);
        memcpy (it->ck + i++, data.mv_data, sizeof (*it->ck));
    } while (
            mdb_cursor_get (it->ctx_cur, &key, &data, MDB_NEXT_DUP)
            == MDB_SUCCESS);
    //log_trace ("setting sentinel @%p", it->ck + i);
    it->ck[i] = NULL_KEY;
 
    return rc;
}
 
 
static VOLK_rc
mdbiter_next (
        void *h, VOLK_BufferTriple *sspo, VOLK_Buffer **ctx_p)
{
    MDBIterator *it = h;
    VOLK_rc rc = mdbiter_next_key (it);
 
    if (rc == VOLK_OK) {
        if (sspo) {
            RCCK (key_to_sterm (it->store, it->txn, it->spok[0], sspo->s));
            RCCK (key_to_sterm (it->store, it->txn, it->spok[1], sspo->p));
            RCCK (key_to_sterm (it->store, it->txn, it->spok[2], sspo->o));
        }
 
        // Contexts for current triple.
        if (ctx_p) {
            // Preallocate.
            size_t i = 0;
            while (it->ck[i++]); // Include sentinel in count.
            VOLK_Buffer *ctx;
            log_trace ("Allocating %lu context buffers + sentinel.", i - 1);
            ctx = malloc(i * sizeof (*ctx));
            if (!ctx) return VOLK_MEM_ERR;
 
            for (i = 0; it->ck[i]; i++)
                RCCK (key_to_sterm (it->store, it->txn, it->ck[i], ctx + i));
            memset (ctx + i, 0, sizeof (*ctx)); // Sentinel
            NLRCCK (ctx + i, VOLK_MEM_ERR);
 
            // TODO error handling.
            *ctx_p = ctx;
        }
    }
 
    return rc;
}
 
 
static void
mdbiter_free (void *h)
{
    if (!h) return;
    MDBIterator *it = h;
 
    if (it->cur) mdb_cursor_close (it->cur);
    if (it->ctx_cur) mdb_cursor_close (it->ctx_cur);
    if (it->flags & ITER_OPEN_TXN) mdb_txn_abort (it->txn);
    free (it->ck);
 
    free (it);
}
 
 
static VOLK_rc
mdbstore_update_ctx (
        void *h, const VOLK_Buffer *old_c, const VOLK_Buffer *new_c, void *th)
{
    VOLK_rc rc = VOLK_NOACTION;
    MDBStore *store = h;
    unsigned char *trp_data = NULL;
 
    VOLK_Key
        old_ck = VOLK_buffer_hash (old_c),
        new_ck = VOLK_buffer_hash (new_c);
    // lu_key, lu_data look up all triples with old context in c:spo, and
    // replace old c with new c.
    MDB_txn
        *p_txn = th,
        *txn;
    CHECK (rc = txn_begin (store->env, p_txn, 0, &txn), finally);
 
    MDB_cursor *i_cur, *d_cur;
    CHECK (
            rc = mdb_cursor_open (txn, store->dbi[IDX_C_SPO], &i_cur),
            close_txn);
 
    MDB_val key, data;
 
    // Return error if the graph URI already exists.
    key.mv_data = &new_ck;
    key.mv_size = KLEN;
    rc = mdb_cursor_get (i_cur, &key, &data, MDB_SET);
    if (rc == MDB_SUCCESS) {
        log_error (
                "Context key %lu already exists. Not replacing old graph.",
                new_ck);
        rc = VOLK_CONFLICT;
        goto close_i;
    } else if (rc != MDB_NOTFOUND) CHECK (rc, close_i);
 
    // Add new context term.
    CHECK (rc = mdbstore_add_term (store, new_c, txn), close_i);
 
    key.mv_data = &old_ck;
    // Count triples in cursor.
    rc = mdb_cursor_get (i_cur, &key, &data, MDB_SET);
    if (rc == MDB_NOTFOUND) {
        log_info ("No triples found associated with old context.");
        rc = VOLK_NOACTION;
        goto close_i;
    } else CHECK (rc, close_i);
 
    // From here on, it can only be VOLK_OK or error.
    rc = VOLK_OK;
    size_t trp_ct;
    CHECK (rc = mdb_cursor_count (i_cur, &trp_ct), close_i);
    trp_data = malloc (trp_ct * TRP_KLEN);
    if (UNLIKELY (!trp_data)) {
        rc = VOLK_MEM_ERR;
        goto close_i;
    }
 
    // Copy triple data as one block to temp buffer so that entries can be
    // deleted while cursors are active.
    rc = mdb_cursor_get (i_cur, &key, &data, MDB_GET_MULTIPLE);
    if (rc != MDB_SUCCESS) {
        rc = rc == MDB_NOTFOUND ? VOLK_NOACTION : VOLK_DB_ERR;
        goto close_i;
    }
    size_t loc_cur = 0;
    do {
        memcpy (trp_data + loc_cur, data.mv_data, data.mv_size);
        loc_cur += data.mv_size;
    } while (mdb_cursor_get (
                i_cur, &key, &data, MDB_NEXT_MULTIPLE) == MDB_SUCCESS);
 
    // Zap c:spo entries in one go.
    key.mv_data = &old_ck;
    key.mv_size = KLEN;
    data.mv_size = TRP_KLEN;
    CHECK (rc = mdb_cursor_get (i_cur, &key, NULL, MDB_SET), close_i);
    CHECK (rc = mdb_cursor_del (i_cur, MDB_NODUPDATA), close_i);
 
    // Re-ad c:spo data individually.
    key.mv_data = &new_ck;
    for (size_t i = 0; i < trp_ct; i++) {
        data.mv_data = trp_data + i * data.mv_size;
        CHECK (
                rc = mdb_cursor_put (i_cur, &key, &data, MDB_APPENDDUP),
                close_i);
    }
    // Re-add c:spo data in bulk from buffer with new context.
    // FIXME this is not working. Replaced by the for loop above.
    /*
    MDB_val data_block[] = {
        { .mv_data = &new_ck, .mv_size = TRP_KLEN },
        { .mv_data = NULL, .mv_size = trp_ct },
    };
    db_rc = mdb_cursor_put (i_cur, &key, data_block, MDB_MULTIPLE);
    */
 
    // Main table.
    // Replace spo:c values one by one.
    CHECK (rc = mdb_cursor_open (txn, store->dbi[IDX_SPO_C], &d_cur), close_i);
    key.mv_size = TRP_KLEN;
    data.mv_size = KLEN;
    for (size_t i = 0; i < trp_ct; i++) {
        key.mv_data = trp_data + i * key.mv_size;
        data.mv_data = &old_ck;
        CHECK (
                rc = mdb_cursor_get (d_cur, &key, &data, MDB_GET_BOTH),
                close_d);
        CHECK (rc = mdb_cursor_del (d_cur, 0), close_d);
        data.mv_data = &new_ck;
        CHECK (
                rc = mdb_cursor_put (d_cur, &key, &data, MDB_NOOVERWRITE),
                close_d);
    }
 
close_d:
    mdb_cursor_close (d_cur);
close_i:
    mdb_cursor_close (i_cur);
close_txn:
    if (rc == VOLK_OK) RCCK (txn_commit (txn));
    else mdb_txn_abort (txn);
 
    if (trp_data) free (trp_data);
finally:
 
    return rc;
}
 
 
static VOLK_rc
mdbstore_remove (
        void *h, const VOLK_Buffer *ss, const VOLK_Buffer *sp,
        const VOLK_Buffer *so, const VOLK_Buffer *sc, void *th, size_t *ct_p)
{
    MDBStore *store = h;
    VOLK_rc rc = VOLK_NOACTION;
 
    MDB_txn *txn;
    RCCK (txn_begin (store->env, th, 0, &txn));
    MDB_cursor *cur;
    mdb_cursor_open (txn, store->dbi[IDX_SPO_C], &cur);
 
    if (sc == NULL) sc = VOLK_default_ctx_buf;
    VOLK_Key ck = VOLK_buffer_hash (sc);
    MDB_val spok_v, ck_v;
    spok_v.mv_size = TRP_KLEN;
    ck_v.mv_size = KLEN;
    ck_v.mv_data = &ck;
 
    // Gather all the matching triples in a first pass.
    size_t *ct = ct_p ? ct_p : malloc (sizeof (*ct));
    NLRCCK (ct, VOLK_MEM_ERR);
    MDBIterator *it = mdbstore_lookup (store, ss, sp, so, sc, txn, ct);
    NLRCCK (it, VOLK_DB_ERR);
    log_debug ("Found %lu triples to remove.", *ct);
    VOLK_Key *keys = malloc (*ct * sizeof (VOLK_Key) * 3);
    NLRCCK (it, VOLK_MEM_ERR);
    size_t i = 0;
    while (mdbiter_next_key (it) == VOLK_OK) {
        log_trace ("Adding triple #%zu to remove list.", i);
        memcpy (keys + (3 * i++), &it->spok, TRP_KLEN);
    }
    mdbiter_free (it);
 
    // Iterate over the gathered keys and delete them.
    for (i = 0; i < *ct; i++) {
        spok_v.mv_data = keys + i * 3;
        ck_v.mv_data = &ck;
        log_trace (
                "Removing triple #%zu: %x {%x %x %x}",
                i,
                ((VOLK_Key *)ck_v.mv_data)[0],
                ((VOLK_Key *)spok_v.mv_data)[0],
                ((VOLK_Key *)spok_v.mv_data)[1],
                ((VOLK_Key *)spok_v.mv_data)[2]);
 
        rc = mdb_cursor_get (cur, &spok_v, &ck_v, MDB_GET_BOTH);
        if (rc == MDB_NOTFOUND) {
            log_warn ("No key found in spo:c DB.");
            continue;  // TODO This could be a data problem.
        } else CHECK (rc, fail);
 
        // Delete spo:c entry.
        CHECK (rc = mdb_cursor_del (cur, 0), fail);
        CHECK (rc = index_triple (
            store, OP_REMOVE, keys + i * 3, ck, txn
        ), fail);
    }
    free(keys);
    CHECK (txn_commit (txn), fail);
 
    return rc;
 
fail:
    mdb_txn_abort (txn);
    RCCK (rc);
 
    return VOLK_DB_ERR;
}
 

static VOLK_rc
mdbstore_add_term (void *h, const VOLK_Buffer *sterm, void *th)
{
    //log_trace ("Adding term to MDB store: %s", sterm->addr);
    MDBStore *store = h;
    int db_rc;
    MDB_val key, data;
 
    MDB_txn *txn;
    // If an active transaction was passed, use it, otherwise open and
    // close a new one.
    if (th) txn = th;
    else RCCK (txn_begin (store->env, th, 0, &txn));
 
    MDB_cursor *cur;
    CHECK (mdb_cursor_open (txn, store->dbi[IDX_T_ST], &cur), fail);
 
    VOLK_Key k = VOLK_buffer_hash (sterm);
    key.mv_data = &k;
    key.mv_size = sizeof (k);
 
    data.mv_data = sterm->addr;
    data.mv_size = sterm->size;
 
    db_rc = mdb_cursor_put (cur, &key, &data, MDB_NOOVERWRITE);
    if (db_rc != MDB_KEYEXIST) CHECK (db_rc, fail);
 
    if (txn != th) CHECK (db_rc = txn_commit (txn), fail);
 
    return VOLK_OK;
 
fail:
    if (txn != th) mdb_txn_abort (txn);
    log_trace ("Aborted txn for adding term.");
    return VOLK_DB_ERR;
}
 
 
VOLK_Buffer **
mdbstore_ctx_list (void *h, void *th)
{
    MDBStore *store = h;
    VOLK_rc db_rc;
    MDB_txn *txn;
    VOLK_Buffer **tdata = NULL;
    if (th) txn = th;
    else CHECK (txn_begin (store->env, NULL, MDB_RDONLY, &txn), fail_txn);
 
 
    MDB_cursor *cur;
    CHECK (mdb_cursor_open (txn, store->dbi[IDX_C_SPO], &cur), fail);
    MDB_val key, data;
 
    db_rc = mdb_cursor_get (cur, &key, &data, MDB_FIRST);
    size_t i = 0;
    while (db_rc == MDB_SUCCESS) {
        i++;
        db_rc = mdb_cursor_get (cur, &key, &data, MDB_NEXT_NODUP);
    }
    tdata = malloc ((i + 1) * sizeof (*tdata));
    NLCHECK (tdata, fail);
 
    db_rc = mdb_cursor_get (cur, &key, &data, MDB_FIRST);
    i = 0;
    while (db_rc == MDB_SUCCESS) {
        tdata[i] = BUF_DUMMY;
        VOLK_Key tkey = *(VOLK_Key*)key.mv_data;
        CHECK (key_to_sterm (store, txn, tkey, tdata[i++]), fail);
        db_rc = mdb_cursor_get (cur, &key, &data, MDB_NEXT_NODUP);
    }
    tdata[i] = NULL;  // Sentinel
    mdb_cursor_close (cur);
    if (txn != th) mdb_txn_abort (txn);
 
    return tdata;
 
fail:
    if (txn != th) mdb_txn_abort (txn);
    if (tdata) free (tdata);
fail_txn:
    return NULL;
}
 
 
const VOLK_StoreInt mdbstore_int = {
    .name           = "MDB Store",
    .features       = VOLK_STORE_PERM | VOLK_STORE_CTX | VOLK_STORE_IDX
                      | VOLK_STORE_TXN | VOLK_STORE_COW,
 
    .setup_fn       = mdbstore_setup,
    .new_fn         = mdbstore_new,
    .free_fn        = mdbstore_free,
 
    .size_fn        = mdbstore_size,
    .id_fn          = mdbstore_id,
 
    .txn_begin_fn   = mdbstore_txn_begin,
    .txn_commit_fn  = mdbstore_txn_commit,
    .txn_abort_fn   = mdbstore_txn_abort,
    .iter_txn_fn    = mdbiter_txn,
 
    .add_init_fn    = mdbstore_add_init,
    .add_iter_fn    = mdbstore_add_iter,
    .add_abort_fn   = mdbstore_add_abort,
    .add_done_fn    = mdbstore_add_done,
    .add_term_fn    = mdbstore_add_term,
 
    .update_ctx_fn  = mdbstore_update_ctx,
 
    .lookup_fn      = mdbstore_lookup,
    .lu_next_fn     = mdbiter_next,
    .lu_free_fn     = mdbiter_free,
 
    .remove_fn      = mdbstore_remove,
 
    .ctx_list_fn    = mdbstore_ctx_list,
};
 
 
/* * * Static functions. * * */

static VOLK_rc
index_triple(
        MDBStore *store, StoreOp op, VOLK_TripleKey spok, VOLK_Key ck,
        MDB_txn *txn)
{
    int db_rc;
    VOLK_rc rc = VOLK_NOACTION;
    MDB_val v1, v2;
 
    log_trace ("Indexing triple: {%x %x %x}", spok[0], spok[1], spok[2]);
 
    // Index c:spo.
    if (op == OP_REMOVE) {
        log_trace ("Indexing op: REMOVE");
        if (ck == NULL_KEY) goto skip_remove;
 
        MDB_cursor *cur;
        v1.mv_data = &ck;
        v1.mv_size = KLEN;
        v2.mv_data = spok;
        v2.mv_size = TRP_KLEN;
 
        RCCK (mdb_cursor_open (txn, store->dbi[IDX_C_SPO], &cur));
        db_rc = mdb_cursor_get (cur, &v1, &v2, MDB_GET_BOTH);
        if (db_rc != MDB_NOTFOUND) {
            RCCK (db_rc);
            RCCK (mdb_cursor_del (cur, 0));
            v1.mv_data = &ck;
            v2.mv_data = spok;
            rc = VOLK_OK;
        }
        mdb_cursor_close (cur);
skip_remove:
 
    } else if (op == OP_ADD) {
        log_trace ("Indexing op: ADD");
        if (ck == NULL_KEY) goto skip_add;
 
        v1.mv_data = &ck;
        v1.mv_size = KLEN;
        v2.mv_data = spok;
        v2.mv_size = TRP_KLEN;
 
        db_rc = mdb_put(
                txn, store->dbi[IDX_C_SPO],
                &v1, &v2, MDB_NODUPDATA);
        if (db_rc != MDB_SUCCESS) return VOLK_DB_ERR;
        if (db_rc != MDB_KEYEXIST) rc = VOLK_OK;
skip_add:
 
    } else return VOLK_VALUE_ERR;
 
    VOLK_DoubleKey dbl_keys[3] = {
        {spok[1], spok[2]},  // po
        {spok[0], spok[2]},  // so
        {spok[0], spok[1]},  // sp
    };
 
    // Add or remove index terms.
    v1.mv_size = KLEN;
    v2.mv_size = DBL_KLEN;
 
    for (int i = 0; i < 3; i++) {
        MDB_dbi
            db1 = store->dbi[lookup_indices[i]],      // s:po, p:so, o:sp
            db2 = store->dbi[lookup_indices[i + 3]];  // po:s, so:p, sp:o
 
        v1.mv_data = spok + i;
        v2.mv_data = dbl_keys[i];
 
        if (op == OP_REMOVE) {
            // Remove from 1-bound index.
            MDB_cursor *cur1;
            mdb_cursor_open(txn, store->dbi[lookup_indices[i]], &cur1);
            RCCK (db_rc = mdb_cursor_get (cur1, &v1, &v2, MDB_GET_BOTH));
            mdb_cursor_del (cur1, 0);
            mdb_cursor_close (cur1);
 
            // Restore pointers invalidated after delete.
            v1.mv_data = spok + i;
            v2.mv_data = dbl_keys[i];
 
            // Remove from 2-bound index.
            MDB_cursor *cur2;
            mdb_cursor_open(txn, store->dbi[lookup_indices[i + 3]], &cur2);
            RCCK (db_rc = mdb_cursor_get (cur2, &v2, &v1, MDB_GET_BOTH));
            mdb_cursor_del (cur2, 0);
            mdb_cursor_close (cur2);
 
            rc = VOLK_OK;
 
        } else { // OP_ADD is guaranteed.
            // Add to 1-bound index.
            log_trace ("Indexing in %s: ", db_labels[lookup_indices[i]]);
            log_trace (
                    "%x: %x %x", *(size_t*)(v1.mv_data),
                    *(size_t*)(v2.mv_data), *(size_t*)(v2.mv_data) + 1);
 
            db_rc = mdb_put (txn, db1, &v1, &v2, MDB_NODUPDATA);
 
            if (db_rc == MDB_SUCCESS) rc = VOLK_OK;
            else if (db_rc != MDB_KEYEXIST) return VOLK_DB_ERR;
 
            // Add to 2-bound index.
            log_trace ("Indexing in %s: ", db_labels[lookup_indices[i + 3]]);
            log_trace (
                    "%x %x: %x", *(size_t*)(v2.mv_data),
                    *(size_t*)(v2.mv_data) + 1, *(size_t*)(v1.mv_data));
 
            db_rc = mdb_put (txn, db2, &v2, &v1, MDB_NODUPDATA);
 
            if (db_rc == MDB_SUCCESS) rc = VOLK_OK;
            else if (db_rc != MDB_KEYEXIST) return VOLK_DB_ERR;
        }
    }
 
    return rc;
}
 
 
/* * * Term-specific iterators. * * */

inline static void
it_next_0bound (MDBIterator *it)
{
    memcpy (it->spok, it->key.mv_data, sizeof (VOLK_TripleKey));
    it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_NEXT_NODUP);
}
 

inline static void
it_next_0bound_ctx (MDBIterator *it)
{
    memcpy (it->spok, it->data.mv_data, sizeof (VOLK_TripleKey));
    it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_NEXT_DUP);
}
 

inline static void
it_next_1bound (MDBIterator *it)
{
    VOLK_DoubleKey *lu_dset = it->data.mv_data;
 
    it->spok[it->term_order[0]] = it->luk[0];
    it->spok[it->term_order[1]] = lu_dset[it->i][0];
    it->spok[it->term_order[2]] = lu_dset[it->i][1];
 
    log_trace (
            "Composed triple: {%x %x %x}",
            it->spok[0], it->spok[1], it->spok[2]);
 
    // Ensure next block within the same page is not beyond the last.
    if (it->i < it->data.mv_size / DBL_KLEN - 1) {
        it->i ++;
        //log_debug ("Increasing page cursor to %lu.", it->i);
        //log_debug ("it->rc: %d", it->rc);
 
    } else {
        // If the last block in the page is being yielded,
        // move cursor to beginning of next page.
        it->i = 0;
        //log_debug ("Reset page cursor to %lu.", it->i);
        it->rc = mdb_cursor_get (
                it->cur, &it->key, &it->data, MDB_NEXT_MULTIPLE);
    }
}
 

inline static void
it_next_2bound (MDBIterator *it)
{
    VOLK_Key *lu_dset = it->data.mv_data;
 
    it->spok[it->term_order[0]] = it->luk[0];
    it->spok[it->term_order[1]] = it->luk[1];
    it->spok[it->term_order[2]] = lu_dset[it->i];
 
    // Ensure next block within the same page is not beyond the last.
    if (it->i < it->data.mv_size / KLEN - 1)
        it->i ++;
    else {
        // If the last block in the page is being yielded,
        // move cursor to beginning of next page.
        it->i = 0;
        it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_NEXT_MULTIPLE);
    }
}
 

inline static void
it_next_3bound (MDBIterator *it)
{ it->rc = MDB_NOTFOUND; }
 
 
/* * * Term-specific lookups. * * */
 
inline static VOLK_rc
lookup_0bound (MDBIterator *it, size_t *ct)
{
    log_debug ("Looking up 0 bound terms.");
 
    // Context search looks for all values in c:spo.
    if (it->luc != NULL_KEY) {
        // Look up by given context.
        RCCK (it->rc = mdb_cursor_open (
                it->txn, it->store->dbi[IDX_C_SPO], &it->cur));
 
        it->key.mv_data = &it->luc;
        it->key.mv_size = KLEN;
 
        it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_SET);
        if (ct) {
            if (it->rc == MDB_NOTFOUND) *ct = 0;
            else {
                RCCK (it->rc);
                mdb_cursor_count (it->cur, ct);
            }
            log_debug ("Found %lu triples.", *ct);
        }
        //it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_FIRST_DUP);
        it->iter_op_fn = it_next_0bound_ctx;
 
    // No-context search looks for all keys in spo:c.
    } else {
        RCCK (it->rc = mdb_cursor_open (
                it->txn, it->store->dbi[IDX_SPO_C], &it->cur));
        it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_FIRST);
        if (ct) {
            if (it->rc == MDB_NOTFOUND) *ct = 0;
            else {
                MDB_stat stat;
                // s:po and 1- and 2-bound indices have 1 entry per triple.
                mdb_stat (it->txn, it->store->dbi[IDX_S_PO], &stat);
 
                *ct = stat.ms_entries;
            }
            log_debug ("Found %lu triples.", *ct);
        }
        it->iter_op_fn = it_next_0bound;
    }
    if (it->rc != MDB_NOTFOUND) RCCK (it->rc);
 
    return VOLK_OK;
}
 
 
inline static VOLK_rc
lookup_1bound (uint8_t idx0, MDBIterator *it, size_t *ct)
{
    it->term_order = (const uint8_t*)lookup_ordering_1bound[idx0];
 
    log_debug ("Looking up 1 bound term: %x", it->luk[0]);
 
    RCCK (mdb_cursor_open (
                it->txn, it->store->dbi[lookup_indices[idx0]], &it->cur));
 
    it->key.mv_data = it->luk;
    it->key.mv_size = KLEN;
 
    if (ct) {
        // If a context is specified, the only way to count triples matching
        // the context is to loop over them.
        if (it->luc != NULL_KEY) {
            log_debug ("Counting in context: %x", it->luc);
            MDBIterator *ct_it;
            MALLOC_GUARD (ct_it, VOLK_MEM_ERR);
            /*
            memcpy (ct_it, it, sizeof (*ct_it));
            */
 
            ct_it->store = it->store;
            ct_it->txn = it->txn;
            ct_it->ctx_cur = it->ctx_cur;
            ct_it->key = it->key;
            ct_it->data = it->data;
            ct_it->ck = NULL;
            ct_it->luk[0] = it->luk[0];
            ct_it->luc = it->luc;
            ct_it->i = 0;
 
            PRCCK (lookup_1bound (idx0, ct_it, NULL));
 
            VOLK_rc db_rc;
            while (VOLK_END != (db_rc = mdbiter_next_key (ct_it))) {
                PRCCK (db_rc);
                (*ct)++;
            }
 
            // Free the counter iterator without freeing the shared txn.
            if (ct_it->cur) mdb_cursor_close (ct_it->cur);
            free (ct_it->ck);
            free (ct_it);
 
        } else {
            it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_SET);
            if (it->rc == MDB_SUCCESS) mdb_cursor_count (it->cur, ct);
        }
        log_debug ("Found %lu triples.", *ct);
    }
 
    it->i = 0;
    it->iter_op_fn = it_next_1bound;
 
    it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_SET);
    if (it->rc == MDB_SUCCESS)
        it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_GET_MULTIPLE);
    if (it->rc != MDB_NOTFOUND) RCCK (it->rc);
 
    return VOLK_OK;
}
 
 
inline static VOLK_rc
lookup_2bound(uint8_t idx0, uint8_t idx1, MDBIterator *it, size_t *ct)
{
    uint8_t luk1_offset, luk2_offset;
    MDB_dbi dbi = 0;
 
    // Establish lookup ordering with some awkward offset math.
    for (int i = 0; i < 3; i++) {
        if (
            (
                idx0 == lookup_ordering_2bound[i][0] &&
                idx1 == lookup_ordering_2bound[i][1]
            ) || (
                idx0 == lookup_ordering_2bound[i][1] &&
                idx1 == lookup_ordering_2bound[i][0]
            )
        ) {
            it->term_order = (const uint8_t*)lookup_ordering_2bound[i];
            if (it->term_order[0] == idx0) {
                luk1_offset = 0;
                luk2_offset = 1;
            } else {
                luk1_offset = 1;
                luk2_offset = 0;
            }
            dbi = it->store->dbi[lookup_indices[i + 3]];
            log_debug (
                    "Looking up 2 bound in %s",
                    db_labels[lookup_indices[i + 3]]);
 
            break;
        }
    }
 
    if (dbi == 0) {
        log_error (
                "Values %d and %d not found in lookup keys.",
                idx0, idx1);
        return VOLK_VALUE_ERR;
    }
 
    // Compose term keys in lookup key.
    VOLK_DoubleKey luk;
    luk[luk1_offset] = it->luk[0];
    luk[luk2_offset] = it->luk[1];
 
    it->key.mv_data = luk;
    it->key.mv_size = DBL_KLEN;
 
    mdb_cursor_open (it->txn, dbi, &it->cur);
    it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_SET);
 
    if (ct) {
        // If a context is specified, the only way to count triples matching
        // the context is to loop over them.
        if (it->luc != NULL_KEY) {
            MDBIterator *ct_it;
            MALLOC_GUARD (ct_it, VOLK_MEM_ERR);
 
            ct_it->store = it->store;
            ct_it->txn = it->txn;
            ct_it->ctx_cur = it->ctx_cur;
            ct_it->ck = NULL;
            ct_it->luk[0] = it->luk[0];
            ct_it->luk[1] = it->luk[1];
            ct_it->luc = it->luc;
            ct_it->i = 0;
 
            lookup_2bound (idx0, idx1, ct_it, NULL);
 
            while (mdbiter_next_key (ct_it) != VOLK_END) (*ct) ++;
 
            // Free the counter iterator without freeing the shared txn.
            if (ct_it->cur) mdb_cursor_close (ct_it->cur);
            free (ct_it->ck);
            free (ct_it);
 
        } else {
            it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_SET);
            if (it->rc == MDB_SUCCESS) mdb_cursor_count (it->cur, ct);
        }
        log_debug ("Found %lu triples.", *ct);
    }
 
    it->i = 0;
    it->iter_op_fn = it_next_2bound;
 
    it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_SET);
    if (it->rc == MDB_SUCCESS)
        it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_GET_MULTIPLE);
    if (it->rc != MDB_NOTFOUND) RCCK (it->rc);
 
    return VOLK_OK;
}
 
 
inline static VOLK_rc
lookup_3bound (MDBIterator *it, size_t *ct)
{
    log_debug (
            "Looking up 3 bound: {%x, %x, %x}",
            it->luk[0], it->luk[1], it->luk[2]);
 
    it->key.mv_data = it->luk;
 
    if (it->luc != NULL_KEY) {
        it->rc = mdb_cursor_open (
                it->txn, it->store->dbi[IDX_SPO_C], &it->cur);
 
        it->key.mv_size = TRP_KLEN;
        it->data.mv_data = &it->luc;
        it->data.mv_size = KLEN;
 
    } else {
        it->rc = mdb_cursor_open (it->txn, it->store->dbi[IDX_S_PO], &it->cur);
 
        it->key.mv_size = KLEN;
        it->data.mv_data = it->luk + 1;
        it->data.mv_size = DBL_KLEN;
    }
 
    it->rc = mdb_cursor_get (it->cur, &it->key, &it->data, MDB_GET_BOTH);
    if (it->rc != MDB_NOTFOUND) RCCK (it->rc);
 
    mdb_cursor_close (it->cur);
    it->cur = NULL;
 
    if (ct && it->rc == MDB_SUCCESS) *ct = 1;
 
    it->iter_op_fn = it_next_3bound;
    memcpy (it->spok, it->luk, sizeof (VOLK_TripleKey));
 
    return VOLK_OK;
}