source: trunk/symtab/bitstream_hash_table.h @ 4035

Last change on this file since 4035 was 1665, checked in by vla24, 8 years ago

SymbolTable?: Update symtab library for dictionary div2 delimiter. Fixed some compile errors for log grouping

File size: 2.7 KB
RevLine 
[1387]1/*
[1391]2 * Created on: 26-August-2011
[1387]3 * Author: Vera Lukman
4 *
5 * This hash table is almost an exact copy of HashSymbolTable except that
6 * BitStreamDivHashTable accepts a hashvalue to insert or lookup for a key.
[1391]7 * This hash table is designed specifically for Parallel Bitstream-Based Length Sorting Symbol Table.
8 * It is the base class of BitstreamIdentityHashTable, BitstreamLogHashTable and BitstreamDivHashTable.
[1387]9 *
[1391]10 * Each grouping strategy use different comparison strategy
11 * Identity group sorting        f(L) = L
12 * Log group sorting             f(L) = ceil (log(L))
13 * Division group sorting        f(L) = floor( (L-1)/2^k )
14 *
[1387]15 */
16
[1229]17#ifndef BITSTREAM_HASH_TABLE_H
18#define BITSTREAM_HASH_TABLE_H
19
[1665]20#define DEBUm_BHT 0
[1229]21
[1518]22#define DEFAULT_TABLE_SIZE 256
23#define TABLE_SIZE_MASK(x) x-1
[1229]24
[1518]25#include <string.h>
26#include <stdlib.h>
27
28struct CHAIN {
29    const char* key;
30    int hashvalue;
31    struct CHAIN* next;
32    unsigned int GID;
33    unsigned int lgth;
34};
35
[1229]36class BitStreamHashTable
37{
38
39public:
[1391]40    BitStreamHashTable();
41    ~BitStreamHashTable();
[1229]42
[1391]43    // Symbol length > 16
[1462]44    unsigned int Lookup_Name_17(char * name, const int hashvalue, int L);
[1229]45
[1518]46    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid);
47    void Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth);
[1229]48
[1391]49    // DEBUG FUNCTIONS
[1229]50    void Print_Symbol_Table_Distribution();
51
[1391]52protected:
[1665]53    CHAIN ** m_table;
54    unsigned int m_tableSize;
55    inline unsigned int getBucket(const int hashvalue, unsigned int tableSize);
[1229]56
[1391]57private:
[1518]58    void free_chain(CHAIN* &chain);
59    void expandHashTable();
60
61    inline CHAIN** allocateHashTable(unsigned int size);
62    inline void deallocateHashTable(unsigned int size, CHAIN** &table);
63    inline unsigned int nextTableSize();
64    inline unsigned int chainLength(CHAIN* chain);
[1229]65};
66
[1518]67inline unsigned int BitStreamHashTable::getBucket(const int hashvalue, unsigned int tableSize)
[1229]68{
[1518]69//    return hashvalue & TABLE_SIZE_MASK(tableSize);
70    return hashvalue % tableSize;
[1229]71}
72
[1518]73inline CHAIN** BitStreamHashTable::allocateHashTable(unsigned int size)
74{
75    CHAIN** table = (CHAIN**) calloc(size, sizeof(CHAIN*));
[1665]76    memset(table, 0, m_tableSize*sizeof(CHAIN*));
[1518]77    return table;
78}
79
80inline void BitStreamHashTable::deallocateHashTable(unsigned int size, CHAIN** &table)
81{
82    for(unsigned int hash = 0; hash < size; hash++)
83    {
84        free_chain(table[hash]);
85    }
86    free(table);
87}
88
89inline unsigned int BitStreamHashTable::nextTableSize()
90{
[1665]91    return m_tableSize << 1; // double the size
[1518]92}
93
94unsigned int BitStreamHashTable::chainLength(CHAIN* chain)
95{
96   unsigned int items = 0;
97   CHAIN* curr = chain;
98   while (curr != NULL)
99   {
100       items++;
101       curr = curr->next;
102   }
103   return items;
104}
105
[1229]106#endif // BITSTREAM_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.