/* Includes */
// POSIX Standard C Library
#include <stdio.h>

/* Declarations */
// Named Array class
template<class T> class NamedArray;

/* Classes */
// Named Array class
template<class T> class NamedArray
{
    struct Item
    {
        unsigned int    key;
        T               value;
        Item            *pParent, **ppPlace;
        Item            *pLeft,
                        *pRight;
    };
    protected:
        // Values
        Item            *m_pRoot;
        T               m_invalid;
        unsigned int    m_count;
        // Get a hash from a key
        inline unsigned int _getHash(const char *pszKey)
        {
            unsigned int hash = 0xF00DFACE;
            unsigned int length = 0;
            unsigned int index = 0;
            unsigned int mask = 0xF7;
            while(pszKey[index++])
            {
                hash = ((hash^(mask&0x7F)) | (index^(mask&0x80))) - index;
                mask = mask | (((unsigned int)pszKey[index-1]) ^ 0xFF);
            }
            length = 1<<(index%32);
            length = length | ((mask&0x3F)<<24)|((mask&0x7F)<<16)|((mask&0xFF)<<8)|(mask^0x32);
            hash = (hash*(index>>1)) ^ length;
            printf("[hash:0x%.8X from \"%s\"]\n", hash, pszKey);
            return hash;
        }
        // Add an item
        inline Item *_addItem(const char *pszKey)
        {
            Item *pItem, *pSearch, **ppPlace;
            if (!(pItem = new Item()))
                return (Item*)0;
            pItem->key = _getHash(pszKey);
            pItem->pLeft = pItem->pRight = pItem->pParent = (Item*)0;
            if (!m_pRoot)
            {
                m_pRoot = pItem;
                pItem->ppPlace = &m_pRoot;
            }
            else
            {
                pSearch = m_pRoot;
                while(pSearch)
                {
                    pItem->pParent = pSearch; // Slow, but easy to implement
                    if (pSearch->key < pItem->key)
                        ppPlace = &(pSearch->pLeft);
                    else
                        ppPlace = &(pSearch->pRight);
                    pSearch = *ppPlace;
                }
                (*ppPlace) = pItem;
                pItem->ppPlace = ppPlace;
            }
            m_count++;
            return pItem;
        }
        inline void _remove(Item *pItem)
        {
            if (pItem->pLeft)  _remove(pItem->pLeft);
            if (pItem->pRight) _remove(pItem->pRight);
            *(pItem->ppPlace) = (Item*)0;
            delete pItem;
        }
    public:
        inline NamedArray() : m_pRoot((Item*)0), m_count(0) {}
        inline ~NamedArray() { clear(); }
        inline void setInvalid(T &v) { m_invalid = v; }
        inline unsigned int count(void) { return m_count; }
        inline void clear(void)
        {
            while(m_pRoot)
                _remove(m_pRoot);
        }
        inline T &operator[](const char *pszKey)
        {
            unsigned int hash = _getHash(pszKey);
            Item *pNode = m_pRoot;
            while(pNode)
            {
                if (pNode->key != hash)
                {
                    if (pNode->key < hash)
                        pNode = pNode->pLeft;
                    else
                        pNode = pNode->pRight;
                }
                else
                    return pNode->value;
            }
            pNode = _addItem(pszKey);
            if (pNode)
                return pNode->value;
            return m_invalid;
        }
};

/* Functions */
// Entry point
int main()
{
    NamedArray<int> arr;
    arr["Joe"] = 14;
    arr["Jack"] = 72;
    arr["Test 3"] = 17;
    printf("Joe says %d\n", arr["Joe"]);
    printf("Jack says %d\n", arr["Jack"]);
    printf("Test 3 says %d\n", arr["Test 3"]);
    return 0;
}

[hash:0xDF640AAD from "Joe"]
[hash:0xDF640AAD from "Joe"]
[hash:0xDF640A7B from "Jack"]
[hash:0xDF640A7B from "Jack"]
[hash:0xEF560F8E from "Test 3"]
[hash:0xEF560F8E from "Test 3"]
[hash:0xDF640AAD from "Joe"]
Joe says 14
[hash:0xDF640A7B from "Jack"]
Jack says 72
[hash:0xEF560F8E from "Test 3"]
Test 3 says 17