srfi-69-weak

TOC »

srfi-69-weak

An implementation of SRFI 69 with SRFI 90 extensions. For more information, see SRFI-69 and SRFI-90.

Not a drop-in replacement for the srfi-69 egg. While API compatible, the hashing functions and hash-table operations are in separate libraries, and the hash-table is incompatible. The hashing functions, however, are compatible.

Usage

space vs time - variable reference size: 1 - 2 cons cells

(import (srfi 69 hash) (srfi 69 weak var))

time vs space - fixed reference size: 2 cons cells

(import (srfi 69 hash) (srfi 69 weak fix))

Hash Table Procedures

make-hash-table

(make-hash-table [TEST [HASH]] [SIZE] [#:test TEST] [#:hash HASH] [#:size SIZE] [#:initial INITIAL] [#:min-load MIN-LOAD] [#:max-load MAX-LOAD] [#:weak-keys WEAK-KEYS] [#:weak-values WEAK-VALUES])procedure

Returns a new HASH-TABLE with the supplied configuration.

TEST: (* * -> boolean) ; equivalence function.
HASH: (* fixnum -> fixnum) ; hash function.
SIZE: fixnum ; expected number of table elements.
INITIAL: * ; default initial value.
MIN-LOAD: flonum(0.0 1.0) ; minimum load factor.
MAX-LOAD: flonum(0.0 1.0) ; maximum load factor.
WEAK-KEYS: boolean ; weak references for keys.
WEAK-VALUES: boolean ; weak references for values.

Please note that hash tables are not guaranteed to compare equal? to each other, even if they contain exactly the same key/value pairs.

alist->hash-table

(alist->hash-table ALIST [#:test TEST] [#:hash HASH] [#:size SIZE] [#:initial INITIAL] [#:min-load MIN-LOAD] [#:max-load MAX-LOAD] [#:weak-keys WEAK-KEYS] [#:weak-values WEAK-VALUES])procedure

Returns a new HASH-TABLE. The HASH-TABLE is populated from the ALIST. The keyword arguments are per make-hash-table.

If a key occurs multiple times in ALIST, the first occurrence will be used in the hash table.

hash-table?

hash-table? OBJECTprocedure: Is the OBJECT a hash-table?

hash-table-size

hash-table-size HASH-TABLEprocedure: The HASH-TABLE size. The returned exact non-negative integer is the count of associations in a table that holds data strongly. However weak-keys or weak-values mean the number can only be considered an upper bound.

hash-table-equivalence-function

hash-table-equivalence-function HASH-TABLEprocedure: The HASH-TABLE equivalence-function.

hash-table-hash-function

hash-table-hash-function HASH-TABLEprocedure: The HASH-TABLE hash-function.

hash-table-min-load

hash-table-min-load HASH-TABLEprocedure: The HASH-TABLE minimum load factor.

hash-table-max-load

hash-table-max-load HASH-TABLEprocedure: The HASH-TABLE maximum load factor.

hash-table-weak-keys

hash-table-weak-keys HASH-TABLEprocedure: Does the HASH-TABLE use weak references for keys?

hash-table-weak-values

hash-table-weak-values HASH-TABLEprocedure: Does the HASH-TABLE use weak references for values?

hash-table-has-initial?

hash-table-has-initial? HASH-TABLEprocedure: Does the HASH-TABLE have a default initial value?

hash-table-initial

hash-table-initial HASH-TABLEprocedure: The HASH-TABLE default initial value.

hash-table-empty?

hash-table-empty? HASH-TABLEprocedure: Is the HASH-TABLE without entries?

hash-table-keys

hash-table-keys HASH-TABLEprocedure: Returns a list of the keys in the HASH-TABLE population.

hash-table-values

hash-table-values HASH-TABLEprocedure: Returns a list of the values in the HASH-TABLE population.

hash-table-key-vector

hash-table-key-vector HASH-TABLEprocedure: Returns a vector of the keys in the HASH-TABLE population.

hash-table-value-vector

hash-table-value-vector HASH-TABLEprocedure: Returns a vector of the values in the HASH-TABLE population.

hash-table->alist

hash-table->alist HASH-TABLEprocedure: Returns the population of the HASH-TABLE as an association-list.

hash-table-ref

hash-table-ref HASH-TABLE KEYprocedure

Returns the VALUE for the KEY in the HASH-TABLE.

Aborts with an exception when the KEY is missing.

hash-table-ref/default

hash-table-ref/default HASH-TABLE KEY DEFAULTprocedure: Returns the VALUE for the KEY in the HASH-TABLE, or the DEFAULT when the KEY is missing.

hash-table-exists?

hash-table-exists? HASH-TABLE KEYprocedure: Does the KEY exist in the HASH-TABLE?

hash-table-set!

hash-table-set! HASH-TABLE KEY VALUE ...procedure

Set the VALUE for the KEY in the HASH-TABLE, then repeat for ....

A setter for hash-table-ref is defined.

hash-table-update!

hash-table-update! HASH-TABLE KEY #!optional UPDATE-FUNCTION DEFAULT-VALUE-FUNCTIONprocedure

Sets or replaces the VALUE for KEY in the HASH-TABLE.

The UPDATE-FUNCTION takes the existing VALUE for KEY and returns the new VALUE. The default is identity

The DEFAULT-VALUE-FUNCTION is called when the entry for KEY is missing. The default uses the (hash-table-initial-value), if provided. Otherwise aborts with an exception.

Returns the new VALUE.

hash-table-update!/default

hash-table-update!/default HASH-TABLE KEY UPDATE-FUNCTION DEFAULT-VALUEprocedure

Sets or replaces the VALUE for KEY in the HASH-TABLE.

The UPDATE-FUNCTION takes the existing VALUE for KEY and returns the new VALUE.

The DEFAULT-VALUE is used when the entry for KEY is missing.

Returns the new VALUE.

hash-table-copy

hash-table-copy HASH-TABLEprocedure: Returns a shallow copy of the HASH-TABLE.

hash-table-empty-copy

hash-table-empty-copy HASH-TABLEprocedure: Returns a very shallow copy of the HASH-TABLE, everything but the contents.

hash-table-delete!

hash-table-delete! HASH-TABLE KEYprocedure: Deletes the entry for KEY in the HASH-TABLE.

hash-table-remove!

hash-table-remove! HASH-TABLE PROCprocedure: Calls PROC for all entries in HASH-TABLE with the key and value of each entry. If PROC returns true, then that entry is removed.

hash-table-clean!

hash-table-clean! HASH-TABLEprocedure: Scavenges any broken weak entries in HASH-TABLE.

hash-table-clear!

hash-table-clear! HASH-TABLEprocedure: Deletes all entries in HASH-TABLE.

hash-table-merge

hash-table-merge HASH-TABLE-1 HASH-TABLE-2procedure: Returns a new HASH-TABLE with the union of HASH-TABLE-1 and HASH-TABLE-2. Keys that exist in both tables will be taken from HASH-TABLE-1.

hash-table-merge!

hash-table-merge! HASH-TABLE-1 HASH-TABLE-2procedure: Returns HASH-TABLE-1 as the union of HASH-TABLE-1 and HASH-TABLE-2. Keys that exist in both tables will be taken from HASH-TABLE-1.

hash-table-map

hash-table-map HASH-TABLE FUNCprocedure

Calls FUNC for all entries in HASH-TABLE with the key and value of each entry.

Returns a list of the results of each call.

hash-table-fold

hash-table-fold HASH-TABLE FUNC INITprocedure

Calls FUNC for all entries in HASH-TABLE with the key and value of each entry, and the current folded value. The initial folded value is INIT.

Returns the final folded value.

hash-table-for-each

hash-table-for-each HASH-TABLE PROCprocedure: Calls PROC for all entries in HASH-TABLE with the key and value of each entry.

hash-table-walk

hash-table-walk HASH-TABLE PROCprocedure: Calls PROC for all entries in HASH-TABLE with the key and value of each entry.

Hashing Functions

All hash functions return a fixnum in the range [0 BOUND).

When given the fixnum RANDOMIZATION, these functions will use this to perturb the value; if not specified, the value will differ for each invocation of your program. This is for security reasons; an attacker who knows what a value hashes to can deliberately try to cause collisions, thereby flattening your hash table, effectively reducing it to a list. Always make sure you don't expose any hashed value to an attacker.

hash-bound-default

hash-bound-defaultprocedure: Returns the default BOUND used by the builtin hash functions. The ones defined here.

string-hash

string-hash STRING #!optional BOUND START END RANDOMIZATIONprocedure: For use with string=? as a hash-table-equivalence-function. The optional START and END arguments may be given to limit the hash calculation to a specific sub-section of STRING.

string-ci-hash

string-hash-ci STRING #!optional BOUND START END RANDOMIZATIONprocedure

<br> <procedure>(string-ci-hash STRING [BOUND [START [END [RANDOMIZATION]]]])</procedure>

For use with string-ci=? as a hash-table-equivalence-function.

eq?-hash

eq?-hash OBJECT #!optional BOUND RANDOMIZATIONprocedure: For use with eq? as a hash-table-equivalence-function.

eqv?-hash

eqv?-hash OBJECT #!optional BOUND RANDOMIZATIONprocedure: For use with eqv? as a hash-table-equivalence-function.

equal?-hash

equal?-hash OBJECT #!optional BOUND RANDOMIZATIONprocedure: For use with equal? as a hash-table-equivalence-function.

hash

hash OBJECT #!optional BOUND RANDOMIZATIONprocedure: Synonym for equal?-hash.

hash-by-identity

hash-by-identity OBJECT #!optional BOUND RANDOMIZATIONprocedure: Synonym for eq?-hash.

recursive-hash-max-depth

recursive-hash-max-depth #!optional DEPTHprocedure: The maximum structure depth to follow when computing a hash value. The default is 4.

recursive-hash-max-length

recursive-hash-max-length #!optional LENGTHprocedure: The maximum vector length to follow when computing a hash value. The default is 4.

wrap-hash/triple32

wrap-hash/triple32 FUNCprocedure

Wraps a hash function, (_ fixnum -> fixnum), in a function that scrambles the hash value for higher entropy (more apparent randomness). The returned function has the signature (_ fixnum -> fixnum).

A builtin hash function should be presented to make-hash-table as (wrap-hash/triple32 (wrap-hash/std BUILTIN)), so a fresh salt is supplied.

BUILTIN: {{(or eq?-hash eqv?-hash equal?-hash hash string-hash

string-hash-ci number-hash object-uid-hash symbol-hash keyword-hash)}}

(import scheme (chicken base) (chicken fixnum)
        (srfi 69 hash) (srfi 42) slib-charplot)

(define *bound* 301 #;1073741823 #;(hash-bound-default))

;how make-hash-table handles hash functions
(define hashstd (wrap-hash/std hash))
(define hashmixed (wrap-hash/std (wrap-hash/triple32 hashstd)))

(print "*** hash of 64 gensym (" *bound* ") ***")
(parameterize ((plot-dimensions '(20 60)))
  (time (plot (vector-ec (: i 64) (hashstd (gensym) *bound*))))
  (print "*** w/o mixing ***")
  (time (plot (vector-ec (: i 64) (hashmixed (gensym) *bound*))))
  (print "*** w/ mixing ***") )

wrap-hash/std

wrap-hash/std FUNCprocedure

Wraps a hash function, (_ fixnum -> fixnum), in a function that validates the hash result for type & bounds. The returned function has the signature (_ fixnum -> fixnum). Builtin hash functions are also given a fresh RANDOMIZATION.

Note make-hash-table wraps supplied hash functions. Normally not a user called function.

Author

Felix, Kon, The CHICKEN Team, Kon.

Repository

This egg is hosted on the CHICKEN Subversion repository:

https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/srfi-69-weak

If you want to check out the source code repository of this egg and you are not familiar with Subversion, see this page.

Bugs & Limitations

Use of the hash-table object between (srfi 69), (srfi 90), (srfi 69 weak var) & (srfi 69 weak fix) imports is not supported. But one can fool themselves into thinking it is.
While encountered broken weak entries are scavenged during operations, not all are encountered. So the hash-table-size is an upper bound; an entry is scavenged when either a weak key or value reference is broken. For an accurate hash-table-size perform a hash-table-clean!.
The optional start & end arguments to the string-hash & string-hash-ci functions are of dubious utility.
The (srfi 69 weak fix) module is of dubious utility.

Requirements

test test-utils

License

Copyright (c) 2008-2021, The Chicken Team
Copyright (c) 2000-2007, Felix L. Winkelmann
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. The name of the authors may not be used to endorse or promote products
   derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Version History

1.0.0: Remove (most) SRFI 125 operations.
0.8.0: Add hash-table-empty?, hash-table-all!, hash-table-intern!, & hash-table-count.
0.7.1: Extend hash-table-set! signature.
0.7.0
0.6.0: Fix load calculation. Fix mutating operation types. Add hash-table-pop!, hash-table->plist, plist->hash-table, hash-table-key-vector, hash-table-value-vector, hash-table-find, hash-table-union!, hash-table-intersection!, hash-table-difference!, hash-table-xor!.
0.5.6: Add hash-table-empty-copy.
0.5.5: The equivalence & hash before the initial-size in make-hash-table are optional.
0.5.4: Move srfi-69 link-alike to sub-directory in distribution.
0.5.3: Internal improvements.
0.5.2: (skipped).
0.5.1: Fix for too eager resize attempts.
0.5.0: Storage contraction by hash-table-delete! & hash-table-remove!.
0.4.3: Fix hash-table-remove! - didn't cover the entire table!
0.4.2: Prevent useless resize attempts when at boundries.
0.4.1: Fix resize behavior as reported on #chicken irc by sjamaan (2025-08-17).
0.4.0: Rename *make-hash-function wrap-hash/std. Add wrap-hash/triple32, add hash-bound-default.
0.3.0: Testing w/ 10^5 entries; requires updated test-utils. Removed (srfi 90) module, see srfi-90.
0.2.3: Fix hash-table-clean!.
0.2.2: Support srfi-69 hash-table w/ discriminating record printer.
0.2.1: Provide srfi-90 feature.
0.2.0: Add (srfi 90) import (srfi.69.hash + srfi.69.weak.var).
0.1.1: Provide srfi-69-weak feature.
0.1.0: Initial release (from srfi-69:0.4.3), add 2 weak references implementations, add hash-table-clean!, recursive-hash-max-depth & recursive-hash-max-length are procedure, hash & hash-by-identity are #:clean, hash-table-max-load & hash-table-min-load return float, string-ci-hash & string-hash-ci return fixnum, hash-table-equivalence-function is inlined.

chickadee » srfi-69-weak

Identifier search

TOC »

Contents »