1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/adlc/dict2.cpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,356 @@
1.4 +/*
1.5 + * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +// Dictionaries - An Abstract Data Type
1.29 +
1.30 +#include "adlc.hpp"
1.31 +
1.32 +// #include "dict.hpp"
1.33 +
1.34 +
1.35 +//------------------------------data-----------------------------------------
1.36 +// String hash tables
1.37 +#define MAXID 20
1.38 +static char initflag = 0; // True after 1st initialization
1.39 +static char shft[MAXID + 1] = {1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7};
1.40 +static short xsum[MAXID];
1.41 +
1.42 +//------------------------------bucket---------------------------------------
1.43 +class bucket {
1.44 +public:
1.45 + int _cnt, _max; // Size of bucket
1.46 + const void **_keyvals; // Array of keys and values
1.47 +};
1.48 +
1.49 +//------------------------------Dict-----------------------------------------
1.50 +// The dictionary is kept has a hash table. The hash table is a even power
1.51 +// of two, for nice modulo operations. Each bucket in the hash table points
1.52 +// to a linear list of key-value pairs; each key & value is just a (void *).
1.53 +// The list starts with a count. A hash lookup finds the list head, then a
1.54 +// simple linear scan finds the key. If the table gets too full, it's
1.55 +// doubled in size; the total amount of EXTRA times all hash functions are
1.56 +// computed for the doubling is no more than the current size - thus the
1.57 +// doubling in size costs no more than a constant factor in speed.
1.58 +Dict::Dict(CmpKey initcmp, Hash inithash) : _hash(inithash), _cmp(initcmp), _arena(NULL) {
1.59 + init();
1.60 +}
1.61 +
1.62 +Dict::Dict(CmpKey initcmp, Hash inithash, Arena *arena) : _hash(inithash), _cmp(initcmp), _arena(arena) {
1.63 + init();
1.64 +}
1.65 +
1.66 +void Dict::init() {
1.67 + int i;
1.68 +
1.69 + // Precompute table of null character hashes
1.70 + if (!initflag) { // Not initializated yet?
1.71 + xsum[0] = (short) ((1 << shft[0]) + 1); // Initialize
1.72 + for( i = 1; i < MAXID; i++) {
1.73 + xsum[i] = (short) ((1 << shft[i]) + 1 + xsum[i-1]);
1.74 + }
1.75 + initflag = 1; // Never again
1.76 + }
1.77 +
1.78 + _size = 16; // Size is a power of 2
1.79 + _cnt = 0; // Dictionary is empty
1.80 + _bin = (bucket*)_arena->Amalloc_4(sizeof(bucket) * _size);
1.81 + memset(_bin, 0, sizeof(bucket) * _size);
1.82 +}
1.83 +
1.84 +//------------------------------~Dict------------------------------------------
1.85 +// Delete an existing dictionary.
1.86 +Dict::~Dict() {
1.87 +}
1.88 +
1.89 +//------------------------------Clear----------------------------------------
1.90 +// Zap to empty; ready for re-use
1.91 +void Dict::Clear() {
1.92 + _cnt = 0; // Empty contents
1.93 + for( int i=0; i<_size; i++ )
1.94 + _bin[i]._cnt = 0; // Empty buckets, but leave allocated
1.95 + // Leave _size & _bin alone, under the assumption that dictionary will
1.96 + // grow to this size again.
1.97 +}
1.98 +
1.99 +//------------------------------doubhash---------------------------------------
1.100 +// Double hash table size. If can't do so, just suffer. If can, then run
1.101 +// thru old hash table, moving things to new table. Note that since hash
1.102 +// table doubled, exactly 1 new bit is exposed in the mask - so everything
1.103 +// in the old table ends up on 1 of two lists in the new table; a hi and a
1.104 +// lo list depending on the value of the bit.
1.105 +void Dict::doubhash(void) {
1.106 + int oldsize = _size;
1.107 + _size <<= 1; // Double in size
1.108 + _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*oldsize, sizeof(bucket)*_size );
1.109 + memset( &_bin[oldsize], 0, oldsize*sizeof(bucket) );
1.110 + // Rehash things to spread into new table
1.111 + for( int i=0; i < oldsize; i++) { // For complete OLD table do
1.112 + bucket *b = &_bin[i]; // Handy shortcut for _bin[i]
1.113 + if( !b->_keyvals ) continue; // Skip empties fast
1.114 +
1.115 + bucket *nb = &_bin[i+oldsize]; // New bucket shortcut
1.116 + int j = b->_max; // Trim new bucket to nearest power of 2
1.117 + while( j > b->_cnt ) j >>= 1; // above old bucket _cnt
1.118 + if( !j ) j = 1; // Handle zero-sized buckets
1.119 + nb->_max = j<<1;
1.120 + // Allocate worst case space for key-value pairs
1.121 + nb->_keyvals = (const void**)_arena->Amalloc_4( sizeof(void *)*nb->_max*2 );
1.122 + int nbcnt = 0;
1.123 +
1.124 + for( j=0; j<b->_cnt; j++ ) { // Rehash all keys in this bucket
1.125 + const void *key = b->_keyvals[j+j];
1.126 + if( (_hash( key ) & (_size-1)) != i ) { // Moving to hi bucket?
1.127 + nb->_keyvals[nbcnt+nbcnt] = key;
1.128 + nb->_keyvals[nbcnt+nbcnt+1] = b->_keyvals[j+j+1];
1.129 + nb->_cnt = nbcnt = nbcnt+1;
1.130 + b->_cnt--; // Remove key/value from lo bucket
1.131 + b->_keyvals[j+j ] = b->_keyvals[b->_cnt+b->_cnt ];
1.132 + b->_keyvals[j+j+1] = b->_keyvals[b->_cnt+b->_cnt+1];
1.133 + j--; // Hash compacted element also
1.134 + }
1.135 + } // End of for all key-value pairs in bucket
1.136 + } // End of for all buckets
1.137 +
1.138 +
1.139 +}
1.140 +
1.141 +//------------------------------Dict-----------------------------------------
1.142 +// Deep copy a dictionary.
1.143 +Dict::Dict( const Dict &d ) : _size(d._size), _cnt(d._cnt), _hash(d._hash),_cmp(d._cmp), _arena(d._arena) {
1.144 + _bin = (bucket*)_arena->Amalloc_4(sizeof(bucket)*_size);
1.145 + memcpy( _bin, d._bin, sizeof(bucket)*_size );
1.146 + for( int i=0; i<_size; i++ ) {
1.147 + if( !_bin[i]._keyvals ) continue;
1.148 + _bin[i]._keyvals=(const void**)_arena->Amalloc_4( sizeof(void *)*_bin[i]._max*2);
1.149 + memcpy( _bin[i]._keyvals, d._bin[i]._keyvals,_bin[i]._cnt*2*sizeof(void*));
1.150 + }
1.151 +}
1.152 +
1.153 +//------------------------------Dict-----------------------------------------
1.154 +// Deep copy a dictionary.
1.155 +Dict &Dict::operator =( const Dict &d ) {
1.156 + if( _size < d._size ) { // If must have more buckets
1.157 + _arena = d._arena;
1.158 + _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*_size, sizeof(bucket)*d._size );
1.159 + memset( &_bin[_size], 0, (d._size-_size)*sizeof(bucket) );
1.160 + _size = d._size;
1.161 + }
1.162 + for( int i=0; i<_size; i++ ) // All buckets are empty
1.163 + _bin[i]._cnt = 0; // But leave bucket allocations alone
1.164 + _cnt = d._cnt;
1.165 + *(Hash*)(&_hash) = d._hash;
1.166 + *(CmpKey*)(&_cmp) = d._cmp;
1.167 + for(int k=0; k<_size; k++ ) {
1.168 + bucket *b = &d._bin[k]; // Shortcut to source bucket
1.169 + for( int j=0; j<b->_cnt; j++ )
1.170 + Insert( b->_keyvals[j+j], b->_keyvals[j+j+1] );
1.171 + }
1.172 + return *this;
1.173 +}
1.174 +
1.175 +//------------------------------Insert---------------------------------------
1.176 +// Insert or replace a key/value pair in the given dictionary. If the
1.177 +// dictionary is too full, it's size is doubled. The prior value being
1.178 +// replaced is returned (NULL if this is a 1st insertion of that key). If
1.179 +// an old value is found, it's swapped with the prior key-value pair on the
1.180 +// list. This moves a commonly searched-for value towards the list head.
1.181 +const void *Dict::Insert(const void *key, const void *val) {
1.182 + int hash = _hash( key ); // Get hash key
1.183 + int i = hash & (_size-1); // Get hash key, corrected for size
1.184 + bucket *b = &_bin[i]; // Handy shortcut
1.185 + for( int j=0; j<b->_cnt; j++ )
1.186 + if( !_cmp(key,b->_keyvals[j+j]) ) {
1.187 + const void *prior = b->_keyvals[j+j+1];
1.188 + b->_keyvals[j+j ] = key; // Insert current key-value
1.189 + b->_keyvals[j+j+1] = val;
1.190 + return prior; // Return prior
1.191 + }
1.192 +
1.193 + if( ++_cnt > _size ) { // Hash table is full
1.194 + doubhash(); // Grow whole table if too full
1.195 + i = hash & (_size-1); // Rehash
1.196 + b = &_bin[i]; // Handy shortcut
1.197 + }
1.198 + if( b->_cnt == b->_max ) { // Must grow bucket?
1.199 + if( !b->_keyvals ) {
1.200 + b->_max = 2; // Initial bucket size
1.201 + b->_keyvals = (const void**)_arena->Amalloc_4( sizeof(void *)*b->_max*2 );
1.202 + } else {
1.203 + b->_keyvals = (const void**)_arena->Arealloc( b->_keyvals, sizeof(void *)*b->_max*2, sizeof(void *)*b->_max*4 );
1.204 + b->_max <<= 1; // Double bucket
1.205 + }
1.206 + }
1.207 + b->_keyvals[b->_cnt+b->_cnt ] = key;
1.208 + b->_keyvals[b->_cnt+b->_cnt+1] = val;
1.209 + b->_cnt++;
1.210 + return NULL; // Nothing found prior
1.211 +}
1.212 +
1.213 +//------------------------------Delete---------------------------------------
1.214 +// Find & remove a value from dictionary. Return old value.
1.215 +const void *Dict::Delete(void *key) {
1.216 + int i = _hash( key ) & (_size-1); // Get hash key, corrected for size
1.217 + bucket *b = &_bin[i]; // Handy shortcut
1.218 + for( int j=0; j<b->_cnt; j++ )
1.219 + if( !_cmp(key,b->_keyvals[j+j]) ) {
1.220 + const void *prior = b->_keyvals[j+j+1];
1.221 + b->_cnt--; // Remove key/value from lo bucket
1.222 + b->_keyvals[j+j ] = b->_keyvals[b->_cnt+b->_cnt ];
1.223 + b->_keyvals[j+j+1] = b->_keyvals[b->_cnt+b->_cnt+1];
1.224 + _cnt--; // One less thing in table
1.225 + return prior;
1.226 + }
1.227 + return NULL;
1.228 +}
1.229 +
1.230 +//------------------------------FindDict-------------------------------------
1.231 +// Find a key-value pair in the given dictionary. If not found, return NULL.
1.232 +// If found, move key-value pair towards head of list.
1.233 +const void *Dict::operator [](const void *key) const {
1.234 + int i = _hash( key ) & (_size-1); // Get hash key, corrected for size
1.235 + bucket *b = &_bin[i]; // Handy shortcut
1.236 + for( int j=0; j<b->_cnt; j++ )
1.237 + if( !_cmp(key,b->_keyvals[j+j]) )
1.238 + return b->_keyvals[j+j+1];
1.239 + return NULL;
1.240 +}
1.241 +
1.242 +//------------------------------CmpDict--------------------------------------
1.243 +// CmpDict compares two dictionaries; they must have the same keys (their
1.244 +// keys must match using CmpKey) and they must have the same values (pointer
1.245 +// comparison). If so 1 is returned, if not 0 is returned.
1.246 +int Dict::operator ==(const Dict &d2) const {
1.247 + if( _cnt != d2._cnt ) return 0;
1.248 + if( _hash != d2._hash ) return 0;
1.249 + if( _cmp != d2._cmp ) return 0;
1.250 + for( int i=0; i < _size; i++) { // For complete hash table do
1.251 + bucket *b = &_bin[i]; // Handy shortcut
1.252 + if( b->_cnt != d2._bin[i]._cnt ) return 0;
1.253 + if( memcmp(b->_keyvals, d2._bin[i]._keyvals, b->_cnt*2*sizeof(void*) ) )
1.254 + return 0; // Key-value pairs must match
1.255 + }
1.256 + return 1; // All match, is OK
1.257 +}
1.258 +
1.259 +
1.260 +//------------------------------print----------------------------------------
1.261 +static void printvoid(const void* x) { printf("%p", x); }
1.262 +void Dict::print() {
1.263 + print(printvoid, printvoid);
1.264 +}
1.265 +void Dict::print(PrintKeyOrValue print_key, PrintKeyOrValue print_value) {
1.266 + for( int i=0; i < _size; i++) { // For complete hash table do
1.267 + bucket *b = &_bin[i]; // Handy shortcut
1.268 + for( int j=0; j<b->_cnt; j++ ) {
1.269 + print_key( b->_keyvals[j+j ]);
1.270 + printf(" -> ");
1.271 + print_value(b->_keyvals[j+j+1]);
1.272 + printf("\n");
1.273 + }
1.274 + }
1.275 +}
1.276 +
1.277 +//------------------------------Hashing Functions----------------------------
1.278 +// Convert string to hash key. This algorithm implements a universal hash
1.279 +// function with the multipliers frozen (ok, so it's not universal). The
1.280 +// multipliers (and allowable characters) are all odd, so the resultant sum
1.281 +// is odd - guaranteed not divisible by any power of two, so the hash tables
1.282 +// can be any power of two with good results. Also, I choose multipliers
1.283 +// that have only 2 bits set (the low is always set to be odd) so
1.284 +// multiplication requires only shifts and adds. Characters are required to
1.285 +// be in the range 0-127 (I double & add 1 to force oddness). Keys are
1.286 +// limited to MAXID characters in length. Experimental evidence on 150K of
1.287 +// C text shows excellent spreading of values for any size hash table.
1.288 +int hashstr(const void *t) {
1.289 + register char c, k = 0;
1.290 + register int sum = 0;
1.291 + register const char *s = (const char *)t;
1.292 +
1.293 + while (((c = s[k]) != '\0') && (k < MAXID-1)) { // Get characters till nul
1.294 + c = (char) ((c << 1) + 1); // Characters are always odd!
1.295 + sum += c + (c << shft[k++]); // Universal hash function
1.296 + }
1.297 + assert(k < (MAXID), "Exceeded maximum name length");
1.298 + return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size
1.299 +}
1.300 +
1.301 +//------------------------------hashptr--------------------------------------
1.302 +// Slimey cheap hash function; no guaranteed performance. Better than the
1.303 +// default for pointers, especially on MS-DOS machines.
1.304 +int hashptr(const void *key) {
1.305 +#ifdef __TURBOC__
1.306 + return (int)((intptr_t)key >> 16);
1.307 +#else // __TURBOC__
1.308 + return (int)((intptr_t)key >> 2);
1.309 +#endif
1.310 +}
1.311 +
1.312 +// Slimey cheap hash function; no guaranteed performance.
1.313 +int hashkey(const void *key) {
1.314 + return (int)((intptr_t)key);
1.315 +}
1.316 +
1.317 +//------------------------------Key Comparator Functions---------------------
1.318 +int cmpstr(const void *k1, const void *k2) {
1.319 + return strcmp((const char *)k1,(const char *)k2);
1.320 +}
1.321 +
1.322 +// Cheap key comparator.
1.323 +int cmpkey(const void *key1, const void *key2) {
1.324 + if (key1 == key2) return 0;
1.325 + intptr_t delta = (intptr_t)key1 - (intptr_t)key2;
1.326 + if (delta > 0) return 1;
1.327 + return -1;
1.328 +}
1.329 +
1.330 +//=============================================================================
1.331 +//------------------------------reset------------------------------------------
1.332 +// Create an iterator and initialize the first variables.
1.333 +void DictI::reset( const Dict *dict ) {
1.334 + _d = dict; // The dictionary
1.335 + _i = (int)-1; // Before the first bin
1.336 + _j = 0; // Nothing left in the current bin
1.337 + ++(*this); // Step to first real value
1.338 +}
1.339 +
1.340 +//------------------------------next-------------------------------------------
1.341 +// Find the next key-value pair in the dictionary, or return a NULL key and
1.342 +// value.
1.343 +void DictI::operator ++(void) {
1.344 + if( _j-- ) { // Still working in current bin?
1.345 + _key = _d->_bin[_i]._keyvals[_j+_j];
1.346 + _value = _d->_bin[_i]._keyvals[_j+_j+1];
1.347 + return;
1.348 + }
1.349 +
1.350 + while( ++_i < _d->_size ) { // Else scan for non-zero bucket
1.351 + _j = _d->_bin[_i]._cnt;
1.352 + if( !_j ) continue;
1.353 + _j--;
1.354 + _key = _d->_bin[_i]._keyvals[_j+_j];
1.355 + _value = _d->_bin[_i]._keyvals[_j+_j+1];
1.356 + return;
1.357 + }
1.358 + _key = _value = NULL;
1.359 +}
