Ignore:
Timestamp:
Aug 3, 2011, 5:15:51 PM (8 years ago)
Author:
vla24
Message:

SymbolTable?: Changed hash table memory allocation. Previously we pre-allocated the memory, now we allocate the memory as we need.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/symtab/bitstream_hash_table.h

    r1229 r1270  
    55
    66#define USE_FUNCTION_TEMPLATES
    7 #define DEFAULT_LINES 213
    8 
     7#define TABLE_SIZE 256
     8#define TABLE_SIZE_MASK TABLE_SIZE-1
    99// This hash table is almost an exact copy of HashSymbolTable except that
    1010// BitStreamHashTable accepts a hashvalue to insert or lookup for a key.
     
    2626class BitStreamHashTable
    2727{
    28     struct CHAIN;
    2928    struct CHAIN {
    30             const char* key;
    31             struct CHAIN* next;
    32             unsigned int GID;
    33             unsigned int lgth;
     29        const char* key;
     30        struct CHAIN* next;
     31        unsigned int GID;
     32        unsigned int lgth;
    3433    };
    35     typedef struct CHAIN CHAIN;
    3634
    3735public:
    3836    BitStreamHashTable()
    39         :g_lines_count(DEFAULT_LINES)
    40     {
    41         unsigned int table_bits = 0;
    42         SetTableSize(table_bits, 1);
    43 
    44         g_chains = (CHAIN*)malloc(g_lines_count * sizeof(CHAIN));
    45         if (!g_chains)
    46         {
    47             fprintf(stderr, "Not enough memory");
    48             exit(1);
    49         }
    50         g_table = (CHAIN **)malloc(g_table_size * sizeof(CHAIN *));
    51 
    52         if (!g_table)
    53         {
    54             fprintf(stderr, "Not enough memory");
    55             exit(1);
    56         }
    57 
    58         g_next_free_chain = 0;
    59         memset(g_table, 0, g_table_size * sizeof(CHAIN *));
     37    {
     38        g_table = (CHAIN**) calloc(TABLE_SIZE, sizeof(CHAIN*));
     39        memset(g_table, 0, TABLE_SIZE*sizeof(CHAIN*));
    6040    }
    6141
    6242    ~BitStreamHashTable()
    6343    {
     44        for(int hash = 0; hash < TABLE_SIZE; hash++)
     45        {
     46            free_chain(g_table[hash]);
     47        }
    6448        free(g_table);
    65         free(g_chains);
    6649    }
    6750
     
    10184    void Print_Symbol_Table_Distribution();
    10285
     86    void free_chain(CHAIN* chain);
     87
    10388private:
    104     size_t g_lines_count;
    105     size_t g_table_size_mask;
    106     size_t g_table_size;
    107 
    10889    CHAIN ** g_table;
    109     CHAIN * g_chains;
    110     unsigned int g_next_free_chain;
    11190
    11291    inline void SetTableSize(unsigned int table_bits, unsigned int table_bits_factor);
     
    327306    // If it was not found, add it
    328307    CHAIN* next = g_table[hash];
    329     g_table[hash] = &g_chains[g_next_free_chain++];
     308    g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
    330309    g_table[hash]->next = next;
    331310    g_table[hash]->key = name;
     
    343322    // If it was not found, add it
    344323    CHAIN* next = g_table[hash];
    345     g_table[hash] = &g_chains[g_next_free_chain++];
     324    g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
    346325    g_table[hash]->next = next;
    347326    g_table[hash]->key = name;
     
    354333}
    355334
    356 inline void BitStreamHashTable::SetTableSize(unsigned int table_bits, unsigned int table_bits_factor)
    357 {   if (table_bits == 0)
    358         table_bits = NextLog2(g_lines_count) + table_bits_factor;
    359     if (table_bits + sizeof(void *) > sizeof(size_t) * CHAR_BIT)
    360     {
    361         fprintf(stderr,"table too large (decrease the number of bits or use a 64-bit compiler)");
    362         exit(1);
    363     }
    364     g_table_size = (1 << table_bits);
    365     g_table_size_mask = g_table_size - 1;
    366 }
    367 
    368335inline unsigned int BitStreamHashTable::getIndex(const int hashvalue)
    369336{
    370     return hashvalue & g_table_size_mask;
     337    return hashvalue & TABLE_SIZE_MASK;
    371338}
    372339
     
    388355void BitStreamHashTable::Print_Symbol_Table_Distribution()
    389356{
    390 //    fprintf (stderr, "Table size: %i\n", g_table_size);
    391     for(int hash = 0; hash < g_table_size; hash++)
     357    for(int hash = 0; hash < TABLE_SIZE; hash++)
    392358    {
    393359        int items = 0;
     
    403369}
    404370
     371void BitStreamHashTable::free_chain(CHAIN* chain)
     372{
     373    if (chain == NULL)
     374    {
     375        return;
     376    }
     377
     378    if (chain->next != NULL)
     379    {
     380        free_chain(chain->next);
     381    }
     382    free(chain);
     383    chain = NULL;
     384}
     385
    405386#endif // BITSTREAM_HASH_TABLE_H
Note: See TracChangeset for help on using the changeset viewer.