utringbuffer: dynamic ring-buffer macros for C
==============================================
Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
v2.3.0, February 2021

Here's a link back to the https://github.com/troydhanson/uthash[GitHub project page].

Introduction
------------
The functions in `utringbuffer.h` are based on the general-purpose array macros
provided in `utarray.h`, so before reading this page you should read
link:utarray.html[that page] first.

To use these macros in your own C program, copy both `utarray.h` and `utringbuffer.h`
into your source directory and use `utringbuffer.h` in your program.

  #include "utringbuffer.h"

The provided <<operations,operations>> are based loosely on the C++ STL vector methods.
The ring-buffer data type supports construction (with a specified capacity),
destruction, iteration, and push, but not pop; once the ring-buffer reaches full
capacity, pushing a new element automatically pops and destroys the oldest element.
The elements contained in the ring-buffer can be any simple datatype or structure.

Internally the ring-buffer contains a pre-allocated memory region into which the
elements are copied, starting at position 0. When the ring-buffer reaches full
capacity, the next element to be pushed is pushed at position 0, overwriting the
oldest element, and the internal index representing the "start" of the ring-buffer
is incremented. A ring-buffer, once full, can never become un-full.


Download
~~~~~~~~
To download the `utringbuffer.h` header file,
follow the links on https://github.com/troydhanson/uthash to clone uthash or get a zip file,
then look in the src/ sub-directory.

BSD licensed
~~~~~~~~~~~~
This software is made available under the
link:license.html[revised BSD license].
It is free and open source.

Platforms
~~~~~~~~~
The 'utringbuffer' macros have been tested on:

 * Linux,
 * Mac OS X,
 * Windows, using Visual Studio 2008 and Visual Studio 2010

Usage
-----

Declaration
~~~~~~~~~~~

The ring-buffer itself has the data type `UT_ringbuffer`, regardless of the type of
elements to be stored in it. It is declared like,

  UT_ringbuffer *history;

New and free
~~~~~~~~~~~~
The next step is to create the ring-buffer using `utringbuffer_new`. Later when you're
done with the ring-buffer, `utringbuffer_free` will free it and all its elements.

Push, etc
~~~~~~~~~
The central features of the ring-buffer involve putting elements into it
and iterating over them. There are several <<operations,operations>>
that deal with either single elements or ranges of elements at a
time. In the examples below we will use only the push operation to insert
elements.

Elements
--------

Support for dynamic arrays of integers or strings is especially easy. These are
best shown by example:

Integers
~~~~~~~~
This example makes a ring-buffer of integers, pushes 0-9 into it, then prints it
two different ways. Lastly it frees it.

.Integer elements
-------------------------------------------------------------------------------
#include <stdio.h>
#include "utringbuffer.h"

int main() {
  UT_ringbuffer *history;
  int i, *p;

  utringbuffer_new(history, 7, &ut_int_icd);
  for(i=0; i < 10; i++) utringbuffer_push_back(history, &i);

  for (p = (int*)utringbuffer_front(history);
       p != NULL;
       p = (int*)utringbuffer_next(history, p)) {
    printf("%d\n", *p);  /* prints "3 4 5 6 7 8 9" */
  }

  for (i=0; i < utringbuffer_len(history); i++) {
    p = utringbuffer_eltptr(history, i);
    printf("%d\n", *p);  /* prints "3 4 5 6 7 8 9" */
  }

  utringbuffer_free(history);

  return 0;
}
-------------------------------------------------------------------------------

The second argument to `utringbuffer_push_back` is always a 'pointer' to the type
(so a literal cannot be used). So for integers, it is an `int*`.

Strings
~~~~~~~
In this example we make a ring-buffer of strings, push two strings into it, print
it and free it.

.String elements
-------------------------------------------------------------------------------
#include <stdio.h>
#include "utringbuffer.h"

int main() {
  UT_ringbuffer *strs;
  char *s, **p;

  utringbuffer_new(strs, 7, &ut_str_icd);

  s = "hello"; utringbuffer_push_back(strs, &s);
  s = "world"; utringbuffer_push_back(strs, &s);
  p = NULL;
  while ( (p=(char**)utringbuffer_next(strs,p))) {
    printf("%s\n",*p);
  }

  utringbuffer_free(strs);

  return 0;
}
-------------------------------------------------------------------------------

In this example, since the element is a `char*`, we pass a pointer to it
(`char**`) as the second argument to `utringbuffer_push_back`. Note that "push" makes
a copy of the source string and pushes that copy into the array.

About UT_icd
~~~~~~~~~~~~

Arrays can be made of any type of element, not just integers and strings. The
elements can be basic types or structures. Unless you're dealing with integers
and strings (which use pre-defined `ut_int_icd` and `ut_str_icd`), you'll need
to define a `UT_icd` helper structure. This structure contains everything that
utringbuffer (or utarray) needs to initialize, copy or destruct elements.

  typedef struct {
      size_t sz;
      init_f *init;
      ctor_f *copy;
      dtor_f *dtor;
  } UT_icd;

The three function pointers `init`, `copy`, and `dtor` have these prototypes:

  typedef void (ctor_f)(void *dst, const void *src);
  typedef void (dtor_f)(void *elt);
  typedef void (init_f)(void *elt);

The `sz` is just the size of the element being stored in the array.

The `init` function is used by utarray but is never used by utringbuffer;
you may safely set it to any value you want.

The `copy` function is used whenever an element is copied into the buffer.
It is invoked during `utringbuffer_push_back`.
If `copy` is `NULL`, it defaults to a bitwise copy using memcpy.

The `dtor` function is used to clean up an element that is being removed from
the buffer. It may be invoked due to `utringbuffer_push_back` (on the oldest
element in the buffer), `utringbuffer_clear`, `utringbuffer_done`, or
`utringbuffer_free`.
If the elements need no cleanup upon destruction, `dtor` may be `NULL`.

Scalar types
~~~~~~~~~~~~

The next example uses `UT_icd` with all its defaults to make a ring-buffer of
`long` elements. This example pushes two longs into a buffer of capacity 1,
prints the contents of the buffer (which is to say, the most recent value
pushed), and then frees the buffer.

.long elements
-------------------------------------------------------------------------------
#include <stdio.h>
#include "utringbuffer.h"

UT_icd long_icd = {sizeof(long), NULL, NULL, NULL };

int main() {
  UT_ringbuffer *nums;
  long l, *p;
  utringbuffer_new(nums, 1, &long_icd);

  l=1; utringbuffer_push_back(nums, &l);
  l=2; utringbuffer_push_back(nums, &l);

  p=NULL;
  while((p = (long*)utringbuffer_next(nums,p))) printf("%ld\n", *p);

  utringbuffer_free(nums);
  return 0;
}
-------------------------------------------------------------------------------

Structures
~~~~~~~~~~

Structures can be used as utringbuffer elements. If the structure requires no
special effort to initialize, copy or destruct, we can use `UT_icd` with all
its defaults. This example shows a structure that consists of two integers. Here
we push two values, print them and free the buffer.

.Structure (simple)
-------------------------------------------------------------------------------
#include <stdio.h>
#include "utringbuffer.h"

typedef struct {
    int a;
    int b;
} intpair_t;

UT_icd intpair_icd = {sizeof(intpair_t), NULL, NULL, NULL};

int main() {

  UT_ringbuffer *pairs;
  intpair_t ip, *p;
  utringbuffer_new(pairs, 7, &intpair_icd);

  ip.a=1;  ip.b=2;  utringbuffer_push_back(pairs, &ip);
  ip.a=10; ip.b=20; utringbuffer_push_back(pairs, &ip);

  for(p=(intpair_t*)utringbuffer_front(pairs);
      p!=NULL;
      p=(intpair_t*)utringbuffer_next(pairs,p)) {
    printf("%d %d\n", p->a, p->b);
  }

  utringbuffer_free(pairs);
  return 0;
}
-------------------------------------------------------------------------------

The real utility of `UT_icd` is apparent when the elements stored in the
ring-buffer are structures that require special work to initialize, copy or
destruct.

For example, when a structure contains pointers to related memory areas that
need to be copied when the structure is copied (and freed when the structure is
freed), we can use custom `init`, `copy`, and `dtor` members in the `UT_icd`.

Here we take an example of a structure that contains an integer and a string.
When this element is copied (such as when an element is pushed),
we want to "deep copy" the `s` pointer (so the original element and the new
element point to their own copies of `s`). When an element is destructed, we
want to "deep free" its copy of `s`. Lastly, this example is written to work
even if `s` has the value `NULL`.

.Structure (complex)
-------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include "utringbuffer.h"

typedef struct {
    int a;
    char *s;
} intchar_t;

void intchar_copy(void *_dst, const void *_src) {
  intchar_t *dst = (intchar_t*)_dst, *src = (intchar_t*)_src;
  dst->a = src->a;
  dst->s = src->s ? strdup(src->s) : NULL;
}

void intchar_dtor(void *_elt) {
  intchar_t *elt = (intchar_t*)_elt;
  free(elt->s);
}

UT_icd intchar_icd = {sizeof(intchar_t), NULL, intchar_copy, intchar_dtor};

int main() {
  UT_ringbuffer *intchars;
  intchar_t ic, *p;
  utringbuffer_new(intchars, 2, &intchar_icd);

  ic.a=1; ic.s="hello"; utringbuffer_push_back(intchars, &ic);
  ic.a=2; ic.s="world"; utringbuffer_push_back(intchars, &ic);
  ic.a=3; ic.s="peace"; utringbuffer_push_back(intchars, &ic);

  p=NULL;
  while( (p=(intchar_t*)utringbuffer_next(intchars,p))) {
    printf("%d %s\n", p->a, (p->s ? p->s : "null"));
    /* prints "2 world 3 peace" */
  }

  utringbuffer_free(intchars);
  return 0;
}

-------------------------------------------------------------------------------

[[operations]]
Reference
---------
This table lists all the utringbuffer operations. These are loosely based on the C++
vector class.

Operations
~~~~~~~~~~

[width="100%",cols="50<m,40<",grid="none",options="none"]
|===============================================================================
| utringbuffer_new(UT_ringbuffer *a, int n, UT_icd *icd)  | allocate a new ringbuffer
| utringbuffer_free(UT_ringbuffer *a)                     | free an allocated ringbuffer
| utringbuffer_init(UT_ringbuffer *a, int n, UT_icd *icd) | init a ringbuffer (non-alloc)
| utringbuffer_done(UT_ringbuffer *a)                     | dispose of a ringbuffer (non-alloc)
| utringbuffer_clear(UT_ringbuffer *a)                    | clear all elements from a, making it empty
| utringbuffer_push_back(UT_ringbuffer *a, element *p)    | push element p onto a
| utringbuffer_len(UT_ringbuffer *a)                      | get length of a
| utringbuffer_empty(UT_ringbuffer *a)                    | get whether a is empty
| utringbuffer_full(UT_ringbuffer *a)                     | get whether a is full
| utringbuffer_eltptr(UT_ringbuffer *a, int j)            | get pointer of element from index
| utringbuffer_eltidx(UT_ringbuffer *a, element *e)       | get index of element from pointer
| utringbuffer_front(UT_ringbuffer *a)                    | get oldest element of a
| utringbuffer_next(UT_ringbuffer *a, element *e)         | get element of a following e (front if e is NULL)
| utringbuffer_prev(UT_ringbuffer *a, element *e)         | get element of a before e (back if e is NULL)
| utringbuffer_back(UT_ringbuffer *a)                     | get newest element of a
|===============================================================================

Notes
~~~~~

1. `utringbuffer_new` and `utringbuffer_free` are used to allocate a new ring-buffer
   and to free it,
   while `utringbuffer_init` and `utringbuffer_done` can be used if the UT_ringbuffer
   is already allocated and just needs to be initialized or have its internal resources
   freed.
2. Both `utringbuffer_new` and `utringbuffer_init` take a second parameter `n` indicating
   the capacity of the ring-buffer, that is, the size at which the ring-buffer is considered
   "full" and begins to overwrite old elements with newly pushed ones.
3. Once a ring-buffer has become full, it will never again become un-full except by
   means of `utringbuffer_clear`. There is no way to "pop" a single old item from the
   front of the ring-buffer. You can simulate this ability by maintaining a separate
   integer count of the number of "logically popped elements", and starting your iteration
   with `utringbuffer_eltptr(a, popped_count)` instead of with `utringbuffer_front(a)`.
4. Pointers to elements (obtained using `utringbuffer_eltptr`, `utringbuffer_front`,
   `utringbuffer_next`, etc.) are not generally invalidated by `utringbuffer_push_back`,
   because utringbuffer does not perform reallocation; however, a pointer to the oldest
   element may suddenly turn into a pointer to the 'newest' element if
   `utringbuffer_push_back` is called while the buffer is full.
5. The elements of a ring-buffer are stored in contiguous memory, but once the ring-buffer
   has become full, it is no longer true that the elements are contiguously in order from
   oldest to newest; i.e., `(element *)utringbuffer_front(a) + utringbuffer_len(a)-1` is
   not generally equal to `(element *)utringbuffer_back(a)`.

// vim: set nowrap syntax=asciidoc: