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