Debian Codegraph @

lib/scheme/hash-table.scm

raw
1 ;;;
2 ;;; scheme.hash-table - intermediate hash tables (R7RS Red)
3 ;;;
4 ;;; Copyright (c) 2017-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 ;; Originally SRFI-125.
35
36 ;; Most of procedures are built-in, though some of them have different names
37 ;; to avoid conflict with traditional Gauche procedures.
38
39 (define-module scheme.hash-table
40 (use gauche.hashutil)
41 (export make-hash-table ; extended for compatibility
42 hash-table ; extended for compatibility
43 hash-table-unfold ; extended for compatibility
44 alist->hash-table ; extended for compatibility
45
46 hash-table? ; builtin
47 hash-table-contains? ; builtin
48 hash-table-exists? ; builtin
49 hash-table-empty? ; builtin
50 hash-table=? ; builtin
51 hash-table-mutable? ; builtin
52
53 hash-table-ref ; builtin
54 hash-table-ref/default ; builtin
55
56 hash-table-set! ; builtin
57 (rename hash-table-delete!-r7 hash-table-delete!) ; builtin
58 (rename hash-table-intern!-r7 hash-table-intern!) ; builtin
59 (rename hash-table-update!-r7 hash-table-update!) ; builtin
60 hash-table-update!/default ; builtin
61 (rename hash-table-pop!-r7 hash-table-pop!) ; builtin
62 hash-table-clear! ; builtin
63
64 hash-table-size ; builtin
65 hash-table-keys ; builtin
66 hash-table-values ; builtin
67 hash-table-entries ; builtin
68 (rename hash-table-find-r7 hash-table-find) ; builtin
69 (rename hash-table-count-r7 hash-table-count) ; builtin
70
71 (rename hash-table-map-r7 hash-table-map) ; builtin
72 (rename hash-table-for-each-r7 hash-table-for-each) ; builtin
73 hash-table-walk ; compatibility
74 (rename hash-table-map!-r7 hash-table-map!) ; builtin
75 (rename hash-table-map->list-r7 hash-table-map->list) ; builtin
76 hash-table-fold ; extended for compatibility
77 (rename hash-table-prune!-r7 hash-table-prune!) ; builtin
78
79 hash-table-copy ; builtin
80 hash-table-empty-copy ; builtin
81 hash-table->alist ; builtin
82
83 hash-table-union! ; builtin
84 hash-table-merge! ; compatibility
85 hash-table-intersection! ; builtin
86 hash-table-difference! ; builtin
87 hash-table-xor! ; builtin
88
89 hash ; compatibility
90 string-hash ; compatibility
91 string-ci-hash ; compatibility
92 hash-by-identity ; compatibility
93 hash-table-equivalence-function ; compatibility
94 hash-table-hash-function ; compatibility
95 ))
96 (select-module scheme.hash-table)
97
98 ;; SRFI-69 compatibility layer
99
100 (define %make-hash-table (with-module gauche make-hash-table))
101 (define %alist->hash-table (with-module gauche alist->hash-table))
102
103 (define (%eq-fn->comparator eq-fn)
104 (cond [(eq? eq-fn eq?) eq-comparator]
105 [(eq? eq-fn eqv?) eqv-comparator]
106 [(eq? eq-fn equal?) equal-comparator]
107 [(eq? eq-fn string=?) string-comparator]
108 [(eq? eq-fn string-ci=?) string-ci-comparator]
109 [else (make-comparator #t eq-fn #f default-hash)]))
110
111 (define (make-hash-table cmpr . args)
112 (if (procedure? cmpr) ; SRFI-69
113 (if (and (pair? args) (procedure? (car args)))
114 (%make-hash-table (make-comparator #t cmpr #f (car args)))
115 (%make-hash-table (%eq-fn->comparator cmpr)))
116 (%make-hash-table cmpr)))
117
118 (define (hash-table cmpr . kvs)
119 (cond [(comparator? cmpr) (apply hash-table-r7 cmpr kvs)]
120 [(procedure? cmpr)
121 (if (pair? kvs)
122 (apply hash-table-r7 (make-comparator #t cmpr #f (cadr kvs))
123 (cdr kvs))
124 (error "missing hash function in hash-table (SRFI-69 compatibility):"
125 (list 'hash-table cmpr)))]
126 [else (error "comparator or procedure expected, but got:" cmpr)]))
127
128 (define (alist->hash-table alist cmpr . args)
129 ;; ignore args
130 (cond [(comparator? cmpr) (%alist->hash-table alist cmpr)]
131 [(procedure? cmpr)
132 ;; SRFI-69 compatibility
133 (if (null? args)
134 (%alist->hash-table alist (%eq-fn->comparator cmpr))
135 (let* ([eq-proc cmpr]
136 [hash-proc (car args)])
137 (%alist->hash-table alist
138 (make-comparator #t eq-proc #f hash-proc))))]
139 [else (error "comparator or procedure expected, but got:" cmpr)]))
140
141 (define (hash-table-unfold p f g seed cmpr . args)
142 ;; ignore args
143 ((with-module gauche hash-table-unfold) p f g seed cmpr))
144
145 (define (hash-table-walk ht proc) (hash-table-for-each ht proc))
146
147 (define (hash-table-fold proc seed ht)
148 (if (hash-table? proc)
149 ((with-module gauche hash-table-fold) proc seed ht)
150 (hash-table-fold-r7 proc seed ht)))
151
152 (define (hash-table-merge! ht1 ht2) (hash-table-union! ht1 ht2))
153
154 (define (hash obj :optional ignore)
155 (warn "SRFI-69 `hash' is deprecated. Use `default-hash' instead.")
156 (default-hash obj))
157 (define (string-hash obj :optional ignore)
158 ((with-module gauche string-hash) obj))
159 (define (string-ci-hash obj :optional ignore)
160 ((with-module gauche string-ci-hash) obj))
161 (define (hash-by-identity obj :optional ignore)
162 (warn "SRFI-69 `hash-by-identity' is deprecated and does not work compatible way with Gauche's eq-hash.")
163 (default-hash obj))
164
165 (define (hash-table-equivalence-function ht)
166 (assume-type ht <hash-table>)
167 (comparator-equality-predicate (hash-table-comparator ht)))
168 (define (hash-table-hash-function ht)
169 (assume-type ht <hash-table>)
170 (let1 h (comparator-hash-function (hash-table-comparator ht))
171 (if (eqv? (arity h) 1)
172 (^[obj :optional (bound #f)]
173 (if bound (modulo (h obj) bound) (h obj)))
174 h)))