1 #ifdef USE_PRAGMA_IDENT_SRC 2 #pragma ident "@(#)dict2.cpp 1.19 07/05/05 17:04:59 JVM" 3 #endif 4 /* 5 * Copyright 1998-2002 Sun Microsystems, Inc. All Rights Reserved. 6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 7 * 8 * This code is free software; you can redistribute it and/or modify it 9 * under the terms of the GNU General Public License version 2 only, as 10 * published by the Free Software Foundation. 11 * 12 * This code is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 * version 2 for more details (a copy is included in the LICENSE file that 16 * accompanied this code). 17 * 18 * You should have received a copy of the GNU General Public License version 19 * 2 along with this work; if not, write to the Free Software Foundation, 20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 21 * 22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 23 * CA 95054 USA or visit www.sun.com if you need additional information or 24 * have any questions. 25 * 26 */ 27 28 // Dictionaries - An Abstract Data Type 29 30 #include "adlc.hpp" 31 32 // #include "dict.hpp" 33 34 35 //------------------------------data----------------------------------------- 36 // String hash tables 37 #define MAXID 20 38 static char initflag = 0; // True after 1st initialization 39 static char shft[MAXID] = {1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6}; 40 static short xsum[MAXID + 1]; 41 42 //------------------------------bucket--------------------------------------- 43 class bucket { 44 public: 45 int _cnt, _max; // Size of bucket 46 const void **_keyvals; // Array of keys and values 47 }; 48 49 //------------------------------Dict----------------------------------------- 50 // The dictionary is kept has a hash table. The hash table is a even power 51 // of two, for nice modulo operations. Each bucket in the hash table points 52 // to a linear list of key-value pairs; each key & value is just a (void *). 53 // The list starts with a count. A hash lookup finds the list head, then a 54 // simple linear scan finds the key. If the table gets too full, it's 55 // doubled in size; the total amount of EXTRA times all hash functions are 56 // computed for the doubling is no more than the current size - thus the 57 // doubling in size costs no more than a constant factor in speed. 58 Dict::Dict(CmpKey initcmp, Hash inithash) : _hash(inithash), _cmp(initcmp), _arena(NULL) { 59 init(); 60 } 61 62 Dict::Dict(CmpKey initcmp, Hash inithash, Arena *arena) : _hash(inithash), _cmp(initcmp), _arena(arena) { 63 init(); 64 } 65 66 void Dict::init() { 67 int i; 68 69 // Precompute table of null character hashes 70 if( !initflag ) { // Not initializated yet? 71 xsum[0] = (1<<shft[0])+1; // Initialize 72 for( i = 1; i < MAXID + 1; i++) { 73 xsum[i] = (1<<shft[i])+1+xsum[i-1]; 74 } 75 initflag = 1; // Never again 76 } 77 78 _size = 16; // Size is a power of 2 79 _cnt = 0; // Dictionary is empty 80 _bin = (bucket*)_arena->Amalloc_4(sizeof(bucket)*_size); 81 memset(_bin,0,sizeof(bucket)*_size); 82 } 83 84 //------------------------------~Dict------------------------------------------ 85 // Delete an existing dictionary. 86 Dict::~Dict() { 87 } 88 89 //------------------------------Clear---------------------------------------- 90 // Zap to empty; ready for re-use 91 void Dict::Clear() { 92 _cnt = 0; // Empty contents 93 for( int i=0; i<_size; i++ ) 94 _bin[i]._cnt = 0; // Empty buckets, but leave allocated 95 // Leave _size & _bin alone, under the assumption that dictionary will 96 // grow to this size again. 97 } 98 99 //------------------------------doubhash--------------------------------------- 100 // Double hash table size. If can't do so, just suffer. If can, then run 101 // thru old hash table, moving things to new table. Note that since hash 102 // table doubled, exactly 1 new bit is exposed in the mask - so everything 103 // in the old table ends up on 1 of two lists in the new table; a hi and a 104 // lo list depending on the value of the bit. 105 void Dict::doubhash(void) { 106 int oldsize = _size; 107 _size <<= 1; // Double in size 108 _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*oldsize, sizeof(bucket)*_size ); 109 memset( &_bin[oldsize], 0, oldsize*sizeof(bucket) ); 110 // Rehash things to spread into new table 111 for( int i=0; i < oldsize; i++) { // For complete OLD table do 112 bucket *b = &_bin[i]; // Handy shortcut for _bin[i] 113 if( !b->_keyvals ) continue; // Skip empties fast 114 115 bucket *nb = &_bin[i+oldsize]; // New bucket shortcut 116 int j = b->_max; // Trim new bucket to nearest power of 2 117 while( j > b->_cnt ) j >>= 1; // above old bucket _cnt 118 if( !j ) j = 1; // Handle zero-sized buckets 119 nb->_max = j<<1; 120 // Allocate worst case space for key-value pairs 121 nb->_keyvals = (const void**)_arena->Amalloc_4( sizeof(void *)*nb->_max*2 ); 122 int nbcnt = 0; 123 124 for( j=0; j<b->_cnt; j++ ) { // Rehash all keys in this bucket 125 const void *key = b->_keyvals[j+j]; 126 if( (_hash( key ) & (_size-1)) != i ) { // Moving to hi bucket? 127 nb->_keyvals[nbcnt+nbcnt] = key; 128 nb->_keyvals[nbcnt+nbcnt+1] = b->_keyvals[j+j+1]; 129 nb->_cnt = nbcnt = nbcnt+1; 130 b->_cnt--; // Remove key/value from lo bucket 131 b->_keyvals[j+j ] = b->_keyvals[b->_cnt+b->_cnt ]; 132 b->_keyvals[j+j+1] = b->_keyvals[b->_cnt+b->_cnt+1]; 133 j--; // Hash compacted element also 134 } 135 } // End of for all key-value pairs in bucket 136 } // End of for all buckets 137 138 139 } 140 141 //------------------------------Dict----------------------------------------- 142 // Deep copy a dictionary. 143 Dict::Dict( const Dict &d ) : _size(d._size), _cnt(d._cnt), _hash(d._hash),_cmp(d._cmp), _arena(d._arena) { 144 _bin = (bucket*)_arena->Amalloc_4(sizeof(bucket)*_size); 145 memcpy( _bin, d._bin, sizeof(bucket)*_size ); 146 for( int i=0; i<_size; i++ ) { 147 if( !_bin[i]._keyvals ) continue; 148 _bin[i]._keyvals=(const void**)_arena->Amalloc_4( sizeof(void *)*_bin[i]._max*2); 149 memcpy( _bin[i]._keyvals, d._bin[i]._keyvals,_bin[i]._cnt*2*sizeof(void*)); 150 } 151 } 152 153 //------------------------------Dict----------------------------------------- 154 // Deep copy a dictionary. 155 Dict &Dict::operator =( const Dict &d ) { 156 if( _size < d._size ) { // If must have more buckets 157 _arena = d._arena; 158 _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*_size, sizeof(bucket)*d._size ); 159 memset( &_bin[_size], 0, (d._size-_size)*sizeof(bucket) ); 160 _size = d._size; 161 } 162 for( int i=0; i<_size; i++ ) // All buckets are empty 163 _bin[i]._cnt = 0; // But leave bucket allocations alone 164 _cnt = d._cnt; 165 *(Hash*)(&_hash) = d._hash; 166 *(CmpKey*)(&_cmp) = d._cmp; 167 for(int k=0; k<_size; k++ ) { 168 bucket *b = &d._bin[k]; // Shortcut to source bucket 169 for( int j=0; j<b->_cnt; j++ ) 170 Insert( b->_keyvals[j+j], b->_keyvals[j+j+1] ); 171 } 172 return *this; 173 } 174 175 //------------------------------Insert--------------------------------------- 176 // Insert or replace a key/value pair in the given dictionary. If the 177 // dictionary is too full, it's size is doubled. The prior value being 178 // replaced is returned (NULL if this is a 1st insertion of that key). If 179 // an old value is found, it's swapped with the prior key-value pair on the 180 // list. This moves a commonly searched-for value towards the list head. 181 const void *Dict::Insert(const void *key, const void *val) { 182 int hash = _hash( key ); // Get hash key 183 int i = hash & (_size-1); // Get hash key, corrected for size 184 bucket *b = &_bin[i]; // Handy shortcut 185 for( int j=0; j<b->_cnt; j++ ) 186 if( !_cmp(key,b->_keyvals[j+j]) ) { 187 const void *prior = b->_keyvals[j+j+1]; 188 b->_keyvals[j+j ] = key; // Insert current key-value 189 b->_keyvals[j+j+1] = val; 190 return prior; // Return prior 191 } 192 193 if( ++_cnt > _size ) { // Hash table is full 194 doubhash(); // Grow whole table if too full 195 i = hash & (_size-1); // Rehash 196 b = &_bin[i]; // Handy shortcut 197 } 198 if( b->_cnt == b->_max ) { // Must grow bucket? 199 if( !b->_keyvals ) { 200 b->_max = 2; // Initial bucket size 201 b->_keyvals = (const void**)_arena->Amalloc_4( sizeof(void *)*b->_max*2 ); 202 } else { 203 b->_keyvals = (const void**)_arena->Arealloc( b->_keyvals, sizeof(void *)*b->_max*2, sizeof(void *)*b->_max*4 ); 204 b->_max <<= 1; // Double bucket 205 } 206 } 207 b->_keyvals[b->_cnt+b->_cnt ] = key; 208 b->_keyvals[b->_cnt+b->_cnt+1] = val; 209 b->_cnt++; 210 return NULL; // Nothing found prior 211 } 212 213 //------------------------------Delete--------------------------------------- 214 // Find & remove a value from dictionary. Return old value. 215 const void *Dict::Delete(void *key) { 216 int i = _hash( key ) & (_size-1); // Get hash key, corrected for size 217 bucket *b = &_bin[i]; // Handy shortcut 218 for( int j=0; j<b->_cnt; j++ ) 219 if( !_cmp(key,b->_keyvals[j+j]) ) { 220 const void *prior = b->_keyvals[j+j+1]; 221 b->_cnt--; // Remove key/value from lo bucket 222 b->_keyvals[j+j ] = b->_keyvals[b->_cnt+b->_cnt ]; 223 b->_keyvals[j+j+1] = b->_keyvals[b->_cnt+b->_cnt+1]; 224 _cnt--; // One less thing in table 225 return prior; 226 } 227 return NULL; 228 } 229 230 //------------------------------FindDict------------------------------------- 231 // Find a key-value pair in the given dictionary. If not found, return NULL. 232 // If found, move key-value pair towards head of list. 233 const void *Dict::operator [](const void *key) const { 234 int i = _hash( key ) & (_size-1); // Get hash key, corrected for size 235 bucket *b = &_bin[i]; // Handy shortcut 236 for( int j=0; j<b->_cnt; j++ ) 237 if( !_cmp(key,b->_keyvals[j+j]) ) 238 return b->_keyvals[j+j+1]; 239 return NULL; 240 } 241 242 //------------------------------CmpDict-------------------------------------- 243 // CmpDict compares two dictionaries; they must have the same keys (their 244 // keys must match using CmpKey) and they must have the same values (pointer 245 // comparison). If so 1 is returned, if not 0 is returned. 246 int Dict::operator ==(const Dict &d2) const { 247 if( _cnt != d2._cnt ) return 0; 248 if( _hash != d2._hash ) return 0; 249 if( _cmp != d2._cmp ) return 0; 250 for( int i=0; i < _size; i++) { // For complete hash table do 251 bucket *b = &_bin[i]; // Handy shortcut 252 if( b->_cnt != d2._bin[i]._cnt ) return 0; 253 if( memcmp(b->_keyvals, d2._bin[i]._keyvals, b->_cnt*2*sizeof(void*) ) ) 254 return 0; // Key-value pairs must match 255 } 256 return 1; // All match, is OK 257 } 258 259 260 //------------------------------print---------------------------------------- 261 static void printvoid(const void* x) { printf("%p", x); } 262 void Dict::print() { 263 print(printvoid, printvoid); 264 } 265 void Dict::print(PrintKeyOrValue print_key, PrintKeyOrValue print_value) { 266 for( int i=0; i < _size; i++) { // For complete hash table do 267 bucket *b = &_bin[i]; // Handy shortcut 268 for( int j=0; j<b->_cnt; j++ ) { 269 print_key( b->_keyvals[j+j ]); 270 printf(" -> "); 271 print_value(b->_keyvals[j+j+1]); 272 printf("\n"); 273 } 274 } 275 } 276 277 //------------------------------Hashing Functions---------------------------- 278 // Convert string to hash key. This algorithm implements a universal hash 279 // function with the multipliers frozen (ok, so it's not universal). The 280 // multipliers (and allowable characters) are all odd, so the resultant sum 281 // is odd - guarenteed not divisible by any power of two, so the hash tables 282 // can be any power of two with good results. Also, I choose multipliers 283 // that have only 2 bits set (the low is always set to be odd) so 284 // multiplication requires only shifts and adds. Characters are required to 285 // be in the range 0-127 (I double & add 1 to force oddness). Keys are 286 // limited to MAXID characters in length. Experimental evidence on 150K of 287 // C text shows excellent spreading of values for any size hash table. 288 int hashstr(const void *t) { 289 register char c, k = 0; 290 register int sum = 0; 291 register const char *s = (const char *)t; 292 293 while( ((c = s[k]) != '\0') && (k < MAXID-1) ) { // Get characters till nul 294 c = (c<<1)+1; // Characters are always odd! 295 sum += c + (c<<shft[k++]); // Universal hash function 296 } 297 assert( k < (MAXID + 1), "Exceeded maximum name length"); 298 return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size 299 } 300 301 //------------------------------hashptr-------------------------------------- 302 // Slimey cheap hash function; no guarenteed performance. Better than the 303 // default for pointers, especially on MS-DOS machines. 304 int hashptr(const void *key) { 305 #ifdef __TURBOC__ 306 return (int)((intptr_t)key >> 16); 307 #else // __TURBOC__ 308 return (int)((intptr_t)key >> 2); 309 #endif 310 } 311 312 // Slimey cheap hash function; no guarenteed performance. 313 int hashkey(const void *key) { 314 return (int)((intptr_t)key); 315 } 316 317 //------------------------------Key Comparator Functions--------------------- 318 int cmpstr(const void *k1, const void *k2) { 319 return strcmp((const char *)k1,(const char *)k2); 320 } 321 322 // Slimey cheap key comparator. 323 int cmpkey(const void *key1, const void *key2) { 324 return (int)((intptr_t)key1 - (intptr_t)key2); 325 } 326 327 //============================================================================= 328 //------------------------------reset------------------------------------------ 329 // Create an iterator and initialize the first variables. 330 void DictI::reset( const Dict *dict ) { 331 _d = dict; // The dictionary 332 _i = (int)-1; // Before the first bin 333 _j = 0; // Nothing left in the current bin 334 ++(*this); // Step to first real value 335 } 336 337 //------------------------------next------------------------------------------- 338 // Find the next key-value pair in the dictionary, or return a NULL key and 339 // value. 340 void DictI::operator ++(void) { 341 if( _j-- ) { // Still working in current bin? 342 _key = _d->_bin[_i]._keyvals[_j+_j]; 343 _value = _d->_bin[_i]._keyvals[_j+_j+1]; 344 return; 345 } 346 347 while( ++_i < _d->_size ) { // Else scan for non-zero bucket 348 _j = _d->_bin[_i]._cnt; 349 if( !_j ) continue; 350 _j--; 351 _key = _d->_bin[_i]._keyvals[_j+_j]; 352 _value = _d->_bin[_i]._keyvals[_j+_j+1]; 353 return; 354 } 355 _key = _value = NULL; 356 } 357 358