\ Dynamic hash lists--definitions and allocation vandys
\ This file has a stillborn implementation of a list of values. Set has
\ replaced it, so all that remains here are generic hashing functions
\ used by other places which use hash-based techniques.
only extensions definitions
37 constant (#INITHASH)
100 constant (BINLEN) Local
0 [if]
Collection -> subclass: Hash ivars:
intcell #hash intcell bucks endivars
\ Each slot in "bucks" is a "List" instance of values
Hash -> class -> :method new ( self -- hash ) super-> new ( hash )
(#INITHASH) over Hash>#hash !
(#INITHASH) cells bkzalloc over Hash>bucks ! method;
[then]
\ Dynamic hash lists--hashing vandys
: (>hash) ( ptr -- u ) 5 rshift dup 16 rshift xor ;
0 [if]
: (>bin) { idx self -- idx' }
idx (>hash) self Hash>#hash @ mod ; Local
[then]
\ Dynamic hash lists--growth of bucket size vandys
: prime? ( u -- bool ) dup 2/ 1+ 3 do dup i mod 0= if
unloop drop false exit then
2 +loop drop true ; scrLocal
: (>newhash) ( u -- u' ) 2* 1+ begin dup prime? not while
2 + repeat ;
0 [if]
: (put) ( hash val -- ) swap -> ! ; scrLocal
Hash -> :method grow { self -- }
self Hash>#hash @ self Hash>bucks @ { old# oldbucks }
old# (>newhash) { new# } new# cells bkzalloc { newbucks }
new# self Hash>#hash ! newbucks self Hash>bucks !
oldbucks old# 0 do @+ ?dup if ( 'buck+ buck )
self ['] (put) rot -> do then loop drop
oldbucks bkfree method;
[then]
\ Dynamic hash lists--insertion vandys
0 [if]
Hash -> :method add { val self -- }
val self (>bin) cells self Hash>bucks @ + { 'bin }
'bin @ ?dup 0= if
List -> new dup 'bin ! val swap -> add exit then
{ bin } val bin -> in? if exit then
bin -> size (BINLEN) >= if self -> grow then method;
[then]
\ Dynamic hash lists--testing & display vandys
0 [if]
Hash -> :method in? { key self -- T | F } key self (>bin) ( buckidx )
cells self Hash>bucks @ + @ dup 0= if exit then
{ buck } key buck -> in? method;
Hash -> :method . { self -- } ." Hash {"
self Hash>bucks @ self Hash>#hash @ 0 do
@+ ?dup if ( 'buck+ buck ) -> . then
loop drop ." }" method;
[then]
vandys
Initial number of buckets for hashing
Length of a hash collision chain which forces rehash to larger size
class Hash--we hold count of # of buckets, and pointer to buckets
:method new Populate initial Hash. Our array of buckets starts as null
pointers; an Assocs instance is created on 1st reference
vandys
: (>hash) Convert index into a hash value
: (>bin) Given index and a hash, return index of bucket slot
: prime? Tell if the given number is prime. Assumes number is not
even.
: (>newhash) Given old hash size, double it and then move upward to
next nearest prime number.
: (put) As an iterator function for List's "do", store a member to the hash
:method grow Increase size of hash bucket array, and re-insert all
current contents into newly configured buckets.
vandys
:method add Store value into table.
If the bucket receiving this value has
grown larger than our threshold, grow the array of buckets to spread the
contents across more buckets.
vandys