'2018-06-06T13:22:52
'HASH STORAGE

type element
============
  bstring key   'key name
  bstring dat   'data
  int     ha    'hash code
  int prev,next 'links
end type

class HashStorage
=================
  '
  'BODY
  =====
  element*el  'element pointer
  element*pl  'prev element pointer
  int hb[512] 'hash buckets
  int ha      'hash code
  int hi      'hash bucket index
  int ne      'max number of elements
  sys bu      'element buffer
  int ce      'element count
  int ke      'current element
  '
  macro hash()
  ============
  mov edx,0x35db53bd
  addr rcx,k
  cmp rcx,0
  jz fwd nhashcode
  rhashcode:
    mov al,[ecx]
    cmp al,0
    jz fwd nhashcode
    rol edx,1
    xor dl,al
    inc rcx
    jmp rhashcode
  nhashcode:
  addr rax,ha
  mov [rax],edx
  end macro
  '
  method constructor(int n=1000)
  ==============================
  ne=n
  bu=getmemory sizeof(element)*ne
  end method
  '
  method destructor()
  ===================
  int i
  @el=bu
  for i=1 to ce
    freememory strptr el.key
    freememory strptr el.dat
    @el+=sizeof(el)
  next
  freememory bu
  ne=0
  end method
  '
  method Append()
  ===============
  if ce>=ne then
    sys bp=bu
    int np=ne
    ne+=1000
    bu=getmemory ne*sizeof(element)
    copy bu,bp,np*sizeof(element)
    freememory bp
  end if
  @el=bu+ce*sizeof(element)
  end method
  '
  method disallocate(int c=0)
  ===========================
  ce=c
  int a,i
  int b at @hb
  for i=1 to 512
    do
      if not b then exit do
      a=b-1
      @el=bu+a*sizeof(element)
      el.next=0
      if b>ce then
        del el.key
        del el.dat
        b=el.prev
      else
        exit do
      end if
    loop
    @b+=4
  next
  end method
  '
  method v(string k,d)
  ====================
  'SET
  int p
  hash()
  hi=ha and 511
  ke=hb[hi]
  @pl=0
  if not ke then
    Append()
    el={k,d,ha,0,0}
    ce++
    hb[hi]=ce
  else
    'lookup
    do 'from last to first
      ke-- 'base 0
      @el=bu+ke*sizeof(element)
      if ha=el.ha
        if el.key=k
          'match
          el.dat=d
          exit do
        end if
      end if
      'no match, try previous
      ke=el.prev
      if not ke then 'append
        Append()
        p=hb[hi]
        el={k,d,ha,p,0}
        ce++
        if @pl then pl.next=ce
        hb[hi]=ce
        exit do
      end if
      @pl=@el
    loop   
  end if  
  end method
  '
  method v(string k) as string
  ============================
  'GET
  hash()
  hi=ha and 511
  ke=hb[hi]
  if not ke then return 0
  'lookup
  do
    ke-- 'base 0
    @el=bu+ke*sizeof(element)
    if ha=el.ha
      if el.key=k
        'match
        return el.dat
      end if
    end if
    'no match, try previous
    ke=el.prev
    if not ke then return 0
  loop   
  end method
  '
end class

'TESTS
======
new HashStorage aa(1000)
aa.v("va")=42
aa.v("vb")=43
print aa.v("va")
'print aa.ce
del aa
