For Gauche 0.9.5


Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]

12.13 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 reachers 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

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.

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 it. 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

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.

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

Function: ring-buffer-empty? rb

Returns #t if the ring buffer rb is empty, #f if not.

Function: ring-buffer-full? rb

Returns #t if the ring buffer rb is full, #f if not.

Function: ring-buffer-num-elements rb

Returns the number of current elements in the ring buffer rb.

Function: ring-buffer-capacity rb

Returns the size of the current backing storage of the ring buffer rb.

Function: ring-buffer-front rb
Function: ring-buffer-back rb

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

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

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

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

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.


Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]