/* * Copyright (c) 1997, 2021, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. *
*/
//------------------------------bucket--------------------------------------- class bucket : public ResourceObj { public:
uint _cnt, _max; // Size of bucket void** _keyvals; // Array of keys and values
};
//------------------------------Dict----------------------------------------- // The dictionary is kept has a hash table. The hash table is a even power // of two, for nice modulo operations. Each bucket in the hash table points // to a linear list of key-value pairs; each key & value is just a (void *). // The list starts with a count. A hash lookup finds the list head, then a // simple linear scan finds the key. If the table gets too full, it's // doubled in size; the total amount of EXTRA times all hash functions are // computed for the doubling is no more than the current size - thus the // doubling in size costs no more than a constant factor in speed.
Dict::Dict(CmpKey initcmp, Hash inithash) : _arena(Thread::current()->resource_area()),
_hash(inithash), _cmp(initcmp) {
_size = 16; // Size is a power of 2
_cnt = 0; // Dictionary is empty
_bin = (bucket*)_arena->AmallocWords(sizeof(bucket) * _size);
memset((void*)_bin, 0, sizeof(bucket) * _size);
}
Dict::Dict(CmpKey initcmp, Hash inithash, Arena* arena, int size)
: _arena(arena), _hash(inithash), _cmp(initcmp) { // Size is a power of 2
_size = MAX2(16, round_up_power_of_2(size));
// Deep copy into arena of choice
Dict::Dict(const Dict &d, Arena* arena)
: _arena(arena), _size(d._size), _cnt(d._cnt), _hash(d._hash), _cmp(d._cmp) {
_bin = (bucket*)_arena->AmallocWords(sizeof(bucket) * _size);
memcpy((void*)_bin, (void*)d._bin, sizeof(bucket) * _size); for (uint i = 0; i < _size; i++) { if (!_bin[i]._keyvals) { continue;
}
_bin[i]._keyvals = (void**)_arena->AmallocWords(sizeof(void*) * _bin[i]._max * 2);
memcpy(_bin[i]._keyvals, d._bin[i]._keyvals, _bin[i]._cnt * 2 * sizeof(void*));
}
}
//------------------------------~Dict------------------------------------------ // Delete an existing dictionary.
Dict::~Dict() { }
//------------------------------doubhash--------------------------------------- // Double hash table size. If can't do so, just suffer. If can, then run // thru old hash table, moving things to new table. Note that since hash // table doubled, exactly 1 new bit is exposed in the mask - so everything // 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() {
uint oldsize = _size;
_size <<= 1; // Double in size
_bin = (bucket*)_arena->Arealloc(_bin, sizeof(bucket) * oldsize, sizeof(bucket) * _size);
memset((void*)(&_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->AmallocWords(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
}
//------------------------------Insert---------------------------------------- // Insert or replace a key/value pair in the given dictionary. If the // dictionary is too full, it's size is doubled. The prior value being // replaced is returned (NULL if this is a 1st insertion of that key). If // an old value is found, it's swapped with the prior key-value pair on the // list. This moves a commonly searched-for value towards the list head. void*Dict::Insert(void* key, void* val, bool replace) {
uint hash = _hash(key); // Get hash key
uint i = hash & (_size - 1); // Get hash key, corrected for size
bucket* b = &_bin[i]; for (uint j = 0; j < b->_cnt; j++) { if (!_cmp(key, b->_keyvals[j + j])) { if (!replace) { return b->_keyvals[j + j + 1];
} else { void* prior = b->_keyvals[j + j + 1];
b->_keyvals[j + j ] = key;
b->_keyvals[j + j + 1] = val; return prior;
}
}
} if (++_cnt > _size) { // Hash table is full
doubhash(); // Grow whole table if too full
i = hash & (_size - 1); // Rehash
b = &_bin[i];
} if (b->_cnt == b->_max) { // Must grow bucket? if (!b->_keyvals) {
b->_max = 2; // Initial bucket size
b->_keyvals = (void**)_arena->AmallocWords(sizeof(void*) * b->_max * 2);
} else {
b->_keyvals = (void**)_arena->Arealloc(b->_keyvals, sizeof(void*) * b->_max * 2, sizeof(void*) * b->_max * 4);
b->_max <<= 1; // Double bucket
}
}
b->_keyvals[b->_cnt + b->_cnt ] = key;
b->_keyvals[b->_cnt + b->_cnt + 1] = val;
b->_cnt++; return NULL; // Nothing found prior
}
//------------------------------Delete--------------------------------------- // Find & remove a value from dictionary. Return old value. void* Dict::Delete(void* key) {
uint i = _hash(key) & (_size - 1); // Get hash key, corrected for size
bucket* b = &_bin[i]; // Handy shortcut for (uint j = 0; j < b->_cnt; j++) { if (!_cmp(key, b->_keyvals[j + j])) { void* prior = b->_keyvals[j + j + 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];
_cnt--; // One less thing in table return prior;
}
} return NULL;
}
//------------------------------FindDict------------------------------------- // Find a key-value pair in the given dictionary. If not found, return NULL. // If found, move key-value pair towards head of list. void* Dict::operator [](constvoid* key) const {
uint i = _hash(key) & (_size - 1); // Get hash key, corrected for size
bucket* b = &_bin[i]; // Handy shortcut for (uint j = 0; j < b->_cnt; j++) { if (!_cmp(key, b->_keyvals[j + j])) { return b->_keyvals[j + j + 1];
}
} return NULL;
}
//------------------------------print------------------------------------------ // Handier print routine void Dict::print() {
DictI i(this); // Moved definition in iterator here because of g++.
tty->print("Dict@" INTPTR_FORMAT "[%d] = {", p2i(this), _cnt); for (; i.test(); ++i) {
tty->print("(" INTPTR_FORMAT "," INTPTR_FORMAT "),", p2i(i._key), p2i(i._value));
}
tty->print_cr("}");
}
//------------------------------Hashing Functions---------------------------- // Convert string to hash key. This algorithm implements a universal hash // function with the multipliers frozen (ok, so it's not universal). The // multipliers (and allowable characters) are all odd, so the resultant sum // is odd - guaranteed not divisible by any power of two, so the hash tables // can be any power of two with good results. Also, I choose multipliers // that have only 2 bits set (the low is always set to be odd) so // multiplication requires only shifts and adds. Characters are required to // be in the range 0-127 (I double & add 1 to force oddness). Keys are // limited to MAXID characters in length. Experimental evidence on 150K of // C text shows excellent spreading of values for any size hash table. int hashstr(constvoid* t) { char c; int k = 0;
int32_t sum = 0; constchar* s = (constchar*)t;
while (((c = *s++) != '\0') && (k < MAXID-1)) { // Get characters till null or MAXID-1
c = (c << 1) + 1; // Characters are always odd!
sum += c + (c << shft[k++]); // Universal hash function
} return (int)((sum + xsum[k]) >> 1); // Hash key, un-modulo'd table size
}
//------------------------------hashptr-------------------------------------- // Slimey cheap hash function; no guaranteed performance. Better than the // default for pointers, especially on MS-DOS machines. int hashptr(constvoid* key) { return ((intptr_t)key >> 2);
}
// Slimey cheap hash function; no guaranteed performance. int hashkey(constvoid* key) { return (intptr_t)key;
}
//============================================================================= //------------------------------reset------------------------------------------ // Create an iterator and initialize the first variables. void DictI::reset(const Dict* dict) {
_d = dict;
_i = (uint)-1; // Before the first bin
_j = 0; // Nothing left in the current bin
++(*this); // Step to first real value
}
//------------------------------next------------------------------------------- // Find the next key-value pair in the dictionary, or return a NULL key and // value. void DictI::operator ++(void) { if (_j--) { // Still working in current bin?
_key = _d->_bin[_i]._keyvals[_j + _j];
_value = _d->_bin[_i]._keyvals[_j + _j + 1]; return;
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
