aboutsummaryrefslogtreecommitdiff
path: root/src/hashtable.cpp
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2007-04-03 03:49:53 +0000
committerMike Buland <eichlan@xagasoft.com>2007-04-03 03:49:53 +0000
commitf4c20290509d7ed3a8fd5304577e7a4cc0b9d974 (patch)
tree13cdf64f7cf134f397a7165b7a3fe0807e37026b /src/hashtable.cpp
parent74d4c8cd27334fc7204d5a8773deb3d424565778 (diff)
downloadlibbu++-f4c20290509d7ed3a8fd5304577e7a4cc0b9d974.tar.gz
libbu++-f4c20290509d7ed3a8fd5304577e7a4cc0b9d974.tar.bz2
libbu++-f4c20290509d7ed3a8fd5304577e7a4cc0b9d974.tar.xz
libbu++-f4c20290509d7ed3a8fd5304577e7a4cc0b9d974.zip
Ok, no code is left in src, it's all in src/old. We'll gradually move code back
into src as it's fixed and re-org'd. This includes tests, which, I may write a unit test system into libbu++ just to make my life easier.
Diffstat (limited to 'src/hashtable.cpp')
-rw-r--r--src/hashtable.cpp424
1 files changed, 0 insertions, 424 deletions
diff --git a/src/hashtable.cpp b/src/hashtable.cpp
deleted file mode 100644
index dbcd964..0000000
--- a/src/hashtable.cpp
+++ /dev/null
@@ -1,424 +0,0 @@
1#include <string.h>
2#include <stdio.h>
3#include <math.h>
4
5#include "hashtable.h"
6
7HashTable::HashTable( HashFunction *hNewFunc, unsigned long int nInitSize, bool bAllowDupes )
8{
9 hFunc = hNewFunc;
10 nTableSize = nextPrime( nInitSize );
11 aTable = new HashNode[nTableSize];
12 //for( int j = 0; j < nTableSize; j++ ) if( aTable[j].id || aTable[j].data || aTable[j].bDeleted ) printf("Unclean entry\n");
13 nSize = 0;
14 nFilled = 0;
15 this->bAllowDupes = bAllowDupes;
16}
17
18HashTable::~HashTable()
19{
20 delete[] aTable;
21 delete hFunc;
22}
23
24void HashTable::set( int j, const void *newID, const void *newData )
25{
26 if( newData == NULL )
27 {
28 printf("Inserting NULL data is indestinguishable from uninserted data!\n");
29 }
30 aTable[j].id = newID;
31 aTable[j].data = newData;
32}
33
34void HashTable::clear()
35{
36 memset( aTable, 0, sizeof(HashNode) * nTableSize );
37}
38
39bool HashTable::isFilled( int j )
40{
41 return (aTable[j].id != NULL)||(aTable[j].bDeleted);
42}
43
44void HashTable::reHash( unsigned long int nNewSize )
45{
46 HashNode *aOldTable = aTable;
47 unsigned long int oldSize = nTableSize;
48
49 // If the table can still be used if we just get rid of deleted items, don't
50 // change the size of the table, otherwise, go ahead and use the number
51 // passed in.
52 if( nSize > nTableSize>>1 )
53 {
54 nTableSize = nextPrime( nNewSize );
55 }
56
57 aTable = newTable( nTableSize );
58 //for( int j = 0; j < nTableSize; j++ ) if( aTable[j].id || aTable[j].data || aTable[j].bDeleted ) printf("Unclean entry\n");
59
60 nSize = 0;
61 nFilled = 0;
62
63 for( unsigned long int j = 0; j < oldSize; j++ )
64 {
65 if( aOldTable[j].id != NULL && aOldTable[j].bDeleted == false )
66 {
67 insert( aOldTable[j].id, aOldTable[j].data );
68 }
69 }
70
71 delete[] aOldTable;
72}
73
74unsigned long int HashTable::probe( unsigned long int nStart, const void *id )
75{
76 int nHash = nStart;
77 nStart = nStart%nTableSize;
78 if( bAllowDupes == true )
79 {
80 for(
81 unsigned long int j=0;
82 isFilled( nStart ) && j < 32;
83 nStart = (nStart+(1<<j))%nTableSize, j++
84 );
85
86 /**
87 * This is an ugly little hack. If the hash table is too full in allow-
88 * dups mode we have to fall back on a linear search, otherwise you can
89 * only get up to 32 entries with the same name.
90 */
91 if( isFilled( nStart ) )
92 {
93 unsigned long int nOldStart = nStart;
94 for(
95 nStart++;
96 isFilled( nStart ) && nStart != nOldStart;
97 nStart = (nStart+1)%nTableSize
98 );
99 }
100 }
101 else
102 {
103 for(
104 unsigned long int j=0;
105 isFilled( nStart ) && j < 32;
106 nStart = (nStart+(1<<j))%nTableSize, j++
107 )
108 {
109 if( isFilled( nStart ) )
110 {
111 if( hFunc->cmpIDs( aTable[nStart].id, id ) == true &&
112 aTable[nStart].bDeleted == false )
113 {
114 return nStart;
115 }
116 }
117 }
118 }
119 // This is our insurance, if the table is full, then go ahead and rehash,
120 // then try again.
121 if( isFilled( nStart ) )
122 {
123 reHash( getCapacity()*2 );
124 return probe( nHash, id );
125 }
126 return nStart;
127}
128
129HashTable::HashNode *HashTable::newTable( unsigned long int nNewSize )
130{
131 return new HashNode[nNewSize];
132}
133
134#ifdef HASH_DEBUG_VIS
135void HashTable::printDebugLine( const char *exData )
136{
137 char *buf = new char[getCapacity()+3];
138 int j;
139 buf[0] = '[';
140 for( j = 0; j < getCapacity(); j++ )
141 {
142 buf[j+1] = (aTable[j].bDeleted)?('X'):((isFilled( j ))?('#'):('-'));
143 }
144 buf[j+1] = ']';
145 buf[j+2] = '\0';
146 printf("%s %s\n", buf, exData );
147 delete[] buf;
148}
149#endif
150
151bool HashTable::insert( const void *id, const void *data )
152{
153 unsigned long int nPos = probe( hFunc->hash( id ), id )%nTableSize;
154
155 if( bAllowDupes == true )
156 {
157 if( aTable[nPos].id == NULL && aTable[nPos].bDeleted == false )
158 {
159 set( nPos, id, data );
160#ifdef HASH_DEBUG_VIS
161 printDebugLine( (const char *)id );
162#endif
163 nSize++;
164 nFilled++;
165 return true;
166 }
167 else
168 {
169 return false;
170 }
171 }
172 else
173 {
174 if( aTable[nPos].id == NULL && aTable[nPos].bDeleted == false )
175 {
176 set( nPos, id, data );
177#ifdef HASH_DEBUG_VIS
178 printDebugLine( (const char *)id );
179#endif
180 nSize++;
181 nFilled++;
182 return true;
183 }
184 else if( hFunc->cmpIDs( aTable[nPos].id, id ) == true )
185 {
186 set( nPos, id, data );
187#ifdef HASH_DEBUG_VIS
188 printDebugLine( (const char *)id );
189#endif
190 return true;
191 }
192 else
193 {
194 return false;
195 }
196 }
197}
198
199const void *HashTable::get( const void *id, unsigned long int nSkip )
200{
201 unsigned long int nPos = hFunc->hash( id )%nTableSize;
202
203 for( unsigned long int j=0; j < 32; nPos = (nPos+(1<<j))%nTableSize, j++ )
204 {
205 if( !isFilled( nPos ) ) return NULL;
206 if( aTable[nPos].bDeleted == false )
207 {
208 if( hFunc->cmpIDs( id, aTable[nPos].id ) )
209 {
210 if( nSkip == 0 )
211 {
212 return aTable[nPos].data;
213 }
214 else
215 {
216 nSkip--;
217 }
218 }
219 }
220 }
221
222 if( bAllowDupes )
223 {
224 unsigned long int nOldPos = nPos;
225 for( nPos++; nPos != nOldPos; nPos=(nPos+1)%nTableSize )
226 {
227 if( !isFilled( nPos ) ) return NULL;
228 if( aTable[nPos].bDeleted == false )
229 {
230 if( hFunc->cmpIDs( id, aTable[nPos].id ) )
231 {
232 if( nSkip == 0 )
233 {
234 return aTable[nPos].data;
235 }
236 else
237 {
238 nSkip--;
239 }
240 }
241 }
242 }
243 }
244
245 return NULL;
246}
247
248const void *HashTable::getKey( const void *id, unsigned long int nSkip )
249{
250 unsigned long int nPos = hFunc->hash( id )%nTableSize;
251
252 for( unsigned long int j=0; j < 32; nPos = (nPos+(1<<j))%nTableSize, j++ )
253 {
254 if( !isFilled( nPos ) ) return NULL;
255 if( aTable[nPos].bDeleted == false )
256 {
257 if( hFunc->cmpIDs( id, aTable[nPos].id ) )
258 {
259 if( nSkip == 0 )
260 {
261 return aTable[nPos].id;
262 }
263 else
264 {
265 nSkip--;
266 }
267 }
268 }
269 }
270
271 if( bAllowDupes )
272 {
273 unsigned long int nOldPos = nPos;
274 for( nPos++; nPos != nOldPos; nPos=(nPos+1)%nTableSize )
275 {
276 if( !isFilled( nPos ) ) return NULL;
277 if( aTable[nPos].bDeleted == false )
278 {
279 if( hFunc->cmpIDs( id, aTable[nPos].id ) )
280 {
281 if( nSkip == 0 )
282 {
283 return aTable[nPos].id;
284 }
285 else
286 {
287 nSkip--;
288 }
289 }
290 }
291 }
292 }
293
294 return NULL;
295}
296
297void *HashTable::getFirstItemPos()
298{
299 HashPos *pos = new HashPos;
300 return pos;
301}
302
303const void *HashTable::getItemData( void *xPos )
304{
305 return aTable[((HashPos *)xPos)->nPos].data;
306}
307
308const void *HashTable::getItemID( void *xPos )
309{
310 return aTable[((HashPos *)xPos)->nPos].id;
311}
312
313void *HashTable::getNextItemPos( void *xPos )
314{
315 HashPos *pos = (HashPos *)xPos;
316 if( pos->bStarted == false )
317 {
318 pos->bStarted = true;
319 pos->nPos = 0;
320 }
321 else
322 {
323 pos->nPos++;
324 }
325 if( pos->nPos < nTableSize )
326 {
327 for( ; pos->nPos < nTableSize; pos->nPos++ )
328 {
329 if( isFilled( pos->nPos ) &&
330 aTable[pos->nPos].bDeleted == false )
331 {
332 return xPos;
333 }
334 }
335 }
336
337 delete pos;
338
339 return NULL;
340}
341
342// Big-O sqrt(n)
343// Change this to be erethpothynies table with a storage
344// lookup later on.
345bool HashTable::isPrime (int num)
346{
347 if (num == 2) // the only even prime
348 return true;
349 else if (num % 2 == 0) // other even numbers are composite
350 return false;
351 else
352 {
353 //bool prime = true;
354 int divisor = 3;
355 int upperLimit = static_cast<int>(sqrt(num) + 1);
356 while (divisor <= upperLimit)
357 {
358 if (num % divisor == 0)
359 return false;
360 // prime = false;
361 divisor +=2;
362 }
363 return true;
364 }
365}
366
367// Big-O n^(3/2)
368int HashTable::nextPrime( int base )
369{
370 int nPrime;
371 for( nPrime = base; isPrime( nPrime ) == false; nPrime++ );
372 return nPrime;
373}
374
375unsigned long int HashTable::getCapacity()
376{
377 return nTableSize;
378}
379
380unsigned long int HashTable::getSize()
381{
382 return nSize;
383}
384
385double HashTable::getLoad()
386{
387 return (double)(nFilled)/(double)(nTableSize);
388}
389
390const void *HashTable::operator[](const void *id)
391{
392 return get( id );
393}
394
395bool HashTable::del( const void *id, int nSkip )
396{
397 unsigned long int nPos = hFunc->hash( id )%nTableSize;
398
399 for( unsigned long int j=0; j < 32; nPos = (nPos+(1<<j))%nTableSize, j++ )
400 {
401 if( !isFilled( nPos ) ) return false;
402 //printf("0x%08X \"%s\" == 0x%08X \"%s\" (%d)\n", id, id, aTable[nPos].id, aTable[nPos].id, nPos );
403 if( hFunc->cmpIDs( id, aTable[nPos].id ) &&
404 aTable[nPos].bDeleted == false )
405 {
406 if( nSkip == 0 )
407 {
408 aTable[nPos].bDeleted = true;
409 nSize--;
410#ifdef HASH_DEBUG_VIS
411 printDebugLine( (const char *)id );
412#endif
413 return true;
414 }
415 else
416 {
417 nSkip--;
418 }
419 }
420 }
421
422 return false;
423}
424
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 08:06:12 +0000