Hash table

[Aurel]

Hi Charles...
Is there any example which show how create hash table ?
I look into oxygen src and found only maco() but i don't understand
how this thing work...

[Charles Pegge]

I'm reworking one of the examples, Aurel. Hash table usage is always a bit complicated. Do you want it for storing / finding variable names?

[Aurel]

Do you want it for storing / finding variable names?

Hi Charles..
Yes .
You read my mind..

[Aurel]

When i look into rosseta code
and i know this before
i will for start use two arrays...
In one will be name[] and in second value[] ...and
of course because both have same index this will be no big problem.
I know that this is not real hash table with pointers but will work with
search iteration to find name & value...

Maybe Linked List will be easier to built in...

[Charles Pegge]

Hi Aurel,

This is very close to what I use in Oxygen. It supports scoped and local names.

You can associate any non-zero token with a name, and use the token to index your variables attributes.

It uses a stretchable buffer so the size of the hash table is unrestricted.

Code: [Select]

 function hashcode(string s) as long
  '==================================
  xor eax,eax
  mov edx, [s]     ' name pointer
  mov ecx, [edx-4] ' length
  (
  cmp ecx,0
  jnz exit
  return 0 'EMPTY WORD WILL TRIGGER HASHCODE ERROR LATER
  )
  mov ah,  cl      ' assume max length 255
  (
    xor al,  [edx]
    xor eax,0x3a575a73
    rol eax,18
    inc edx
    dec ecx
    jnz repeat
  )
  return eax
  '
  end function


  type hashrec
  '===========
  string name
  sys    hash
  sys    next
  sys    token
  end type


  'GLOBAL
  '======

  hashrec*   ht
  string     hashbuf
  sys        lenbuf
  sys        maxr,maxri,maxrs[64]


  function stretchbuf()
  '====================
  if maxr*sizeof hashrec>lenbuf
    hashbuf+=nuls(1024*sizeof hashrec)
    lenbuf=len hashbuf
    @ht=strptr hashbuf
  end if
  end function


  function storename(string name, sys token)
  '=========================================
  sys h,b,c,i,le
  h=hashcode name
  b=h and 511
  c=b
  do
    b=ht[b].next
    if b=0 or b>maxr
      maxr++
      b=maxr
      stretchbuf()
      ht[c].next=b
      ht[b]<=name,h,0,token
      exit do
    end if
    c=b
  end do
  end function


  function findname(string name) as sys
  '====================================
  sys h,b,c,f
  h=hashcode name
  b=h and 511
  c=b
  b=ht[b].next
  do
    if b=0
      exit do
    elseif b>maxr
      if c
        ht[c].next=0
      end if
      exit do
    end if
    if h=ht[b].hash
      if name=ht[b].name
        f=b
      end if
    end if
    c=b
    b=ht[b].next
  end do
  if f
    return ht[f].token 'LAST MATCH
  end if
  end function


  function pushmaxr()
  '==================
  maxri++
  maxrs[maxri]=maxr
  end function


  function popmaxr()
  '==================
  maxr=maxrs[maxri]
  maxri--
  end function


  'INITIAL
  '=======
  '
  maxr=511
  stretchbuf()

  'TEST STORAGE
  '============

  storename "aardvard",41
  storename "aardvark",42
  storename "aardvarc",43
  pushmaxr 'FENCE FOR LOCAL SCOPE
  storename "aardvark",142

  print " 41>>" findname "aardvard"
  print "142>>" findname "aardvark"
  print " 43>>" findname "aardvarc"
  popmaxr 'RELEASE LOCAL SCOPE
  print " 42>>" findname "aardvark"


  'TEST HASHCODER
  '==============


  function falsematchtest(sys e) 'CHECKING FOR FALSE MATCHES
  '=============================
  'e 0x40000 'takes a while!
  'e 0x4000

  type htest
    string s
    sys    h
  end type

  string buf=nuls((e+1)*sizeof htest)
  htest *t
  @t=strptr buf

  sys a,c,i,j,p

  for i=1 to e
    t[i].s="aaaa"
    p=strptr t[i].s
    *p+=i
    t[i].h=hashcode t[i].s
  next

  string pr,cr
  cr=chr(13)+chr(10)
  pr=""
  for i=1 to e-1
    a=t[i].h
    for j=i+1 to e
      if a=t[j].h then
        pr+= hex(i,8) "    " hex(j,8) "    " hex(t[i].h,8)  cr
        c++
        if c>20 then goto fin 'LIMIT LIST
      end if
    next
  next
  
  fin:
  ====

  if pr
    print "false coincidences: "+cr+pr
  else
    print "no false coincidences in " e
  end if
  end function

  'falsematchtest 0x4000


Charles

[Aurel]

Thanks Charles...
 

[Aurel]

Charles..
because i don't understand ASM do you can translate this code to oxygen basic code:

Code: [Select]

function hashcode(string s) as long
  '==================================
  xor eax,eax
  mov edx, [s]     ' name pointer
  mov ecx, [edx-4] ' length
  (
  cmp ecx,0
  jnz exit
  return 0 'EMPTY WORD WILL TRIGGER HASHCODE ERROR LATER
  )
  mov ah,  cl      ' assume max length 255
  (
    xor al,  [edx]
    xor eax,0x3a575a73
    rol eax,18
    inc edx
    dec ecx
    jnz repeat
  )
  return eax
  '
  end function

[Peter]

Hi Aurel,

This is a OxygenBasic Function. No need for translation.

[Aurel]

Hi
i am to old to start learn assembler
So maybe you know how this sounds in Basic syntax?

[Peter]

Hi,

I am too old now to translate it to Basic hocus-pocus.

[Aurel]

Is not maybe easier to you to say
I DON'T WANT ...right?
 

[Charles Pegge]

Hi Aurel,

Still need to use rol (rotate left) but the syntax will pass for basic.

Code: [Select]

function hashcode(string s) as long
===================================
if not s then return 0
byte b at (strptr s)
sys  e=len s
sys  a=e*256
sys  i
for i=1 to e
  a = a xor 0x3a575a73 xor b
  rol a,18
  @b++
next
return a
end function


function hashcodeA(string s) as long
====================================
  xor eax,eax
  mov edx, [s]     ' name pointer
  mov ecx, [edx-4] ' length
  (
  cmp ecx,0
  jnz exit
  return 0 'EMPTY WORD WILL TRIGGER HASHCODE ERROR LATER
  )
  mov ah,  cl      ' assume max length 255
  (
    xor al,  [edx]
    xor eax,0x3a575a73
    rol eax,18
    inc edx
    dec ecx
    jnz repeat
  )
  return eax
  '
  end function

  n="A" : print hex(Hashcode(n)) + "    " + hex(HashcodeA(n))
  n="Maxmillian" : print hex(Hashcode(n)) + "    " + hex(HashcodeA(n))

Charles

[Aurel]

Thank you Charles