Public Member Functions
	LongHash (int startsize=32)
void	Grow ()
void	Shrink ()
void	SetSize (int newsize)
void	Clear ()
int	Capacity () const
int	Entries () const
ObjectT	Object (int i) const
ObjectT &	Object (int i)
void	SetObject (int i, ObjectT object)
unsigned int	Add (long long key, ObjectT object)
unsigned int	Find (long long key)
unsigned int	Rehash (long long key, unsigned int h)
LongHash &	operator= (const LongHash &rhs)
ObjectT	operator[] (int i) const
ObjectT	operator[] (unsigned int i) const
void	Delete (unsigned int index)
bool	SlotInUse (int index) const
bool	SlotInUse (unsigned int index) const
long long	GetKey (int index) const
long long	GetKey (const unsigned int index) const
void	SetAllowDuplicateKeys (bool toggle)

Protected Attributes
ObjectT *	objects
long long *	keys
bool *	occupancy
unsigned int	count
unsigned int	size
unsigned int	mask
bool	allowDuplicates

Detailed Description

template<class ObjectT>
class LongHash< ObjectT >

Definition at line 31 of file LongHash.h.

Constructor & Destructor Documentation

◆ LongHash()

template<class ObjectT>

LongHash< ObjectT >::LongHash ( int startsize = 32 )

inline

Definition at line 42 of file LongHash.h.

    {
        count = 0;
        size  = startsize;
        mask  = startsize - 1;
 
        // In this implementation, the size of hash tables must be a power of two
        if (startsize & mask)
            error("LongHash: Hash table size must be a power of two.\n");
 
        occupancy = new bool [size];
        objects = new ObjectT [size];
        keys    = new long long [size];
 
        allowDuplicates = false;
 
        for (unsigned int i = 0; i < size; i++)
        {
            occupancy[i] = false;
        }
    };

◆ ~LongHash()

template<class ObjectT>

LongHash< ObjectT >::~LongHash ( )

inline

Definition at line 64 of file LongHash.h.

    {
        delete [] occupancy;
        delete [] objects;
        delete [] keys;
    }

Member Function Documentation

◆ Add()

template<class ObjectT>

unsigned int LongHash< ObjectT >::Add	(	long long	key,
		ObjectT	object )

inline

Definition at line 154 of file LongHash.h.

    {
        if (count * 2 > size)
            Grow();
 
        unsigned int h = Iterate(key);
 
        while (allowDuplicates && occupancy[h] && objects[h] != object)
            h = ReIterate(key, h);
 
        if (!occupancy[h])
        {
            occupancy[h] = true;
            keys[h] = key;
            count++;
        }
 
        objects[h] = object;
 
        return h;
    }

◆ Capacity()

template<class ObjectT>

int LongHash< ObjectT >::Capacity ( ) const

inline

Definition at line 131 of file LongHash.h.

    {
        return size;
    }

◆ Clear()

template<class ObjectT>

void LongHash< ObjectT >::Clear ( )

inline

Definition at line 120 of file LongHash.h.

    {
        count = 0;
 
        if (size > 32)
            SetSize(32);
 
        for (unsigned int i = 0; i < size; i++)
            occupancy[i] = false;
    }

◆ Delete()

template<class ObjectT>

void LongHash< ObjectT >::Delete ( unsigned int index )

inline

Definition at line 201 of file LongHash.h.

    {
        if (index >= size || !occupancy[index])
            return;
 
        occupancy[index] = false;
        count--;
 
        if (count * 8 < size && size > 32)
            Shrink();
        else
        {
            // rehash the next entries until we find empty slot
            index = (index + 1) & mask;
 
            while (occupancy[index])
            {
                if ((keys[index] & mask) != index)
                {
                    unsigned int h = Iterate(keys[index]);
 
                    while (occupancy[h] && objects[h] != objects[index])
                        h = ReIterate(keys[index], h);
 
                    if (h != (unsigned int) index)
                    {
                        keys[h] = keys[index];
                        occupancy[h] = true;
                        objects[h] = objects[index];
 
                        occupancy[index] = false;
                    }
                }
 
                index = (index + 1) & mask;
            }
        }
    }

◆ Entries()

template<class ObjectT>

int LongHash< ObjectT >::Entries ( ) const

inline

Definition at line 135 of file LongHash.h.

    {
        return count;
    }

◆ Find()

template<class ObjectT>

unsigned int LongHash< ObjectT >::Find ( long long key )

inline

Definition at line 176 of file LongHash.h.

    {
        unsigned int h = Iterate(key);
 
        return occupancy[h] ? h : LH_NOTFOUND;
    }

◆ GetKey() [1/2]

template<class ObjectT>

long long LongHash< ObjectT >::GetKey ( const unsigned int index ) const

inline

Definition at line 256 of file LongHash.h.

    {
        return keys[index];
    }

◆ GetKey() [2/2]

template<class ObjectT>

long long LongHash< ObjectT >::GetKey ( int index ) const

inline

Definition at line 251 of file LongHash.h.

    {
        return keys[index];
    }

◆ Grow()

template<class ObjectT>

void LongHash< ObjectT >::Grow ( )

inline

Definition at line 71 of file LongHash.h.

    {
        SetSize(size * 2);
    }

◆ Object() [1/2]

template<class ObjectT>

ObjectT & LongHash< ObjectT >::Object ( int i )

inline

Definition at line 144 of file LongHash.h.

    {
        return objects[i];
    }

◆ Object() [2/2]

template<class ObjectT>

ObjectT LongHash< ObjectT >::Object ( int i ) const

inline

Definition at line 140 of file LongHash.h.

    {
        return objects[i];
    }

◆ operator[]() [1/2]

template<class ObjectT>

ObjectT LongHash< ObjectT >::operator[] ( int i ) const

inline

Definition at line 192 of file LongHash.h.

    {
        return objects[i];
    }

◆ operator[]() [2/2]

template<class ObjectT>

ObjectT LongHash< ObjectT >::operator[] ( unsigned int i ) const

inline

Definition at line 196 of file LongHash.h.

    {
        return objects[i];
    }

◆ Rehash()

template<class ObjectT>

unsigned int LongHash< ObjectT >::Rehash	(	long long	key,
		unsigned int	h )

inline

Definition at line 183 of file LongHash.h.

    {
        h = ReIterate(key, h);
 
        return occupancy[h] ? h : LH_NOTFOUND;
    }

◆ SetAllowDuplicateKeys()

template<class ObjectT>

void LongHash< ObjectT >::SetAllowDuplicateKeys ( bool toggle )

inline

Definition at line 261 of file LongHash.h.

    {
        allowDuplicates = toggle;
 
        if (count && !allowDuplicates)
            SetSize(size);
    }

◆ SetObject()

template<class ObjectT>

void LongHash< ObjectT >::SetObject	(	int	i,
		ObjectT	object )

inline

Definition at line 149 of file LongHash.h.

    {
        objects[i] = object;
    }

◆ SetSize()

template<class ObjectT>

void LongHash< ObjectT >::SetSize ( int newsize )

inline

Definition at line 80 of file LongHash.h.

    {
        int newmask = newsize - 1;
 
        bool      * newoccupancy = new bool [newsize];
        ObjectT   * newobjects = new ObjectT [newsize];
        long long * newkeys = new long long [newsize];
 
        for (int i = 0; i < newsize; i++)
            newoccupancy[i] = false;
 
        if (count)
            for (unsigned int i = 0; i < size; i++)
                if (occupancy[i] != false)
                {
                    long long  key = keys[i];
                    unsigned int h = newmask & (unsigned int) key;
 
                    while (newoccupancy[h] == true && (newkeys[h] != key || allowDuplicates))
                        h = (h + 1) & newmask;
 
                    if (newoccupancy[h])
                        count--;
 
                    newkeys[h] = key;
                    newobjects[h] = objects[i];
                    newoccupancy[h] = true;
                }
 
        delete [] occupancy;
        delete [] objects;
        delete [] keys;
 
        occupancy = newoccupancy;
        objects = newobjects;
        keys = newkeys;
        size = newsize;
        mask = newmask;
    }

◆ Shrink()

template<class ObjectT>

void LongHash< ObjectT >::Shrink ( )

inline

Definition at line 75 of file LongHash.h.

    {
        SetSize(size / 2);
    }

◆ SlotInUse() [1/2]

template<class ObjectT>

bool LongHash< ObjectT >::SlotInUse ( int index ) const

inline

Definition at line 241 of file LongHash.h.

    {
        return occupancy[index] == true;
    }

◆ SlotInUse() [2/2]

template<class ObjectT>

bool LongHash< ObjectT >::SlotInUse ( unsigned int index ) const

inline

Definition at line 245 of file LongHash.h.

    {
        return occupancy[index] == true;
    }

Member Data Documentation

◆ allowDuplicates

template<class ObjectT>

bool LongHash< ObjectT >::allowDuplicates

protected

Definition at line 39 of file LongHash.h.

◆ count

template<class ObjectT>

unsigned int LongHash< ObjectT >::count

protected

Definition at line 37 of file LongHash.h.

◆ keys

template<class ObjectT>

long long* LongHash< ObjectT >::keys

protected

Definition at line 35 of file LongHash.h.

◆ mask

template<class ObjectT>

unsigned int LongHash< ObjectT >::mask

protected

Definition at line 38 of file LongHash.h.

◆ objects

template<class ObjectT>

ObjectT* LongHash< ObjectT >::objects

protected

Definition at line 34 of file LongHash.h.

◆ occupancy

template<class ObjectT>

bool* LongHash< ObjectT >::occupancy

protected

Definition at line 36 of file LongHash.h.

◆ size

template<class ObjectT>

unsigned int LongHash< ObjectT >::size

protected

Definition at line 37 of file LongHash.h.

The documentation for this class was generated from the following file:

general/LongHash.h

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ LongHash()

◆ ~LongHash()

Member Function Documentation

◆ Add()

◆ Capacity()

◆ Clear()

◆ Delete()

◆ Entries()

◆ Find()

◆ GetKey() [1/2]

◆ GetKey() [2/2]

◆ Grow()

◆ Object() [1/2]

◆ Object() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ Rehash()

◆ SetAllowDuplicateKeys()

◆ SetObject()

◆ SetSize()

◆ Shrink()

◆ SlotInUse() [1/2]

◆ SlotInUse() [2/2]

Member Data Documentation

◆ allowDuplicates

◆ count

◆ keys

◆ mask

◆ objects

◆ occupancy

◆ size