1 karl 1.15 //%2005////////////////////////////////////////////////////////////////////////
|
2 mike 1.10 //
|
3 karl 1.14 // Copyright (c) 2000, 2001, 2002 BMC Software; Hewlett-Packard Development
4 // Company, L.P.; IBM Corp.; The Open Group; Tivoli Systems.
5 // Copyright (c) 2003 BMC Software; Hewlett-Packard Development Company, L.P.;
|
6 karl 1.13 // IBM Corp.; EMC Corporation, The Open Group.
|
7 karl 1.14 // Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.;
8 // IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
|
9 karl 1.15 // Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.;
10 // EMC Corporation; VERITAS Software Corporation; The Open Group.
|
11 mike 1.10 //
12 // Permission is hereby granted, free of charge, to any person obtaining a copy
|
13 kumpf 1.12 // of this software and associated documentation files (the "Software"), to
14 // deal in the Software without restriction, including without limitation the
15 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
|
16 mike 1.10 // sell copies of the Software, and to permit persons to whom the Software is
17 // furnished to do so, subject to the following conditions:
18 //
|
19 kumpf 1.12 // THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
|
20 mike 1.10 // ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. THE SOFTWARE IS PROVIDED
21 // "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
|
22 kumpf 1.12 // LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
23 // PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
24 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
|
25 mike 1.10 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27 //
28 //==============================================================================
29 //
30 // Author: Mike Brasher (mbrasher@bmc.com)
31 //
32 // Modified By:
33 //
34 //%/////////////////////////////////////////////////////////////////////////////
35
36 #include <cstring>
37 #include "HashTable.h"
38
39 PEGASUS_NAMESPACE_BEGIN
40
41 ////////////////////////////////////////////////////////////////////////////////
42 //
43 // Hash()
44 //
45 ////////////////////////////////////////////////////////////////////////////////
46 mike 1.10
47 Uint32 HashFunc<String>::hash(const String& str)
48 {
49 Uint32 h = 0;
50
51 for (Uint32 i = 0, n = str.size(); i < n; i++)
52 h = 5 * h + str[i];
53
54 return h;
55 }
56
57 ////////////////////////////////////////////////////////////////////////////////
58 //
59 // _HashTableRep::_BucketBase
60 //
61 ////////////////////////////////////////////////////////////////////////////////
62
63 _BucketBase::~_BucketBase()
64 {
65
66 }
67 mike 1.10
68 ////////////////////////////////////////////////////////////////////////////////
69 //
70 // _HashTableIteratorBase
71 //
72 ////////////////////////////////////////////////////////////////////////////////
73
74 _HashTableIteratorBase _HashTableIteratorBase::operator++(int)
75 {
76 _HashTableIteratorBase tmp = *this;
77 operator++();
78 return tmp;
79 }
80
81 _HashTableIteratorBase& _HashTableIteratorBase::operator++()
82 {
83 // At the end?
84
85 if (!_bucket)
86 return *this;
87
88 mike 1.10 // More buckets this chain?
89
90 if ((_bucket = _bucket->next))
91 return *this;
92
93 // Find the next non-empty chain:
94
95 _bucket = 0;
96
97 while (_first != _last)
98 {
99 if (*_first)
100 {
101 _bucket = *_first++;
102 break;
103 }
104
105 _first++;
106 }
107
108 return *this;
109 mike 1.10 }
110
111 _HashTableIteratorBase::_HashTableIteratorBase(
112 _BucketBase** first,
113 _BucketBase** last) : _first(first), _last(last)
114 {
115 _bucket = 0;
116
117 while (_first != last)
118 {
119 if (*_first)
120 {
121 _bucket = *_first++;
122 break;
123 }
124
125 _first++;
126 }
127 }
128
129 ////////////////////////////////////////////////////////////////////////////////
130 mike 1.10 //
131 // _HashTableRep
132 //
133 ////////////////////////////////////////////////////////////////////////////////
134
135 _HashTableRep::_HashTableRep(Uint32 numChains) : _size(0), _numChains(numChains)
136 {
137 if (numChains < 8)
138 numChains = 8;
139
140 _chains = new _BucketBase*[_numChains];
141 memset(_chains, 0, sizeof(_BucketBase*) * _numChains);
142 }
143
144 _HashTableRep::_HashTableRep(const _HashTableRep& x)
145 {
146 _size = 0;
147 _numChains = 0;
148 _chains = 0;
149 operator=(x);
150 }
151 mike 1.10
152 _HashTableRep::~_HashTableRep()
153 {
154 clear();
|
155 konrad.r 1.17 if (_chains)
156 delete [] _chains;
|
157 mike 1.10 }
158
159 _HashTableRep& _HashTableRep::operator=(const _HashTableRep& x)
160 {
161 if (this == &x)
162 return *this;
163
164 // Destroy the old representation:
165
166 clear();
167
168 if (_chains)
169 delete [] _chains;
170
171 // Create chain array:
172
173 _chains = new _BucketBase*[_numChains = x._numChains];
174 memset(_chains, 0, sizeof(_BucketBase*) * _numChains);
175 _size = x._size;
176
177 // Copy over the buckets:
178 mike 1.10
179 for (Uint32 i = 0; i < _numChains; i++)
180 {
181 if (x._chains[i])
182 {
183 _chains[i] = x._chains[i]->clone();
184
185 _BucketBase* curr = _chains[i];
186 _BucketBase* next = x._chains[i]->next;
187
188 for (; next; next = next->next)
189 {
190 curr->next = next->clone();
191 curr = curr->next;
192 }
193 }
194 }
195
196 return *this;
197 }
198
199 mike 1.10 void _HashTableRep::clear()
200 {
201 for (Uint32 i = 0; i < _numChains; i++)
202 {
203 for (_BucketBase* bucket = _chains[i]; bucket; )
204 {
205 _BucketBase* next = bucket->next;
206 delete bucket;
207 bucket = next;
208 }
209 }
210
211 _size = 0;
212
213 if (_numChains)
214 memset(_chains, 0, sizeof(_BucketBase*) * _numChains);
215 }
216
217 Boolean _HashTableRep::insert(
218 Uint32 hashCode,
219 _BucketBase* bucket,
220 mike 1.10 const void* key)
221 {
222 // Check for duplicate entry with same key:
223
224 Uint32 i = hashCode % _numChains;
225 _BucketBase* last = 0;
226
227 for (_BucketBase* b = _chains[i]; b; b = b->next)
228 {
229 if (b->equal(key))
230 {
231 delete bucket;
232 return false;
233 }
234
235 last = b;
236 }
237
238 // Insert bucket:
239
240 bucket->next = 0;
241 mike 1.10
242 if (last)
243 last->next = bucket;
244 else
245 _chains[i] = bucket;
246
247 _size++;
248 return true;
249 }
250
251 const _BucketBase* _HashTableRep::lookup(
252 Uint32 hashCode,
|
253 mike 1.11 const void* key) const
|
254 mike 1.10 {
|
255 gs.keenan 1.16 #ifdef PEGASUS_OS_VMS
256 //
257 // This is to prevent a crash when the hash
258 // code hasn't been initialized!
259 //
260 if (_numChains == 0)
261 {
262 return 0;
263 }
264 #endif
|
265 mike 1.10 Uint32 i = hashCode % _numChains;
266
267 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
268 {
269 if (bucket->equal(key))
270 return bucket;
271 }
272
273 // Not found!
274 return 0;
275 }
276
277 Boolean _HashTableRep::remove(Uint32 hashCode, const void* key)
278 {
279 for (Uint32 i = 0; i < _numChains; i++)
280 {
281 _BucketBase* prev = 0;
282
283 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
284 {
285 if (bucket->equal(key))
286 mike 1.10 {
287 if (prev)
288 prev->next = bucket->next;
289 else
290 _chains[i] = bucket->next;
291
292 delete bucket;
293 _size--;
294 return true;
295 }
296 prev = bucket;
297 }
298 }
299
300 return false;
301 }
302
303 PEGASUS_NAMESPACE_END
|
Return to
HashTable.cpp
CVS log
Up to [Pegasus] / pegasus / src / Pegasus / Common