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 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
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"
30
31 // Dictionaries - An Abstract Data Type
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),
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
312 // is odd - guaranteed not divisible by any power of two, so the hash tables
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--------------------------------------
332 // Slimey cheap hash function; no guaranteed performance. Better than the
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
342 // Slimey cheap hash function; no guaranteed performance.
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
352 // Cheap key comparator.
353 int32 cmpkey(const void *key1, const void *key2) {
354 if (key1 == key2) return 0;
355 intptr_t delta = (intptr_t)key1 - (intptr_t)key2;
356 if (delta > 0) return 1;
357 return -1;
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) {
|
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 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "libadt/dict.hpp"
27
28 // Dictionaries - An Abstract Data Type
29
30 // %%%%% includes not needed with AVM framework - Ungar
31
32 #include <assert.h>
33
34 //------------------------------data-----------------------------------------
35 // String hash tables
36 #define MAXID 20
37 static uint8_t initflag = 0; // True after 1st initialization
38 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};
39 static short xsum[MAXID];
40
41 //------------------------------bucket---------------------------------------
42 class bucket : public ResourceObj {
43 public:
44 uint _cnt, _max; // Size of bucket
45 void **_keyvals; // Array of keys and values
46 };
47
48 //------------------------------Dict-----------------------------------------
49 // The dictionary is kept has a hash table. The hash table is a even power
50 // of two, for nice modulo operations. Each bucket in the hash table points
51 // to a linear list of key-value pairs; each key & value is just a (void *).
52 // The list starts with a count. A hash lookup finds the list head, then a
53 // simple linear scan finds the key. If the table gets too full, it's
54 // doubled in size; the total amount of EXTRA times all hash functions are
55 // computed for the doubling is no more than the current size - thus the
56 // doubling in size costs no more than a constant factor in speed.
57 Dict::Dict(CmpKey initcmp, Hash inithash) : _hash(inithash), _cmp(initcmp),
252 }
253 return NULL;
254 }
255
256 //------------------------------FindDict-------------------------------------
257 // Find a key-value pair in the given dictionary. If not found, return NULL.
258 // If found, move key-value pair towards head of list.
259 void *Dict::operator [](const void *key) const {
260 uint i = _hash( key ) & (_size-1); // Get hash key, corrected for size
261 bucket *b = &_bin[i]; // Handy shortcut
262 for( uint j=0; j<b->_cnt; j++ )
263 if( !_cmp(key,b->_keyvals[j+j]) )
264 return b->_keyvals[j+j+1];
265 return NULL;
266 }
267
268 //------------------------------CmpDict--------------------------------------
269 // CmpDict compares two dictionaries; they must have the same keys (their
270 // keys must match using CmpKey) and they must have the same values (pointer
271 // comparison). If so 1 is returned, if not 0 is returned.
272 int32_t Dict::operator ==(const Dict &d2) const {
273 if( _cnt != d2._cnt ) return 0;
274 if( _hash != d2._hash ) return 0;
275 if( _cmp != d2._cmp ) return 0;
276 for( uint i=0; i < _size; i++) { // For complete hash table do
277 bucket *b = &_bin[i]; // Handy shortcut
278 if( b->_cnt != d2._bin[i]._cnt ) return 0;
279 if( memcmp(b->_keyvals, d2._bin[i]._keyvals, b->_cnt*2*sizeof(void*) ) )
280 return 0; // Key-value pairs must match
281 }
282 return 1; // All match, is OK
283 }
284
285 //------------------------------print------------------------------------------
286 // Handier print routine
287 void Dict::print() {
288 DictI i(this); // Moved definition in iterator here because of g++.
289 tty->print("Dict@0x%lx[%d] = {", this, _cnt);
290 for( ; i.test(); ++i ) {
291 tty->print("(0x%lx,0x%lx),", i._key, i._value);
292 }
293 tty->print_cr("}");
294 }
295
296 //------------------------------Hashing Functions----------------------------
297 // Convert string to hash key. This algorithm implements a universal hash
298 // function with the multipliers frozen (ok, so it's not universal). The
299 // multipliers (and allowable characters) are all odd, so the resultant sum
300 // is odd - guaranteed not divisible by any power of two, so the hash tables
301 // can be any power of two with good results. Also, I choose multipliers
302 // that have only 2 bits set (the low is always set to be odd) so
303 // multiplication requires only shifts and adds. Characters are required to
304 // be in the range 0-127 (I double & add 1 to force oddness). Keys are
305 // limited to MAXID characters in length. Experimental evidence on 150K of
306 // C text shows excellent spreading of values for any size hash table.
307 int hashstr(const void *t) {
308 register char c, k = 0;
309 register int32_t sum = 0;
310 register const char *s = (const char *)t;
311
312 while( ((c = *s++) != '\0') && (k < MAXID-1) ) { // Get characters till null or MAXID-1
313 c = (c<<1)+1; // Characters are always odd!
314 sum += c + (c<<shft[k++]); // Universal hash function
315 }
316 return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size
317 }
318
319 //------------------------------hashptr--------------------------------------
320 // Slimey cheap hash function; no guaranteed performance. Better than the
321 // default for pointers, especially on MS-DOS machines.
322 int hashptr(const void *key) {
323 return ((intptr_t)key >> 2);
324 }
325
326 // Slimey cheap hash function; no guaranteed performance.
327 int hashkey(const void *key) {
328 return (intptr_t)key;
329 }
330
331 //------------------------------Key Comparator Functions---------------------
332 int32_t cmpstr(const void *k1, const void *k2) {
333 return strcmp((const char *)k1,(const char *)k2);
334 }
335
336 // Cheap key comparator.
337 int32_t cmpkey(const void *key1, const void *key2) {
338 if (key1 == key2) return 0;
339 intptr_t delta = (intptr_t)key1 - (intptr_t)key2;
340 if (delta > 0) return 1;
341 return -1;
342 }
343
344 //=============================================================================
345 //------------------------------reset------------------------------------------
346 // Create an iterator and initialize the first variables.
347 void DictI::reset( const Dict *dict ) {
348 _d = dict; // The dictionary
349 _i = (uint)-1; // Before the first bin
350 _j = 0; // Nothing left in the current bin
351 ++(*this); // Step to first real value
352 }
353
354 //------------------------------next-------------------------------------------
355 // Find the next key-value pair in the dictionary, or return a NULL key and
356 // value.
357 void DictI::operator ++(void) {
|