---

Hash.h

Go to the documentation of this file.

/*
    File:       Hash.h

    Function:   Defines a string-based hash table

    Author:     Andrew Willmott

    Copyright:  
*/

#ifndef __Hash__
#define __Hash__

#include "cl/String.h"
#include "cl/Array.h"

class HashEntry
{
public:
    Char        *key;
    ULong       hash;
    Void        *data;
};

class HashIter
{
public:
    virtual Void    ProcessVoidItem(StrConst s, Void *data) = 0;
};

class Hash
{
public:
    Hash(Int n = 0);
    
    Void            SetVoidItem(StrConst s, Void *data);
    Void            *GetVoidItem(StrConst s)
                    {
                        HashEntry *he = Find(s);
                        if (he && he->key)
                            return(he->data);
                        else
                            return(0);
                    };
    Bool            ItemExists(StrConst s)
                    { 
                        HashEntry *he = Find(s);
                        return(he && he->data);
                    };
                    
    Void            DeleteItem(StrConst s);
                    // delete item s
    Void            Iterate(HashIter &iter);
                    // iterate over all keys

    // low-level functions

    HashEntry       *Find(StrConst s);
                    // returns the entry corresponding to the key if it exists,
                    // or a new entry if not. if the latter, you must set the
                    // key field to indicate it's being used.
                    // returns 0 if we ran out of memory.
    Int             Init(Int n);
                    // (re)initialises table, assuming max of n entries
                    // returns the number of entries in the new table

                    // delete s's entry
    virtual Void    FreeData(Void *data);

    Void            FreeKey(Char *key);
    Void            FreeTable();

    ULong           CalcHash(StrConst s);
    
protected:

    Array<HashEntry>    table;
    Int                 numDeleted;
    Bool                copyKey;
};

// This is here both as an example, and the most commonly used hash.
// For any data-specific hash, you will need to override FreeData() to
// correctly dispose of the data (if necessary), and will probably
// want to create your own SetItem/GetItem methods as below.

class IntHash : public Hash
{
public:
    Void        SetItem(StrConst s, Int a)
                { SetVoidItem(s, (Void *) (a + 1)); };

    Int         GetItem(StrConst s) 
                { return(((SAddrInt) GetVoidItem(s)) - 1); };

    Void        FreeData(Void *data)
                {};
};

class IntHashIter : public HashIter
{
public:
    virtual Void    ProcessItem(StrConst s, Int a) = 0;
    virtual Void    ProcessVoidItem(StrConst s, Void *data)
                    { ProcessItem(s, ((SAddrInt) data) - 1); };
};

#endif

---