PureBasic Forums - English

Code: Select all

;
; hashtable.pb
;   provide associative strings storage
;   global methods
;     .i addmultimap(key$, value$, Array key$(1), Array value$(1), Array table.s_hashtable(1))
;
;       desc:     add value pair to respective arrays
;                 generate hash for key and append relation information to
;                 table and return index of added value pair
;
;       key$      value pair to be added to map
;       value$
;       key$()    storage arrays for the type
;       value$()
;       table     relation table, uses initial size as table width
;                 conflicting hashes will add depth to the table
;
;     .i querymapindex(key$, start, Array key$(1), Array table.s_hashtable(1))
;
;       desc:     search for key in table and return the index number of the
;                 value pair
;
;       key$      search string
;       start     starting index of valid results
;       key$()
;       table
;
;   private methods
;     .i hashtable_hashingfunction(string$)
;
;       desc:     generate a deterministic positive number
;                 associated with the string
;
;       string$
;
;   global structures
;     s_hashtable
;
;       desc:     data structure for associative relation of value pair
;
;   private structures
;     hashtable_char
;
;       desc:     pointer access of string contents
;


XIncludeFile "generic.pb"

; structures

Structure s_hashtable
  c.i ; index of current value
  n.i ; index of next value
EndStructure

Structure hashtable_char
  c.c
EndStructure

; methods

Procedure.i hastable_hashingfunction(string$)

  *p.hashtable_char = @string$
  s = SizeOf(*p\c)

  ; calculate hash value using the shift-add algorithm
  For i = 1 To Len(string$)
    h << 4
    h + *p\c
    *p + s
  Next
  
  ; make sure h is positive
  If h < 0
    h = ~h + 1
  EndIf

  ProcedureReturn h
  
EndProcedure

Procedure.i addmultimap(key$, value$, Array key$(1), Array value$(1), Array table.s_hashtable(1))
  
  c = -1                    ; default value for the index parameter
  ks = ArraySize(key$())    ; get initial array size
  vs = ArraySize(value$())
  ts = ArraySize(table())

  ; table size must be >= 1
  ; should be about the size of the anticipated datum
  Assert(ts < 1)
  
  ; check whether table has been initialized
  ; use initial table size as hash size
  If table(0)\c = 0
    table(0)\n = ts
  EndIf
  
  ; get hash table size
  hs = table(0)\n 

  ; add key, value to array
  ; resize array as necessary
  c = table(0)\c
  
  If c > ks
    ks = ((ks + 1) * 2 - 1)
    ReDim key$(ks)
  EndIf
  key$(c) = key$
  
  If c > vs
    vs = ((vs + 1) * 2 - 1)
    ReDim value$(vs)
  EndIf
  value$(c) = value$
  
  ; calculate hash and array index
  i = hastable_hashingfunction(key$) % hs + 1
  
  ; go to the end of the hash space
  While Not(table(i)\n = 0)
    i = table(i)\n
  Wend
  
  ; add new hash link
  ; resize array as necessary
  t = 1 + table(0)\c + table(0)\n
  If t > ts
    ts = ((ts + 1) * 2 - 1)
    ReDim table(ts)
  EndIf
  table(t)\c = c
  table(i)\n = t
  
  ; change index parameter to next position
  table(0)\c + 1
  
  ProcedureReturn c
  
EndProcedure

Procedure.i querymapindex(key$, start, Array key$(1), Array table.s_hashtable(1))

  c = -1                   ; default value for the index parameter
  ts = ArraySize(table())  ; get array size

  ; table size must be >= 1
  ; should be about the size of the anticipated datum
  Assert(ts < 1)
  
  hs = table(0)\n ; get hash table size

  ; calculate hash and array index
  i = hastable_hashingfunction(key$) % hs + 1
  
  ; go to the first match greater than start
  ; stop at the end of hash space
  While Not(table(i)\n = 0 Or (key$(table(i)\c) = key$ And table(i)\c >= start))
      i = table(i)\n
  Wend
  
  If i > 0
    c = table(i)\c ; return the index of the value pair
  EndIf
  
  ProcedureReturn c
  
EndProcedure

Code: Select all

XIncludeFile "readcsv.pb"
XIncludeFile "hashtable.pb"

; main program

Dim csv$(0)
Dim index(0)

Dim key$(0)
Dim value$(0)
Dim table.s_hashtable(500)

If readcsv("test3.csv", csv$(), index())

  ; do csv processing here
  For i = 0 To ArraySize(index()) - 1
    j = index(i)
    k = index(i + 1) - j
    If k >= 2
      addmultimap(csv$(j), csv$(j + 1), key$(), value$(), table())
    EndIf
  Next
  
  For i = 0 To table(0)\c - 1
    Debug Str(i) + ": " + key$(i) + " -> " + value$(i)
  Next
  
  i = querymapindex(key$(10), 0, key$(), table())
  If i >= 0
    Debug Str(i) + ": " + key$(i) + " -> " + value$(i)
  EndIf
  
EndIf

End