CVS difference for ai05s/ai05-0159-1.txt
--- ai05s/ai05-0159-1.txt 2010/04/30 02:23:22 1.8
+++ ai05s/ai05-0159-1.txt 2010/05/20 03:54:01 1.9
@@ -1,4 +1,4 @@
-!standard A.18.24 10-04-12 AI05-0159-1/05
+!standard A.18.24 10-05-10 AI05-0159-1/06
!class Amendment 05-10-24
!status work item 10-04-29
!status ARG Approved 11-0-0 10-02-27
@@ -20,10 +20,13 @@
!proposal
-Add a synchronized interface and four implementations of task-safe queues.
-We suggest adding both regular queues and priority queues. In addition, there
-are bounded and unbounded versions of both kinds of queues.
+Add a synchronized interface and four implementations of task-safe queues. We
+have both regular queues and priority queues. There are bounded and unbounded
+versions of both kinds of queues.
+In addition, add another interface for indefinite queues, with two
+implementations: unbounded regular queues and priority queues.
+
!wording
A.18.23 Containers.Synchronized_Queue_Interfaces
@@ -64,11 +67,11 @@
(Container : in out Queue;
New_Item : Element_Type) is abstract;
-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; otherwise Enqueue does not block.
-In any case, it then copies New_Item onto the queue.
+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;
+otherwise Enqueue does not block. In any case, it then copies New_Item onto the
+queue.
procedure Dequeue
(Container : in out Queue;
@@ -92,22 +95,31 @@
Static Semantics
-The language-defined generic package
-Containers.Unbounded_Synchronized_Queues provides type Queue, which
-implements the interface type Containers.Synchronized_Queue_Interfaces.Queue.
+The language-defined generic package Containers.Unbounded_Synchronized_Queues
+provides type Queue, which implements the interface type
+Containers.Synchronized_Queue_Interfaces.Queue.
+with System;
with Ada.Containers.Synchronized_Queue_Interfaces;
generic
with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>);
+ Default_Ceiling: System.Any_Priority := System.Priority'Last;
package Ada.Containers.Unbounded_Synchronized_Queues is
pragma Preelaborate;
- type Queue is synchronized new Queue_Interfaces.Queue with private;
+ protected type Queue (Ceiling: System.Any_Priority := Default_Ceiling) is
+ new Queue_Interfaces.Queue with
+ pragma Priority(Ceiling);
+
+ entry Enqueue(Container: in out Queue; New_Item: Element_Type);
+ entry Dequeue(Container: in out Queue; Element: out Element_Type);
+
+ private
+ -- not specified by the language
+ end Queue;
private
-
-- not specified by the language
-
end Ada.Containers.Unbounded_Synchronized_Queues;
The type Queue is used to represent task-safe queues. The type Queue needs
@@ -115,39 +127,53 @@
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.
+AARM Ramification: Enqueue never blocks; if more storage is needed for a new
+element, it is allocated dynamically.
A.18.25 Containers.Bounded_Synchronized_Queues
Static Semantics
-The language-defined generic package
-Containers.Bounded_Synchronized_Queues provides type Queue, which
-implements the interface type Containers.Synchronized_Queue_Interfaces.Queue.
+The language-defined generic package Containers.Bounded_Synchronized_Queues
+provides type Queue, which implements the interface type
+Containers.Synchronized_Queue_Interfaces.Queue.
+with System;
with Ada.Containers.Synchronized_Queue_Interfaces;
generic
with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>);
+ Default_Capacity : Count_Type := 1;
+ Default_Ceiling: System.Any_Priority := System.Priority'Last; package Ada.Containers.Bounded_Synchronized_Queues is
package Ada.Containers.Bounded_Synchronized_Queues is
- pragma Pure;
+ pragma Preelaborate;
- type Queue (Capacity : Count_Type) is
- synchronized new Queue_Interfaces.Queue with private;
+ protected type Queue
+ (Capacity : Count_Type := Default_Capacity;
+ Ceiling: System.Any_Priority := Default_Ceiling) is
+ new Queue_Interfaces.Queue with
+ pragma Priority(Ceiling);
+
+ entry Enqueue(Container: in out Queue; New_Item: Element_Type);
+ entry Dequeue(Container: in out Queue; Element: out Element_Type);
+
+ private
+ -- not specified by the language
+ end Queue;
private
-
-- not specified by the language
-
end Ada.Containers.Bounded_Synchronized_Queues;
-The type Queue is used to represent task-safe queues. The type Queue needs
-finalization if and only if type Element_Type needs finalization.
+The semantics are the same as for Unbounded_Synchronized_Queues,
+except:
-The capacity for instances of type Queue is bounded and specified
-by the discriminant Capacity.
+ - The type Queue needs finalization (see 7.6) if and only if Element_Type
+ needs finalization.
+ - The capacity for instances of type Queue is bounded and specified by the
+ discriminant Capacity.
+
AARM Ramification: Since this type has a bounded capacity, Enqueue might block
if the queue is full.
@@ -161,24 +187,42 @@
Static Semantics
-The language-defined generic package
-Containers.Unbounded_Priority_Queues provides type Queue, which
-implements the interface type Containers.Synchronized_Queue_Interfaces.Queue.
+The language-defined generic package Containers.Unbounded_Priority_Queues
+provides type Queue, which implements the interface type
+Containers.Synchronized_Queue_Interfaces.Queue.
+with System;
with Ada.Containers.Synchronized_Queue_Interfaces;
generic
with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>);
- with function Before
+ type Queue_Priority is private;
+ with function Get_Priority
+ (Element: Queues.Element_Type) return Queue_Priority is <>;
+ with function "<"
(Left, Right : Queues.Element_Type) return Boolean is <>;
+ Default_Ceiling: System.Any_Priority := System.Priority'Last;
package Ada.Containers.Unbounded_Priority_Queues is
pragma Preelaborate;
- type Queue is synchronized new Queue_Interfaces.Queue with private;
+ protected type Queue
+ (Ceiling: System.Any_Priority := Default_Ceiling) is
+ new Queue_Interfaces.Queue with
+ pragma Priority(Ceiling);
+
+ entry Enqueue(Container: in out Queue; New_Item: Element_Type);
+ entry Dequeue(Container: in out Queue; Element: out Element_Type);
+
+ entry Dequeue_Only_High_Priority
+ (Container : in out Queue;
+ Minimum_Priority : Queue_Priority;
+ Element : out Element_Type);
+
+ private
+ -- not specified by the language
+ end Queue;
private
-
-- not specified by the language
-
end Ada.Containers.Unbounded_Priority_Queues;
The type Queue is used to represent task-safe priority queues. The type Queue
@@ -186,79 +230,97 @@
The capacity for instances of type Queue is unbounded.
+Two elements E1 and E2 are equivalent if Get_Priority(E1) < Get_Priority(E2) and
+Get_Priority(E2) < Get_Priority(E1) both return False.
+
+Enqueue inserts an item according to the order specified by the "<" function. If
+the queue already contains elements equivalent to New_Item, then it is inserted
+after the existing equivalent elements.
+
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.
-
-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.
+Dequeue_Only_High_Priority is the same as Dequeue, except that it blocks until
+the element E at the head of the queue satisfies not (Get_Priority(E) <
+Minimum_Priority).
+
+The actual functions for Get_Priority and "<" are expected to return the same
+value each time they are called with the same actuals, and should not modify
+their actuals. "<" 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.
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.Synchronized_Queue_Interfaces.Queue.
+Static Semantics
+
+The language-defined generic package Containers.Bounded_Priority_Queues provides
+type Queue, which implements the interface type
+Containers.Synchronized_Queue_Interfaces.Queue.
+with System;
with Ada.Containers.Synchronized_Queue_Interfaces;
generic
with package Queue_Interfaces is new Ada.Containers.Synchronized_Queue_Interfaces (<>);
- with function Before
- (Left, Right : Queues.Element_Type) return Boolean;
+ type Queue_Priority is private;
+ with function Get_Priority
+ (Element: Queues.Element_Type) return Queue_Priority is <>;
+ with function "<"
+ (Left, Right : Queues.Element_Type) return Boolean is <>;
+ Default_Capacity : Count_Type := 1;
+ Default_Ceiling: System.Any_Priority := System.Priority'Last;
package Ada.Containers.Bounded_Priority_Queues is
- pragma Pure;
+ pragma Preelaborate;
- type Queue (Capacity : Count_Type) is
- synchronized new Queue_Interfaces.Queue with private;
+ protected type Queue
+ (Capacity : Count_Type := Default_Capacity;
+ Ceiling: System.Any_Priority := Default_Ceiling) is
+ new Queue_Interfaces.Queue with
+ pragma Priority(Ceiling);
+
+ entry Enqueue(Container: in out Queue; New_Item: Element_Type);
+ entry Dequeue(Container: in out Queue; Element: out Element_Type);
+
+ entry Dequeue_Only_High_Priority
+ (Container : in out Queue;
+ Minimum_Priority : Queue_Priority;
+ Element : out Element_Type);
+
+ private
+ -- not specified by the language
+ end Queue;
private
-
-- not specified by the language
-
end Ada.Containers.Bounded_Priority_Queues;
+The semantics are the same as for Unbounded_Priority_Queues, except:
-The type Queue is used to represent task-safe priority queues. The type Queue
-needs finalization if and only if type Element_Type needs finalization.
+ - The type Queue needs finalization (see 7.6) if and only if Element_Type
+ needs finalization.
-The capacity for instances of type Queue is bounded and specified
-by the discriminant Capacity.
+ - 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
-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.
+AARM Ramification: Since this type has a bounded capacity, Enqueue might block
+if the queue is full.
Implementation Advice
Bounded priority queue objects should be implemented without implicit
pointers or dynamic allocation.
+A.18.28 Indefinite Synchronized Queues
+
+There are three generic packages
+Containers.Indefinite_Synchronized_Queue_Interfaces,
+Containers.Indefinite_Unbounded_Synchronized_Queues, and
+Containers.Indefinite_Unbounded_Priority_Queues. These are identical to
+Containers.Synchronized_Queue_Interfaces,
+Containers.Unbounded_Synchronized_Queues, and
+Containers.Unbounded_Priority_Queues, respectively, except that Element_Type is
+indefinite.
!discussion
@@ -1164,6 +1226,35 @@
not have an indefinite unbounded queue (other than that it doesn't fit well with
the interface definition -- maybe another reason that the interface isn't that
good of an idea??), and it surely is inconsistent.
+
+****************************************************************
+
+From: Bob Duff
+Date: Monday, May 10, 2010 10:50 AM
+
+Here's a new version of AI05-0159-1, modified as per the April 29 telephone
+meeting.
+
+Everything is heavily modified, except the !example, which I didn't change (nor
+even read).
+
+One way in which I disobeyed my marching orders: I gave the Ceiling priority
+discriminant a default even in the Bounded case. This requires giving a default
+for Capacity. I chose 1. Most users will want to specify some other value, but
+I don't see that as a problem. Objections?
+
+There are two levels of default -- you pass in a Ceiling (and Capacity in the
+bounded case) as generic formals with defaults. Then these are used as the
+default for the discriminant(s).
+
+Anyway, a single-element queue is not entirely nonsensical.
+
+I also tried to remove some duplicated verbiage. For example, the "interfaces"
+part says that Enqueue blocks if and only of the thing is bounded and is full.
+We don't need to mention that again in AARM notes for the concrete types, which
+are only a small distance away.
+
+[This is version /06 - Editor.]
****************************************************************
Questions? Ask the ACAA Technical Agent