GHashTable.h

#ifndef _GHashTbl_H_
#define _GHashTbl_H_

#include <ctype.h>
#include "GArray.h"
#include "GString.h"

template<typename CHAR>
uint LgiHash(CHAR *v, int l, bool Case)
{
    uint32 h = 0;

    if (Case)
    {
        // case sensitive
        if (l > 0)
        {
            while (l--)
            {
                h = (h << 5) - h + *v++;
            }
        }
        else
        {
            for (; *v; v ++)
            {
                h = (h << 5) - h + *v;
            }
        }
    }
    else
    {
        // case insensitive
        CHAR c;
        if (l > 0)
        {
            while (l--)
            {
                c = tolower(*v);
                v++;
                h = (h << 5) - h + c;
            }
        }
        else
        {
            for (; *v; v++)
            {
                c = tolower(*v);
                h = (h << 5) - h + c;
            }
        }
    }

    return h;
}

#define HASH_TABLE_SHRINK_THRESHOLD         15
#define HASH_TABLE_GROW_THRESHOLD           50

template<typename Key, typename Value>
class GHashTbl
{
    Key NullKey;
    Value NullValue;

    template<typename T>
    struct KeyPool
    {
        int Size;
        int Used;
        char *Mem;

        KeyPool()
        {
            Size = 64 << 10;
            Used = 0;
            Mem = new char[Size];
        }

        ~KeyPool()
        {
            DeleteArray(Mem);
        }

        int New(int i)
        {
            return i;
        }
        
        void *New(void *i)
        {
            return i;
        }
        
        char *New(char *s)
        {
            int Len = strlen(s) + 1;
            if (Used < Size - Len)
            {
                char *p = Mem + Used;
                strcpy(p, s);
                Used += Len;
                return p;
            }
            return 0;
        }

        char16 *New(char16 *s)
        {
            int Len = StrlenW(s) + sizeof(char16);
            if (Used < Size - Len)
            {
                char16 *p = (char16*) (Mem + Used);
                StrcpyW(p, s);
                Used += Len;
                return p;
            }
            return 0;
        }
    };

    struct Entry
    {
        Key k;
        Value v;
    };

    int Size;
    int Cur;
    int Used;
    bool Case;
    Entry *Table;
    int SizeBackup; // temp variable for debugging

    bool Pool;
    
    typedef GArray<KeyPool<Key>*> KeyPoolArr;
    KeyPoolArr Pools;

    int Percent()
    {
        return Used * 100 / Size;
    }

    bool GetEntry(Key k, int &Index, bool Debug = false)
    {
        if (k != NullKey && Table)
        {
            uint32 h = Hash(k);

            for (int i=0; i<Size; i++)
            {
                Index = (h + i) % Size;
                LgiAssert(Index >= 0);

                if (Table[Index].k == NullKey)
                    return false;
                    
                if (CmpKey(Table[Index].k, k))
                    return true;
            }
        }

        return false;
    }

    bool Between(int Val, int Min, int Max)
    {
        if (Min <= Max)
        {
            // Not wrapped
            return Val >= Min AND Val <= Max;
        }
        else
        {
            // Wrapped
            return Val <= Max OR Val >= Min;
        }
    }

    // Type specific implementations

        // char
            uint Hash(char *s) { return LgiHash<uchar>((uchar*)s, 0, Case); }
            char *CopyKey(char *a) { return NewStr(a); }
            int SizeKey(char *a) { return strlen(a) + 1; }
            void FreeKey(char *&a) { DeleteArray(a); }
            bool CmpKey(char *a, char *b)
            {
                if (Case)
                    return strcmp(a, b) == 0;
                else
                    #ifdef WIN32
                    return stricmp(a, b) == 0;
                    #else
                    return strcasecmp(a, b) == 0;
                    #endif
            }

        // char16
            uint Hash(char16 *s) { return LgiHash<char16>(s, 0, Case); }
            char16 *CopyKey(char16 *a) { return NewStrW(a); }
            int SizeKey(char16 *a) { return StrlenW(a) + 1; }
            void FreeKey(char16 *&a) { DeleteArray(a); }
            bool CmpKey(char16 *a, char16 *b)
            {
                if (Case)
                    return StrcmpW(a, b) == 0;
                else
                    return StricmpW(a, b) == 0;
            }

        // int
            uint Hash(int s) { return s; }
            int CopyKey(int a) { return a; }
            int SizeKey(int a) { return sizeof(a); }
            void FreeKey(int &a) { memcpy(&a, &NullKey, sizeof(a)); }
            bool CmpKey(int a, int b)
            {
                return a == b;
            }

        // int64
            uint Hash(int64 s) { return s; }
            int CopyKey(int64 a) { return a; }
            int SizeKey(int64 a) { return sizeof(a); }
            void FreeKey(int64 &a) { memcpy(&a, &NullKey, sizeof(a)); }
            bool CmpKey(int64 a, int64 b)
            {
                return a == b;
            }

        // void*
            uint Hash(void *s) { return ((uint)s)/31; }
            void *CopyKey(void *a) { return a; }
            int SizeKey(void *a) { return sizeof(a); }
            void FreeKey(void *&a) { memcpy(&a, &NullKey, sizeof(a)); }
            bool CmpKey(void *a, void *b)
            {
                return a == b;
            }

    void InitializeTable(Entry *e, int len)
    {
        if (!e || len < 1) return;
        while (len--)
        {
            e->k = NullKey;
            e->v = NullValue;
            e++;
        }
    }

public:
    GHashTbl
    (
        int size = 0,
        bool is_case = true,
        Key nullkey = 0,
        Value nullvalue = (Value)0
    )
    {
        NullKey = nullkey;
        NullValue = nullvalue;
        Used = 0;
        Cur = -1;
        Case = is_case;
        Pool = false;
        SizeBackup = Size = size ? max(size, 16) : 512;
        LgiAssert(Size < 10000);
        
        if (Table = new Entry[Size])
        {
            InitializeTable(Table, Size);
        }
    }
    
    virtual ~GHashTbl()
    {
        Empty();
        DeleteArray(Table);
    }

    GHashTbl<Key, Value> &operator =(GHashTbl<Key, Value> &c)
    {
        if (IsOk() && c.IsOk())
        {
            Empty();

            NullKey = c.NullKey;
            NullValue = c.NullValue;
            Case = c.Case;
            Pool = c.Pool;

            int Added = 0;
            for (int i=0; i<c.Size; i++)
            {
                if (c.Table[i].k != c.NullKey)
                {
                    Added += Add(c.Table[i].k, c.Table[i].v) ? 1 : 0;
                    LgiAssert(Added <= c.Used);
                }
            }
        }
        return *this;
    }

    int64 GetSize()
    {
        return IsOk() ? Size : 0;
    }
    
    bool SetSize(int64 s)
    {
        bool Status = false;

        if (!IsOk())
            return false;

        int OldSize = Size;
        int NewSize = max((int)s, Used * 10 / 7);
        if (NewSize != Size)
        {
            Entry *OldTable = Table;

            Used = 0;
            // LgiAssert(NewSize <= (512 << 10));
            SizeBackup = Size = NewSize;

            Table = new Entry[Size];
            if (Table)
            {
                KeyPoolArr OldPools;
                OldPools = Pools;
                Pools.Length(0);

                int i;
                InitializeTable(Table, Size);
                for (i=0; i<OldSize; i++)
                {
                    if (OldTable[i].k != NullKey)
                    {
                        if (!Add(OldTable[i].k, OldTable[i].v))
                        {
                            LgiAssert(0);
                        }
                        if (!Pool)
                            FreeKey(OldTable[i].k);
                    }
                }

                OldPools.DeleteObjects();
                Status = true;
            }
            else
            {
                LgiAssert(Table);
                Table = OldTable;
                SizeBackup = Size = OldSize;
                return false;
            }

            DeleteArray(OldTable);
        }

        return Status;
    }
    
    bool GetStringPool()
    {
        return IsOk() ? Pool : false;
    }
    
    void SetStringPool(bool b)
    {
        if (IsOk())
            Pool = b;
    }
    
    bool IsCase()
    {
        return IsOk() ? Case : false;
    }

    void IsCase(bool c)
    {
        if (IsOk())
            Case = c;
    }
    
    bool IsOk()
    {
        bool Status =   this != 0 &&
                        Table != 0;
        if (!Status)
        {
            LgiStackTrace("%s:%i - this=%p Table=%p Used=%i Size=%i\n", _FL, this, Table, Used, Size);
        }
        LgiAssert(Status);
        return Status;
    }

    int Length()
    {
        return IsOk() ? Used : 0;
    }

    bool Add
    (
        Key k,
        Value v
    )
    {
        if (IsOk() &&
            k != NullKey &&
            v != NullValue)
        {
            uint32 h = Hash(k);

            int Index = -1;
            for (int i=0; i<Size; i++)
            {
                int idx = (h + i) % Size;
                if
                (
                    Table[idx].k == NullKey
                    ||
                    CmpKey(Table[idx].k, k)
                )
                {
                    Index = idx;
                    break;
                }
            }

            if (Index >= 0)
            {
                if (Table[Index].k == NullKey)
                {
                    if (Pool)
                    {
                        KeyPool<Key> *p = 0;
                        if (Pools.Length() == 0)
                        {
                            Pools[0] = p = new KeyPool<Key>;
                        }
                        else
                        {
                            p = Pools[Pools.Length()-1];
                        }
                        
                        if (!(Table[Index].k = p->New(k)))
                        {
                            Pools.Add(p = new KeyPool<Key>);
                            Table[Index].k = p->New(k);
                        }
                    }
                    else
                    {
                        Table[Index].k = CopyKey(k);
                    }
                    Used++;
                }
                Table[Index].v = v;

                if (Percent() > HASH_TABLE_GROW_THRESHOLD)
                {
                    SetSize(Size << 1);
                }
                return true;
            }
        }

        return false;
    }
    
    bool Delete
    (
        Key k
    )
    {
        int Index = -1;
        if (GetEntry(k, Index))
        {
            // Delete the entry
            if (Pool)
            {
                // Memory is owned by the string pool, not us.
                Table[Index].k = NullKey;
            }
            else
            {
                FreeKey(Table[Index].k);
            }
            Table[Index].v = NullValue;
            Used--;
            
            // Bubble down any entries above the hole
            int Hole = Index;
            for (int i = (Index + 1) % Size; i != Index; i = (i + 1) % Size)
            {
                if (Table[i].k != NullKey)
                {
                    uint32 Hsh = Hash(Table[i].k);
                    uint32 HashIndex = Hsh % Size;
                    
                    if (HashIndex != i AND Between(Hole, HashIndex, i))
                    {
                        // Do bubble
                        if (Table[Hole].k != NullKey)
                        {
                            LgiAssert(0);
                        }
                        memmove(Table + Hole, Table + i, sizeof(Table[i]));
                        InitializeTable(Table + i, 1);
                        Hole = i;
                    }
                }
                else
                {
                    // Reached the end of entries that could have bubbled
                    break;
                }
            }

            // Check for auto-shrink limit
            if (Percent() < HASH_TABLE_SHRINK_THRESHOLD)
            {
                SetSize(Size >> 1);
            }
            
            return true;
        }
        else
        {
            GetEntry(k, Index, true);
        }

        return false;
    }

    Value Find(Key k)
    {
        int Index = -1;
        if (IsOk() && GetEntry(k, Index))
        {
            return Table[Index].v;
        }

        return NullValue;
    }
    
    Value First(Key *k = 0)
    {
        Cur = 0;
        if (IsOk())
        {
            while (Cur < Size)
            {
                if (Table[Cur].k != NullKey)
                {
                    if (k)
                    {
                        *k = Table[Cur].k;
                    }
                    return Table[Cur].v;
                }
                else Cur++;
            }
        }

        return NullValue;
    }
    
    Value Current(Key *k = 0)
    {
        if (Cur >= 0 &&
            Cur < Size &&
            Table &&
            Table[Cur].k != NullKey)
        {
            if (k)
            {
                *k = Table[Cur].k;
            }
            return Table[Cur].v;
        }

        return NullValue;
    }
    
    Value Next(Key *k = 0)
    {
        if (IsOk() && Cur >= 0)
        {
            while (++Cur < Size)
            {
                if (Table[Cur].k != NullKey)
                {
                    if (k)
                    {
                        *k = Table[Cur].k;
                    }
                    return Table[Cur].v;
                }
            }
        }

        return NullValue;
    }

    void Empty()
    {
        if (!IsOk())
            return;

        if (Pool)
        {
            Pools.DeleteObjects();

            for (int i=0; i<Size; i++)
            {
                Table[i].k = NullKey;
                Table[i].v = NullValue;
            }
        }
        else
        {
            for (int i=0; i<Size; i++)
            {
                if (Table[i].k != NullKey)
                {
                    FreeKey(Table[i].k);
                    LgiAssert(Table[i].k == NullKey);
                }
                Table[i].v = NullValue;
            }
        }

        Used = 0;
        SetSize(512);
    }

    int64 Sizeof()
    {
        int64 Sz = sizeof(*this);
        char s[64];

        Sz += Sz * sizeof(Entry);

        // LgiFormatSize(s, Size);
        // LgiTrace("%s in %i hash entries (%i used)\n", s, Size, Used);

        int Keys = 0;
        int64 KeySize = 0;
        if (Pool)
        {
            for (int i=0; i<Pools.Length(); i++)
            {
                KeyPool<Key> *p = Pools[i];
                KeySize += sizeof(*p) + p->Size;
            }
        }
        else
        {
            for (int i=0; i<Size; i++)
            {
                if (Table[i].k != NullKey)
                {
                    Keys++;
                    KeySize += SizeKey(Table[i].k);
                }
            }
        }

        // LgiFormatSize(s, KeySize);
        // LgiTrace("%s in %i keys\n", s, Keys);

        return Sz + KeySize;
    }

    void DeleteObjects()
    {
        for (int i=0; i<Size; i++)
        {
            if (Table[i].k != NullKey)
                FreeKey(Table[i].k);

            if (Table[i].v != NullValue)
                DeleteObj(Table[i].v);
        }

        Used = 0;
    }

    void DeleteArrays()
    {
        for (int i=0; i<Size; i++)
        {
            if (Table[i].k != NullKey)
                FreeKey(Table[i].k);

            if (Table[i].v != NullValue)
                DeleteArray(Table[i].v);
        }

        Used = 0;
    }
};

class LgiClass GHashTable : public GHashTbl<char*, void*>
{
public:
    GHashTable(int Size = 0, bool Case = true)
        : GHashTbl<char*, void*>(Size, Case)
    {
    }
    
    bool Add(char *k, void *v = (void*)1)
    {
        return GHashTbl<char*, void*>::Add(k, v);
    }
    
};

#endif

---