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