|Peter H. Fröhlich 3e7e869b41|
Replace queues that are in active use! 😄
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?
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.)
The implementation in
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.
Speaking of complications:
- The technique used violates a basic queue invariant, namely that you can
pop at most
nelements 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.
- If you need to
freemessages as they're being dequeued, you'll need to think about what happens when
rcq_freeis 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.)
- 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...
- Threads? Oh well. You'll need to add mutexes or apply fancy atomics in all the right places. Sorry, you're on your own.
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.