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

Last change on this file since 34689 was 34689, checked in by evhan, 6 weeks ago

srfi-69: Apply sjamaan's documentation updates from core (e311b617)

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