'2018-06-07T13:52:25
'HASH STORAGE WITH MEMORY POOL


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

class HashStoragePool
=====================
 '
  'BODY
  '=====
  '
  element*el  'element pointer
  element*pp  '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
  sys pu      'memory pool
  int ce      'element count
  int ke      'current element
  int pl      'memory pool length
  int pe      'memory pool offset
  '
  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
  pu=getmemory 8000
  end method
  '
  method destructor()
  ===================
  @el=bu
  freememory bu
  freememory pu
  ne=0 : pl=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
        'itr loss of pooled string in older members
        pe=el.key-4 'disallocate pooled strings
        b=el.prev
      else
        exit do
      end if
    loop
    @b+=4
  next
  end method

  method poolput(string s,int k=0) as int
  =======================================
  'WRITE STRING TO POOL
  'itr disallocation
  int ls=len(s)
  sys ps=strptr(s)-4
  if k>0 then
    int lp at pu+k-4
    if ls<=lp then
      'reuse existing location
      copy pu+k-4,ps,ls+6
      return k
    end if
  end if
  k=pe+ls+6
  if k>pl then
    sys po=pu
    int n=pl
    pl+=0x10000+ls+6
    pu=getmemory pl
    copy pu,po,n
    freememory po 'free old pool
  end if
  copy pu+pe,ps,ls+6
  method=pe+4
  pe=k
  end method
  '
  method poolget(int k) as string
  ===============================
  'READ STRING FROM POOL
  if k then
    int ls at pu+k-4
    method=nuls ls
    copy strptr(method),pu+k,ls
  end if
  end method
  '
  method poolcmp(string s, int k) as int
  ======================================
  'COMPARE STRING WITH POOLED STRING
  int ls=len s
  int lk at pu+k-4
  if ls<>lk then return 0
  byte bs at strptr s
  byte bp at pu+k
  int i
  for i=1 to ls
    if bs<>bp then return 0
    @bs++ : @bp++
  next
  return 1
  end method
  '
  method v(string k,d)
  ====================
  'SET
  int p, kp, dp
  hash()
  hi=ha and 511
  ke=hb[hi]
  @pp=0
  if not ke then
    Append()
    kp=poolput(k)
    dp=poolput(d)
    el={kp,dp,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 poolcmp(k,el.key)
          'match
          dp=poolput(d,el.dat)
          el.dat=dp
          exit do
        end if
      end if
      'no match, try previous
      ke=el.prev
      if not ke then 'append
        Append()
        p=hb[hi]
        kp=poolput(k)
        dp=poolput(d)
        el={kp,dp,ha,p,0}
        ce++
        if @pp then pp.next=ce
        hb[hi]=ce
        exit do
      end if
      @pp=@el
    loop   
  end if
  end method
  '
  method v(string k) as string
  ============================
  'GET
  return poolget(p(k)) 
  end method
  '
  method p(string k) as sys
  ==========================
  '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 poolcmp(k,el.key)
        '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
======
'#recordof HashStoragePool
new HashStoragePool aa(1000)
aa.v("va")=42
aa.v("vb")=43
print aa.v("vb")
'print aa.ce
del aa


