Changeset 1776 for trunk


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

Location:
trunk/symtab
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/symtab/hash_symbol_table.cpp

    r1229 r1776  
    11#include "hash_symbol_table.h"
    2 #include "hash.h"
    32#include "symtab.h"
    43
    5 #define DEFAULT_LINES 5013
     4#define DEFAULT_TABLE_SIZE 128
     5#define MAX_CHAIN 4
    66
    77HashSymbolTable::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);
     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    }
    2117}
    2218
    2319HashSymbolTable::~HashSymbolTable()
    2420{
    25     FreeHashTable();
    26 }
    27 
    28 void 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
     21    deallocateHashTable(g_tableSize, g_table);
    4722}
    4823
     
    5227unsigned int HashSymbolTable::Lookup_or_Insert_Name(char *name, int lgth)
    5328{
    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 
    81 void 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 
    94 void HashSymbolTable::FreeHashTable(void) {
    95         free(g_table);
    96         free(g_chains);
    97 }
    98 
    99 void HashSymbolTable::InitHashTable(void) {
    100         g_next_free_chain = 0;
    101         memset(g_table, 0, g_table_size * sizeof(CHAIN *));
     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;
    10274}
    10375#else
     
    156128        return g_table[hash].GID; //return GID
    157129}
    158 #endif
    159 
     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}
  • 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.