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