source: trunk/symtab/bitstream_hash_table.h @ 4004

Last change on this file since 4004 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
Line 
1/*
2 * Created on: 26-August-2011
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.
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.
9 *
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 *
15 */
16
17#ifndef BITSTREAM_HASH_TABLE_H
18#define BITSTREAM_HASH_TABLE_H
19
20#define DEBUm_BHT 0
21
22#define DEFAULT_TABLE_SIZE 256
23#define TABLE_SIZE_MASK(x) x-1
24
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
36class BitStreamHashTable
37{
38
39public:
40    BitStreamHashTable();
41    ~BitStreamHashTable();
42
43    // Symbol length > 16
44    unsigned int Lookup_Name_17(char * name, const int hashvalue, int L);
45
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);
48
49    // DEBUG FUNCTIONS
50    void Print_Symbol_Table_Distribution();
51
52protected:
53    CHAIN ** m_table;
54    unsigned int m_tableSize;
55    inline unsigned int getBucket(const int hashvalue, unsigned int tableSize);
56
57private:
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);
65};
66
67inline unsigned int BitStreamHashTable::getBucket(const int hashvalue, unsigned int tableSize)
68{
69//    return hashvalue & TABLE_SIZE_MASK(tableSize);
70    return hashvalue % tableSize;
71}
72
73inline CHAIN** BitStreamHashTable::allocateHashTable(unsigned int size)
74{
75    CHAIN** table = (CHAIN**) calloc(size, sizeof(CHAIN*));
76    memset(table, 0, m_tableSize*sizeof(CHAIN*));
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{
91    return m_tableSize << 1; // double the size
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
106#endif // BITSTREAM_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.