+------+------+------+------+------+-------+
| | | | | | |
| k | idx | x_0 | x_1 | … | x_k-1 |
| | | | | | |
+------+------+------+------+------+-------+
Index 0 1 k-1
This simple implementation has //only a single index// that identifies both, the location of the oldest value as well as the location where the newest value is to be stored. Because of this it always stores //exactly k// values. (More sophisticated implementations for general circular buffers manage a read and a write location and can store //from 0 up to k// values.)
When storing a new value it is written in the buffer at index position idx overwriting the old value that is stored there. After that idx is increased. If it exceeds the buffer capacity it restarts at 0. So the index runs around in circles given the circular buffer its name.
When reading values from the buffer, the oldest value can be accessed at index idx and the next k-1 entries (wrapping the index around at the buffer end i.e. index k-1) will be the oldest to latest entries.
Note, that the entries x_i have cell size. They can however be pointers to larger data structures such as arrays of sample data or floating point values.
=== Pseudo code of a single primitive circular buffer using global variables ===
Create circular buffer:
Define a variable idx and initialize it to 0.
Allocate a variable circular-buffer with k cells of memory, called x_0 … x_k-1
here. Maybe erase x_0 … x_k-1 to zero if initialization is desired.
Function: store-new-value ( x -- )
Store x in circular buffer at index idx.
Increment idx wrapping around at k-1.
Function: read-oldest-value ( -- x )
Read x from buffer at index idx.
Function: read-ith-oldest-value ( i -- x ) \ 0: oldest … k-1: youngest
Read x from buffer at index (i+idx) wrapping around at k-1.
----
For comparison here is a pseudo code version, that used a more Forth like style:
=== Pseudo code of a single primitive circular buffer using global variables (Forth like) ===
\ create circular buffer
«k» CONSTANT k
VARIABLE idx 0 idx !
CREATE circular-buffer k CELLS ALLOT
\ maybe erase x_0 … x_k-1 to zero if initialization is desired
: store-new-value ( x -- )
store x in circular buffer at index idx
increment idx wrapping around at k-1
;
: read-oldest-value ( -- x )
read x from buffer at index idx
;
: read-ith-oldest-value ( i -- x ) \ 0: oldest … k-1: youngest
read x from buffer at index (i+idx) wrapping around at k-1
;
----
=== Pseudo code of primitive circular buffer data structure identified by its address (Forth like) ===
: create-new-primitive-circular-buffer ( k -- pcb-addr )
allocate memory for k, idx and k entries x_0 to x_k-1
initialize field k to k, idx to 0
maybe erase x_0 … x_k-1 to zero if initialization is desired
return address of allocated memory
;
: store-new-value ( x pcb-addr -- )
store x in the buffer at index idx
increment idx wrapping around at k-1
;
: read-oldest-value ( pcb-addr -- x )
read x from buffer at index idx
;
: read-ith-oldest-value ( i pcb-addr -- x ) \ 0: oldest … k-1: youngest
read x from buffer at index (i + idx) wrapping around at k-1
;
The Fields k and idx as well as the address of x_0 in the above structure can best be defined using the word ''%%+FIELD%%'' ([[https://forth-standard.org/standard/facility/PlusFIELD|Forth-2012]]).
----
==== Forth implementations ====
The following implementations are provided:
**[[https://github.com/project-forth-works/project-forth-works.github.io/blob/main/minimalforth.md|Generic Forth]]** (a minimal Forth-94 and Forth-2012 subset) implementation of a single primitive circular buffer using global variables. This implementation assumes k to be a power of two so that the index wrap-around can be implemented by masking the bits of k-1.
\ primitive circular buffer in Generic Forth
\ -----------------------------------------------------------------
\ Primitive Circular Buffer
8 CONSTANT k \ k must be a power of 2 so that wrapping can be done by masking
VARIABLE idx 0 idx !
HERE k CELLS ALLOT CONSTANT circular-buffer
circular-buffer k CELLS 0 FILL
: 'item ( -- addr )
circular-buffer idx @ CELLS + ;
: wrap-around ( u1 -- u2 )
k 1 - AND
;
: store-new-value ( x -- )
'item !
idx @ 1 + wrap-around idx !
;
: read-oldest-value ( -- x )
'item @
;
: read-ith-oldest-value ( i -- x ) \ 0: oldest … k-1: youngest
idx @ + wrap-around CELLS circular-buffer + @
;
**Forth-94** implementation of the primitive circular buffer data structure identified by its address\\ A portable Forth-94 implementation can be found in [[https://github.com/project-forth-works/project-forth-works/blob/main/Data-Structures/Primitive-Circular-Buffer/primitive-circular-buffer-forth-94.fs|primitive-circular-buffer-forth-94.fs]].
This implementation uses a modulo k division to wrap around when the index reaches k-1. It also does address arithmetic every time the buffer is accessed. The implementation also includes tests using the test suite **[[http://www.forth200x.org/tests/ttester.fs|ttester.fs]]**. If the system does not support ttester, the tests can be performed by hand. The allocation and access to the data structure is aware of systems that might provide read only (ROM) and read write (RAM) memory areas.
**SwiftForth** implementation\\ Similar to the above Forth-94 implementation this makes use of the SwiftForth ''%%package%%'' mechanism to hide internal word. [[https://github.com/project-forth-works/project-forth-works/blob/main/Data-Structures/Primitive-Circular-Buffer/primitive-circular-buffer-SwiftForth.f|primitive-circular-buffer-SwiftForth.f]].
**[[https://github.com/project-forth-works/project-forth-works/tree/main/Data-Structures/Primitive-Circular-Buffer/noForth|noForth]]**, specific implementation using the Generic Forth approach.