reconque/README.md

# reconque

Replace queues that are in active use! 😄

## Motivation

Say you're writing a network service that uses queues to buffer messages.
Say you need to be able to *dynamically* adjust the sizes of those queues while
the service is running.
Say you cannot afford to lose any messages even when *reducing* the capacity of
a queue.
Say you cannot afford to *copy* existing messages from one queue to another
either (those queues might be long-ish).

What do you do?

## Design

The basic idea is simple:
Allow a new queue to "wrap" an existing one.
Problem solved! 😄

A push or enqueue operation works on the new queue; a pop or dequeue operation
works on the old queue until it's empty; once the old queue is empty, you free
it; from here on out, a pop or dequeue operation works on the new queue.
(Yes this would be harder with stacks.)

## Implementation

The implementation in `reconque.h` and `reconque.c` is designed to be as simple
as possible. The point was to illustrate the idea and to avoid complications
that are not strictly necessary. The `demo.c` program is not much of a demo,
more of a unit test really. Sorry for the lack of comments, but I hope the code
is readable enough.

## Complications

Speaking of complications:

1. The technique used violates a basic queue invariant, namely that you can
   pop at most `n` elements out of a queue with capacity `n`. This can trip up
   code using a queue wrapping others. Here we get away with it because there's
   no operation to ask a queue how many elements it has. If you need that kind
   of information, you'll have to think a little.
2. If you need to `free` messages as they're being dequeued, you'll need to
   think about what happens when `rcq_free` is being called on a non-empty,
   potentially wrapping, queue. (I mostly put reference-counted objects into
   queues, and as part of my `rcq_free`-equivalent I'd release those.)
3. If you're performance-hungry, make sure you replace the `%` with a bitwise
   `&` and power-of-two capacities. I wouldn't recommend replacing the recursive
   parts, but if you find them offensive...
4. Threads? Oh well. You'll need to add mutexes or apply fancy atomics in all
   the right places. Sorry, you're on your own.

## License

I very much doubt that you can use the code "as is" for a real system, but feel
free to take it as a starting point if that seems helpful. Since it's under a
0-clause BSD license, which essentially makes it public domain, you're welcome
to do as you please. If the code was helpful to you I'd *appreciate* an email,
but it's certainly not required.