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 #include <cstring>
29 #include "HashTable.h"
30
31 PEGASUS_NAMESPACE_BEGIN
32
33 ////////////////////////////////////////////////////////////////////////////////
34 //
35 // Hash()
36 //
37 ////////////////////////////////////////////////////////////////////////////////
38
39 Uint32 Hash(const String& str)
40 {
41 Uint32 h = 0;
42
43 mike 1.1 for (Uint32 i = 0, n = str.getLength(); i < n; i++)
44 h = 5 * h + str[i];
45
46 return h;
47 }
48
49 ////////////////////////////////////////////////////////////////////////////////
50 //
|
51 mike 1.2 // _HashTableBase::_BucketBase
|
52 mike 1.1 //
53 ////////////////////////////////////////////////////////////////////////////////
54
|
55 mike 1.2 _BucketBase::~_BucketBase()
|
56 mike 1.1 {
57
58 }
59
60 ////////////////////////////////////////////////////////////////////////////////
61 //
|
62 mike 1.2 // _HashTableIteratorBase
|
63 mike 1.1 //
64 ////////////////////////////////////////////////////////////////////////////////
65
|
66 mike 1.2 _HashTableIteratorBase _HashTableIteratorBase::operator++(int)
|
67 mike 1.1 {
|
68 mike 1.2 _HashTableIteratorBase tmp = *this;
|
69 mike 1.1 operator++();
70 return tmp;
71 }
72
|
73 mike 1.2 _HashTableIteratorBase& _HashTableIteratorBase::operator++()
|
74 mike 1.1 {
75 // At the end?
76
77 if (!_bucket)
78 return *this;
79
80 // More buckets this chain?
81
82 if ((_bucket = _bucket->next))
83 return *this;
84
85 // Find the next non-empty chain:
86
87 _bucket = 0;
88
89 while (_first != _last)
90 {
91 if (*_first)
92 {
93 _bucket = *_first++;
94 break;
95 mike 1.1 }
96
97 _first++;
98 }
99
100 return *this;
101 }
102
|
103 mike 1.2 _HashTableIteratorBase::_HashTableIteratorBase(
104 _BucketBase** first,
105 _BucketBase** last) : _first(first), _last(last)
|
106 mike 1.1 {
107 while (_first != last)
108 {
109 if (*_first)
110 {
111 _bucket = *_first++;
112 break;
113 }
114
115 _first++;
116 }
117 }
118
119 ////////////////////////////////////////////////////////////////////////////////
120 //
|
121 mike 1.2 // _HashTableBase
|
122 mike 1.1 //
123 ////////////////////////////////////////////////////////////////////////////////
124
|
125 mike 1.2 _HashTableBase::_HashTableBase(Uint32 numChains) : _size(0), _numChains(numChains)
|
126 mike 1.1 {
127 if (numChains < 8)
128 numChains = 8;
129
|
130 mike 1.2 _chains = new _BucketBase*[_numChains];
131 memset(_chains, 0, sizeof(_BucketBase*) * _numChains);
|
132 mike 1.1 }
133
|
134 mike 1.2 _HashTableBase::_HashTableBase(const _HashTableBase& x)
135 {
136 _size = 0;
137 _numChains = 0;
138 _chains = 0;
139 operator=(x);
140 }
141
142 _HashTableBase::~_HashTableBase()
|
143 mike 1.1 {
144 clear();
|
145 mike 1.2 delete [] _chains;
|
146 mike 1.1 }
147
|
148 mike 1.2 _HashTableBase& _HashTableBase::operator=(const _HashTableBase& x)
|
149 mike 1.1 {
|
150 mike 1.2 if (this == &x)
151 return *this;
152
153 // Destroy the old representation:
154
155 clear();
156
157 if (_chains)
158 delete [] _chains;
159
160 // Create chain array:
161
162 _chains = new _BucketBase*[_numChains = x._numChains];
163 memset(_chains, 0, sizeof(_BucketBase*) * _numChains);
164 _size = x._size;
165
166 // Copy over the buckets:
167
|
168 mike 1.1 for (Uint32 i = 0; i < _numChains; i++)
169 {
|
170 mike 1.2 if (x._chains[i])
|
171 mike 1.1 {
|
172 mike 1.2 _chains[i] = x._chains[i]->clone();
173
174 _BucketBase* curr = _chains[i];
175 _BucketBase* next = x._chains[i]->next;
176
177 for (; next; next = next->next)
178 {
179 curr->next = next->clone();
180 curr = curr->next;
181 }
182 }
183 }
184
185 return *this;
186 }
187
188 void _HashTableBase::clear()
189 {
190 for (Uint32 i = 0; i < _numChains; i++)
191 {
192 for (_BucketBase* bucket = _chains[i]; bucket; )
193 mike 1.2 {
194 _BucketBase* next = bucket->next;
|
195 mike 1.1 delete bucket;
196 bucket = next;
197 }
198 }
199
200 _size = 0;
|
201 mike 1.2
202 if (_numChains)
203 memset(_chains, 0, sizeof(_BucketBase*) * _numChains);
|
204 mike 1.1 }
205
|
206 mike 1.2 Boolean _HashTableBase::insert(
|
207 mike 1.1 Uint32 hashCode,
|
208 mike 1.2 _BucketBase* bucket,
|
209 mike 1.1 const void* key)
210 {
211 // Check for duplicate entry with same key:
212
213 Uint32 i = hashCode % _numChains;
|
214 mike 1.2 _BucketBase* last = 0;
|
215 mike 1.1
|
216 mike 1.2 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
|
217 mike 1.1 {
218 if (bucket->equal(key))
219 {
220 delete bucket;
221 return false;
222 }
223
224 last = bucket;
225 }
226
227 // Insert bucket:
228
229 bucket->next = 0;
230
231 if (last)
232 last->next = bucket;
233 else
234 _chains[i] = bucket;
235
236 _size++;
237 return true;
238 mike 1.1 }
239
|
240 mike 1.2 const _BucketBase* _HashTableBase::lookup(
|
241 mike 1.1 Uint32 hashCode,
242 const void* key)
243 {
244 Uint32 i = hashCode % _numChains;
245
|
246 mike 1.2 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
|
247 mike 1.1 {
248 if (bucket->equal(key))
249 return bucket;
250 }
251
252 // Not found!
253 return 0;
254 }
255
|
256 mike 1.2 Boolean _HashTableBase::remove(Uint32 hashCode, const void* key)
|
257 mike 1.1 {
258 for (Uint32 i = 0; i < _numChains; i++)
259 {
|
260 mike 1.2 _BucketBase* prev = 0;
|
261 mike 1.1
|
262 mike 1.2 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
|
263 mike 1.1 {
264 if (bucket->equal(key))
265 {
266 if (prev)
267 prev->next = bucket->next;
268 else
269 _chains[i] = bucket->next;
270
271 delete bucket;
272 _size--;
273 return true;
274 }
275 prev = bucket;
276 }
277 }
278
279 return false;
280 }
281
282 PEGASUS_NAMESPACE_END
|
Return to
HashTable.cpp
CVS log
Up to [Pegasus] / pegasus / src / Pegasus / Common