BasicHash Class Reference

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

Protected Attributes
void **	objects
unsigned int *	keys
unsigned int	count
unsigned int	size
unsigned int	mask

Detailed Description

Definition at line 23 of file BasicHash.h.

Constructor & Destructor Documentation

BasicHash()

BasicHash::BasicHash

(

int

startsize = 32

)

Definition at line 23 of file BasicHash.cpp.

{
    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("BasicHash: Hash table size must be a power of two.\n");
 
    objects = new void * [size];
    keys    = new unsigned int [size];
 
    for (unsigned int i = 0; i < size; i++)
    {
        objects[i] = NULL;
    }
};

~BasicHash()

BasicHash::~BasicHash ( )

virtual

Definition at line 42 of file BasicHash.cpp.

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

Member Function Documentation

Add()

int BasicHash::Add	(	int	key,
		void *	object = NULL
	)

Definition at line 96 of file BasicHash.cpp.

{
    if (count * 2 > size)
        Grow();
 
    unsigned int h = Iterate(key);
 
    while ((objects[h] != NULL) && (objects[h] != object))
        h = ReIterate(key, h);
 
    if (objects[h] == NULL)
    {
//      printf("At position %d, inserted %x\n", h, key);
        keys[h] = key;
        count++;
    }
 
    objects[h] = object;
 
    return h;
}

Capacity()

int BasicHash::Capacity ( ) const

inline

Definition at line 48 of file BasicHash.h.

    {
        return size;
    }

Clear()

void BasicHash::Clear

(

)

Definition at line 48 of file BasicHash.cpp.

{
//   printf("Clearing...\n");
 
    count = 0;
 
    if (size > 16)
        SetSize(16);
 
    for (unsigned int i = 0; i < size; i++)
        objects[i] = NULL;
}

Delete()

void BasicHash::Delete

(

unsigned int

index

)

Definition at line 132 of file BasicHash.cpp.

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

Entries()

int BasicHash::Entries ( ) const

inline

Definition at line 52 of file BasicHash.h.

    {
        return count;
    }

Find()

int BasicHash::Find

(

int

key

)

Definition at line 118 of file BasicHash.cpp.

{
    int h = Iterate(key);
 
    return objects[h] == NULL ? -1 : h;
}

Grow()

void BasicHash::Grow ( )

inline

Definition at line 35 of file BasicHash.h.

    {
        SetSize(size * 2);
    }

Object()

void * BasicHash::Object ( int  i ) const

inline

Definition at line 57 of file BasicHash.h.

    {
        return objects[i];
    }

operator[]()

void * BasicHash::operator[] ( int  i ) const

inline

Definition at line 73 of file BasicHash.h.

    {
        return objects[i];
    }

Rehash()

int BasicHash::Rehash	(	int	key,
		int	h
	)

Definition at line 125 of file BasicHash.cpp.

{
    h = ReIterate(key, h);
 
    return objects[h] == NULL ? -1 : h;
}

SetObject()

void BasicHash::SetObject ( int  i, void *  object  )

inline

Definition at line 62 of file BasicHash.h.

    {
        objects[i] = object;
    }

SetSize()

void BasicHash::SetSize

(

int

newsize

)

Definition at line 61 of file BasicHash.cpp.

{
    int newmask = newsize - 1;
 
    void     ** newobjects = new void * [newsize];
    unsigned int * newkeys = new unsigned int [newsize];
 
    for (int i = 0; i < newsize; i++)
    {
        newobjects[i] = NULL;
    }
 
    if (count)
        for (unsigned int i = 0; i < size; i++)
            if (objects[i] != NULL)
            {
                unsigned int key = keys[i];
                unsigned int h   = key & newmask;
 
                while (newobjects[h] != NULL && newkeys[h] != h)
                    h = (h + 1) & newmask;
 
                newkeys[h] = key;
                newobjects[h] = objects[i];
            }
 
    delete [] objects;
    delete [] keys;
 
    objects = newobjects;
    keys = newkeys;
    size = newsize;
    mask = newmask;
}

Shrink()

void BasicHash::Shrink ( )

inline

Definition at line 39 of file BasicHash.h.

    {
        SetSize(size / 2);
    }

SlotInUse()

bool BasicHash::SlotInUse ( int  index )

inline

Definition at line 80 of file BasicHash.h.

    {
        return objects[index] != NULL;
    }

Member Data Documentation

count

unsigned int BasicHash::count

protected

Definition at line 28 of file BasicHash.h.

keys

unsigned int* BasicHash::keys

protected

Definition at line 27 of file BasicHash.h.

mask

unsigned int BasicHash::mask

protected

Definition at line 29 of file BasicHash.h.

objects

void** BasicHash::objects

protected

Definition at line 26 of file BasicHash.h.

size

unsigned int BasicHash::size

protected

Definition at line 28 of file BasicHash.h.

---

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

• general/BasicHash.h
• general/BasicHash.cpp