This is the mail archive of the guile@cygnus.com mailing list for the guile project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
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). * ************************************************************************/