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 mike 1.3 Uint32 HashFunc<String>::hash(const String& str)
|
40 mike 1.1 {
41 Uint32 h = 0;
42
|
43 mike 1.6 for (Uint32 i = 0, n = str.size(); i < n; i++)
|
44 mike 1.1 h = 5 * h + str[i];
45
46 return h;
47 }
48
49 ////////////////////////////////////////////////////////////////////////////////
50 //
|
51 mike 1.3 // _HashTableRep::_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 mike 1.4 _bucket = 0;
108
|
109 mike 1.1 while (_first != last)
110 {
111 if (*_first)
112 {
113 _bucket = *_first++;
114 break;
115 }
116
117 _first++;
118 }
119 }
120
121 ////////////////////////////////////////////////////////////////////////////////
122 //
|
123 mike 1.3 // _HashTableRep
|
124 mike 1.1 //
125 ////////////////////////////////////////////////////////////////////////////////
126
|
127 mike 1.3 _HashTableRep::_HashTableRep(Uint32 numChains) : _size(0), _numChains(numChains)
|
128 mike 1.1 {
129 if (numChains < 8)
130 numChains = 8;
131
|
132 mike 1.2 _chains = new _BucketBase*[_numChains];
133 memset(_chains, 0, sizeof(_BucketBase*) * _numChains);
|
134 mike 1.1 }
135
|
136 mike 1.3 _HashTableRep::_HashTableRep(const _HashTableRep& x)
|
137 mike 1.2 {
138 _size = 0;
139 _numChains = 0;
140 _chains = 0;
141 operator=(x);
142 }
143
|
144 mike 1.3 _HashTableRep::~_HashTableRep()
|
145 mike 1.1 {
146 clear();
|
147 mike 1.2 delete [] _chains;
|
148 mike 1.1 }
149
|
150 mike 1.3 _HashTableRep& _HashTableRep::operator=(const _HashTableRep& x)
|
151 mike 1.1 {
|
152 mike 1.2 if (this == &x)
153 return *this;
154
155 // Destroy the old representation:
156
157 clear();
158
159 if (_chains)
160 delete [] _chains;
161
162 // Create chain array:
163
164 _chains = new _BucketBase*[_numChains = x._numChains];
165 memset(_chains, 0, sizeof(_BucketBase*) * _numChains);
166 _size = x._size;
167
168 // Copy over the buckets:
169
|
170 mike 1.1 for (Uint32 i = 0; i < _numChains; i++)
171 {
|
172 mike 1.2 if (x._chains[i])
|
173 mike 1.1 {
|
174 mike 1.2 _chains[i] = x._chains[i]->clone();
175
176 _BucketBase* curr = _chains[i];
177 _BucketBase* next = x._chains[i]->next;
178
179 for (; next; next = next->next)
180 {
181 curr->next = next->clone();
182 curr = curr->next;
183 }
184 }
185 }
186
187 return *this;
188 }
189
|
190 mike 1.3 void _HashTableRep::clear()
|
191 mike 1.2 {
192 for (Uint32 i = 0; i < _numChains; i++)
193 {
194 for (_BucketBase* bucket = _chains[i]; bucket; )
195 {
196 _BucketBase* next = bucket->next;
|
197 mike 1.1 delete bucket;
198 bucket = next;
199 }
200 }
201
202 _size = 0;
|
203 mike 1.2
204 if (_numChains)
205 memset(_chains, 0, sizeof(_BucketBase*) * _numChains);
|
206 mike 1.1 }
207
|
208 mike 1.3 Boolean _HashTableRep::insert(
|
209 mike 1.1 Uint32 hashCode,
|
210 mike 1.2 _BucketBase* bucket,
|
211 mike 1.1 const void* key)
212 {
213 // Check for duplicate entry with same key:
214
215 Uint32 i = hashCode % _numChains;
|
216 mike 1.2 _BucketBase* last = 0;
|
217 mike 1.1
|
218 mike 1.5 for (_BucketBase* b = _chains[i]; b; b = b->next)
|
219 mike 1.1 {
|
220 mike 1.5 if (b->equal(key))
|
221 mike 1.1 {
222 delete bucket;
223 return false;
224 }
225
|
226 mike 1.5 last = b;
|
227 mike 1.1 }
228
229 // Insert bucket:
230
231 bucket->next = 0;
232
233 if (last)
234 last->next = bucket;
235 else
236 _chains[i] = bucket;
237
238 _size++;
239 return true;
240 }
241
|
242 mike 1.3 const _BucketBase* _HashTableRep::lookup(
|
243 mike 1.1 Uint32 hashCode,
244 const void* key)
245 {
246 Uint32 i = hashCode % _numChains;
247
|
248 mike 1.2 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
|
249 mike 1.1 {
250 if (bucket->equal(key))
251 return bucket;
252 }
253
254 // Not found!
255 return 0;
256 }
257
|
258 mike 1.3 Boolean _HashTableRep::remove(Uint32 hashCode, const void* key)
|
259 mike 1.1 {
260 for (Uint32 i = 0; i < _numChains; i++)
261 {
|
262 mike 1.2 _BucketBase* prev = 0;
|
263 mike 1.1
|
264 mike 1.2 for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
|
265 mike 1.1 {
266 if (bucket->equal(key))
267 {
268 if (prev)
269 prev->next = bucket->next;
270 else
271 _chains[i] = bucket->next;
272
273 delete bucket;
274 _size--;
275 return true;
276 }
277 prev = bucket;
278 }
279 }
280
281 return false;
282 }
283
284 PEGASUS_NAMESPACE_END
|
Return to
HashTable.cpp
CVS log
Up to [Pegasus] / pegasus / src / Pegasus / Common