---

Hash.cc

Go to the documentation of this file.

/*
    File:       Hash.cc

    Function:   Provides a string-based hash table

    Author:     Andrew Willmott, using C code from Greg Ward

    Notes:      When a hash entry is deleted, we can't just clear it completely,
                as it might be part of a chain, and doing so would make it
                impossible to find all entries after it.

                Instead, the data field is set to zero, to mark it as
                deleted, and these entries are reclaimed only when the
                hash table fills up.  

                This is mostly taken from Greg Ward's code in mgflib

                indicators:
                    key == null -> empty entry
                    otherwise
                    data == null -> deleted entry
*/

#include "cl/Hash.h"

#include <stdio.h>

const Int tHashSize[] =
{
     31, 61, 127, 251, 509, 1021, 2039, 4093,
     8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573,
     2097143, 4194301, 8388593, 0
};

Hash::Hash(Int n) : copyKey(true)
{
    if (n > 0)
        Init(n);
}

Int Hash::Init(Int n)
{
    const Int   *hsp;
    Int         i;

    // aim for 66% occupancy
    n += n / 2;

    // find a good prime size for our table
    for (hsp = tHashSize; *hsp; hsp++)
        if (*hsp > n)
            break;

    if (*hsp == 0)
        // too big for our table!
        n = n * 2 + 1;      // not always prime, but hey...
    else
        n = *hsp;

    table.SetSize(n);
    for (i = 0; i < table.NumItems(); i++)
    {
        table[i].key = 0;
        table[i].hash = 0;
        table[i].data = 0;
    }

    numDeleted = 0;

    return(table.NumItems());
}

const Byte tShuffle[256] =
{
    0, 157, 58, 215, 116, 17, 174, 75, 232, 133, 34,
    191, 92, 249, 150, 51, 208, 109, 10, 167, 68, 225,
    126, 27, 184, 85, 242, 143, 44, 201, 102, 3, 160,
    61, 218, 119, 20, 177, 78, 235, 136, 37, 194, 95,
    252, 153, 54, 211, 112, 13, 170, 71, 228, 129, 30,
    187, 88, 245, 146, 47, 204, 105, 6, 163, 64, 221,
    122, 23, 180, 81, 238, 139, 40, 197, 98, 255, 156,
    57, 214, 115, 16, 173, 74, 231, 132, 33, 190, 91,
    248, 149, 50, 207, 108, 9, 166, 67, 224, 125, 26,
    183, 84, 241, 142, 43, 200, 101, 2, 159, 60, 217,
    118, 19, 176, 77, 234, 135, 36, 193, 94, 251, 152,
    53, 210, 111, 12, 169, 70, 227, 128, 29, 186, 87,
    244, 145, 46, 203, 104, 5, 162, 63, 220, 121, 22,
    179, 80, 237, 138, 39, 196, 97, 254, 155, 56, 213,
    114, 15, 172, 73, 230, 131, 32, 189, 90, 247, 148,
    49, 206, 107, 8, 165, 66, 223, 124, 25, 182, 83,
    240, 141, 42, 199, 100, 1, 158, 59, 216, 117, 18,
    175, 76, 233, 134, 35, 192, 93, 250, 151, 52, 209,
    110, 11, 168, 69, 226, 127, 28, 185, 86, 243, 144,
    45, 202, 103, 4, 161, 62, 219, 120, 21, 178, 79,
    236, 137, 38, 195, 96, 253, 154, 55, 212, 113, 14,
    171, 72, 229, 130, 31, 188, 89, 246, 147, 48, 205,
    106, 7, 164, 65, 222, 123, 24, 181, 82, 239, 140,
    41, 198, 99
};

ULong Hash::CalcHash(StrConst s)
{
    Int     i = 0;
    ULong   result = 0;
    Byte    *t = (Byte *) (const Char *) s;

    while (*t)
            result ^= (ULong) tShuffle[*t++] << ((i += 11) & 0x0F);

    return(result);
}


HashEntry *Hash::Find(StrConst s)
// find a table entry 
{
    ULong       hash;
    Int         i, n;
    Int         ndx;
    HashEntry   *le;
    
    // look up object 

    if (table.NumItems() == 0)
        if (!Init(16))
            return(0);

    hash = CalcHash(s);

    // this is a closed hash table. if there's a collision, we
    // chain by x^2. i.e. positions n, n + 1, n + 4, n + 9...
    // belong to the same bucket.

    // start from the hash
    ndx = hash % table.NumItems();
    
    for (i = 0, n = 1; i < table.NumItems(); i++, n += 2)
    {
        // look at next entry in the chain
        le = &table[ndx];

        if (le->key == 0)
        // the entry is free: return it for the user to (maybe) fill in
        {
            le->hash = hash;
            return(le);
        }

        if (le->hash == hash && (le->key == s))
        // we have a match!
        {
            return(le);
        }

        // find next entry in the chain
        ndx += n;
        if (ndx >= table.NumItems())
            ndx = ndx % table.NumItems();
    }

    // table is full; reallocate 

    Array<HashEntry>    oldTable;

    oldTable.Replace(table);

    // try to resize table
    if (!Init(table.NumItems() - numDeleted + 1))
    {
        // revert back to old table & return if ran out of memory
        table.Replace(oldTable);        
        return(0);
    }
    
    // copy contents of old table to the new...
    ndx = oldTable.NumItems();
    while (ndx--)
        if (oldTable[ndx].key != 0)
            if (oldTable[ndx].data != 0)
                // in-use entry
                *Find(oldTable[ndx].key) = oldTable[ndx];
            else 
                // deleted entry
                FreeKey(oldTable[ndx].key);

    oldTable.Clear();

    return(Find(s));
}

Void Hash::SetVoidItem(StrConst s, Void *data)
{
    HashEntry *he = Find(s);
    if (he)
    {
        if (copyKey)
        {
            he->key = new Char[s.Length() + 1];
            strcpy(he->key, s);
        }
        else
            he->key = (Char *) (const Char *) s;

        if (he->data)
            FreeData(he->data);
        he->data = data;
    }
};

Void Hash::DeleteItem(StrConst s)
{
    HashEntry   *le;

    le = Find(s);
    if (!le)
        return;

    // something to free?
    if (le->key == 0 || le->data == 0)
        return;
        
    FreeData(le);
    le->data = 0;

    numDeleted++;
}

Void Hash::Iterate(HashIter &iter)
{
    Int     i;

    for (i = 0; i < table.NumItems(); i++)
        if (table[i].key && table[i].data)
            iter.ProcessVoidItem(table[i].key, table[i].data);
}

Void Hash::FreeData(Void *data)
{
}

Void Hash::FreeKey(Char *key)
{
    if (copyKey)
        delete key;
    key = 0;
}

Void Hash::FreeTable()
// free table and contents
{
    Int     i;
    
    for (i = 0; i < table.NumItems(); i++)
        if (table[i].key != 0)
        {
            FreeKey(table[i].key);
            if (table[i].data != 0)
                FreeData(&table[i]);
        }

    table.Clear();
    numDeleted = 0;
}
 
#ifdef CL_SGI_INST
#pragma instantiate Array<HashEntry>
#endif

---