!standard A.18.24 09-10-18 AI05-0159-1/03 !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 Num_In_Use (Container : Queue) return Count_Type is abstract; function Max_In_Use (Container : Queue) return Count_Type is abstract; end Ada.Containers.Queues; [ARG] Any interest in a Peek? (This was suggested on ada-comment.) Could also have Peek_First (Peek_Head), Peek_Last (Peak_Tail). Something like: procedure Peek_Head (Container : Queue; Element : out Element_Type; Available : out Boolean); procedure Peek_Tail (Container : Queue; Element : out Element_Type; Available : out Boolean); [END ARG] procedure Enqueue (Container : in out Queue; New_Item : Element_Type) is abstract; Copies New_Item onto the tail of the queue. If the number of existing elements equals the capacity, then Enqueue waits on the entry for storage to become available. procedure Dequeue (Container : in out Queue; Element : out Element_Type) is abstract; Returns a copy of the element at the head of the queue, and removes it from the container. If the queue is empty, then Dequeue waits on the entry for an item to become available. function Num_In_Use (Container : Queue) return Count_Type is abstract; Returns the number of elements currently in the queue. function Max_In_Use (Container : Queue) return Count_Type is abstract; Returns the maximum number of elements that have been in the queue at any one time. 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; [ARG] We need to say something about Enqueue never waiting for storage. Not sure what, though - RLB [End ARG] 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] We probably need some wording to tie the Capacity here with the lower case "capacity" given in the interface. Maybe we need to define capacity better in the interface. - RLB [End ARG] 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 Before (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; Two elements E1 and E2 are equivalent if both Before (E1, E2) and Before (E2, E1) return False, using the generic formal function Before. Enqueue inserts an item according to the order specified by the generic formal Before operation. If the queue already contains elements equivalent to New_Item, then it is inserted after the existing equivalent elements. The actual function for the generic formal function Before of Unbounded_Priority_Queues is expected to return the same value each time it is called with a particular pair of element values. It should define a strict weak ordering relationship (see A.18); it should not modify the elements. If the actual for Before behaves in some other manner, the behavior of Unbounded_Priority_Queues is unspecified. How many times Enqueue calls Before is unspecified. 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. Two elements E1 and E2 are equivalent if both Before (E1, E2) and Before (E2, E1) return False, using the generic formal function Before. Enqueue inserts an item according to the order specified by the generic formal Before operation. If the queue already contains elements equivalent to New_Item, then it is inserted after the existing equivalent elements. The actual function for the generic formal function Before of Bounded_Priority_Queues is expected to return the same value each time it is called with a particular pair of element values. It should define a strict weak ordering relationship (see A.18); it should not modify the elements. If the actual for Before behaves in some other manner, the behavior of Bounded_Priority_Queues is unspecified. How many times Enqueue calls Before is unspecified. 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 ****************************************************************