Re: Scheme style auto-resizing hashtable (fwd)

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

alright, the non-hash storing code, "hashtab-nostore.[ch]" looks a bit
rough but "hashtab-type.[ch]" is okay.

the code, and extra goodies, are at
http://www.giss.nasa.gov/~jglascoe/hashtab-type/

Here's the comments preceding "hashtab-type.c"

/**********************************************************************
 *  File "hashtab-type.c", by Jay Glascoe.  10/30/98
 *  Inspired by Jim Blandy's image-type example,
 *  the Python dictionary object, and a whole host
 *  of messages on the Guile mailing list.
 *  Special thanks to Maciej Stachowiak of MIT
 *  and Harvey J. Stein of BFM Financial Research.
 *  And thanks to Dirk Herrmann from [somewhere in Germany]
 *  for helping me to "see the light" with regards to the
 *  advantages of not storing a key's hash value in the
 *  associated entry.
 *
 *  This is a Guile extension providing procedures to
 *  create and operate on auto-resizing hash tables.
 *
 *  A hash table is a pair, it looks like this
 *
 *     (header . vector)
 *
 *  The car of the pair, the header, is a vector.  It's used to
 *  keep track of various book keeping details.  It looks
 *  like this
 *
 *     #(hashtab-type number-entries auto-shrink-flag store-hash-flag)
 *
 *  The cdr of the hash table pair is also a vector.  Its
 *  elements are referred to as "buckets" or "entry lists".
 *  It looks like this
 *
 *     #(bucket1 bucket2 ... bucketN)
 *
 *  Each bucket is a list of entries
 *
 *     (entry1 entry2 ... entryN)
 *
 *  Each entry is a pair, or "association".  The car of the
 *  association is the "hash value" of the entry's key.  The
 *  cdr of the association is a key-value pair.  Entries look
 *  like this
 *
 *     (hash (key . value))
 * 
 *  OR, if the store-hash option is disabled
 * 
 *     (key . value)
 *
 *  The procedures defined in this extension are listed below.
 *
 *  primitive: make-hashtab
 *  primitive: make-hashtabv
 *  primitive: make-hashtabq
 *      Return a new auto-resizing hash table (auto-shrink is ON
 *      and store-hash is ON, by default).  A "hashtab" type
 *      hash table uses the equal? prediacte.  A "hashtabv"
 *      type hash table uses the eqv? predicate.  And a
 *      "hashtabq" type table uses the eq? predicate.  All
 *      three types use appropriate hashing functions.
 *
 *  primitive: hashtab-enable hashtab symbol
 *  primitive: hashtab-disable hashtab symbol
 *      "symbol" should be one of 'auto-shrink, 'store-hash.
 *      Turn the specified option on/off.  When the "store-hash"
 *      option is toggled, rebuild hash table "hashtab" so that
 *      the hash value of all keys in the table are/aren't stored
 *      with the associated entry.
 *          In general, you'll probably want the store-hash option
 *      ON.  However, if the keys you use are primarily symbols, booleans,
 *      characters, or integers (NOT "big integers"), then you should
 *      consider disabling the store-hash option.  YMMV
 *          In general, you'll probably want the auto-shrink option ON
 *      even if you're constantly deleting entries from the hash table.
 *      Timing tests show no advantages to disabling auto-shrink,
 *      even when the tests consist solely of inserting 10,000
 *      entries, then deleting them all, then re-inserting them,
 *      re-deleting, etc., etc.  YMMV      
 *
 *  primitive: hashtab-set! hashtab key value
 *      Insert "value" in hash table "hashtab" under key "key".
 *      If "key" is already present in "hashtab", overwrite the
 *      previous associated value with "value".  Return "value".
 *
 *  primitive: hashtab-ref hashtab key [default]
 *      Look up "key" in the hash table "hashtab", and return the value
 *	(if any) associated with it. If "key" is not found, return
 *      "default" (or #f if no default argument is supplied). 
 *
 *  primitive: hashtab-del! hashtab key [default]
 *      Delete the entry in hash table "hashtab" having key "key",
 *      and return the value associated with "key" (if any).
 *      If "key" is not found, return "default" (or #f if no default
 *      argument is supplied). 
 *
 ************************************************************************/