1 mike  1.7 //%/////////////////////////////////////////////////////////////////////////////
  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.7 //
 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.7 
 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.7 //
 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.7 
 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.7     _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.7 
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.7     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.7     // 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.7 
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.7     _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.7     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, 
245               const void* key)
246           {
247               Uint32 i = hashCode % _numChains;
248           
249               for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
250               {
251           	if (bucket->equal(key))
252           	    return bucket;
253 mike  1.7     }
254           
255               // Not found!
256               return 0;
257           }
258           
259           Boolean _HashTableRep::remove(Uint32 hashCode, const void* key)
260           {
261               for (Uint32 i = 0; i < _numChains; i++)
262               {
263           	_BucketBase* prev = 0;
264           
265           	for (_BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
266           	{
267           	    if (bucket->equal(key))
268           	    {
269           		if (prev)
270           		    prev->next = bucket->next;
271           		else
272           		    _chains[i] = bucket->next;
273           
274 mike  1.7 		delete bucket;
275           		_size--;
276           		return true;
277           	    }
278           	    prev = bucket;
279           	}
280               }
281           
282               return false;
283           }
284           
285           PEGASUS_NAMESPACE_END