PureBasic Forums - English

http://www.purebasic.com
https://www.purebasic.fr/english/

yet another HashTable

https://www.purebasic.fr/english/viewtopic.php?t=33633

Page 1 of 1

yet another HashTable

Posted: Wed Aug 06, 2008 11:21 pm
by pcfreak
use it as you like, an example is added
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 "------------------------------"
All times are UTC+01:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited