Ignore:
Timestamp:
Dec 13, 2011, 8:22:09 PM (7 years ago)
Author:
vla24
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/symtab/hash_symbol_table.h

    r1229 r1776  
    66//#define STORE_32
    77#define _CRT_SECURE_NO_DEPRECATE
     8#define TABLE_SIZE_MASK(x) x-1
    89
    910
     
    1213#include <string.h>
    1314#include <vector>
     15//#include "hash.h"
     16
     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}
    1424
    1525using namespace std;
     
    1727struct Name_Data;
    1828
    19 class HashSymbolTable
    20 {
    21 
    2229#ifdef USE_CHAINING
    2330    struct CHAIN;
    2431    struct CHAIN {
    25             const char* key;
     32            char* key;
    2633            struct CHAIN* next;
    2734            unsigned int GID;
     35            unsigned int lgth;
    2836    };
    2937    typedef struct CHAIN CHAIN;
     
    3745    } ITEM;
    3846#endif
     47class HashSymbolTable
     48{
    3949
    4050public:
     
    8898
    8999    vector<Name_Data> NameTable;
     100    void Print_Symbol_Table_Distribution();
    90101
    91102private:
    92     size_t g_lines_count;
    93     size_t g_table_size_mask;
    94     size_t g_table_size;
    95 
    96103    StringPool<4096,100> pool;
    97104
    98105    unsigned int m_globalNameCount;
    99106
    100 #ifdef USE_CHAINING
    101     CHAIN ** g_table;
    102     CHAIN * g_chains;
    103     unsigned int g_next_free_chain;
    104 #else
    105     ITEM * g_table;
    106 #endif
     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);
    107112
    108     void AllocateHashTable();
    109     void InitHashTable();
    110     void SetTableSize(unsigned int table_bits, unsigned int table_bits_factor);
    111     void FreeHashTable();
     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();
    112117
    113118};
    114119
     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;
     141#else
     142        return HashRamakrishna(name, lgth) & TABLE_SIZE_MASK(table_size);
     143#endif
     144}
     145
     146inline unsigned int HashSymbolTable::nextTableSize()
     147{
     148    return g_tableSize << 1;
     149}
     150
    115151#endif // HASH_SYMBOL_TABLE_H
Note: See TracChangeset for help on using the changeset viewer.