feedback is welcome of course
DoublyHashTable.pbi
Code: Select all
Enumeration
;creates the hash table
#DHT_CREATE_TABLE
;adds an element to the hash table
#DHT_ADD_ELEMENT
;deletes the element with the given key
#DHT_DEL_ELEMENT
;returns the element of the given key
#DHT_GET_ELEMENT
;returns the number of elements in the hash table
#DHT_COUNT_ELEMENTS
;deletes all elements in the hash table
#DHT_CLEAR_TABLE
;deletes all elements in the hash table and the hash table itself, returns 0 if successful
#DHT_DELETE
EndEnumeration
#DHT_KD_STRING = ""
#DHT_KD_NUMBER = 0
;keyDefault means the default value for the key
;Values for keyDefault:
; #DHT_KD_STRING if key is of type String
; #DHT_KD_NUMBER if key is a numerical type like Long
;Examples for keyCompare:
; key = *item\item\key
; sameKey(key, *item\item\key) ;(sameKey() must be declared prior of course)
;Remark: first compare param is always "key" and second one starts always with "*item\"
Macro CreateDoublyHashTableClass(dataVariable, dataType, keyType, keyDefault, keyCompare, itemCountLevel1, itemCountLevel2, Index1ProcAddr, Index2ProcAddr)
CompilerIf Defined(DOUBLY_HASH_TABLE_ENTRY_#dataType, #PB_Structure) = #False
Prototype.l DoublyHashTable_Index1_#dataType#(key.keyType, TableSize.l)
Prototype.l DoublyHashTable_Index2_#dataType#(key.keyType, TableSize.l)
#DOUBLY_HASH_TABLE_LVL1_#dataType = itemCountLevel1
#DOUBLY_HASH_TABLE_LVL2_#dataType = itemCountLevel2
#DOUBLY_HASH_TABLE_KD_#dataType = keyDefault
Structure DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType
*next.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType
dataVariable#.dataType#
EndStructure
Structure DOUBLY_HASH_TABLE_ENTRY_L2_#dataType
*item.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType[itemCountLevel2]
EndStructure
Structure DOUBLY_HASH_TABLE_ENTRY_L1_#dataType
*item.DOUBLY_HASH_TABLE_ENTRY_L2_#dataType[itemCountLevel1]
size.l
EndStructure
Procedure.l DoublyHashTable_#dataType#(option.l, *handle.DOUBLY_HASH_TABLE_ENTRY_L1_#dataType = 0, key.keyType = keyDefault, *dat.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType = 0)
Select option
Case #DHT_CREATE_TABLE
If *handle = 0
*handle = AllocateMemory(SizeOf(DOUBLY_HASH_TABLE_ENTRY_L1_#dataType))
If *handle
*handle\size = 0
EndIf
EndIf
Case #DHT_ADD_ELEMENT
If *handle And *dat And key <> keyDefault
i1proc.DoublyHashTable_Index1_#dataType# = Index1ProcAddr
i2proc.DoublyHashTable_Index2_#dataType# = Index2ProcAddr
Index1.l = i1proc(key, itemCountLevel1)
Index2.l = i2proc(key, itemCountLevel2)
If *handle\item[Index1] = 0
*handle\item[Index1] = AllocateMemory(SizeOf(DOUBLY_HASH_TABLE_ENTRY_L2_#dataType))
If *handle\item[Index1] = 0
ProcedureReturn 0
EndIf
EndIf
If *handle\item[Index1]
*item.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType = *handle\item[Index1]\item[Index2]
keyAlreadyInUse.l = #False
While *item
If keyCompare
keyAlreadInUse = #True
Break 1
EndIf
*item = *item\next
Wend
If keyAlreadyInUse
ProcedureReturn *item
Else
If *handle\item[Index1]\item[Index2] = 0
*item = AllocateMemory(SizeOf(DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType))
Else
*item = *handle\item[Index1]\item[Index2]
While *item
*item = *item\next
Wend
*item\next = AllocateMemory(SizeOf(DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType))
EndIf
CopyMemory(*dat, @*item\dataVariable, SizeOf(DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType))
If *handle\item[Index1]\item[Index2] = 0
*handle\item[Index1]\item[Index2] = *item
EndIf
*handle\size + 1
ProcedureReturn *item
EndIf
EndIf
EndIf
ProcedureReturn 0
Case #DHT_DEL_ELEMENT
If *handle And key <> keyDefault
i1proc.DoublyHashTable_Index1_#dataType# = Index1ProcAddr
i2proc.DoublyHashTable_Index2_#dataType# = Index2ProcAddr
Index1.l = i1proc(key, itemCountLevel1)
Index2.l = i2proc(key, itemCountLevel2)
If *handle\item[Index1]
If *handle\item[Index1]\item[Index2]
*item.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType = *handle\item[Index1]\item[Index2]
Index.l = 0
While *item
If keyCompare
If Index = 0
pointer.l = *handle\item[Index1]\item[Index2]\next
FreeMemory(*handle\item[Index1]\item[Index2])
*handle\item[Index1]\item[Index2] = pointer
Else
*element.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType = *handle\item[Index1]\item[Index2]
a.l = 0
While *element\next And a < Index - 1
*element = *element\next
a + 1
Wend
pointer.l = *element\next\next
FreeMemory(*element\next)
*element\next = pointer
EndIf
*handle\size - 1
ProcedureReturn *handle
EndIf
Index + 1
*item = *item\next
Wend
EndIf
EndIf
EndIf
ProcedureReturn 0
Case #DHT_GET_ELEMENT
If *handle And key <> keyDefault
i1proc.DoublyHashTable_Index1_#dataType# = Index1ProcAddr
i2proc.DoublyHashTable_Index2_#dataType# = Index2ProcAddr
Index1.l = i1proc(key, itemCountLevel1)
Index2.l = i2proc(key, itemCountLevel2)
If *handle\item[Index1]
If *handle\item[Index1]\item[Index2]
*item.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType = *handle\item[Index1]\item[Index2]
While *item
If keyCompare
ProcedureReturn *item
EndIf
*item = *item\next
Wend
EndIf
EndIf
EndIf
ProcedureReturn 0
Case #DHT_COUNT_ELEMENTS
If *handle
ProcedureReturn *handle\size
EndIf
ProcedureReturn 0
Case #DHT_CLEAR_TABLE
If *handle
For i = 0 To itemCountLevel1 - 1
If *handle\item[i]
For k = 0 To itemCountLevel2 - 1
If *handle\item[i]\item[k]
If *handle\item[i]\item[k]
*element.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType = *handle\item[i]\item[k]\next
FreeMemory(*handle\item[i]\item[k])
While *element
*handle\item[i]\item[k] = *element
*element = *element\next
FreeMemory(*handle\item[i]\item[k])
Wend
EndIf
EndIf
Next
FreeMemory(*handle\item[i])
*handle\item[i] = 0
EndIf
Next
*handle\size = 0
ProcedureReturn *handle
EndIf
ProcedureReturn 0
Case #DHT_DELETE
If *handle
For i = 0 To itemCountLevel1 - 1
If *handle\item[i]
For k = 0 To itemCountLevel2 - 1
If *handle\item[i]\item[k]
If *handle\item[i]\item[k]
*element.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType = *handle\item[i]\item[k]\next
FreeMemory(*handle\item[i]\item[k])
While *element
*handle\item[i]\item[k] = *element
*element = *element\next
FreeMemory(*handle\item[i]\item[k])
Wend
EndIf
EndIf
Next
FreeMemory(*handle\item[i])
EndIf
Next
FreeMemory(*handle)
EndIf
ProcedureReturn 0
EndSelect
ProcedureReturn *handle
EndProcedure
CompilerEndIf
EndMacro
Macro DefineDoublyHashTable(variable, dataType)
variable#.DOUBLY_HASH_TABLE_ENTRY_L1_#dataType
EndMacro
Macro DefineDoublyHashTableItem(variable, dataType)
variable#.DOUBLY_HASH_TABLE_ITEM_STRUC_#dataType
EndMacro
Macro DoublyHashTable(dataType, option, handle, key = 0, dat = 0)
CompilerSelect option
CompilerCase #DHT_CREATE_TABLE
__DHT_rv__.l = DoublyHashTable_#dataType#(option, handle)
handle = __DHT_rv__
CompilerCase #DHT_ADD_ELEMENT
__DHT_rv__.l = DoublyHashTable_#dataType#(option, handle, key, dat)
CompilerCase #DHT_DEL_ELEMENT
__DHT_rv__.l = DoublyHashTable_#dataType#(option, handle, key)
CompilerCase #DHT_GET_ELEMENT
__DHT_rv__.l = DoublyHashTable_#dataType#(option, handle, key)
CompilerCase #DHT_COUNT_ELEMENTS
__DHT_rv__.l = DoublyHashTable_#dataType#(option, handle)
CompilerCase #DHT_CLEAR_TABLE
__DHT_rv__.l = DoublyHashTable_#dataType#(option, handle)
CompilerCase #DHT_DELETE
__DHT_rv__.l = DoublyHashTable_#dataType#(option, handle)
handle = __DHT_rv__
CompilerEndSelect
EndMacro
Macro DHT_ReturnValue
__DHT_rv__
EndMacro
Macro DHTForEach(dataType, handle, element)
DefineDoublyHashTableItem(element, dataType) = 0
If handle
For _i__ = 0 To #DOUBLY_HASH_TABLE_LVL1_#dataType - 1
If handle\item[_i__]
For _k__ = 0 To #DOUBLY_HASH_TABLE_LVL2_#dataType - 1
If handle\item[_i__]\item[_k__]
element = handle\item[_i__]\item[_k__]
While element
EndMacro
Macro DHTNext(dataType, handle, element)
element = element\next
Wend
EndIf
Next
EndIf
Next
EndIf
EndMacro
Macro DHTBreak()
Break 3
EndMacro
; ###############
;# Example #
; ###############
Debug "=============================="
Debug "Example"
Structure DNS_IP
dns.s{128}
ip.l
EndStructure
Procedure.l HashIndexLvl1(key$, limit.l)
key$ = LCase(key$)
ProcedureReturn (CRC32Fingerprint(@key$, StringByteLength(key$), $00000000) & $7FFFFFFF) % limit
EndProcedure
Procedure.l HashIndexLvl2(key$, limit.l)
key$ = LCase(key$)
ProcedureReturn (CRC32Fingerprint(@key$, StringByteLength(key$), $FFFFFFFF) & $7FFFFFFF) % limit
EndProcedure
CreateDoublyHashTableClass(item, DNS_IP, s, #DHT_KD_STRING, LCase(key) = LCase(*item\item\dns), 10, 5, @HashIndexLvl1(), @HashIndexLvl2())
DefineDoublyHashTable(*dns_mapping, DNS_IP)
DefineDoublyHashTableItem(dns_item, DNS_IP)
DefineDoublyHashTableItem(*dns_item, DNS_IP)
DoublyHashTable(DNS_IP, #DHT_CREATE_TABLE, *dns_mapping)
Debug "Created the hash table."
Debug ""
dns_item\item\dns = "www.google.com"
dns_item\item\ip = MakeIPAddress(74, 125, 39, 103)
DoublyHashTable(DNS_IP, #DHT_ADD_ELEMENT, *dns_mapping, dns_item\item\dns, @dns_item\item)
If DHT_ReturnValue
Debug "Add item to hash table."
Else
Debug "Couldn't add item to hash table."
EndIf
dns_item\item\dns = "www.google.de"
dns_item\item\ip = MakeIPAddress(66, 249, 93, 99)
DoublyHashTable(DNS_IP, #DHT_ADD_ELEMENT, *dns_mapping, dns_item\item\dns, @dns_item\item)
If DHT_ReturnValue
Debug "Add item to hash table."
Else
Debug "Couldn't add item to hash table."
EndIf
dns_item\item\dns = "www.google.fr"
dns_item\item\ip = MakeIPAddress(209, 85, 129, 147)
DoublyHashTable(DNS_IP, #DHT_ADD_ELEMENT, *dns_mapping, dns_item\item\dns, @dns_item\item)
If DHT_ReturnValue
Debug "Add item to hash table."
Else
Debug "Couldn't add item to hash table."
EndIf
Debug ""
DoublyHashTable(DNS_IP, #DHT_COUNT_ELEMENTS, *dns_mapping)
Debug "The hash table contains "+Str(DHT_ReturnValue)+" entries:"
DHTForEach(DNS_IP, *dns_mapping, *dns_item)
Debug *dns_item\item\dns
Debug IPString(*dns_item\item\ip)
DHTNext(DNS_IP, *dns_mapping, *dns_item)
Debug ""
DoublyHashTable(DNS_IP, #DHT_GET_ELEMENT, *dns_mapping, "www.GOOGLE.com")
*dns_item = DHT_ReturnValue
If *dns_item
Debug "The ip for www.GOOGLE.com is:"
Debug IPString(*dns_item\item\ip)
Else
Debug "Couldn't get element for "+Chr('"')+"www.GOOGLE.com"+Chr('"')+"."
EndIf
Debug ""
DoublyHashTable(DNS_IP, #DHT_GET_ELEMENT, *dns_mapping, "www.google.br")
*dns_item = DHT_ReturnValue
If *dns_item
Debug "The ip for www.google.br is:"
Debug IPString(*dns_item\item\ip)
Else
Debug "Couldn't get element for "+Chr('"')+"www.google.br"+Chr('"')+"."
EndIf
Debug ""
DoublyHashTable(DNS_IP, #DHT_CLEAR_TABLE, *dns_mapping)
Debug "Deleted all entries from the hash table."
Debug ""
DoublyHashTable(DNS_IP, #DHT_GET_ELEMENT, *dns_mapping, "www.google.com")
*dns_item = DHT_ReturnValue
If *dns_item
Debug "The ip for www.google.com is:"
Debug IPString(*dns_item\item\ip)
Else
Debug "Couldn't get element for "+Chr('"')+"www.google.com"+Chr('"')+"."
EndIf
DoublyHashTable(DNS_IP, #DHT_COUNT_ELEMENTS, *dns_mapping)
Debug "The hash table contains "+Str(DHT_ReturnValue)+" entries."
Debug ""
DoublyHashTable(DNS_IP, #DHT_DELETE, *dns_mapping)
Debug "Deleted the hash table."
Debug "------------------------------"