( ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ )
( Proposed hash function for Retro -- based on djb2, Bernstein )
(                                                              )
( see: http://www.cse.yorku.ca/~oz/hash.html, for example.     )
( ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ )
( Copyright [c] 2010, Marc Simpson                             )
( License: ISC                                                 )
( ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ )
( Most documented hash functions leverage unsigned longs       )
( during computation -- here we use *signed* cells as unsigned )
( words are not offered by Retro at the present time.  So that )
( we avoid returning negative hash values, hashing is filtered )
( through 'abs'.  [Negative values emerge due to shifting into )
( the sign bit.]                                               )
(                                                              )
( The 'hash-prime' variable has been selected to provide a     )
( reasonable balance between clashing and key size -- this is  )
( to ensure that associative arrays built using 'hash' don't   )
( need to allocate too much heap.  This can be adjusted by     )
( revectoring 'hash' in the [unlikely] event of large tables.  )
( ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ )
( NOTE:                                                        )
( -----                                                        )
(                                                              )
( Since altering 'hash-prime' would affect previously written  )
( tables, we shall introduce the following condition: you may  )
( modify 'hash-prime' before creating hash-tables, but once    )
( this has been done, do NOT change its value afterward.       )
(                                                              )
( Of course, we could make 'hash' more flexible and have it    )
( read a prime value [or define a second word that respects a  )
( stack value for modding].  For now, let's just regard our    )
( stipulation as well justified; either tweak the provided     )
( hashing routines _before_ use, or leave them be.             )
( ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ )

vocab hashing
((
  {{
    : abs  dup 0 <if neg then ;
    ---reveal---
    ( Dan Bernstein, comp.lang.c with 'abs' hack )
    : djb2 ( $-n )
      5381 over getLength fori push
      dup 5 << + over pop + @ + nexti nip abs ;
  }}

  ( 193, 389, 769 are all pretty good; if you expect to have )
  ( a lot of keys, use a larger prime.                       )
  389 variable: hash-prime

  ( Vector the favoured hash function -- we intend to offer  )
  ( a range of implementations and allow the user to choose  )
  : hash ( $-n ) djb2 hash-prime @ mod ;
))

' hashing shut