codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
/* 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; }
Private
[
?
]
Run code
Submit