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