source: trunk/symbol_table/hash_table.hpp @ 1960

/*
 * Created on: 18-December-2011
 * Author: Ken Herdy
 *
 * Length partitioned parallel bit stream hashing with chaining.
 *
 */
#ifndef HASH_TABLE_HPP
#define HASH_TABLE_HPP

/*=============================================================================
  allocator.hpp - Coterminal memory pool allocators.
  Created on: 18-December-2011
  Author: Ken Herdy
=============================================================================*/

//#define HASH_TABLE_HPP_DEBUG

#define MIN(a, b) ((a < b) ? a : b)
#define MAX(a, b) ((a > b) ? a : b)
#define MAX_TABLE_SIZE 65536

#include "../lib/bitblock.hpp"
#include "../lib/byte_compare.hpp"
#include "../lib/allocator.hpp"
#include "../lib/s2p.hpp"
#include "../lib/byte_pool.hpp"
#include "../lib/hash.hpp"
#include <cmath>
#include <stdint.h>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;

typedef uint32_t gid_type;

typedef struct node {
    uint8_t * raw_bytes;
    uint32_t  raw_bytes_lgth;
    uint8_t * h0;
    uint8_t * h1;
    uint32_t  hash_bit_lgth;
    gid_type gid;
    node * next;
} node;

class gid {
public:
    static uint64_t next() { return value++; }
private:
    static uint64_t value;
};

/* Global GID for all hash_tables */
uint64_t gid::value = 1;

/*
TODO - Move raw_data_pool up into a base class
that so all hash table implementation share the same memory pool.
*/

template<class COMPARE_STRATEGY, class HASH_STRATEGY, class ALLOCATOR>
class hash_table {
public:

    hash_table(const uint32_t table_size=4096, const uint32_t load_factor=2) {
        init(table_size,load_factor);
    }

    virtual ~hash_table() {
        destroy_table(this->table, this->table_size);
    }

    IDISA_ALWAYS_INLINE uint64_t get_bucket(const uint8_t * h0, const uint8_t * h1, const uint32_t idx, const uint32_t slice_bits) {
        return hash_strategy.hash(h0,h1,idx,slice_bits,hash_size);
    }

    IDISA_ALWAYS_INLINE void insert(const uint64_t bucket, uint8_t * raw_bytes, uint32_t raw_byte_lgth, uint8_t * h0, uint8_t * h1, uint32_t hash_bit_lgth, gid_type gid) {

        node * next = (node *) malloc(sizeof(node));
        if (next == NULL) {
            cerr << "Out of Memory" << endl;
            abort();
        }


        next->raw_bytes = raw_bytes;
        next->raw_bytes_lgth = raw_byte_lgth;
        next->h0 = h0;
        next->h1 = h1;
        next->hash_bit_lgth = hash_bit_lgth;
        next->gid = gid;

        next->next = table[bucket];
        table[bucket] = next;
    }

    IDISA_ALWAYS_INLINE gid_type lookup_or_insert(uint8_t * raw_bytes, const uint32_t idx, const uint32_t raw_byte_lgth,
                                                  uint8_t * h0, uint8_t * h1, const uint32_t hash_bit_lgth) {

        uint64_t bucket = get_bucket(h0,h1,idx,hash_bit_lgth);

        node * crt = table[bucket];
        node * prev = crt;

        /* lookup */
        while(NULL != crt) {
            if(compare_strategy.compare(&raw_bytes[idx], crt->raw_bytes, raw_byte_lgth)) {
                return crt->gid;
            }
            prev = crt;
            crt = crt->next;
        }

        /* insert */
        gid_type gid = gid::next();

        uint64_t x0 = bit_slice(h0, idx, hash_bit_lgth);
        uint64_t x1 = bit_slice(h1, idx, hash_bit_lgth);

#ifdef HASH_TABLE_HPP_DEBUG
        cout << "Insert: ";
        cout << "Idx: " << idx << ", ";
        cout << "GID: " << gid << ", ";
        cout << "Val: '" << string((char *) &raw_bytes[idx],0,raw_byte_lgth) << "', ";
        cout << "Bkt: " << bucket << endl;
#endif

        insert( bucket,
                raw_data_pool.insert(&raw_bytes[idx],raw_byte_lgth),
                raw_byte_lgth,
                raw_data_pool.insert((uint8_t *)&x0, bits2bytes(hash_bit_lgth)),
                raw_data_pool.insert((uint8_t *)&x1, bits2bytes(hash_bit_lgth)),
                hash_bit_lgth,
                gid);

        if(expansion_test(table[bucket])) {
            expand();
        }
        // elements++;
        return gid;
    }

    void print_table() const {

        for(int i=0;i<table_size;i++) {

            node * head = table[i];
            node * crt = head;

            if(head != NULL) { cout << "table[" << i << "]"; }

            while(crt != NULL) {
                cout << "->"    << "(GID:" << crt->gid
                                << ", Val:'" << string((char *)&crt->raw_bytes[0], crt->raw_bytes_lgth)
                                << "', Len:" << crt->raw_bytes_lgth << ")";
                crt = crt->next;
            }

            if(head != NULL) { cout << endl; }
        }
    }

private:
    // ----- Members -----
    uint32_t table_size;
    uint32_t hash_size;
    uint32_t load_factor;

    node ** table;
    // uint32_t elements;
    byte_pool<ALLOCATOR> raw_data_pool;
    COMPARE_STRATEGY compare_strategy;
    HASH_STRATEGY hash_strategy;

    // ----- Helpers -----
    uint32_t log2msb(uint32_t v) {
        uint32_t r = 0;
        while (v >>= 1) {r++;}
        return r;
    }

    void init(const uint32_t size, const uint32_t factor) {

        hash_size = MIN((log2msb(size)),hash_strategy.max_hashsize());
        table_size = pow(2.0, (double)hash_size);
        table = (node**) calloc(table_size, sizeof(node*));

        if ((table) == NULL) {
                cerr << "Out of Memory" << endl;
                abort();
        }
        // elements = 0;
        load_factor = factor;
    }

    void destroy_table(node ** table, const uint32_t table_size) {
        node * crt = NULL;
        node * next = NULL;

        for(int i=0;i<table_size;i++) {
            crt = table[i];
            while(crt != NULL) {
                next = crt->next;
                free((node  *)crt);
                crt = next;
            }
        }

        free((node **) table);
        table = NULL;
    }

    uint32_t chain_lgth(const node * chain) {
        uint32_t lgth = 0;
        node * crt = (node *)chain;
        while(NULL != crt) {
            lgth++;
            crt = crt->next; //?
        }
        return lgth;
    }

    bool expansion_test(const node * chain) {

        if ((chain_lgth(chain) > load_factor)
                && (hash_size < hash_strategy.max_hashsize())
                && table_size <= MAX_TABLE_SIZE) {
            return true;
        }
        return false;
    }

    void expand() { // naive expansion

        node ** prev_table = this->table;
        uint32_t prev_size = this->table_size;

        init(table_size*2, load_factor); // TODO - WARNING - CONSIDER MAX MEMORY

        uint64_t bucket;
        node * crt;

        for(int i=0;i<prev_size;i++) {
            crt = prev_table[i];

            while(crt != NULL) {
                bucket = this->get_bucket(crt->h0,
                                          crt->h1,
                                          0,
                                          crt->hash_bit_lgth);
                this->insert(bucket,
                             crt->raw_bytes,
                             crt->raw_bytes_lgth,
                             crt->h0,
                             crt->h1,
                             crt->hash_bit_lgth,
                             crt->gid);

                crt = crt->next;
            }
        }

        destroy_table(prev_table,prev_size);
        crt = NULL;

        for(int i=0;i<table_size;i++) {
            if(expansion_test(table[i])) {
                expand();
            }
        }
    }

};

/* Length specialized strategy classes. Hash, Compare */

/* Templated approach:
(1) Avoids duplicate code,
(2) Avoid vtable overhead,
(3) Introduces additional coding complexity.
*/

/* Hash Strategy */
class hash_strategy {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits);
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize();
protected:
    hash_strategy() {}
};

template<uint32_t LGTH>
class hash_strategy_t: public hash_strategy {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits);
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize();
};

/* Specialized 'Byte' hash functions. */
template<> class hash_strategy_t<1> {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
        return h0[idx];
    }
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(1); }
};

template<> class hash_strategy_t<2> {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits); // TODO byte_compress_hash
    }
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(2); }
};

template<> class hash_strategy_t<3> {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    }
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(3); }
};

template<> class hash_strategy_t<4>: public hash_strategy {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    };
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(4); }
};

template<> class hash_strategy_t<5>: public hash_strategy {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    };
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(5); }
};

template<> class hash_strategy_t<6>: public hash_strategy {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    };
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(6); }
};

template<> class hash_strategy_t<7>: public hash_strategy {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
        return bit_compress_hash(h0, h1, bytes2bits(idx), slice_bits, hash_bits);
    };
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return bytes2bits(7); }
};

template<> class hash_strategy_t<8>: public hash_strategy {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
        return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits);
    };
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 8; }
};

/* Default */
class hash_strategy_d: public hash_strategy {
public:
    static IDISA_ALWAYS_INLINE uint64_t hash(const uint8_t * h0, const uint8_t * h1, const int32_t idx, const uint32_t slice_bits, const uint32_t hash_bits) {
        return bit_compress_hash(h0, h1, idx, slice_bits, hash_bits); // expect h0 as hash bit stream
    }
    /* WARNING: Min bit count of any default (non-specialized) bit_compress_hash. */
    static IDISA_ALWAYS_INLINE uint32_t max_hashsize() { return 9; }
};

/* Compare Strategy */
class compare_strategy {
public:
    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0);
protected:
    compare_strategy() {}
};

/* Length specific comparison */
template<class T, uint32_t LGTH>
class identity_strategy_t: public compare_strategy {
public:
    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
        return overlap_compare<T,LGTH>(x,y);
    }
};

/* Default */
class identity_strategy_d: public compare_strategy {
public:
    static IDISA_ALWAYS_INLINE bool compare(uint8_t * x, uint8_t * y, const uint32_t lgth=0) {
        return mem_compare(x,y,lgth);
    }
};

#endif // HASH_TABLE_HPP