- Generated by
1.9.8
|
CX Framework
Cross-platform C utility framework
|
Data Structures | |
| struct | PrQueue |
Typedefs | |
| typedef enum PrqGrowthEnum | PrqGrowth |
| How much a dynamic PrQueue grows or shrinks by when it resizes. | |
| typedef struct PrQueue | PrQueue |
Enumerations | |
| enum | PrqGrowthEnum { PRQ_Grow_None = 1 , PRQ_Grow_25 , PRQ_Grow_50 , PRQ_Grow_100 , PRQ_Grow_150 , PRQ_Grow_200 } |
| How much a dynamic PrQueue grows or shrinks by when it resizes. More... | |
Functions | |
| void | prqInitFixed (PrQueue *prq, uint32 sz) |
| void | prqInitDynamic (PrQueue *prq, uint32 minsz, uint32 targetsz, uint32 maxsz, PrqGrowth growth, PrqGrowth shrink) |
| bool | prqDestroy (PrQueue *prq) |
| bool | prqPush (PrQueue *prq, void *ptr) |
| void * | prqPop (PrQueue *prq) |
| bool | prqCollect (PrQueue *prq) |
| uint32 | prqCount (PrQueue *prq) |
| void * | prqPeek (PrQueue *prq, uint32 n) |
A thread-safe, lock-free, optionally growable ring buffer of pointers. Multiple threads can push and pop at the same time.
PrQueue is low-level plumbing for building other concurrent structures, such as containers or a work queue, rather than a general-purpose collection to reach for directly. It moves only raw void* pointers - it never dereferences, allocates, frees, or copies whatever they point to. All lifetime management of the pointed-to data is the caller's responsibility.
NULL may never be pushed into the queue. prqPop() uses NULL as the "queue is empty" sentinel, so inserting one is an error.
Pushing a pointer transfers ownership of it to the queue - don't touch it again after a successful prqPush(). Popping transfers ownership back to the caller.
A fixed queue never grows, and prqPush() simply fails when it's full. A dynamic queue grows toward its target size under load and shrinks back within its bounds, but every push and pop on a dynamic queue pays extra atomic bookkeeping to guard against a segment being freed out from under it, often close to double the atomic operations of a fixed queue doing the same work. Prefer a fixed queue whenever there's a defensible upper bound on depth; reach for dynamic only when the depth genuinely can't be bounded.
Pushing and popping are lock-free in the classical sense: a thread that suspends or terminates in the middle of an operation cannot corrupt the queue or permanently block other threads, though it can cost performance until it clears.
Garbage collection (prqCollect()) is the one exception. It reclaims buffer segments that were retired when a dynamic queue grew, and it does use a lock - but that lock never blocks the caller: if it can't be acquired, prqCollect() returns immediately instead of waiting. Call it opportunistically at natural idle points, such as a consumer thread about to go to sleep. GC is not required for correctness; a queue that never runs GC keeps working, it just holds on to retired segments and wastes memory after growth events. A thread that stalls in the middle of a push also blocks GC from pruning until it clears, for the same reason. Fixed queues never grow, so they never need GC.
Pushes from a single thread are popped in order, as long as a single thread (not necessarily the same one) pops them sequentially. Across multiple threads, ordering is only best-effort: pushes and pops generally complete in something close to real-time order, but operations happening at nearly the same time on different threads may be reordered slightly. Don't build anything that needs strict global ordering on top of this queue; rely only on the per-pair FIFO guarantee.
Lock-free pointer FIFO queue
Access it only through the prq* functions - there is no supported direct field access.
| enum PrqGrowthEnum |
How much a dynamic PrQueue grows or shrinks by when it resizes.
| bool prqCollect | ( | PrQueue * | prq | ) |
Run one garbage collection cycle on the queue
Reclaims buffer segments that were retired by a previous growth event. Never blocks: if the internal GC lock is already held by another thread, this returns immediately without doing anything. Call it opportunistically, such as from a consumer thread that is about to go idle.
Not needed for correctness, and a no-op on a fixed queue, which never retires segments.
| prq | Queue to run a GC cycle on |
| uint32 prqCount | ( | PrQueue * | prq | ) |
Get an estimated count of items in the queue
This is only an estimate, and its accuracy drops the busier the queue is. Use prqPop() returning NULL as the authoritative test for "empty," not a count of zero from this function.
| prq | Queue to inspect |
| bool prqDestroy | ( | PrQueue * | prq | ) |
Destroy a PrQueue and release its resources
Fails if the queue still holds any entries, since this is a low-level API with no idea what the stored pointers mean or how to clean them up. The caller must pop and dispose of everything, and make sure no thread is still pushing, before calling this.
| prq | Queue to destroy |
| void prqInitDynamic | ( | PrQueue * | prq, |
| uint32 | minsz, | ||
| uint32 | targetsz, | ||
| uint32 | maxsz, | ||
| PrqGrowth | growth, | ||
| PrqGrowth | shrink | ||
| ) |
Initialize a growable PrQueue
The queue starts at minsz slots, grows toward targetsz (and up to maxsz) as it fills, and shrinks back down again as load drops. growth and shrink control how large each resize step is.
Always succeeds, or asserts.
| prq | Pointer to uninitialized queue structure |
| minsz | Minimum and initial size, in pointer slots |
| targetsz | Size the queue tries to reach under load |
| maxsz | Maximum size it will ever grow to |
| growth | How much to grow by at a time |
| shrink | How much to shrink by at a time |
| void prqInitFixed | ( | PrQueue * | prq, |
| uint32 | sz | ||
| ) |
Initialize a fixed-size PrQueue
The queue never grows past sz slots; prqPush() fails once it is full. This is the cheaper of the two flavors to operate, and the one to prefer whenever the maximum depth is known ahead of time.
Always succeeds, or asserts.
| prq | Pointer to uninitialized queue structure |
| sz | Fixed capacity, in pointer slots |
| void * prqPeek | ( | PrQueue * | prq, |
| uint32 | n | ||
| ) |
Fetch a copy of the nth pointer in the queue without removing it
| prq | Queue to inspect |
| n | Index of the item to fetch, starting from the head of the queue |
| void * prqPop | ( | PrQueue * | prq | ) |
Pop a pointer from the queue
| prq | Queue to pop from |
| bool prqPush | ( | PrQueue * | prq, |
| void * | ptr | ||
| ) |
Push a pointer into the queue
ptr must not be NULL. On success, the queue owns the pointer; don't touch it again until it comes back out of a prqPop() call.
| prq | Queue to push into |
| ptr | Pointer to push. Must not be NULL |
1.9.8