Version 1.3 of ai05s/ai05-0159-1.txt

Unformatted version of ai05s/ai05-0159-1.txt version 1.3
Other versions for file ai05s/ai05-0159-1.txt

!standard A.18.24          09-10-15 AI05-0159-1/02
!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;
[ARG]
Any interest in a Peek?
Conditional deque:
procedure Dequeue
(Container : in out Queue;
Element : out Element_Type; Available : out Boolean) is abstract;
[END ARG]
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
-- not specified by the language
end Ada.Containers.Unbounded_Queues;
Is_Full always returns False, because storage for new items is allocated dynamically.
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
-- not specified by the language
end Ada.Containers.Bounded_Queues;
The type Queue needs finalization if and only type Element_Type needs finalization.
[ARG] Is the above what we want? [End ARG]
Is_Full returns True when the number of elements that have been enqueued equals the Capacity; otherwise it returns False.
Implementation Advice
Bounded queue objects should be implemented without implicit pointers or dynamic allocation.
A.18.26 Containers.Unbounded_Priority_Queues
Static Semantics
The language-defined generic package Containers.Unbounded_Priority_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 (<>); 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
-- not specified by the language
end Ada.Containers.Unbounded_Priority_Queues;
[ARG]
We might need to refactor this description, so that it applies to both priority queue forms.
[Editor's note: Well, either that or duplicate it in the bounded form. Doing neither is just wrong.]
[END ARG]
Two elements E1 and E2 are equivalent if both E1 < E2 and E2 < E1 return False, using the generic formal "<" operator for elements.
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.
[ARG]
Do we need that last sentence?
[END ARG]
If the value of an element stored in a set is changed other than by an operation in this package such that "<" gives a different result, the behavior of this package is unspecified.
Enque inserts an item according to the order specified by the generic formal "<" operator. If the queue already contains an element equivalent to New_Item, then the new item is inserted after existing equivalent elements.
Is_Full always returns False, because storage for new items is allocated dynamically.
A.18.27 Containers.Bounded_Priority_Queues
The language-defined generic package Containers.Bounded_Priority_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 (<>); 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
-- not specified by the language
end Ada.Containers.Bounded_Priority_Queues;
The type Queue needs finalization if and only type Element_Type needs finalization.
[ARG] Is the above what we want? [End ARG]
Is_Full returns True when the number of elements that have been enqueued equals the Capacity; otherwise it returns False.
Implementation Advice
Bounded priority queue objects should be implemented without implicit pointers or dynamic allocation.
!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