CIntAssoc

[Ionic Wind Support Team]

Here's an integer associative array class I use in a few projects.  It is a way to map one integer to another using a hash table. Adapted from the Aurora class that maps integers to strings.  Feel free to adapt and use in your Emergence projects.

usage:

Code Select Expand


CIntAssoc test
test.Create()
test.Add(999,54545)
test.Add(123,14150)
print test.Lookup(999)


The source file:

Code Select Expand


autodefine "off"
$include "CIntAssoc.inc"

SUB CIntAssoc::CIntAssoc()
m_pHashTable = NULL
m_nHashTableSize = 17
m_nCount = 0
m_pFreeList = NULL
m_pBlocks = NULL
m_nBlockSize = 10
m_ListPlex = NULL
Endsub

SUB CIntAssoc::_CIntAssoc()
RemoveAll()
Endsub

SUB CIntAssoc::GetCount(),int
return m_nCount
Endsub

SUB CIntAssoc::Add(int key,int value)
UINT nHash:nHash = 0
POINTER pAssoc
pAssoc = GetAssocAt(key, nHash)
if (pAssoc = NULL)
IF (m_pHashTable = NULL)
InitHashTable(m_nHashTableSize)
ENDIF

'// it doesn't exist, add a new Association
pAssoc = NewAssoc()
#<IAssoc>pAssoc.nHashValue = nHash
#<IAssoc>pAssoc.key = key
'#<IAssoc>pAssoc.#<STRING>key = key

'// put into hash table
#<IAssoc>pAssoc.pNext = #<POINTER>m_pHashTable[nHash]
#<POINTER>m_pHashTable[nHash] = pAssoc
endif
#<IAssoc>pAssoc.value = value
'return pAssoc->value;  // return new reference
RETURN 0
Endsub

SUB CIntAssoc::Create(OPT hashtablesize=17 as int,OPT blocksize=10 as int),int
if(blocksize > 0)
m_pHashTable = NULL
m_nHashTableSize = hashtablesize
m_nCount = 0
m_pFreeList = NULL
m_pBlocks = NULL
m_nBlockSize = BlockSize
m_ListPlex = ListCreate
return 1
endif
return 0
Endsub

SUB CIntAssoc::Free()
RemoveAll()
Endsub

SUB CIntAssoc::GetStartAssoc(),uint
IF m_nCount > 0 THEN RETURN -1
RETURN 0
Endsub

SUB CIntAssoc::GetNextAssoc(rNextPosition as uint BYREF),pointer
UINT nBucket
POINTER pAssocRet:pAssocRet = rNextPosition + 0

if (pAssocRet = -1)
'// find the first association
for nBucket = 0 TO m_nHashTableSize-1
pAssocRet = #<POINTER>m_pHashTable[nBucket]
if (pAssocRet <> NULL)
breakfor
endif
next nBucket
ENDIF

'// find next association
POINTER pAssocNext
pAssocNext = #<IAssoc>pAssocRet.pNext
if pAssocNext =  NULL
'// go to next bucket
for nBucket = #<IAssoc>pAssocRet.nHashValue + 1 TO m_nHashTableSize-1
pAssocNext = #<POINTER>m_pHashTable[nBucket]
if pAssocNext <> NULL
breakfor
endif
next nBucket
endif

rNextPosition = pAssocNext+0

'// fill in return data
'rKey = pAssocRet->key;
'rValue = pAssocRet->value;
RETURN pAssocRet
Endsub

SUB CIntAssoc::GetKey(pAssoc as pointer),int
IF(pAssoc <> NULL)
RETURN #<IAssoc>pAssoc.key
ENDIF
Return 0
Endsub

SUB CIntAssoc::GetValue(pAssoc as pointer),int
IF(pAssoc <> NULL)
RETURN #<IAssoc>pAssoc.value
ENDIF
Return 0
Endsub

SUB CIntAssoc::Lookup(int key),int
UINT nHash:nHash = 0
POINTER pAssoc:pAssoc = GetAssocAt(key, nHash)
if (pAssoc = NULL)
return 0
endif

RETURN #<IAssoc>pAssoc.value
Endsub

SUB CIntAssoc::Remove(key as int),int
if (m_pHashTable = NULL) THEN return FALSE

POINTER ppAssocPrev
ppAssocPrev = &#<POINTER>m_pHashTable[HashKey(key) % m_nHashTableSize]

POINTER pAssoc
pAssoc = #<POINTER>ppAssocPrev
WHILE pAssoc <> NULL
if  #<IAssoc>pAssoc.key = key
#<POINTER>ppAssocPrev = #<IAssoc>pAssoc.pNext
FreeAssoc(pAssoc)
return TRUE
endif
ppAssocPrev = &#<IAssoc>pAssoc.pNext
pAssoc = #<IAssoc>pAssoc.pNext
ENDWHILE
return FALSE
Endsub

SUB CIntAssoc::RemoveAll()
UINT nHash
POINTER pAssoc
if (m_pHashTable <> NULL)
for nHash = 0 to m_nHashTableSize - 1
'DebugPrint("Hash = " + str$(nHash))
pAssoc = #<POINTER>m_pHashTable[nHash]
WHILE pAssoc <> NULL
IF #<IAssoc>pAssoc.key <> 0
'DebugPrint("  Key:" + #<IAssoc>pAssoc.#<STRING>key)
'DELETE #<IAssoc>pAssoc.key
'DELETE #<IAssoc>pAssoc.value
ENDIF
pAssoc = #<IAssoc>pAssoc.pNext
ENDWHILE
next nHash
delete m_pHashTable
m_pHashTable = NULL
endif

m_nCount = 0
m_pFreeList = NULL
ListRemoveAll(m_ListPlex,TRUE)
m_ListPlex = NULL
Endsub

SUB CIntAssoc::InitHashTable(uint nHashSize, OPT bAllocNow=TRUE as int)
'//
'// Used to force allocation of a hash table or to override the default
'//   hash table size of (which is fairly small)
if (m_pHashTable <> NULL)
'// free hash table
delete m_pHashTable
m_pHashTable = NULL
endif

if (bAllocNow)
m_pHashTable = new(UINT, nHashSize)
ENDIF
m_nHashTableSize = nHashSize
RETURN
Endsub

SUB CIntAssoc::NewAssoc(), pointer
POINTER pAssoc:pAssoc = NULL
POINTER newBlock:newBlock = NULL
INT i
if(1)
if (m_pFreeList = NULL)
'// add another block
pAssoc = ListAdd(m_ListPlex,new(CHAR,m_nBlockSize * LEN(IAssoc)))
'// chain them into free list
'// free in reverse order to make it easier to debug
pAssoc += (m_nBlockSize - 1) * LEN(IAssoc)
for  i = m_nBlockSize-1 TO 0 STEP -1
#<IAssoc>pAssoc.pNext = m_pFreeList
m_pFreeList = pAssoc
pAssoc -= LEN(IAssoc)
next i
endif
pAssoc = m_pFreeList
m_pFreeList = #<IAssoc>m_pFreeList.pNext
m_nCount++

#<IAssoc>pAssoc.key = 0
#<IAssoc>pAssoc.value = 0
#<IAssoc>pAssoc.nHashValue = 0
endif
return pAssoc
Endsub

SUB CIntAssoc::GetAssocAt(key as int, nHash as uint BYREF),pointer
nHash = key % m_nHashTableSize
'DebugPrint("GetAssocAt nHash = "+str$(nHash))
if (m_pHashTable = NULL) then return NULL

'// see if it exists
POINTER pAssoc
pAssoc = #<POINTER>m_pHashTable[nHash]
WHILE pAssoc <> NULL
IF (#<IAssoc>pAssoc.key <> 0) AND (#<IAssoc>pAssoc.key = key) THEN return pAssoc
pAssoc = #<IAssoc>pAssoc.pNext
ENDWHILE

return NULL

Endsub

SUB CIntAssoc::HashKey(key as int),uint
UINT nHash:nHash = key
return nHash
Endsub

SUB CIntAssoc::FreeAssoc(pointer pAssoc)

#<IAssoc>pAssoc.pNext = m_pFreeList
m_pFreeList = pAssoc
m_nCount--

'// if no more elements, cleanup completely
if (m_nCount = 0)
Free()
endif
Endsub


The include file:

Code Select Expand


TYPE IAssoc
POINTER pNext
UINT nHashValue
INT key
INT value
ENDTYPE

Class CIntAssoc
Declare CIntAssoc()
Declare _CIntAssoc()
Declare Add(int key,int value)
Declare Create(OPT hashtablesize=17 as int,OPT blocksize=10 as int),int
Declare Free()
Declare GetStartAssoc(),uint
Declare GetNextAssoc(rNextPosition as uint BYREF),pointer
Declare GetKey(pAssoc as pointer),int
Declare GetValue(pAssoc as pointer),int
Declare Lookup(int key),int
Declare Remove(key as int),int
Declare RemoveAll()
Declare InitHashTable(uint nHashSize, OPT bAllocNow=TRUE as int)
Declare NewAssoc(), pointer
Declare GetAssocAt(key as int, nHash as uint BYREF),pointer
Declare HashKey(key as int),uint
Declare FreeAssoc(pointer pAssoc)
Declare GetCount(),int
Protected
POINTER m_pHashTable
UINT m_nHashTableSize
int m_nCount
POINTER m_pFreeList
POINTER m_pBlocks
int m_nBlockSize
POINTER m_ListPlex
Endclass


Notes:

The hash is generated by the remainder of the integer key with the hash table size.  For large key ranges increase the hash table size for more speed if needed.

The class can also be used to map an integer to a pointer, which is useful for associating data with control or menu id's

pointer pData
pData = store.Lookup(menuid)

Add the source file to your project, and include the include file in any source file you are using the class in. 

Paul,