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: 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->flat-vector rb :optional start end ¶

{data.ring-buffer} Returns the current valid content of the ring buffer rb as a fresh flat 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->flat-vector 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->flat-vector rb) ⇒ #(y z a b)
(ring-buffer->flat-vector rb 1 3) ⇒ #(z a)