IntHash Class Reference

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

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

Detailed Description

Definition at line 40 of file IntHash.h.

Constructor & Destructor Documentation

IntHash()

IntHash::IntHash

(

int

startsize = 32

)

Definition at line 23 of file IntHash.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("IntHash: Hash table size must be a power of two.\n");
 
    objects = new bool [size];
    keys    = new unsigned int [size];
 
    for (unsigned int i = 0; i < size; i++)
    {
        objects[i] = false;
    }
};

~IntHash()

IntHash::~IntHash ( )

virtual

Definition at line 42 of file IntHash.cpp.

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

Member Function Documentation

Add()

int IntHash::Add	(	int	key,
		bool	object = true
	)

Definition at line 96 of file IntHash.cpp.

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

Capacity()

int IntHash::Capacity ( ) const

inline

Definition at line 65 of file IntHash.h.

    {
        return size;
    }

Clear()

void IntHash::Clear

(

)

Definition at line 48 of file IntHash.cpp.

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

Delete()

void IntHash::Delete

(

unsigned int

index

)

Definition at line 132 of file IntHash.cpp.

{
    if (index >= size || objects[index] == false)
        return;
 
    objects[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 (objects[index] != false)
        {
            if ((keys[index] & mask) != index)
            {
                unsigned int h = Iterate(keys[index]);
 
                while ((objects[h] != false) && (objects[h] != objects[index]))
                    h = ReIterate(keys[index], h);
 
                if (h != (unsigned int) index)
                {
                    keys[h] = keys[index];
                    objects[h] = objects[index];
                    objects[index] = false;
                }
            }
 
            index = (index + 1) & mask;
        }
    }
}

Entries()

int IntHash::Entries ( ) const

inline

Definition at line 69 of file IntHash.h.

    {
        return count;
    }

Find()

int IntHash::Find

(

int

key

)

Definition at line 118 of file IntHash.cpp.

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

Grow()

void IntHash::Grow ( )

inline

Definition at line 52 of file IntHash.h.

    {
        SetSize(size * 2);
    }

Object()

bool IntHash::Object ( int  i ) const

inline

Definition at line 74 of file IntHash.h.

    {
        return objects[i];
    }

operator[]()

bool IntHash::operator[] ( int  i ) const

inline

Definition at line 90 of file IntHash.h.

    {
        return objects[i];
    }

Rehash()

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

Definition at line 125 of file IntHash.cpp.

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

SetObject()

void IntHash::SetObject ( int  i, bool  object  )

inline

Definition at line 79 of file IntHash.h.

    {
        objects[i] = object;
    }

SetSize()

void IntHash::SetSize

(

int

newsize

)

Definition at line 61 of file IntHash.cpp.

{
    int newmask = newsize - 1;
 
    bool      * newobjects = new bool [newsize];
    unsigned int * newkeys = new unsigned int [newsize];
 
    for (int i = 0; i < newsize; i++)
    {
        newobjects[i] = false;
    }
 
    if (count)
        for (unsigned int i = 0; i < size; i++)
            if (objects[i] != false)
            {
                unsigned int key = keys[i];
                unsigned int h   = key & newmask;
 
                while (newobjects[h] != false && 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 IntHash::Shrink ( )

inline

Definition at line 56 of file IntHash.h.

    {
        SetSize(size / 2);
    }

SlotInUse()

bool IntHash::SlotInUse ( int  index )

inline

Definition at line 97 of file IntHash.h.

    {
        return objects[index] != false;
    }

Member Data Documentation

count

unsigned int IntHash::count

protected

Definition at line 45 of file IntHash.h.

keys

unsigned int* IntHash::keys

protected

Definition at line 44 of file IntHash.h.

mask

unsigned int IntHash::mask

protected

Definition at line 46 of file IntHash.h.

objects

bool* IntHash::objects

protected

Definition at line 43 of file IntHash.h.

size

unsigned int IntHash::size

protected

Definition at line 45 of file IntHash.h.

---

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

• general/IntHash.h
• general/IntHash.cpp