Changeset 1653
- Timestamp:
- Nov 2, 2011, 8:34:40 PM (6 years ago)
- Location:
- trunk/symtab
- Files:
-
- 3 added
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/symtab/bitstream_div_hash_table.h
r1518 r1653 18 18 19 19 #include <stdlib.h> 20 #include "bitstream_hash_table.h"21 20 #include "pbgs_utilities.h" 22 #include "ls_symbol_table_util.h" 23 #include "limits.h" 21 #include "bitstream_super_hash_table.h" 22 #include "pbgs_hash_functions.h" 23 #include "bitstream_id_hash_table.h" 24 #undef BitStreamHashTableImpl 25 #define BitStreamHashTableImpl BitStreamDivHashTable 24 26 25 class BitStreamDivHashTable : public BitStreamHashTable 27 // Use L = 17 to indicate a group for symbols with length > 16 28 // if L in [1,16], L should be an even number. 29 template <int L> 30 class BitStreamDivHashTable : public BitStreamSuperHashTable 26 31 { 27 32 public: 28 33 29 //Returns 0 upon failure 30 // Symbol L in [1,16] and L should be an even number. 34 BitStreamDivHashTable() {}; 35 ~BitStreamDivHashTable() {}; 36 37 // Returns 0 upon failure 38 // Symbol L in [1,16] 31 39 // Use this method to do _first_ symbol lookup: _before_ checking if the last 32 40 // character is a delimiter 33 template <int L>inline unsigned int Lookup_Name(char * name, const int hashvalue);41 inline unsigned int Lookup_Name(char * name, const int hashvalue); 34 42 35 // Symbol L in [1,16] and L should be an _odd_ number.43 // Symbol L in [1,16] 36 44 // Use this method to do _second_ symbol lookup: _after_ checking if the last 37 45 // character is a delimiter 38 template <int L> inline unsigned int Lookup_Name_Delimiter(char * name, const int hashvalue); 46 inline unsigned int Lookup_Name_Odd(char * name, const int hashvalue); 47 48 // Symbol length > 16 49 unsigned int Lookup_Name_17(char * name, const int hashvalue, int length); 50 51 // Use this method for identity and div2 grouping, L <= 16 52 void Insert_Name(const char * name, const int hashvalue, const unsigned int gid); 53 54 // Use this method for arbitrary length. 55 void Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth); 56 57 // Use this method for identity and div2 grouping, L <= 16 58 inline void Insert_Name_Odd_Symbol(const char * name, const int hashvalue, const unsigned int gid); 59 60 protected: 61 // Use this for L in [1,16] 62 inline unsigned int getBucket(const char* name, const int hashvalue, unsigned int tableSize); 63 64 // Use this for L > 16 65 inline unsigned int getBucket(const int hashvalue, unsigned int tableSize, unsigned int length); 66 67 private: 68 void expandHashTable(); 69 BitStreamIdentityHashTable<L-1> m_oddSymbolTable; 39 70 }; 40 71 72 // L in [1,16] 41 73 template <int L> 42 inline unsigned int BitStreamDivHashTable ::Lookup_Name(char * name, const int hashvalue)74 inline unsigned int BitStreamDivHashTable<L>::Lookup_Name(char * name, const int hashvalue) 43 75 { 44 unsigned int bucket = getBucket( hashvalue, g_tableSize);76 unsigned int bucket = getBucket(name, hashvalue, m_tableSize); 45 77 46 78 // Look up the value in the chain 47 for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {79 for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) { 48 80 #if DEBUG_BHT 49 81 printf ("Check symbol: %s\n", chain->key); … … 64 96 } 65 97 66 // L i s odd98 // L in [1,16] 67 99 template <int L> 68 inline unsigned int BitStreamDivHashTable ::Lookup_Name_Delimiter(char * name, const int hashvalue)100 inline unsigned int BitStreamDivHashTable<L>::Lookup_Name_Odd(char * name, const int hashvalue) 69 101 { 70 unsigned int bucket = getBucket(hashvalue, g_tableSize); 71 72 // Look up the value in the chain 73 for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) { 74 #if DEBUG_BHT 75 printf ("Check key: %s\n", chain->key); 76 #endif 77 if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) ) 78 { 79 #if DEBUG_BHT 80 printf ("Found GID: %i\n", chain->GID); 81 #endif 82 return chain->GID; 83 } 84 } 85 86 // Flip the last bit of the hash value 87 unsigned int newBucket = getBucket(flipBit<L+1>(hashvalue), g_tableSize); 88 89 #if DEBUG_BHT 90 print_general_register_32 ("hash", hashvalue); 91 print_general_register_32 ("flipped hash", flipBit<L+1>(hashvalue)); 92 printf ("\n"); 93 #endif 94 // FIXME: Should we check? 95 if (bucket == newBucket) 96 { 97 return 0; 98 } 99 100 // Look up the value in the chain 101 for(CHAIN* chain = g_table[newBucket]; chain != NULL; chain = chain->next) { 102 #if DEBUG_BHT 103 printf ("Check key: %s\n", chain->key); 104 #endif 105 if( div_equal_compare <L> ((unsigned char*)chain->key, (unsigned char*)name) ) 106 { 107 #if DEBUG_BHT 108 printf ("Found GID: %i\n", chain->GID); 109 #endif 110 return chain->GID; 111 } 112 } 113 114 #if DEBUG_BHT 115 printf ("Not Found GID: %i\n", 0); 116 #endif 117 return 0; 102 return m_oddSymbolTable.Lookup_Name(name, hashvalue); 118 103 } 119 104 105 //Use this method for L in [1,16], name has odd length 106 template <int L> 107 void BitStreamDivHashTable<L>::Insert_Name_Odd_Symbol(const char * name, const int hashvalue, const unsigned int gid) 108 { 109 m_oddSymbolTable.Insert_Name(name, hashvalue, gid); 110 } 111 112 #include "bitstream_hash_table_impl.h" 113 120 114 #endif // BITSTREAM_DIV_HASH_TABLE_H -
trunk/symtab/bitstream_id_hash_table.h
r1518 r1653 13 13 #ifndef BITSTREAM_ID_HASH_TABLE_H 14 14 #define BITSTREAM_ID_HASH_TABLE_H 15 #define USE_IDENTITY_SORT 15 #include "pbgs_utilities.h" 16 #include "pbgs_hash_functions.h" 17 #include "bitstream_super_hash_table.h" 18 #undef BitStreamHashTableImpl 19 #define BitStreamHashTableImpl BitStreamIdentityHashTable 16 20 17 # include "bitstream_hash_table.h"18 #include "pbgs_utilities.h" 19 20 class BitStreamIdentityHashTable : public BitStream HashTable21 #define DEBUG_BHT 0 22 // Use L = 17 to indicate a group for symbols with length > 16 23 template <int L> 24 class BitStreamIdentityHashTable : public BitStreamSuperHashTable 21 25 { 22 26 public: … … 24 28 //Returns 0 upon failure 25 29 // Symbol length [1,16] 26 template <int L> inline unsigned int Lookup_Name(char * name, const int hashvalue); 30 inline unsigned int Lookup_Name(char * name, const int hashvalue); 31 32 // Symbol length > 16 33 unsigned int Lookup_Name_17(char * name, const int hashvalue, int length); 34 35 // Use this method for identity and div2 grouping, L <= 16 36 void Insert_Name(const char * name, const int hashvalue, const unsigned int gid); 37 38 // Use this method for arbitrary length. 39 void Insert_Name(const char * name, const int hashvalue, const unsigned int gid, const unsigned int lgth); 40 41 protected: 42 // Use this for L in [1,16] 43 inline unsigned int getBucket(const char* name, const int hashvalue, unsigned int tableSize); 44 45 // Use this for L > 16 46 inline unsigned int getBucket(const int hashvalue, unsigned int tableSize, unsigned int length); 47 48 private: 49 void expandHashTable(); 27 50 }; 28 51 29 52 template <int L> 30 unsigned int BitStreamIdentityHashTable::Lookup_Name(char * name, const int hashvalue)53 unsigned int BitStreamIdentityHashTable<L>::Lookup_Name(char * name, const int hashvalue) 31 54 { 32 unsigned int bucket = getBucket( hashvalue, g_tableSize);55 unsigned int bucket = getBucket(name, hashvalue, m_tableSize); 33 56 34 57 // Look up the value in the chain 35 for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) {58 for(CHAIN* chain = m_table[bucket]; chain != NULL; chain = chain->next) { 36 59 #if DEBUG_BHT 37 60 printf ("Check symbol: %s\n", chain->key); … … 40 63 { 41 64 #if DEBUG_BHT 42 printf (" Found GID: %i\n", chain->GID);65 printf ("%s%i Found GID: %i\n", __FUNCTION__, L, chain->GID); 43 66 #endif 44 67 return chain->GID; … … 47 70 48 71 #if DEBUG_BHT 49 printf (" Not Found GID: %i\n",0);72 printf ("%s%i Not Found GID: %i\n", __FUNCTION__, L, 0); 50 73 #endif 51 74 52 75 return 0; 53 76 } 77 78 #include "bitstream_hash_table_impl.h" 54 79 #endif // BITSTREAM_ID_HASH_TABLE_H -
trunk/symtab/bitstream_log_hash_table.h
r1518 r1653 44 44 inline unsigned int BitStreamLogHashTable::Lookup_Name_1(char * name, const int hashvalue) 45 45 { 46 unsigned int bucket = getBucket(hashvalue, g_tableSize); 46 unsigned int bucket = getBucket(hashvalue, m_tableSize); 47 unsigned int chainlgth = m_table->size(bucket); 47 48 48 49 // Look up the value in the chain 49 for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) { 50 for(unsigned int i = 0; i < chainlgth; i++) { 51 CHAIN chain = m_table->get(bucket, i); 50 52 #if DEBUG_BHT 51 printf ("Check symbol: %s\n", chain ->key);53 printf ("Check symbol: %s\n", chain.key); 52 54 #endif 53 if( log_equal_compare_1 ((unsigned char*)chain ->key, (unsigned char*)name) )55 if( log_equal_compare_1 ((unsigned char*)chain.key, (unsigned char*)name) ) 54 56 { 55 57 #if DEBUG_BHT 56 printf ("Found GID: %i\n", chain ->GID);58 printf ("Found GID: %i\n", chain.GID); 57 59 #endif 58 return chain ->GID;60 return chain.GID; 59 61 } 60 62 } … … 68 70 inline unsigned int BitStreamLogHashTable::Lookup_Name_2(char * name, const int hashvalue) 69 71 { 70 unsigned int bucket = getBucket(hashvalue, g_tableSize); 72 unsigned int bucket = getBucket(hashvalue, m_tableSize); 73 unsigned int chainlgth = m_table->size(bucket); 71 74 72 75 // Look up the value in the chain 73 for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) { 76 for(unsigned int i = 0; i < chainlgth; i++) { 77 CHAIN chain = m_table->get(bucket, i); 74 78 #if DEBUG_BHT 75 printf ("Check symbol: %s\n", chain ->key);79 printf ("Check symbol: %s\n", chain.key); 76 80 #endif 77 if( log_equal_compare_2 ((unsigned char*)chain ->key, (unsigned char*)name) )81 if( log_equal_compare_2 ((unsigned char*)chain.key, (unsigned char*)name) ) 78 82 { 79 83 #if DEBUG_BHT 80 printf ("Found GID: %i\n", chain ->GID);84 printf ("Found GID: %i\n", chain.GID); 81 85 #endif 82 return chain ->GID;86 return chain.GID; 83 87 } 84 88 } … … 93 97 inline unsigned int BitStreamLogHashTable::Lookup_Name_4(char * name, const int hashvalue, int L) 94 98 { 95 unsigned int bucket = getBucket(hashvalue, g_tableSize); 99 unsigned int bucket = getBucket(hashvalue, m_tableSize); 100 unsigned int chainlgth = m_table->size(bucket); 96 101 97 102 // Look up the value in the chain 98 for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) { 103 for(unsigned int i = 0; i < chainlgth; i++) { 104 CHAIN chain = m_table->get(bucket, i); 99 105 #if DEBUG_BHT 100 printf ("Check symbol: %s\n", chain ->key);106 printf ("Check symbol: %s\n", chain.key); 101 107 #endif 102 108 103 109 #ifdef USE_MASK_COMPARE 104 if( log_equal_compare_4 ((unsigned char*)chain ->key, (unsigned char*)name, L) )110 if( log_equal_compare_4 ((unsigned char*)chain.key, (unsigned char*)name, L) ) 105 111 { 106 112 #else 107 if( overlap_compare<uint16_t>((unsigned char*)chain ->key, (unsigned char*)name, chain->lgth, L) )113 if( overlap_compare<uint16_t>((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) ) 108 114 { 109 115 #endif 110 116 #if DEBUG_BHT 111 printf ("Found GID: %i\n", chain ->GID);117 printf ("Found GID: %i\n", chain.GID); 112 118 #endif 113 return chain ->GID;119 return chain.GID; 114 120 } 115 121 } … … 124 130 inline unsigned int BitStreamLogHashTable::Lookup_Name_8(char * name, const int hashvalue, int L) 125 131 { 126 unsigned int bucket = getBucket(hashvalue, g_tableSize); 132 unsigned int bucket = getBucket(hashvalue, m_tableSize); 133 unsigned int chainlgth = m_table->size(bucket); 127 134 128 135 // Look up the value in the chain 129 for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) { 136 for(unsigned int i = 0; i < chainlgth; i++) { 137 CHAIN chain = m_table->get(bucket, i); 130 138 #if DEBUG_BHT 131 printf ("Check symbol: %s\n", chain ->key);139 printf ("Check symbol: %s\n", chain.key); 132 140 #endif 133 if( overlap_compare<uint32_t> ((unsigned char*)chain ->key, (unsigned char*)name, chain->lgth, L) )141 if( overlap_compare<uint32_t> ((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) ) 134 142 { 135 143 #if DEBUG_BHT 136 printf ("Found GID: %i\n", chain ->GID);144 printf ("Found GID: %i\n", chain.GID); 137 145 #endif 138 return chain ->GID;146 return chain.GID; 139 147 } 140 148 } … … 149 157 inline unsigned int BitStreamLogHashTable::Lookup_Name_16(char * name, const int hashvalue, int L) 150 158 { 151 unsigned int bucket = getBucket(hashvalue, g_tableSize); 159 unsigned int bucket = getBucket(hashvalue, m_tableSize); 160 unsigned int chainlgth = m_table->size(bucket); 152 161 153 162 // Look up the value in the chain 154 for(CHAIN* chain = g_table[bucket]; chain != NULL; chain = chain->next) { 163 for(unsigned int i = 0; i < chainlgth; i++) { 164 CHAIN chain = m_table->get(bucket, i); 155 165 #if DEBUG_BHT 156 printf ("Check symbol: %s\n", chain ->key);166 printf ("Check symbol: %s\n", chain.key); 157 167 #endif 158 if( overlap_compare<uint64_t> ((unsigned char*)chain ->key, (unsigned char*)name, chain->lgth, L) )168 if( overlap_compare<uint64_t> ((unsigned char*)chain.key, (unsigned char*)name, chain.lgth, L) ) 159 169 { 160 170 #if DEBUG_BHT 161 printf ("Found GID: %i\n", chain ->GID);171 printf ("Found GID: %i\n", chain.GID); 162 172 #endif 163 return chain ->GID;173 return chain.GID; 164 174 } 165 175 } -
trunk/symtab/pbgs_div_symbol_table.h
r1517 r1653 23 23 #define USE_FUNCTION_TEMPLATES 24 24 #include "stringpool.h" 25 #include "bitstream_super_hash_table.h" 25 26 #include "bitstream_div_hash_table.h" 26 27 #include "ls_symbol_table_compare.h" … … 37 38 { 38 39 public: 39 PBGSDivSymbolTable() 40 :m_globalNameCount(1) 41 {}; 40 PBGSDivSymbolTable(); 41 ~PBGSDivSymbolTable(); 42 42 43 43 template <int L> inline int Lookup_or_Insert_Name(char* name, int hashvalue); … … 51 51 private: 52 52 StringPool <4096,100> m_pool; 53 BitStream DivHashTablem_hashTable[TOTAL_GROUPS];53 BitStreamSuperHashTable* m_hashTable[TOTAL_GROUPS]; 54 54 int m_globalNameCount; 55 55 56 inline int get HashTableIndex(int L);56 inline int getGroup(int L); 57 57 inline bool isDelimiter(const char c); 58 59 template <int L> inline char* Store_Name(const char* name); 58 60 }; 59 61 62 PBGSDivSymbolTable::PBGSDivSymbolTable() 63 :m_globalNameCount(1) 64 { 65 m_hashTable[1] = new BitStreamDivHashTable<2>(); 66 m_hashTable[2] = new BitStreamDivHashTable<4>(); 67 m_hashTable[3] = new BitStreamDivHashTable<6>(); 68 m_hashTable[4] = new BitStreamDivHashTable<8>(); 69 m_hashTable[5] = new BitStreamDivHashTable<10>(); 70 m_hashTable[6] = new BitStreamDivHashTable<12>(); 71 m_hashTable[7] = new BitStreamDivHashTable<14>(); 72 m_hashTable[8] = new BitStreamDivHashTable<16>(); 73 m_hashTable[9] = new BitStreamDivHashTable<17>(); 74 }; 75 76 PBGSDivSymbolTable::~PBGSDivSymbolTable() 77 { 78 for (int i = 1; i < TOTAL_GROUPS; i ++) 79 { 80 delete m_hashTable[i]; 81 m_hashTable[i] = NULL; 82 } 83 } 84 85 template <> inline char* PBGSDivSymbolTable::Store_Name<3>(const char* name) 86 { 87 return m_pool.Insert(name, 3, 1); 88 } 89 90 template <> inline char* PBGSDivSymbolTable::Store_Name<5>(const char* name) 91 { 92 return m_pool.Insert(name, 5, 3); 93 } 94 95 template <> inline char* PBGSDivSymbolTable::Store_Name<6>(const char* name) 96 { 97 return m_pool.Insert(name, 6, 2); 98 } 99 100 template <> inline char* PBGSDivSymbolTable::Store_Name<7>(const char* name) 101 { 102 return m_pool.Insert(name, 7, 1); 103 } 104 105 template <int L> inline char* PBGSDivSymbolTable::Store_Name(const char* name) 106 { 107 return m_pool.Insert(name, L); 108 } 109 60 110 // L should be an even number, L is in [1,16] 61 template <int L> inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue) 111 template <int L> 112 inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue) 62 113 { 63 114 int GID = 0; 64 int group = get HashTableIndex(L);115 int group = getGroup(L); 65 116 66 117 //Lookup 67 GID = m_hashTable[group].Lookup_Name<L>(name, hashvalue);118 GID = ((BitStreamDivHashTable<L>*)m_hashTable[group])->Lookup_Name(name, hashvalue); 68 119 69 120 if (!GID) //symbol not found 70 121 { 122 // Store the symbol 123 char* c = Store_Name<L>(name); 124 71 125 //Check if the last character is a delimiter 72 126 if (isDelimiter(name[L-1])) 73 127 { 74 128 //Do another lookup for name with L = L-1 75 GID = m_hashTable[group].Lookup_Name_Delimiter<L-1>(name, hashvalue);76 77 if ( GID)129 GID = ((BitStreamDivHashTable<L>*)m_hashTable[group])->Lookup_Name_Odd(name, hashvalue); 130 131 if (!GID) 78 132 { 79 //Symbol found, return immediately 80 return GID; 133 //Symbol is not found in odd table 134 GID = m_globalNameCount; 135 m_globalNameCount++; 136 137 // Store symbol for odd length. We need to do this because the symbol-key comparison 138 // in the hash table does not mask out characters. 139 char* oddSymbol = Store_Name<L-1>(name); 140 141 // Insert into odd table 142 ((BitStreamDivHashTable<L>*)m_hashTable[group])->Insert_Name_Odd_Symbol(oddSymbol, hashvalue, GID); 81 143 } 82 144 } 83 84 //Insert 85 char* c = m_pool.Insert(name, L); 86 GID = m_globalNameCount; 87 88 m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount); 89 m_globalNameCount++; 145 else 146 { 147 //even length symbol 148 GID = m_globalNameCount; 149 m_globalNameCount++; 150 } 151 152 //Insert into even table 153 ((BitStreamDivHashTable<L>*)m_hashTable[group])->Insert_Name(c, hashvalue, GID); 90 154 } 91 155 #if DEBUG_PBGS_DIV … … 100 164 101 165 // Use this function for L > 16 102 inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)166 inline int PBGSDivSymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int lgth) 103 167 { 104 168 int GID = 0; … … 107 171 cout << "Lookup or Insert: " << name << endl; 108 172 #endif 109 int group = getHashTableIndex(L);110 173 111 174 //Lookup 112 GID = m_hashTable[group].Lookup_Name_17(name, hashvalue,L);175 GID = ((BitStreamDivHashTable<17>*)m_hashTable[LAST_GROUP])->Lookup_Name_17(name, hashvalue, lgth); 113 176 114 177 //Insert 115 178 if (!GID) //symbol not found 116 179 { 117 char* c = m_pool.Insert(name, L);180 char* c = m_pool.Insert(name, lgth); 118 181 GID = m_globalNameCount; 119 182 120 m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);183 ((BitStreamDivHashTable<17>*)m_hashTable[LAST_GROUP])->Insert_Name(c, hashvalue, m_globalNameCount, lgth); 121 184 m_globalNameCount++; 122 185 } … … 130 193 } 131 194 132 inline int PBGSDivSymbolTable::get HashTableIndex(int L)195 inline int PBGSDivSymbolTable::getGroup(int L) 133 196 { 134 197 if (L > 16) … … 140 203 void PBGSDivSymbolTable::Print_Symbol_Table_Distribution() 141 204 { 142 for (int i = 0; i < TOTAL_GROUPS; i++)205 for (int i = 1; i < TOTAL_GROUPS; i ++) 143 206 { 144 207 fprintf (stderr, "Group #%i\n", i ); 145 m_hashTable[i].Print_Symbol_Table_Distribution(); 146 } 208 m_hashTable[i]->Print_Symbol_Table_Distribution(); 209 } 210 147 211 } 148 212 #endif // PBGS_DIV_SYMBOL_TABLE_H -
trunk/symtab/pbgs_identity_symbol_table.h
r1517 r1653 20 20 #define USE_FUNCTION_TEMPLATES 21 21 #include "stringpool.h" 22 #include "bitstream_super_hash_table.h" 22 23 #include "bitstream_id_hash_table.h" 23 24 #include "ls_symbol_table_compare.h" … … 32 33 { 33 34 public: 34 PBGSIdentitySymbolTable() 35 :m_globalNameCount(1) 36 {}; 35 PBGSIdentitySymbolTable(); 36 ~PBGSIdentitySymbolTable(); 37 37 38 38 // Use this function for 1 <= L <= 16 … … 46 46 private: 47 47 StringPool <4096,100> m_pool; 48 BitStream IdentityHashTablem_hashTable[TOTAL_GROUPS];48 BitStreamSuperHashTable* m_hashTable[TOTAL_GROUPS]; 49 49 50 inline int get HashTableIndex(int L);50 inline int getGroup(int L); 51 51 int m_globalNameCount; 52 53 template <int L> inline char* Store_Name(const char* name); 52 54 }; 53 55 54 template <> 55 inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<3>(char* name, int hashvalue) 56 PBGSIdentitySymbolTable::PBGSIdentitySymbolTable() 57 :m_globalNameCount(1) 58 { 59 m_hashTable[1] = new BitStreamIdentityHashTable<1>(); 60 m_hashTable[2] = new BitStreamIdentityHashTable<2>(); 61 m_hashTable[3] = new BitStreamIdentityHashTable<3>(); 62 m_hashTable[4] = new BitStreamIdentityHashTable<4>(); 63 m_hashTable[5] = new BitStreamIdentityHashTable<5>(); 64 m_hashTable[6] = new BitStreamIdentityHashTable<6>(); 65 m_hashTable[7] = new BitStreamIdentityHashTable<7>(); 66 m_hashTable[8] = new BitStreamIdentityHashTable<8>(); 67 m_hashTable[9] = new BitStreamIdentityHashTable<9>(); 68 m_hashTable[10] = new BitStreamIdentityHashTable<10>(); 69 m_hashTable[11] = new BitStreamIdentityHashTable<11>(); 70 m_hashTable[12] = new BitStreamIdentityHashTable<12>(); 71 m_hashTable[13] = new BitStreamIdentityHashTable<13>(); 72 m_hashTable[14] = new BitStreamIdentityHashTable<14>(); 73 m_hashTable[15] = new BitStreamIdentityHashTable<15>(); 74 m_hashTable[16] = new BitStreamIdentityHashTable<16>(); 75 m_hashTable[17] = new BitStreamIdentityHashTable<17>(); 76 }; 77 78 PBGSIdentitySymbolTable::~PBGSIdentitySymbolTable() 79 { 80 for (int i = 1; i < TOTAL_GROUPS; i ++) 81 { 82 delete m_hashTable[i]; 83 m_hashTable[i] = NULL; 84 } 85 } 86 87 template <> inline char* PBGSIdentitySymbolTable::Store_Name<3>(const char* name) 88 { 89 return m_pool.Insert(name, 3, 1); 90 } 91 92 template <> inline char* PBGSIdentitySymbolTable::Store_Name<5>(const char* name) 93 { 94 return m_pool.Insert(name, 5, 3); 95 } 96 97 template <> inline char* PBGSIdentitySymbolTable::Store_Name<6>(const char* name) 98 { 99 return m_pool.Insert(name, 6, 2); 100 } 101 102 template <> inline char* PBGSIdentitySymbolTable::Store_Name<7>(const char* name) 103 { 104 return m_pool.Insert(name, 7, 1); 105 } 106 107 template <int L> inline char* PBGSIdentitySymbolTable::Store_Name(const char* name) 108 { 109 return m_pool.Insert(name, L); 110 } 111 112 // Use this function for 1 <= L <= 16 113 template <int L> inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue) 56 114 { 57 115 int GID = 0; 58 int group = get HashTableIndex(3);116 int group = getGroup(L); 59 117 60 118 //Lookup 61 GID = m_hashTable[group].Lookup_Name<3>(name, hashvalue);119 GID = ((BitStreamIdentityHashTable<L>*)m_hashTable[group])->Lookup_Name(name, hashvalue); 62 120 63 121 //Insert 64 122 if (!GID) //symbol not found 65 123 { 66 char* c = m_pool.Insert(name, 3, 1);124 char* c = Store_Name<L>(name); 67 125 GID = m_globalNameCount; 68 126 69 m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount); 70 m_globalNameCount++; 71 } 72 #if DEBUG_PBGS 73 int advance = 1; 74 int L = 3; 75 char delim = name[L]; 76 name[L] = '\0'; 77 cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl; 78 name[L] = delim; 79 #endif 80 81 return GID; 82 } 83 84 template <> 85 inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<5>(char* name, int hashvalue) 86 { 87 int GID = 0; 88 int group = getHashTableIndex(5); 89 90 //Lookup 91 GID = m_hashTable[group].Lookup_Name<5>(name, hashvalue); 92 93 //Insert 94 if (!GID) //symbol not found 95 { 96 char* c = m_pool.Insert(name, 5, 3); 97 GID = m_globalNameCount; 98 99 m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount); 100 m_globalNameCount++; 101 } 102 #if DEBUG_PBGS 103 int advance = 3; 104 int L = 5; 105 char delim = name[L]; 106 name[L] = '\0'; 107 cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl; 108 name[L] = delim; 109 #endif 110 111 return GID; 112 } 113 114 template <> 115 inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<6>(char* name, int hashvalue) 116 { 117 int GID = 0; 118 int group = getHashTableIndex(6); 119 120 //Lookup 121 GID = m_hashTable[group].Lookup_Name<6>(name, hashvalue); 122 123 //Insert 124 if (!GID) //symbol not found 125 { 126 char* c = m_pool.Insert(name, 6, 2); 127 GID = m_globalNameCount; 128 129 m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount); 130 m_globalNameCount++; 131 } 132 #if DEBUG_PBGS 133 int advance = 2; 134 int L = 6; 135 char delim = name[L]; 136 name[L] = '\0'; 137 cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl; 138 name[L] = delim; 139 #endif 140 141 return GID; 142 } 143 144 template <> 145 inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name<7>(char* name, int hashvalue) 146 { 147 int GID = 0; 148 int group = getHashTableIndex(7); 149 150 //Lookup 151 GID = m_hashTable[group].Lookup_Name<7>(name, hashvalue); 152 153 //Insert 154 if (!GID) //symbol not found 155 { 156 char* c = m_pool.Insert(name, 7, 1); 157 GID = m_globalNameCount; 158 159 m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount); 160 m_globalNameCount++; 161 } 162 #if DEBUG_PBGS 163 int advance = 1; 164 int L = 7; 165 char delim = name[L]; 166 name[L] = '\0'; 167 cout << "Lookup or Insert: " << name << " | lgth: " << L << " | group: " << group << " | advance: " << advance << endl; 168 name[L] = delim; 169 #endif 170 171 return GID; 172 } 173 174 // Use this function for 1,2, 4, 8 <= L <= 32 175 template <int L> inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue) 176 { 177 int GID = 0; 178 int group = getHashTableIndex(L); 179 180 //Lookup 181 GID = m_hashTable[group].Lookup_Name<L>(name, hashvalue); 182 183 //Insert 184 if (!GID) //symbol not found 185 { 186 char* c = m_pool.Insert(name, L); 187 GID = m_globalNameCount; 188 189 m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount); 127 ((BitStreamIdentityHashTable<L>*)m_hashTable[group])->Insert_Name(c, hashvalue, m_globalNameCount); 190 128 m_globalNameCount++; 191 129 } … … 201 139 202 140 // Use this function for L > 16 203 inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int L)141 inline int PBGSIdentitySymbolTable::Lookup_or_Insert_Name(char* name, int hashvalue, int lgth) 204 142 { 205 143 int GID = 0; … … 208 146 cout << "Lookup or Insert: " << name << endl; 209 147 #endif 210 int group = getHashTableIndex(L);211 148 212 149 //Lookup 213 GID = m_hashTable[group].Lookup_Name_17(name, hashvalue, L);150 GID = ((BitStreamIdentityHashTable<17>*)m_hashTable[LAST_GROUP])->Lookup_Name_17(name, hashvalue, lgth); 214 151 215 152 //Insert 216 153 if (!GID) //symbol not found 217 154 { 218 char* c = m_pool.Insert(name, L);155 char* c = m_pool.Insert(name, lgth); 219 156 GID = m_globalNameCount; 220 157 221 m_hashTable[group].Insert_Name(c, hashvalue, m_globalNameCount);158 ((BitStreamIdentityHashTable<17>*)m_hashTable[LAST_GROUP])->Insert_Name(c, hashvalue, m_globalNameCount, lgth); 222 159 m_globalNameCount++; 223 160 } … … 225 162 } 226 163 227 inline int PBGSIdentitySymbolTable::get HashTableIndex(int L)164 inline int PBGSIdentitySymbolTable::getGroup(int L) 228 165 { 229 166 if (L > 16) … … 235 172 void PBGSIdentitySymbolTable::Print_Symbol_Table_Distribution() 236 173 { 237 for (int i = 0; i < TOTAL_GROUPS; i++)174 for (int i = 1; i < TOTAL_GROUPS; i ++) 238 175 { 239 240 m_hashTable[i].Print_Symbol_Table_Distribution();176 fprintf (stderr, "Group #%i\n", i ); 177 m_hashTable[i]->Print_Symbol_Table_Distribution(); 241 178 } 179 242 180 } 243 181 #endif // PBGS_LENGTH_SYMBOL_TABLE_H -
trunk/symtab/pbgs_utilities.h
r1518 r1653 121 121 } 122 122 123 124 //template<> 125 //inline bool div_equal_compare<3>(const unsigned char * key, const unsigned char * symbol) { 126 // return ((* ((uint32_t *) key)) == 127 // ((* ((uint32_t *) symbol)) & (0xFFFFFF << LOW_BYTE_SHIFT))); // s4int32() 128 //} 129 130 //template<> 131 //inline bool div_equal_compare<5>(const unsigned char * key, const unsigned char * symbol) { 132 // return ((* ((uint64_t *) key)) == 133 // ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFULL << (3 * LOW_BYTE_SHIFT)))); // s8int64() 134 //} 135 136 //template<> 137 //inline bool div_equal_compare<6>(const unsigned char * key, const unsigned char * symbol) { 138 // return ((* ((uint64_t *) key)) == 139 // ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFULL << (2 * LOW_BYTE_SHIFT)))); // s8int64() 140 //} 141 142 //template<> 143 //inline bool div_equal_compare<7>(const unsigned char * key, const unsigned char * symbol) { 144 // return ((* ((uint64_t *) key)) == 145 // ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFFFULL << LOW_BYTE_SHIFT))); // s8int64() 146 //} 123 template<> 124 inline bool div_equal_compare<3>(const unsigned char * key, const unsigned char * symbol) { 125 return ((* ((uint32_t *) key)) == 126 ((* ((uint32_t *) symbol)) & (0xFFFFFF << LOW_BYTE_SHIFT))); // s4int32() 127 } 128 129 template<> 130 inline bool div_equal_compare<5>(const unsigned char * key, const unsigned char * symbol) { 131 return ((* ((uint64_t *) key)) == 132 ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFULL << (3 * LOW_BYTE_SHIFT)))); // s8int64() 133 } 134 135 template<> 136 inline bool div_equal_compare<6>(const unsigned char * key, const unsigned char * symbol) { 137 return ((* ((uint64_t *) key)) == 138 ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFULL << (2 * LOW_BYTE_SHIFT)))); // s8int64() 139 } 140 141 template<> 142 inline bool div_equal_compare<7>(const unsigned char * key, const unsigned char * symbol) { 143 return ((* ((uint64_t *) key)) == 144 ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFFFULL << LOW_BYTE_SHIFT))); // s8int64() 145 } 147 146 148 147 … … 190 189 return value ^ 0x8000; 191 190 } 191 192 // Returns a mask for L bits 193 // eg. mask<3> returns 0x7 (0000...00111) 194 template <size_t L> 195 inline unsigned int maskBit() 196 { 197 return ~(~0 << L); 198 } 199 192 200 #endif /* PBGS_DIV_UTILITIES_H_ */
Note: See TracChangeset
for help on using the changeset viewer.