From 997f13ec4791adcda91cd4db41cdb5962b73d47d Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Tue, 3 Apr 2007 05:10:59 +0000 Subject: Just deleted a few things from old that definately have to go. --- src/old/arraylist.cpp | 100 --------- src/old/arraylist.h | 80 ------- src/old/hashfunction.cpp | 10 - src/old/hashfunction.h | 48 ----- src/old/hashfunctioncasestring.cpp | 39 ---- src/old/hashfunctioncasestring.h | 28 --- src/old/hashfunctionint.cpp | 20 -- src/old/hashfunctionint.h | 26 --- src/old/hashfunctionstring.cpp | 51 ----- src/old/hashfunctionstring.h | 27 --- src/old/hashtable.cpp | 424 ------------------------------------- src/old/hashtable.h | 308 --------------------------- 12 files changed, 1161 deletions(-) delete mode 100644 src/old/arraylist.cpp delete mode 100644 src/old/arraylist.h delete mode 100644 src/old/hashfunction.cpp delete mode 100644 src/old/hashfunction.h delete mode 100644 src/old/hashfunctioncasestring.cpp delete mode 100644 src/old/hashfunctioncasestring.h delete mode 100644 src/old/hashfunctionint.cpp delete mode 100644 src/old/hashfunctionint.h delete mode 100644 src/old/hashfunctionstring.cpp delete mode 100644 src/old/hashfunctionstring.h delete mode 100644 src/old/hashtable.cpp delete mode 100644 src/old/hashtable.h (limited to 'src/old') 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 @@ -#include "arraylist.h" -#include -#include - -ArrayList::ArrayList( int initSize, int growByFactor ) -{ - apData = new void *[initSize]; - nSize = 0; - nCapacity = initSize; - nGrowByFactor = growByFactor; -} - -ArrayList::~ArrayList( ) -{ - delete[] apData; -} - -void *ArrayList::getAt( int index ) -{ - if( index < 0 || index > nSize ) - return NULL; - - return apData[index]; -} - -void ArrayList::append( void *data ) -{ - insertBefore( data, nSize ); -} - -void ArrayList::insertBefore( void *data, int pos ) -{ - if( pos < 0 || pos > nSize ) - return; - - checkResize(); - memmove( &apData[pos+1], &apData[pos], (nSize-pos)*sizeof(void*) ); - apData[pos] = data; - nSize++; -} - -int ArrayList::getSize( ) -{ - return nSize; -} - -bool ArrayList::isEmpty( ) -{ - return nSize==0; -} - -void ArrayList::deleteAt( int index ) -{ - if( index < 0 || index >= nSize ) - return; - - memmove( &apData[index], &apData[index+1], (nSize-index-1)*sizeof(void *) ); - nSize--; -} - -void ArrayList::empty() -{ - // Probably the easiest as far as things go. - nSize = 0; -} - -void ArrayList::resizeTo( int newSize ) -{ - void **apNew = new void *[newSize]; - memmove( apNew, apData, nSize*sizeof(void *) ); - nCapacity = newSize; - delete[] apData; - apData = apNew; -} - -void ArrayList::checkResize() -{ - if( nSize >= nCapacity ) - { - resizeTo( nCapacity + nGrowByFactor ); - } -} - -void ArrayList::setSize( int newSize ) -{ - if( newSize < 0 ) - return; - - nSize = newSize; - checkResize(); -} - -void ArrayList::setAt( int index, void *data ) -{ - if( index < 0 || index >= nSize ) - return; - - apData[index] = data; -} - 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 @@ -/** \file arraylist.h - * Describes the ArrayList class. - *@author Mike Buland - */ -#ifndef ARRAY_LIST_H -#define ARRAY_LIST_H - -#include "list.h" - -/** A simple list which uses an array. This is a great choice if you won't do - * a lot of adding and deleting and need a fast random access list. Otherwise - * use the LinkedList. - *@author Mike Buland - */ -class ArrayList : public List -{ -public: - /** Creates an arraylist with some pre-defined specs spelled out. - *@param initSize the inital number of elements to allocate. - *@param growByFactor How much to increase the size of the array by - * each time we run out of room. - */ - ArrayList( int initSize=100, int growByFactor=10 ); - /** - * Destroy the ArrayList - */ - virtual ~ArrayList(); - - void *getAt( int nIndex ); - void append( void *pData ); - void insertBefore( void *pData, int nPos = 0 ); - int getSize( ); - bool isEmpty( ); - void deleteAt( int nIndex ); - void empty(); - void setSize( int nNewSize ); - void setAt( int nIndex, void *pData ); - -private: - /** - * Checks to see if the system needs to be resized, if it does, this will - * automatically resize based on your parameters. - */ - void checkResize(); - - /** - * Resize the system to a specified size. If it is larger, then all data - * will be retained, if smaller the elements at the end will be cut off. - *@param newSize The number of elements to include after resizing. - */ - void resizeTo( int newSize ); - - /** - * Actual master array of pointers. This is done to follow the List specs. - * All data transactions are performed with pointers or compatable - * primitive data-types. - */ - void **apData; - - /** - * The number of filled in elements in the array. This is the practical - * real size of the ArrayList for all userspace applications. - */ - int nSize; - - /** - * The number of elements allocated in memory. Not all of these have to be - * filled in, and it is usually larger than nSize so that adding and - * deleting elements is fast and easy. - */ - int nCapacity; - - /** - * The amount to grow by whenever the array needs resizing. - */ - int nGrowByFactor; -}; - -#endif - 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 @@ -#include "hashfunction.h" - -HashFunction::HashFunction() -{ -} - -HashFunction::~HashFunction() -{ -} - 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 @@ -#ifndef HASH_FUNCTION -#define HASH_FUNCTION - -/** This represents the shell of a hash function. It must be aggregated in - * order to be used. Please read about it's two functions for specificatins - * relating to what values will be passed to them and what they should return - * for creating your own hash functions. - *@author Mike Buland. - */ -class HashFunction -{ -public: - /** - * Standard Constructor. - */ - HashFunction(); - - /** - * Standard Deconstructor. - */ - virtual ~HashFunction(); - - /** Hashes the value represnted by id. This must return a fairly unique - * number in the range of 0-2^32 (or whatever the size of an unsigned long - * is on your system) based on the id given. The faster the number changes - * the better in a general sence. The return value will be the index - * (after probing takes place) to the data assosiated with an id, so this - * function should always produce the same number for any given id. - *@param id The identifier to use to create a unique numerical identifier. - *@returns A mostly unique numerical identifier generated using the given - * id. - */ - virtual unsigned long int hash( const void *id ) = 0; - - /** This function must compare two ids in the format that this hashfunction - * accepts. For example, if the hash function hashes strings it should - * probably { return strcmp( id1, id2 ) == 0 }. - *@param id1 One value to use in the comparison - *@param id2 Another value to use in the comparison - *@returns True if the two values match, otherwise false. - */ - virtual bool cmpIDs( const void *id1, const void *id2 ) = 0; - -// virtual void *createPersistantID( const void *id ) = 0; -// virtual void destroyPersistantID( const void *id ) = 0; -}; - -#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 @@ -#include -#include -#include -#include "hashfunctioncasestring.h" - -HashFunctionCaseString::HashFunctionCaseString() -{ -} - -HashFunctionCaseString::~HashFunctionCaseString() -{ -} - -unsigned long int HashFunctionCaseString::hash( const void *id ) -{ - const char *str = (const char *)id; - unsigned long int nPos = 0; - for( int j = 0; str[j] != '\0'; j++ ) - { - nPos = tolower(str[j]) + (nPos << 6) + (nPos << 16) - nPos; -// nPos += nPos<<16|(((unsigned long int)tolower(str[j]))<<((j*7)%24)); - } - return nPos; -} - -bool HashFunctionCaseString::cmpIDs( const void *id1, const void *id2 ) -{ - const char *str1 = (const char *)id1; - const char *str2 = (const char *)id2; - - int j; - for( j = 0; str1[j] != '\0' && str2[j] != '\0'; j++ ) - { - if( tolower(str1[j]) != tolower(str2[j]) ) - return false; - } - return (str1[j]==str2[j]); -} - 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 @@ -#ifndef HASH_FUNCTION_CASE_STRING -#define HASH_FUNCTION_CASE_STRING - -#include "hashfunction.h" - -/** A hash function for string data. This hash function does strings, but is - * actually generalized to handle any binary stream of characters terminated - * by a null character. This is different than HashFunctionString in that - * this does comparisons without regaurd to case. - *@author Mike Buland. - */ -class HashFunctionCaseString : public HashFunction -{ -public: - /** - * Standard Constructor. - */ - HashFunctionCaseString(); - - /** - * Standard Deconstructor. - */ - virtual ~HashFunctionCaseString(); - unsigned long int hash( const void *id ); - bool cmpIDs( const void *id1, const void *id2 ); -}; - -#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 @@ -#include "hashfunctionint.h" - -HashFunctionInt::HashFunctionInt() -{ -} - -HashFunctionInt::~HashFunctionInt() -{ -} - -unsigned long int HashFunctionInt::hash( const void *id ) -{ - return (unsigned long)(id); -} - -bool HashFunctionInt::cmpIDs( const void *id1, const void *id2 ) -{ - return (unsigned long)(id1) == (unsigned long)(id2); -} - 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 @@ -#ifndef HASH_FUNCTION_INT -#define HASH_FUNCTION_INT - -#include "hashfunction.h" - -/** A hash function for integer data. Really, this does almost nothing except - * ensure we're dealing with positive indicies. - *@author Mike Buland. - */ -class HashFunctionInt : public HashFunction -{ -public: - /** - * Standard Constructor. - */ - HashFunctionInt(); - - /** - * Standard Deconstructor. - */ - virtual ~HashFunctionInt(); - unsigned long int hash( const void *id ); - bool cmpIDs( const void *id1, const void *id2 ); -}; - -#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 @@ -#include "hashfunctionstring.h" -#ifndef NULL -#define NULL ((void *) 0) -#endif - -HashFunctionString::HashFunctionString() -{ -} - -HashFunctionString::~HashFunctionString() -{ -} - -unsigned long int HashFunctionString::hash( const void *id ) -{ - if (id == NULL) - { - return 0; - } - - unsigned long int nPos = 0; - for( const char *s = (const char *)id; *s; s++ ) - { - nPos = *s + (nPos << 6) + (nPos << 16) - nPos; - } - return nPos; -} - -bool HashFunctionString::cmpIDs( const void *id1, const void *id2 ) -{ - if (id1 == NULL || id2 == NULL) - { - return false; - } - if (id1 == id2) - { - return true; - } - - const char *str1 = (const char *)id1; - const char *str2 = (const char *)id2; - - int j; - for( j = 0; str1[j] != '\0' && str2[j] != '\0'; j++ ) - { - if( str1[j] != str2[j] ) - return false; - } - return (str1[j]==str2[j]); -} - 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 @@ -#ifndef HASH_FUNCTION_STRING -#define HASH_FUNCTION_STRING - -#include "hashfunction.h" - -/** A hash function for string data. This hash function does strings, but is - * actually generalized to handle any binary stream of characters terminated - * by a null character. - *@author Mike Buland. - */ -class HashFunctionString : public HashFunction -{ -public: - /** - * Standard Constructor. - */ - HashFunctionString(); - - /** - * Standard Deconstructor. - */ - virtual ~HashFunctionString(); - unsigned long int hash( const void *id ); - bool cmpIDs( const void *id1, const void *id2 ); -}; - -#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 @@ -#include -#include -#include - -#include "hashtable.h" - -HashTable::HashTable( HashFunction *hNewFunc, unsigned long int nInitSize, bool bAllowDupes ) -{ - hFunc = hNewFunc; - nTableSize = nextPrime( nInitSize ); - aTable = new HashNode[nTableSize]; - //for( int j = 0; j < nTableSize; j++ ) if( aTable[j].id || aTable[j].data || aTable[j].bDeleted ) printf("Unclean entry\n"); - nSize = 0; - nFilled = 0; - this->bAllowDupes = bAllowDupes; -} - -HashTable::~HashTable() -{ - delete[] aTable; - delete hFunc; -} - -void HashTable::set( int j, const void *newID, const void *newData ) -{ - if( newData == NULL ) - { - printf("Inserting NULL data is indestinguishable from uninserted data!\n"); - } - aTable[j].id = newID; - aTable[j].data = newData; -} - -void HashTable::clear() -{ - memset( aTable, 0, sizeof(HashNode) * nTableSize ); -} - -bool HashTable::isFilled( int j ) -{ - return (aTable[j].id != NULL)||(aTable[j].bDeleted); -} - -void HashTable::reHash( unsigned long int nNewSize ) -{ - HashNode *aOldTable = aTable; - unsigned long int oldSize = nTableSize; - - // If the table can still be used if we just get rid of deleted items, don't - // change the size of the table, otherwise, go ahead and use the number - // passed in. - if( nSize > nTableSize>>1 ) - { - nTableSize = nextPrime( nNewSize ); - } - - aTable = newTable( nTableSize ); - //for( int j = 0; j < nTableSize; j++ ) if( aTable[j].id || aTable[j].data || aTable[j].bDeleted ) printf("Unclean entry\n"); - - nSize = 0; - nFilled = 0; - - for( unsigned long int j = 0; j < oldSize; j++ ) - { - if( aOldTable[j].id != NULL && aOldTable[j].bDeleted == false ) - { - insert( aOldTable[j].id, aOldTable[j].data ); - } - } - - delete[] aOldTable; -} - -unsigned long int HashTable::probe( unsigned long int nStart, const void *id ) -{ - int nHash = nStart; - nStart = nStart%nTableSize; - if( bAllowDupes == true ) - { - for( - unsigned long int j=0; - isFilled( nStart ) && j < 32; - nStart = (nStart+(1<cmpIDs( aTable[nStart].id, id ) == true && - aTable[nStart].bDeleted == false ) - { - return nStart; - } - } - } - } - // This is our insurance, if the table is full, then go ahead and rehash, - // then try again. - if( isFilled( nStart ) ) - { - reHash( getCapacity()*2 ); - return probe( nHash, id ); - } - return nStart; -} - -HashTable::HashNode *HashTable::newTable( unsigned long int nNewSize ) -{ - return new HashNode[nNewSize]; -} - -#ifdef HASH_DEBUG_VIS -void HashTable::printDebugLine( const char *exData ) -{ - char *buf = new char[getCapacity()+3]; - int j; - buf[0] = '['; - for( j = 0; j < getCapacity(); j++ ) - { - buf[j+1] = (aTable[j].bDeleted)?('X'):((isFilled( j ))?('#'):('-')); - } - buf[j+1] = ']'; - buf[j+2] = '\0'; - printf("%s %s\n", buf, exData ); - delete[] buf; -} -#endif - -bool HashTable::insert( const void *id, const void *data ) -{ - unsigned long int nPos = probe( hFunc->hash( id ), id )%nTableSize; - - if( bAllowDupes == true ) - { - if( aTable[nPos].id == NULL && aTable[nPos].bDeleted == false ) - { - set( nPos, id, data ); -#ifdef HASH_DEBUG_VIS - printDebugLine( (const char *)id ); -#endif - nSize++; - nFilled++; - return true; - } - else - { - return false; - } - } - else - { - if( aTable[nPos].id == NULL && aTable[nPos].bDeleted == false ) - { - set( nPos, id, data ); -#ifdef HASH_DEBUG_VIS - printDebugLine( (const char *)id ); -#endif - nSize++; - nFilled++; - return true; - } - else if( hFunc->cmpIDs( aTable[nPos].id, id ) == true ) - { - set( nPos, id, data ); -#ifdef HASH_DEBUG_VIS - printDebugLine( (const char *)id ); -#endif - return true; - } - else - { - return false; - } - } -} - -const void *HashTable::get( const void *id, unsigned long int nSkip ) -{ - unsigned long int nPos = hFunc->hash( id )%nTableSize; - - for( unsigned long int j=0; j < 32; nPos = (nPos+(1<cmpIDs( id, aTable[nPos].id ) ) - { - if( nSkip == 0 ) - { - return aTable[nPos].data; - } - else - { - nSkip--; - } - } - } - } - - if( bAllowDupes ) - { - unsigned long int nOldPos = nPos; - for( nPos++; nPos != nOldPos; nPos=(nPos+1)%nTableSize ) - { - if( !isFilled( nPos ) ) return NULL; - if( aTable[nPos].bDeleted == false ) - { - if( hFunc->cmpIDs( id, aTable[nPos].id ) ) - { - if( nSkip == 0 ) - { - return aTable[nPos].data; - } - else - { - nSkip--; - } - } - } - } - } - - return NULL; -} - -const void *HashTable::getKey( const void *id, unsigned long int nSkip ) -{ - unsigned long int nPos = hFunc->hash( id )%nTableSize; - - for( unsigned long int j=0; j < 32; nPos = (nPos+(1<cmpIDs( id, aTable[nPos].id ) ) - { - if( nSkip == 0 ) - { - return aTable[nPos].id; - } - else - { - nSkip--; - } - } - } - } - - if( bAllowDupes ) - { - unsigned long int nOldPos = nPos; - for( nPos++; nPos != nOldPos; nPos=(nPos+1)%nTableSize ) - { - if( !isFilled( nPos ) ) return NULL; - if( aTable[nPos].bDeleted == false ) - { - if( hFunc->cmpIDs( id, aTable[nPos].id ) ) - { - if( nSkip == 0 ) - { - return aTable[nPos].id; - } - else - { - nSkip--; - } - } - } - } - } - - return NULL; -} - -void *HashTable::getFirstItemPos() -{ - HashPos *pos = new HashPos; - return pos; -} - -const void *HashTable::getItemData( void *xPos ) -{ - return aTable[((HashPos *)xPos)->nPos].data; -} - -const void *HashTable::getItemID( void *xPos ) -{ - return aTable[((HashPos *)xPos)->nPos].id; -} - -void *HashTable::getNextItemPos( void *xPos ) -{ - HashPos *pos = (HashPos *)xPos; - if( pos->bStarted == false ) - { - pos->bStarted = true; - pos->nPos = 0; - } - else - { - pos->nPos++; - } - if( pos->nPos < nTableSize ) - { - for( ; pos->nPos < nTableSize; pos->nPos++ ) - { - if( isFilled( pos->nPos ) && - aTable[pos->nPos].bDeleted == false ) - { - return xPos; - } - } - } - - delete pos; - - return NULL; -} - -// Big-O sqrt(n) -// Change this to be erethpothynies table with a storage -// lookup later on. -bool HashTable::isPrime (int num) -{ - if (num == 2) // the only even prime - return true; - else if (num % 2 == 0) // other even numbers are composite - return false; - else - { - //bool prime = true; - int divisor = 3; - int upperLimit = static_cast(sqrt(num) + 1); - while (divisor <= upperLimit) - { - if (num % divisor == 0) - return false; - // prime = false; - divisor +=2; - } - return true; - } -} - -// Big-O n^(3/2) -int HashTable::nextPrime( int base ) -{ - int nPrime; - for( nPrime = base; isPrime( nPrime ) == false; nPrime++ ); - return nPrime; -} - -unsigned long int HashTable::getCapacity() -{ - return nTableSize; -} - -unsigned long int HashTable::getSize() -{ - return nSize; -} - -double HashTable::getLoad() -{ - return (double)(nFilled)/(double)(nTableSize); -} - -const void *HashTable::operator[](const void *id) -{ - return get( id ); -} - -bool HashTable::del( const void *id, int nSkip ) -{ - unsigned long int nPos = hFunc->hash( id )%nTableSize; - - for( unsigned long int j=0; j < 32; nPos = (nPos+(1<cmpIDs( id, aTable[nPos].id ) && - aTable[nPos].bDeleted == false ) - { - if( nSkip == 0 ) - { - aTable[nPos].bDeleted = true; - nSize--; -#ifdef HASH_DEBUG_VIS - printDebugLine( (const char *)id ); -#endif - return true; - } - else - { - nSkip--; - } - } - } - - return false; -} - 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 @@ -/**\hashtable.h - * Describes the HashFunction, HashFunctionString, and HashTable classes. It - * was just easier to put them all in one set of files. - *@author Mike Buland - */ - -#ifndef HASH_TABLE_H -#define HASH_TABLE_H - -//Uncomment this line to see a cool text-mode visualization of what's going on -//#define HASH_DEBUG_VIS 1 - -#include -#include -#include - -#include "hashfunction.h" - -/** - * A simple yet flexable hash-table. This uses several tricks to help ensure - * that the table is always running at maximum efficiency. You no longer have - * to specify a "danger fill level" when more space is needed a rehash is - * automatically trigered. Deleting elements is fully supported, as well as - * duplicate elements. To work with and allow duplicates simple construct your - * HashTable the way you normally would, but when deleting or getting elements - * you can specify a skip value. This effectively allows you to treat elements - * with duplicate ID's as though they were in a zero-based array. The first - * element inserted with a given ID would be at skip zero, the next at skip 1 - * and so on. This allows you to quickly search for elements with duplicate - * names, just stop when you get a null for a skip number, i.e. - * 
- *   for( int j = 0;; j++ )
- *   {
- *       void *pData = hash.get( myID, j );
- *       if( !pData ) break;
- *       // Do something interesting with pData
- *   }
- *
- * There are new features in this HashTable that also allow for memory saving - * when dealing with systems where many elements are being deleted from the - * table. In those cases the elements deleted cannot be simply deleted, instead - * they have to be marked as deleted and hidden from the user, but maintained in - * the table so that future hashing operations don't fail. When rehashing - * occurs all elements marked as deleted are quietly removed. In these cases, - * if the number of deleted items would free enough space in the table for the - * table to be used efficiently without resizing, it is left the same size and - * rehashing is performed effectively in place, allowing the deleted items to - * be removed. - *
- * For info on adding new hashing algorithms, please see the HashFunction class. - *@author Mike Buland - *@todo Fix probing for tables that allow duplicates, and delete an item, then - * insert an item with the same name. - */ -class HashTable -{ -public: - /** Constructs a hash table. - *@param hNewFunc A pointer to a hashfunction class to use. If this is - * null the default general string type will be used. - *@param nInitSize The initial size of the hashtable. - *@param bAllowDupes Setting this value to true allows the system to - * insert more than one copy of any given key. This can be tricky, and - * will require you to use the nSkip parameter on the get function. - */ - HashTable( HashFunction *hNewFunc, unsigned long int nInitSize, bool bAllowDupes=false ); - - /** - * Destroys the hashtable, cleaning up all internal storage, but not stored - * elements. Also deletes the HashFunction passed in in the constructor. - */ - virtual ~HashTable(); - - /** Inserts an item into the hashtable. This function will trigger a - * rehash if adding another item would force the table's load factor over - * the danger level. - *@param id used to find the data later. - *@param data The data item to insert into the table with the identifier - * id - *@returns True if insertion was successfull, and false if it failed. - */ - bool insert( const void *id, const void *data ); - - /** Gets an item in the hashtable based on the id of that item. If there - * is more than one item with the same id you can use the nSkip parameter - * to access all of them. - *@param id The id of the item you're trying to find. - *@param nSkip The number of items with that id to skip before returning - * with the requested item. - *@returns A pointer to the data stored at the given id. - */ - const void *get( const void *id, unsigned long int nSkip=0 ); - - const void *getKey( const void *id, unsigned long int nSkip=0 ); - - /** Gets the total capacity of the hashtable. This is actually the number - * of total positions available inside the hashtable at the moment. This - * will change when the hashtable's load exceeds the danger level. - * Please note that this is NOT the actual amount of space available. - * In reality you can only access about 45-50 percent of that space. - *@returns The total capacity. - */ - unsigned long int getCapacity(); - - /** Gets the number of filled in items in the hash table. This is roughly - * equivelent to the getSize function assosiated with the Lists. - *@returns The number of filled in items in the hash table. - */ - unsigned long int getSize(); - - /** Gets the load (percentage) of filled in items in the table. This is - * technically the size divided by the capacity, but is definately usefull - * since it's required to check if it's time to rehash. - *@returns The table load in the range 0.0 to 1.0 - */ - double getLoad(); - - /** Sets up an xPos object for use indexing the items in the table. Call - * this first and follow the directions for getNextItemPos below to - * iterate through every item in the table, while avoiding the empty - * spaces. - *@returns A pointer to a xPos object telling the hashtable where to find - * the item you're looking at. - */ - void *getFirstItemPos(); - - /** Get the item's data that is being pointed to by xPos. This is only - * valid after xPos was created using getFirstItemPos and getNextItemPos - * was called at least once. - *@param xPos supplied by getFirstItemPos. - *@returns The key value that was used to insert the data into the table. - */ - const void *getItemData( void *xPos ); - - /** Get the item's ID that is being pointed to by xPos. This is only - * valid after xPos was created using getFirstItemPos and getNextItemPos - * was called at least once. - *@param xPos supplied by getFirstItemPos. - *@returns The key value that was used to insert the data into the table. - */ - const void *getItemID( void *xPos ); - - /** Used for iterating through a hash table sequentially. This will - * update the xPos pointer to point to the next time, all ready to - * be accessed with getItemID and getItemData. This must be called at - * least once before xPos is meaningful, and will return a NULL when it - * has reached the last item. - *@param xPos This must be an object created by a call to the function - * getFirstItemPos, and is only meaningful to the internal routines. - * Aborting a call in the middle (not running to the end of the table) - * may result in a memory leak at the moment. - *@returns xPos if still iterating through the list, otherwise it will - * return NULL when the end has been reached and the xPos variable has - * been deleted. - */ - void *getNextItemPos( void *xPos ); - - /** A helpful operator to make accessing items easier. Please note that - * this simply returns a pointer to the data stored internally, and cannot - * be used like the STL operator to store new data, use insert for that. - *@param id The identifier used to store the requested item. - *@returns The data value assosiated with the given id, or NULL if it - * wasn't found in the table. - */ - const void *operator[](const void *id); - - /** - * Delete the specified item from the hashtable. This actually keeps the - * data and marks it deleted. For all intents and purposes to the user it - * is deleted, except that the space is still used until a rehash is forced. - * This means that in hashtables where elements are being inserted and - * deleted frequently you may run into a higher rate of expansion. - *@param id The ID to delete. - *@param nSkip The number of similar id's to skip before deleting in a - * hashtable that allows duplicates. - *@returns True if the element was found and deleted, false otherwise. - */ - bool del( const void *id, int nSkip=0 ); - - /** - * Deletes every entry in the hash table. See the notes on del to see what - * this means, except that since no data is being kept, the entire table is - * just marked as usable space. - */ - void clear(); - -private: - /** - * Contains info related to a position in the hashtable. Used for - * searching through hashtables one item at a time, in order. This class - * should never be created by anything but a HashTable, and should never - * be referenced directly. Instead the hashtable returns a void pointer, - * which is what should be passed back in next time you use a search - * function. Always finish a search, since the object is deleted at the - * end of the search. - *@author Mike Buland - */ - class HashPos - { - public: - /** Create a blank HashPos. */ - HashPos() { bStarted=false; nPos = 0; }; - /** Has the search been started? */ - bool bStarted; - /** The position (index) into the backend storage structure. */ - unsigned long int nPos; - }; - - /** - * All data related to a single element in the hashtable. This should - * really only be used and manipulated by the HashTable itself. - *@author Mike Buland - */ - typedef struct HashNode - { - public: - /** Create a new, empty HashNode. */ - HashNode() { id = NULL; data = NULL; bDeleted = false; }; - /** A pointer to the original ID that was used to key the data. */ - const void *id; - /** A pointer to the data stored along with the above ID. */ - const void *data; - /** Weather or not this data should really...exist */ - bool bDeleted; - } HashNode; - -private: - /** - * Just sets the values in the element to some friendly values. - *@param newID The new ID to store. - *@param newData The new Data to store. - */ - void set( int j, const void *newID, const void *newData ); - /** - * Tells you if the node is filled or not. - *@returns True=an ID has been stored here, False=no ID. - */ - bool isFilled( int j ); - /** - * This actually resizes, but since every resize requires a reHash to go - * along with it, that's the name. This actually creates a new buffer for - * all of the contained data and then pulls every old element that was in - * the old table out and performs the hashing placement calculations again. - * This function skips all data that was marked as deleted, so at this - * point it really will be. - *@param nNewSize The new size to set the table to while re-hashing. - *@returns True if the operation was successful, false otherwise. - */ - void reHash( unsigned long int nNewSize ); - - /** - * Helper function to allocate a new table. Really just does the memory - * allocation. - *@param nNewSize The size of the table to generate. - *@returns A new, blank array of HashNode objects the size you specified. - */ - HashNode *newTable( unsigned long int nNewSize ); - - /** - * This function is used once an actual hash code is obtained. nStart is - * the given hash code, which is then wrapped to the size of the table. If - * there is data at that location, tests are performed to see if it's the - * right one. If it is, then it is returned, otherwise a series of further - * tests based on a 2^n search pattern is performed. The position of the - * requested data in the back-end storage is returned if found, otherwise - * another less useful value is returned... - *@param nStart The initial hashcode of the ID testing for. - *@param id A pointer to the id that is being searched for. - *@returns The real location of the data requested. - */ - unsigned long int probe( unsigned long int nStart, const void *id ); - - /** - * Simple helper function to determine if a number is prime or not. - * This function runs in sqrt(n) time. - *@param num Number to test for prime-hood. - *@returns True if the number is prime, false otherwise. - */ - bool isPrime( int num ); - - /** - * Given any number, this function finds the first number after it that is - * prime. Since this number is a multiple internally it's rare that the - * starting number would be prime. - *@param base The number to start the prime search on. - *@returns The first prime after the number given. - */ - int nextPrime( int base ); - -#ifdef HASH_DEBUG_VIS - void printDebugLine( const char *exData ); -#endif - - /** A pointer to the HashFunction subclass instance to use. */ - HashFunction *hFunc; - /** The complete array of HashNode objects to store data in. */ - HashNode *aTable; - /** The actual size of the table, not how many elements are in it. */ - unsigned long int nTableSize; - /** The number of elements that are in the table. */ - unsigned long int nSize; - /** The number of elements that are unavailable now. */ - unsigned long int nFilled; - /** Allow duplicate ID's in the table. */ - bool bAllowDupes; -}; - -#endif -- cgit v1.2.3