source: project/wiki/eggref/5/srfi-69 @ 31404

Last change on this file since 31404 was 31404, checked in by felix, 3 years ago

added srfi 18/69 documentation

File size: 11.1 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4== srfi-69
5
6An implementation of SRFI 69 with SRFI 90 extensions. For more information, see
7[[http://srfi.schemers.org/srfi-69/srfi-69.html|SRFI-69]] and
8[[http://srfi.schemers.org/srfi-90/srfi-90.html|SRFI-90]].
9A straightforward implementation of [[http://en.wikipedia.org/wiki/Binary_search|binary search]].
10
11
12=== Hash Table Procedures
13
14
15==== make-hash-table
16
17<procedure>(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>
18
19Returns a new {{HASH-TABLE}} with the supplied configuration.
20
21; {{TEST}} : The equivalence function.
22; {{HASH}} : The hash function.
23; {{SIZE}} : The expected number of table elements.
24; {{INITIAL}} : The default initial value.
25; {{MIN-LOAD}} : The minimum load factor. A {{flonum}} in (0.0 1.0).
26; {{MAX-LOAD}} : The maximum load factor. A {{flonum}} in (0.0 1.0).
27; {{WEAK-KEYS}} : Use weak references for keys. (Ignored)
28; {{WEAK-VALUES}} : Use weak references for values. (Ignored)
29
30Please note that hash tables are ''not'' guaranteed to compare {{equal?}}
31to each other, even if they contain exactly the same key/value pairs.
32
33
34==== alist->hash-table
35
36<procedure>(alist->hash-table A-LIST [#: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>
37
38Returns a new {{HASH-TABLE}}. The {{HASH-TABLE}} is populated from the
39{{A-LIST}}. The keyword arguments are per {{make-hash-table}}.
40
41
42==== hash-table?
43
44<procedure>(hash-table? OBJECT)</procedure>
45
46Is the {{OBJECT}} a {{hash-table}}?
47
48
49==== hash-table-size
50
51<procedure>(hash-table-size HASH-TABLE)</procedure>
52
53The {{HASH-TABLE}} size.
54
55
56==== hash-table-equivalence-function
57
58<procedure>(hash-table-equivalence-function HASH-TABLE)</procedure>
59
60The {{HASH-TABLE}} {{equivalence-function}}.
61
62
63==== hash-table-hash-function
64
65<procedure>(hash-table-hash-function HASH-TABLE)</procedure>
66
67The {{HASH-TABLE}} {{hash-function}}.
68
69
70==== hash-table-min-load
71
72<procedure>(hash-table-min-load HASH-TABLE)</procedure>
73
74The {{HASH-TABLE}} minimum load factor.
75
76
77==== hash-table-max-load
78
79<procedure>(hash-table-max-load HASH-TABLE)</procedure>
80
81The {{HASH-TABLE}} maximum load factor.
82
83
84==== hash-table-weak-keys
85
86<procedure>(hash-table-weak-keys HASH-TABLE)</procedure>
87
88Does the {{HASH-TABLE}} use weak references for keys?
89
90
91==== hash-table-weak-values
92
93<procedure>(hash-table-weak-values HASH-TABLE)</procedure>
94
95Does the {{HASH-TABLE}} use weak references for values?
96
97
98==== hash-table-has-initial?
99
100<procedure>(hash-table-has-initial? HASH-TABLE)</procedure>
101
102Does the {{HASH-TABLE}} have a default initial value?
103
104
105==== hash-table-initial
106
107<procedure>(hash-table-initial HASH-TABLE)</procedure>
108
109The {{HASH-TABLE}} default initial value.
110
111
112==== hash-table-keys
113
114<procedure>(hash-table-keys HASH-TABLE)</procedure>
115
116Returns a list of the keys in the {{HASH-TABLE}} population.
117
118
119==== hash-table-values
120
121<procedure>(hash-table-values HASH-TABLE)</procedure>
122
123Returns a list of the values in the {{HASH-TABLE}} population.
124
125
126==== hash-table->alist
127
128<procedure>(hash-table->alist HASH-TABLE)</procedure>
129
130Returns the population of the {{HASH-TABLE}} as an {{a-list}}.
131
132
133
134==== hash-table-ref
135
136<procedure>(hash-table-ref HASH-TABLE KEY)</procedure>
137
138Returns the {{VALUE}} for the {{KEY}} in the {{HASH-TABLE}}.
139
140Aborts with an exception when the {{KEY}} is missing.
141
142
143==== hash-table-ref/default
144
145<procedure>(hash-table-ref/default HASH-TABLE KEY DEFAULT)</procedure>
146
147Returns the {{VALUE}} for the {{KEY}} in the {{HASH-TABLE}}, or the {{DEFAULT}}
148when the {{KEY}} is missing.
149
150
151==== hash-table-exists?
152
153<procedure>(hash-table-exists? HASH-TABLE KEY)</procedure>
154
155Does the {{KEY}} exist in the {{HASH-TABLE}}?
156
157
158==== hash-table-set!
159
160<procedure>(hash-table-set! HASH-TABLE KEY VALUE)</procedure>
161
162Set the {{VALUE}} for the {{KEY}} in the {{HASH-TABLE}}.
163
164A setter for {{hash-table-ref}} is defined, so
165
166<enscript highlight=scheme>
167(set! (hash-table-ref HASH-TABLE KEY) VALUE)
168</enscript>
169
170is equivalent to
171
172<enscript highlight=scheme>
173(hash-table-set! HASH-TABLE KEY VALUE)
174</enscript>
175
176
177==== hash-table-update!
178
179<procedure>(hash-table-update! HASH-TABLE KEY [UPDATE-FUNCTION [DEFAULT-VALUE-FUNCTION]])</procedure>
180
181Sets or replaces the {{VALUE}} for {{KEY}} in the {{HASH-TABLE}}.
182
183The {{UPDATE-FUNCTION}} takes the existing {{VALUE}} for {{KEY}} and returns
184the new {{VALUE}}. The default is {{identity}}
185
186The {{DEFAULT-VALUE-FUNCTION}} is called when the entry for {{KEY}} is missing.
187The default uses the {{(hash-table-initial-value)}}, if provided. Otherwise
188aborts with an exception.
189
190Returns the new {{VALUE}}.
191
192
193==== hash-table-update!/default
194
195<procedure>(hash-table-update!/default HASH-TABLE KEY UPDATE-FUNCTION DEFAULT-VALUE)</procedure>
196
197Sets or replaces the {{VALUE}} for {{KEY}} in the {{HASH-TABLE}}.
198
199The {{UPDATE-FUNCTION}} takes the existing {{VALUE}} for {{KEY}} and returns
200the new {{VALUE}}.
201
202The {{DEFAULT-VALUE}} is used when the entry for {{KEY}} is missing.
203
204Returns the new {{VALUE}}.
205
206
207==== hash-table-copy
208
209<procedure>(hash-table-copy HASH-TABLE)</procedure>
210
211Returns a shallow copy of the {{HASH-TABLE}}.
212
213
214==== hash-table-delete!
215
216<procedure>(hash-table-delete! HASH-TABLE KEY)</procedure>
217
218Deletes the entry for {{KEY}} in the {{HASH-TABLE}}.
219
220
221==== hash-table-remove!
222
223<procedure>(hash-table-remove! HASH-TABLE PROC)</procedure>
224
225Calls {{PROC}} for all entries in {{HASH-TABLE}} with the key and value of each
226entry. If {{PROC}} returns true, then that entry is removed.
227
228
229==== hash-table-clear!
230
231<procedure>(hash-table-clear! HASH-TABLE)</procedure>
232
233Deletes all entries in {{HASH-TABLE}}.
234
235
236==== hash-table-merge
237
238<procedure>(hash-table-merge HASH-TABLE-1 HASH-TABLE-2)</procedure>
239
240Returns a new {{HASH-TABLE}} with the union of {{HASH-TABLE-1}} and
241{{HASH-TABLE-2}}.
242
243
244==== hash-table-merge!
245
246<procedure>(hash-table-merge! HASH-TABLE-1 HASH-TABLE-2)</procedure>
247
248Returns {{HASH-TABLE-1}} as the union of {{HASH-TABLE-1}} and
249{{HASH-TABLE-2}}.
250
251
252==== hash-table-map
253
254<procedure>(hash-table-map HASH-TABLE FUNC)</procedure>
255
256Calls {{FUNC}} for all entries in {{HASH-TABLE}} with the key and value of each
257entry.
258
259Returns a list of the results of each call.
260
261
262==== hash-table-fold
263
264<procedure>(hash-table-fold HASH-TABLE FUNC INIT)</procedure>
265
266Calls {{FUNC}} for all entries in {{HASH-TABLE}} with the key and value of each
267entry, and the current folded value. The initial folded value is {{INIT}}.
268
269Returns the final folded value.
270
271
272==== hash-table-for-each
273
274<procedure>(hash-table-for-each HASH-TABLE PROC)</procedure>
275
276Calls {{PROC}} for all entries in {{HASH-TABLE}} with the key and value of each
277entry.
278
279
280==== hash-table-walk
281
282<procedure>(hash-table-walk HASH-TABLE PROC)</procedure>
283
284Calls {{PROC}} for all entries in {{HASH-TABLE}} with the key and value of each
285entry.
286
287
288=== Hashing Functions
289
290All hash functions return a {{fixnum}} in the range [0 {{BOUND}}).
291
292When given the fixnum RANDOMIZATION, these functions will use this
293to perturb the value; if not specified, the value will differ for
294each invocation of your program. This is for security reasons; an
295attacker who knows what a value hashes to can deliberately try to
296cause collisions, thereby flattening your hash table, effectively
297reducing it to a list.  Always make sure you don't expose any
298hashed value to an attacker.
299
300
301==== number-hash
302
303<procedure>(number-hash NUMBER [BOUND RANDOMIZATION])</procedure>
304
305For use with {{=}} as a {{hash-table-equivalence-function}}.
306
307
308==== object-uid-hash
309
310<procedure>(object-uid-hash OBJECT [BOUND RANDOMIZATION])</procedure>
311
312Currently a synonym for {{equal?-hash}}.
313
314
315==== symbol-hash
316
317<procedure>(symbol-hash SYMBOL [BOUND RANDOMIZATION])</procedure>
318
319For use with {{eq?}} as a {{hash-table-equivalence-function}}.
320
321
322==== keyword-hash
323
324<procedure>(keyword-hash KEYWORD [BOUND RANDOMIZATION])</procedure>
325
326For use with {{eq?}} as a {{hash-table-equivalence-function}}.
327
328
329==== string-hash
330
331<procedure>(string-hash STRING [BOUND START END RANDOMIZATION])</procedure>
332
333For use with {{string=?}} as a {{hash-table-equivalence-function}}.
334The optional {{START}} and {{END}} arguments may be given to limit
335the hash calculation to a specific sub-section of {{STRING}}.
336
337
338==== string-ci-hash
339
340<procedure>(string-hash-ci STRING [BOUND START END RANDOMIZATION])</procedure><br>
341<procedure>(string-ci-hash STRING [BOUND START END RANDOMIZATION])</procedure>
342
343For use with {{string-ci=?}} as a {{hash-table-equivalence-function}}.
344
345
346==== eq?-hash
347
348<procedure>(eq?-hash OBJECT [BOUND RANDOMIZATION])</procedure>
349
350For use with {{eq?}} as a {{hash-table-equivalence-function}}.
351
352
353==== eqv?-hash
354
355<procedure>(eqv?-hash OBJECT [BOUND RANDOMIZATION])</procedure>
356
357For use with {{eqv?}} as a {{hash-table-equivalence-function}}.
358
359
360==== equal?-hash
361
362<procedure>(equal?-hash OBJECT [BOUND RANDOMIZATION])</procedure>
363
364For use with {{equal?}} as a {{hash-table-equivalence-function}}.
365
366
367==== hash
368
369<procedure>(hash OBJECT [BOUND RANDOMIZATION])</procedure>
370
371Synonym for {{equal?-hash}}.
372
373
374==== hash-by-identity
375
376<procedure>(hash-by-identity OBJECT [BOUND RANDOMIZATION])</procedure>
377
378Synonym for {{eq?-hash}}.
379
380
381==== recursive-hash-max-depth
382
383<parameter>(recursive-hash-max-depth)</parameter>
384
385The maximum structure depth to follow when computing a hash value. The default is {{4}}.
386
387
388==== recursive-hash-max-length
389
390<parameter>(recursive-hash-max-length)</parameter>
391
392The maximum vector length to follow when computing a hash value. The default is {{4}}.
393
394
395=== Author
396
397Original implementation by Felix, then heavily extended by Kon Lovett,
398now maintained by The CHICKEN Team.
399
400
401=== License
402
403 Copyright (c) 2008-2014, The Chicken Team
404 Copyright (c) 2000-2007, Felix L. Winkelmann
405 All rights reserved.
406 
407 Redistribution and use in source and binary forms, with or without
408 modification, are permitted provided that the following conditions
409 are met:
410 1. Redistributions of source code must retain the above copyright
411    notice, this list of conditions and the following disclaimer.
412 2. Redistributions in binary form must reproduce the above copyright
413    notice, this list of conditions and the following disclaimer in the
414    documentation and/or other materials provided with the distribution.
415 3. The name of the authors may not be used to endorse or promote products
416    derived from this software without specific prior written permission.
417 
418 THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
419 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
420 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
421 IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
422 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
423 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
424 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
425 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
426 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
427 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
428 
429
430=== Version History
431
432; 1.0 : Taken from the srfi-69 core library unit and released as an egg.
Note: See TracBrowser for help on using the repository browser.