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.