Loading...
Searching...
No Matches
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