source: trunk/symtab/bitstream_super_hash_table.h @ 2136

Last change on this file since 2136 was 1773, checked in by vla24, 8 years ago

Reverted table expansion decision changes. It slows down performance

File size: 2.8 KB
Line 
1#ifndef BITSTREAM_SUPER_HASH_TABLE_H
2#define BITSTREAM_SUPER_HASH_TABLE_H
3
4#define DEFAULT_TABLE_SIZE      128
5#define TABLE_SIZE_MASK(x)      x-1
6
7 // Counts the number of consecutive bits
8 // PRECONDITION: x should be (power of two - 1)
9 // e.g. input = 4 = 0100
10 //      output = 2
11#define BIT_SIZE(x)             cfzl(x)
12#define BYTES_TO_BITS(x)        x << 3
13#define MAX_CHAIN               4
14
15#include <string.h>
16#include <stdlib.h>
17#include <stdio.h>
18
19struct CHAIN {
20    const char* key;
21    int hashvalue;
22    CHAIN* next;
23    unsigned int GID;
24    unsigned int lgth;
25
26    CHAIN()
27        :key(NULL)
28        ,hashvalue(0)
29        ,next(NULL)
30        ,GID(0)
31        ,lgth(0)
32    {}
33};
34
35class BitStreamSuperHashTable
36{
37public:
38    BitStreamSuperHashTable();
39    ~BitStreamSuperHashTable();
40    void Print_Symbol_Table_Distribution();
41
42protected:
43    CHAIN** m_table;
44    unsigned int m_tableSize;
45    inline CHAIN** allocateHashTable(unsigned int size);
46    inline void deallocateHashTable(unsigned int size, CHAIN** &table);
47    void free_chain(CHAIN* &chain);
48
49    unsigned int nextTableSize();
50    unsigned int chainLength(CHAIN* chain);
51};
52
53BitStreamSuperHashTable::BitStreamSuperHashTable()
54    :m_tableSize(DEFAULT_TABLE_SIZE)
55{
56    m_table = allocateHashTable(m_tableSize);
57    if (!m_table)
58    {
59        printf ("Failed to allocate table!\n");
60    }
61}
62
63BitStreamSuperHashTable::~BitStreamSuperHashTable()
64{
65    deallocateHashTable(m_tableSize, m_table);
66}
67
68inline CHAIN** BitStreamSuperHashTable::allocateHashTable(unsigned int size)
69{
70    CHAIN** table = (CHAIN**) calloc(size, sizeof(CHAIN*));
71    return table;
72}
73
74inline void BitStreamSuperHashTable::deallocateHashTable(unsigned int size, CHAIN** &table)
75{
76    for(unsigned int hash = 0; hash < size; hash++)
77    {
78        free_chain(table[hash]);
79    }
80    free(table);
81    table = NULL;
82}
83
84void BitStreamSuperHashTable::free_chain(CHAIN* &chain)
85{
86    if (chain == NULL)
87    {
88        return;
89    }
90    free_chain(chain->next);
91    free(chain);
92    chain = NULL;
93}
94
95inline unsigned int BitStreamSuperHashTable::nextTableSize()
96{
97    return m_tableSize << 1; // double the size
98}
99
100unsigned int BitStreamSuperHashTable::chainLength(CHAIN* chain)
101{
102   unsigned int items = 0;
103   CHAIN* curr = chain;
104   while (curr != NULL)
105   {
106       items++;
107       curr = curr->next;
108   }
109   return items;
110}
111
112void BitStreamSuperHashTable::Print_Symbol_Table_Distribution()
113{
114    for(unsigned int bucket = 0; bucket < m_tableSize; bucket++)
115    {
116        int items = chainLength(m_table[bucket]);
117        if (items >= 1)
118        {
119            printf ("\tBucket: %i | #items: %i\n", bucket, items);
120        }
121        if (items > MAX_CHAIN)
122        {
123            printf ("\t\tSymbols: ");
124            CHAIN* curr = m_table[bucket];
125            while (curr != NULL)
126            {
127                printf ("%s ", curr->key);
128                curr = curr->next;
129            }
130            printf ("\n");
131        }
132    }
133}
134
135#endif // BITSTREAM_SUPER_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.