DICTREMOVE anomolies

[myql]

I have a moderately large program (a few thousand lines) that among other things does occasional DICTREMOVE. In a case where the value associated with a key is an empty string, I get an Access Violation while executing the DICTREMOVE. Any clues why an Access violation might occur? It's not that the dict pointer is null; closely prior to the DICTREMOVE, there is a successful DICTLOOKUP with the same arguments.

I tried to reproduce the problem with a simple test program, and uncovered a different failure--the remove did not work.
It wasn't apparent until the dict had two entries with empty values, and I attempted to remove both of the them.

Attached is the code that shows the latter problem.

Michael

[Ficko]

Hi Michael!

Change "empty", "empty1" to "empty01","empty02"

Regards,
Ficko

[myql]

Hi Ficko,

So it's sensitive to what the keys are, as well. That's perhaps even more disturbing. Of course, in the application I don't really have control of what the keys might be, or especially their values.

If I can't get a safe program using DICTREMOVE, I may be able to avoid using it (but tolerate some minor memory leaks). That's probably my best choice at the moment.

Michael

[Ionic Wind Support Team]

More likely a bug in the hash calculation routine.  Have to investigate it.

[Ionic Wind Support Team]

Yep it's a confirmed bug.  Update this weekend.

Paul.

[myql]

Thanks, Paul.
Think that could also be the cause of the Access Violation, or could it be a separate bug?

Michael

[myql]

Hi Paul,

While you're at it, it would be useful to have a DICTHASKEY function. DICTLOOKUP cannot distinguish between a value of "" and a missing key. Sometimes that can be important.

Michael

[Ionic Wind Support Team]

Michael,
The dictionary commands were not designed to handle an empty string as a value, since an empty string represents a non existent mapping.  You can use an empty string as a key though. You can also designate a value as "empty" which is what I normally do, such as "__EMPTY__" or even just a space " "

The commands were designed after the C++ template hash classes and if you want to design your own for a specific purpose here is the source for a derivation that maps integers to integers:

'include

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


'source

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


[myql]

Paul,

When you say the dictionary commands were not designed to handle an empty string as a value, does that mean there is a danger in having an empty string value? Is that the root of the problems I've been seeing?

If an empty string is permitted as a value, the attached code can differentiate that from an absent key. It would be better to determine that without disrupting the dictionary, which is why I suggested that you implement DICTHASKEY.

Michael

[Ionic Wind Support Team]

There is no danger in an empty string.  There is just no difference between no match and an empty string.  As I said it is by design and there is nothing wrong with the commands.  I provided you with an alternative for your use.

There will be no further additions to the language concerning the dictionary commands.

[myql]

Hi Paul,

OK, I understand not wanting to add to the language. Do you see anything wrong with my implementation of DictHasKey?

Michael