aboutsummaryrefslogtreecommitdiff
path: root/src/old
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/old/arraylist.cpp100
-rw-r--r--src/old/arraylist.h80
-rw-r--r--src/old/hashfunction.cpp10
-rw-r--r--src/old/hashfunction.h48
-rw-r--r--src/old/hashfunctioncasestring.cpp39
-rw-r--r--src/old/hashfunctioncasestring.h28
-rw-r--r--src/old/hashfunctionint.cpp20
-rw-r--r--src/old/hashfunctionint.h26
-rw-r--r--src/old/hashfunctionstring.cpp51
-rw-r--r--src/old/hashfunctionstring.h27
-rw-r--r--src/old/hashtable.cpp424
-rw-r--r--src/old/hashtable.h308
12 files changed, 0 insertions, 1161 deletions
diff --git a/src/old/arraylist.cpp b/src/old/arraylist.cpp
deleted file mode 100644
index ef21426..0000000
--- a/src/old/arraylist.cpp
+++ /dev/null
@@ -1,100 +0,0 @@
1#include "arraylist.h"
2#include <stdlib.h>
3#include <string.h>
4
5ArrayList::ArrayList( int initSize, int growByFactor )
6{
7 apData = new void *[initSize];
8 nSize = 0;
9 nCapacity = initSize;
10 nGrowByFactor = growByFactor;
11}
12
13ArrayList::~ArrayList( )
14{
15 delete[] apData;
16}
17
18void *ArrayList::getAt( int index )
19{
20 if( index < 0 || index > nSize )
21 return NULL;
22
23 return apData[index];
24}
25
26void ArrayList::append( void *data )
27{
28 insertBefore( data, nSize );
29}
30
31void ArrayList::insertBefore( void *data, int pos )
32{
33 if( pos < 0 || pos > nSize )
34 return;
35
36 checkResize();
37 memmove( &apData[pos+1], &apData[pos], (nSize-pos)*sizeof(void*) );
38 apData[pos] = data;
39 nSize++;
40}
41
42int ArrayList::getSize( )
43{
44 return nSize;
45}
46
47bool ArrayList::isEmpty( )
48{
49 return nSize==0;
50}
51
52void ArrayList::deleteAt( int index )
53{
54 if( index < 0 || index >= nSize )
55 return;
56
57 memmove( &apData[index], &apData[index+1], (nSize-index-1)*sizeof(void *) );
58 nSize--;
59}
60
61void ArrayList::empty()
62{
63 // Probably the easiest as far as things go.
64 nSize = 0;
65}
66
67void ArrayList::resizeTo( int newSize )
68{
69 void **apNew = new void *[newSize];
70 memmove( apNew, apData, nSize*sizeof(void *) );
71 nCapacity = newSize;
72 delete[] apData;
73 apData = apNew;
74}
75
76void ArrayList::checkResize()
77{
78 if( nSize >= nCapacity )
79 {
80 resizeTo( nCapacity + nGrowByFactor );
81 }
82}
83
84void ArrayList::setSize( int newSize )
85{
86 if( newSize < 0 )
87 return;
88
89 nSize = newSize;
90 checkResize();
91}
92
93void ArrayList::setAt( int index, void *data )
94{
95 if( index < 0 || index >= nSize )
96 return;
97
98 apData[index] = data;
99}
100
diff --git a/src/old/arraylist.h b/src/old/arraylist.h
deleted file mode 100644
index 0fda34a..0000000
--- a/src/old/arraylist.h
+++ /dev/null
@@ -1,80 +0,0 @@
1/** \file arraylist.h
2 * Describes the ArrayList class.
3 *@author Mike Buland
4 */
5#ifndef ARRAY_LIST_H
6#define ARRAY_LIST_H
7
8#include "list.h"
9
10/** A simple list which uses an array. This is a great choice if you won't do
11 * a lot of adding and deleting and need a fast random access list. Otherwise
12 * use the LinkedList.
13 *@author Mike Buland
14 */
15class ArrayList : public List
16{
17public:
18 /** Creates an arraylist with some pre-defined specs spelled out.
19 *@param initSize the inital number of elements to allocate.
20 *@param growByFactor How much to increase the size of the array by
21 * each time we run out of room.
22 */
23 ArrayList( int initSize=100, int growByFactor=10 );
24 /**
25 * Destroy the ArrayList
26 */
27 virtual ~ArrayList();
28
29 void *getAt( int nIndex );
30 void append( void *pData );
31 void insertBefore( void *pData, int nPos = 0 );
32 int getSize( );
33 bool isEmpty( );
34 void deleteAt( int nIndex );
35 void empty();
36 void setSize( int nNewSize );
37 void setAt( int nIndex, void *pData );
38
39private:
40 /**
41 * Checks to see if the system needs to be resized, if it does, this will
42 * automatically resize based on your parameters.
43 */
44 void checkResize();
45
46 /**
47 * Resize the system to a specified size. If it is larger, then all data
48 * will be retained, if smaller the elements at the end will be cut off.
49 *@param newSize The number of elements to include after resizing.
50 */
51 void resizeTo( int newSize );
52
53 /**
54 * Actual master array of pointers. This is done to follow the List specs.
55 * All data transactions are performed with pointers or compatable
56 * primitive data-types.
57 */
58 void **apData;
59
60 /**
61 * The number of filled in elements in the array. This is the practical
62 * real size of the ArrayList for all userspace applications.
63 */
64 int nSize;
65
66 /**
67 * The number of elements allocated in memory. Not all of these have to be
68 * filled in, and it is usually larger than nSize so that adding and
69 * deleting elements is fast and easy.
70 */
71 int nCapacity;
72
73 /**
74 * The amount to grow by whenever the array needs resizing.
75 */
76 int nGrowByFactor;
77};
78
79#endif
80
diff --git a/src/old/hashfunction.cpp b/src/old/hashfunction.cpp
deleted file mode 100644
index 51f2259..0000000
--- a/src/old/hashfunction.cpp
+++ /dev/null
@@ -1,10 +0,0 @@
1#include "hashfunction.h"
2
3HashFunction::HashFunction()
4{
5}
6
7HashFunction::~HashFunction()
8{
9}
10
diff --git a/src/old/hashfunction.h b/src/old/hashfunction.h
deleted file mode 100644
index cbcf70f..0000000
--- a/src/old/hashfunction.h
+++ /dev/null
@@ -1,48 +0,0 @@
1#ifndef HASH_FUNCTION
2#define HASH_FUNCTION
3
4/** This represents the shell of a hash function. It must be aggregated in
5 * order to be used. Please read about it's two functions for specificatins
6 * relating to what values will be passed to them and what they should return
7 * for creating your own hash functions.
8 *@author Mike Buland.
9 */
10class HashFunction
11{
12public:
13 /**
14 * Standard Constructor.
15 */
16 HashFunction();
17
18 /**
19 * Standard Deconstructor.
20 */
21 virtual ~HashFunction();
22
23 /** Hashes the value represnted by id. This must return a fairly unique
24 * number in the range of 0-2^32 (or whatever the size of an unsigned long
25 * is on your system) based on the id given. The faster the number changes
26 * the better in a general sence. The return value will be the index
27 * (after probing takes place) to the data assosiated with an id, so this
28 * function should always produce the same number for any given id.
29 *@param id The identifier to use to create a unique numerical identifier.
30 *@returns A mostly unique numerical identifier generated using the given
31 * id.
32 */
33 virtual unsigned long int hash( const void *id ) = 0;
34
35 /** This function must compare two ids in the format that this hashfunction
36 * accepts. For example, if the hash function hashes strings it should
37 * probably { return strcmp( id1, id2 ) == 0 }.
38 *@param id1 One value to use in the comparison
39 *@param id2 Another value to use in the comparison
40 *@returns True if the two values match, otherwise false.
41 */
42 virtual bool cmpIDs( const void *id1, const void *id2 ) = 0;
43
44// virtual void *createPersistantID( const void *id ) = 0;
45// virtual void destroyPersistantID( const void *id ) = 0;
46};
47
48#endif
diff --git a/src/old/hashfunctioncasestring.cpp b/src/old/hashfunctioncasestring.cpp
deleted file mode 100644
index 6361f45..0000000
--- a/src/old/hashfunctioncasestring.cpp
+++ /dev/null
@@ -1,39 +0,0 @@
1#include <stdlib.h>
2#include <string.h>
3#include <ctype.h>
4#include "hashfunctioncasestring.h"
5
6HashFunctionCaseString::HashFunctionCaseString()
7{
8}
9
10HashFunctionCaseString::~HashFunctionCaseString()
11{
12}
13
14unsigned long int HashFunctionCaseString::hash( const void *id )
15{
16 const char *str = (const char *)id;
17 unsigned long int nPos = 0;
18 for( int j = 0; str[j] != '\0'; j++ )
19 {
20 nPos = tolower(str[j]) + (nPos << 6) + (nPos << 16) - nPos;
21// nPos += nPos<<16|(((unsigned long int)tolower(str[j]))<<((j*7)%24));
22 }
23 return nPos;
24}
25
26bool HashFunctionCaseString::cmpIDs( const void *id1, const void *id2 )
27{
28 const char *str1 = (const char *)id1;
29 const char *str2 = (const char *)id2;
30
31 int j;
32 for( j = 0; str1[j] != '\0' && str2[j] != '\0'; j++ )
33 {
34 if( tolower(str1[j]) != tolower(str2[j]) )
35 return false;
36 }
37 return (str1[j]==str2[j]);
38}
39
diff --git a/src/old/hashfunctioncasestring.h b/src/old/hashfunctioncasestring.h
deleted file mode 100644
index 7816a1b..0000000
--- a/src/old/hashfunctioncasestring.h
+++ /dev/null
@@ -1,28 +0,0 @@
1#ifndef HASH_FUNCTION_CASE_STRING
2#define HASH_FUNCTION_CASE_STRING
3
4#include "hashfunction.h"
5
6/** A hash function for string data. This hash function does strings, but is
7 * actually generalized to handle any binary stream of characters terminated
8 * by a null character. This is different than HashFunctionString in that
9 * this does comparisons without regaurd to case.
10 *@author Mike Buland.
11 */
12class HashFunctionCaseString : public HashFunction
13{
14public:
15 /**
16 * Standard Constructor.
17 */
18 HashFunctionCaseString();
19
20 /**
21 * Standard Deconstructor.
22 */
23 virtual ~HashFunctionCaseString();
24 unsigned long int hash( const void *id );
25 bool cmpIDs( const void *id1, const void *id2 );
26};
27
28#endif
diff --git a/src/old/hashfunctionint.cpp b/src/old/hashfunctionint.cpp
deleted file mode 100644
index 4bd0feb..0000000
--- a/src/old/hashfunctionint.cpp
+++ /dev/null
@@ -1,20 +0,0 @@
1#include "hashfunctionint.h"
2
3HashFunctionInt::HashFunctionInt()
4{
5}
6
7HashFunctionInt::~HashFunctionInt()
8{
9}
10
11unsigned long int HashFunctionInt::hash( const void *id )
12{
13 return (unsigned long)(id);
14}
15
16bool HashFunctionInt::cmpIDs( const void *id1, const void *id2 )
17{
18 return (unsigned long)(id1) == (unsigned long)(id2);
19}
20
diff --git a/src/old/hashfunctionint.h b/src/old/hashfunctionint.h
deleted file mode 100644
index 0fbc764..0000000
--- a/src/old/hashfunctionint.h
+++ /dev/null
@@ -1,26 +0,0 @@
1#ifndef HASH_FUNCTION_INT
2#define HASH_FUNCTION_INT
3
4#include "hashfunction.h"
5
6/** A hash function for integer data. Really, this does almost nothing except
7 * ensure we're dealing with positive indicies.
8 *@author Mike Buland.
9 */
10class HashFunctionInt : public HashFunction
11{
12public:
13 /**
14 * Standard Constructor.
15 */
16 HashFunctionInt();
17
18 /**
19 * Standard Deconstructor.
20 */
21 virtual ~HashFunctionInt();
22 unsigned long int hash( const void *id );
23 bool cmpIDs( const void *id1, const void *id2 );
24};
25
26#endif
diff --git a/src/old/hashfunctionstring.cpp b/src/old/hashfunctionstring.cpp
deleted file mode 100644
index bd14643..0000000
--- a/src/old/hashfunctionstring.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
1#include "hashfunctionstring.h"
2#ifndef NULL
3#define NULL ((void *) 0)
4#endif
5
6HashFunctionString::HashFunctionString()
7{
8}
9
10HashFunctionString::~HashFunctionString()
11{
12}
13
14unsigned long int HashFunctionString::hash( const void *id )
15{
16 if (id == NULL)
17 {
18 return 0;
19 }
20
21 unsigned long int nPos = 0;
22 for( const char *s = (const char *)id; *s; s++ )
23 {
24 nPos = *s + (nPos << 6) + (nPos << 16) - nPos;
25 }
26 return nPos;
27}
28
29bool HashFunctionString::cmpIDs( const void *id1, const void *id2 )
30{
31 if (id1 == NULL || id2 == NULL)
32 {
33 return false;
34 }
35 if (id1 == id2)
36 {
37 return true;
38 }
39
40 const char *str1 = (const char *)id1;
41 const char *str2 = (const char *)id2;
42
43 int j;
44 for( j = 0; str1[j] != '\0' && str2[j] != '\0'; j++ )
45 {
46 if( str1[j] != str2[j] )
47 return false;
48 }
49 return (str1[j]==str2[j]);
50}
51
diff --git a/src/old/hashfunctionstring.h b/src/old/hashfunctionstring.h
deleted file mode 100644
index 7d2a1a6..0000000
--- a/src/old/hashfunctionstring.h
+++ /dev/null
@@ -1,27 +0,0 @@
1#ifndef HASH_FUNCTION_STRING
2#define HASH_FUNCTION_STRING
3
4#include "hashfunction.h"
5
6/** A hash function for string data. This hash function does strings, but is
7 * actually generalized to handle any binary stream of characters terminated
8 * by a null character.
9 *@author Mike Buland.
10 */
11class HashFunctionString : public HashFunction
12{
13public:
14 /**
15 * Standard Constructor.
16 */
17 HashFunctionString();
18
19 /**
20 * Standard Deconstructor.
21 */
22 virtual ~HashFunctionString();
23 unsigned long int hash( const void *id );
24 bool cmpIDs( const void *id1, const void *id2 );
25};
26
27#endif
diff --git a/src/old/hashtable.cpp b/src/old/hashtable.cpp
deleted file mode 100644
index dbcd964..0000000
--- a/src/old/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
diff --git a/src/old/hashtable.h b/src/old/hashtable.h
deleted file mode 100644
index 179b694..0000000
--- a/src/old/hashtable.h
+++ /dev/null
@@ -1,308 +0,0 @@
1/**\hashtable.h
2 * Describes the HashFunction, HashFunctionString, and HashTable classes. It
3 * was just easier to put them all in one set of files.
4 *@author Mike Buland
5 */
6
7#ifndef HASH_TABLE_H
8#define HASH_TABLE_H
9
10//Uncomment this line to see a cool text-mode visualization of what's going on
11//#define HASH_DEBUG_VIS 1
12
13#include <stdlib.h>
14#include <string.h>
15#include <ctype.h>
16
17#include "hashfunction.h"
18
19/**
20 * A simple yet flexable hash-table. This uses several tricks to help ensure
21 * that the table is always running at maximum efficiency. You no longer have
22 * to specify a "danger fill level" when more space is needed a rehash is
23 * automatically trigered. Deleting elements is fully supported, as well as
24 * duplicate elements. To work with and allow duplicates simple construct your
25 * HashTable the way you normally would, but when deleting or getting elements
26 * you can specify a skip value. This effectively allows you to treat elements
27 * with duplicate ID's as though they were in a zero-based array. The first
28 * element inserted with a given ID would be at skip zero, the next at skip 1
29 * and so on. This allows you to quickly search for elements with duplicate
30 * names, just stop when you get a null for a skip number, i.e.
31 * <pre>
32 * for( int j = 0;; j++ )
33 * {
34 * void *pData = hash.get( myID, j );
35 * if( !pData ) break;
36 * // Do something interesting with pData
37 * }
38 * </pre>
39 * There are new features in this HashTable that also allow for memory saving
40 * when dealing with systems where many elements are being deleted from the
41 * table. In those cases the elements deleted cannot be simply deleted, instead
42 * they have to be marked as deleted and hidden from the user, but maintained in
43 * the table so that future hashing operations don't fail. When rehashing
44 * occurs all elements marked as deleted are quietly removed. In these cases,
45 * if the number of deleted items would free enough space in the table for the
46 * table to be used efficiently without resizing, it is left the same size and
47 * rehashing is performed effectively in place, allowing the deleted items to
48 * be removed.
49 * <br>
50 * For info on adding new hashing algorithms, please see the HashFunction class.
51 *@author Mike Buland
52 *@todo Fix probing for tables that allow duplicates, and delete an item, then
53 * insert an item with the same name.
54 */
55class HashTable
56{
57public:
58 /** Constructs a hash table.
59 *@param hNewFunc A pointer to a hashfunction class to use. If this is
60 * null the default general string type will be used.
61 *@param nInitSize The initial size of the hashtable.
62 *@param bAllowDupes Setting this value to true allows the system to
63 * insert more than one copy of any given key. This can be tricky, and
64 * will require you to use the nSkip parameter on the get function.
65 */
66 HashTable( HashFunction *hNewFunc, unsigned long int nInitSize, bool bAllowDupes=false );
67
68 /**
69 * Destroys the hashtable, cleaning up all internal storage, but not stored
70 * elements. Also deletes the HashFunction passed in in the constructor.
71 */
72 virtual ~HashTable();
73
74 /** Inserts an item into the hashtable. This function will trigger a
75 * rehash if adding another item would force the table's load factor over
76 * the danger level.
77 *@param id used to find the data later.
78 *@param data The data item to insert into the table with the identifier
79 * id
80 *@returns True if insertion was successfull, and false if it failed.
81 */
82 bool insert( const void *id, const void *data );
83
84 /** Gets an item in the hashtable based on the id of that item. If there
85 * is more than one item with the same id you can use the nSkip parameter
86 * to access all of them.
87 *@param id The id of the item you're trying to find.
88 *@param nSkip The number of items with that id to skip before returning
89 * with the requested item.
90 *@returns A pointer to the data stored at the given id.
91 */
92 const void *get( const void *id, unsigned long int nSkip=0 );
93
94 const void *getKey( const void *id, unsigned long int nSkip=0 );
95
96 /** Gets the total capacity of the hashtable. This is actually the number
97 * of total positions available inside the hashtable at the moment. This
98 * will change when the hashtable's load exceeds the danger level.
99 * Please note that this is NOT the actual amount of space available.
100 * In reality you can only access about 45-50 percent of that space.
101 *@returns The total capacity.
102 */
103 unsigned long int getCapacity();
104
105 /** Gets the number of filled in items in the hash table. This is roughly
106 * equivelent to the getSize function assosiated with the Lists.
107 *@returns The number of filled in items in the hash table.
108 */
109 unsigned long int getSize();
110
111 /** Gets the load (percentage) of filled in items in the table. This is
112 * technically the size divided by the capacity, but is definately usefull
113 * since it's required to check if it's time to rehash.
114 *@returns The table load in the range 0.0 to 1.0
115 */
116 double getLoad();
117
118 /** Sets up an xPos object for use indexing the items in the table. Call
119 * this first and follow the directions for getNextItemPos below to
120 * iterate through every item in the table, while avoiding the empty
121 * spaces.
122 *@returns A pointer to a xPos object telling the hashtable where to find
123 * the item you're looking at.
124 */
125 void *getFirstItemPos();
126
127 /** Get the item's data that is being pointed to by xPos. This is only
128 * valid after xPos was created using getFirstItemPos and getNextItemPos
129 * was called at least once.
130 *@param xPos supplied by getFirstItemPos.
131 *@returns The key value that was used to insert the data into the table.
132 */
133 const void *getItemData( void *xPos );
134
135 /** Get the item's ID that is being pointed to by xPos. This is only
136 * valid after xPos was created using getFirstItemPos and getNextItemPos
137 * was called at least once.
138 *@param xPos supplied by getFirstItemPos.
139 *@returns The key value that was used to insert the data into the table.
140 */
141 const void *getItemID( void *xPos );
142
143 /** Used for iterating through a hash table sequentially. This will
144 * update the xPos pointer to point to the next time, all ready to
145 * be accessed with getItemID and getItemData. This must be called at
146 * least once before xPos is meaningful, and will return a NULL when it
147 * has reached the last item.
148 *@param xPos This must be an object created by a call to the function
149 * getFirstItemPos, and is only meaningful to the internal routines.
150 * Aborting a call in the middle (not running to the end of the table)
151 * may result in a memory leak at the moment.
152 *@returns xPos if still iterating through the list, otherwise it will
153 * return NULL when the end has been reached and the xPos variable has
154 * been deleted.
155 */
156 void *getNextItemPos( void *xPos );
157
158 /** A helpful operator to make accessing items easier. Please note that
159 * this simply returns a pointer to the data stored internally, and cannot
160 * be used like the STL operator to store new data, use insert for that.
161 *@param id The identifier used to store the requested item.
162 *@returns The data value assosiated with the given id, or NULL if it
163 * wasn't found in the table.
164 */
165 const void *operator[](const void *id);
166
167 /**
168 * Delete the specified item from the hashtable. This actually keeps the
169 * data and marks it deleted. For all intents and purposes to the user it
170 * is deleted, except that the space is still used until a rehash is forced.
171 * This means that in hashtables where elements are being inserted and
172 * deleted frequently you may run into a higher rate of expansion.
173 *@param id The ID to delete.
174 *@param nSkip The number of similar id's to skip before deleting in a
175 * hashtable that allows duplicates.
176 *@returns True if the element was found and deleted, false otherwise.
177 */
178 bool del( const void *id, int nSkip=0 );
179
180 /**
181 * Deletes every entry in the hash table. See the notes on del to see what
182 * this means, except that since no data is being kept, the entire table is
183 * just marked as usable space.
184 */
185 void clear();
186
187private:
188 /**
189 * Contains info related to a position in the hashtable. Used for
190 * searching through hashtables one item at a time, in order. This class
191 * should never be created by anything but a HashTable, and should never
192 * be referenced directly. Instead the hashtable returns a void pointer,
193 * which is what should be passed back in next time you use a search
194 * function. Always finish a search, since the object is deleted at the
195 * end of the search.
196 *@author Mike Buland
197 */
198 class HashPos
199 {
200 public:
201 /** Create a blank HashPos. */
202 HashPos() { bStarted=false; nPos = 0; };
203 /** Has the search been started? */
204 bool bStarted;
205 /** The position (index) into the backend storage structure. */
206 unsigned long int nPos;
207 };
208
209 /**
210 * All data related to a single element in the hashtable. This should
211 * really only be used and manipulated by the HashTable itself.
212 *@author Mike Buland
213 */
214 typedef struct HashNode
215 {
216 public:
217 /** Create a new, empty HashNode. */
218 HashNode() { id = NULL; data = NULL; bDeleted = false; };
219 /** A pointer to the original ID that was used to key the data. */
220 const void *id;
221 /** A pointer to the data stored along with the above ID. */
222 const void *data;
223 /** Weather or not this data should really...exist */
224 bool bDeleted;
225 } HashNode;
226
227private:
228 /**
229 * Just sets the values in the element to some friendly values.
230 *@param newID The new ID to store.
231 *@param newData The new Data to store.
232 */
233 void set( int j, const void *newID, const void *newData );
234 /**
235 * Tells you if the node is filled or not.
236 *@returns True=an ID has been stored here, False=no ID.
237 */
238 bool isFilled( int j );
239 /**
240 * This actually resizes, but since every resize requires a reHash to go
241 * along with it, that's the name. This actually creates a new buffer for
242 * all of the contained data and then pulls every old element that was in
243 * the old table out and performs the hashing placement calculations again.
244 * This function skips all data that was marked as deleted, so at this
245 * point it really will be.
246 *@param nNewSize The new size to set the table to while re-hashing.
247 *@returns True if the operation was successful, false otherwise.
248 */
249 void reHash( unsigned long int nNewSize );
250
251 /**
252 * Helper function to allocate a new table. Really just does the memory
253 * allocation.
254 *@param nNewSize The size of the table to generate.
255 *@returns A new, blank array of HashNode objects the size you specified.
256 */
257 HashNode *newTable( unsigned long int nNewSize );
258
259 /**
260 * This function is used once an actual hash code is obtained. nStart is
261 * the given hash code, which is then wrapped to the size of the table. If
262 * there is data at that location, tests are performed to see if it's the
263 * right one. If it is, then it is returned, otherwise a series of further
264 * tests based on a 2^n search pattern is performed. The position of the
265 * requested data in the back-end storage is returned if found, otherwise
266 * another less useful value is returned...
267 *@param nStart The initial hashcode of the ID testing for.
268 *@param id A pointer to the id that is being searched for.
269 *@returns The real location of the data requested.
270 */
271 unsigned long int probe( unsigned long int nStart, const void *id );
272
273 /**
274 * Simple helper function to determine if a number is prime or not.
275 * This function runs in sqrt(n) time.
276 *@param num Number to test for prime-hood.
277 *@returns True if the number is prime, false otherwise.
278 */
279 bool isPrime( int num );
280
281 /**
282 * Given any number, this function finds the first number after it that is
283 * prime. Since this number is a multiple internally it's rare that the
284 * starting number would be prime.
285 *@param base The number to start the prime search on.
286 *@returns The first prime after the number given.
287 */
288 int nextPrime( int base );
289
290#ifdef HASH_DEBUG_VIS
291 void printDebugLine( const char *exData );
292#endif
293
294 /** A pointer to the HashFunction subclass instance to use. */
295 HashFunction *hFunc;
296 /** The complete array of HashNode objects to store data in. */
297 HashNode *aTable;
298 /** The actual size of the table, not how many elements are in it. */
299 unsigned long int nTableSize;
300 /** The number of elements that are in the table. */
301 unsigned long int nSize;
302 /** The number of elements that are unavailable now. */
303 unsigned long int nFilled;
304 /** Allow duplicate ID's in the table. */
305 bool bAllowDupes;
306};
307
308#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 18:04:35 +0000