1. Fixed-length queues

1.1. Introduction

.intro: This is the design of the ABQ module, which implements a fixed-length queue of small objects.

.readership: This document is intended for any MM developer.

.name: The name ABQ originally stood for “Available Block Queue” as the module is used by the MVT pool.

1.2. Requirements

.req.push: Clients can efficiently push new elements onto the queue.

.req.pop: Clients can efficiently pop elements from the queue.

.req.empty: Clients can efficiently test whether the queue is empty.

.req.abstract: The ABQ module does not know anything about the elements in the queue other than their size.

.req.delete: Clients can delete elements from the queue. (Note: not necessarily efficiently.)

.req.iterate: Clients can iterate over elements in the queue.

1.3. Interface

ABQStruct *ABQ

ABQ is the type of a queue. It is an alias for ABQStruct *. ABQStruct is defined in the header so that it can be inlined in client structures: clients must not depend on its implementation details.

ABQInit(Arena arena, ABQ abq, void *owner, Count elements, Size elementSize)

Initialize the queue abq. The parameter arena is the arena whose control pool should be used to allocate the memory for the queue; owner is passed to MeterInit() for the statistics; elements is the maximum number of elements that can be stored in the queue; and elementSize is the size of each element.

void ABQFinish(Arena arena, ABQ abq)

Finish abq and free all resources associated with it.

Bool ABQPush(ABQ abq, void *element)

If the queue is full, leave it unchanged and return FALSE. Otherwise, push element on to the queue and return TRUE.

Bool ABQPop(ABQ abq, void *elementReturn)

If the queue is empty, return FALSE. Otherwise, copy the first element on the queue into the memory pointed to by elementReturn, remove the element from the queue, and return TRUE.

Bool ABQPeek(ABQ abq, void *elementReturn)

If the queue is empty, return FALSE. Otherwise, copy the first element on the queue into the memory pointed to by elementReturn and return TRUE. (This is the same as ABQPop() except that the queue is unchanged.)

Bool ABQIsEmpty(ABQ abq)

If the queue is empty, return TRUE, otherwise return FALSE.

Bool ABQIsFull(ABQ abq)

If the queue is full, return TRUE, otherwise return FALSE.

Count ABQDepth(ABQ abq)

Return the number of elements in the queue.

Bool (*ABQVisitor)(Bool *deleteReturn, void *element, void *closure)

A callback function for ABQIterate(). The parameter element is an element in the queue, and closure is the value originally passed to ABQIterate(). This function must set *deleteReturn to FALSE if element must be kept in the queue, or TRUE if element must be deleted from the queue. It must return TRUE if the iteration must continue, or FALSE if the iteration must stop after processing element.

void ABQIterate(ABQ abq, ABQVisitor visitor, void *closure)

Call visitor for each element in the queue, passing the element and closure. See ABQVisitor for details.