Debian Codegraph @

test/hash.scm

raw
1 ;;
2 ;; Test hash table
3 ;;
4
5 (use gauche.test)
6 (use scheme.list)
7 (use srfi.13)
8 (use gauche.uvector)
9
10 ;; Note: test/object.scm contains extra tests of hashtables using
11 ;; object-equal? and object-hash overload.
12
13 (test-start "hash tables")
14
15 ;;------------------------------------------------------------------
16 (test-section "hash function")
17
18 ;; Test portable hash function. We must guarantee hash values by
19 ;; portable-hash won't change.
20
21 (let ([data '((#f 3428989595 3428989595)
22 (#t 64744347 64744347)
23 (#\a 3754065427 3754065427)
24 (#\null 3668339987 3668339987)
25 (0 0 2654435761)
26 (1 2654435761 387276917)
27 (-1 2654435761 626627309)
28 (45174651375937459317569347657 3238994630 3238994630)
29 (1.1 324783707 2919879337)
30 (-1.1 1508195907 1375087959)
31 (3.767278962604361e-10 3208588342 0)
32 ;; NB: with old 'hash' code, the following was 0 on 8087
33 (3.767278962604362e-10 3983142176 1)
34 (3.767278962604363e-10 462728714 1)
35 (-3.767278962604361e-10 2477197406 0)
36 ;; NB: with old 'hash' code, the following was 0 on 8087
37 (-3.767278962604362e-10 3251751240 4294967295)
38 (-3.767278962604363e-10 4026305074 4294967295)
39 ;; NB: with old 'hash' code, this was 1981270711 on 8087
40 (3.474701543e9 3535247838 1981271040)
41 (3.474701544e9 3780614622 0)
42 (-3.474701544e9 3597766888 0)
43 (+inf.0 0 0)
44 (+nan.0 0 0)
45 (1/2 1401181143 1401181143)
46 (-5/4 3964193037 91423867)
47 (3.0+1.0i 2174816445 2027808452)
48 (() 995466395 995466395)
49 ((#f a 0) 590094886 509715512)
50 (#(#t :b 3.2) 2915469923 1522869008)
51 ("" 3183946422 0)
52 ("zye" 1276445264 121094)
53 (abc 4121390185 96354)
54 (:foo 696220911 101574))])
55 (test* "portable hash (new, legacy)" data
56 (map (^p (list (car p)
57 (portable-hash (car p) 0)
58 (hash (car p))))
59 data)))
60
61 ;; uvector hash support
62 (let ([data '((#u8() 1137702107 103389108)
63 (#s8() 3183946422 1028203680)
64 (#u16() 4026203278 2385671743)
65 (#s16() 521471644 3175907405)
66 (#u32() 2096652405 3737183940)
67 (#s32() 1176995887 2817527422)
68 (#u64() 3594299835 939864074)
69 (#s64() 4097263002 2456731467)
70 (#f16() 2577174380 936642845)
71 (#f32() 2264331153 3904862688)
72 (#f64() 404970645 2045502180)
73
74 (#u8(0) 2711902886 356952918)
75 (#s8(0) 241632508 3086832956)
76 (#u16(0) 2951147206 3338424123)
77 (#s16(0) 2607358220 2994635137)
78 (#u32(0) 1893327433 1506050516)
79 (#s32(0) 1590012139 1202735222)
80 (#u64(0) 791629991 404353074)
81 (#s64(0) 3306445826 3693722743)
82 (#f16(0) 970012 388246929)
83 (#f32(0) 2731721173 2344444256)
84 (#f64(0) 3019130455 2631853538)
85
86 (#u8(1) 253287183 824885740)
87 (#s8(1) 312535652 1326439597)
88 (#u16(1) 1310615671 1697892588)
89 (#s16(1) 966826685 1354103602)
90 (#u32(1) 252795898 4160486277)
91 (#s32(1) 4244447900 3857170983)
92 (#u64(1) 3446065752 3058788835)
93 (#s64(1) 1665914291 2053191208)
94 (#f16(1) 9718044 396994961)
95 (#f32(1) 173195733 4080886112)
96 (#f64(1) 1555830517 1168553600)
97
98 (#u8(1 2 3) 241852752 4262278780)
99 (#s8(1 2 3) 3864380406 3888224286)
100 (#u16(1 2 3) 2848547228 3940535561)
101 (#s16(1 2 3) 2843757170 3935745503)
102 (#u32(1 2 3) 2172856679 1080868346)
103 (#s32(1 2 3) 3179908921 2087920588)
104 (#u64(1 2 3) 400224405 3603203368)
105 (#s64(1 2 3) 3141078136 4233066469)
106 (#f16(1 2 3) 3019376060 4111364393)
107 (#f32(1 2 3) 3998543309 2906554976)
108 (#f64(1 2 3) 529975387 3732954350)
109 )])
110 (dolist [d data]
111 (test* #"portable hash uvector ~(car d)" d
112 (list (car d)
113 (portable-hash (car d) 0)
114 (portable-hash (car d) 1)))))
115
116 ;;------------------------------------------------------------------
117 (test-section "eq?-hash")
118
119 (define h-eq (make-hash-table))
120
121 (test* "make-hash-table" #t
122 (hash-table? h-eq))
123
124 (test* "hash-table-type" 'eq?
125 (hash-table-type h-eq))
126
127 (test* "a => 8" 8
128 (begin
129 (hash-table-put! h-eq 'a 8)
130 (hash-table-get h-eq 'a)))
131
132 (test* "a adjoin" 8
133 (begin
134 (hash-table-adjoin! h-eq 'a 9)
135 (hash-table-get h-eq 'a)))
136
137 (test* "a replace" 7
138 (begin
139 (hash-table-replace! h-eq 'a 7)
140 (hash-table-get h-eq 'a)))
141
142 (test* "b => non" #t
143 (hash-table-get h-eq 'b #t))
144
145 (test* "b => error" (test-error)
146 (hash-table-get h-eq 'b))
147
148 (test* "b replace" #f
149 (begin
150 (hash-table-replace! h-eq 'b 100)
151 (hash-table-get h-eq 'b #f)))
152
153 (test* "b => \"b\"" "b"
154 (begin
155 (hash-table-put! h-eq 'b "b")
156 (hash-table-get h-eq 'b)))
157
158 (test* "c => #\C" #\C
159 (begin
160 (hash-table-put! h-eq 'c #\C)
161 (hash-table-get h-eq 'c)))
162
163 (test* "c => #\c" #\c
164 (begin
165 (hash-table-put! h-eq 'c #\c)
166 (hash-table-get h-eq 'c)))
167
168 (test* "d adjoin" "D"
169 (begin
170 (hash-table-adjoin! h-eq 'd "D")
171 (hash-table-adjoin! h-eq 'd "d")
172 (hash-table-get h-eq 'd)))
173
174 (test* "e => 10" 10
175 (begin
176 (hash-table-put! h-eq 'e 8)
177 (hash-table-update! h-eq 'e (^x (+ x 1)))
178 (hash-table-update! h-eq 'e (^x (+ x 1)))
179 (hash-table-get h-eq 'e)))
180
181 (test* "f => 1" 3
182 (begin
183 (hash-table-update! h-eq 'f (^x (+ x 1)) 2)
184 (hash-table-get h-eq 'f)))
185
186 (test* "eq? test" 8
187 (begin
188 (hash-table-put! h-eq (string #\d) 4)
189 (hash-table-put! h-eq (string #\d) 5)
190 (length (hash-table-keys h-eq))))
191
192 (test* "hash-table-values(1)" #t
193 (lset= equal? (hash-table-values h-eq) '(7 "b" #\c "D" 3 4 5 10)))
194
195 (test* "delete!" '(#t #f #f)
196 (let* ((a (hash-table-delete! h-eq 'c))
197 (b (hash-table-delete! h-eq 'c)))
198 (list a b (hash-table-get h-eq 'c #f))))
199
200 (test* "clear!" '()
201 (begin (hash-table-clear! h-eq)
202 (hash-table-keys h-eq)))
203
204 ;;------------------------------------------------------------------
205 (test-section "eqv?-hash")
206
207 (define h-eqv (make-hash-table 'eqv?))
208
209 (test* "make-hash-table" #t
210 (hash-table? h-eqv))
211
212 (test* "hash-table-type" 'eqv?
213 (hash-table-type h-eqv))
214
215 (test* "a => 8" 8
216 (begin
217 (hash-table-put! h-eqv 'a 8)
218 (hash-table-get h-eqv 'a)))
219
220 (test* "b => non" #t
221 (hash-table-get h-eqv 'b #t))
222
223 (test* "b => error" (test-error)
224 (hash-table-get h-eqv 'b))
225
226 (test* "b => \"b\"" "b"
227 (begin
228 (hash-table-put! h-eqv 'b "b")
229 (hash-table-get h-eqv 'b)))
230
231 (test* "2.0 => #\C" #\C
232 (begin
233 (hash-table-put! h-eqv 2.0 #\C)
234 (hash-table-get h-eqv 2.0)))
235
236 (test* "2.0 => #\c" #\c
237 (begin
238 (hash-table-put! h-eqv 2.0 #\c)
239 (hash-table-get h-eqv 2.0)))
240
241
242 (test* "87592876592374659237845692374523694756 => 0" 0
243 (begin
244 (hash-table-put! h-eqv 87592876592374659237845692374523694756 0)
245 (hash-table-get h-eqv 87592876592374659237845692374523694756)))
246
247 (test* "87592876592374659237845692374523694756 => -1" -1
248 (begin
249 (hash-table-put! h-eqv 87592876592374659237845692374523694756 -1)
250 (hash-table-get h-eqv 87592876592374659237845692374523694756)))
251
252 (test* "377/120 => pi" 'pi
253 (begin
254 (hash-table-put! h-eqv 377/120 'pi)
255 (hash-table-get h-eqv 377/120)))
256
257 (test* "377/120 => PI" 'PI
258 (begin
259 (hash-table-put! h-eqv 377/120 'PI)
260 (hash-table-get h-eqv 377/120)))
261
262 (test* "eqv? test" 7
263 (begin
264 (hash-table-put! h-eqv (string #\d) 4)
265 (hash-table-put! h-eqv (string #\d) 5)
266 (length (hash-table-keys h-eqv))))
267
268 (test* "hash-table-values(2)" #t
269 (lset= equal? (hash-table-values h-eqv) '(8 "b" #\c -1 4 5 PI)))
270
271 (define h-eqv-copied (hash-table-copy h-eqv))
272
273 (test* "delete!" #f
274 (begin
275 (hash-table-delete! h-eqv 87592876592374659237845692374523694756)
276 (hash-table-get h-eqv 87592876592374659237845692374523694756 #f)))
277
278 (test* "copy" #t
279 (lset= equal? (hash-table-values h-eqv-copied) '(8 "b" #\c -1 4 5 PI)))
280
281 ;;------------------------------------------------------------------
282 (test-section "equal?-hash")
283
284 (define h-equal (make-hash-table 'equal?))
285
286 (test* "make-hash-table" #t
287 (hash-table? h-equal))
288
289 (test* "hash-table-type" 'equal?
290 (hash-table-type h-equal))
291
292 (test* "a => 8" 8
293 (begin
294 (hash-table-put! h-equal 'a 8)
295 (hash-table-get h-equal 'a)))
296
297 (test* "b => non" #t
298 (hash-table-get h-equal 'b #t))
299
300 (test* "b => error" (test-error)
301 (hash-table-get h-equal 'b))
302
303 (test* "b => \"b\"" "b"
304 (begin
305 (hash-table-put! h-equal 'b "b")
306 (hash-table-get h-equal 'b)))
307
308 (test* "2.0 => #\C" #\C
309 (begin
310 (hash-table-put! h-equal 2.0 #\C)
311 (hash-table-get h-equal 2.0)))
312
313 (test* "2.0 => #\c" #\c
314 (begin
315 (hash-table-put! h-equal 2.0 #\c)
316 (hash-table-get h-equal 2.0)))
317
318 (test* "87592876592374659237845692374523694756 => 0" 0
319 (begin
320 (hash-table-put! h-equal 87592876592374659237845692374523694756 0)
321 (hash-table-get h-equal 87592876592374659237845692374523694756)))
322
323 (test* "87592876592374659237845692374523694756 => -1" -1
324 (begin
325 (hash-table-put! h-equal 87592876592374659237845692374523694756 -1)
326 (hash-table-get h-equal 87592876592374659237845692374523694756)))
327
328 (test* "e => \"e\"" "E"
329 (begin
330 (hash-table-put! h-equal 'e "e")
331 (hash-table-update! h-equal 'e (^x (string-upcase x)))
332 (hash-table-get h-equal 'e)))
333
334 (test* "equal? test" 6
335 (begin
336 (hash-table-put! h-equal (string #\d) 4)
337 (hash-table-put! h-equal (string #\d) 5)
338 (length (hash-table-keys h-equal))))
339
340 (test* "equal? test" 7
341 (begin
342 (hash-table-put! h-equal (cons 'a 'b) 6)
343 (hash-table-put! h-equal (cons 'a 'b) 7)
344 (length (hash-table-keys h-equal))))
345
346 (test* "equal? test" 8
347 (begin
348 (hash-table-put! h-equal (vector (cons 'a 'b) 3+3i) 60)
349 (hash-table-put! h-equal (vector (cons 'a 'b) 3+3i) 61)
350 (length (hash-table-keys h-equal))))
351
352 ;; u8vector hash support
353 (test* "equal? test" 9
354 (begin
355 (hash-table-put! h-equal (u8vector (char->integer #\d)) 70)
356 (hash-table-put! h-equal (u8vector (char->integer #\d)) 71)
357 (length (hash-table-keys h-equal))))
358
359 (test* "hash-table-values(3)" #t
360 (lset= equal? (hash-table-values h-equal) '(8 "b" #\c -1 "E" 5 7 61 71)))
361
362 (test* "delete!" #f
363 (begin
364 (hash-table-delete! h-equal (vector (cons 'a 'b) 3+3i))
365 (hash-table-get h-equal (vector (cons 'a 'b) 3+3i) #f)))
366
367 ;;------------------------------------------------------------------
368 (test-section "string?-hash")
369
370 (define h-string (make-hash-table 'string=?))
371
372 (test* "make-hash-table" #t
373 (hash-table? h-string))
374
375 (test* "hash-table-type" 'string=?
376 (hash-table-type h-string))
377
378 (test* "\"a\" => 8" 8
379 (begin
380 (hash-table-put! h-string "a" 8)
381 (hash-table-get h-string "a")))
382
383 (test* "\"b\" => non" #t
384 (hash-table-get h-string "b" #t))
385
386 (test* "\"b\" => non" (test-error)
387 (hash-table-get h-string "b"))
388
389 (test* "\"b\" => \"b\"" "b"
390 (begin
391 (hash-table-put! h-string "b" "b")
392 (hash-table-get h-string "b")))
393
394 (test* "string=? test" 3
395 (begin
396 (hash-table-put! h-string (string #\d) 4)
397 (hash-table-put! h-string (string #\d) 5)
398 (length (hash-table-keys h-string))))
399
400 (test* "\"e\" => 9" 9
401 (begin
402 (hash-table-put! h-string "e" 8)
403 (hash-table-update! h-string "e" (^x (+ x 1)))
404 (hash-table-get h-string "e")))
405
406 (test* "hash-table-values(4)" #t
407 (lset= equal? (hash-table-values h-string) '(8 "b" 5 9)))
408
409 (test* "delete!" #f
410 (begin
411 (hash-table-delete! h-string "d")
412 (hash-table-get h-string "d" #f)))
413
414 ;;------------------------------------------------------------------
415 (test-section "generic hash")
416
417 (let* ([c (make-comparator (^x (and (integer? x) (<= 0 x 255)))
418 (^[a b] (= (modulo a 13) (modulo b 13)))
419 #f
420 (^x (eqv-hash (modulo x 13))))]
421 [h (make-hash-table c)])
422 (test* "construction" 'general (hash-table-type h))
423 (test* "retrieve comparator" c (hash-table-comparator h))
424 (test* "nonexistent" #f (hash-table-exists? h 0))
425 (test* "domain error 1" (test-error) (hash-table-exists? h 'a))
426 (test* "domain error 2" (test-error) (hash-table-exists? h -1))
427 (test* "put/get" 'a
428 (begin (hash-table-put! h 1 'a)
429 (hash-table-get h 1)))
430 (test* "hash and equality check" '(#t a)
431 (list (hash-table-exists? h 14)
432 (hash-table-get h 27)))
433 (test* "hash and equality check 2" 'b
434 (begin (hash-table-put! h 40 'b)
435 (hash-table-get h 1)))
436 (test* "hash and equality check 3"
437 '((0 . 247) (1 . 248) (2 . 249) (3 . 250) (4 . 251)
438 (5 . 252) (6 . 253) (7 . 254) (8 . 255) (9 . 243)
439 (10 . 244) (11 . 245) (12 . 246))
440 (begin
441 (dotimes [n 256]
442 (hash-table-put! h n n))
443 (sort-by (hash-table->alist h) car)))
444 )
445
446 (let ([x `((eq? . ,eq-comparator)
447 (eqv? . ,eqv-comparator)
448 (equal? . ,equal-comparator)
449 (string=? . ,string-comparator))])
450 (test* "recognizing special comparators"
451 (map car x)
452 (map (^p (hash-table-type (make-hash-table (cdr p)))) x))
453 (test* "retrieving comparators"
454 (map cdr x)
455 (map (^p (hash-table-comparator (make-hash-table (car p)))) x)))
456
457 ;;------------------------------------------------------------------
458 (test-section "hash-table-copy & rehash")
459
460 ;; https://github.com/shirok/Gauche/issues/400
461
462 (test* "hash-table-copy & rehash" #t
463 (let1 h (fold (^[n h] (rlet1 h (hash-table-copy h)
464 (hash-table-put! h n 1) h))
465 (make-hash-table 'eqv?)
466 (iota 20))
467 (every (cut hash-table-contains? h <> ) (iota 20))))
468
469 ;;------------------------------------------------------------------
470 (test-section "iterators")
471
472 (define h-it (hash-table-from-pairs 'eq?
473 '(a . 3)
474 '(c . 8)
475 '(b . 4)
476 '(d . 10)))
477
478 (test* "hash-table"
479 '(a b c d)
480 (hash-table-keys h-it)
481 (^[a b] (lset= equal? a b)))
482
483 (test* "hash-table-map"
484 '((a . 3) (b . 4) (c . 8) (d . 10))
485 (hash-table-map h-it cons)
486 (^[a b] (lset= equal? a b)))
487
488 (test* "hash-table-for-each"
489 '((a . 3) (b . 4) (c . 8) (d . 10))
490 (let ((r '()))
491 (hash-table-for-each h-it (^[k v] (push! r (cons k v))))
492 r)
493 (^[a b] (lset= equal? a b)))
494
495 (test* "hash-table-fold"
496 '((a . 3) (b . 4) (c . 8) (d . 10))
497 (hash-table-fold h-it acons '())
498 (^[a b] (lset= equal? a b)))
499
500 (test* "alist->hash-table" '(a b)
501 (let1 ht (alist->hash-table '((5 . b) (3 . a)) 'eqv?)
502 (list (hash-table-get ht 3)
503 (hash-table-get ht 5))))
504 (test* "hash-table->alist" '(("a" . 3) ("b" . 5))
505 (let1 a (hash-table->alist
506 (hash-table 'equal? '("a" . 3) '("b" . 5)))
507 (list (assoc "a" a)
508 (assoc "b" a))))
509
510 (test* "hash-table-find" 16
511 (hash-table-find h-it (^[k v] (and (eq? k 'c) (* v 2)))))
512
513 (test* "hash-table-find" 'oops
514 (hash-table-find h-it (^[k v] (and (eq? k 'e) (* v 2)))
515 (^[] 'oops)))
516
517 ;;------------------------------------------------------------------
518 (test-section "compare as sets")
519
520 (let ([a (hash-table-r7 eq-comparator 'a 1)]
521 [b (hash-table-r7 eq-comparator 'a 1 'b 2)]
522 [c (hash-table-r7 eq-comparator 'a 1 'b 2 'c 3)]
523 [d (hash-table-r7 eq-comparator 'a 1 'b 2 'c -3)]
524 [e (hash-table-r7 eq-comparator 'a 1 'e 2)]
525 [f (hash-table-r7 eq-comparator 'a 1 'b 2 'c 3 'e 2)]
526 [g (hash-table-r7 eq-comparator 'a 1 'b 2 'c 3)])
527 (define (inv a) (and a (- a)))
528 (define-syntax D
529 (syntax-rules ()
530 ([_ x y expected] `(,x ,y x y ,expected))))
531 (define data
532 (list (D a b -1)
533 (D a c -1)
534 (D b c -1)
535 (D b d -1)
536 (D b e #f)
537 (D c d #f)
538 (D c e #f)
539 (D d e #f)
540 (D e f -1)
541 (D c g 0)))
542
543 (dolist [d data]
544 (receive (x y xname yname expected) (apply values d)
545 (test* "hash-table-compare-as-sets"
546 `((,xname ,yname ,expected)
547 (,yname ,xname ,(and expected (- expected))))
548 (list
549 `(,xname ,yname ,(hash-table-compare-as-sets x y eqv? #f))
550 `(,yname ,xname ,(hash-table-compare-as-sets y x eqv? #f))))))
551
552 (test* "hash-table=? c d" #f
553 (hash-table=? eqv-comparator c d))
554 (test* "hash-table=? c g" #t
555 (hash-table=? eqv-comparator c g))
556 (test* "hash-table=? c c" #t
557 (hash-table=? eqv-comparator c c))
558 (test* "hash-table=? f a" #f
559 (hash-table=? eqv-comparator f a))
560 (test* "hash-table=? c d (custom compar)" #t
561 (hash-table=? (make-comparator number? (^[a b] (= (abs a) (abs b)))
562 #f #f)
563 c d)))
564
565 (test-end)