A Ring Buffer

A ring buffer is an array that is thought of as circular; that is the first element follows the last. Uses include:

A queue, which is like a stack, but items can be added to or taken off either end.

A stack from which old elements are automatically discarded.

Programming a ring buffer

An indexed array of size n becomes a ring buffer if one always reduces the index modulus n. If n is a power of 2, then masking with n-1 will reduce the index without doing any arithmetic.

32 array (ring)
: ring ( i -- addr) 31 and (ring) ;

: ring ( i -- addr) 31 and (ring) ;

: ring ( i -- addr) 31 and cells (ring) + ;

In the above, 32 and 31 are "hard-wired." To alter the size of the buffer requires two changes. The following requires only one:

32 constant ring-size
ring-size array (ring)
: ring ( i -- addr) [ ring-size 1- ] literal and (ring) ;

Note the use of the brackets, [ and ]. These turn compilation off and on, respectively, leaving 31 on the stack. This is then used by literal. The two versions of ring have the same action; in fact, they compile exactly the same in most Forths.

A stack that discards obsolete values

By defining a stack in a ring, there can never be more than n values on the stack. Overflow cannot occur because obsolete values are automatically discarded. It is the programmer's responsibility to guard against underflow.

variable ring-pointer \ pointer to top of stack

: initialize-ring ( -- )
     0 ring-pointer ! ;

:  ring! ( n -- )       \ push n onto ring
     ring-pointer @     \ n i     get index of top of stack
     dup 1+ \ n i i+1
         ring-pointer ! \ n i     update pointer
     ring               \ n a     convert to address
     !        ;         \ --     1     & store

: ring@ ( -- n)         \ pop n off ring
     ring-pointer @     \ i
     1- dup             \ i' i'
     ring-pointer !     \ i' update pointer
     ring 
     @        ;         \ & fetch

Code meets requrements for an ANS Forth standard program.

Home

Updated: July 28, 1996

\ array is defined in arrays.htm
32 constant ring-size  \ Must be a power of 2
ring-size array (ring)
: ring ( i -- addr)
     [ ring-size 1- ] literal and (ring) ;

variable ring-pointer \ pointer to top of stack
: initialize-ring ( -- )
     0 ring-pointer !  ;

:  ring! ( n -- )       \ push n onto ring
     ring-pointer @     \ n i     get index of top of stack
     dup 1+ \ n i i+1
         ring-pointer ! \ n i     update pointer
     ring               \ n a     convert to address
     !  ;               \ --     1     & store

: ring@ ( -- n)         \ pop n off ring
     ring-pointer @     \ i
     1- dup             \ i' i'
     ring-pointer !     \ i' update pointer
     ring 
     @  ;               \ & fetch