Version 1.2 of ai05s/ai05-0159-1.txt
!standard A.18.24 09-06-02 AI05-0159-1/01
!class Amendment 05-10-24
!status work item 06-03-15
!status received 05-10-02
!priority Medium
!difficulty Hard
!subject Queue containers
!summary
(See proposal.)
!problem
The Ada 2005 containers only allow a single task to access them at a time,
leaving it to the users to manage access by multiple tasks. There is a
need for task-safe containers.
!proposal
Add task-safe queues to the set of containers.
!wording
A.18.23 Containers.Queues
The language-defined generic package Containers.Queues provides
interface type Queue, and a set of operations for that type.
Interface Queue specifies a first-in, first-out queue.
Static Semantics
The generic library package Containers.Queues has the following
declaration:
generic
type Element_Type is private;
package Ada.Containers.Queues is
pragma Pure;
type Queue is synchronized interface;
procedure Enqueue
(Container : in out Queue;
New_Item : Element_Type) is abstract;
pragma Implemented (Enqueue, By_Entry);
procedure Dequeue
(Container : in out Queue;
Element : out Element_Type) is abstract;
pragma Implemented (Dequeue, By_Entry);
function Is_Empty (Container : Queue) return Boolean is abstract;
function Is_Full (Container : Queue) return Boolean is abstract;
end Ada.Containers.Queues;
procedure Enqueue
(Container : in out Queue;
New_Item : Element_Type) is abstract;
Copies New_Item onto the tail of the queue. If Is_Full is True, then
Enqueue waits on the entry for storage to become available.
procedure Dequeue
(Container : in out Queue;
Element : out Element_Type) is abstract;
Removes the element at the head of the queue, and returns a copy of
the element. Is Is_Empty is True, then Dequeue waits on the entry for
an item to become available.
function Is_Empty (Container : Queue) return Boolean is abstract;
Returns True if Container contains items.
function Is_Full (Container : Queue) return Boolean is abstract;
Returns True if Container is able to contain more items.
A.18.24 Containers.Unbounded_Queues
Static Semantics
The language-defined generic package Containers.Unbounded_Queues
provides type Queue, which implements the interface type
Containers.Queues.Queue.
with Ada.Containers.Queues;
generic
with package Queues is new Ada.Containers.Queues (<>);
package Ada.Containers.Unbounded_Queues is
pragma Preelaborate;
type Queue is synchronized new Queues.Queue with private;
private
--
end Ada.Containers.Unbounded_Queues;
[Editor's comment: We need some wording here to describe how these work!
In particular, Is_Full is never true for one of these queues, right?]
A.18.25 Containers.Bounded_Queues
Static Semantics
The language-defined generic package Containers.Bounded_Queues
provides type Queue, which implements the interface type
Containers.Queues.Queue.
with Ada.Containers.Queues;
generic
with package Queues is new Ada.Containers.Queues (<>);
package Ada.Containers.Bounded_Queues is
pragma Pure;
type Queue (Capacity : Count_Type) is
synchronized new Queues.Queue with private;
private
--
end Ada.Containers.Bounded_Queues;
[Editor's comment: We need some wording here to describe how these work!
In particular, Is_Full becomes True only after Capacity items are
queued. We can't leave this to chance!]
A.18.26 Containers.Priority_Queues
The language-defined generic package Containers.Priority_Queues
provides interface type Queue, and a set of operations for that type.
Interface Queue specifies a queue that orders its elements per a
specified relation.
Static Semantics
The generic library package Containers.Priority_Queues has the
following declaration:
generic
type Element_Type is private;
[ARG]
Do we pass order relation here, or in child package?
One possible answer is that the order relation should be defined here
(in the root package), so that other generic packages (outside of this
subsystem) can import the order relation as a generic actual
parameter.
[END ARG]
package Ada.Containers.Priority_Queues is
pragma Pure;
type Queue is synchronized interface;
procedure Insert
(Container : in out Queue;
New_Item : Element_Type) is abstract;
pragma Implemented (Insert, By_Entry);
procedure Remove
(Container : in out Queue;
Element : out Element_Type) is abstract;
pragma Implemented (Remove, By_Entry);
[ARG]
We went back and forth during the meeting about the names to use here,
but I don't remember what names we finally settled on. Should
"Remove" be "Delete" or "Delete_First"?
[END ARG]
function Is_Empty (Container : Queue) return Boolean is abstract;
function Is_Full (Container : Queue) return Boolean is abstract;
end Ada.Containers.Priority_Queues;
The actual function for the generic formal function "<" on
Element_Type values is expected to return the same value each time it
is called with a particular pair of key values. It should define a
strict ordering relationship, that is, be irreflexive, asymmetric, and
transitive. If the actual for "<" behaves in some other manner, the
behavior of this package is unspecified. Which subprograms of this
package call "<" and how many times they call it, is unspecified.
If the value of an element stored in a set is changed other than by an
operation in this package such that at least one of "<" gives
different results, the behavior of this package is unspecified.
procedure Insert
(Container : in out Queue;
New_Item : Element_Type) is abstract;
Adds New_Item to Container, per the specified order. If Is_Full is
True, then Insert waits on the entry for storage to become available.
procedure Remove
(Container : in out Queue;
Element : out Element_Type) is abstract;
Removes the element at the head of the queue, and returns a copy of
the element. Is Is_Empty is True, then Remove waits on the entry for
an item to become available.
function Is_Empty (Container : Queue) return Boolean is abstract;
Returns True if Container contains items.
function Is_Full (Container : Queue) return Boolean is abstract;
Returns True if Container is able to contain more items.
A.18.27 Containers.Unbounded_Priority_Queues
Static Semantics
The language-defined generic package
Containers.Unbounded_Priority_Queues provides type Queue, which
implements the interface type Containers.Priority_Queues.Queue.
with Ada.Containers.Priority_Queues;
generic
with package Queues is new Ada.Containers.Priority_Queues (<>);
with function "<"
(Left, Right : Queues.Element_Type) return Boolean is <>;
package Ada.Containers.Unbounded_Priority_Queues is
pragma Preelaborate;
type Queue is synchronized new Queues.Queue with private;
private
--
end Ada.Containers.Unbounded_Priority_Queues;
A.18.28 Containers.Bounded_Priority_Queues
Static Semantics
The language-defined generic package
Containers.Bounded_Priority_Queues provides type Queue, which
implements the interface type Containers.Priority_Queues.Queue.
with Ada.Containers.Priority_Queues;
generic
with package Queues is new Ada.Containers.Queues (<>);
with function "<"
(Left, Right : Queues.Element_Type) return Boolean is <>;
package Ada.Containers.Bounded_Priority_Queues is
pragma Pure;
type Queue (Capacity : Count_Type) is
synchronized new Queues.Queue with private;
private
--
end Ada.Containers.Bounded_Priority_Queues;
!discussion
We considered making protected forms of all of the existing containers, but
determined that there are various problems with such an approach:
(1) What kind of protection is needed (multiread, single write vs. multi anything)?
(2) Some of the operations (especially those with callbacks) could potentially
deadlock. How do we handle those cases (allow a single task to do anything while
it holds the lock vs. always locking).
(3) Can we actually do better performance-wise than the user wrapping the
operations that they need? Note that the existing containers are not potentially
blocking, so they can be called from protected operations. A well-designed
protected type will have much better abstraction than anything we could provide,
and probably would not have as large a performance cost.
Thus, we decided to provide task-safe queue abstractions (which are commonly
needed) and let the users create any others that they need.
!example
!ACATS test
ACATS Tests are needed for these new packages.
!appendix
****************************************************************
Questions? Ask the ACAA Technical Agent