Working dictionary / associative array

[Parker]

Yay, I've made two accomplishments:
1) 5 topics in a row startedÂÃ, 
2) Working associative array implementation in a class.

It's implemented in two separate source files in a much bigger project, but here is the dictionary class file and the linked lists file it depends on:

dictionary.src

Code Select Expand

// Dictionary

struct listnode {
pointer pData;
listnode *pNext;
listnode *pPrev;
}

declare extern ListCreate(),pointer;
declare extern ListAdd(listnode *list, pointer item),pointer;
declare extern ListAddHead(listnode *list, pointer item),pointer;
declare extern ListGetFirst(listnode *list),pointer;
declare extern ListGetLast(listnode *list),pointer;
declare extern ListGetNext(listnode *list),pointer;
declare extern ListGetPrev(listnode *list),pointer;
declare extern ListGetData(listnode *list),pointer;
declare extern ListRemove(listnode *list, opt int bDelete = 0),pointer;
declare extern ListRemoveAll(listnode *list, opt int bDelete = 0);

class Dictionary
{
unsigned int m_uHashSize;
listnode *m_pLists;

declare Create(unsigned int size);
declare Hash(string str),unsigned int;
declare Add(string key, pointer value);
declare Get(string key),pointer;
}

struct DictNode
{
pointer key;
pointer value;
}

Dictionary::Create(unsigned int size)
{
unsigned int i;
pointer pNode;

m_uHashSize = size;
m_pLists = new(listnode, size);

return;
}

Dictionary::Destroy(opt unsigned int delCallback=0)
{
unsigned int hProc;
pointer i, j;
pointer pData, pValue;
hProc = delCallback;

for (i = m_pLists; i <= (m_pLists+((m_uHashSize-1) * len(listnode))); i += len(listnode))
{
for (j = ListGetFirst(i); j <> 0; j = ListGetNext(j))
{
pData = ListGetData(j);
if (hProc)
{
pValue = *(DictNode)pData.value;
#asm
lea edx, [ebp-4]
mov eax, [ebp-20]
lea eax, [eax-16]
push dword eax
call [edx]
#endasm
}
delete *(DictNode)pData.key;
}
ListRemoveAll(i, 1);
}

return;
}

Dictionary::Hash(string str)
{
unsigned int i, hash;
hash = 0;

for (i = 0; i < len(str); i++)
{
hash = hash << 5 | str[i];
}
hash = hash % m_uHashSize;

return hash;
}

Dictionary::Add(string key, pointer value)
{
if ((m_pLists = 0) or (m_uHashSize = 0)) return;

unsigned int uHash;
DictNode *node;
uHash = Hash(key);
node = new(DictNode,1);
*node.key = new(byte, len(key)+1);
*node.*key = key;
*node.value = value;

ListAdd(m_pLists+(uHash*len(listnode)), node);

return;
}

Dictionary::Get(string key)
{
pointer pList, pNode;
DictNode *pData;
string *pKey;
pList = m_pLists + (Hash(key) * len(listnode));
if (pList = 0) return 0;
pNode = ListGetFirst(pList);
if (pNode = 0) return 0;
while (pNode <> 0)
{
pData = ListGetData(pNode);
pKey = *pData.key;
if (*pKey = key) break;
pNode = ListGetNext(pNode);
}

if (*pKey = key) return *(DictNode)pData.value else return 0;
}

linkedlist.src

Code Select Expand

struct listnode {
pointer pData;
listnode *pNext;
listnode *pPrev;
}

// Linked List implementation, like the one in IB

// CREATE
global sub ListCreate(),pointer
{
listnode *pTemp;
pTemp = new(listnode,1);
// new automatically zeroes memory.

return pTemp;
}

// ADD, ADDHEAD

global sub ListAdd(listnode *list, pointer item),pointer
{
listnode *pTemp;

if (list = 0) return item;

pTemp = ListGetLast(list);

*pTemp.pNext = new(listnode,1);
*pTemp.*pNext.pPrev = pTemp;
*pTemp.*pNext.pData = item;

return item;
}

global sub ListAddHead(listnode *list, pointer item),pointer
{
listnode *pTemp;

if (list = 0) return item;

pTemp = *list.pNext;
*list.pNext = new(listnode,1);

*list.*pNext.pPrev = list;
*list.*pNext.pData = item;
*list.*pNext.pNext = pTemp;

if (pTemp <> 0)
{
*pTemp.pPrev = *list.pNext;
}

return item;
}

// GETFIRST, GETLAST

global sub ListGetFirst(listnode *list),pointer
{
if (list = 0) return 0;

return *list.pNext;
}

global sub ListGetLast(listnode *list),pointer
{
listnode *pTemp;

if (list = 0) return 0;

pTemp = list;
while (*pTemp.pNext <> 0)
{
pTemp = *pTemp.pNext;
}

return pTemp;
}

// GETNEXT, GETPREV

global sub ListGetNext(listnode *list),pointer
{
if (list = 0) return 0;

return *list.pNext;
}

global sub ListGetPrev(listnode *list),pointer
{
// can't do anything to a null list
if (list = 0) return 0;
// this is needed for below
if (*list.pPrev = 0) return 0;
// since the list starts with a null node (pPrev and pData = 0),
// the first should be the one right after the real first.
if (*list.*pPrev.pPrev = 0) return 0;

return *list.pPrev;
}

// GETDATA

global sub ListGetData(listnode *list),pointer
{
if (list = 0) return 0;

return *list.pData;
}

// REMOVE, REMOVEALL

global sub ListRemove(listnode *list, opt int bDelete = 0),pointer
{
listnode *pPrev;
listnode *pNext;

if (list = 0) return 0;

pPrev = *list.pPrev;
pNext = *list.pNext;

if ((*list.pData <> 0) and (bDelete <> 0)) delete *list.pData;

delete list;

if (pPrev <> 0)
{
*pPrev.pNext = pNext;
}
if (pNext <> 0)
{
*pNext.pPrev = pPrev;
}

return pNext;
}

global sub ListRemoveAll(listnode *list, opt int bDelete = 0)
{
listnode *node;

if (list = 0) return 0;

for (node = ListGetFirst(list); node <> 0; node = ListRemove(node))
{
if (bDelete) delete *node.pData;
}

return;
}

example (in header.inc, just paste the Dictionary class and DictNode definitions):

Code Select Expand

#include "header.inc"

global sub main()
{
Dictionary d;
int *i;

d.Create(20);

i = new(int,1);
*i = 1;
d.Add("First", i);
i = new(int, 1);
*i = 2;
d.Add("Second", i);
i = d.Get("Second");
writeln("Found: "+str$(*i,0)+"\n");
d.Destroy(&DictDestroy);

while (GetKey() = "");
return 0;
}

sub DictDestroy(pointer pData)
{
writeln("Destroying: "+str$(*(int)pData,0)+"\n");
delete pData;
return;
}

You can store whatever you want in it, but you have to store it as a pointer using Add. If you don't want it to be case sensitive, just use lcase$() or ucase$() to convert the strings before using Get and Add.

Edit: I've added the Destroy() function. It takes one optional parameter, the address of a function to call when an item needs to be deleted. It's demonstrated in the example. Also, Get() now works correctly.

[Zen]

Woo Hoo. Dictionary functions to store any type of data. IBasic could only store strings so this is great news for me.

Thanks a lot.
Lewis

[Parker]

Sorry for bringing back up an old topic, but I wanted to know a couple of things:
- Is the asm bit I used to call the function okay? What I mean is, this bit seemed a little odd: "lea eax, [eax-16]" because apparently the item I want to pass isn't stored as I thought it was. Maybe I just miscalculated, but it seemed a little odd to me.

- Is there a syntax for calling functions indirectly like this? It'd be nice if there was something better than IBasic's !<Template>Function(value) maybe something like FB:
dim x as function(value as integer) as integer
x = @somefunction
y = x(3)