From 4b8bad3d711f39db84f094edf83c5496a3f02cd6 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Tue, 21 Nov 2006 12:23:13 +0000 Subject: Wow, craziness. Part way through working on the confpair system I got some sudden insperation and completely redid Hash. Now everything but delete is implemented, including typesafe iterators and more. It's really cool, and everyone should check it out and start using it right away! --- src/confpair.h | 48 +++++- src/confpairbase.cpp | 17 ++ src/confpairbase.h | 24 +++ src/hash.cpp | 80 +++++++++ src/hash.h | 447 ++++++++++++++++++++++++++++++++++++++++++------- src/hashable.h | 5 +- src/staticstring.cpp | 20 ++- src/staticstring.h | 5 +- src/tests/confpair.cpp | 11 +- src/tests/hash.cpp | 77 ++++++++- 10 files changed, 662 insertions(+), 72 deletions(-) create mode 100644 src/confpairbase.cpp create mode 100644 src/confpairbase.h diff --git a/src/confpair.h b/src/confpair.h index 5be33c8..56eb06e 100644 --- a/src/confpair.h +++ b/src/confpair.h @@ -3,11 +3,14 @@ #include #include +#include +#include "confpairbase.h" + /** * */ template -class ConfPair +class ConfPair : public ConfPairBase { public: ConfPair( const std::string &sName ) : @@ -27,9 +30,52 @@ public: return sName; } + virtual void setFromString( const std::string &sStr ) + { + std::stringstream(sStr) >> tValue; + } + + virtual std::string getAsString() + { + std::stringstream tmp; + tmp << tValue; + return tmp.str(); + } + private: std::string sName; T tValue; }; +template<> +void ConfPair::setFromString( const std::string &sStr ) +{ + tValue = sStr; +} + +template<> +std::string ConfPair::getAsString() +{ + return tValue; +} + +template<> +void ConfPair::setFromString( const std::string &sStr ) +{ + if( !strcasecmp( sStr.c_str(), "true" ) || + !strcasecmp( sStr.c_str(), "yes" ) || + !strcasecmp( sStr.c_str(), "on" ) ) + tValue = true; + else + tValue = false; +} + +template<> +std::string ConfPair::getAsString() +{ + if( tValue == true ) + return "True"; + return "False"; +} + #endif diff --git a/src/confpairbase.cpp b/src/confpairbase.cpp new file mode 100644 index 0000000..1203dc0 --- /dev/null +++ b/src/confpairbase.cpp @@ -0,0 +1,17 @@ +#include "confpairbase.h" + +ConfPairBase::ConfPairBase() +{ +} + +ConfPairBase::~ConfPairBase() +{ +} + +ConfPairBase &ConfPairBase::operator=( const std::string &s ) +{ + setFromString( s ); + + return *this; +} + diff --git a/src/confpairbase.h b/src/confpairbase.h new file mode 100644 index 0000000..2530756 --- /dev/null +++ b/src/confpairbase.h @@ -0,0 +1,24 @@ +#ifndef CONF_PAIR_BASE_H +#define CONF_PAIR_BASE_H + +#include +#include +#include +#include + +class ConfPairBase +{ +public: + ConfPairBase(); + virtual ~ConfPairBase(); + + virtual void setFromString( const std::string &sStr )=0; + virtual std::string getAsString()=0; + + ConfPairBase &operator=( const std::string &s ); + +private: + +}; + +#endif diff --git a/src/hash.cpp b/src/hash.cpp index b4aac77..14be208 100644 --- a/src/hash.cpp +++ b/src/hash.cpp @@ -1 +1,81 @@ #include "hash.h" + +template<> +uint32_t __calcHashCode( const char * k ) +{ + if (k == NULL) + { + return 0; + } + + unsigned long int nPos = 0; + for( const char *s = k; *s; s++ ) + { + nPos = *s + (nPos << 6) + (nPos << 16) - nPos; + } + + return nPos; +} + +template<> bool __cmpHashKeys( const char *a, const char *b ) +{ + if( a == b ) + return true; + + for(; *a != *b; a++, b++ ) + if( *a == '\0' && *b == '\0' ) + return true; + + return false; +} + +template<> +uint32_t __calcHashCode( char *k ) +{ + return __calcHashCode((const char *)k ); +} + +template<> bool __cmpHashKeys( char *a, char *b ) +{ + return __cmpHashKeys((const char *)a, (const char *)b ); +} + +template<> uint32_t __calcHashCode( const std::string k ) +{ + std::string::size_type j, sz = k.size(); + const char *s = k.c_str(); + + unsigned long int nPos = 0; + for( j = 0; j < sz; j++, s++ ) + { + nPos = *s + (nPos << 6) + (nPos << 16) - nPos; + } + + return nPos; +} + +template<> bool __cmpHashKeys( const std::string a, const std::string b ) +{ + return a == b; +} + +template<> uint32_t __calcHashCode( std::string k ) +{ + return __calcHashCode( k ); +} + +template<> bool __cmpHashKeys( std::string a, std::string b ) +{ + return __cmpHashKeys( a, b ); +} + +template<> uint32_t __calcHashCode( Hashable &k ) +{ + return k.getHashCode(); +} + +template<> bool __cmpHashKeys( Hashable &a, Hashable &b ) +{ + return a.compareForHash( b ); +} + diff --git a/src/hash.h b/src/hash.h index 8385bb9..b8ced99 100644 --- a/src/hash.h +++ b/src/hash.h @@ -1,106 +1,431 @@ #ifndef HASH_H #define HASH_H -/* + #include #include +#include +#include #include "hashable.h" -#define bitsToBytes( n ) (n/8+(n%8>0 ? 1 : 0)) +#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0)) + +template +uint32_t __calcHashCode( T k ); + +template +bool __cmpHashKeys( T a, T b ); + +struct __calcNextTSize_fast +{ + uint32_t operator()( uint32_t nCapacity, uint32_t nFill, uint32_t nDeleted ) const + { + return nCapacity*2+1; + } +}; + +template, typename valuealloc = std::allocator, typename challoc = std::allocator > +class Hash; + +template< typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc > +struct HashProxy +{ + friend class Hash; +private: + HashProxy( Hash &h, key k, value v ) : + hsh( h ), + tKey( k ), + tValue( v ), + bFilled( true ) + { + } + + HashProxy( Hash &h, key k ) : + hsh( h ), + tKey( k ), + bFilled( false ) + { + } + + Hash &hsh; + key tKey; + value tValue; + bool bFilled; + +public: + operator value() + { + if( bFilled == false ) + throw "Nope, no data there"; + return tValue; + } -template + value operator=( value nval ) + { + hsh.insert( tKey, nval ); + return nval; + } + +}; + +template class Hash { - class iterator +public: + Hash() : + nCapacity( 11 ), + nFilled( 0 ), + nDeleted( 0 ), + bFilled( NULL ), + aKeys( NULL ), + aValues( NULL ), + aHashCodes( NULL ) { - friend class Hash; - private: - iterator( Hash *hsh, int nIndex, key keyval, bool bInsert ) : - hsh( hsh ), - nIndex( nIndex ), - keyval( keyval ), - bInsert( bInsert ) + nKeysSize = bitsToBytes( nCapacity ); + bFilled = ca.allocate( nKeysSize ); + bDeleted = ca.allocate( nKeysSize ); + clearBits(); + + aHashCodes = ca.allocate( nCapacity ); + aKeys = ka.allocate( nCapacity ); + aValues = va.allocate( nCapacity ); + } + + virtual ~Hash() + { + for( uint32_t j = 0; j < nCapacity; j++ ) { + if( isFilled( j ) ) + { + va.destroy( &aValues[j] ); + ka.destroy( &aKeys[j] ); + } } + va.deallocate( aValues, nCapacity ); + ka.deallocate( aKeys, nCapacity ); + ca.deallocate( bFilled, nKeysSize ); + ca.deallocate( bDeleted, nKeysSize ); + ca.deallocate( aHashCodes, nCapacity ); + } - public: - iterator() : - hsh( NULL ), - nIndex( -1 ) + void clearBits() + { + for( uint32_t j = 0; j < nKeysSize; j++ ) { + bFilled[j] = bDeleted[j] = 0; } + } + + int hasKey( key keyval ) + { + printf("%s\n", keyval ); + } + + uint32_t getCapacity() + { + return nCapacity; + } + + uint32_t getFill() + { + return nFilled; + } + + uint32_t getDeleted() + { + return nDeleted; + } + + HashProxy operator[]( key k ) + { + uint32_t hash = __calcHashCode( k ); + bool bFill; + uint32_t nPos = probe( hash, k, bFill ); - iterator &operator=( iterator &src ) + if( bFill ) { - this->hsh = src.hsh; - this->nIndex = src.nIndex; + return HashProxy( *this, aKeys[nPos], aValues[nPos] ); } + else + { + return HashProxy( *this, k ); + } + } + + void insert( key k, value v ) + { + uint32_t hash = __calcHashCode( k ); + bool bFill; + uint32_t nPos = probe( hash, k, bFill ); - iterator &operator=( value &src ) + if( bFill ) { - if( bInsert ) - printf("You wanted to insert %d\n", src ); - else - printf("You wanted to insert %d\n", src ); + va.destroy( &aValues[nPos] ); + va.construct( &aValues[nPos], v ); + } + else + { + va.construct( &aValues[nPos], v ); + ka.construct( &aKeys[nPos], k ); + fill( nPos ); + aHashCodes[nPos] = hash; + nFilled++; } + } - private: - Hash *hsh; - int nIndex; - bool bInsert; - key keyval; - }; + value get( key k ) + { + uint32_t hash = __calcHashCode( k ); + bool bFill; + uint32_t nPos = probe( hash, k, bFill ); + + if( bFill ) + { + return aValues[nPos]; + } + else + { + throw "Hey, no such thing..."; + } + } + + uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true ) + { + uint32_t nCur = hash%nCapacity; + + // First we scan to see if the key is already there, abort if we + // run out of probing room, or we find a non-filled entry + for( int8_t j = 0; + isFilled( nCur ) && j < 32; + nCur = (nCur + (1< - class VRef + void fill( uint32_t loc ) { + bFilled[loc/32] |= (1<<(loc%32)); + } + + bool isFilled( uint32_t loc ) + { + return (bFilled[loc/32]&(1<<(loc%32)))!=0; + } + + bool isDeleted( uint32_t loc ) + { + return (bDeleted[loc/32]&(1<<(loc%32)))!=0; + } + + typedef struct iterator + { + friend class Hash; + private: + iterator( Hash &hsh ) : + hsh( hsh ), + bFinished( false ), + nPos( 0 ) + { + nPos = hsh.getFirstPos( bFinished ); + } + + iterator( Hash &hsh, bool bDone ) : + hsh( hsh ), + nPos( 0 ), + bFinished( bDone ) + { + } + + Hash &hsh; + + uint32_t nPos; + bool bFinished; + public: - VRef( refval &data ) : - data( data ) + iterator operator++( int ) { + if( bFinished == false ) + nPos = hsh.getNextPos( nPos, bFinished ); + + return *this; + } + + iterator operator++() + { + if( bFinished == false ) + nPos = hsh.getNextPos( nPos, bFinished ); + + return *this; + } + + bool operator==( const iterator &oth ) + { + if( bFinished != oth.bFinished ) + return false; + if( bFinished == true ) + { + return true; + } + else + { + if( oth.nPos == nPos ) + return true; + return false; + } + } + + bool operator!=( const iterator &oth ) + { + return !(*this == oth ); + } + + std::pair operator *() + { + return hsh.getAtPos( nPos ); } - refval &data; }; -public: - Hash() : - nCapacity( 11 ), - nFilled( 0 ), - bFilled( NULL ), - aKeys( NULL ), - aValues( NULL ), - aHashCodes( NULL ) + iterator begin() { - int nKeysSize = bitsToBytes( nCapacity ); - bFilled = new unsigned char[ nKeysSize ]; - memset( bFilled, 0, nKeysSize ); - - aKeys = new VRef*[nCapacity]; - aValues = new value[nCapacity]; + return iterator( *this ); + } + + iterator end() + { + return iterator( *this, true ); } - virtual ~Hash() +private: + std::pair getAtPos( uint32_t nPos ) { + return std::pair(aKeys[nPos],aValues[nPos]); } - iterator operator[]( key keyval ) + uint32_t getFirstPos( bool &bFinished ) { - //iterator i( this, 4, keyval, true ); - //return i; - printf("%s\n", keyval.getString() ); + for( uint32_t j = 0; j < nCapacity; j++ ) + { + if( isFilled( j ) ) + return j; + } + + bFinished = true; } - int hasKey( key keyval ) + uint32_t getNextPos( uint32_t nPos, bool &bFinished ) { - printf("%s\n", keyval.getString() ); + for( uint32_t j = nPos+1; j < nCapacity; j++ ) + { + if( isFilled( j ) ) + return j; + } + + bFinished = true; } private: - int nCapacity; - int nFilled; - unsigned char *bFilled; - VRef **aKeys; - unsigned long int *aHashCodes; + uint32_t nCapacity; + uint32_t nFilled; + uint32_t nDeleted; + uint32_t *bFilled; + uint32_t *bDeleted; + uint32_t *aHashCodes; + uint32_t nKeysSize; value *aValues; + key *aKeys; + valuealloc va; + keyalloc ka; + challoc ca; + sizecalc szCalc; }; -*/ + +template<> uint32_t __calcHashCode( const char *k ); +template<> bool __cmpHashKeys( const char *a, const char *b ); + +template<> uint32_t __calcHashCode( char *k ); +template<> bool __cmpHashKeys( char *a, char *b ); + +template<> uint32_t __calcHashCode( const std::string k ); +template<> bool __cmpHashKeys( const std::string a, const std::string b ); + +template<> uint32_t __calcHashCode( std::string k ); +template<> bool __cmpHashKeys( std::string a, std::string b ); + +template<> uint32_t __calcHashCode( Hashable &k ); +template<> bool __cmpHashKeys( Hashable &a, Hashable &b ); + #endif diff --git a/src/hashable.h b/src/hashable.h index 33ff8b8..ce49130 100644 --- a/src/hashable.h +++ b/src/hashable.h @@ -1,10 +1,11 @@ #ifndef HASHABLE_H #define HASHABLE_H -/* + class Hashable { public: virtual unsigned long int getHashCode() = 0; + virtual bool compareForHash( Hashable &other ) = 0; }; -*/ + #endif diff --git a/src/staticstring.cpp b/src/staticstring.cpp index 9eac92e..0012b0f 100644 --- a/src/staticstring.cpp +++ b/src/staticstring.cpp @@ -243,10 +243,28 @@ bool StaticString::operator!=( StaticString &str ) unsigned long int StaticString::getHashCode() { unsigned long int nPos = nLen; - for( const char *s = (const char *)lpStr; *s; s++ ) + unsigned long int j = 0; + for( const char *s = (const char *)lpStr; j< nLen; s++, j++ ) { nPos = *s + (nPos << 6) + (nPos << 16) - nPos; } return nPos; } +bool StaticString::compareForHash( Hashable &other ) +{ + if( ((StaticString &)other).nLen != nLen ) + return false; + + const char *a = ((StaticString &)other).lpStr; + const char *b = lpStr; + if( a == b ) + return true; + + for( unsigned long j = 0; j < nLen; j++, a++, b++ ) + if( *a != *b ) + return false; + + return true; +} + diff --git a/src/staticstring.h b/src/staticstring.h index 61501bf..1ff3f63 100644 --- a/src/staticstring.h +++ b/src/staticstring.h @@ -3,7 +3,7 @@ #include #include "serializable.h" -//#include "hashable.h" +#include "hashable.h" /** * Simple string managing class. Allows for dynamically allocated string data @@ -12,7 +12,7 @@ * and making accessing meta-info like length fast and reliable as well. *@author Mike Buland */ -class StaticString : public Serializable//, public Hashable +class StaticString : public Serializable, public Hashable { public: StaticString(); @@ -51,6 +51,7 @@ public: virtual void serialize( class Serializer &ar ); virtual unsigned long int getHashCode(); + virtual bool compareForHash( Hashable &other ); private: char *lpStr; diff --git a/src/tests/confpair.cpp b/src/tests/confpair.cpp index 8e03730..fb1b0d3 100644 --- a/src/tests/confpair.cpp +++ b/src/tests/confpair.cpp @@ -5,10 +5,15 @@ using namespace std; int main() { - ConfPair p1("DebugMode"); - p1.value() = true; + ConfPair p1("DebugMode"); + p1.value() = 12; cout << p1.value() << "\n"; - p1.value() = false; + p1.value() = 55; cout << p1.value() << "\n"; + + ConfPairBase &p = p1; + + p = "33.12"; + cout << p.getAsString(); } diff --git a/src/tests/hash.cpp b/src/tests/hash.cpp index d0f5fa6..8406439 100644 --- a/src/tests/hash.cpp +++ b/src/tests/hash.cpp @@ -3,8 +3,81 @@ int main() { - //Hash sTest; + const char *names[]={ + "Homer the Great", + "And Maggie Makes Three", + "Bart's Comet", + "Homie The Clown", + "Bart Vs Australia", + "Homer vs Patty and Selma", + "A star is burns", + "Lisa's Wedding", + "Two Dozen and One Greyhounds", + "The PTA Disbands", + "Round Springfield", + "The Springfield connection", + "Lemon of Troy", + "Who Shot Mr. Burns (Pt. 1)", + "Who Shot Mr. Burns (pt. 2)", + "Radioactive Man", + "Home Sweet Homediddly-dum-doodly", + "Bart Sells His Soul", + "Lisa the Vegetarian", + "Treehouse of horror VI", + "King Size Homer", + "Mother Simpson", + "Sideshow Bob's Last Gleaming", + "The Simpson's 138th Show Spectacular", + "Marge Be Not Proud", + "Team Homer", + "Two Bad Neighbors", + "Scenes From the Class Struggle in Springfield", + "Bart the Fink", + "Lisa the Iconoclast", + "Homer the Smithers", + "The Day the Violence Died", + "A Fish Called Selma", + "Bart on the road", + "22 Short Films about Springfield", + "The Curse of the Flying Hellfish", + "Much Apu about Nothing", + "Homerpalooza", + "The Summer of 4 Ft 2", + "Treehouse of Horror VII", + "You Only Move Twice", + "The Homer They Fall", + "Burns Baby Burns", + "Bart After Dark", + "A Millhouse Divided", + "Lisas Date With Destiny", + "Hurricane Neddy", + "The Mysterious Voyage of Our Homer", + "The Springfield Files", + "The Twisted World of Marge Simpson", + "Mountain of Madness", + NULL + }; - //sTest.hasKey("hello"); + Hash sTest; + + printf("Inserting\n-------------------\n\n"); + for( int j = 0; j < 33; j++ ) + { + sTest[names[j]] = j; + } + + printf("Getting\n-------------------\n\n"); + printf("%d\n", sTest.get( names[10] ) ); + printf("%d\n", (int)sTest[names[10]] ); + sTest[names[10]] = 22; + sTest["That one guy"] = 135; + printf("%d\n", (int)sTest[names[10]] ); + + for( Hash::iterator i = sTest.begin(); + i != sTest.end(); i++ ) + { + Hash::iterator j = i; + printf("%d: %s\n", (*j).second, (*j).first.c_str() ); + } } -- cgit v1.2.3