Mercurial > hg > truffle
comparison src/share/vm/libadt/dict.hpp @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | 98cb887364d3 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a61af66fc99e |
---|---|
1 /* | |
2 * Copyright 1997-2003 Sun Microsystems, Inc. All Rights Reserved. | |
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 * | |
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
21 * have any questions. | |
22 * | |
23 */ | |
24 | |
25 #ifndef _DICT_ | |
26 #define _DICT_ | |
27 // Dictionaries - An Abstract Data Type | |
28 //INTERFACE | |
29 class ostream; | |
30 class Dict; | |
31 | |
32 // These dictionaries define a key-value mapping. They can be inserted to, | |
33 // searched or deleted from. They grow and shrink as needed. The key is a | |
34 // pointer to something (or anything which can be stored in a pointer). A | |
35 // key comparison routine determines if two keys are equal or not. A hash | |
36 // function can be provided; if it's not provided the key itself is used | |
37 // instead. A nice string hash function is included. | |
38 typedef int32 (*CmpKey)(const void *key1, const void *key2); | |
39 typedef int (*Hash)(const void *key); | |
40 typedef void (*FuncDict)(const void *key, const void *val, Dict *d); | |
41 | |
42 class Dict : public ResourceObj { // Dictionary structure | |
43 private: | |
44 class Arena *_arena; // Where to draw storage from | |
45 class bucket *_bin; // Hash table is array of buckets | |
46 uint _size; // Size (# of slots) in hash table | |
47 uint32 _cnt; // Number of key-value pairs in hash table | |
48 const Hash _hash; // Hashing function | |
49 const CmpKey _cmp; // Key comparison function | |
50 void doubhash( void ); // Double hash table size | |
51 | |
52 public: | |
53 friend class DictI; // Friendly iterator function | |
54 | |
55 // cmp is a key comparision routine. hash is a routine to hash a key. | |
56 Dict( CmpKey cmp, Hash hash ); | |
57 Dict( CmpKey cmp, Hash hash, Arena *arena, int size=16 ); | |
58 ~Dict(); | |
59 | |
60 Dict( const Dict & ); // Deep-copy guts | |
61 Dict &operator =( const Dict & ); | |
62 | |
63 // Zap to empty; ready for re-use | |
64 void Clear(); | |
65 | |
66 // Return # of key-value pairs in dict | |
67 uint32 Size(void) const { return _cnt; } | |
68 | |
69 // Insert inserts the given key-value pair into the dictionary. The prior | |
70 // value of the key is returned; NULL if the key was not previously defined. | |
71 void *Insert(void *key, void *val, bool replace = true); // A new key-value | |
72 void *Delete(void *key); // Delete & return old | |
73 | |
74 // Find finds the value of a given key; or NULL if not found. | |
75 // The dictionary is NOT changed. | |
76 void *operator [](const void *key) const; // Do a lookup | |
77 | |
78 // == compares two dictionaries; they must have the same keys (their keys | |
79 // must match using CmpKey) and they must have the same values (pointer | |
80 // comparison). If so 1 is returned, if not 0 is returned. | |
81 int32 operator ==(const Dict &d) const; // Compare dictionaries for equal | |
82 | |
83 // Print out the dictionary contents as key-value pairs | |
84 void print(); | |
85 }; | |
86 | |
87 // Hashing functions | |
88 int hashstr(const void *s); // Nice string hash | |
89 // Slimey cheap hash function; no guarenteed performance. Better than the | |
90 // default for pointers, especially on MS-DOS machines. | |
91 int hashptr(const void *key); | |
92 // Slimey cheap hash function; no guarenteed performance. | |
93 int hashkey(const void *key); | |
94 | |
95 // Key comparators | |
96 int32 cmpstr(const void *k1, const void *k2); | |
97 // Slimey cheap key comparator. | |
98 int32 cmpkey(const void *key1, const void *key2); | |
99 | |
100 //------------------------------Iteration-------------------------------------- | |
101 // The class of dictionary iterators. Fails in the presences of modifications | |
102 // to the dictionary during iteration (including searches). | |
103 // Usage: for( DictI i(dict); i.test(); ++i ) { body = i.key; body = i.value;} | |
104 class DictI { | |
105 private: | |
106 const Dict *_d; // Dictionary being iterated over | |
107 uint _i; // Counter over the bins | |
108 uint _j; // Counter inside each bin | |
109 public: | |
110 const void *_key, *_value; // Easy access to the key-value pair | |
111 DictI( const Dict *d ) {reset(d);}; // Create a new iterator | |
112 void reset( const Dict *dict ); // Reset existing iterator | |
113 void operator ++(void); // Increment iterator | |
114 int test(void) { return _i<_d->_size;} // Test for end of iteration | |
115 }; | |
116 | |
117 #endif // _DICT_ |