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