12.22 data.ring-buffer - Ring buffer ¶

Module: data.ring-buffer ¶

A ring buffer is an array with two fill pointers; in a typical usage, a producer adds new data to one end while a consumer removes data from the other end; if fill pointer reaches at the end of the array, it wraps around to the beginning, hence the name.

The ring buffer of this module allows adding and removing elements from both ends, hence functionally it is a double-ended queue, or deque. It also allows O(1) indexed access to the contents, and customized handling for the case when the buffer gets full.

You can use an ordinary vector or a uniform vector as the backing storage of a ring buffer.

Function: make-ring-buffer :optional initial-storage :key overflow-handler initial-head-index initial-tail-index ¶

{data.ring-buffer} Creates a ring buffer. By default, a fresh vector is allocated for the backing storage. You can pass a vector or a uvector to initial-storage to be used instead. The passed storage must be mutable, and will be modified by the ring buffer; the caller shouldn’t modify it, nor make assumption about its content.

By default, the storage you pass as initial-storage is assumed to be an empty buffer. You can also pass a pre-filled storage, by specifing valid range of existing data with initial-head-index and initial-tail-index arguments (both are defaulted to 0). For example, the following code returns a ring buffer of initial capacity 8, with the first 4 items are already filled.

(make-ring-buffer (vector 'a 'b 'c 'd #f #f #f #f)
                  :initial-tail-index 4)

The overflow-handler keyword argument specifies what to do when a new element is about to be added to the full buffer. It must be a procedure, or a symbol error or overwrite.

If it is a procedure, it will be called with a ring buffer and a backing storage (vector or uvector) when it is filled. The procedure must either (1) allocate and return a larger vector/uvector of the same type of the passed backing storage, (2) return a symbol error, or (3) return a symbol overwrite. If it returns a vector/uvector, it will be used as the new backing storage. The returned vector doesn’t need to be initialized; the ring buffer routine takes care of copying the necessary data. If it returns error, an error (“buffer is full”) is thrown. If it returns overwrite, the new element overwrites the existing element (as if one element from the other end is popped and discarded.)

Passing a symbol error or overwrite to overflow-handler is a shorthand of passing a procedure that unconditionally returns error or overwrite, respectively.

The default behavior on overflow is to double the size of backing storage. You can use make-overflow-doubler below to create the customized overflow handler easily.

Function: make-overflow-doubler :key max-increase max-capacity ¶

{data.ring-buffer} Returns a procedure suitable to be passed to the overflow-handler keyword argument of make-ring-buffer.

The returned procedure takes a ring buffer and its backing storage, and behaves as follows.

• If the size of current backing storage is equal to or greater than max-capacity, returns error.
• Otherwise, if the size of current backing storage is equal to or greater than max-increase, allocates a vector/uvector of the same type of the current backing storage, with the size (+ max-increase size-of-current-storage).
• Otherwise, allocates a vector/uvector of the same type of the current backing storage with the size (* 2 size-of-current-storage).

The default value of max-increase and max-capacity is +inf.0.

Function: ring-buffer-empty? rb ¶

{data.ring-buffer} Returns #t if the ring buffer rb is empty, #f if not.

Function: ring-buffer-full? rb ¶

{data.ring-buffer} Returns #t if the ring buffer rb is full, #f if not.

Function: ring-buffer-num-entries rb ¶

{data.ring-buffer} Returns the number of current elements in the ring buffer rb.

Function: ring-buffer-capacity rb ¶

{data.ring-buffer} Returns the size of the current backing storage of the ring buffer rb.

Function: rinb-buffer-room rb ¶

{data.ring-buffer} Returns the remaining room in the current backing storage of the ring buffer rb, before triggering the overflow handler. It is the difference of ring-buffer-capacity and ring-buffer-num-entries.

Function: ring-buffer-front rb ¶

Function: ring-buffer-back rb ¶

{data.ring-buffer} Returns the element in the front or back of the ring buffer rb, respectively. If the buffer is empty, an error is signaled.

Function: ring-buffer-add-front! rb elt ¶

Function: ring-buffer-add-back! rb elt ¶

{data.ring-buffer} Add an element to the front or back of the ring buffer rb, respectively. If rb is full, the behavior is determined by the buffer’s overflow handler, as described in make-ring-buffer.

Function: ring-buffer-remove-front! rb ¶

Function: ring-buffer-remove-back! rb ¶

{data.ring-buffer} Remove an element from the front or back of the ring buffer rb, and returns the removed element, respectively. If the buffer is empty, an error is signaled.

Function: ring-buffer-ref rb index :optional fallback ¶

{data.ring-buffer} Returns index-th element in the ring buffer rb. The elements are counted from the front; thus, if a new element is added to the front, the indexes of existing elements will shift.

If the index out of bounds of the existing content, fallback will be returned; if fallback is not provided, an error is signaled.

Function: ring-buffer-set! rb index value ¶

{data.ring-buffer} Sets index-th element of the ring buffer rb to value. The elements are counted from the front; thus, if a new element is added to the front, the indexes of existing elements will shift.

An error is signaled if the index is out of bounds.

Function: ring-buffer->xvector rb :optional start end ¶

{data.ring-buffer} Returns the current valid content of the ring buffer rb as a fresh vector of the same type as rb’s storage. If the optional start/end indexes are given, the content between those indexes are taken.

(define rb (make-ring-buffer (make-vector 4)))

(ring-buffer->xvector rb) ⇒ #()

(ring-buffer-add-back! rb 'a)
(ring-buffer-add-back! rb 'b)
(ring-buffer-add-front! rb 'z)
(ring-buffer-add-front! rb 'y)

(ring-buffer->xvector rb) ⇒ #(y z a b)
(ring-buffer->xvector rb 1 3) ⇒ #(z a)

Function: ring-buffer->xvector! target tstart rb :optional start end ¶

{data.ring-buffer} Like ring-buffer->xvector above, but store the result into target, starting from index tstart. Target must be the same type of vector of the backing storage of rb, and must be large enough to hold the result. If the optional start/end indexes are given, the content between those indexes are taken.

Function: ring-buffer->xsubvectors rb :optional start end ¶

{data.ring-buffer} Returns (vec start1 end1) or (vec start1 end1 vec start2 end2), where vec is the backing storage of ring buffer rb, and start1, end1, start2, end2 are integer index into vec. They represent the range(s) in the backing storage where active ring buffer data is stored. It may be contiguous, or splitted to two parts when the buffer is wrapped around.

The optional start and end arguments are indexes of the contents of ring buffer (not the indexes to the backing storage) to limit the range of the contents to be extracted.

The returned list can be passed as arguments to vector-append-subvectors (see scheme.vector - R7RS vectors) or @vector-append-subvector (see Uvector basic operations).

This procedure is lightweight, for it doesn’t allocate. However, be aware that the content of vec may be changed and/or indexes become invalid by operations on rb. I you want a snapshot of the ring buffer contents, you can use ring-buffer->xvector above.