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