From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Kevin Ryde Newsgroups: gmane.lisp.guile.devel Subject: doco hash tables Date: Thu, 31 Jul 2003 09:02:34 +1000 Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Message-ID: <87oezb1uut.fsf@zip.com.au> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: main.gmane.org 1059606503 698 80.91.224.249 (30 Jul 2003 23:08:23 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Wed, 30 Jul 2003 23:08:23 +0000 (UTC) Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Jul 31 01:08:18 2003 Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 19i036-000096-00 for ; Thu, 31 Jul 2003 01:08:00 +0200 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.20) id 19hzzo-0008L8-Kj for guile-devel@m.gmane.org; Wed, 30 Jul 2003 19:04:36 -0400 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.20) id 19hzyY-000838-6H for guile-devel@gnu.org; Wed, 30 Jul 2003 19:03:18 -0400 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.20) id 19hzyI-0007o8-Np for guile-devel@gnu.org; Wed, 30 Jul 2003 19:03:03 -0400 Original-Received: from snoopy.pacific.net.au ([61.8.0.36]) by monty-python.gnu.org with esmtp (Exim 4.20) id 19hzy1-0007bu-Iy for guile-devel@gnu.org; Wed, 30 Jul 2003 19:02:45 -0400 Original-Received: from sunny.pacific.net.au (sunny.pacific.net.au [203.2.228.40]) by snoopy.pacific.net.au (8.12.3/8.12.3/Debian-6.4) with ESMTP id h6UN2giI031360 for ; Thu, 31 Jul 2003 09:02:43 +1000 Original-Received: from wisma.pacific.net.au (wisma.pacific.net.au [210.23.129.72]) by sunny.pacific.net.au with ESMTP id h6UN2g7a007280 for ; Thu, 31 Jul 2003 09:02:42 +1000 (EST) Original-Received: from localhost (ppp28.dyn228.pacific.net.au [203.143.228.28]) by wisma.pacific.net.au (8.12.9/8.12.9) with ESMTP id h6UN2daB029318 for ; Thu, 31 Jul 2003 09:02:40 +1000 (EST) Original-Received: from gg by localhost with local (Exim 3.35 #1 (Debian)) id 19hzxr-0001Yb-00; Thu, 31 Jul 2003 09:02:35 +1000 Original-To: guile-devel@gnu.org Mail-Copies-To: never User-Agent: Gnus/5.090019 (Oort Gnus v0.19) Emacs/21.2 (gnu/linux) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.2 Precedence: list List-Id: Developers list for Guile, the GNU extensibility library List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.devel:2672 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.devel:2672 This is a proposed revision for the hash tables node. The main aim is to cut down the duplication between the function descriptions, to try to the basic operations clearer. I've tried to spruce up the introductory words too. An example of using the hashx functions might be nice, maybe case-insensitive string keys like already mentioned, if someone's got a nice hash function along those lines. I noticed there's no hashx-remove!, is that merely an omission (in the code that is), or am I missing something? Is it true that modifying the hash table while hash-fold is iterating over it will have unpredicatable results? (As far as the elements seen or not seen go.) Probably worth a warning about that. Hash Table Reference .................... A hash table stores key/value pairs, designed for fast lookups by key. Keys and values can be any Scheme objects. A hash table is similar to an association list in the way it holds keys and values (*note Association Lists::), but an association list requires a linear search to locate an element, which can be slow when the list is long. A hash table instead uses arithmetic to make a array index from a key, so lookups take a more or less fixed time no matter how big the table. Like the association list functions, the hash table functions come in several varieties, according to the equality test used for the keys. Plain `hash-' functions use `equal?', `hashq-' functions use `eq?', `hashv-' functions use `eqv?', and the `hashx-' functions use an application supplied test (for instance to implement case insensitive strings). A single `make-hash-table' creates a hash table suitable for use with any set of functions, but it's imperative that just one set is then used consistently, or results will be unpredictable. Hash tables are implemented as a vector indexed by an integer formed from the key, and a association list of key/value pairs for each bucket in case distinct keys hash together. Direct access to the pairs in those lists is provided by the `-handle-' functions. For the `hashx-' "extended" routines, an application supplies a HASH function producing an integer index (as per `hashq' etc below), and an ASSOC alist search function (as per `assq' etc, *Note Retrieving Alist Entries::.). The aim in the HASH function is to have different keys spread out across the vector, so the bucket lists don't become long, but the exact values generated are otherwise arbitrary. - Scheme Procedure: make-hash-table size Create a new hash table of SIZE slots. Note that the number of slots does not limit the size of the table, it just tells how large the underlying vector will be. The SIZE should be similar to the expected number of elements which will be added to the table, but they need not match. For good performance, it might be a good idea to use a prime number as the SIZE. - Scheme Procedure: hash-ref table key [dflt] - Scheme Procedure: hashq-ref table key [dflt] - Scheme Procedure: hashv-ref table key [dflt] - Scheme Procedure: hashx-ref hash assoc table key [dflt] - C Function: scm_hash_ref (table, key, dflt) - C Function: scm_hashq_ref (table, key, dflt) - C Function: scm_hashv_ref (table, key, dflt) - C Function: scm_hashx_ref (hash, assoc, table, key, dflt) Lookup KEY in the given hash TABLE, and return the associated value. If KEY is not found, return DFLT, or `#f' if DFLT is not given. (For the C functions, DFLT must be given.) - Scheme Procedure: hash-set! table key val - Scheme Procedure: hashq-set! table key val - Scheme Procedure: hashv-set! table key val - Scheme Procedure: hashx-set! hash assoc table key val - C Function: scm_hash_set_x (table, key, val) - C Function: scm_hashq_set_x (table, key, val) - C Function: scm_hashv_set_x (table, key, val) - C Function: scm_hashx_set_x (hash, assoc, table, key, val) Associate VAL with KEY in the given hash TABLE. If KEY is already present then it's associated value is changed. If it's not present then a new entry is created. - Scheme Procedure: hash-remove! table key - Scheme Procedure: hashq-remove! table key - Scheme Procedure: hashv-remove! table key - C Function: scm_hash_remove_x (table, key) - C Function: scm_hashq_remove_x (table, key) - C Function: scm_hashv_remove_x (table, key) Remove any association for KEY in the given hash TABLE. If KEY is not in TABLE then nothing is done. - Scheme Procedure: hash key size - Scheme Procedure: hashq key size - Scheme Procedure: hashv key size - C Function: scm_hash (key, size) - C Function: scm_hashq (key, size) - C Function: scm_hashv (key, size) Return a hash value for KEY. This is a number in the range 0 to SIZE - 1, which is suitable for use in a hash table of the given SIZE. Note that `hashq' and `hashv' may use internal addresses of objects, so if an object is garbage collected and re-created it can have a different hash value, even when the two are notionally `eq?'. For instance with symbols, (hashq 'something 123) => 19 (gc) (hashq 'something 123) => 62 In normal use this is not a problem, since an object entered into a hash table won't be garbage collected until removed. It's only if hashing calculations are somehow separated from normal references to an object that its lifetime needs to be considered. - Scheme Procedure: hash-get-handle table key - Scheme Procedure: hashq-get-handle table key - Scheme Procedure: hashv-get-handle table key - Scheme Procedure: hashx-get-handle hash assoc table key - C Function: scm_hash_get_handle (table, key) - C Function: scm_hashq_get_handle (table, key) - C Function: scm_hashv_get_handle (table, key) - C Function: scm_hashx_get_handle (hash, assoc, table, key) Return the `(KEY . VALUE)' pair for KEY in the given hash TABLE, or `#f' if KEY is not in TABLE. - Scheme Procedure: hash-create-handle! table key init - Scheme Procedure: hashq-create-handle! table key init - Scheme Procedure: hashv-create-handle! table key init - Scheme Procedure: hashx-create-handle! hash assoc table key init - C Function: scm_hash_create_handle_x (table, key, init) - C Function: scm_hashq_create_handle_x (table, key, init) - C Function: scm_hashv_create_handle_x (table, key, init) - C Function: scm_hashx_create_handle_x (hash, assoc, table, key, init) Return the `(KEY . VALUE)' pair for KEY in the given hash TABLE. If KEY is not in TABLE then create an entry for it with INIT as the value, and return that pair. - Scheme Procedure: hash-fold proc init table - C Function: scm_hash_fold (proc, init, table) Accumulate a result by applying PROC to the elements of the given hash TABLE. Each call is `(PROC KEY VALUE PRIOR-RESULT)', where KEY and VALUE are from the TABLE and PRIOR-RESULT is the return from the previous PROC call. For the first call, PRIOR-RESULT is the given INIT value. Calls are made over the elements in an unspecified order. For example, the following returns an alist comprising all the entries from a hash table `mytable', (hash-fold acons '() mytable) _______________________________________________ Guile-devel mailing list Guile-devel@gnu.org http://mail.gnu.org/mailman/listinfo/guile-devel