lphash.h

Go to the documentation of this file.

#ifndef CSNIP_LPHASH_H
#define CSNIP_LPHASH_H
 
#include <csnip/preproc.h>
 
/* table description:
 *   - N: table capacity
 *   - key type
 *   - dummy variables k (key), u, v (slot indices)
 *   - hashing expression: k -> hash value.
 *   - is_empty expression: u -> 0 or 1
 *   - is_match expression: u, k -> 0 or 1
 *   - get_key expression u -> key value
 *   - copy: copy or move the u-th entry to the v-th entry
 *   - clear: clear the u-th table entry (mark it as empty)
 *
 * MISSING in the table description
 *   - is_replaceable expression: u -> 0 or 1.
 *     There is still some question whether this is worth doing for
 *     linear probing;  it would cover some more advanced special
 *     purpose applications, but also somewhat complicate the find
 *     algorithms. (Use cases:  Suppose we want to automatically
 *     invalidate entries in a hashing table, without the need to
 *     explicitly delete them.  That could be the case for example
 *     for "old" table entries; that could be implemented by some form
 *     of is_replaceable.  This needs more thought, because you still
 *     want to make sure that a fixed fraction of entries remains truly
 *     empty rather than just replaceable.)
 */
 
#define csnip_lphash_Find( \
        N, \
        keytype, \
        k, u, \
        hash, \
        is_empty, \
        is_match, \
        get_key, \
        \
        key, \
        return_loc, \
        return_state) \
    do { \
        /* Special case: Empty table.
         *
         * Treat this specially since hash % N is undefined
         * in this case. */ \
        if((N) == 0) { \
            (return_loc) = -1; \
            (return_state) = 2; \
            break; \
        } \
        \
        /* Get the first location */ \
        keytype k = (key); \
        size_t u = (hash) % (N); \
        size_t last = u; \
        \
        /* Continue until a match is found */ \
        (return_state) = 0; \
        while (!(is_empty) && !(is_match)) \
        { \
            ++u; \
            if (u == (N)) \
                u = 0; \
            if (u == last) { \
                /* Not found & table full. */ \
                (return_state) = 2; \
                break; \
            } \
        } \
        \
        if (is_empty) { \
            (return_state) = 1; \
        } \
        (return_loc) = u; \
    } while(0)
 
#define csnip_lphash_Findnext( \
        N, \
        keytype, \
        k, u, \
        hash, \
        is_empty, \
        is_match, \
        get_key, \
        \
        key, \
        loc_prev, \
        ret_loc, \
        ret_state) \
    do { \
        keytype k = (key); \
        size_t u = (loc_prev); \
        size_t last = u; \
        do { \
            ++u; \
            if (u == (N)) \
                u = 0; \
            if (u == last) { \
                /* FIXME: wrapped; handle error */ \
                break; \
            } \
        } while(!(is_empty) && !(is_match)); \
        \
        (ret_loc) = u; \
    } while(0)
 
#define csnip_lphash_Delete( \
        N, \
        keytype, \
        k, u, v, \
        hash, \
        is_empty, \
        get_key, \
        copy, \
        clear, \
        \
        loc) \
    do { \
        size_t v = (loc); \
        size_t u = v; \
        do { \
            if (++u == (N)) \
                u = 0; \
            \
            if ((is_empty) || u == v) { \
                u = v; \
                clear; \
                break; \
            } \
            \
            keytype k = (get_key); \
            size_t h = (hash) % (N); \
            if (v - h < u - h) { \
                copy; \
                v = u; \
            } \
        } while(1); \
    } while(0)
 
#define csnip_lphash_Nextentry( \
        N, \
        u, \
        is_empty, \
        \
        loc, ret) \
    do { \
        size_t u = (loc); \
        while ((is_empty) && u < (N)) { \
            ++u; \
        } \
        (ret) = u; \
    } while (0)
 
#define CSNIP_LPHASH_DECL_FUNCS(scope, prefix, keytype, argl) \
    scope size_t prefix ## findloc(csnip_pp_prepend_##argl \
                keytype key, int* state); \
    scope size_t prefix ## findnextloc(csnip_pp_prepend_##argl keytype key, size_t loc); \
    scope void prefix ## deleteloc(csnip_pp_prepend_##argl size_t loc); \
    scope size_t prefix ## nextentry(csnip_pp_prepend_##argl size_t loc);
 
#define CSNIP_LPHASH_DEF_FUNCS(scope, prefix, \
                argl, \
                N, \
                keytype, \
                k, u, v, \
                hash, \
                is_empty, \
                is_match, \
                get_key, \
                copy, \
                clear) \
    scope size_t prefix##findloc( \
        csnip_pp_prepend_##argl \
        keytype key, \
        int* state_) \
    { \
        size_t ret_; \
        csnip_lphash_Find(N, keytype, k, u, hash, is_empty, is_match, \
            get_key, key, ret_, *state_); \
        return ret_; \
    } \
    \
    scope size_t prefix ## findnextloc( \
        csnip_pp_prepend_##argl \
        keytype key, \
        size_t loc, \
        int* state_) \
    { \
        size_t ret_; \
        csnip_lphash_Findnext(N, keytype, k, u, hash, is_empty, \
            is_match, get_key, key, loc, ret_, *state_); \
        return ret_; \
    } \
    \
    scope void prefix ## deleteloc(csnip_pp_prepend_##argl size_t loc) \
    { \
        csnip_lphash_Delete(N, keytype, k, u, v, hash, is_empty, \
            get_key, copy, clear, loc); \
    } \
    \
    scope size_t prefix ## nextentry(csnip_pp_prepend_##argl size_t loc) \
    { \
        csnip_lphash_Nextentry(N, u, is_empty, loc, loc); \
        return loc; \
    }
 
#endif /* CSNIP_LPHASH_H */