Loading...
Searching...
No Matches
LongHash< ObjectT > Class Template Reference

## 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
Definition LongHash.h:32

## ~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