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
// 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
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):
#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.
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
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)