I'm processing items in multiple threads, and the producers may output them into buffers out of order. Some later pipeline stages are not memoryless, and I need to put the partially processed items in order, so I have a thread gathering them from buffers output by previous stage workers and putting them into a standard heap-based priority queue, pulling from the top of the heap while the item counter is the successor to the last item that was pulled.
The item are stamped with a 32-bit unsigned counter by the hardware that generates them. There are several thousand items per second, and after a few days the counter wraps around. How do I handle this without switching to 64-bit counters? The program needs to be able to run indefinitely.
[Edit]
One idea I had is that, since the heap is limited in size to a few million items, I can modify the heap comparator to check the difference between the counters being compared and set a threshold of say half the maximum value of the unsigned, which if exceeded would be taken to assume a wraparound has occurred. The downside is the overhead of an extra conditional per each item checked in heap operations, and I don't know if there's some way to reduce it to a combination of subtraction/cast/etc. with just a single comparison.
How about using a 2nd queue. The insert operation switches on wrap and popping switches when current queue is empty, or just use a flag for the active queue