LongHash.h
/*
* Copyright (C) 2010 Regents of the University of Michigan
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef __LONGHASH_H__
#define __LONGHASH_H__
#include "Error.h"
#include <limits.h>
#ifdef UINT_MAX
#define LH_NOTFOUND (UINT_MAX)
#else
#define LH_NOTFOUND 0xFFFFFFFF
#endif
template <class ObjectT> class LongHash
{
protected:
ObjectT * objects;
long long * keys;
bool * occupancy;
unsigned int count, size;
unsigned int mask;
bool allowDuplicates;
public:
LongHash(int startsize = 32)
{
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()
{
delete [] occupancy;
delete [] objects;
delete [] keys;
}
void Grow()
{
SetSize(size * 2);
}
void Shrink()
{
SetSize(size / 2);
}
void SetSize(int newsize)
{
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;
}
void Clear()
{
count = 0;
if (size > 32)
SetSize(32);
for (unsigned int i = 0; i < size; i++)
occupancy[i] = false;
}
int Capacity() const
{
return size;
}
int Entries() const
{
return count;
}
ObjectT Object(int i) const
{
return objects[i];
}
ObjectT & Object(int i)
{
return objects[i];
}
void SetObject(int i, ObjectT object)
{
objects[i] = object;
}
unsigned int Add(long long key, ObjectT object)
{
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;
}
unsigned int Find(long long key)
{
unsigned int h = Iterate(key);
return occupancy[h] ? h : LH_NOTFOUND;
}
unsigned int Rehash(long long key, unsigned int h)
{
h = ReIterate(key, h);
return occupancy[h] ? h : LH_NOTFOUND;
}
LongHash & operator = (const LongHash & rhs);
ObjectT operator [](int i) const
{
return objects[i];
}
ObjectT operator [](unsigned int i) const
{
return objects[i];
}
void Delete(unsigned int index)
{
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;
}
}
}
bool SlotInUse(int index) const
{
return occupancy[index] == true;
}
bool SlotInUse(unsigned int index) const
{
return occupancy[index] == true;
}
// Accessor to get a key.
long long GetKey(int index) const
{
return keys[index];
}
long long GetKey(const unsigned int index) const
{
return keys[index];
}
void SetAllowDuplicateKeys(bool toggle)
{
allowDuplicates = toggle;
if (count && !allowDuplicates)
SetSize(size);
}
private:
unsigned int Iterate(long long key) const
{
unsigned int h = mask & (unsigned int) key;
while (occupancy[h] == true && keys[h] != key)
h = (h + 1) & mask;
return h;
}
unsigned int ReIterate(long long key, unsigned int h) const
{
h = (h + 1) & mask;
while (occupancy[h] == true && keys[h] != key)
h = (h + 1) & mask;
return h;
}
};
#endif
LongHash
Definition: LongHash.h:31