1 mike 1.1 //%/////////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2000 The Open Group, BMC Software, Tivoli Systems, IBM
4 //
5 // Permission is hereby granted, free of charge, to any person obtaining a
6 // copy of this software and associated documentation files (the "Software"),
7 // to deal in the Software without restriction, including without limitation
8 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 // and/or sell copies of the Software, and to permit persons to whom the
10 // Software is furnished to do so, subject to the following conditions:
11 //
12 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
13 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
14 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
15 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
16 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
17 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
18 // DEALINGS IN THE SOFTWARE.
19 //
20 //==============================================================================
21 //
22 mike 1.1 // Author: Mike Brasher (mbrasher@bmc.com)
23 //
24 // Modified By:
25 //
26 //%/////////////////////////////////////////////////////////////////////////////
27
28 #ifndef Pegasus_HashTable_h
29 #define Pegasus_HashTable_h
30
31 #include <Pegasus/Common/Config.h>
32 #include <Pegasus/Common/String.h>
33
34 PEGASUS_NAMESPACE_BEGIN
35
|
36 mike 1.2 PEGASUS_COMMON_LINKAGE Uint32 Hash(const String& str);
37
38 inline Uint32 Hash(Uint32 x) { return x + 13; }
|
39 mike 1.1
40 /** Representation for a bucket. The HashTable class derives from this
41 bucket to append a key and value. This base class just defines
42 the pointer to the next bucket in the chain.
43 */
|
44 mike 1.2 class PEGASUS_COMMON_LINKAGE _BucketBase
|
45 mike 1.1 {
46 public:
47
|
48 mike 1.2 /** Default constructor. */
49 _BucketBase() : next(0) { }
50
|
51 mike 1.1 /** Virtual destructor to ensure destruction of derived class
52 elements.
53 */
|
54 mike 1.2 virtual ~_BucketBase();
|
55 mike 1.1
56 /** returns true if the key pointed to by the key argument is equal
57 to the internal key of this bucket. This method must be overridden
58 by the derived class.
59 */
60 virtual Boolean equal(const void* key) const = 0;
61
|
62 mike 1.2 /** Clone this bucket. */
63 virtual _BucketBase* clone() const = 0;
64
65 _BucketBase* next;
|
66 mike 1.1 };
67
|
68 mike 1.2 class _HashTableBase;
|
69 mike 1.1
70 /** This class implements a simple hash table forward iterator. */
|
71 mike 1.2 class PEGASUS_COMMON_LINKAGE _HashTableIteratorBase
|
72 mike 1.1 {
73 public:
74
|
75 mike 1.2 _HashTableIteratorBase() : _first(0), _last(0), _bucket(0) { }
|
76 mike 1.1
77 operator Boolean() const { return _bucket != 0; }
78
|
79 mike 1.2 _HashTableIteratorBase operator++(int);
|
80 mike 1.1
|
81 mike 1.2 _HashTableIteratorBase& operator++();
|
82 mike 1.1
|
83 mike 1.2 _HashTableIteratorBase(_BucketBase** first, _BucketBase** last);
|
84 mike 1.1
85 protected:
86
|
87 mike 1.2 _BucketBase** _first;
88 _BucketBase** _last;
89 _BucketBase* _bucket;
90 friend _HashTableBase;
|
91 mike 1.1 };
92
|
93 mike 1.2 /** The _HashTableBase class is the base class which HashTable derives from.
|
94 mike 1.1
95 This code is primarily an internal class used to implement the HashTable.
96 But there may be occasions to use it directly.
97
|
98 mike 1.2 _HashTableBase parcels out much of the large code so that that code is not
|
99 mike 1.1 instantiated by the HashTable template class many times. This scheme helps
100 reduce code bloat caused by templates. The HashTable template class below
101 acts as kind of a wrapper around this class.
102
|
103 mike 1.2 _HashTableBase is implemented as an array of pointers to chains of hash
|
104 mike 1.1 buckets. The table initially allocates some number of chains (which can
105 be controlled by the constructor) and then may increase the number of
106 chains later (resulting in a reorganization of the hash table).
107
108 ATTN: reorganization not supported yet.
109 */
|
110 mike 1.2 class PEGASUS_COMMON_LINKAGE _HashTableBase
|
111 mike 1.1 {
112 public:
113
114 /** This constructor allocates an array of pointers to chains of buckets,
115 which of course are all empty at this time. The numChains argument
116 If the numChains argument is less than eight, then eight chains will
117 be created.
118 @param numChains - specifies the initial number of chains.
119 */
|
120 mike 1.2 _HashTableBase(Uint32 numChains);
121
122 /** Copy constructor. */
123 _HashTableBase(const _HashTableBase& x);
|
124 mike 1.1
125 /** Destructor. */
|
126 mike 1.2 ~_HashTableBase();
127
128 /** Assignment operator. */
129 _HashTableBase& operator=(const _HashTableBase& x);
|
130 mike 1.1
131 /** Returns the size of this hash table (the number of entries). */
132 Uint32 getSize() const { return _size; }
133
134 /** Clears the contents of this hash table. After this is called, the
135 getSize() method returns zero.
136 */
137 void clear();
138
139 /** Inserts new key-value pair into hash table. Deletes the bucket on
140 failure so caller need not.
141 @param hashCode - hash code generated by caller's hash function.
142 @param bucket - bucket to be inserted.
143 @param key - pointer to key.
144 @return true if insertion successful; false if duplicate key.
145 */
|
146 mike 1.2 Boolean insert(Uint32 hashCode, _BucketBase* bucket, const void* key);
|
147 mike 1.1
148 /** Finds the bucket with the given key. This method uses the
|
149 mike 1.2 _BucketBase::equal() method to compare keys.
|
150 mike 1.1 @param hashCode - hash code generated by caller's hash function.
151 @param key - void pointer to key.
152 @return pointer to bucket with that key or zero otherwise.
153 */
|
154 mike 1.2 const _BucketBase* lookup(Uint32 hashCode, const void* key);
|
155 mike 1.1
156 /** Removes the bucket with the given key. This method uses the
|
157 mike 1.2 _BucketBase::equal() method to compare keys.
|
158 mike 1.1 @param hashCode - hash code generated by caller's hash function.
159 @param key - void pointer to key.
160 @return true if entry found and removed and false otherwise.
161 */
162 Boolean remove(Uint32 hashCode, const void* key);
163
164 protected:
165
166 Uint32 _size;
167 Uint32 _numChains;
|
168 mike 1.2 _BucketBase** _chains;
|
169 mike 1.1 };
170
|
171 mike 1.2 /** The _Bucket class is used to implement the HashTable class.
|
172 mike 1.1 */
173 template<class K, class V>
|
174 mike 1.2 class _Bucket : public _BucketBase
|
175 mike 1.1 {
176 public:
177
|
178 mike 1.2 _Bucket(const K& key, const V& value) : _key(key), _value(value) { }
|
179 mike 1.1
|
180 mike 1.2 virtual ~_Bucket();
|
181 mike 1.1
182 virtual Boolean equal(const void* key) const;
183
|
184 mike 1.2 virtual _BucketBase* clone() const;
185
|
186 mike 1.1 K& getKey() { return _key; }
187
188 V& getValue() { return _value; }
189
190 private:
191
192 K _key;
193 V _value;
194 };
195
196 template<class K, class V>
|
197 mike 1.2 Boolean _Bucket<K,V>::equal(const void* key) const
|
198 mike 1.1 {
199 return *((K*)key) == _key;
200 }
201
202 template<class K, class V>
|
203 mike 1.2 _Bucket<K,V>::~_Bucket()
|
204 mike 1.1 {
205
206 }
207
|
208 mike 1.2 template<class K, class V>
209 _BucketBase* _Bucket<K,V>::clone() const
210 {
211 return new _Bucket<K,V>(_key, _value);
212 }
213
|
214 mike 1.1 /** Iterator for HashTable class. */
215 template<class K, class V>
|
216 mike 1.2 class _HashTableIterator : public _HashTableIteratorBase
|
217 mike 1.1 {
218 public:
219
|
220 mike 1.2 _HashTableIterator()
221 : _HashTableIteratorBase() { }
|
222 mike 1.1
|
223 mike 1.2 _HashTableIterator(_BucketBase** first, _BucketBase** last)
224 : _HashTableIteratorBase(first, last) { }
|
225 mike 1.1
|
226 mike 1.2 const K& key() const { return ((_Bucket<K,V>*)_bucket)->getKey(); }
|
227 mike 1.1
|
228 mike 1.2 const V& value() const { return ((_Bucket<K,V>*)_bucket)->getValue(); }
|
229 mike 1.1 };
230
231 /** HashTable provides a simple hash table implementation which associates
232 key-value pairs.
233 */
234 template<class K, class V>
|
235 mike 1.2 class HashTable : public _HashTableBase
|
236 mike 1.1 {
237 public:
238
|
239 mike 1.2 typedef _HashTableIterator<K,V> Iterator;
|
240 mike 1.1
241 /** By default, we create this many chains initially */
242 enum { DEFAULT_NUM_CHAINS = 32 };
243
244 /** Constructor.
245 @param numChains - number of chains to create.
246 */
247 HashTable(Uint32 numChains = DEFAULT_NUM_CHAINS)
|
248 mike 1.2 : _HashTableBase(numChains)
|
249 mike 1.1 {
250 }
251
252 /** Inserts new key-value pair into hash table.
253 @param key - key component.
254 @param value - value component.
255 @return true on success; false if duplicate key.
256 */
257 Boolean insert(const K& key, const V& value)
258 {
|
259 mike 1.2 return _HashTableBase::insert(
260 Hash(key), new _Bucket<K,V>(key, value), &key);
|
261 mike 1.1 }
262
263 /** Looks up the entry with the given key.
264 @param key - key of entry to be located.
265 @param value - output value.
266 @return true if found; false otherwise.
267 */
268 Boolean lookup(const K& key, V& value);
269
270 /** Removes the entry with the given key.
271 @param key - key of entry to be removed.
272 @return true on success; false otherwise.
273 */
274 Boolean remove(const K& key)
275 {
|
276 mike 1.2 return _HashTableBase::remove(Hash(key), &key);
|
277 mike 1.1 }
278
279 /** Obtains an iterator for this object. */
280 Iterator start() const
281 {
282 return Iterator(_chains, _chains + _numChains);
283 }
284 };
285
286 template<class K, class V>
287 inline Boolean HashTable<K,V>::lookup(const K& key, V& value)
288 {
|
289 mike 1.2 _Bucket<K,V>* bucket
290 = (_Bucket<K,V>*)_HashTableBase::lookup(Hash(key), &key);
|
291 mike 1.1
292 if (bucket)
293 {
294 value = bucket->getValue();
295 return true;
296 }
297
298 return false;
299 }
300
301 PEGASUS_NAMESPACE_END
302
303 #endif /* Pegasus_HashTable_h */
|
Return to
HashTable.h
CVS log
Up to [Pegasus] / pegasus / src / Pegasus / Common