Ring Buffers

To use the ring buffer implementation, create an instance of the ring_buffer type using rb_create(). You can then use the data management functions to add and remove data blocks from the buffer. You can also use the functional data operations to transform, reduce, or filter the data in the buffer as if it were a list.

Creation and Destruction

ring_buffer rb_create(const struct ds_properties *props)

Create a new ring buffer with the given properties.

Allocates and initializes a new ring buffer with the given properties.

Parameters
  • props: A pointer to a data structure properties structure (non-NULL)

Return
Upon successful completion, rb_create() shall return the newly created ring buffer. Otherwise, NULL shall be returned and errno set to indicate the error.

void rb_destroy(ring_buffer *buf)

Destroy and deallocate a ring buffer.

Destroys and deallocates the ring buffer pointed to by buf.

Parameters
  • buf: A pointer to a struct ring_buffer (non-NULL)

Data Management

bool rb_empty(const ring_buffer buf)

Determine if a ring buffer is empty.

Return
This function shall return true if buf is empty, or false otherwise.
Parameters
  • buf: The ring buffer to check (non-NULL)

bool rb_full(const ring_buffer buf)

Determine if a ring buffer is full.

Return
This function shall return true if buf is full, or false otherwise.
Parameters
  • buf: The ring buffer to check (non-NULL)

size_t rb_size(const ring_buffer buf)

Determine the number of data blocks stored in a ring buffer.

Return
This function shall return the number of data blocks stored in the ring buffer buf. This is distinct from the capacity of the ring buffer, which is the number of entries it will contain when full.
Parameters
  • buf: The ring buffer to check (non-NULL)

void *rb_pop_head(ring_buffer buf)

Pop a data element from the head of a ring buffer.

Remove and return the data element at the head of buf. After this operation the returned data element will no longer be stored in buf.

Parameters
  • buf: The ring buffer to pop from (non-NULL)

This pointer must be explicitly freed with free() when it is no longer needed. It is not equivalent to the pointer which was used to insert the data into buf.

Return
Upon successful completion, this function shall return a pointer to the data block stored at the head of buf; otherwise, NULL shall be returned and errno set appropriately.

void *rb_pop_tail(ring_buffer buf)

Pop a data element from the tail of a ring buffer.

Remove and return the data block at the tail of buf. After this operation the returned data block will no longer be stored in buf.

Parameters
  • buf: The ring buffer to pop from (non-NULL)

This pointer must be explicitly freed with free() when it is no longer needed. It is not equivalent to the pointer which was used to insert the data into buf.

Return
Upon successful completion, this function shall return a pointer to the data block stored at the tail of buf; otherwise, NULL shall be returned and errno set appropriately.

bool rb_push_head(ring_buffer buf, const void *data)

Push a new data block onto the head of a ring buffer.

Push a newly allocated copy of data onto the head of buf.

Parameters
  • buf: The ring buffer to push onto
  • data: A pointer to the data to push

bool rb_push_tail(ring_buffer buf, const void *data)

Push a new data block onto the tail of a ring buffer.

Push a newly allocated copy of data onto the tail of buf.

Parameters
  • buf: The ring buffer to push onto
  • data: A pointer to the data to push

bool rb_elem(const ring_buffer buf, const void *data)

Determine if a ring buffer contains a value.

Determines if buf contains an entry matching data. The operation compares the contents of the memory pointed to by data, and not the memory addresses of the data pointers.

Parameters
  • buf: The ring buffer to search
  • data: The data to search for

Return
true if a matching entry is found, otherwise false

bool rb_insert(ring_buffer buf, const void *data, const ssize_t pos)

Insert a data block into a ring buffer at a certain position.

Insert a newly allocated copy of data into buf at the index indicated by pos.

Parameters
  • buf: The ring buffer to insert into (non-NULL)
  • data: A pointer to the data to insert
  • pos: The position to insert the data block at

Return
Upon successful completion, this function shall return true; otherwise, false shall be returned and errno set appropriately.

void *rb_fetch(const ring_buffer buf, const ssize_t pos)

Fetch a data block from a given index of a ring buffer.

Fetch the data stored at index pos in buf.

Parameters
  • buf: The ring buffer to fetch from
  • pos: The index to fetch the block from

Return
A pointer to the data at index pos, or NULL on failure. This pointer should not be free()d explicitly, or the buf will become corrupted. This pointer will be free()d when rb_free() is called, so if the data is needed after buf is destroyed, make a copy of it or make sure to call rb_remove() on the data’s index before destroying buf.

bool rb_delete(ring_buffer buf, const size_t pos)

Delete a data element from a given index of a ring buffer.

Delete the copy of data stored in buf at the index indicated by pos.

Parameters
  • buf: The ring buffer to delete from
  • pos: The index to delete the element at

Return
Upon successful completion, this function shall return true; otherwise, false shall be returned and errno set appropriately..

void *rb_remove(ring_buffer buf, const size_t pos)

Delete and return a data element from a given index of a ring buffer.

Delete the copy of data stored in buf at the index indicated by pos.

Parameters
  • buf: The ring buffer to delete from
  • pos: The index to delete the element at

Return
A pointer to the data removed from buf, or NULL on failure. This pointer must be explicitly freed with free() when it is no longer needed. It is not equivalent to the pointer which was used to insert the data into buf.

bool rb_reverse(ring_buffer buf)

Reverse the contents of a ring buffer in-place.

Reverses buf in-place so that the data blocks are in reverse order when enumerated from head to tail.

Parameters
  • buf: The ring buffer to reverse

Higher Order Functions

void rb_map(ring_buffer buf, const map_fn fn)

Map a function over the contents of a ring buffer in-place.

A map operation iterates over buf and transforms each data block using the function fn, replacing the old value with the result of the transformation. In pseudo-code: 

for i from 0 to (length - 1):
    buffer[i] = fn(buffer[i])
Parameters
  • buf: A ring buffer to map over
  • fn: A function that will transform each data block in the buffer

void *rb_foldr(const ring_buffer buf, const foldr_fn fn, const void *init)

Right associative fold for ring buffers.

A right associative fold uses the binary function fn to sequentially reduce a list of values to a single value, starting from some initial value init: 

fn(init, fn(buf[0], fn(buf[1], ...)))
Parameters
  • buf: A ring buffer to reduce
  • fn: A binary function that will sequentially reduce values
  • init: An initial value for the fold

Return
Upon successful completetion, this function shall return the result of a right associate fold over buf. If buf is empty, the fold will be equal to the value of buf. Otherwise, NULL shall be returned and errno set to indicate the error.

void *rb_foldl(const ring_buffer buf, const foldl_fn fn, const void *init)

Left associative fold for ring buffers.

A left associative fold uses the binary function fn to sequentially reduce a list of values to a single value, starting from some initial value init: 

fn(fn(fn(..., init), buf[0]), buf[1])
Parameters
  • buf: A ring buffer to reduce
  • fn: A binary function that will sequentially reduce values
  • init: An initial value for the fold

Return
Upon successful completetion, this function shall return the result of a left associate fold over buf. If buf is empty, the fold will be equal to the value of buf. Otherwise, NULL shall be returned and errno set to indicate the error.

bool rb_any(const ring_buffer buf, const pred_fn pred)

Determine if any value in a ring buffer satisifies some condition.

Iterate over each value stored in buf, and determine if any of them satisfies pred (e.g. pred returns true when passed that value).

Parameters
  • buf: A ring buffer to check
  • pred: The predicate function (representing a condition to be satisfied).

Return
true if there is at least one value that satisfies the predicate. Otherwise, it returns false.

bool rb_all(const ring_buffer buf, const pred_fn pred)

Determines if all values in a ring buffer satisify some condition.

Iterate over each value stored in buf, and determine if all of them satisfy pred (e.g. pred returns true when passed that value).

Parameters
  • buf: A list of values
  • pred: The predicate function (representing a condition to be satisfied).

Return
false if there is at least one value that does not satisfy the predicate. Otherwise, it returns true.

void rb_filter(ring_buffer buf, const pred_fn pred)

Filter a buffer to contain only values that satisfy some predicate.

Filter buf in-place by removing elements that do not satisfy the predicate pred. Elements that do satisfy the predicate pred remain in the buffer.

Parameters
  • buf: The buffer to filter
  • pred: The predicate

void rb_drop_while(ring_buffer buf, const pred_fn pred)

Drop elements from the head of the buffer until the predicate is unsatisfied.

Drop each element that satisfies the predicate pred, starting at the beginning of buf and continuing until reaching the first element that does not satisfy the predicate pred.

This function is an in-place equivalent to Haskell’s dropWhile.

void rb_take_while(ring_buffer buf, const pred_fn pred)

Keep elements from the head of the buffer until the predicate is unsatisfied.

Iterate over each element of buf, starting at the beginning, that satisfies the predicate pred. Once an element that does not satisfy the predicate pred is reached, drop the rest of the list including that element.

This function is an in-place equivalent to Haskell’s takeWhile.

Debugging

void rb_dump(const ring_buffer buf)

Dump the contents of a ring_buffer to standard output.

Prints the contents of a ring buffer in nice format, byte by byte, including information on addresses, indices, and the locations of the head and tail pointers.

Parameters
  • buf: The buffer to display.