1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
.. highlight:: none


.. index::
   pair: fixed-length queues; design

.. _design-abq:


Fixed-length queues
===================

.. mps:prefix:: design.mps.abq


Introduction
------------

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

:mps:tag:`readership` This document is intended for any MM developer.

:mps:tag:`name` The name ABQ originally stood for "Available Block Queue" as
the module is used by the MVT pool.


Requirements
------------

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

:mps:tag:`req.pop` Clients can efficiently pop elements from the queue.

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

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

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

:mps:tag:`req.iterate` Clients can iterate over elements in the queue.


Interface
---------

.. c:type:: ABQStruct *ABQ

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

.. c:function:: void 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 :c:func:`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.

.. c:function:: void ABQFinish(Arena arena, ABQ abq)

Finish ``abq`` and free all resources associated with it.

.. c:function:: Bool ABQPush(ABQ abq, void *element)

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

.. c:function:: Bool ABQPop(ABQ abq, void *elementReturn)

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

.. c:function:: Bool ABQPeek(ABQ abq, void *elementReturn)

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

.. c:function:: Bool ABQIsEmpty(ABQ abq)

If the queue is empty, return :c:macro:`TRUE`, otherwise return :c:macro:`FALSE`.

.. c:function:: Bool ABQIsFull(ABQ abq)

If the queue is full, return :c:macro:`TRUE`, otherwise return :c:macro:`FALSE`.

.. c:function:: Count ABQDepth(ABQ abq)

Return the number of elements in the queue.

.. c:type:: Bool (*ABQVisitor)(Bool *deleteReturn, void *element, void *closure)

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

.. c:function:: 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.