source: trunk/symtab/bitstream_hash_table.cpp @ 4004

Last change on this file since 4004 was 1665, checked in by vla24, 8 years ago

SymbolTable?: Update symtab library for dictionary div2 delimiter. Fixed some compile errors for log grouping

File size: 3.6 KB
RevLine 
[1518]1#include <stdlib.h>
2#include <stdio.h>
[1462]3#include "bitstream_hash_table.h"
4#include "pbgs_utilities.h"
5#include "ls_symbol_table_util.h"
6
[1518]7#define MAX_CHAIN 2
8
[1462]9BitStreamHashTable::BitStreamHashTable()
[1665]10    :m_tableSize(DEFAULT_TABLE_SIZE)
[1462]11{
[1665]12    m_table = allocateHashTable(m_tableSize);
[1462]13}
14
15BitStreamHashTable::~BitStreamHashTable()
16{
[1665]17    deallocateHashTable(m_tableSize, m_table);
[1462]18}
19
20// Use this method if L > 16
21unsigned int BitStreamHashTable::Lookup_Name_17(char * name, const int hashvalue, int L)
22{
[1665]23    unsigned int bucket = getBucket(hashvalue, m_tableSize);
[1462]24
25    // Look up the value in the chain
[1665]26    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
27#if DEBUm_BHT
[1462]28        printf ("Check symbol: %s\n", chain->key);
29#endif
30        if( simd_compare ((unsigned char*)chain->key, (unsigned char*)name, L) )
31        {
[1665]32#if DEBUm_BHT
[1462]33            printf ("Found GID: %i\n", chain->GID);
34#endif
35            return chain->GID;
36        }
37    }
38
[1665]39#if DEBUm_BHT
[1462]40    printf ("Not Found GID: %i\n", 0);
41#endif
42    return 0;
43}
44
[1518]45void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid)
[1462]46{
[1665]47    unsigned int bucket = getBucket(hashvalue, m_tableSize);
[1462]48
49    // If it was not found, add it
[1665]50    CHAIN* next = m_table[bucket];
[1518]51    unsigned int chainlgth = chainLength(next);
52    if (chainlgth == MAX_CHAIN)
53    {
54        //current chain length is maximum, expand the table
55        expandHashTable();
[1665]56        bucket = getBucket(hashvalue, m_tableSize);
57        next = m_table[bucket];
[1518]58    }
59    CHAIN* curr = (CHAIN*) malloc(sizeof(CHAIN));
60    curr->next = next;
61    curr->key = name;
62    curr->hashvalue = hashvalue;
63    curr->GID = gid;
[1665]64    m_table[bucket] = curr;
[1462]65
[1665]66#if DEBUm_BHT
67    printf ("Given GID: %i | Stored GID: %i\n", gid, m_table[hash]->GID);
[1462]68#endif
69}
70
[1518]71void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
[1462]72{
[1665]73    unsigned int bucket = getBucket(hashvalue, m_tableSize);
[1462]74
75    // If it was not found, add it
[1665]76    CHAIN* next = m_table[bucket];
[1518]77    unsigned int chainlgth = chainLength(next);
78    if (chainlgth == MAX_CHAIN)
79    {
80        //current chain length is maximum, expand the table
81        expandHashTable();
[1665]82        bucket = getBucket(hashvalue, m_tableSize);
83        next = m_table[bucket];
[1518]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;
[1665]91    m_table[bucket] = curr;
[1462]92
[1665]93#if DEBUm_BHT
94    printf ("Given GID: %i | Stored GID: %i\n", gid, m_table[hash]->GID);
[1462]95#endif
96}
97
[1518]98void BitStreamHashTable::expandHashTable()
[1462]99{
[1518]100    unsigned int tempTableSize = nextTableSize();
101    CHAIN** tempTable = allocateHashTable(tempTableSize);
102
[1665]103    for(unsigned int bucket = 0; bucket < m_tableSize; bucket++)
[1462]104    {
[1665]105        CHAIN* curr = m_table[bucket];
106        m_table[bucket] = NULL;
[1518]107
108        while (curr != NULL)
[1462]109        {
[1518]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;
[1462]120        }
[1518]121    }
122
[1665]123    // Deallocate m_table
124    deallocateHashTable(m_tableSize, m_table);
[1518]125
[1665]126    // Reassign m_table
127    m_table = tempTable;
128    m_tableSize = tempTableSize;
[1518]129}
130
131void BitStreamHashTable::Print_Symbol_Table_Distribution()
132{
[1665]133    for(unsigned int bucket = 0; bucket < m_tableSize; bucket++)
[1518]134    {
[1665]135        int items = chainLength(m_table[bucket]);
[1462]136        if (items >= 1)
137        {
[1518]138            fprintf (stderr, "\tBucket: %i | #items: %i\n", bucket, items);
[1462]139        }
140    }
141}
142
[1518]143void BitStreamHashTable::free_chain(CHAIN* &chain)
[1462]144{
145    if (chain == NULL)
146    {
147        return;
148    }
149    free(chain);
150    chain = NULL;
151}
Note: See TracBrowser for help on using the repository browser.