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           // HashTableBase::BucketBase
 52           //
 53           ////////////////////////////////////////////////////////////////////////////////
 54           
 55           BucketBase::~BucketBase()
 56           {
 57           
 58           }
 59           
 60           ////////////////////////////////////////////////////////////////////////////////
 61           //
 62           // HashTableIteratorBase
 63           //
 64 mike  1.1 ////////////////////////////////////////////////////////////////////////////////
 65           
 66           HashTableIteratorBase HashTableIteratorBase::operator++(int)
 67           {
 68               HashTableIteratorBase tmp = *this;
 69               operator++();
 70               return tmp;
 71           }
 72           
 73           HashTableIteratorBase& HashTableIteratorBase::operator++()
 74           {
 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 mike  1.1     // 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           	}
 96           
 97           	_first++;
 98               }
 99           
100               return *this;
101           }
102           
103           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           // HashTableBase
122           //
123           ////////////////////////////////////////////////////////////////////////////////
124           
125           HashTableBase::HashTableBase(Uint32 numChains) : _size(0), _numChains(numChains)
126           {
127 mike  1.1     if (numChains < 8)
128           	numChains = 8;
129           
130               _chains = new BucketBase*[_numChains];
131               memset(_chains, 0, sizeof(BucketBase*) * _numChains);
132           }
133           
134           HashTableBase::~HashTableBase()
135           {
136               clear();
137           }
138           
139           void HashTableBase::clear()
140           {
141               for (Uint32 i = 0; i < _numChains; i++)
142               {
143           	for (BucketBase* bucket = _chains[i]; bucket; )
144           	{
145           	    BucketBase* next = bucket->next;
146           	    delete bucket;
147           	    bucket = next;
148 mike  1.1 	}
149               }
150           
151               _size = 0;
152               memset(_chains, 0, sizeof(BucketBase*) * _numChains);
153           }
154           
155           Boolean HashTableBase::insert(
156               Uint32 hashCode, 
157               BucketBase* bucket, 
158               const void* key)
159           {
160               // Check for duplicate entry with same key:
161           
162               Uint32 i = hashCode % _numChains;
163               BucketBase* last = 0;
164           
165               for (BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
166               {
167           	if (bucket->equal(key))
168           	{
169 mike  1.1 	    delete bucket;
170           	    return false;
171           	}
172           
173           	last = bucket;
174               }
175           
176               // Insert bucket:
177           
178               bucket->next = 0;
179           
180               if (last)
181           	last->next = bucket;
182               else
183           	_chains[i] = bucket;
184           
185               _size++;
186               return true;
187           }
188           
189           const BucketBase* HashTableBase::lookup(
190 mike  1.1     Uint32 hashCode, 
191               const void* key)
192           {
193               Uint32 i = hashCode % _numChains;
194           
195               for (BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
196               {
197           	if (bucket->equal(key))
198           	    return bucket;
199               }
200           
201               // Not found!
202               return 0;
203           }
204           
205           Boolean HashTableBase::remove(Uint32 hashCode, const void* key)
206           {
207               for (Uint32 i = 0; i < _numChains; i++)
208               {
209           	BucketBase* prev = 0;
210           
211 mike  1.1 	for (BucketBase* bucket = _chains[i]; bucket; bucket = bucket->next)
212           	{
213           	    if (bucket->equal(key))
214           	    {
215           		if (prev)
216           		    prev->next = bucket->next;
217           		else
218           		    _chains[i] = bucket->next;
219           
220           		delete bucket;
221           		_size--;
222           		return true;
223           	    }
224           	    prev = bucket;
225           	}
226               }
227           
228               return false;
229           }
230           
231           PEGASUS_NAMESPACE_END