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.

1 files changed, 744 insertions, 0 deletions

diff --git a/src/old/hash.h b/src/old/hash.h
new file mode 100644
index 0000000..e819379
--- /dev/null
+++ b/src/old/hash.h
@@ -0,0 +1,744 @@
+#ifndef HASH_H
+#define HASH_H
+
+#include <stddef.h>
+#include <string.h>
+#include <memory>
+#include <iostream>
+#include <list>
+#include "exceptionbase.h"
+#include "hashable.h"
+#include "serializable.h"
+#include "serializer.h"
+
+#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0))
+
+subExceptionDecl( HashException )
+
+enum eHashException
+{
+        excodeNotFilled
+};
+
+template<typename T>
+uint32_t __calcHashCode( const T &k );
+
+template<typename T>
+bool __cmpHashKeys( const T &a, const T &b );
+
+struct __calcNextTSize_fast
+{
+        uint32_t operator()( uint32_t nCapacity, uint32_t nFill, uint32_t nDeleted ) const
+        {
+                if( nDeleted >= nCapacity/2 )
+                        return nCapacity;
+                return nCapacity*2+1;
+        }
+};
+
+template<typename key, typename value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<value>, typename challoc = std::allocator<uint32_t> >
+class Hash;
+
+template< typename key, typename _value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<_value>, typename challoc = std::allocator<uint32_t> >
+struct HashProxy
+{
+        friend class Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc>;
+private:
+        HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, key *k, uint32_t nPos, uint32_t hash ) :
+                hsh( h ),
+                pKey( k ),
+                nPos( nPos ),
+                hash( hash ),
+                bFilled( false )
+        {
+        }
+
+        HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, uint32_t nPos, _value *pValue ) :
+                hsh( h ),
+                nPos( nPos ),
+                pValue( pValue ),
+                bFilled( true )
+        {
+        }
+
+        Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &hsh;
+        key *pKey;
+        uint32_t nPos;
+        _value *pValue;
+        uint32_t hash;
+        bool bFilled;
+
+public:
+        operator _value &()
+        {
+                if( bFilled == false )
+                        throw HashException(
+                                        excodeNotFilled,
+                                        "No data assosiated with that key."
+                                        );
+                return *pValue;
+        }
+
+        _value &value()
+        {
+                if( bFilled == false )
+                        throw HashException(
+                                        excodeNotFilled,
+                                        "No data assosiated with that key."
+                                        );
+                return *pValue;
+        }
+
+        bool isFilled()
+        {
+                return bFilled;
+        }
+
+        void erase()
+        {
+                if( bFilled )
+                {
+                        hsh._erase( nPos );
+                        hsh.onDelete();
+                }
+        }
+
+        _value operator=( _value nval )
+        {
+                if( bFilled )
+                {
+                        hsh.va.destroy( pValue );
+                        hsh.va.construct( pValue, nval );
+                        hsh.onUpdate();
+                }
+                else
+                {
+                        hsh.fill( nPos, *pKey, nval, hash ); 
+                        hsh.onInsert();
+                }
+
+                return nval;
+        }
+
+        _value *operator->()
+        {
+                if( bFilled == false )
+                        throw HashException(
+                                        excodeNotFilled,
+                                        "No data assosiated with that key."
+                                        );
+                return pValue;
+        }
+};
+
+template<typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc >
+class Hash
+{
+        friend struct HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>;
+public:
+        Hash() :
+                nCapacity( 11 ),
+                nFilled( 0 ),
+                nDeleted( 0 ),
+                bFilled( NULL ),
+                bDeleted( NULL ),
+                aKeys( NULL ),
+                aValues( NULL ),
+                aHashCodes( NULL )
+        {
+                nKeysSize = bitsToBytes( nCapacity );
+                bFilled = ca.allocate( nKeysSize );
+                bDeleted = ca.allocate( nKeysSize );
+                clearBits();
+
+                aHashCodes = ca.allocate( nCapacity );
+                aKeys = ka.allocate( nCapacity );
+                aValues = va.allocate( nCapacity );
+        }
+
+        Hash( const Hash &src ) :
+                nCapacity( src.nCapacity ),
+                nFilled( 0 ),
+                nDeleted( 0 ),
+                bFilled( NULL ),
+                bDeleted( NULL ),
+                aKeys( NULL ),
+                aValues( NULL ),
+                aHashCodes( NULL )
+        {
+                nKeysSize = bitsToBytes( nCapacity );
+                bFilled = ca.allocate( nKeysSize );
+                bDeleted = ca.allocate( nKeysSize );
+                clearBits();
+
+                aHashCodes = ca.allocate( nCapacity );
+                aKeys = ka.allocate( nCapacity );
+                aValues = va.allocate( nCapacity );
+
+                for( uint32_t j = 0; j < src.nCapacity; j++ )
+                {
+                        if( src.isFilled( j ) )
+                        {
+                                insert( src.aKeys[j], src.aValues[j] );
+                        }
+                }
+        }
+
+        Hash &operator=( const Hash &src )
+        {
+                for( uint32_t j = 0; j < nCapacity; j++ )
+                {
+                        if( isFilled( j ) )
+                                if( !isDeleted( 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 );
+
+                nFilled = 0;
+                nDeleted = 0;
+                nCapacity = src.nCapacity;
+                nKeysSize = bitsToBytes( nCapacity );
+                bFilled = ca.allocate( nKeysSize );
+                bDeleted = ca.allocate( nKeysSize );
+                clearBits();
+
+                aHashCodes = ca.allocate( nCapacity );
+                aKeys = ka.allocate( nCapacity );
+                aValues = va.allocate( nCapacity );
+
+                for( uint32_t j = 0; j < src.nCapacity; j++ )
+                {
+                        if( src.isFilled( j ) )
+                        {
+                                insert( src.aKeys[j], src.aValues[j] );
+                        }
+                }
+
+                return *this;
+        }
+
+        virtual ~Hash()
+        {
+                for( uint32_t j = 0; j < nCapacity; j++ )
+                {
+                        if( isFilled( j ) )
+                                if( !isDeleted( 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 );
+        }
+
+        uint32_t getCapacity()
+        {
+                return nCapacity;
+        }
+
+        uint32_t getFill()
+        {
+                return nFilled;
+        }
+
+        uint32_t size()
+        {
+                return nFilled-nDeleted;
+        }
+
+        uint32_t getDeleted()
+        {
+                return nDeleted;
+        }
+
+        virtual HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( key k )
+        {
+                uint32_t hash = __calcHashCode( k );
+                bool bFill;
+                uint32_t nPos = probe( hash, k, bFill );
+
+                if( bFill )
+                {
+                        return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, nPos, &aValues[nPos] );
+                }
+                else
+                {
+                        return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, &k, nPos, hash );
+                }
+        }
+
+        virtual void insert( key k, value v )
+        {
+                uint32_t hash = __calcHashCode( k );
+                bool bFill;
+                uint32_t nPos = probe( hash, k, bFill );
+
+                if( bFill )
+                {
+                        va.destroy( &aValues[nPos] );
+                        va.construct( &aValues[nPos], v );
+                        onUpdate();
+                }
+                else
+                {
+                        fill( nPos, k, v, hash );
+                        onInsert();
+                }
+        }
+
+        virtual void erase( key k )
+        {
+                uint32_t hash = __calcHashCode( k );
+                bool bFill;
+                uint32_t nPos = probe( hash, k, bFill );
+
+                if( bFill )
+                {
+                        _erase( nPos );
+                        onDelete();
+                }
+        }
+
+        struct iterator;
+        virtual void erase( struct iterator &i )
+        {
+                if( this != &i.hsh )
+                        throw HashException("This iterator didn't come from this Hash.");
+                if( isFilled( i.nPos ) && !isDeleted( i.nPos ) )
+                {
+                        _erase( i.nPos );
+                        onDelete();
+                }
+        }
+
+        virtual void clear()
+        {
+                for( uint32_t j = 0; j < nCapacity; j++ )
+                {
+                        if( isFilled( j ) )
+                                if( !isDeleted( j ) )
+                                {
+                                        va.destroy( &aValues[j] );
+                                        ka.destroy( &aKeys[j] );
+                                        onDelete();
+                                }
+                }
+                
+                clearBits();
+        }
+
+        virtual 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 HashException(
+                                        excodeNotFilled,
+                                        "No data assosiated with that key."
+                                        );
+                }
+        }
+
+        virtual bool has( key k )
+        {
+                bool bFill;
+                probe( __calcHashCode( k ), k, bFill, false );
+
+                return bFill;
+        }
+
+        typedef struct iterator
+        {
+                friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
+        private:
+                iterator( Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh ) :
+                        hsh( hsh ),
+                        nPos( 0 ),
+                        bFinished( false )
+                {
+                        nPos = hsh.getFirstPos( bFinished );
+                }
+                
+                iterator( Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh, bool bDone ) :
+                        hsh( hsh ),
+                        nPos( 0 ),
+                        bFinished( bDone )
+                {
+                }
+
+                Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> &hsh;
+                uint32_t nPos;
+                bool bFinished;
+
+        public:
+                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 );
+                }
+
+                iterator operator=( const iterator &oth )
+                {
+                        if( &hsh != &oth.hsh )
+                                throw HashException(
+                                        "Cannot mix iterators from different hash objects.");
+                        nPos = oth.nPos;
+                        bFinished = oth.bFinished;
+                }
+
+                std::pair<key,value> operator *()
+                {
+                        return hsh.getAtPos( nPos );
+                }
+                
+                key &getKey()
+                {
+                        return hsh.getKeyAtPos( nPos );
+                }
+
+                value &getValue()
+                {
+                        return hsh.getValueAtPos( nPos );
+                }
+        };
+
+        iterator begin()
+        {
+                return iterator( *this );
+        }
+        
+        iterator end()
+        {
+                return iterator( *this, true );
+        }
+
+        std::list<key> getKeys()
+        {
+                std::list<key> lKeys;
+
+                for( uint32_t j = 0; j < nCapacity; j++ )
+                {
+                        if( isFilled( j ) )
+                        {
+                                if( !isDeleted( j ) )
+                                {
+                                        lKeys.push_back( aKeys[j] );
+                                }
+                        }
+                }
+
+                return lKeys;
+        }
+
+protected:
+        virtual void onInsert() {}
+        virtual void onUpdate() {}
+        virtual void onDelete() {}
+        virtual void onReHash() {}
+
+        virtual void clearBits()
+        {
+                for( uint32_t j = 0; j < nKeysSize; j++ )
+                {
+                        bFilled[j] = bDeleted[j] = 0;
+                }
+        }
+
+        virtual void fill( uint32_t loc, key &k, value &v, uint32_t hash )
+        {
+                bFilled[loc/32] |= (1<<(loc%32));
+                va.construct( &aValues[loc], v );
+                ka.construct( &aKeys[loc], k );
+                aHashCodes[loc] = hash;
+                nFilled++;
+                //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
+                //      nFilled, nDeleted, nCapacity );
+        }
+
+        virtual void _erase( uint32_t loc )
+        {
+                bDeleted[loc/32] |= (1<<(loc%32));
+                va.destroy( &aValues[loc] );
+                ka.destroy( &aKeys[loc] );
+                nDeleted++;
+                //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
+                //      nFilled, nDeleted, nCapacity );
+        }
+
+        virtual std::pair<key,value> getAtPos( uint32_t nPos )
+        {
+                return std::pair<key,value>(aKeys[nPos],aValues[nPos]);
+        }
+        
+        virtual key &getKeyAtPos( uint32_t nPos )
+        {
+                return aKeys[nPos];
+        }
+        
+        virtual value &getValueAtPos( uint32_t nPos )
+        {
+                return aValues[nPos];
+        }
+
+        virtual uint32_t getFirstPos( bool &bFinished )
+        {
+                for( uint32_t j = 0; j < nCapacity; j++ )
+                {
+                        if( isFilled( j ) )
+                                if( !isDeleted( j ) )
+                                        return j;
+                }
+
+                bFinished = true;
+                return 0;
+        }
+
+        virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished )
+        {
+                for( uint32_t j = nPos+1; j < nCapacity; j++ )
+                {
+                        if( isFilled( j ) )
+                                if( !isDeleted( j ) )
+                                        return j;
+                }
+
+                bFinished = true;
+                return 0;
+        }
+
+        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<<j))%nCapacity, j++
+                        )
+                {
+                        // Is this the same hash code we were looking for?
+                        if( hash == aHashCodes[nCur] )
+                        {
+                                // Skip over deleted entries.  Deleted entries are also filled,
+                                // so we only have to do this check here.
+                                if( isDeleted( nCur ) )
+                                        continue;
+
+                                // Is it really the same key? (for safety)
+                                if( __cmpHashKeys( aKeys[nCur], k ) == true )
+                                {
+                                        bFill = true;
+                                        return nCur;
+                                }
+                        }
+                }
+
+                // This is our insurance, if the table is full, then go ahead and
+                // rehash, then try again.
+                if( isFilled( nCur ) && rehash == true )
+                {
+                        reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
+
+                        // This is potentially dangerous, and could cause an infinite loop.
+                        // Be careful writing probe, eh?
+                        return probe( hash, k, bFill );
+                }
+
+                bFill = false;
+                return nCur;
+        }
+
+        void reHash( uint32_t nNewSize )
+        {
+                //printf("---REHASH---");
+                //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
+                //      nFilled, nDeleted, nCapacity );
+                
+                // Save all the old data
+                uint32_t nOldCapacity = nCapacity;
+                uint32_t *bOldFilled = bFilled;
+                uint32_t *aOldHashCodes = aHashCodes;
+                uint32_t nOldKeysSize = nKeysSize;
+                uint32_t *bOldDeleted = bDeleted;
+                value *aOldValues = aValues;
+                key *aOldKeys = aKeys;
+                
+                // Calculate new sizes
+                nCapacity = nNewSize;
+                nKeysSize = bitsToBytes( nCapacity );
+        
+                // Allocate new memory + prep
+                bFilled = ca.allocate( nKeysSize );
+                bDeleted = ca.allocate( nKeysSize );
+                clearBits();
+
+                aHashCodes = ca.allocate( nCapacity );
+                aKeys = ka.allocate( nCapacity );
+                aValues = va.allocate( nCapacity );
+
+                nDeleted = nFilled = 0;
+
+                // Re-insert all of the old data (except deleted items)
+                for( uint32_t j = 0; j < nOldCapacity; j++ )
+                {
+                        if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
+                                (bOldDeleted[j/32]&(1<<(j%32)))==0 )
+                        {
+                                insert( aOldKeys[j], aOldValues[j] );
+                        }
+                }
+
+                // Delete all of the old data
+                for( uint32_t j = 0; j < nOldCapacity; j++ )
+                {
+                        if( (bOldFilled[j/32]&(1<<(j%32)))!=0 )
+                        {
+                                va.destroy( &aOldValues[j] );
+                                ka.destroy( &aOldKeys[j] );
+                        }
+                }
+                va.deallocate( aOldValues, nOldCapacity );
+                ka.deallocate( aOldKeys, nOldCapacity );
+                ca.deallocate( bOldFilled, nOldKeysSize );
+                ca.deallocate( bOldDeleted, nOldKeysSize );
+                ca.deallocate( aOldHashCodes, nOldCapacity );
+        }
+
+        virtual bool isFilled( uint32_t loc ) const
+        {
+                return (bFilled[loc/32]&(1<<(loc%32)))!=0;
+        }
+
+        virtual bool isDeleted( uint32_t loc )
+        {
+                return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
+        }
+
+protected:
+        uint32_t nCapacity;
+        uint32_t nFilled;
+        uint32_t nDeleted;
+        uint32_t *bFilled;
+        uint32_t *bDeleted;
+        uint32_t nKeysSize;
+        key *aKeys;
+        value *aValues;
+        uint32_t *aHashCodes;
+        valuealloc va;
+        keyalloc ka;
+        challoc ca;
+        sizecalc szCalc;
+};
+
+template<> uint32_t __calcHashCode<int>( const int &k );
+template<> bool __cmpHashKeys<int>( const int &a, const int &b );
+
+template<> uint32_t __calcHashCode<unsigned int>( const unsigned int &k );
+template<> bool __cmpHashKeys<unsigned int>( const unsigned int &a, const unsigned int &b );
+
+template<> uint32_t __calcHashCode<const char *>( const char * const &k );
+template<> bool __cmpHashKeys<const char *>( const char * const &a, const char * const &b );
+
+template<> uint32_t __calcHashCode<char *>( char * const &k );
+template<> bool __cmpHashKeys<char *>( char * const &a, char * const &b );
+
+template<> uint32_t __calcHashCode<std::string>( const std::string &k );
+template<> bool __cmpHashKeys<std::string>( const std::string &a, const std::string &b );
+
+template<> uint32_t __calcHashCode<Hashable>( const Hashable &k );
+template<> bool __cmpHashKeys<Hashable>( const Hashable &a, const Hashable &b );
+
+template<typename key, typename value>
+Serializer &operator<<( Serializer &ar, Hash<key,value> &h )
+{
+        ar << h.size();
+        for( typename Hash<key,value>::iterator i = h.begin(); i != h.end(); i++ )
+        {
+                std::pair<key,value> p = *i;
+                ar << p.first << p.second;
+        }
+
+        return ar;
+}
+
+template<typename key, typename value>
+Serializer &operator>>( Serializer &ar, Hash<key,value> &h )
+{
+        h.clear();
+        uint32_t nSize;
+        ar >> nSize;
+
+        for( uint32_t j = 0; j < nSize; j++ )
+        {
+                key k; value v;
+                ar >> k >> v;
+                h.insert( k, v );
+        }
+
+        return ar;
+}
+
+template<typename key, typename value>
+Serializer &operator&&( Serializer &ar, Hash<key,value> &h )
+{
+        if( ar.isLoading() )
+        {
+                return ar >> h;
+        }
+        else
+        {
+                return ar << h;
+        }
+}
+
+#endif