Ignore:
Timestamp:
Oct 5, 2011, 7:41:38 PM (8 years ago)
Author:
vla24
Message:

SymbolTable?: hash table implementation for paralel bitstream based length sorting (PBGS) now auto-resizes. Fixed flipBit function used by Div2 grouping strategy

File:
1 edited

Legend:

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

    r1462 r1518  
     1#include <stdlib.h>
     2#include <stdio.h>
    13#include "bitstream_hash_table.h"
    2 #include <stdlib.h>
    34#include "pbgs_utilities.h"
    45#include "ls_symbol_table_util.h"
    56
     7#define MAX_CHAIN 2
     8
    69BitStreamHashTable::BitStreamHashTable()
     10    :g_tableSize(DEFAULT_TABLE_SIZE)
    711{
    8     g_table = (CHAIN**) calloc(TABLE_SIZE, sizeof(CHAIN*));
    9     memset(g_table, 0, TABLE_SIZE*sizeof(CHAIN*));
     12    g_table = allocateHashTable(g_tableSize);
    1013}
    1114
    1215BitStreamHashTable::~BitStreamHashTable()
    1316{
    14     for(int hash = 0; hash < TABLE_SIZE; hash++)
    15     {
    16         free_chain(g_table[hash]);
    17     }
    18     free(g_table);
     17    deallocateHashTable(g_tableSize, g_table);
    1918}
    2019
     
    2221unsigned int BitStreamHashTable::Lookup_Name_17(char * name, const int hashvalue, int L)
    2322{
    24     unsigned int hash = getIndex(hashvalue);
     23    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    2524
    2625    // Look up the value in the chain
    27     for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
     26    for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {
    2827#if DEBUG_BHT
    2928        printf ("Check symbol: %s\n", chain->key);
     
    4443}
    4544
    46 void BitStreamHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid)
     45void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid)
    4746{
    48     unsigned int hash = getIndex(hashvalue);
     47    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    4948
    5049    // If it was not found, add it
    51     CHAIN* next = g_table[hash];
    52     g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
    53     g_table[hash]->next = next;
    54     g_table[hash]->key = name;
    55     g_table[hash]->GID = gid;
     50    CHAIN* next = g_table[bucket];
     51    unsigned int chainlgth = chainLength(next);
     52    if (chainlgth == MAX_CHAIN)
     53    {
     54        //current chain length is maximum, expand the table
     55        expandHashTable();
     56        bucket = getBucket(hashvalue, g_tableSize);
     57        next = g_table[bucket];
     58    }
     59    CHAIN* curr = (CHAIN*) malloc(sizeof(CHAIN));
     60    curr->next = next;
     61    curr->key = name;
     62    curr->hashvalue = hashvalue;
     63    curr->GID = gid;
     64    g_table[bucket] = curr;
    5665
    5766#if DEBUG_BHT
     
    6069}
    6170
    62 void BitStreamHashTable::Insert_Name(char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
     71void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
    6372{
    64     unsigned int hash = getIndex(hashvalue);
     73    unsigned int bucket = getBucket(hashvalue, g_tableSize);
    6574
    6675    // If it was not found, add it
    67     CHAIN* next = g_table[hash];
    68     g_table[hash] = (CHAIN*) malloc(sizeof(CHAIN*));
    69     g_table[hash]->next = next;
    70     g_table[hash]->key = name;
    71     g_table[hash]->GID = gid;
    72     g_table[hash]->lgth = lgth;
     76    CHAIN* next = g_table[bucket];
     77    unsigned int chainlgth = chainLength(next);
     78    if (chainlgth == MAX_CHAIN)
     79    {
     80        //current chain length is maximum, expand the table
     81        expandHashTable();
     82        bucket = getBucket(hashvalue, g_tableSize);
     83        next = g_table[bucket];
     84    }
     85    CHAIN* curr = (CHAIN*) malloc(sizeof(CHAIN));
     86    curr->next = next;
     87    curr->key = name;
     88    curr->hashvalue = hashvalue;
     89    curr->GID = gid;
     90    curr->lgth = lgth;
     91    g_table[bucket] = curr;
    7392
    7493#if DEBUG_BHT
     
    7796}
    7897
     98void BitStreamHashTable::expandHashTable()
     99{
     100    unsigned int tempTableSize = nextTableSize();
     101    CHAIN** tempTable = allocateHashTable(tempTableSize);
     102
     103    for(unsigned int bucket = 0; bucket < g_tableSize; bucket++)
     104    {
     105        CHAIN* curr = g_table[bucket];
     106        g_table[bucket] = NULL;
     107
     108        while (curr != NULL)
     109        {
     110            CHAIN* next = curr->next;
     111
     112            //insert to new table
     113            unsigned int tempIndex = getBucket(curr->hashvalue, tempTableSize);
     114            CHAIN* tempNext = tempTable[tempIndex];
     115            curr->next = tempNext;
     116            tempTable[tempIndex] = curr;
     117
     118            //update curr
     119            curr = next;
     120        }
     121    }
     122
     123    // Deallocate g_table
     124    deallocateHashTable(g_tableSize, g_table);
     125
     126    // Reassign g_table
     127    g_table = tempTable;
     128    g_tableSize = tempTableSize;
     129}
     130
    79131void BitStreamHashTable::Print_Symbol_Table_Distribution()
    80132{
    81     for(int hash = 0; hash < TABLE_SIZE; hash++)
     133    for(unsigned int bucket = 0; bucket < g_tableSize; bucket++)
    82134    {
    83         int items = 0;
    84         for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next)
    85         {
    86             items++;
    87         }
     135        int items = chainLength(g_table[bucket]);
    88136        if (items >= 1)
    89137        {
    90             fprintf (stderr, "\tBucket: %i | #items: %i\n", hash, items);
     138            fprintf (stderr, "\tBucket: %i | #items: %i\n", bucket, items);
    91139        }
    92140    }
    93141}
    94142
    95 void BitStreamHashTable::free_chain(CHAIN* chain)
     143void BitStreamHashTable::free_chain(CHAIN* &chain)
    96144{
    97145    if (chain == NULL)
     
    99147        return;
    100148    }
    101 
    102     if (chain->next != NULL)
    103     {
    104         free_chain(chain->next);
    105     }
    106149    free(chain);
    107150    chain = NULL;
Note: See TracChangeset for help on using the changeset viewer.