Debian Codegraph @

libsrc/data/ring-buffer.scm

raw
1 ;;;
2 ;;; data.ring-buffer - Ring buffers
3 ;;;
4 ;;; Copyright (c) 2015-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 ;; NB: This module is loaded for REPL with input editing, so mind the
35 ;; loading time.
36
37 (define-module data.ring-buffer
38 (use gauche.sequence)
39 (use gauche.uvector)
40 (use gauche.record)
41 (use scheme.vector)
42 (use util.match)
43 (export make-ring-buffer
44 make-overflow-doubler
45 ring-buffer?
46 ring-buffer-empty? ring-buffer-full?
47 ring-buffer-num-entries ring-buffer-capacity ring-buffer-room
48 ring-buffer-front ring-buffer-back
49 ring-buffer-add-front! ring-buffer-add-back!
50 ring-buffer-remove-front! ring-buffer-remove-back!
51 ring-buffer-ref ring-buffer-set!
52 ring-buffer-insert-all!
53 ring-buffer-clear!
54
55 ring-buffer->xsubvectors
56 ring-buffer->xvector ring-buffer->xvector!))
57 (select-module data.ring-buffer)
58
59 ;;
60 ;; +-----------+ +-----------+
61 ;; | (vacant) | |///////////|
62 ;; | | |///////////|
63 ;; +-----------+ |///////////|
64 ;; head >|///////////| +-----------+
65 ;; |///////////| tail >| (vacant) |
66 ;; |///////////| | |
67 ;; |///////////| | |
68 ;; +-----------+ | |
69 ;; tail >| (vacant) | +-----------+
70 ;; | | head >|///////////|
71 ;; +-----------+ +-----------+ < capacity
72
73 ;; Although we define ring-buffer as a record-type, we don't export
74 ;; accessors/constructors. Users of this module should use exported
75 ;; public APIs.
76 ;;
77 ;; Originally, ring-buffer is only supposed to grow by one item
78 ;; at a time, so overflow-handler only needs to expand a storage at least one.
79 ;; However, we decdied to use ring-buffer as a basis of flexvector (SRFI-214)
80 ;; and needs some additional features, including the ability to extend
81 ;; the storage in arbitrary length. We think it is slightly out-of-scope
82 ;; as a feature of a ring-buffer, so for now we keep it unofficial.
83
84 (define-record-type (ring-buffer <record> :mixins (<sequence>))
85 %make-ring-buffer ring-buffer?
86 (storage)
87 overflow-handler
88 room-maker ;only used by ring-buffer-insert-all!
89 (head)
90 (tail)
91 (capacity)
92 (num-entries))
93
94 ;; ref/set! dispatcher
95 ;; We avoid using generic dispatch of '~', for ring buffers
96 ;; may be used in speed-conscious/allocation-conscious situation.
97 ;; It is kind of dumb that we have to roll our own dispatcher, though;
98 ;; there should be a built-in support.
99 (define *dispatch-table*
100 ($ hash-table 'eq?
101 `(,<vector> ,vector-length ,vector-ref ,vector-set!
102 ,make-vector . ,vector-copy!)
103 `(,<u8vector> ,uvector-length ,u8vector-ref ,u8vector-set!
104 ,make-u8vector . ,uvector-copy!)
105 `(,<s8vector> ,uvector-length ,s8vector-ref ,s8vector-set!
106 ,make-s8vector . ,uvector-copy!)
107 `(,<u16vector> ,uvector-length ,u16vector-ref ,u16vector-set!
108 ,make-u16vector . ,uvector-copy!)
109 `(,<s16vector> ,uvector-length ,s16vector-ref ,s16vector-set!
110 ,make-s16vector . ,uvector-copy!)
111 `(,<u32vector> ,uvector-length ,u32vector-ref ,u32vector-set!
112 ,make-u32vector . ,uvector-copy!)
113 `(,<s32vector> ,uvector-length ,s32vector-ref ,s32vector-set!
114 ,make-s32vector . ,uvector-copy!)
115 `(,<u64vector> ,uvector-length ,u64vector-ref ,u64vector-set!
116 ,make-u64vector . ,uvector-copy!)
117 `(,<s64vector> ,uvector-length ,s64vector-ref ,s64vector-set!
118 ,make-s64vector . ,uvector-copy!)
119 `(,<f16vector> ,uvector-length ,f16vector-ref ,f16vector-set!
120 ,make-f16vector . ,uvector-copy!)
121 `(,<f32vector> ,uvector-length ,f32vector-ref ,f32vector-set!
122 ,make-f32vector . ,uvector-copy!)
123 `(,<f64vector> ,uvector-length ,f64vector-ref ,f64vector-set!
124 ,make-f64vector . ,uvector-copy!)
125 ))
126
127 ;; dprocs is (<length> <ref> <set!> <alloc> . <copy!>)
128 (define-inline (%dprocs storage)
129 (hash-table-get *dispatch-table* (class-of storage)))
130
131 (define-inline (%rb-size dprocs storage)
132 ((car dprocs) storage))
133
134 (define-inline (%rb-mod-index dprocs storage index)
135 (modulo index (%rb-size dprocs storage)))
136
137 (define-inline (%rb-ref dprocs storage index)
138 ((cadr dprocs) storage index))
139
140 (define-inline (%rb-ref-1 dprocs storage index)
141 ((cadr dprocs) storage (%rb-mod-index dprocs storage (- index 1))))
142
143 (define-inline (%rb-set! dprocs storage index val)
144 ((caddr dprocs) storage index val))
145
146 (define-inline (%rb-alloc dprocs size)
147 ((cadddr dprocs) size))
148
149 (define-inline (%rb-copy! dprocs dest dstart src sstart send)
150 ((cddddr dprocs) dest dstart src sstart send))
151
152 (define (%rb-copy-contents! rb newvec oldvec)
153 (let1 dprocs (%dprocs oldvec)
154 (let ([h (ring-buffer-head rb)]
155 [t (ring-buffer-tail rb)])
156 (if (<= t h)
157 (let1 c (ring-buffer-capacity rb)
158 (%rb-copy! dprocs newvec 0 oldvec h c)
159 (%rb-copy! dprocs newvec (- c h) oldvec 0 t))
160 (%rb-copy! dprocs newvec 0 oldvec h t)))))
161
162 (define-inline (%rb-head-inc! rb dprocs storage delta)
163 ($ ring-buffer-head-set! rb
164 (%rb-mod-index dprocs (ring-buffer-storage rb)
165 (+ (ring-buffer-head rb) delta))))
166
167 (define-inline (%rb-tail-inc! rb dprocs storage delta)
168 ($ ring-buffer-tail-set! rb
169 (%rb-mod-index dprocs (ring-buffer-storage rb)
170 (+ (ring-buffer-tail rb) delta))))
171
172 ;; predefined overflow handlers
173 (define (overflow-error rb v) 'error)
174 (define (overflow-overwrite rb v) 'overwrite)
175
176 ;; API
177 (define (make-overflow-doubler :key (max-increase +inf.0)
178 (max-capacity +inf.0))
179 (^[rb v]
180 (let1 size (ring-buffer-capacity rb)
181 (cond [(>= size max-capacity) 'error]
182 [(>= size max-increase)
183 (%rb-alloc (%dprocs v) (+ size max-increase))]
184 [else
185 (%rb-alloc (%dprocs v) (* size 2))]))))
186
187 ;; API
188 ;; make-ring-buffer
189 ;; Returns a ring buffer.
190 ;; STORAGE can be vector-like objects.
191 ;; OVERFLOW-HANDLER must be a procedure that takes ring buffer instance
192 ;; and the current backing storage. It can perform one of the following
193 ;; ops.
194 ;;
195 ;; Returns 'error - causes the API to throws an error
196 ;; Returns 'overwrite - overwrite existing entries.
197 ;; Allocates larger backing storage
198 (define (make-ring-buffer :optional (storage (make-vector 4))
199 :key (overflow-handler (make-overflow-doubler))
200 (room-maker #f)
201 (initial-head-index 0)
202 (initial-tail-index 0))
203 (assume (exact-integer? initial-head-index))
204 (assume (exact-integer? initial-tail-index))
205 (assume (or (vector? storage) (uvector? storage))
206 "Ring buffer storage must be a vector-like object, but got:" storage)
207 (assume (<= 0 initial-head-index (- (size-of storage) 1))
208 "initial-head-index out of range:" initial-head-index)
209 (assume (<= initial-head-index initial-tail-index (size-of storage))
210 "initial-tail-index out of range:" initial-tail-index)
211 (let1 ov-handler
212 (case overflow-handler
213 [(error) overflow-error]
214 [(overwrite) overflow-overwrite]
215 [else (unless (applicable? overflow-handler ring-buffer <top>)
216 (error "overflow-handler must be a procedure, or \
217 a symbol error of overwrite, but got"
218 overflow-handler))
219 overflow-handler])
220 (%make-ring-buffer storage ov-handler room-maker
221 initial-head-index
222 (modulo initial-tail-index (size-of storage))
223 (size-of storage)
224 (- initial-tail-index initial-head-index))))
225
226 ;; API
227 (define (ring-buffer-empty? rb) (zero? (ring-buffer-num-entries rb)))
228
229 ;; API
230 (define (ring-buffer-full? rb)
231 (= (ring-buffer-num-entries rb) (ring-buffer-capacity rb)))
232
233 ;; API
234 (define (ring-buffer-room rb)
235 (- (ring-buffer-capacity rb) (ring-buffer-num-entries rb)))
236
237 (define (%ensure-nonempty rb)
238 (when (ring-buffer-empty? rb)
239 (error "Ring buffer is empty:" rb)))
240
241 ;; Make sure there's room for at least one entry in rb
242 (define (%ensure-room! rb dir) ; dir = 'forward | 'backward
243 (when (= (ring-buffer-num-entries rb) (ring-buffer-capacity rb))
244 (let1 v ((ring-buffer-overflow-handler rb) rb (ring-buffer-storage rb))
245 (case v
246 [(error) (error "Ring buffer overflow:" rb)]
247 [(overwrite)
248 ;; pop the last item so that we can fill it
249 (ecase dir
250 [(forward)
251 (let1 s (ring-buffer-storage rb)
252 (%rb-head-inc! rb (%dprocs s) s 1))]
253 [(backward)
254 (let1 s (ring-buffer-storage rb)
255 (%rb-tail-inc! rb (%dprocs s) s -1))])
256 (dec! (ring-buffer-num-entries rb))]
257 [else
258 (unless (or (vector? v) (uvector? v))
259 (error "Ring buffer overflow handler returned invalid object:" v))
260 (%rb-copy-contents! rb v (ring-buffer-storage rb))
261 (ring-buffer-head-set! rb 0)
262 (ring-buffer-tail-set! rb (ring-buffer-num-entries rb))
263 (ring-buffer-capacity-set! rb (size-of v))
264 (ring-buffer-storage-set! rb v)]))))
265
266 ;; API
267 (define (ring-buffer-front rb)
268 (%ensure-nonempty rb)
269 (let1 s (ring-buffer-storage rb)
270 (%rb-ref (%dprocs s) s (ring-buffer-head rb))))
271
272 ;; API
273 (define (ring-buffer-back rb)
274 (%ensure-nonempty rb)
275 (let1 s (ring-buffer-storage rb)
276 (%rb-ref-1 (%dprocs s) s (ring-buffer-tail rb))))
277
278 ;; API
279 (define (ring-buffer-add-front! rb elt)
280 (%ensure-room! rb 'backward)
281 (let* ([s (ring-buffer-storage rb)]
282 [dprocs (%dprocs s)])
283 (%rb-head-inc! rb dprocs s -1)
284 (%rb-set! dprocs s (ring-buffer-head rb) elt)
285 (inc! (ring-buffer-num-entries rb))
286 (undefined)))
287
288 ;; API
289 (define (ring-buffer-add-back! rb elt)
290 (%ensure-room! rb 'forward)
291 (let* ([s (ring-buffer-storage rb)]
292 [dprocs (%dprocs s)])
293 (%rb-set! dprocs s (ring-buffer-tail rb) elt)
294 (%rb-tail-inc! rb dprocs s 1)
295 (inc! (ring-buffer-num-entries rb))
296 (undefined)))
297
298 ;; API
299 (define (ring-buffer-remove-front! rb)
300 (%ensure-nonempty rb)
301 (let* ([s (ring-buffer-storage rb)]
302 [dprocs (%dprocs s)])
303 (rlet1 v (%rb-ref dprocs s (ring-buffer-head rb))
304 (%rb-head-inc! rb dprocs s 1)
305 (dec! (ring-buffer-num-entries rb)))))
306
307 ;; API
308 (define (ring-buffer-remove-back! rb)
309 (%ensure-nonempty rb)
310 (let* ([s (ring-buffer-storage rb)]
311 [dprocs (%dprocs s)])
312 (%rb-tail-inc! rb dprocs s -1)
313 (dec! (ring-buffer-num-entries rb))
314 (%rb-ref dprocs s (ring-buffer-tail rb))))
315
316 ;; API
317 (define (ring-buffer-ref rb n :optional fallback)
318 (if (<= 0 n (- (ring-buffer-num-entries rb) 1))
319 (let* ([s (ring-buffer-storage rb)]
320 [dprocs (%dprocs s)])
321 (%rb-ref dprocs s (%rb-mod-index dprocs s (+ (ring-buffer-head rb) n))))
322 (if (undefined? fallback)
323 (errorf "index out of range (~s) for a ring buffer ~s" n rb)
324 fallback)))
325
326 ;; API
327 (define (ring-buffer-set! rb n val)
328 (unless (<= 0 n (- (ring-buffer-num-entries rb) 1))
329 (errorf "index out of range (~s) for a ring buffer ~s" n rb))
330 (let* ([s (ring-buffer-storage rb)]
331 [dprocs (%dprocs s)])
332 (%rb-set! dprocs s (%rb-mod-index dprocs s (+ (ring-buffer-head rb) n))
333 val)))
334
335 ;; API
336 (define (ring-buffer-clear! rb)
337 (ring-buffer-head-set! rb 0)
338 (ring-buffer-tail-set! rb 0)
339 (ring-buffer-num-entries-set! rb 0))
340
341 ;; API (Unofficial)
342 ;; Insert ITEMS (a list or a (u)vector) at N-th position of RB, shifting
343 ;; the rest elements.
344 ;; This is to implement flexvector. We're not sure if this is appropriate
345 ;; as a feature of ring-buffer, though, so for now we keep this unofficial.
346 ; Note: The ring buffer needs room-maker callback, which takes
347 (define (ring-buffer-insert-all! rb n items)
348 (assume (<= 0 n (ring-buffer-num-entries rb))
349 "index out of range:"n)
350 (let1 size (size-of items)
351 (if (>= (+ (ring-buffer-num-entries rb) size) (ring-buffer-capacity rb))
352 (if-let1 room-maker (ring-buffer-room-maker rb)
353 (let1 newbuf ($ room-maker rb
354 (ring-buffer-storage rb)
355 (+ size (ring-buffer-num-entries rb)))
356 (ring-buffer->xvector! newbuf 0 rb 0 n)
357 (ring-buffer->xvector! newbuf (+ n size) rb n)
358 (for-each-with-index
359 (^[i item] (set! (~ newbuf (+ n i)) item))
360 items)
361 (ring-buffer-storage-set! rb newbuf)
362 (ring-buffer-num-entries-set! rb (+ size (ring-buffer-num-entries rb)))
363 (ring-buffer-capacity-set! rb (size-of newbuf))
364 (ring-buffer-head-set! rb 0)
365 (ring-buffer-tail-set! rb (ring-buffer-num-entries rb)))
366 (errorf "ring buffer overflow (capacity=~s, required=~s)"
367 (ring-buffer-capacity rb)
368 (+ size (ring-buffer-num-entries rb))))
369 (let ([storage (ring-buffer-storage rb)]
370 [cap (ring-buffer-capacity rb)])
371 (do ([i (- size 1) (- i 1)])
372 [(< i 0)]
373 (set! (~ storage (modulo (+ n i) cap))
374 (~ storage (modulo (+ n size i) cap))))
375 (for-each-with-index
376 (^[i item] (set! (~ storage (modulo (+ n i) cap)) item))
377 items))))
378 (undefined))
379
380 ;; API
381 ;; Returns (vec1 start1 end1 vec2 start2 end2 ...)
382 ;; The list is compatbile to the argument list of *vector-append-subvectors.
383 ;; With the current implementation, the number of subvector ranges are
384 ;; 0, 1 or 2, but the caller shouldn't assume that.
385 (define (ring-buffer->xsubvectors rb
386 :optional (start 0)
387 (end (ring-buffer-num-entries rb)))
388 (define storage (ring-buffer-storage rb))
389 (assume (<= 0 start end (ring-buffer-num-entries rb))
390 "start/end index out of range:" (list start end))
391 (if (= start end)
392 '()
393 (let ([h (modulo (+ (ring-buffer-head rb) start)
394 (ring-buffer-capacity rb))]
395 [t (modulo (+ (ring-buffer-head rb) end)
396 (ring-buffer-capacity rb))])
397 (cond [(< h t) `(,storage ,h ,t)]
398 [(= t 0) `(,storage ,h ,(ring-buffer-capacity rb))]
399 [else `(,storage ,h ,(ring-buffer-capacity rb) ,storage ,0 ,t)]))))
400
401 ;; API
402 (define (ring-buffer->xvector rb
403 :optional (start 0)
404 (end (ring-buffer-num-entries rb)))
405 (define storage (ring-buffer-storage rb))
406 (define appender
407 ;; there should be better way
408 (cond [(vector? storage) vector-append-subvectors]
409 [(u8vector? storage) u8vector-append-subvectors]
410 [(s8vector? storage) s8vector-append-subvectors]
411 [(u16vector? storage) u16vector-append-subvectors]
412 [(s16vector? storage) s16vector-append-subvectors]
413 [(u32vector? storage) u32vector-append-subvectors]
414 [(s32vector? storage) s32vector-append-subvectors]
415 [(u64vector? storage) u64vector-append-subvectors]
416 [(s64vector? storage) s64vector-append-subvectors]
417 [(f16vector? storage) f16vector-append-subvectors]
418 [(f32vector? storage) f32vector-append-subvectors]
419 [(f64vector? storage) f64vector-append-subvectors]
420 [(c32vector? storage) c32vector-append-subvectors]
421 [(c64vector? storage) c64vector-append-subvectors]
422 [(c128vector? storage) c128vector-append-subvectors]
423 [else (error "Unsupported backing storage:" storage)]))
424 (apply appender (ring-buffer->xsubvectors rb start end)))
425
426 ;; API
427 (define (ring-buffer->xvector! target tstart rb
428 :optional (start 0)
429 (end (ring-buffer-num-entries rb)))
430 (define storage (ring-buffer-storage rb))
431 (define fill! (if (vector? storage) vector-copy! uvector-copy!))
432
433 (assume (eqv? (class-of storage) (class-of target))
434 "target must be the same class as ring-buffer's backing storage:"
435 (list (class-of target) (class-of storage)))
436 (assume (<= 0 start end (ring-buffer-num-entries rb))
437 "start/end index out of range:" (list start end))
438 (assume (and (<= 0 tstart)
439 (<= (+ tstart (- end start)) (size-of target)))
440 "tstart out of range:" tstart)
441
442 (let loop ([k tstart]
443 [subvecs (ring-buffer->xsubvectors rb start end)])
444 (match subvecs
445 [() (undefined)]
446 [(vec s e . rest) (fill! target k vec s e) (loop (+ k (- e s)) rest)])))
447
448 ;;
449 ;; Sequence protocol
450 ;;
451
452 (define-method call-with-iterator ((rb ring-buffer) proc :key (start 0))
453 (define len (ring-buffer-num-entries rb))
454 (define k start)
455 (proc (^[] (>= k len))
456 (^[] (rlet1 v (ring-buffer-ref rb k)
457 (inc! k)))))
458
459 (define-method call-with-reverse-iterator ((rb ring-buffer) proc
460 :key
461 (start 0)
462 (end (ring-buffer-num-entries rb))
463 :allow-other-keys)
464 (define k (- end 1))
465 (proc (^[] (<= start k))
466 (^[] (rlet1 v (ring-buffer-ref rb k)
467 (dec! k)))))
468
469 (define-method referencer ((rb ring-buffer)) ring-buffer-ref)
470 (define-method modifier ((rb ring-buffer)) ring-buffer-set!)