source: trunk/symtab/bitstream_super_hash_table.h @ 1772

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

Updated symbol table expansion decision.

File size: 2.9 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    unsigned int m_maxSymbols;
53    unsigned int m_totalSymbols;
54};
55
56BitStreamSuperHashTable::BitStreamSuperHashTable()
57    :m_tableSize(DEFAULT_TABLE_SIZE)
58    ,m_totalSymbols(0)
59{
60    m_table = allocateHashTable(m_tableSize);
61    if (!m_table)
62    {
63        printf ("Failed to allocate table!\n");
64    }
65
66    m_maxSymbols = m_tableSize >> 1 + m_tableSize >> 2;
67}
68
69BitStreamSuperHashTable::~BitStreamSuperHashTable()
70{
71    deallocateHashTable(m_tableSize, m_table);
72}
73
74inline CHAIN** BitStreamSuperHashTable::allocateHashTable(unsigned int size)
75{
76    CHAIN** table = (CHAIN**) calloc(size, sizeof(CHAIN*));
77    return table;
78}
79
80inline void BitStreamSuperHashTable::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    table = NULL;
88}
89
90void BitStreamSuperHashTable::free_chain(CHAIN* &chain)
91{
92    if (chain == NULL)
93    {
94        return;
95    }
96    free_chain(chain->next);
97    free(chain);
98    chain = NULL;
99}
100
101inline unsigned int BitStreamSuperHashTable::nextTableSize()
102{
103    return m_tableSize << 1; // double the size
104}
105
106unsigned int BitStreamSuperHashTable::chainLength(CHAIN* chain)
107{
108   unsigned int items = 0;
109   CHAIN* curr = chain;
110   while (curr != NULL)
111   {
112       items++;
113       curr = curr->next;
114   }
115   return items;
116}
117
118void BitStreamSuperHashTable::Print_Symbol_Table_Distribution()
119{
120    for(unsigned int bucket = 0; bucket < m_tableSize; bucket++)
121    {
122        int items = chainLength(m_table[bucket]);
123        if (items >= 1)
124        {
125            printf ("\tBucket: %i | #items: %i\n", bucket, items);
126        }
127        if (items > MAX_CHAIN)
128        {
129            printf ("\t\tSymbols: ");
130            CHAIN* curr = m_table[bucket];
131            while (curr != NULL)
132            {
133                printf ("%s ", curr->key);
134                curr = curr->next;
135            }
136            printf ("\n");
137        }
138    }
139}
140
141#endif // BITSTREAM_SUPER_HASH_TABLE_H
Note: See TracBrowser for help on using the repository browser.