source: trunk/symtab/hash_symbol_table.h @ 2136

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

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

File size: 3.0 KB
RevLine 
[1229]1#ifndef HASH_SYMBOL_TABLE_H
2#define HASH_SYMBOL_TABLE_H
3
4//#define USE_PRIME
5#define USE_CHAINING
6//#define STORE_32
7#define _CRT_SECURE_NO_DEPRECATE
[1776]8#define TABLE_SIZE_MASK(x) x-1
[1229]9
10
11#include <stdlib.h>
12#include "stringpool.h"
13#include <string.h>
14#include <vector>
[1776]15//#include "hash.h"
[1229]16
[1776]17static unsigned int HashRamakrishna(const char *key, unsigned int len) {
18        unsigned int h = 0;
19        for(unsigned int i = 0; i < len; ++i) {
20                h ^= (h << 5) + (h >> 2) + key[i];
21        }
22        return h;
23}
24
[1229]25using namespace std;
26
27struct Name_Data;
28
29#ifdef USE_CHAINING
30    struct CHAIN;
31    struct CHAIN {
[1776]32            char* key;
[1229]33            struct CHAIN* next;
34            unsigned int GID;
[1776]35            unsigned int lgth;
[1229]36    };
37    typedef struct CHAIN CHAIN;
38#else
39    typedef struct {
40            const char* key;
41    #ifdef STORE_32
42            UINT hash32;
43    #endif
44            unsigned int GID;
45    } ITEM;
46#endif
[1776]47class HashSymbolTable
48{
[1229]49
50public:
51    /*
52    enum HashFuncEnum
53    {
54        HashBernstein,
55        HashKernighanRitchie,
56        Hash17_unrolled,
57        Hash65599,
58        HashFNV1a,
59        HashUniversal,
60        HashWeinberger,
61        HashLarson,
62        HashPaulHsieh,
63        HashOneAtTime,
64        HashLookup3,
65        HashArashPartow,
66        CRC32,
67        HashRamakrishna,
68        HashFletcher,
69        HashMurmur2,
70        HashHanson,
71        NovakHashUnrolled,
72        HashSBox,
73        HashMaPrime2c,
74        Hash_Jesteress,
75        Hash_Meiyan,
76        HashMurmur2A,
77    #ifdef _WIN64
78        HashAlfalfa_QWORD,
79        HashFNV1A_unrolled8
80    #endif
81    //    HashFNV1A_unrolled,
82    //    HashAlfalfa,
83    //    HashAlfalfa_HALF,
84    //    HashAlfalfa_DWORD,
85    //    Hash_Sixtinsensitive,
86    //    Hash_WHIZ,
87    };
88*/
89    HashSymbolTable();
90    ~HashSymbolTable();
91
92    // Returns hash value
93    // Returns -1 upon failure
94    unsigned int Lookup_or_Insert_Name(char * name, int lgth);
95
96//    char * Get_Name(int nameID);
97//    int Get_Lgth(int nameID);
98
99    vector<Name_Data> NameTable;
[1776]100    void Print_Symbol_Table_Distribution();
[1229]101
102private:
103    StringPool<4096,100> pool;
104
105    unsigned int m_globalNameCount;
106
[1776]107    CHAIN** g_table;
108    unsigned int g_tableSize;
109    inline CHAIN** allocateHashTable(unsigned int size);
110    inline void deallocateHashTable(unsigned int size, CHAIN** &table);
111    void free_chain(CHAIN* &chain);
112
113    inline unsigned int getBucket(char *name, int lgth, int table_size);
114    unsigned int chainLength(CHAIN* chain);
115    inline unsigned int nextTableSize();
116    void expandHashTable();
117
118};
119
120
121inline void HashSymbolTable::deallocateHashTable(unsigned int size, CHAIN** &table)
122{
123    for(unsigned int hash = 0; hash < size; hash++)
124    {
125        free_chain(table[hash]);
126    }
127    free(table);
128    table = NULL;
129}
130
131inline CHAIN** HashSymbolTable::allocateHashTable(unsigned int size)
132{
133    CHAIN** table = (CHAIN**) calloc(size, sizeof(CHAIN*));
134    return table;
135}
136
137inline unsigned int HashSymbolTable::getBucket(char *name, int lgth, int table_size)
138{
139#ifdef USE_PRIME
140        return HashRamakrishna(name, lgth) % table_size;
[1229]141#else
[1776]142        return HashRamakrishna(name, lgth) & TABLE_SIZE_MASK(table_size);
[1229]143#endif
[1776]144}
[1229]145
[1776]146inline unsigned int HashSymbolTable::nextTableSize()
147{
148    return g_tableSize << 1;
149}
[1229]150
151#endif // HASH_SYMBOL_TABLE_H
Note: See TracBrowser for help on using the repository browser.