< prev index next >

src/share/vm/libadt/dict.cpp

Print this page
rev 8847 : 8140482: Various minor code improvements (runtime)
Reviewed-by: dholmes, coleenp, sspitsyn, dsamersoff

*** 138,178 **** // in the old table ends up on 1 of two lists in the new table; a hi and a // lo list depending on the value of the bit. void Dict::doubhash(void) { uint oldsize = _size; _size <<= 1; // Double in size ! _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*oldsize, sizeof(bucket)*_size ); ! memset( &_bin[oldsize], 0, oldsize*sizeof(bucket) ); // Rehash things to spread into new table ! for( uint i=0; i < oldsize; i++) { // For complete OLD table do bucket *b = &_bin[i]; // Handy shortcut for _bin[i] ! if( !b->_keyvals ) continue; // Skip empties fast bucket *nb = &_bin[i+oldsize]; // New bucket shortcut uint j = b->_max; // Trim new bucket to nearest power of 2 ! while( j > b->_cnt ) j >>= 1; // above old bucket _cnt ! if( !j ) j = 1; // Handle zero-sized buckets ! nb->_max = j<<1; // Allocate worst case space for key-value pairs ! nb->_keyvals = (void**)_arena->Amalloc_4( sizeof(void *)*nb->_max*2 ); uint nbcnt = 0; ! for( j=0; j<b->_cnt; j++ ) { // Rehash all keys in this bucket ! void *key = b->_keyvals[j+j]; ! if( (_hash( key ) & (_size-1)) != i ) { // Moving to hi bucket? ! nb->_keyvals[nbcnt+nbcnt] = key; ! nb->_keyvals[nbcnt+nbcnt+1] = b->_keyvals[j+j+1]; ! nb->_cnt = nbcnt = nbcnt+1; b->_cnt--; // Remove key/value from lo bucket ! b->_keyvals[j+j ] = b->_keyvals[b->_cnt+b->_cnt ]; ! b->_keyvals[j+j+1] = b->_keyvals[b->_cnt+b->_cnt+1]; ! j--; // Hash compacted element also } } // End of for all key-value pairs in bucket } // End of for all buckets - - } //------------------------------Dict----------------------------------------- // Deep copy a dictionary. Dict::Dict( const Dict &d ) : _size(d._size), _cnt(d._cnt), _hash(d._hash),_cmp(d._cmp), _arena(d._arena) { --- 138,178 ---- // in the old table ends up on 1 of two lists in the new table; a hi and a // lo list depending on the value of the bit. void Dict::doubhash(void) { uint oldsize = _size; _size <<= 1; // Double in size ! _bin = (bucket*)_arena->Arealloc(_bin, sizeof(bucket) * oldsize, sizeof(bucket) * _size); ! memset(&_bin[oldsize], 0, oldsize * sizeof(bucket)); // Rehash things to spread into new table ! for (uint i = 0; i < oldsize; i++) { // For complete OLD table do bucket *b = &_bin[i]; // Handy shortcut for _bin[i] ! if (!b->_keyvals) continue; // Skip empties fast bucket *nb = &_bin[i+oldsize]; // New bucket shortcut uint j = b->_max; // Trim new bucket to nearest power of 2 ! while (j > b->_cnt) { j >>= 1; } // above old bucket _cnt ! if (!j) { j = 1; } // Handle zero-sized buckets ! nb->_max = j << 1; // Allocate worst case space for key-value pairs ! nb->_keyvals = (void**)_arena->Amalloc_4(sizeof(void *) * nb->_max * 2); uint nbcnt = 0; ! for (j = 0; j < b->_cnt; ) { // Rehash all keys in this bucket ! void *key = b->_keyvals[j + j]; ! if ((_hash(key) & (_size-1)) != i) { // Moving to hi bucket? ! nb->_keyvals[nbcnt + nbcnt] = key; ! nb->_keyvals[nbcnt + nbcnt + 1] = b->_keyvals[j + j + 1]; ! nb->_cnt = nbcnt = nbcnt + 1; b->_cnt--; // Remove key/value from lo bucket ! b->_keyvals[j + j] = b->_keyvals[b->_cnt + b->_cnt]; ! b->_keyvals[j + j + 1] = b->_keyvals[b->_cnt + b->_cnt + 1]; ! // Don't increment j, hash compacted element also. ! } else { ! j++; // Iterate. } } // End of for all key-value pairs in bucket } // End of for all buckets } //------------------------------Dict----------------------------------------- // Deep copy a dictionary. Dict::Dict( const Dict &d ) : _size(d._size), _cnt(d._cnt), _hash(d._hash),_cmp(d._cmp), _arena(d._arena) {
< prev index next >