Debian Codegraph @

src/libhash.scm

raw
1 ;;;
2 ;;; libhash.scm - hashtables and treemaps
3 ;;;
4 ;;; Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 (select-module gauche.internal)
35
36 ;;;
37 ;;; Dictionary common macros
38 ;;;
39
40 (inline-stub
41 (.include "gauche/priv/configP.h")
42
43 (define-cise-stmt dict-check-entry
44 [(_ dict key expr)
45 `(when ,expr (Scm_Error "%S doesn't have an entry for key %S" ,dict ,key))])
46
47 (define-cise-stmt dict-get
48 [(_ dict referencer)
49 `(let* ([v (,referencer ,dict key fallback)])
50 (dict-check-entry ,dict key (SCM_UNBOUNDP v))
51 (return v))])
52
53 (define-cise-expr dict-exists?
54 [(_ dict referencer)
55 `(not (SCM_UNBOUNDP (,referencer ,dict key SCM_UNBOUND)))])
56
57 (define-cise-stmt dict-update!
58 [(_ dict searcher xtractor cc) ;; assumes key, proc, and fallback
59 `(let* ([e::ScmDictEntry*]
60 [data::(.array void* (1))])
61 (cond [(SCM_UNBOUNDP fallback)
62 (set! e (,searcher (,xtractor ,dict) (cast intptr_t key)
63 SCM_DICT_GET))
64 (dict-check-entry ,dict key (== e NULL))]
65 [else
66 (set! e (,searcher (,xtractor ,dict) (cast intptr_t key)
67 SCM_DICT_CREATE))
68 (unless (-> e value)
69 (cast void (SCM_DICT_SET_VALUE e fallback)))])
70 (set! (aref data 0) (cast void* e))
71 (Scm_VMPushCC ,cc data 1)
72 (return (Scm_VMApply1 proc (SCM_DICT_VALUE e))))])
73
74 (define-cise-stmt dict-push!
75 [(_ dict searcher xtractor)
76 `(let* ([e::ScmDictEntry* (,searcher (,xtractor ,dict )
77 (cast intptr_t key)
78 SCM_DICT_CREATE)]
79 [prev (?: (-> e value) (SCM_DICT_VALUE e) '())])
80 (cast void (SCM_DICT_SET_VALUE e (Scm_Cons value prev))))])
81
82 (define-cise-stmt dict-pop!
83 [(_ dict searcher xtractor)
84 `(let* ([e::ScmDictEntry* (,searcher (,xtractor ,dict)
85 (cast intptr_t key)
86 SCM_DICT_GET)])
87 (cond
88 [(not e)
89 (dict-check-entry ,dict key (SCM_UNBOUNDP fallback))
90 (return fallback)]
91 [(not (SCM_PAIRP (SCM_DICT_VALUE e)))
92 (when (SCM_UNBOUNDP fallback)
93 (Scm_Error "%S's value for key %S is not a pair: %S"
94 ,dict key (SCM_DICT_VALUE e)))
95 (return fallback)]
96 [else
97 (let* ([resultval_ (SCM_CAR (SCM_DICT_VALUE e))])
98 (cast void (SCM_DICT_SET_VALUE e (SCM_CDR (SCM_DICT_VALUE e))))
99 (return resultval_))]))])
100 )
101
102 ;; An unique object, used to detect exhausted iterator
103 (define *unique* (cons #f #f))
104
105 ;;;
106 ;;; Hashtables
107 ;;;
108
109 (select-module gauche)
110 (inline-stub
111 ;; this is called only for simple hash types, so don't need to handle
112 ;; SCM_HASH_GENEAL.
113 (define-cise-stmt set-hash-type!
114 [(_ cvar scmvar)
115 `(cond [(SCM_EQ ,scmvar 'eq?) (set! ,cvar SCM_HASH_EQ)]
116 [(SCM_EQ ,scmvar 'eqv?) (set! ,cvar SCM_HASH_EQV)]
117 [(SCM_EQ ,scmvar 'equal?) (set! ,cvar SCM_HASH_EQUAL)]
118 [(SCM_EQ ,scmvar 'string=?) (set! ,cvar SCM_HASH_STRING)]
119 [else (Scm_Error "unsupported hash type: %S" ,scmvar)])])
120
121 (define-cise-stmt get-hash-type
122 [(_ expr)
123 `(case ,expr
124 [(SCM_HASH_EQ) (return 'eq?)]
125 [(SCM_HASH_EQV) (return 'eqv?)]
126 [(SCM_HASH_EQUAL) (return 'equal?)]
127 [(SCM_HASH_STRING) (return 'string=?)]
128 [(SCM_HASH_GENERAL) (return 'general)]
129 [else (return '#f)] ; TODO: need to think over
130 )])
131 )
132
133 (select-module gauche)
134 (define-cproc hash-salt () ::<fixnum> Scm_HashSaltRef)
135
136 (define-cproc eq-hash (obj) ::<ulong> :fast-flonum Scm_EqHash)
137 (define-cproc eqv-hash (obj) ::<ulong> :fast-flonum Scm_EqvHash)
138 (define-cproc legacy-hash (obj) ::<ulong> :fast-flonum Scm_Hash)
139 (define-cproc portable-hash (obj salt::<fixnum>) ::<ulong>
140 :fast-flonum Scm_PortableHash)
141 (define-cproc default-hash (obj) ::<fixnum> :fast-flonum Scm_DefaultHash)
142 (define-cproc combine-hash-value (a::<ulong> b::<ulong>) ::<ulong>
143 Scm_CombineHashValue)
144
145 ;; see object-hash in libomega.scm for the reason of this implementation
146 (define (hash obj)
147 (let1 h ((with-module gauche.internal %current-recursive-hash))
148 (if h (h obj) (legacy-hash obj))))
149
150 (define-cproc hash-table? (obj) ::<boolean> :fast-flonum SCM_HASH_TABLE_P)
151
152 (define-cproc %make-hash-table-simple (type init-size::<int>)
153 (let* ([ctype::int 0])
154 (set-hash-type! ctype type)
155 (return (Scm_MakeHashTableSimple ctype init-size))))
156
157 (inline-stub
158 (define-cfn generic-hashtable-hash (h::(const ScmHashCore*) key::intptr_t)
159 ::u_long :static
160 (let* ([c::ScmComparator* (cast ScmComparator* (-> h data))]
161 [v::ScmObj (Scm_ApplyRec1 (Scm_ComparatorHashFunction c)
162 (SCM_OBJ key))])
163 (unless (or (SCM_INTP v) (SCM_BIGNUMP v))
164 (Scm_Error "Comparator %S's hash function should return \
165 an exact integer, but got: %S" c v))
166 (return (Scm_GetIntegerUMod v))))
167
168 (define-cfn generic-hashtable-hash-typecheck (h::(const ScmHashCore*)
169 key::intptr_t)
170 ::u_long :static
171 (let* ([c::ScmComparator* (cast ScmComparator* (-> h data))]
172 [t::ScmObj (Scm_ApplyRec1 (-> c typeFn) (SCM_OBJ key))])
173 (when (SCM_FALSEP t)
174 (Scm_Error "Invalid key for hashtable: %S" (SCM_OBJ key)))
175 (return (generic-hashtable-hash h key))))
176
177 (define-cfn generic-hashtable-eq (h::(const ScmHashCore*)
178 a::intptr_t b::intptr_t)
179 ::int :static
180 (let* ([c::ScmComparator* (cast ScmComparator* (-> h data))]
181 [e::ScmObj (Scm_ApplyRec2 (-> c eqFn) (SCM_OBJ a) (SCM_OBJ b))])
182 (return (not (SCM_FALSEP e)))))
183
184 (define-cfn generic-hashtable-eq-typecheck (h::(const ScmHashCore*)
185 a::intptr_t b::intptr_t)
186 ::int :static
187 (let* ([c::ScmComparator* (cast ScmComparator* (-> h data))]
188 [t::ScmObj (Scm_ApplyRec1 (-> c typeFn) (SCM_OBJ a))])
189 ;; NB: a is the key given from outside, and b is the key that's already
190 ;; in the table, so we only need to check a.
191 ;; TODO: Currently we may perform typecheck of a multiple times if
192 ;; we have more than one items with the same hash value in the table;
193 ;; optimization required.
194 (when (SCM_FALSEP t)
195 (Scm_Error "Invalid key for hashtable: %S" (SCM_OBJ a)))
196 (return (generic-hashtable-eq h a b))))
197 )
198
199 (define-cproc %make-hash-table-from-comparator (comparator::<comparator>
200 init-size::<int>
201 has-type-check::<boolean>)
202 (if has-type-check
203 (return (Scm_MakeHashTableFull generic-hashtable-hash-typecheck
204 generic-hashtable-eq-typecheck
205 init-size
206 comparator))
207 (return (Scm_MakeHashTableFull generic-hashtable-hash
208 generic-hashtable-eq
209 init-size
210 comparator))))
211
212 ;; Comparator argument can be <comparator> or one of the symbols
213 ;; eq?, eqv?, equal? or string=?.
214 (define (make-hash-table :optional (comparator 'eq?) (init-size 0))
215 (case comparator
216 [(eq? eqv? equal? string=?)
217 (%make-hash-table-simple comparator init-size)]
218 [else
219 (unless (comparator? comparator)
220 (error "make-hash-table requires a comparator or \
221 one of the symbols in eq?, eqv?, equal? or string=?, but got:"
222 comparator))
223 ;; If comparator's equality predicate is eq?/eqv?, we ignore
224 ;; the its hash function and force using eq-/eqv-hash,
225 ;; as permitted in SRFI-125. It allows object that doesn't have
226 ;; custom hash method can still be used with hashtables based on
227 ;; (make-eq[v]-comparator).
228 ;; https://github.com/shirok/Gauche/issues/708
229 (cond
230 [(or (eq? comparator eq-comparator)
231 (eq? (comparator-equality-predicate comparator) eq?))
232 (make-hash-table 'eq? init-size)]
233 [(or (eq? comparator eqv-comparator)
234 (eq? (comparator-equality-predicate comparator) eqv?))
235 (make-hash-table 'eqv? init-size)]
236 [(eq? comparator equal-comparator)
237 (make-hash-table 'equal? init-size)]
238 [(eq? comparator string-comparator)
239 (make-hash-table 'string=? init-size)]
240 [else
241 (unless (comparator-hashable? comparator)
242 (error "make-hash-table requires a comparator with hash function, \
243 but got:" comparator))
244 ($ %make-hash-table-from-comparator
245 comparator init-size
246 (not (eq? (comparator-type-test-predicate comparator)
247 (with-module gauche.internal default-type-test))))])]))
248
249 (define-cproc hash-table-type (hash::<hash-table>)
250 (get-hash-type (-> hash type)))
251
252 (select-module gauche.internal)
253 (define-cproc %hash-table-comparator-int (hash::<hash-table>)
254 (if (== (Scm_HashTableType hash) SCM_HASH_GENERAL)
255 (let* ([r (SCM_OBJ (-> (SCM_HASH_TABLE_CORE hash) data))])
256 (unless (SCM_COMPARATORP r)
257 (Scm_Error "Got some weird hashtable - possibly internal bug: %S"
258 hash))
259 (return r))
260 (return '#f)))
261 (select-module gauche)
262 (define (hash-table-comparator hash)
263 (case (hash-table-type hash)
264 [(eq?) eq-comparator]
265 [(eqv?) eqv-comparator]
266 [(equal?) equal-comparator]
267 [(string=?) string-comparator]
268 [(general) ((with-module gauche.internal %hash-table-comparator-int) hash)]
269 [else (error "unknown hashtable type:" hash)]))
270
271 (define-cproc hash-table-num-entries (hash::<hash-table>) ::<int>
272 (return (Scm_HashCoreNumEntries (SCM_HASH_TABLE_CORE hash))))
273
274 (define-cproc hash-table-clear! (hash::<hash-table>) ::<void>
275 (Scm_HashCoreClear (SCM_HASH_TABLE_CORE hash)))
276
277 (define-cproc hash-table-get (hash::<hash-table> key :optional fallback)
278 (dict-get hash Scm_HashTableRef))
279
280 (define-cproc hash-table-put! (hash::<hash-table> key value) ::<void>
281 (Scm_HashTableSet hash key value 0))
282
283 (define-cproc hash-table-adjoin! (hash::<hash-table> key value) ::<void>
284 (Scm_HashTableSet hash key value SCM_DICT_NO_OVERWRITE))
285
286 (define-cproc hash-table-replace! (hash::<hash-table> key value) ::<void>
287 (Scm_HashTableSet hash key value SCM_DICT_NO_CREATE))
288
289 ;; this is hash-table-remove! in STk. I use `delete' for
290 ;; it's consistent with SRFI-1 and dbm-delete!.
291 (define-cproc hash-table-delete! (hash::<hash-table> key) ::<boolean>
292 (return (not (SCM_UNBOUNDP (Scm_HashTableDelete hash key)))))
293
294 (define-cproc hash-table-exists? (hash::<hash-table> key) ::<boolean>
295 (return (dict-exists? hash Scm_HashTableRef)))
296
297 (inline-stub
298 (define-cfn hash-table-update-cc (result (data :: void**)) :static
299 (let* ([e::ScmDictEntry* (cast ScmDictEntry* (aref data 0))])
300 (cast void (SCM_DICT_SET_VALUE e result))
301 (return result)))
302 )
303
304 (define-cproc hash-table-update! (hash::<hash-table> key proc
305 :optional fallback)
306 (dict-update! hash Scm_HashCoreSearch SCM_HASH_TABLE_CORE
307 hash-table-update-cc))
308
309 (define-cproc hash-table-push! (hash::<hash-table> key value) ::<void>
310 (dict-push! hash Scm_HashCoreSearch SCM_HASH_TABLE_CORE))
311
312 (define-cproc hash-table-pop! (hash::<hash-table> key :optional fallback)
313 (dict-pop! hash Scm_HashCoreSearch SCM_HASH_TABLE_CORE))
314
315 (inline-stub
316 (define-cfn hash-table-iter (args::ScmObj* _::int data::void*) :static
317 (let* ([iter::ScmHashIter* (cast ScmHashIter* data)]
318 [e::ScmDictEntry* (Scm_HashIterNext iter)]
319 [eofval (aref args 0)])
320 (if (== e NULL)
321 (return (values eofval eofval))
322 (return (values (SCM_DICT_KEY e) (SCM_DICT_VALUE e))))))
323 )
324
325 (select-module gauche.internal)
326 (define-cproc %hash-table-iter (hash::<hash-table>)
327 (let* ([iter::ScmHashIter* (SCM_NEW ScmHashIter)])
328 (Scm_HashIterInit iter (SCM_HASH_TABLE_CORE hash))
329 (return (Scm_MakeSubr hash_table_iter iter 1 0 '"hash-table-iterator"))))
330
331 (select-module gauche)
332 (define-cproc hash-table-copy (ht::<hash-table> :optional _)
333 ;; we don't have immutable hash table, and ignore the optional
334 ;; mutable? argument (SRFI-125)
335 (return (Scm_HashTableCopy ht)))
336 (define-cproc hash-table-keys (ht::<hash-table>) Scm_HashTableKeys)
337 (define-cproc hash-table-values (ht::<hash-table>) Scm_HashTableValues)
338 (define-cproc hash-table-stat (ht::<hash-table>) Scm_HashTableStat)
339
340 ;; used in some internal routines
341 (define (hash-table-fold ht kons knil)
342 (assume-type ht <hash-table>)
343 (let1 i ((with-module gauche.internal %hash-table-iter) ht)
344 (let loop ([r knil])
345 (receive [k v] (i (with-module gauche.internal *unique*))
346 (if (eq? k (with-module gauche.internal *unique*))
347 r
348 (loop (kons k v r)))))))
349
350 ;; conversion to/from hash-table
351 (define (alist->hash-table a . opt-cmpr)
352 (rlet1 tb (apply make-hash-table opt-cmpr)
353 (for-each (^x (hash-table-put! tb (car x) (cdr x))) a)))
354
355 (define (hash-table->alist h)
356 (hash-table-map h cons))
357
358 (define unique (cons #f #f))
359
360 ;; vararg constructor 'hash-table' has conflicting API between
361 ;; legacy Gauche and R7RS scheme.hash-table (SRFI-125).
362 ;; R7RS's API is more convenient to use, so we eventually
363 ;; switch to it. Meantime, we provide original hash-table
364 ;; with a different name, hash-table-from-pairs, and R7RS
365 ;; hash-table as hash-table-r7.
366 (define (hash-table-from-pairs cmpr . kvs)
367 (rlet1 h (make-hash-table cmpr)
368 (for-each (^[kv] (hash-table-put! h (car kv) (cdr kv))) kvs)))
369
370 (define hash-table hash-table-from-pairs) ; transient
371
372 (define (hash-table-r7 cmpr . kvs) ; r7rs's hash-table
373 (rlet1 h (make-hash-table cmpr)
374 (doplist [(k v) kvs] (hash-table-put! h k v))))
375
376 (define (hash-table-empty? h) (zero? (hash-table-num-entries h))) ; r7rs
377 (define hash-table-contains? hash-table-exists?) ; r7rs
378 (define hash-table-size hash-table-num-entries) ; r7rs
379
380 (define (hash-table-mutable? ht) ; r7rs
381 (assume-type ht <hash-table>)
382 #t)
383
384 (define (hash-table-empty-copy ht) ; r7rs
385 (make-hash-table (hash-table-comparator ht)))
386
387 (define (hash-table-entries ht) ; r7rs
388 ;; can be more efficient
389 (values (hash-table-keys ht) (hash-table-values ht)))
390
391 (define (hash-table-unfold p f g seed cmpr . args) ; r7rs
392 (rlet1 ht (apply make-hash-table cmpr args)
393 (do ([seed seed (g seed)])
394 [(p seed)]
395 (receive [k v] (f seed)
396 (hash-table-put! ht k v)))))
397
398 ;; r7rs accessors
399
400 (define (hash-table-ref ht key :optional failure (success identity)) ;r7rs
401 ;; We avoid giving default value to failure, for the default closure
402 ;; needs to enclose key and it's costly.
403 (let1 v (hash-table-get ht key unique)
404 (if (eq? v unique)
405 (if (undefined? failure)
406 (error "hash table doesn't have an entry for key:" key)
407 (failure))
408 (success v))))
409
410 (define (hash-table-ref/default ht key default) ; r7rs
411 (hash-table-get ht key default))
412
413 (define (hash-table-set! ht . kvs) ; r7rs
414 (doplist [[k v] kvs]
415 (hash-table-put! ht k v)))
416
417 (define (hash-table-intern!-r7 ht key failure) ; r7rs
418 ;; we can't use hash-table-adjoin!, for we have to evaluate failure thunk
419 ;; after we know the entry's not in the table.
420 (let1 v (hash-table-get ht key unique)
421 (if (eq? v unique)
422 (rlet1 v (failure)
423 (hash-table-put! ht key v))
424 v)))
425
426 (define (hash-table-delete!-r7 ht . keys) ; r7rs
427 (fold (^[key count] (if (hash-table-delete! ht key) (+ count 1) count))
428 0 keys))
429
430 (define (hash-table-update!/default ht key updater default) ;r7rs
431 (hash-table-update! ht key updater default))
432
433 (define (hash-table-update!-r7 ht key updater ; r7rs
434 :optional failure (success identity))
435 (let1 v (hash-table-get ht key unique)
436 (if (eq? v unique)
437 (if (undefined? failure)
438 (error "hash table doesn't have an entry for key:" key)
439 (hash-table-put! ht key (updater (failure))))
440 (hash-table-put! ht key (updater (success v))))))
441
442 (define (hash-table-pop!-r7 ht) ; r7rs
443 (assume-type ht <hash-table>)
444 (let1 i ((with-module gauche.internal %hash-table-iter) ht)
445 (receive [k v] (i unique)
446 (when (eq? k unique)
447 (error "empty hash table can't be popped:" ht))
448 (hash-table-delete! ht k)
449 (values k v))))
450
451 ;; hash-table-map also disagree between Gauche and R7RS.
452 ;; We keep Gauche API, for we have consistent interface with other *-map
453 ;; procedures. We add a check in case the caller mistook this with R7RS one.
454 (define (hash-table-map ht proc :optional arg)
455 (when (not (undefined? arg))
456 (error "Gauche's built-in hash-table-map is called with R7RS interface. \
457 Use hash-table-map-r7, or say (use scheme.hash-table)."))
458 (assume-type ht <hash-table>)
459 (let1 i ((with-module gauche.internal %hash-table-iter) ht)
460 (let loop ([r '()])
461 (receive [k v] (i unique)
462 (if (eq? k unique)
463 r
464 (loop (cons (proc k v) r)))))))
465
466 ;; This is R7RS version of hash-table-map
467 (define (hash-table-map-r7 proc cmpr ht) ; r7rs
468 (assume-type cmpr <comparator>)
469 (assume-type ht <hash-table>)
470 (rlet1 r (make-hash-table cmpr)
471 (hash-table-for-each ht (^[k v] (hash-table-put! r k (proc v))))))
472
473 (define (hash-table-map!-r7 proc ht) ; r7rs
474 (assume-type ht <hash-table>)
475 (hash-table-for-each ht (^[k v] (hash-table-put! ht k (proc k v)))))
476
477 (define (hash-table-map->list-r7 proc ht) ; r7rs
478 (hash-table-map ht proc))
479
480 (define (hash-table-for-each ht proc)
481 (assume-type ht <hash-table>)
482 (let1 i ((with-module gauche.internal %hash-table-iter) ht)
483 (let loop ()
484 (receive [k v] (i unique)
485 (unless (eq? k unique)
486 (proc k v) (loop))))))
487
488 (define (hash-table-for-each-r7 proc ht) ; r7rs
489 (hash-table-for-each ht proc))
490
491 (define (hash-table-fold-r7 kons knil ht) ; r7rs
492 (hash-table-fold ht kons knil))
493
494 (define (hash-table-prune!-r7 proc ht) ; r7rs
495 (hash-table-for-each ht (^[k v] (when (proc k v) (hash-table-delete! ht k)))))
496
497 (define (hash-table-seek ht pred fail succ)
498 (assume-type ht <hash-table>)
499 (let1 i ((with-module gauche.internal %hash-table-iter) ht)
500 (let loop ()
501 (receive [k v] (i unique)
502 (cond [(eq? k unique) (fail)]
503 [(pred k v) => (^r (succ r k v))]
504 [else (loop)])))))
505
506 ;; hash-table-find. This doesn't align with other '*-find' API in a way that
507 ;; it returns the result of PRED.
508 (define (hash-table-find ht pred :optional (failure (^[] #f)))
509 (hash-table-seek ht pred failure (^[r k v] r)))
510
511 (define (hash-table-find-r7 pred ht failure) ; r7rs
512 (hash-table-seek ht pred failure (^[r k v] r)))
513
514 (define (hash-table-count-r7 pred ht) ; r7rs
515 ($ hash-table-fold ht
516 (^[k v count] (if (pred k v) (+ count 1) count)) 0))
517
518 ;; Set operations
519
520 (define (hash-table-union! ht1 ht2)
521 (assume-type ht1 <hash-table>)
522 (assume-type ht2 <hash-table>)
523 ($ hash-table-for-each ht2
524 (^[k v] (unless (hash-table-exists? ht1 k)
525 (hash-table-put! ht1 k v))))
526 ht1)
527
528 (define (hash-table-intersection! ht1 ht2)
529 (assume-type ht1 <hash-table>)
530 (assume-type ht2 <hash-table>)
531 ($ hash-table-for-each ht1
532 (^[k v] (unless (hash-table-exists? ht2 k)
533 (hash-table-delete! ht1 k))))
534 ht1)
535
536 (define (hash-table-difference! ht1 ht2)
537 (assume-type ht1 <hash-table>)
538 (assume-type ht2 <hash-table>)
539 ($ hash-table-for-each ht1
540 (^[k v] (when (hash-table-exists? ht2 k)
541 (hash-table-delete! ht1 k))))
542 ht1)
543
544 (define (hash-table-xor! ht1 ht2)
545 (assume-type ht1 <hash-table>)
546 (assume-type ht2 <hash-table>)
547 ($ hash-table-for-each ht2
548 (^[k v] (if (hash-table-exists? ht1 k)
549 (hash-table-delete! ht1 k)
550 (hash-table-put! ht1 k v))))
551 ht1)
552
553 ;; We delegate most hash calculation to the built-in default-hash.
554 ;; These type-specific hash functions are mostly
555 ;; for the compatibility of SRFI-128.
556
557 (define (boolean-hash obj)
558 (assume-type obj <boolean>)
559 (default-hash obj))
560
561 (define (char-hash obj)
562 (assume-type obj <char>)
563 (default-hash obj))
564
565 (define (char-ci-hash obj)
566 (assume-type obj <char>)
567 (default-hash (char-foldcase obj)))
568
569 (define (string-hash obj)
570 (assume-type obj <string>)
571 (default-hash obj))
572
573 (define (symbol-hash obj)
574 (assume-type obj <symbol>)
575 (default-hash obj))
576
577 (define (number-hash obj)
578 (assume-type obj <number>)
579 (default-hash obj))
580
581 ;; This is a placeholder to conform SRFI-128.
582 (define (hash-bound) (greatest-fixnum))
583
584 ;; Compare two hash-tables as sets.
585 (define (hash-table-compare-as-sets h1 h2
586 :optional (value=? equal?)
587 (fallback (undefined)))
588 (define unique (cons #f #f))
589 (define (fail)
590 (if (undefined? fallback)
591 (error "hash-tables can't be ordered:" h1 h2)
592 fallback))
593 ;; Returns #t iff smaller is a subset of larger.
594 (define (subset? smaller larger)
595 (hash-table-seek smaller
596 (^[k v] (let1 w (hash-table-get larger k unique)
597 (or (eq? unique w)
598 (not (value=? v w)))))
599 (^[] #t)
600 (^[r k v] #f)))
601
602 ;; Check comparator compatibility
603 (let ([c1 (hash-table-comparator h1)]
604 [c2 (hash-table-comparator h2)])
605 (cond [(and c1 c2 (equal? c1 c2)) c1]
606 [(or c1 c2) (error "hash-tables with different comparators can't be \
607 compared:" h1 h2)]
608 [else (error "hash-tables don't have comparators and can't be \
609 compared:" h1 h2)]))
610 ;; Let's start
611 (if (eq? h1 h2)
612 0 ;fast path
613 (let ([n1 (hash-table-num-entries h1)]
614 [n2 (hash-table-num-entries h2)])
615 (cond
616 [(= n1 n2) (if (subset? h1 h2) 0 (fail))]
617 [(< n1 n2) (if (subset? h1 h2) -1 (fail))]
618 [else (if (subset? h2 h1) 1 (fail))]))))
619
620 (define (hash-table=? value-cmpr h1 h2)
621 (or (eq? h1 h2)
622 (and (= (hash-table-num-entries h1) (hash-table-num-entries h2))
623 (equal? (hash-table-comparator h1) (hash-table-comparator h2))
624 (zero? (hash-table-compare-as-sets h1 h2
625 (cut =? value-cmpr <> <>)
626 100))))) ;; any non-zero number
627
628 ;;;
629 ;;; TreeMap
630 ;;;
631
632 (select-module gauche)
633 (inline-stub
634 ;; If tree-map-cmp is called, core->data should contain a comparator.
635 (define-cfn tree-map-cmp (core::ScmTreeCore* x::intptr_t y::intptr_t)
636 ::int :static
637 (let* ([cmpr (SCM_OBJ (-> core data))]
638 [_ (SCM_ASSERT (and cmpr (SCM_COMPARATORP cmpr)))]
639 [r (Scm_ApplyRec2 (Scm_ComparatorComparisonProcedure
640 (SCM_COMPARATOR cmpr))
641 (SCM_OBJ x) (SCM_OBJ y))])
642 (unless (SCM_INTP r)
643 (Scm_Error "compare procedure of tree-map's comparator %S returned \
644 non-integral value: %S" cmpr r))
645 (return (SCM_INT_VALUE r))))
646 )
647
648 (define-cproc %make-tree-map (comparator)
649 (begin
650 (SCM_ASSERT (SCM_COMPARATORP comparator))
651 (return (Scm_MakeTreeMap tree_map_cmp comparator))))
652
653 ;; TODO: We do want to return something even for tree-maps that aren't
654 ;; created from the Scheme world. But how?
655 (define-cproc tree-map-comparator (tm::<tree-map>)
656 (let* ([d::void* (-> (SCM_TREE_MAP_CORE tm) data)])
657 (if (or (== d NULL)
658 (!= (-> (SCM_TREE_MAP_CORE tm) cmp) tree-map-cmp))
659 (return SCM_FALSE)
660 (begin
661 (SCM_ASSERT (SCM_COMPARATORP d))
662 (return (SCM_OBJ d))))))
663
664 (define-cproc tree-map-copy (tm::<tree-map>) Scm_TreeMapCopy)
665
666 (define-cproc tree-map? (obj) ::<boolean> SCM_TREE_MAP_P)
667
668 (define-cproc tree-map-get (tm::<tree-map> key :optional fallback)
669 (dict-get tm Scm_TreeMapRef))
670
671 (define-cproc tree-map-put! (tm::<tree-map> key val) ::<void>
672 (Scm_TreeMapSet tm key val 0))
673
674 (define-cproc tree-map-adjoin! (tm::<tree-map> key val) ::<void>
675 (Scm_TreeMapSet tm key val SCM_DICT_NO_OVERWRITE))
676
677 (define-cproc tree-map-replace! (tm::<tree-map> key val) ::<void>
678 (Scm_TreeMapSet tm key val SCM_DICT_NO_CREATE))
679
680 (define-cproc tree-map-delete! (tm::<tree-map> key) ::<boolean>
681 (return (not (SCM_UNBOUNDP (Scm_TreeMapDelete tm key)))))
682
683 (inline-stub
684 (define-cfn tree-map-update-cc (result data::void**) :static
685 (let* ([e::ScmDictEntry* (cast ScmDictEntry* (aref data 0))])
686 (cast void (SCM_DICT_SET_VALUE e result))
687 (return result)))
688 )
689
690 (define-cproc tree-map-update! (tm::<tree-map> key proc :optional fallback)
691 (dict-update! tm Scm_TreeCoreSearch SCM_TREE_MAP_CORE tree_map_update_cc))
692
693 (define-cproc tree-map-push! (tm::<tree-map> key value) ::<void>
694 (dict-push! tm Scm_TreeCoreSearch SCM_TREE_MAP_CORE))
695
696 (define-cproc tree-map-pop! (tm::<tree-map> key :optional fallback)
697 (dict-pop! tm Scm_TreeCoreSearch SCM_TREE_MAP_CORE))
698
699 (define-cproc tree-map-exists? (tm::<tree-map> key) ::<boolean>
700 (return (dict-exists? tm Scm_TreeMapRef)))
701
702 (define-cproc tree-map-num-entries (tm::<tree-map>) ::<int>
703 (return (Scm_TreeCoreNumEntries (SCM_TREE_MAP_CORE tm))))
704
705 (select-module gauche.internal)
706 (define-cproc %tree-map-bound (tm::<tree-map> min::<boolean> pop::<boolean>)
707 (let* ([op::ScmTreeCoreBoundOp (?: min SCM_TREE_CORE_MIN SCM_TREE_CORE_MAX)]
708 [e::ScmDictEntry*
709 (?: pop
710 (Scm_TreeCorePopBound (SCM_TREE_MAP_CORE tm) op)
711 (Scm_TreeCoreGetBound (SCM_TREE_MAP_CORE tm) op))])
712 (if e
713 (return (Scm_Cons (SCM_DICT_KEY e) (SCM_DICT_VALUE e)))
714 (return '#f))))
715
716 (inline-stub
717 (define-cfn tree-map-iter (args::ScmObj* _::int data::void*) :static
718 (let* ([iter::ScmTreeIter* (cast ScmTreeIter* data)]
719 [e::ScmDictEntry* (?: (SCM_FALSEP (aref args 1))
720 (Scm_TreeIterNext iter)
721 (Scm_TreeIterPrev iter))])
722 (if (not e)
723 (return (values (aref args 0) (aref args 0)))
724 (return (values (SCM_DICT_KEY e) (SCM_DICT_VALUE e))))))
725 )
726
727 (select-module gauche.internal)
728 (define-cproc %tree-map-iter (tm::<tree-map>)
729 (let* ([iter::ScmTreeIter* (SCM_NEW ScmTreeIter)])
730 (Scm_TreeIterInit iter (SCM_TREE_MAP_CORE tm) NULL)
731 (return (Scm_MakeSubr tree_map_iter iter 2 0 '"tree-map-iterator"))))
732
733 (select-module gauche.internal)
734 (define-cproc %tree-map-check-consistency (tm::<tree-map>)
735 (Scm_TreeCoreCheckConsistency (SCM_TREE_MAP_CORE tm))
736 (return '#t))
737
738 (select-module gauche.internal)
739 (define-cproc %tree-map-dump (tm::<tree-map>) ::<void>
740 (Scm_TreeMapDump tm SCM_CUROUT))
741
742 (select-module gauche)
743 (define-cproc tree-map-clear! (tm::<tree-map>) ::<void>
744 (Scm_TreeCoreClear (SCM_TREE_MAP_CORE tm)))
745
746 (inline-stub
747 ;;
748 ;; Finds the entry closest to the given key
749 ;;
750 (define-cise-stmt tree-map-closest-entry
751 [(_ inclusive? lh make-result)
752 (if inclusive?
753 `(let* ([lo::ScmDictEntry* NULL]
754 [hi::ScmDictEntry* NULL]
755 [eq::ScmDictEntry*
756 (Scm_TreeCoreClosestEntries (SCM_TREE_MAP_CORE tm)
757 (cast intptr_t key)
758 (& lo) (& hi))])
759 (cond
760 [(!= eq NULL) (,make-result (SCM_DICT_KEY eq) (SCM_DICT_VALUE eq))]
761 [(!= ,lh NULL) (,make-result (SCM_DICT_KEY ,lh) (SCM_DICT_VALUE ,lh))]
762 [else (,make-result key-fb val-fb)]))
763 `(let* ([lo::ScmDictEntry* NULL]
764 [hi::ScmDictEntry* NULL])
765 (Scm_TreeCoreClosestEntries (SCM_TREE_MAP_CORE tm)
766 (cast intptr_t key)
767 (& lo) (& hi))
768 (if (!= ,lh NULL)
769 (,make-result (SCM_DICT_KEY ,lh) (SCM_DICT_VALUE ,lh))
770 (,make-result key-fb val-fb))))])
771
772 (define-cise-stmt tree-map-closest-key-result [(_ k v) `(return ,k)])
773 (define-cise-stmt tree-map-closest-val-result [(_ k v) `(return ,v)])
774 (define-cise-stmt tree-map-closest-kv-result [(_ k v) `(return ,k ,v)])
775 )
776
777 (define-cproc tree-map-floor
778 (tm::<tree-map> key :optional (key-fb #f) (val-fb #f)) ::(<top> <top>)
779 (tree-map-closest-entry #t lo tree-map-closest-kv-result))
780 (define-cproc tree-map-floor-key (tm::<tree-map> key :optional (key-fb #f))
781 (tree-map-closest-entry #t lo tree-map-closest-key-result))
782 (define-cproc tree-map-floor-value (tm::<tree-map> key :optional (val-fb #f))
783 (tree-map-closest-entry #t lo tree-map-closest-val-result))
784
785 (define-cproc tree-map-ceiling
786 (tm::<tree-map> key :optional (key-fb #f) (val-fb #f)) ::(<top> <top>)
787 (tree-map-closest-entry #t hi tree-map-closest-kv-result))
788 (define-cproc tree-map-ceiling-key (tm::<tree-map> key :optional (key-fb #f))
789 (tree-map-closest-entry #t hi tree-map-closest-key-result))
790 (define-cproc tree-map-ceiling-value (tm::<tree-map> key :optional (val-fb #f))
791 (tree-map-closest-entry #t hi tree-map-closest-val-result))
792
793 (define-cproc tree-map-predecessor
794 (tm::<tree-map> key :optional (key-fb #f) (val-fb #f)) ::(<top> <top>)
795 (tree-map-closest-entry #f lo tree-map-closest-kv-result))
796 (define-cproc tree-map-predecessor-key
797 (tm::<tree-map> key :optional (key-fb #f))
798 (tree-map-closest-entry #f lo tree-map-closest-key-result))
799 (define-cproc tree-map-predecessor-value
800 (tm::<tree-map> key :optional (val-fb #f))
801 (tree-map-closest-entry #f lo tree-map-closest-val-result))
802
803 (define-cproc tree-map-successor
804 (tm::<tree-map> key :optional (key-fb #f) (val-fb #f)) ::(<top> <top>)
805 (tree-map-closest-entry #f hi tree-map-closest-kv-result))
806 (define-cproc tree-map-successor-key
807 (tm::<tree-map> key :optional (key-fb #f))
808 (tree-map-closest-entry #f hi tree-map-closest-key-result))
809 (define-cproc tree-map-successor-value
810 (tm::<tree-map> key :optional (val-fb #f))
811 (tree-map-closest-entry #f hi tree-map-closest-val-result))