source: trunk/symtab/hash_symbol_table.cpp @ 2152

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

updated hash table implementation to use ramakrishna hash and added auto-expand capability

File size: 4.5 KB
Line 
1#include "hash_symbol_table.h"
2#include "symtab.h"
3
4#define DEFAULT_TABLE_SIZE 128
5#define MAX_CHAIN 4
6
7HashSymbolTable::HashSymbolTable()
8//    :g_lines_count(DEFAULT_LINES)
9    :m_globalNameCount(1)
10    ,g_tableSize(DEFAULT_TABLE_SIZE)
11{
12    g_table = allocateHashTable(g_tableSize);
13    if (!g_table)
14    {
15        printf ("Failed to allocate table!\n");
16    }
17}
18
19HashSymbolTable::~HashSymbolTable()
20{
21    deallocateHashTable(g_tableSize, g_table);
22}
23
24// =================
25// Separate chaining
26#ifdef USE_CHAINING
27unsigned int HashSymbolTable::Lookup_or_Insert_Name(char *name, int lgth)
28{
29    unsigned int bucket = getBucket(name, lgth, g_tableSize);
30
31    // Look up the value in the chain
32    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
33        if( memcmp(chain->key, name, lgth * sizeof(char)) == 0 )
34        {
35            return chain->GID;
36        }
37    }
38
39    // If it was not found, add it
40    char * s = pool.Insert(name,lgth);
41    CHAIN* next = g_table[bucket];
42
43    unsigned int chainlgth = chainLength(next);
44    if (chainlgth == MAX_CHAIN)
45    {
46        //current chain length is maximum, expand the table
47        expandHashTable();
48        bucket = getBucket(name, lgth, g_tableSize);
49        next = g_table[bucket];
50    }
51
52    g_table[bucket] = (CHAIN*) malloc(sizeof(CHAIN));
53    g_table[bucket]->next = next;
54    g_table[bucket]->key = s;
55    g_table[bucket]->GID = m_globalNameCount;
56    g_table[bucket]->lgth = lgth;
57    m_globalNameCount++;
58    Name_Data name_data;
59    name_data.name_string = s;
60    name_data.lgth = lgth;
61    NameTable.push_back(name_data);
62    return g_table[bucket]->GID;
63}
64
65void HashSymbolTable::free_chain(CHAIN* &chain)
66{
67    if (chain == NULL)
68    {
69        return;
70    }
71    free_chain(chain->next);
72    free(chain);
73    chain = NULL;
74}
75#else
76void HashSymbolTable::AllocateHashTable() {
77        g_table = (ITEM *)malloc(g_table_size * sizeof(ITEM));
78        if (!g_table)
79        {
80            Die("Not enough memory");
81        }
82}
83
84void HashSymbolTable::FreeHashTable() {
85        free(g_table);
86}
87
88void HashSymbolTable::InitHashTable() {
89        memset(g_table, 0, g_table_size * sizeof(ITEM));
90}
91
92unsigned int HashSymbolTable::Lookup_or_Insert_Name(char *name, int lgth) {
93        unsigned int hash32 = Hash_Jesteress(name, lgth);
94#ifdef USE_PRIME
95        unsigned int hash = hash32 % table_size;
96#else
97        unsigned int hash = hash32 & g_table_size_mask;
98#endif
99        // Look up the value in the table
100        while(g_table[hash].key != 0) {
101#ifdef STORE_32
102                if( g_table[hash].hash32 == hash32 &&
103                        memcmp(g_table[hash].key, name, lgth * sizeof(CHAR)) == 0 )
104                        return g_table[hash].GID;
105#else
106                if( memcmp(g_table[hash].key, name, lgth * sizeof(CHAR)) == 0 )
107                        return g_table[hash].GID;
108#endif
109#ifdef USE_PRIME
110                hash = (hash + 1) % g_table_size;
111#else
112                hash = (hash + 1) & g_table_size_mask;
113#endif
114        }
115
116        // If it was not found, add it
117        char * s = pool.Insert(name,lgth);
118        g_table[hash].key = s;
119#ifdef STORE_32
120        g_table[hash].hash32 = hash32;
121#endif
122        g_table[hash].GID = m_globalNameCount;
123        m_globalNameCount ++;
124        Name_Data name_data;
125        name_data.name_string = s;
126        name_data.lgth = lgth;
127        NameTable.push_back(name_data);
128        return g_table[hash].GID; //return GID
129}
130
131#endif
132
133unsigned int HashSymbolTable::chainLength(CHAIN* chain)
134{
135   unsigned int items = 0;
136   CHAIN* curr = chain;
137   while (curr != NULL)
138   {
139       items++;
140       curr = curr->next;
141   }
142   return items;
143}
144
145void HashSymbolTable::Print_Symbol_Table_Distribution()
146{
147    for(unsigned int bucket = 0; bucket < g_tableSize; bucket++)
148    {
149        int items = chainLength(g_table[bucket]);
150        if (items >= 1)
151        {
152            printf ("\tBucket: %i | #items: %i\n", bucket, items);
153        }
154        if (items > MAX_CHAIN)
155        {
156            printf ("\t\tSymbols: ");
157            CHAIN* curr = g_table[bucket];
158            while (curr != NULL)
159            {
160                printf ("%s ", curr->key);
161                curr = curr->next;
162            }
163            printf ("\n");
164        }
165    }
166}
167
168void HashSymbolTable::expandHashTable()
169{
170    unsigned int tempTableSize = nextTableSize();
171    CHAIN** tempTable = allocateHashTable(tempTableSize);
172    if (!tempTable)
173    {
174        printf ("Failed to allocate new table, cannot add new symbols.\n");
175    }
176
177    for(unsigned int bucket = 0; bucket < g_tableSize; bucket++)
178    {
179        CHAIN* curr = g_table[bucket];
180        g_table[bucket] = NULL;
181
182        while (curr != NULL)
183        {
184            CHAIN* next = curr->next;
185
186            //insert to new table
187            unsigned int tempIndex = getBucket(curr->key, curr->lgth, tempTableSize);
188            CHAIN* tempNext = tempTable[tempIndex];
189            curr->next = tempNext;
190            tempTable[tempIndex] = curr;
191
192            //update curr
193            curr = next;
194        }
195    }
196
197    // Deallocate m_table
198    deallocateHashTable(g_tableSize, g_table);
199
200    // Reassign m_table
201    g_table = tempTable;
202    g_tableSize = tempTableSize;
203}
Note: See TracBrowser for help on using the repository browser.