source: trunk/lib/symtab/hash_symbol_table.cpp @ 1518

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

Reorganized SymbolTable? library

File size: 4.0 KB
Line 
1#include "hash_symbol_table.h"
2#include "hash.h"
3#include "symtab.h"
4
5#define DEFAULT_LINES 5013
6
7HashSymbolTable::HashSymbolTable()
8    :g_lines_count(DEFAULT_LINES)
9    ,m_globalNameCount(1)
10{
11    unsigned int table_bits = 0;
12    SetTableSize(table_bits, 1);
13    AllocateHashTable();
14    InitHashTable();
15
16
17    Name_Data name_data;
18    name_data.name_string = NULL;
19    name_data.lgth = 0;
20    NameTable.push_back(name_data);
21}
22
23HashSymbolTable::~HashSymbolTable()
24{
25    FreeHashTable();
26}
27
28void HashSymbolTable::SetTableSize(unsigned int table_bits, unsigned int table_bits_factor) {
29    if (table_bits == 0)
30            table_bits = NextLog2(g_lines_count) + table_bits_factor;
31    if (table_bits + sizeof(void *) > sizeof(SIZE_T) * CHAR_BIT)
32    {
33        FreeHashTable();
34        Die("table too large (decrease the number of bits or use a 64-bit compiler)");
35    }
36#ifdef USE_PRIME
37                                 // 1  2  4   8  16  32  64  128  256  512  1024  2048  4096
38    unsigned int closest_prime[] = {2, 2, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099,
39                                    8209,16411, 32771, 65537, 131101, 262147, 524309, 1048583,
40                                    2097169, 4194319, 8388617, 16777259, 33554467, 67108879,
41                                    134217757, 268435459, 536870923, 1073741827, 2147483659};
42    g_table_size = closest_prime[ table_bits ];
43#else
44    g_table_size = (1 << table_bits);
45    g_table_size_mask = g_table_size - 1;
46#endif
47}
48
49// =================
50// Separate chaining
51#ifdef USE_CHAINING
52unsigned int HashSymbolTable::Lookup_or_Insert_Name(char *name, int lgth)
53{
54#ifdef USE_PRIME
55        unsigned int hash = Hash_Jesteress(name, lgth) % g_table_size;
56#else
57        unsigned int hash = Hash_Jesteress(name, lgth) & g_table_size_mask;
58#endif
59        // Look up the value in the chain
60        for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
61            if( memcmp(chain->key, name, lgth * sizeof(CHAR)) == 0 )
62            {
63                return chain->GID;
64            }
65        }
66        // If it was not found, add it
67        char * s = pool.Insert(name,lgth);
68        CHAIN* next = g_table[hash];
69        g_table[hash] = &g_chains[g_next_free_chain++];
70        g_table[hash]->next = next;
71        g_table[hash]->key = s;
72        g_table[hash]->GID = m_globalNameCount;
73        m_globalNameCount++;
74        Name_Data name_data;
75        name_data.name_string = s;
76        name_data.lgth = lgth;
77        NameTable.push_back(name_data);
78        return g_table[hash]->GID;
79}
80
81void HashSymbolTable::AllocateHashTable(void) {
82        g_table = (CHAIN **)malloc(g_table_size * sizeof(CHAIN *));
83        if (!g_table)
84        {
85            Die("Not enough memory");
86        }
87        g_chains = (CHAIN*)malloc(g_lines_count * sizeof(CHAIN));
88        if (!g_chains)
89        {
90            Die("Not enough memory");
91        }
92}
93
94void HashSymbolTable::FreeHashTable(void) {
95        free(g_table);
96        free(g_chains);
97}
98
99void HashSymbolTable::InitHashTable(void) {
100        g_next_free_chain = 0;
101        memset(g_table, 0, g_table_size * sizeof(CHAIN *));
102}
103#else
104void HashSymbolTable::AllocateHashTable() {
105        g_table = (ITEM *)malloc(g_table_size * sizeof(ITEM));
106        if (!g_table)
107        {
108            Die("Not enough memory");
109        }
110}
111
112void HashSymbolTable::FreeHashTable() {
113        free(g_table);
114}
115
116void HashSymbolTable::InitHashTable() {
117        memset(g_table, 0, g_table_size * sizeof(ITEM));
118}
119
120unsigned int HashSymbolTable::Lookup_or_Insert_Name(char *name, int lgth) {
121        unsigned int hash32 = Hash_Jesteress(name, lgth);
122#ifdef USE_PRIME
123        unsigned int hash = hash32 % table_size;
124#else
125        unsigned int hash = hash32 & g_table_size_mask;
126#endif
127        // Look up the value in the table
128        while(g_table[hash].key != 0) {
129#ifdef STORE_32
130                if( g_table[hash].hash32 == hash32 &&
131                        memcmp(g_table[hash].key, name, lgth * sizeof(CHAR)) == 0 )
132                        return g_table[hash].GID;
133#else
134                if( memcmp(g_table[hash].key, name, lgth * sizeof(CHAR)) == 0 )
135                        return g_table[hash].GID;
136#endif
137#ifdef USE_PRIME
138                hash = (hash + 1) % g_table_size;
139#else
140                hash = (hash + 1) & g_table_size_mask;
141#endif
142        }
143
144        // If it was not found, add it
145        char * s = pool.Insert(name,lgth);
146        g_table[hash].key = s;
147#ifdef STORE_32
148        g_table[hash].hash32 = hash32;
149#endif
150        g_table[hash].GID = m_globalNameCount;
151        m_globalNameCount ++;
152        Name_Data name_data;
153        name_data.name_string = s;
154        name_data.lgth = lgth;
155        NameTable.push_back(name_data);
156        return g_table[hash].GID; //return GID
157}
158#endif
159
Note: See TracBrowser for help on using the repository browser.