The mmap() copy-on-write trick: reducing memory usage of array copies

https://i.imgur.com/NfZTICG.png

p = memory address of the beginning of the first page

o = the head index

s = the size

C = capacity = size of page

Now suppose I wish to append 10 bytes. I would simply do:

memcpy(p + (o + s) % C, input_data, 10)

s += 10

Or, to remove 15 bytes from the beginning, I would do:

o = (o + 15) % C

s -= 15

Because any given 'slice' of the ring buffer's space can be represented as a contiguous range of memory (thanks to the second page), I can use the already optimized memcpy routine for adding and removing data at the beginning or end of the buffer. But I still need to make sure that the head index is always updated modulo the capacity, or it will increment unboundedly, as you say.

As you can tell in the above example, I'm not adding/removing individual bytes. Magic ring buffers only make sense when you frequently need to add or remove several elements from the ends of the buffer. It's particularly well suited for when you have a stream of data and need to operate on it in chunks.

Here's a GitHub repo that contains an implementation of the magic ring buffer: https://github.com/willemt/cbuffer