## hnt - Generic Hash Table

### Module Description

The hnt module implements a generic hash table that can store variable size nodes. It is the base module for more specialized hash tables, for example the cell hash table [hct].

### Module Words

#### Hash table structure

hnt% ( -- n )
  Get the required space for a hash table variable

#### Hash table creation, initialisation and destruction

hnt-init ( u hnt -- )
  Initialise the hash table with an initial size u
hnt-(free) ( xt hnt -- )
  Free the nodes from the heap using xt
hnt-create ( u "<spaces>name" -- ; -- hnt )
  Create a named hash table with an initial size u in the dictionary
hnt-new ( u -- hnt )
  Create a hash table with an initial size u on the heap
hnt-free ( hnt -- )
  Free the hash table from the heap

#### Module words

hnt+hash ( c-addr1 u1 -- u2 )
  Calculate the hash value of the key c-addr1 u1

#### Member words

hnt-empty? ( hnt -- flag )
  Check for an empty table
hnt-length@ ( hnt -- u )
  Get the number of nodes in the table
hnt-load@ ( hnt -- u )
  Get the load factor [*100%]
hnt-load! ( u hnt -- )
  Set the load factor [*100%]
hnt-size! ( u hnt -- )
  Resize the hash table

#### Hash table words

hnt-search ( c-addr u hnt -- u hnn )
  Search the node based on the key, return the hash u and the node hnn
hnt-insert ( hnn hnt -- )
  Insert the node hnn in the table, double keys are NOT checked
hnt-delete ( c-addr u hnt -- nil | hnn )
  Delete the key c-addr u from the table, return the deleted node hnn
hnt-get ( c-addr u hnt -- nil | hnn )
  Get the node related to the key c-addr u from the table, return the node hnn
hnt-has? ( c-addr u hnt -- flag )
  Check if the key c-addr u is present in the table

#### Special words

hnt-execute ( i*x xt hnt -- j*x )
  Execute xt for every key and node in table

#### Inspection

hnt-dump ( hnt -- )
  Dump the hash table

### Examples

    include ffl/hnt.fs
    include ffl/hni.fs

    \ Example: store scientific constants in a hash table

    \ Extend the base node with a float for storing the value of the constant

    begin-structure sc%
      hnn%
      +field  sc>ht                      \ Node extends the base node
      ffield: sc>value                   \ Value of constant
    end-structure

    \ Create the hash table in the dictionary with an initial size of 10

    10 hnt-create sc-table

    \ Word for adding the value

    : sc-add ( r c-addr u -- = value key )
      2dup sc-table hnt-search                     \ Search if the key is already present in the hash table
      dup nil<> IF                                 \ If the key is already present Then
        nip nip nip                                \   Remove the key and hash value from stack
        sc>value f!                                \   Update the node in the hash table with the value
      ELSE                                         \ Else
        drop                                       \   Drop nil
        sc% allocate throw                         \   Allocate a new sc% node
        >r
        r@ hnn-init                                \   Initialise the new sc% node with the key and hash
        r@ sc>value f!                             \   Save the value in the node
        r> sc-table hnt-insert                     \   Store the sc% node in the hash table
      THEN
    ;

    \ Add the constants

    3.14158E+0 s" pi"     sc-add
    2.71828E+0 s" euler"  sc-add
    1.61803E+0 s" golden" sc-add

    \ Word for printing the scientific constant

    : sc-emit ( sc% -- )
      dup hnn-key@ type ."  -> " sc>value f@ f. cr
    ;

    \ Print all scientific constants

    ' sc-emit sc-table hnt-execute                \ Execute the word sc-emit for all entries in the hash table

    \ Example hash table iterator

    \ Create the hash table iterator in the dictionary

    sc-table hni-create sc-iter                   \ Create an iterator named sc-iter on the sc-table hash table

    \ Moving the iterator

    sc-iter hni-first                             \ Move the iterator to the first record
    nil<> [IF]                                    \ If record exists Then ..
      sc-iter hni-key type                        \   Type the key ..
      .(  => )
      sc-iter hni-get sc>value f@ f.              \   .. and the value
      cr
    [THEN]

    sc-iter hni-next                              \ Move the iterator to the next record
    nil<> [IF]                                    \ If record exists Then ..
      sc-iter hni-key type                        \   Type the key ..
      .(  => )
      sc-iter hni-get sc>value f@ f.              \   .. and the value
      cr
    [ELSE]
      .( No next record in the hash table) cr
    [THEN]

generated 03-Jun-2010 by ofcfrth-0.10.0