Changes between Version 69 and Version 70 of HashTablesCowan
 Timestamp:
 07/01/13 23:20:36 (4 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

HashTablesCowan
v69 v70 104 104 Hash tables are allowed to cache the results of calling the equality predicate and hash function, so programs cannot rely on the hash function being called exactly once for every primitive hash table operation: it may be called zero, one, or more times. 105 105 106 No procedure passed to `hashtablefind`, `hashtablecount`, `hashtablemap`, `hashtableforeach`, `hashtableupdateeach!`, `hashtablemap>list`, or `hashtablefold` may mutatethe hash table being walked.106 It is an error if the procedure argument of `hashtablefind`, `hashtablecount`, `hashtablemap`, `hashtableforeach`, `hashtableupdateeach!`, `hashtablemap>list`, or `hashtablefold` mutates the hash table being walked. 107 107 108 108 === Index === … … 162 162 Returns `#t` if there is any association to ''key'' in ''hashtable'', and `#f` otherwise. Must execute in expected amortized constant time. (SRFI 69 `hashtableexists?`; R6RS `hashtablecontains?`) 163 163 164 `(hashtable=? `''value= hashtable,,1,, hashtable,,2,,''`)`165 166 Returns `#t` if ''hashtable,,1,,'' and ''hashtable,,2,,'' have the same size, the same keys (in the sense of their common equality predicate) and the same values (in the sense of the ''value= '' predicate) for each key, and `#f` otherwise. It is an error to compare two hash tables that have distinct comparators or distinct equality predicates.164 `(hashtable=? `''value=? hashtable,,1,, hashtable,,2,,''`)` 165 166 Returns `#t` if ''hashtable,,1,,'' and ''hashtable,,2,,'' have the same size, the same keys (in the sense of their common equality predicate) and the same values (in the sense of the ''value=?'' predicate) for each key, and `#f` otherwise. It is an error to compare two hash tables that have distinct comparators or distinct equality predicates. 167 167 168 168 === Accessors === … … 172 172 `(hashtableref `''hashtable key'' [ ''failure'' [ ''success'' ] ]`)` 173 173 174 Extracts the value associated to ''key'' in ''hashtable'', invokes the procedure ''success'' on it, and returns its result. Otherwise, invokes the procedure ''failure'' on no arguments and returns its result. If ''success'' is not provided and is required, the value itself is returned. If ''failure'' is not provided but is required, an error that satisfies `hashtablenotfound?` is signaled. Must execute in expected amortized O(1)time, not counting the time to call the procedures. (SRFI 69 `hashtableref`)174 Extracts the value associated to ''key'' in ''hashtable'', invokes the procedure ''success'' on it, and returns its result. Otherwise, invokes the procedure ''failure'' on no arguments and returns its result. If ''success'' is not provided and is required, the value itself is returned. If ''failure'' is not provided but is required, an error that satisfies `hashtablenotfound?` is signaled. Must execute in expected amortized constant time, not counting the time to call the procedures. (SRFI 69 `hashtableref`) 175 175 176 176 `(hashtableref/default `''hashtable key default''`)` … … 195 195 `(hashtablesetentries! `''hashtable keyslist valueslist''`)` 196 196 197 Repeatedly mutates ''hashtable'', setting each element of ''keyslist'' to the corresponding element of ''valueslist'' in the order given. 197 Repeatedly mutates ''hashtable'', setting each element of ''keyslist'' to the corresponding element of ''valueslist'' in the order given. Excess keys or values are ignored. 198 198 199 199 `(hashtablesetalist! `''hashtable alist''`)` … … 270 270 Returns the number of associations in ''hashtable'' as an exact integer. Should execute in expected amortized constant time. (SRFI 69 `hashtablesize`, R6RS `hashtablesize`; Common Lisp `hashtablecount`.) 271 271 272 Returns the number of keys in ''hashtable''.273 274 272 `(hashtablekeys `''hashtable''`)` 275 273 … … 286 284 `(hashtablefind `''hashtable proc''`)` 287 285 288 For each association of ''hashtable'', invoke ''proc'' on its key and value in an unspecified order. If ''proc'' returns true , then return the value. If ''proc'' always returns`#f`, return `#f`.286 For each association of ''hashtable'', invoke ''proc'' on its key and value in an unspecified order. If ''proc'' returns true on a value, then return that value. If all the calls to ''proc'' return `#f`, return `#f`. 289 287 290 288 `(hashtablecount `''hashtable pred''`)` … … 348 346 `(hashtableunion! `''hashtable,,1,, hashtable,,2,,'' [ ''merger'' ]`)` 349 347 350 Adds the associations of ''hashtable,,2,,'' to ''hashtable,,1,,'' and returns ''hashtable,,1,,''. The values of keys that appear in both hash tables are set to the result of the ''merger'' procedure, which accepts the arguments ''key,,1,, value,,1,, key,,2,, value,,2,,'' and defaults to `(lambda (key1 value1 key2 value2) value2)`. (SRFI 69 `hashtablemerge!`)348 Adds the associations of ''hashtable,,2,,'' to ''hashtable,,1,,'' and returns ''hashtable,,1,,''. The values of keys that appear in both hash tables are set to the result of invoking the ''merger'' procedure, which accepts the arguments ''key,,1,, value,,1,, key,,2,, value,,2,,'' and defaults to `(lambda (key1 value1 key2 value2) value2)`. (SRFI 69 `hashtablemerge!`) 351 349 352 350 `(hashtableintersection! `''hashtable,,1,, hashtable,,2,,'' [ ''merger'' ]`)` … … 366 364 == Implementation == 367 365 368 The sample implementation (''not yet written'') is designed to be easily layered over any hash table implementation that supports either SRFI 69 or R6RS (there is an implementation of [https://code.launchpad.net/~schemelibrariesteam/schemelibraries/srfi SRFI 69 on top of R6RS] ,It was originally intended to support all the native hash table systems mentioned in [#Sources Sources] above as well. However, this turned out not to be practical for the following reasons:366 The sample implementation (''not yet written'') is designed to be easily layered over any hash table implementation that supports either SRFI 69 or R6RS (there is an implementation of [https://code.launchpad.net/~schemelibrariesteam/schemelibraries/srfi SRFI 69 on top of R6RS]). It was originally intended to support all the native hash table systems mentioned in [#Sources Sources] above as well. However, this turned out not to be practical for the following reasons: 369 367 370 368 * Gauche does not support arbitrary equality predicates, only `eq?`, `eqv?`, `equal?`, and `string=?`. … … 382 380 As a result, the sample implementation assumes the existence of a SRFI 69 implementation, and imports just the core procedures `makehashtable`, `hashtable?`, `hashtableref/default`, `hashtableset!`, `hashtabledelete!`, `hashtablesize`, `hashtablewalk`, and `hashtablecopy`. New implementers who need to support the present proposal from scratch can take the implementations of these procedures from the SRFI 69 implementation and add them to this implementation. 383 381 384 To layer the implementation directly on top of R6RS, the corresponding procedures need to be imported from `(rnrs hashtables)`. See the file `hashtables.sls` in the implementation. It should also be possible to adapt the sample implementation for use on Racket, MIT, Gambit, and Bigloo .382 To layer the implementation directly on top of R6RS, the corresponding procedures need to be imported from `(rnrs hashtables)`. See the file `hashtables.sls` in the implementation. It should also be possible to adapt the sample implementation for use on Racket, MIT, Gambit, and Bigloo native hash tables, all of which provide at least the above core.