Oxygen Basic
Programming => Example Code => Data Processing => Topic started by: Aurel on December 03, 2012, 10:59:49 PM
-
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... :-\
-
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?
-
Do you want it for storing / finding variable names?
Hi Charles..
Yes .
You read my mind.. ;)
-
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...
-
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.
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
-
Thanks Charles...
;)
-
Charles..
because i don't understand ASM do you can translate this code to oxygen basic code:
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
-
Hi Aurel,
This is a OxygenBasic Function. No need for translation.
-
Hi
i am to old to start learn assembler ;D
So maybe you know how this sounds in Basic syntax?
-
Hi,
I am too old now to translate it to Basic hocus-pocus.
-
Is not maybe easier to you to say
I DON'T WANT ...right?
-
Hi Aurel,
Still need to use rol (rotate left) but the syntax will pass for basic.
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
-
Thank you Charles ;)