CVS difference for ai05s/ai05-0159-1.txt
--- ai05s/ai05-0159-1.txt 2009/10/23 06:06:31 1.5
+++ ai05s/ai05-0159-1.txt 2009/12/11 07:15:33 1.6
@@ -1,4 +1,4 @@
-!standard A.18.24 09-10-18 AI05-0159-1/03
+!standard A.18.24 09-11-08 AI05-0159-1/04
!class Amendment 05-10-24
!status work item 06-03-15
!status received 05-10-02
@@ -22,21 +22,21 @@
!wording
-A.18.23 Containers.Queues
+A.18.23 Containers.Synchronized_Queues
-The language-defined generic package Containers.Queues provides
-interface type Queue, and a set of operations for that type.
+The language-defined generic package Containers.Synchronized_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:
+The generic library package Containers.Synchronized_Queues has the
+following declaration:
generic
type Element_Type is private;
-package Ada.Containers.Queues is
+package Ada.Containers.Synchronized_Queues is
pragma Pure;
type Queue is synchronized interface;
@@ -51,71 +51,51 @@
Element : out Element_Type) is abstract;
pragma Implemented (Dequeue, By_Entry);
- function Num_In_Use (Container : Queue) return Count_Type is abstract;
+ function Current_Use (Container : Queue) return Count_Type is abstract;
+ function Peak_Use (Container : Queue) return Count_Type is abstract;
- function Max_In_Use (Container : Queue) return Count_Type is abstract;
+end Ada.Containers.Synchronized_Queues;
-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.
+A queue type that implements this interface may have a bounded
+*capacity*. If the queue object has a bounded capacity,
+and the number of existing elements equals the capacity, then Enqueue
+blocks until storage becomes available. It then copies New_Item onto
+the tail of the queue.
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.
+If the queue is empty, then Dequeue blocks until an item becomes
+available. It then returns a copy of the element at the head of the
+queue, and removes it from the container.
- function Num_In_Use (Container : Queue) return Count_Type is abstract;
+ function Current_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;
+ function Peak_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
+A.18.24 Containers.Unbounded_Synchronized_Queues
Static Semantics
-The language-defined generic package Containers.Unbounded_Queues
-provides type Queue, which implements the interface type
-Containers.Queues.Queue.
+The language-defined generic package
+Containers.Unbounded_Synchronized_Queues provides type Queue, which
+implements the interface type Containers.Synchronized_Queues.Queue.
-with Ada.Containers.Queues;
+with Ada.Containers.Synchronized_Queues;
generic
- with package Queues is new Ada.Containers.Queues (<>);
-
-package Ada.Containers.Unbounded_Queues is
+ with package Queues is new Ada.Containers.Synchronized_Queues (<>);
+package Ada.Containers.Unbounded_Synchronized_Queues is
pragma Preelaborate;
type Queue is synchronized new Queues.Queue with private;
@@ -124,28 +104,30 @@
-- not specified by the language
-end Ada.Containers.Unbounded_Queues;
+end Ada.Containers.Unbounded_Synchronized_Queues;
-[ARG]
+The type Queue is used to represent queues. The type Queue needs
+finalization (see 7.6).
-We need to say something about Enqueue never waiting for storage. Not sure what, though - RLB
+The capacity for instances of type Queue is unbounded.
-[End ARG]
+AARM Ramification: Enqueue never blocks; if more storage is
+needed for a new element, it is allocated dynamically.
-A.18.25 Containers.Bounded_Queues
+A.18.25 Containers.Bounded_Synchronized_Queues
Static Semantics
-The language-defined generic package Containers.Bounded_Queues
-provides type Queue, which implements the interface type
-Containers.Queues.Queue.
+The language-defined generic package
+Containers.Bounded_Synchronized_Queues provides type Queue, which
+implements the interface type Containers.Synchronized_Queues.Queue.
-with Ada.Containers.Queues;
+with Ada.Containers.Synchronized_Queues;
generic
- with package Queues is new Ada.Containers.Queues (<>);
+ with package Queues is new Ada.Containers.Synchronized_Queues (<>);
-package Ada.Containers.Bounded_Queues is
+package Ada.Containers.Bounded_Synchronized_Queues is
pragma Pure;
type Queue (Capacity : Count_Type) is
@@ -154,19 +136,17 @@
private
-- not specified by the language
-
-end Ada.Containers.Bounded_Queues;
-The type Queue needs finalization if and only type
-Element_Type needs finalization.
+end Ada.Containers.Bounded_Synchronized_Queues;
-[ARG]
+The type Queue is used to represent queues. The type Queue needs
+finalization if and only type Element_Type needs finalization.
-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
+The capacity for instances of type Queue is bounded and specified
+by the discriminant Capacity.
-[End ARG]
+AARM Ramification: Since this type has a bounded capacity, Enqueue may block
+if the queue is full.
Implementation Advice
@@ -180,11 +160,11 @@
The language-defined generic package
Containers.Unbounded_Priority_Queues provides type Queue, which
-implements the interface type Containers.Queues.Queue.
+implements the interface type Containers.Synchronized_Queues.Queue.
-with Ada.Containers.Queues;
+with Ada.Containers.Synchronized_Queues;
generic
- with package Queues is new Ada.Containers.Queues (<>);
+ with package Queues is new Ada.Containers.Synchronized_Queues (<>);
with function Before
(Left, Right : Queues.Element_Type) return Boolean is <>;
@@ -199,6 +179,14 @@
end Ada.Containers.Unbounded_Priority_Queues;
+The type Queue is used to represent queues. The type Queue needs
+finalization (see 7.6).
+
+The capacity for instances of type Queue is unbounded.
+
+AARM Ramification: Enqueue never blocks; if more storage is
+needed for a new element, it is allocated dynamically.
+
Two elements E1 and E2 are equivalent if both Before (E1, E2) and
Before (E2, E1) return False, using the generic formal function
Before.
@@ -221,13 +209,13 @@
The language-defined generic package
Containers.Bounded_Priority_Queues provides type Queue, which
-implements the interface type Containers.Queues.Queue.
+implements the interface type Containers.Synchronized_Queues.Queue.
-with Ada.Containers.Queues;
+with Ada.Containers.Synchronized_Queues;
generic
- with package Queues is new Ada.Containers.Queues (<>);
- with function "<"
- (Left, Right : Queues.Element_Type) return Boolean is <>;
+ with package Queues is new Ada.Containers.Synchronized_Queues (<>);
+ with function Before
+ (Left, Right : Queues.Element_Type) return Boolean;
package Ada.Containers.Bounded_Priority_Queues is
pragma Pure;
@@ -241,9 +229,12 @@
end Ada.Containers.Bounded_Priority_Queues;
+
+The type Queue is used to represent queues. The type Queue needs
+finalization if and only type Element_Type needs finalization.
-The type Queue needs finalization if and only type
-Element_Type needs finalization.
+The capacity for instances of type Queue is bounded and specified
+by the discriminant Capacity.
Two elements E1 and E2 are equivalent if both Before (E1, E2) and
Before (E2, E1) return False, using the generic formal function
@@ -287,6 +278,105 @@
!example
+declare
+
+ -- First we create the queue interface.
+
+ package Widgets is
+ type Widget is new Integer; -- for example
+ ...
+ end Widgets;
+
+ package Widget_Queue_Types is
+ new Ada.Containers.Synchronized_Queues (Widgets.Widget);
+
+ -- Now we design an algorithm around our interface. Here
+ -- we have a set of assembly lines that fabricate widgets,
+ -- adding them to a common queue. We also have a task that
+ -- removes widgets from the queue for delivery.
+
+ task type Assembly_Line_Task
+ (Q : access Widget_Queue_Types.Queue'Class := null,
+ N : Natural := 0) -- number of widgets
+ is end;
+
+ function New_Assembly_Line_Task
+ (Q : not null access Widget_Queue_Types.Queue'Class;
+ N : Natural) return Assembly_Line_Task
+ is
+ begin
+ return T : Assembly_Line_Task (Q, N);
+ end New_Assembly_Line_Task;
+
+ type Assembly_Line_Task_Array is
+ array (Positive range <>) of Assembly_Line_Task;
+
+ task type Delivery_Service_Task
+ (Q : not null access Widget_Queue_Types.Queue'Class;
+ N : Natural) -- number of assembly lines
+ is end;
+
+ -- An assembly line task fabricates widgets until the
+ -- requisite number have been made, and then it puts a
+ -- distinguished value into the queue to indicate to
+ -- the delivery service that there are no more widgets
+ -- from this assembly line.
+
+ task body Assembly_Line_Task is
+ begin
+ for I in 1 .. N loop
+ delay 0.5;
+ Q.Enqueue (Widget (I));
+ end loop;
+
+ Q.Enqueue (Widget'(0)); -- no more widgets
+ end Assembly_Line_Task;
+
+ -- The delivery service task continually dequeues widgets
+ -- from the queue (dispensing widget objects as necessary),
+ -- and keeps track of how many assembly lines have
+ -- finished making widgets. When all of the assembly lines
+ -- are done, the delivery service task terminates.
+
+ task body Delivery_Service_Task is
+ W : Widget;
+ Done : Natural := 0;
+
+ begin
+ loop
+ Q.Dequeue (W);
+
+ if W > 0 then
+ Put_Line ("Delivering widget" & Widget'Image (W));
+ else
+ Done := Done + 1;
+ exit when Done >= N;
+ end if;
+ end loop;
+ end Delivery_Service_Task;
+
+ -- None of what we have done so far depends on any specific widget
+ -- queue type. Here we instantiate the unbounded queue package
+ -- for use as our widget queue object.
+
+ package Widget_Queues is
+ new Ada.Containers.Unbounded_Synchronized_Queues
+ (Queues => Widget_Queue_Types);
+
+ Q : aliased Widget_Queues.Queue;
+
+ -- Now we elaborate our assembly line and delivery service task
+ -- objects, binding them to the widget queue object.
+
+ Assembly_Lines : Assembly_Line_Task_Array (1 .. 5) :=
+ (others => New_Assembly_Line_Task (Q'Access, 10));
+
+ Delivery_Service : Delivery_Service_Task (Q'Access, Assembly_Lines'Length);
+
+begin -- activate tasks
+ null;
+end;
+
!ACATS test
ACATS Tests are needed for these new packages.
Questions? Ask the ACAA Technical Agent