source: trunk/symtab/bitstream_hash_table.cpp @ 3028

Last change on this file since 3028 was 1665, checked in by vla24, 7 years ago

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

File size: 3.6 KB
Line 
1#include <stdlib.h>
2#include <stdio.h>
3#include "bitstream_hash_table.h"
4#include "pbgs_utilities.h"
5#include "ls_symbol_table_util.h"
6
7#define MAX_CHAIN 2
8
9BitStreamHashTable::BitStreamHashTable()
10    :m_tableSize(DEFAULT_TABLE_SIZE)
11{
12    m_table = allocateHashTable(m_tableSize);
13}
14
15BitStreamHashTable::~BitStreamHashTable()
16{
17    deallocateHashTable(m_tableSize, m_table);
18}
19
20// Use this method if L > 16
21unsigned int BitStreamHashTable::Lookup_Name_17(char * name, const int hashvalue, int L)
22{
23    unsigned int bucket = getBucket(hashvalue, m_tableSize);
24
25    // Look up the value in the chain
26    for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) {
27#if DEBUm_BHT
28        printf ("Check symbol: %s\n", chain->key);
29#endif
30        if( simd_compare ((unsigned char*)chain->key, (unsigned char*)name, L) )
31        {
32#if DEBUm_BHT
33            printf ("Found GID: %i\n", chain->GID);
34#endif
35            return chain->GID;
36        }
37    }
38
39#if DEBUm_BHT
40    printf ("Not Found GID: %i\n", 0);
41#endif
42    return 0;
43}
44
45void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid)
46{
47    unsigned int bucket = getBucket(hashvalue, m_tableSize);
48
49    // If it was not found, add it
50    CHAIN* next = m_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, m_tableSize);
57        next = m_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    m_table[bucket] = curr;
65
66#if DEBUm_BHT
67    printf ("Given GID: %i | Stored GID: %i\n", gid, m_table[hash]->GID);
68#endif
69}
70
71void BitStreamHashTable::Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth)
72{
73    unsigned int bucket = getBucket(hashvalue, m_tableSize);
74
75    // If it was not found, add it
76    CHAIN* next = m_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, m_tableSize);
83        next = m_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    m_table[bucket] = curr;
92
93#if DEBUm_BHT
94    printf ("Given GID: %i | Stored GID: %i\n", gid, m_table[hash]->GID);
95#endif
96}
97
98void BitStreamHashTable::expandHashTable()
99{
100    unsigned int tempTableSize = nextTableSize();
101    CHAIN** tempTable = allocateHashTable(tempTableSize);
102
103    for(unsigned int bucket = 0; bucket < m_tableSize; bucket++)
104    {
105        CHAIN* curr = m_table[bucket];
106        m_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 m_table
124    deallocateHashTable(m_tableSize, m_table);
125
126    // Reassign m_table
127    m_table = tempTable;
128    m_tableSize = tempTableSize;
129}
130
131void BitStreamHashTable::Print_Symbol_Table_Distribution()
132{
133    for(unsigned int bucket = 0; bucket < m_tableSize; bucket++)
134    {
135        int items = chainLength(m_table[bucket]);
136        if (items >= 1)
137        {
138            fprintf (stderr, "\tBucket: %i | #items: %i\n", bucket, items);
139        }
140    }
141}
142
143void BitStreamHashTable::free_chain(CHAIN* &chain)
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.