BasicHash.cpp

/*
 *  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/>.
 */

#include "BasicHash.h"
#include "Error.h"

#include <stdio.h>

BasicHash::BasicHash(int startsize)
{
    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()
{
    delete [] objects;
    delete [] keys;
}

void BasicHash::Clear()
{
//   printf("Clearing...\n");

    count = 0;

    if (size > 16)
        SetSize(16);

    for (unsigned int i = 0; i < size; i++)
        objects[i] = NULL;
}

void BasicHash::SetSize(int newsize)
{
    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;
}

int BasicHash::Add(int key, void * object)
{
    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;
}

int BasicHash::Find(int key)
{
    int h = Iterate(key);

    return objects[h] == NULL ? -1 : h;
}

int BasicHash::Rehash(int key, int h)
{
    h = ReIterate(key, h);

    return objects[h] == NULL ? -1 : h;
}

void BasicHash::Delete(unsigned int index)
{
    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;
        }
    }
}