A.18.30 The Generic Package Containers.Unbounded_Priority_Queues
Static Semantics
{
AI05-0159-1}
The language-defined generic package Containers.Unbounded_Priority_Queues
provides type Queue, which implements the interface type Containers.Synchronized_Queue_Interfaces.Queue.
{
AI12-0112-1}
with System;
with Ada.Containers.Synchronized_Queue_Interfaces;
generic
with package Queue_Interfaces
is
new Ada.Containers.Synchronized_Queue_Interfaces (<>);
type Queue_Priority
is private;
with function Get_Priority
(Element : Queue_Interfaces.Element_Type)
return Queue_Priority
is <>;
with function Before
(Left, Right : Queue_Priority)
return Boolean
is <>;
Default_Ceiling : System.Any_Priority := System.Priority'Last;
package Ada.Containers.Unbounded_Priority_Queues
with Preelaborate,
Nonblocking, Global =>
in out synchronized isDiscussion: {
AI12-0112-1}
For discussion on the reasons and meaning of the specifications of the
Global and Nonblocking aspects of this generic package, see the notes
on the specification of the Containers.Vectors package (see
A.18.2).
package Implementation is
... -- not specified by the language
end Implementation;
protected type Queue
(Ceiling : System.Any_Priority := Default_Ceiling)
with Priority => Ceiling
is
new Queue_Interfaces.Queue
with
overriding
entry Enqueue (New_Item :
in Queue_Interfaces.Element_Type);
overriding
entry Dequeue (Element :
out Queue_Interfaces.Element_Type);
{
AI05-0159-1}
{
AI05-0251-1}
not overriding
procedure Dequeue_Only_High_Priority
(At_Least :
in Queue_Priority;
Element :
in out Queue_Interfaces.Element_Type;
Success :
out Boolean);
{
AI12-0112-1}
overriding
function Current_Use
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
overriding
function Peak_Use
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
private
... -- not specified by the language
end Queue;
private
... -- not specified by the language
end Ada.Containers.Unbounded_Priority_Queues;
{
AI05-0159-1}
The type Queue is used to represent task-safe priority queues.
{
AI05-0159-1}
The capacity for instances of type Queue is unbounded.
{
AI05-0159-1}
Two elements
E1 and
E2 are equivalent if Before(Get_Priority(
E1),
Get_Priority(
E2)) and Before(Get_Priority(
E2), Get_Priority(
E1))
both return False.
{
AI05-0159-1}
{
AI05-0248-1}
The actual functions for Get_Priority and Before are expected to return
the same value each time they are called with the same actuals, and should
not modify their actuals. Before should define a strict weak ordering
relationship (see
A.18). If the actual functions
behave in some other manner, the behavior of Unbounded_Priority_Queues
is unspecified.
{
AI05-0159-1}
Enqueue inserts an item according to the order specified by the Before
function on the result of Get_Priority on the elements; Before should
return True if Left is to be inserted before Right. If the queue already
contains elements equivalent to New_Item, then it is inserted after the
existing equivalent elements.
Ramification: Enqueue never blocks; if
more storage is needed for a new element, it is allocated dynamically.
We don't need to explicitly specify that Queue needs finalization, because
it is visibly protected.
{
AI05-0159-1}
{
AI05-0251-1}
{
AI05-0262-1}
For a call on Dequeue_Only_High_Priority, if the head of the nonempty
queue is
E, and the function Before(At_Least, Get_Priority(
E))
returns False, then
E is assigned to Element and then removed
from the queue, and Success is set to True; otherwise, Success is set
to False and Element is unchanged.
Ramification: {
AI05-0251-1}
Unlike Dequeue, Dequeue_Only_High_Priority is not blocking; it always
returns immediately.
Reason: {
AI05-0251-1}
The use of Before is "backwards" so that it acts like ">="
(it is defined similarly to ">"); thus we dequeue only when
it is False.
Extensions to Ada 2005
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
