/* 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;
}