| 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)) |