| 1 |
;; ring-buffer |
| 2 |
|
| 3 |
(use gauche.test) |
| 4 |
(test-start "data.ring-buffer") |
| 5 |
(test-section "data.ring-buffer") |
| 6 |
(use data.ring-buffer) |
| 7 |
(test-module 'data.ring-buffer) |
| 8 |
(use gauche.sequence) |
| 9 |
(use gauche.uvector) |
| 10 |
(use scheme.list) |
| 11 |
|
| 12 |
|
| 13 |
(define (test-ring-buffer initial-storage) |
| 14 |
(define c (class-name (class-of initial-storage))) |
| 15 |
(define (remove-all-from-front rb) |
| 16 |
(unfold ring-buffer-empty? |
| 17 |
ring-buffer-remove-front! |
| 18 |
identity |
| 19 |
rb)) |
| 20 |
(define (remove-all-from-back rb) |
| 21 |
(unfold ring-buffer-empty? |
| 22 |
ring-buffer-remove-back! |
| 23 |
identity |
| 24 |
rb)) |
| 25 |
(define (test-add-remove n) |
| 26 |
(let1 rb (make-ring-buffer initial-storage) |
| 27 |
(test* #"add front - remove front (~c, ~n))" |
| 28 |
(reverse (iota n)) |
| 29 |
(begin |
| 30 |
(dotimes (i n) (ring-buffer-add-front! rb i)) |
| 31 |
(remove-all-from-front rb)))) |
| 32 |
(let1 rb (make-ring-buffer initial-storage) |
| 33 |
(test* #"add front - remove back (~c, ~n))" |
| 34 |
(iota n) |
| 35 |
(begin |
| 36 |
(dotimes (i n) (ring-buffer-add-front! rb i)) |
| 37 |
(remove-all-from-back rb)))) |
| 38 |
(let1 rb (make-ring-buffer initial-storage) |
| 39 |
(test* #"add back - remove front (~c, ~n))" |
| 40 |
(iota n) |
| 41 |
(begin |
| 42 |
(dotimes (i n) (ring-buffer-add-back! rb i)) |
| 43 |
(remove-all-from-front rb)))) |
| 44 |
(let1 rb (make-ring-buffer initial-storage) |
| 45 |
(test* #"add back - remove back (~c, ~n))" |
| 46 |
(reverse (iota n)) |
| 47 |
(begin |
| 48 |
(dotimes (i n) (ring-buffer-add-back! rb i)) |
| 49 |
(remove-all-from-back rb))))) |
| 50 |
|
| 51 |
(define (test-basic) |
| 52 |
(let1 rb (make-ring-buffer initial-storage) |
| 53 |
(test* #"empty (~c)" #t (ring-buffer-empty? rb)) |
| 54 |
(test* #"empty (~c)" 0 (ring-buffer-num-entries rb)) |
| 55 |
(test* #"initial (~c)" '(10 10 1 #f) |
| 56 |
(begin (ring-buffer-add-front! rb 10) |
| 57 |
(list (ring-buffer-front rb) |
| 58 |
(ring-buffer-back rb) |
| 59 |
(ring-buffer-num-entries rb) |
| 60 |
(ring-buffer-empty? rb)))) |
| 61 |
(test* #"2 elemenst (~c)" '(10 11 2 #f) |
| 62 |
(begin (ring-buffer-add-back! rb 11) |
| 63 |
(list (ring-buffer-front rb) |
| 64 |
(ring-buffer-back rb) |
| 65 |
(ring-buffer-num-entries rb) |
| 66 |
(ring-buffer-empty? rb)))) |
| 67 |
(test* "ring-buffer-room" (- (size-of initial-storage) 2) |
| 68 |
(ring-buffer-room rb)))) |
| 69 |
(define (test-overflow) |
| 70 |
(let1 rb (make-ring-buffer initial-storage :overflow-handler 'error) |
| 71 |
(test* #"overflow - error (~c)" (test-error) |
| 72 |
(dotimes [i (+ (size-of initial-storage) 1)] |
| 73 |
(ring-buffer-add-back! rb i)))) |
| 74 |
(let1 rb (make-ring-buffer initial-storage :overflow-handler 'overwrite) |
| 75 |
(test* #"overflow - overwrite forward (~c)" |
| 76 |
(iota (size-of initial-storage) |
| 77 |
(size-of initial-storage)) |
| 78 |
(begin |
| 79 |
(dotimes [i (* (size-of initial-storage) 2)] |
| 80 |
(ring-buffer-add-back! rb i)) |
| 81 |
(remove-all-from-front rb)))) |
| 82 |
(let1 rb (make-ring-buffer initial-storage :overflow-handler 'overwrite) |
| 83 |
(test* #"overflow - overwrite backward (~c)" |
| 84 |
(reverse (iota (size-of initial-storage) |
| 85 |
(size-of initial-storage))) |
| 86 |
(begin |
| 87 |
(dotimes [i (* (size-of initial-storage) 2)] |
| 88 |
(ring-buffer-add-front! rb i)) |
| 89 |
(remove-all-from-front rb))))) |
| 90 |
|
| 91 |
;; body of test-ring-buffer |
| 92 |
(test-basic) |
| 93 |
(test-overflow) |
| 94 |
(test-add-remove 3) |
| 95 |
(test-add-remove 12) ; causes realloc |
| 96 |
) |
| 97 |
|
| 98 |
(test-ring-buffer (make-vector 4)) |
| 99 |
(test-ring-buffer (make-u8vector 5)) |
| 100 |
|
| 101 |
;; ring-buffer->xvector |
| 102 |
(let ((buf (make-ring-buffer (make-u8vector 4)))) |
| 103 |
(test* "->xvector (empty)" '#u8() |
| 104 |
(ring-buffer->xvector buf)) |
| 105 |
(ring-buffer-add-back! buf 1) |
| 106 |
(test* "->xvector (1)" '#u8(1) |
| 107 |
(ring-buffer->xvector buf)) |
| 108 |
(ring-buffer-add-back! buf 2) |
| 109 |
(test* "->xvector (2)" '#u8(1 2) |
| 110 |
(ring-buffer->xvector buf)) |
| 111 |
(ring-buffer-add-back! buf 3) |
| 112 |
(test* "->xvector (3)" '#u8(1 2 3) |
| 113 |
(ring-buffer->xvector buf)) |
| 114 |
(test* "->xvector (3, range)" '#u8(2 3) |
| 115 |
(ring-buffer->xvector buf 1)) |
| 116 |
(test* "->xvector (3, range)" '#u8(2) |
| 117 |
(ring-buffer->xvector buf 1 2)) |
| 118 |
(ring-buffer-remove-front! buf) |
| 119 |
(ring-buffer-remove-front! buf) |
| 120 |
(test* "->xvector (-2)" '#u8(3) |
| 121 |
(ring-buffer->xvector buf)) |
| 122 |
(ring-buffer-add-back! buf 4) |
| 123 |
(ring-buffer-add-back! buf 5) |
| 124 |
(test* "->xvector (3)" '#u8(3 4 5) |
| 125 |
(ring-buffer->xvector buf)) |
| 126 |
(test* "->xvector (3, range)" '#u8(5) |
| 127 |
(ring-buffer->xvector buf 2)) |
| 128 |
(test* "->xvector (3, range)" '#u8(3 4) |
| 129 |
(ring-buffer->xvector buf 0 2)) |
| 130 |
(ring-buffer-remove-front! buf) |
| 131 |
(ring-buffer-remove-front! buf) |
| 132 |
(ring-buffer-remove-front! buf) |
| 133 |
(test* "->xvector (0)" '#u8() |
| 134 |
(ring-buffer->xvector buf)) |
| 135 |
) |
| 136 |
|
| 137 |
;; from the manual |
| 138 |
(let ((rb (make-ring-buffer (make-vector 4)))) |
| 139 |
(test* "->xvector (empty)" '#() |
| 140 |
(ring-buffer->xvector rb)) |
| 141 |
(ring-buffer-add-back! rb 'a) |
| 142 |
(ring-buffer-add-back! rb 'b) |
| 143 |
(ring-buffer-add-front! rb 'z) |
| 144 |
(ring-buffer-add-front! rb 'y) |
| 145 |
(test* "-> xvector (4)" '#(y z a b) |
| 146 |
(ring-buffer->xvector rb)) |
| 147 |
(test* "-> xvector (4, range)" '#(z a) |
| 148 |
(ring-buffer->xvector rb 1 3)) |
| 149 |
) |
| 150 |
|
| 151 |
;; test with initial data |
| 152 |
(let ((buf (make-ring-buffer (vector 'a 'b 'c 'd 'e) |
| 153 |
:initial-head-index 1 |
| 154 |
:initial-tail-index 5))) |
| 155 |
(test* "ring-buffer/initial" '(4 b e) |
| 156 |
(list (ring-buffer-num-entries buf) |
| 157 |
(ring-buffer-front buf) |
| 158 |
(ring-buffer-back buf))) |
| 159 |
(ring-buffer-add-back! buf 'f) |
| 160 |
(ring-buffer-add-front! buf 'z) |
| 161 |
(test* "ring-buffer/initial expand" '#(z b c d e f) |
| 162 |
(ring-buffer->xvector buf)) |
| 163 |
(ring-buffer-remove-front! buf) |
| 164 |
(ring-buffer-remove-front! buf) |
| 165 |
(ring-buffer-remove-front! buf) |
| 166 |
(ring-buffer-add-back! buf 'g) |
| 167 |
(ring-buffer-add-back! buf 'h) |
| 168 |
(ring-buffer-add-back! buf 'i) |
| 169 |
(ring-buffer-add-back! buf 'j) |
| 170 |
(ring-buffer-add-back! buf 'k) |
| 171 |
(ring-buffer-add-back! buf 'l) |
| 172 |
(ring-buffer-add-back! buf 'm) |
| 173 |
(test* "ring-buffer/initial expand" '#(d e f g h i j k l m) |
| 174 |
(ring-buffer->xvector buf)) |
| 175 |
|
| 176 |
(test* "ring-buffer-clear!" '#() |
| 177 |
(begin |
| 178 |
(ring-buffer-clear! buf) |
| 179 |
(ring-buffer->xvector buf))) |
| 180 |
|
| 181 |
(ring-buffer-add-front! buf 'A) |
| 182 |
(ring-buffer-add-front! buf 'B) |
| 183 |
(ring-buffer-add-back! buf 'Z) |
| 184 |
(test* "ring-buffer add after clear" '#(B A Z) |
| 185 |
(ring-buffer->xvector buf)) |
| 186 |
) |
| 187 |
|
| 188 |
;; flat vector fill |
| 189 |
(let ((buf (make-ring-buffer (make-s16vector 5)))) |
| 190 |
(ring-buffer-add-back! buf 1) |
| 191 |
(ring-buffer-add-back! buf 2) |
| 192 |
(ring-buffer-add-back! buf 3) |
| 193 |
(ring-buffer-add-back! buf 4) |
| 194 |
(ring-buffer-add-back! buf 5) |
| 195 |
(ring-buffer-remove-front! buf) |
| 196 |
(ring-buffer-remove-front! buf) |
| 197 |
(ring-buffer-add-back! buf 6) |
| 198 |
(ring-buffer-add-back! buf 7) |
| 199 |
|
| 200 |
(test* "ring-buffer->xvector!" |
| 201 |
'#s16(0 0 0 3 4 5 6 7 0 0) |
| 202 |
(rlet1 v (make-s16vector 10) |
| 203 |
(ring-buffer->xvector! v 3 buf))) |
| 204 |
(ring-buffer-add-front! buf -1) |
| 205 |
(ring-buffer-add-front! buf -2) |
| 206 |
(ring-buffer-add-front! buf -3) |
| 207 |
(test* "ring-buffer->xvector!" |
| 208 |
'#s16(-2 -1 3 4 5 0 0 0 0 0) |
| 209 |
(rlet1 v (make-s16vector 10) |
| 210 |
(ring-buffer->xvector! v 0 buf 1 6))) |
| 211 |
) |
| 212 |
|
| 213 |
;; insert |
| 214 |
(let ((buf (make-ring-buffer (make-vector 4) |
| 215 |
:room-maker (^[rb old size] (make-vector size))))) |
| 216 |
(ring-buffer-add-back! buf 'a) |
| 217 |
(ring-buffer-add-back! buf 'b) |
| 218 |
(ring-buffer-add-back! buf 'c) |
| 219 |
(ring-buffer-add-front! buf 'z) |
| 220 |
(test* "ring-buffer-insert-all!" |
| 221 |
'#(z a p q r b c) |
| 222 |
(begin |
| 223 |
(ring-buffer-insert-all! buf 2 '(p q r)) |
| 224 |
(ring-buffer->xvector buf))) |
| 225 |
(test* "ring-buffer-insert-all!" |
| 226 |
'#(z a p q r b c d e f g h i j k l m n o s t u v) |
| 227 |
(begin |
| 228 |
(ring-buffer-insert-all! buf 7 '#(d e f g h i j k l m n o s t u v)) |
| 229 |
(ring-buffer->xvector buf))) |
| 230 |
) |
| 231 |
|
| 232 |
;; sequence protocol |
| 233 |
(let ((buf (make-ring-buffer))) |
| 234 |
(ring-buffer-add-back! buf 'a) |
| 235 |
(ring-buffer-add-back! buf 'b) |
| 236 |
(ring-buffer-add-back! buf 'c) |
| 237 |
(ring-buffer-add-front! buf 'z) |
| 238 |
(ring-buffer-add-front! buf 'y) |
| 239 |
(ring-buffer-add-front! buf 'x) |
| 240 |
(test* "ring-buffer sequence protocol" '(x y z a b c) |
| 241 |
(coerce-to <list> buf))) |
| 242 |
|
| 243 |
(test-end) |