CVS difference for ai05s/ai05-0001-1.txt
--- ai05s/ai05-0001-1.txt 2008/10/25 04:53:13 1.3
+++ ai05s/ai05-0001-1.txt 2008/11/14 02:39:45 1.4
@@ -202,7 +202,7 @@
(Splice with one container also doesn't change)
[END ARG].
-The semantics of
+The semantics of
procedure Splice
(Target : in out List;
@@ -219,7 +219,7 @@
element at a time to be copied to the target and then immediately deleted from
source. [END ARG]
-The semantics of
+The semantics of
procedure Splice
(Target : in out List;
@@ -500,17 +500,17 @@
function Is_Full (Q : Queue) return Boolean is abstract;
-- [ARG] What about:
- --
+ --
-- procedure Enqueue
-- (Q : in out Queue;
-- New_Item : in Element_Type;
-- Existing : out Count_Type) is abstract;
- --
+ --
-- procedure Dequeue
-- (Q : in out Queue;
-- Element : out Element_Type;
-- Remaining : out Count_Type) is abstract;
- --
+ --
-- function Length (Q : Queue) return Count_Type is abstract;
--
-- [END ARG]
@@ -1180,16 +1180,16 @@
!from Bibb Latting 05-02-09
!keywords Containers, Storage Pools
!discussion
-
+
The capability to use a derivation of root_storage_pool with a container
is desired to provide flexibility in the management of the storage
underlying the container. This capability provides the opportunity for
the user to optimize memory allocation for a given application, work-around
fragmentation in the hardware mapping of memory, provide non-core memory
allocation of the container, or to comply with safety/security issues.
-
+
Please feel free to change the above discussion as desired.
-
+
****************************************************************
From: Tucker Taft
@@ -1647,13 +1647,13 @@
From: Matthew Heaney
Sent: Thursday, March 16, 2006 7:56 AM
-> (I'd hoped someone else would answer this, but since no one
+> (I'd hoped someone else would answer this, but since no one
> has, I'll take a stab at it...)
I sent him some email privately.
-
-> In any case, Move destroys all of the cursors; the language
-> defines them as "invalid", and any future use is erroneous.
+
+> In any case, Move destroys all of the cursors; the language
+> defines them as "invalid", and any future use is erroneous.
> (If the error was detected, you are lucky.)
In the GNAT case (that's the compiler he's using), the cursor is implemented
@@ -1663,8 +1663,8 @@
cursor-based operations do is compare the list pointer to the address of the
list parameter.
-> In this sense,
-> Move is very similar to destroying the container itself (say,
+> In this sense,
+> Move is very similar to destroying the container itself (say,
> by calling Unchecked_Deallocation on it).
Well, it's not quite as extreme as that, since the nodes haven't been
@@ -1674,10 +1674,10 @@
There is often a tradeoff between flexibility and safety, and Move is an
example where some flexibility was lost as a result of adding the checks.
-> But Move isn't intended for cases where you need to preserve
-> cursors. The four parameter Splice is designed for that, as
-> it returns the new cursor for where the element(s) are
-> inserted. If you want to preserve the original container,
+> But Move isn't intended for cases where you need to preserve
+> cursors. The four parameter Splice is designed for that, as
+> it returns the new cursor for where the element(s) are
+> inserted. If you want to preserve the original container,
> just use ":=".
You could use Splice (in fact that's what I told him), but it can get a
@@ -1700,14 +1700,14 @@
> Given the inherent insecurity with First()...Next(), is there a better
> iterator, such as the 'natural' extension of the For Loop construct
> to iterators ... eg:
->
+>
> for C in L loop
> ... do something using Element (C) or Update_Element(..)
> end loop;
-For what it is worth, I would point out that Ada is really a somewhat
-lower level language than Python. I find iterating awkward in Ada (and
-in many other languages, to a lesser or greater degree), but I often
+For what it is worth, I would point out that Ada is really a somewhat
+lower level language than Python. I find iterating awkward in Ada (and
+in many other languages, to a lesser or greater degree), but I often
find that, in Ada, an alternative such as:
declare
@@ -1727,7 +1727,7 @@
Sent: Monday, March 20, 2006 8:00 AM
> in Ada, an alternative such as:
->
+>
> declare
> procedure Mogrify (C : in Widget_Lists.Cursor) is
> begin
@@ -1736,7 +1736,7 @@
> begin
> Widget_Lists.Iterate (My_Widgets, Mogrify'Access);
> end;
->
+>
> alleviates the dangers of missing something vital out.
I fail to see what dangers it alleviates. I for one would much prefer to
@@ -1832,11 +1832,11 @@
Alwyn Barry wrote [forwarded by Randy Brukardt]:
-> ... What is particularly frustrating is that though iterate() is
+> ... What is particularly frustrating is that though iterate() is
> provided [effectively apply()], there is a lack of reduce() and map()
-> functions which would remove the need for the iterator functions to
-> access other variables outside the function in order to do their
-> task. These functions can easily be provided, but could have been
+> functions which would remove the need for the iterator functions to
+> access other variables outside the function in order to do their
+> task. These functions can easily be provided, but could have been
> included. ...
These functions (reduce and map) could not be so easily provided in Ada
@@ -1847,11 +1847,11 @@
as its generic parameter. In other words, they would be not be the
elegant one-liners that they are in Python.
-> ... Anyway, I've got around it by the old trick of having two
+> ... Anyway, I've got around it by the old trick of having two
> records, one the 'current' and one the 'backup' list and indexes, and
-> simply switching pointers. I used to do this in C, which I guess
-> says something about the elegance or otherwise of the solution. It
-> does save copying, but where speed is not really an issue it is a
+> simply switching pointers. I used to do this in C, which I guess
+> says something about the elegance or otherwise of the solution. It
+> does save copying, but where speed is not really an issue it is a
> pity there is not a better way. ...
This is the kind of solution that I would have adopted. I'm sure that it
@@ -1861,8 +1861,8 @@
Randy Brukardt replied:
-> The general answer is that you can't provide the solution to every
-> possible need, and keep things efficient. ... [if I had designed
+> The general answer is that you can't provide the solution to every
+> possible need, and keep things efficient. ... [if I had designed
> them, they would have worked quite differently!], but the real value
> here is that they're standard. There never was any intent that this
> version would be the final word in containers for Ada. ...
@@ -1885,10 +1885,10 @@
> For cases
> where there are large tasks to do, Iterate is great. For
-> single statements it is overkill.
+> single statements it is overkill.
-The library works by providing primitives that you can use to synthesize
-higher-level abstractions. Any "single statement" can be written as a
+The library works by providing primitives that you can use to synthesize
+higher-level abstractions. Any "single statement" can be written as a
generic and instantiated as necessary.
> What is particularly
@@ -1896,19 +1896,19 @@
> apply()], there is a lack of reduce() and map() functions
> which would remove the need for the iterator functions to
> access other variables outside the function in order to do
-> their task.
+> their task.
-Well this is just silly. Of *course* local functions "access variables
-outside the function" since otherwise there'd be little point in making
-them local. Ada has *always* worked this way; the container library
+Well this is just silly. Of *course* local functions "access variables
+outside the function" since otherwise there'd be little point in making
+them local. Ada has *always* worked this way; the container library
simply conforms to already-established language idioms.
> These functions can easily be provided, but
> could have been included.
-Yes of course, and that is by design. Obviously we didn't include
-everything. If you want a map function, then it's trivial to write it
-once and then keep reusing it. Here's one for arrays (which of course
+Yes of course, and that is by design. Obviously we didn't include
+everything. If you want a map function, then it's trivial to write it
+once and then keep reusing it. Here's one for arrays (which of course
could be generalized):
generic
@@ -1946,24 +1946,24 @@
> languages have included exactly so that the "dropped next()"
> errors do not occur. In regard to the other problem...
-What "other languages" are we speaking about? Ada is a low-level
-systems programming language. It is not a scripting language. In
+What "other languages" are we speaking about? Ada is a low-level
+systems programming language. It is not a scripting language. In
particular it is neither Perl nor Python.
-Ada's closest analog is C++. Anything you can do in the STL you can do
+Ada's closest analog is C++. Anything you can do in the STL you can do
in the Ada container library.
-We didn't even attempt to include a generic algorithms library too,
-since we were trying to keep the scope of the revision small. The
-simplest thing for you to do it write the generic algorithms you need
+We didn't even attempt to include a generic algorithms library too,
+since we were trying to keep the scope of the revision small. The
+simplest thing for you to do it write the generic algorithms you need
and reuse them as necessary.
> Splice() could be used, but there is no cursor update
-> with it.
+> with it.
-Of course there is cursor update with it. I don't know what you're
-talking about here. The Position parameter of the 4-parameter Splice is
-passed using inout mode, the purpose of which is to rebind the cursor
+Of course there is cursor update with it. I don't know what you're
+talking about here. The Position parameter of the 4-parameter Splice is
+passed using inout mode, the purpose of which is to rebind the cursor
from the old (source) list to the new (target) list.
> As Matthew Heaney points out in his reply, trying
@@ -1971,8 +1971,1627 @@
> once the item has moved, yet the new list does not contain
> the item so you cannot update the cursor before the splice).
-So you update the cursor *during* the call to Splice, by specifying the
+So you update the cursor *during* the call to Splice, by specifying the
cursor you want to rebind as the Position parameter.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, September 25, 2008 5:55 PM
+
+Following is my notes on the two days of containers meetings. Matt has his own
+set of notes that probably differ from mine. I made a quick pass thorough these
+notes to eliminate/clarify nonsense, but otherwise they are as I took them.
+
+A quick summary is that we agreed on the form and semantics of the bounded
+containers (as little as change is possible, but no pointers and no controlled
+types are expected to be used in the implementation of them so that that can be
+used in safety-critical environments). We looked at a design for shared
+(task-safe) queue abstractions, but concluded that there wasn't enough need for
+generalized task-safe containers. (Especially as there are as many meanings of
+"task-safe" as there are programmers.)
+
+We rejected storage-optimized variants of the containers, as they are
+insufficiently different from the basic containers.
+
+We also studied issues involved with defining containers for limited element
+types. This probably would need some language support, or intensive headstands
+by an implementer. We looked at some options for that language support.
+
+ Randy Brukardt.
+
+----------------
+
+Containers Meeting - September 22-23, 2008
+
+Present: Randy Brukardt, Bob Duff, Tucker Taft, Ed Schonberg, Matt Heaney.
+
+
+Who is the customer? "The programmer of the future".
+
+Why would someone not be able to use the existing containers? Restricted
+environments (no dynamic allocation, no finalization). Synchronization issues.
+
+Programs can add synchronization, so that is a secondary issue.
+
+Another dimension is limitedness.
+
+Limited,
+No dynamic allocation
+No finalization
+Synchronization
+
+New container types: achieve parity with C++ (multimaps, multisets).
+
+Surely No dynamic allocation is the most important issue.
+
+There is a meta-rule that the containers can be written in Ada.
+
+Tucker suggests that setting an address with the tampering bits could be use add
+detection of copying of these bits.
+
+Tucker is trying to order these kinds of containers.
+
+No dynamic allocation
+No controlled types
+
+Turning to protected (task-safe) containers. Bob wonders if there is any real
+value to wrapping these containers? But the shared queue is commonly wanted.
+Perhaps we should just invent a shared queue abstraction and provide that.
+
+Tucker wonders if a generic that protected a set of operations and provided a
+protected operation would work. The idea is the underlying storage would be
+provided by the formal, so that alternative storage mechanism could be used.
+
+We talk about limited containers. That brings up issues about control of
+finalization. The current containers do not have that. For instance, how can we
+use a constructor function in a limited bounded form. C++ has placement new for
+this. Tucker thinks that you could play games with storage pools to do that.
+
+We talk about bounded hash table. Matt wonders how you set the hash table size
+here, because it can't be calculated after the fact. Tucker suggests two
+discriminants (or formal parameter). Bob suggests that one could use a
+constructor function to calculate the discriminants (which could be private).
+
+Type Hash_Objects (Hash_Size, Element_Size : Integer) is record
+ H : Hash_Table (1..Hash_Size);
+ E : Element_Table (1..Element_Size); End record;
+
+Should these be discriminants? Per-object boundedness seems valuable. The
+discriminants would be visible, and you would need a subtype in order to be
+compose these (container of container).
+
+Thus, the bounded forms, will not be based on storage pools, just based on
+discriminants, specified on the object.
+
+Matt suggests another model where the memory is allocated in the package body.
+That seems too much like a heap implementation. Per-object makes much more
+sense.
+
+If we had done it on the instantiation, we would have the choice of for one
+object or for all objects. But we don't want to do that.
+
+We don't think assignment is too likely, so we believe that mismatching
+discriminants is not an issue.
+
+---
+
+Synchronized operations: multiple vs. single readers? Is a queue good enough, or
+should we make all of the containers protected? Tucker is against that, as there
+are many other things that you are likely to need to do.
+
+We have an aside about transactional memory.
+
+Tucker would like to try separating storage and protection aspects for a
+synchronized queue.
+
+---
+
+We go through Matt's list of issues.
+
+We discuss what happens with uninitialized elements. We have covered that for
+vectors; they're called empty elements, and accessing them is a bounded error.
+We should just follow this model; and not worry about last wishes.
+
+Bounded forms are non-limited; we'll look at limited forms later and separately.
+
+Ordered multisets: should we have them? Tucker asks this is a "bag"?
+Essentially, yes. It contains objects, possibly duplicated.
+
+What new operations are there? There are additional iterators for iterating over
+an equivalence set.
+
+Bob wonders if this makes more sense for multi-maps.
+
+Tucker wonders if Generic_Keys could be used for that; it offers a second
+equivalence class. Ed doesn't seem to understand what this is used for.
+
+Matt says that you end up having to have a second-level indirection to use the
+existing containers this way.
+
+A.18.8(87/2) shows that it is not intended for Generic_Keys to establish some
+other equivalence class. So Tucker's idea won't work.
+
+The difference between a set and a map is that the key exists in the data in the
+set, while it is separate in map.
+
+So lets look at a multimap. (That's a one-to-many mapping). Even better, let's
+have lunch.
+
+----
+
+Matt explains his uses for this Multimap/Multiset package. It still doesn't
+sound that fundamental.
+
+Tucker now suggests breaking the key into multiple pieces (the primary key and a
+disambiguating key). Then using Floor and Ceiling to iterate over the subrange.
+The uniqueness key would not necessarily participate in the ordering relation
+(nor is it very interesting).
+
+So it is obvious that we can use some extra memory to get the effect with the
+existing packages. The question is it worth it to have this container? Is it a
+lot of extra work (definitionally) compared to the existing containers?
+
+Matt prefers a multiset, others think a multimap is more important. We agree
+that this is lower priority than bounded, queues, and even limited is more
+important (Tucker notes that limited adds a new capability, multiset is just a
+bit easier).
+
+Moving on to "case-insensitive string hash and less operations". GNAT has those.
+
+How do this work? Just apply To_Upper or To_Lower. But which is used matters for
+">". Bob notes that Unix programmers would use To_Lower, and everyone else would
+use To_Upper. Matt says that he uses To_Lower.
+
+Tucker wonders if implementations would optimize this, that's the main reason to
+do it.
+
+Robert Dewar joins us and suggests that we simply try to do whatever C does for
+in similar functions (StrCaseCpy). But that doesn't seem to be standard.
+
+We originally dropped these because we thought that using a string map was
+better than having extra functions for all four kinds of strings.
+
+Robert says that going to lower is better, because there are lower case
+characters that have no upper characters. That gives you weird results.
+
+These are common enough that we should have them. Most uses would not care about
+the corner cases, and we should not let good enough to be killed off by best.
+
+No promises that Hash(Lower(Key)) = Insens_Hash(Key). Robert disagrees.
+
+Matt offers the question of storage optimized form. (He specifically mentions
+singly linked lists). Tucker says that they are just in the way most of the
+time. It's not that much of a savings in normal usage.
+
+Robert talks about a pointer that is always the xor of the forward/backward
+list. This scheme allows implementing a doubly linked list with only a single
+pointer. We think it might be possible to implement the existing package that
+way. Which means that potentially there is no savings at all from a singly
+linked list package.
+
+We don't think that storage optimized forms are that important. These would only
+be necessary on the bleeding edge, and there is no problem switching the
+implementation on their own. Do C++ have competing STLs based on performance
+characteristics?
+
+Moving to "more sort algorithms". Matt uses Heap Sort because it is stable and
+predictable.
+
+Bob wonders if we should have other sorts of sorting. He mentions a radix sort.
+That is not worthwhile. But this has little to do with generic that Matt
+proposed, that seems to be worthwhile. But it does not have much to do with
+anonymous arrays, so drop that part from the name. (That is, it is just
+"Generic_Sorting").
+
+Recursive data structures: Tucker again thinks its harder to figure out how to
+instantiate or use these packages than to write them yourself. No one disagrees.
+
+Should we be considering lock-free algorithms? That really belongs to a
+multicore group; we don't have the expertise for that. We really ought to have a
+multicore research group. If we are doing an Amendment, hopefully the ARG will
+set up one of those.
+
+We turn to discussion of "smart pointers".
+
+Function F return T_Access is
+ X : Auto_Ptr := Init(new T);
+Begin
+ ...
+ Return To_Access(X);
+End F;
+
+The idea is that it is a generic wrapper that adds this functionality.
+
+Tucker thinks that this belongs to the storage management realm, and this is
+really outside of the scope of this group. He's interested in it, but agrees
+with Randy's (old) opinion that this is probably the wrong level of abstraction.
+The ARG is already looking at this (lightly).
+
+We talk about lifetime of pointers. Randy talks about his problems in Claw with
+pointers that you want to have a defined lifetime and no more (that is, no
+copying).
+
+Tucker brings up another dimension: persistence. Passive partitions have this
+feature, but that was not the original idea of them. Anyway, pointers into the
+persistent area need lifetime information so we can find out when an object has
+become unreferenced by the program.
+
+Robert suggests using reference counts for this, but that doesn't work if you
+want to swap out a whole page: you'd have to find all of the reference counts
+that point in.
+
+Matt mentions iterator syntax "for each obj in collection". Bob mentions "Sather
+iterators"; Ed tries to find more about that on the web. It's in the ACM portal.
+In any case, this is an area of interest for future work. Randy notes he floated
+a proposal in 2005 (AC-0112).
+
+---
+
+We look at a bounded vector specification. Should we still have the Capacity and
+Reserve_Capacity? The function Capacity should be available for consistency.
+Reserve_Capacity should be gone, it makes no sense.
+
+But there is some sense to it; just ignored if smaller or same, raises
+Storage_Error if bigger. That's the same semantics as the Unbounded case, with
+less restrictions.
+
+Tucker asks what is the capacity of the vector objects that are returned from
+functions. Since these are constants, the smallest possible is fine. That would
+be annoying if it is later assigned.
+
+Tucker suggests something, but it doesn't work.
+
+Also, there is no need to constrain the discriminants subtype.
+
+Matt has Assign, which allows assigning objects with different capacity. That
+makes sense, some exception will be raised if the source doesn't fit in the
+target. Do nothing if Source = Target.
+
+He also has Copy, which changes the capacity of a object on the fly.
+
+What about Move? It is a destruction Copy; implement by copying Source to Target
+then zeroing Source.
+
+Buglet: Move should say something about the Capacity of Source afterwards. It
+could be zero. Bob suggests that we say that Reserve_Capacity (Source, 0) is
+called (that allows rounding up). This should have another AI (it needs to be
+done for all of the containers).
+
+Bob thinks he doesn't want Storage_Error raised here, as this is not running out
+of all memory. That is a big difference here, especially since the user can
+understand when they have run out. He thinks that it is very similar to a range
+1..10, and talking about 11. He would want to raise Constraint_Error.
+
+Tucker suggests that this is similar to Storage_Size on an access type. That
+raises Storage_Error even though memory is not exhausted.
+
+Tucker also suggests defining Capacity_Error.
+
+Merge is looked at, but it is decided that there is no problem.
+
+Moving to Bounded_Doubly_Linked_Lists.
+
+The list has to be implemented with indices, as pointers don't work in
+assignment. That has to be bitwise copy (remember, no controlled types are
+desired).
+
+Matt shows us a poor man's initialization and finalization scheme, we decided we
+don't want it.
+
+Splice makes sense, but it probably requires some changes.
+
+Merge also makes sense and should be included.
+
+Maps. Matt wants the hash table to be a prime number. If you allow specifying
+it, that no longer works. It should be OK for this to be true.
+
+Function Init (Capacity : Count_Type; Hash_Table_Length : Hash_Type := 0)
+ return Map;
+
+The problem is that these things are not very static looking (and probably not
+static at all; it would be on the secondary stack at best).
+
+So Type Map (Capacity : Count_Type; Hash_Table_Length : Hash_Type);
+
+Function Default_Hash_Table_Length (Capacity : Count_Type) return Hash_Type;
+
+No restrictions on hash table length, because we are using a bucket
+implementation.
+
+Do not need a function Hash_Table_Length, using that would lock them into the
+bounded form (and they can read the discriminant anyway.
+
+Tucker suggests "Modulus" to "Hash_Type_Length". The current rules don't say how
+the hash value is mapped to the hash table, so this seems like
+overspecification. Others think it is good enough. The function then is
+Default_Modulus. Put the function at the bottom.
+
+Assign and Copy are in all of the packages. Copy works like Reserve_Capacity;
+the hash table also gets shrunk, calling Default_Modulus to figure out the
+appropriate hash table size. Copy gets an extra parameter Modulus, use
+Default_Modulus if it is zero.
+
+Ordered_Maps.
+
+Looks pretty similar.
+
+Should we add Assign and Copy to the original containers? We should plan to do
+it "next time", whenever that is.
+
+To_Set would decide its capacity, it does not get a new parameters.
+
+Hashed_Maps.
+
+Add Default_Modulus, etc. Otherwise works like the Hashed_Maps.
+
+Robert leaves us.
+
+----
+
+We talk a bit about indefinite, bounded forms, where the elements come a storage
+pool and the rest of the "control" stuff is bounded and allocated statically.
+Randy had previously suggested that, because the unbounded forms allocate all
+kinds of control junk, and that would complicate a storage pool that is tailored
+to a particular element type. But the idea seems pretty complex, though, and the
+users that want this probably wouldn't like the complexity.
+
+----
+
+End of day 1.
+
+Day 2. On to the queue abstraction.
+
+----
+
+Generic
+ Type Element_Type is private;
+Package Ada.Containers.Queues is
+ Type Queue (Capacity : Count_Type) is ...
+ Procedure Enqueue (Q : in out Queue; New_Item : in Element);
+ Pragma Implemented (Enqueue, By_Entry);
+ Procedure Dequeue (Q : in out Queue; Item : out Element);
+ Pragma Implemented (Dequeue, By_Entry);
+ Function Is_Empty (Q : Queue) return Boolean;
+ Function Is_Full (Q : Queue);
+ Function Count (Q : Queue) return Count_Type is abstract; End Ada.Containers.Queues;
+
+
+
+Dequeuing from an empty queue generally waits; Enqueuing to a full (bounded)
+queue, then you wait. (You could also raise an exception in both cases.)
+
+Generic
+ Type Element_Type is private;
+Package Ada.Containers.Queues is
+ Type Queue is synchronized interface;
+ Procedure Enqueue (Q : in out Queue; New_Item : in Element_Type) is abstract;
+ Procedure Dequeue (Q : in out Queue; Item : out Element_Type) is abstract;
+ Function Is_Empty (Q : Queue) return Boolean is abstract;
+ Function Is_Full (Q : Queue) is abstract; End Ada.Containers.Queues;
+
+Generic
+Package Ada.Containers.Queues.Unbounded Is
+ Type Queue is synchronized new Queues.Queue with private;
+ Procedure Enqueue (Q : in out Queue; New_Item : in Element_Type);
+ Procedure Dequeue (Q : in out Queue; Item : out Element_Type);
+ Function Is_Empty (Q : Queue) return Boolean;
+ Function Is_Full (Q : Queue);
+Private
+ Protected type Queue is
+ Procedure Enqueue (Item : Element_Type); -- Entry for bounded cases.
+ Entry Dequeue (Item : out Element_Type);
+ Function Is_Entry return Boolean;
+ Private
+ L : List;
+ End Queue;
+ Function Is_Full (Q : Queue);
+End Ada.Containers.Queues.Unbounded;
+
+Bob doesn't want this interface, because it is different than the current design
+of the containers. We could have done that for all of them. Tucker says he
+wanted something like that, but he didn't get it.
+
+We could add child signature packages, even to the original (especially for Sets
+and Maps to extract the commonality).
+
+But here we have an interface. Bob thinks we should use a signature here.
+
+Matt says that there is penalty here for the use of the interface; two
+instantiations. The solution would to be write a wrapper generic, that should
+cut it to one instance for simple uses.
+
+Generic
+Package Ada.Containers.Queues.Bounded Is
+ Type Queue (Capacity : Count_Type) is
+ synchronized new Queues.Queue with private;
+ Procedure Enqueue (Q : in out Queue; New_Item : in Element_Type);
+ Procedure Dequeue (Q : in out Queue; Item : out Element_Type);
+ Function Is_Empty (Q : Queue) return Boolean;
+ Function Is_Full (Q : Queue);
+Private
+ Protected type Queue (Capacity : Count) is
+ Procedure Enqueue (Item : Element_Type); -- Entry for bounded cases.
+ Entry Dequeue (Item : out Element_Type);
+ Function Is_Entry return Boolean;
+ Function Is_Full return Boolean;
+ Private
+ A : Element_Array_Type(1..Capacity);
+ Front, Back : Natural;
+ End Queue;
+End Ada.Containers.Queues.Bounded;
+
+
+Bob asks about a signature package; he says it has less overhead than an
+interface. But we decide it is not necessary because the overhead could be
+avoided by declaring a generic with a formal derived type:
+
+Generic
+ Type T is new Inst.Queues.Queue with private; Package
+
+Bob worries that copying large objects could be expensive. He thinks about
+callback to initialize. Tucker worries that the callback would be in a protected
+action, that would greatly limit what could be done. Matt notes that the point
+here is to pass an object to the container.
+
+The interface package should be Pure, the unbounded packages should be
+Preelaborate, the types should NOT have preelaborable initialization. The
+bounded packages (including yesterdays) should have Pure. (We don't want any
+pointers in the implementation).
+
+Lock-free queues. Bob says when we get that figured out we should next talk
+about bug-free queues.
+
+We should be able to implement this interface with a lock-free algorithm
+(presuming the use implementation-defined constructs for the implementation of
+the package). That (for now at least) would be in an implementation-defined
+subpackage.
+
+----
+
+Limited Containers
+
+An old Bob Duff design for Ada 95:
+
+Lookup_Ptr (Map, Key) return Element_Ptr;
+
+Lookup_CPtr (Map, Key) return Element_CPtr --(access-constant)
+
+Lookup_Optional_Ptr (Map, Key) return Element_Ptr;
+
+Insert_Ptr (Map, Key) return Element_Ptr;
+
+Lookup_and_Insert_Ptr (Map, Key) return Element_Ptr;
+
+These are all functions, they use a Rosen trick/access parameter to handle
+updates to the Map.
+
+The idea is rename the returned value:
+
+ O : Element renames Lookup_Ptr (Map, Key).all;
+
+---
+
+We turn to Matt's proposal:
+
+Generic
+ Type Element_Type is limited private; Package Limited_Hash_Tables is
+
+ Type Map is tagged limited private;
+
+ Function Insert (M : not null access Map; K : Key)
+ return not null access Element_Type;
+
+ Procedure Insert (M : in out Map;
+ K : Key;
+ New_Item : not null access function return Element_Type);
+ -- The function is for initialization.
+
+
+Is vector useful for limited elems? Assume Element_Type is such that Bitwise
+copy isn't meaningful (e.g. it has internal ptrs) so make it limited. How do you
+make a stack of these things?
+
+When you pop the stack, you want the effect of Unchecked_Deallocation on the
+object; and the effect of new on pushing the stack.
+
+Tucker suggests that the container itself is a storage pool with additional
+operations
+
+Type Stack is new Root_Storage_Pool with record
+ Data : array (...) of Element_Type;
+ Top : Int := 0;
+End record;
+
+Tucker thinks you would need to export a package with a single object of this
+type.
+
+Inst (Element_Type => Scope_Descriptor); Obj : Inst.Stack; Type Scope_Ptr is
+access Scope_Descriptor; For Scope_Ptr'Storage_Pool use Obj;
+
+Then new would add an object to the top of the stack, and Unchecked_Deallocation
+would pop the item from the stack.
+
+Matt wonders:
+ Type Pool_Type (EA : access Storage_Element_Array) is new Root_Storage_Pool ...
+
+ Type Stack is record
+ EA : Storage_Element_Array (1..
+10*Element_Type'Max_Storage_Size_in_elements);
+
+ Procedure Push (S : Stack) is
+ Pool : Pool_Type (S.EA);
+ Type Acc is access Element_Type;
+ For Acc'Storage_Pool use Pool;
+ Begin
+
+
+But this doesn't work because the object will be finalized when the access type
+goes away.
+
+Tucker is trying to figure out a fix for that. We decide to look at his subpool
+proposal in detail.
+
+Storage Pool <-->access type 1, access type 2.
+ (subpool) <--> object.
+
+The idea is to allow a bunch of subpools which have a (potentially) shorter
+lifetime than the whole pool.
+
+For instance, a hash table defined globally, with a local object.
+
+ Procedure...
+
+ Subpool <-- HT (access Subpool)
+ HT1 : HT (new Subpool); or
+ HT (Subpool1'access);
+
+Note that you can't use that now, only in a local access type. So we add
+Storage_Pool to new (per-object):
+
+Procedure Insert (H : HT; E : Element_Type) is
+ New HT1.SP Node'(...E...);
+
+This works, but is horribly unsafe.
+
+So we add some checks. Goal: Ptr must not outlive designated object.
+
+Tucker wants to do the checking at the subpool level, not the individual object.
+So the goal becomes Subpool or stack frame (P) containing Ptr must not outlive
+subpool containing designated object (D).
+
+Rule: Check when storing ptr into object resident in subpool (T for target) that
+T does not outlive D.
+
+Temp := new (HT1.SP) Node'();
+Heap_Obj.X := temp;
+
+Access value must be able to determine what subpool that contains the designated
+object. This is an additional requirement on subpools (need a way to get from
+the address to the pool, implementer must make that work)
+
+Heap_obj is in T, Temp is in D.
+
+Assert (Does_Not_Outlive(T, D));
+
+Tucker is proposing May_Reference (A, B). This creates a partial ordering on the
+lifetime of the subpools. This creates a dependence (a counted reference) from
+subpool A to subpool B. The finalization of a subpool involves checking that the
+reference count of a pool is zero (but he also wants to detect cycles, all
+finalizing at once). A subpool handle is a counted reference (it accesses the
+subpool); no direct access to subpools. The subpool is finalized when its counts
+gets to zero (modulo cycles).
+
+A subpool handle is intended to be used for checks for stack frames. (For
+instance, you can't return one of these pointers.) Also need to check on return
+that caller has handle on D.
+
+May_Reference and Does_Not_Outlive are provided by the implementation, so that
+they can be optimized out in many cases. The data would part of the private part
+of subpools.
+
+Tucker hopes that this totally eliminates the possibility of dangling
+references; the subpool sticks around until the (inter-pool) pointers go away.
+
+The purpose is to allow cleaning up sets of data where the type is globally
+defined.
+
+Each subpool is master, both for tasks and finalization. Whatever task finds the
+last subpool is unreferenced is the one that would do the cleanup.
+
+Weak references (subpool+object pointer): can get either null or a strong
+reference to a subpool handle. There also needs to be way to destroy the strong
+references when they are not needed.
+
+Weak references need to be managed by the storage pool. A strong reference would
+a controlled object to decrement the reference count.
+
+Anonymous access parameter issues. How does that work; perhaps you would want to
+have master rather than a level for that check. But we had previously said that
+we wanted to preserve the model. Tucker suggests that we could give them a very
+deep level (as with anonymous access-to-subprogram), so that they could be
+passed but not converted to anything else.
+
+One could use Unchecked_Deallocation for finalizing, even though it isn't really
+Unchecked nor would it Deallocate. We'd only be using the finalization
+side-effect.
+
+----
+
+We turn to looking at control of initialization and finalization.
+
+X : LT := F(...);
+For X'Address use Constant_Value;
+For X'Master use Master_Obj; -- Object is user defined, master object.
+
+In this case, initialization happens at the point of X, but it is initialized
+into memory previously allocated. The new thing is to be able to specify the
+master of X (so it doesn't finalize too early).
+
+For a bounded hash table:
+
+Procedure Insert (HT : in out Hash_Type; Key : in Key_Type) is
+
+X : Element_Type := F(...);
+For X'Address use HT.Element_Array(I);
+For X'Master use HT.Master; -- Or existing HT'Master
+
+Element_Type'Finalize_All (HT.Element_Array(I));
+
+This is unsafe, because we don't know if the original location is already
+initialized. In any case, we have to suppress the initialization on the
+original object (else it would be initialized twice).
+
+Pragma Suppress_Default_Initialize (HT.Element_Array);
+
+Element_Type'Initialize_All (HT.Element_Array(I), HT'Master, F(...));
+
+(The last parameter is optional.)
+
+Do we need to pass master to T'Finalize_All? Probably not,
+Unchecked_Deallocation does not need it.
+
+Bob doesn't want the overhead of using a linked list for the finalization of an
+array of items. That's necessary with this model, because you can't know how the
+code is going to call T'Initialize_All. He would like the master to be
+user-defined.
+
+Do they get extra space for dope? That's hard to do, because we don't know a
+size.
+
+Element_Type'Initialize_All (HT.Element_Array(I), [F(...)]);
+
+Function T'Initialize_All (P : access ET; Initial_Value : ET);
+ -- We use access ET because we want to worry about by-copy types; P should be by-reference.
+ -- Also could use for pointer math.
+
+But you could Unchecked_Convert to access ET, then pass UC.all.
+
+You would have to apply Suppress_Default_Init before using T'Initialize_All,
+else the code is erroneous.
+
+Bob suggests pragma Suppress_Default_Init be applied to types. And then the
+Initialize_All and Finalize_All could be called for that type (otherwise, we
+wouldn't allow it).
+
+Tucker notes that you define a derivation of Element_Type to make Bob's idea work.
+
+It is erroneous to access an uninitialized object (that is, before the call to
+Initialize_All. Tucker notes that you could even add a bit to detect this
+problem.
+
+Indeed, one could imagine a type with pragma SDI as an Unchecked_Union of a
+bag-o-bits and Element_Type. Then actually an assignment would do the right
+thing (but of course that doesn't work for build-in-place). And if you stored
+the discriminant, you could actually check for double initialization and
+finalization.
+
+The model is that T'Initialize_All is an assignment to a record where we're
+changing the discriminants from bag-o-bits to Element_Type, T'Finalize_All goes
+in the reverse.
+
+Logically:
+
+ Type ET (Initted : Boolean := False) is record
+ Case Initted is
+ When False => Bag_o_Bits : Storage_Element_Array (1 .. Right_Size);
+ When True => Object : Element_Type;
+ End case;
+ End record;
+
+Goal, if T'Finalize_All is a no-op (because there is no controlled components),
+then there should be nothing put on any lists.
+
+Finalize_All for Obj w. components that suppress_default_init. If
+Unchecked_Deallocation needs to remove these, it depends on whether it is
+on a the list. Randy says it works the same as now, if it is on a list.
+
+Lots more brainstorming goes on, but I gave up making notes for a while.
+
+There is some discussion about only doing this for types that do not have
+controlled/task/protected components.
+
+Bob thinks that the initialized bit ought to exist (with the possibility of
+suppressing it), and then the routines should check the bit.
+
+Matt suggests possibly using a magical generic for this purpose. He is trying to
+make a way to get to C++ placement new.
+
+Package P is new Magic(Element_Type);
+Type EAT is array () of P.T;
+HT Arr : EAT;
+Ptr := new (HT.Arr(I) Element_Type'(...); Ptr := New_Object (HT.Arr(I));
+Delete_Object (HT.Arr(I));
+
+Tucker has to leave to make his train, so the meeting ends at 4:15 p.m.
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Thursday, September 25, 2008 7:16 PM
+
+Thanks, Randy, for taking notes.
+
+You mention these below in passing, but I believe we (tentatively, of course)
+agreed on having case-insensitive string hash and comparison, using To_Lower as
+the "folding" before comparison (by the way, I finally found a definitive
+statement that that is what the C-based standard requires).
+
+I think we also tentatively agreed to provide a Generic_Sort routine that takes
+Swap and comparison formal subprograms, without actually taking the array itself
+as a parameter.
+
+Thanks again for the notes.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Monday, September 29, 2008 5:55 PM
+
+Minutes for containers meeting at AdaCore on 22-3 Sep 2008
+
+Sep 22-3 2008 (Mon, Tue)
+
+Q: What is our goal for this meeting?
+
+A: Greater demand for restricted ("bounded") forms, rather than matching what's
+in the C++ STL. (There has been actual demand for bounded forms, so that should
+have priority.)
+
+In bounded forms, there is the issue of initialization and finalization of
+elements. The objects don't actually get created and destroyed, so if an
+element is deleted from a container, and then re-inserted, what value should the
+newly-inserted object have? One solution is to use vector semantics.
+
+[Similar to a bounded form, a vector has storage for elements that doesn't get
+deallocated (at least immediately). For that container, there are a few
+insertion forms. The first form accepts a new value as a parameter, so that's
+the value that a newly-inserted element has. The second form omits a new value,
+and in that case a local variable having a default value is assigned to the
+newly-inserted element, so in that case the element has the default value of the
+type. In the third case, there's a distinct Insert_Space operation that simply
+opens up that slot in the internal array, the intent of which is for the caller
+to make a separate call to Replace_Element to properly assign a value to the
+newly-inserted element. --MJH]
+
+
+Can you use a storage pool hack to initialize and finalized storage that is
+statically allocated? No, because when the scope of the (local) access type
+ends, it will finalize the storage associated with that access type. [on Tue we
+discussed ways the language could be modified to support such a feature. --MJH]
+
+AI05-107 deallocation issues?
+
+AI05-0069-1 ??
+
+"standards track technical report" - for this committee. MJH has the task of
+actually writing the TR.
+
+Next ARG meeting: Oct 30-1 (Thu, Fri), Nov 1-2 (Sat, Sun). WG9 meeting on Thu
+afternoon. [I will be attending the meeting on Sat-Sun. --MJH]
+
+Incorporate AI-69 into TR?
+
+AI05-0001-1 (describes need for bounded forms?)
+
+TR: will eventually become a standard.
+
+Synchronized forms - no clear meaning of what a "protected form" even is.
+
+Randy said that there was a discussion about this issue on CLA. Lock for a
+single container vs. lock shared among several containers.
+
+Composibility issues. e.g. set of sets.
+
+Locking mechanism: semaphore (Seize, Release) vs. monitor
+
+Canada: our main customer?
+
+What not let user wrap container in a PO himself?
+
+Dimensions of our problem space:
+limited-ness
+controlled-ness
+dynamic allocation
+synchronized
+new containers
+other non-container features
+space-optimized forms
+persistance
+
+Issue with tampering bits: there is a pathological condition in which assignment
+of the container is made in a tampering context. The problem is that the
+tampering bits are set, and these get copied to the object on the LHS of the
+assignment. Without controlled-ness, there's no way to reset these bits.
+
+However, the goal is to not require that the bounded forms be implemented as a
+private derviation from controlled. [Do we require that controlled-ness cannot
+be used? --MJH] So we could decide that this is a bounded error. The
+implementation might be able to detect this state and raise an exception. Or it
+could detect this state and automatically reset the bits. (There's a trick you
+can use: with an access component that is set to point to the current instance
+of the type. If you notice that the access value doesn't match the current
+instance, then assignment has occured and you can reset the bits. Alternatively
+you could set the access value when you enter the tampering context.)
+
+thread-safety vs. performance: if we can't do it better than a user can do
+himself, then why do it?
+
+operations are not potentially blocking [does this refer to synchronized
+forms???]
+
+Since we can't decide what a protected container is, we can punt and just supply
+a (bounded) queue, which is useful all by itself as a stand-alone abstraction.
+One possibility is to write a generic queue that imports the underlying
+structure (e.g. a bounded vector, or unblunded list) as a generic formal type.
+But then do we supply pre-defined instantiations? [See notes for Tue, where we
+tenatively decided on what the spec should look like. --MJH]
+
+Other abstractions for synchronization: barriers. Not enough complexity here to
+standardize?
+
+(Limited) containers with limited elements: how to finalize elements in a
+bounded form?
+
+What does "new T" mean? Does this count as dynamic allocation, even if (say)
+the access type is associated with a storage pool that is itself bounded? [I
+think the answer is yes, because (in GNAT at least) the compiler handles a
+restrictions pragma by noting where the allocators are used. So in order to
+satisfy the requirement for "no dynamic allocation" we must use a bounded form
+(the type is implemented with an array component) instead of importing some
+storage pool as a generic formal object.]
+
+Bounded hash table: issue of how to declare number of elements vs. size of
+backbone. Backbone size: specified via discriminant vs. generic formal
+parameter.
+
+Secondary stack
+discrim vs. generic formal
+instantiation provides defaults (but tagged types cannot have defaults for
+discrim)
+
+MJH argues that it would be nice if the user didn't have to specify backbone
+size (since he might specify a value that doesn't scatter hash values very
+well). However the consensus is that we should allow user to control both
+number of elements and backbone size.
+
+Bounded forms: do not use a storage pool. Use per-object storage rather than a
+"pool" shared among instances. Per-object storage is specified via discriminant
+(rather than generic formal parameter).
+
+Note that assignement of bounded forms will cause CE if discrims don't match.
+
+Corrigendum doesn't do much for users; amendment is more useful.
+
+Tuck's storage pool for persistence AI.
+
+John Barnes/American customers: US decision for proper amendment?
+
+What is role of ARG: to make amendment or corrigendum?
+
+Protected forms: multiple readers? Or only provide queues? Which operations
+are waiting?
+
+Linda language: has "tuple spaces"
+
+Thread-safe vs. atomicity: atomicity is more useful.
+
+Ed S. mentioned conference at NYU(?) about hardware-level abort/rety
+
+synchronized queue
+
+Vector has "empty" elements: created as a result of Insert_Space. It's a
+bounded error to read from them, so you can't assign them a value via
+Update_Element (e.g. in indefinite form you don't even have an element), so you
+must use Replace_Element.
+
+Trick for (re)initializing a statically-allocated element: use pragma Import to
+fake placement new.
+
+How to grant last wishes: insert nothing (default init), insert item, insert
+space. Can potentially raise exception if touch "empty" element.
+
+non-limited bounded forms: are not controlled
+
+multiset - same as bag
+
+Tucker wants MJH to supply an example that demonstrates how a problem is more
+easily solved using a multiset instead of a existing forms (e.g. map of sets).
+
+To guarantee uniqueness of key you could make a two-part key, with one part just
+a number that simply gets incremented (to satisfy uniqueness requirements).
+
+Multiset: how to you designant elements in a subrange. [Using an additional
+passive iterator that accepts a key. You might also be able to use
+floor/ceiling to perform active iteration (but maybe not, since they're
+semantics don't match C++ lower_bound/upper bounded).]
+
+Having (limited) container of limited elements is more important that a
+multiset.
+
+Case-insensitive string hash, string equality, string less: defined in terms of
+To_Upper or To_Lower (answer influences outcome of test)? In GNAT we use
+To_Lower. _stricmp, _wcsicmp in Microsoft C also uses lowercase compare; gives
+example of JOHNSON vs. JOHN_HENRY. Whatever we do should be the same as what C
+does (using 8-bit chars)???
+
+We had originally gotten rid them at the Phoenix meeting. Specify map function
+to specify folding? But this is more than we really need.
+
+We have tenatively decided that they're a good idea: use same names as in
+GNAT:
+
+Ada.Strings.Equal_Case_Insensitive
+Ada.Strings.Hash_Case_Insensitive
+Ada.Strings.Less_Case_Insensitive
+
+and to fold to lower case.
+
+We don't promise that case-insensitive hash returns same result as
+case-sensitive hash will all lower-case letters (because implementation could
+use knowledge to make an optimal hash function).
+
+It would be possible to make a space-optimized doubly-linked list by xor'ing
+prev and next, but in order to navigate you need to refer to a pair of nodes.
+
+Cursors: for vector cursor can be "ambiguous" (see RM p.243) vs. "invalid"
+cursor.
+
+Radix sort? (But heap sort is probably good enough. "Heap" came from Knuth,
+but this is same as Floyd's "tree" sort.)
+
+Should be have a sort algorithm for an "anonymous" (my term) array? Yes, here's
+what the spec should look like:
+
+generic
+ type Index_Type is (<>);
+ with function Less (Left, Right : Index_Type) return Boolean is <>;
+ with procedure Swap (Left, Right : Index_Type) is <>;
+
+procedure Ada.Containers.Generic_Sort
+ (First, Last : Index_Type'Base);
+
+pragma Pure (Ada.Containers.Generic_Sort); --??? gnat-specific?
+
+
+"lock-free container": multi-core extensions for Ada; to be discussed at ARG
+meeting in Portland.
+
+lock-free algorithms
+transactions
+multi-core
+
+
+auto_ptr abstraction for Ada. Outside charter of this group, but it's part of
+"storage management issues" to be disussed by ARG (in Portland?).
+
+
+Persistance: via passive partition or other?
+pointer-swizzling
+
+
+language extensions for iteration:
+
+e.g. vbscript
+
+ Set objCollection = ...
+ For Each objItem in objCollection
+ 'manipulate objItem
+ Next
+
+Sather - nice iteration syntax
+CLU
+Randy's proposal: see Ada-Comment on 12 April 2005 (AC-112)
+
+
+super-null arrays
+
+Spec of bounded forms: one of our goals is to minimize changes to spec of
+unbounded form, so we keep some functions that don't necessarily make sense for
+bounded forms.
+
+The bounded non-hashed forms are declared this way (pass capacity as
+discrim):
+
+ type Map (Capacity : Count_Type) is tagged private;
+
+The bounded hashed forms are declared this way (pass both capacity and hash
+table length):
+
+ type Map (Capacity : Count_Type; Modulus : Hash_Type) is tagged private;
+
+Capacity function - keep this to support non-prefix function calls; if prefix
+form is used, language has preference for discriminant so we're OK.
+
+Keep Reserve_Capacity, since we can follow same semantics as for unbounded form.
+One issue (to be resolved) is what exception to propagate if user specifies
+capacity parameter larger than capacity of bounded container. My examples in
+the jean repository raise Storage_Error, but there was some debate about whether
+some other exception (e.g. Constraint_Error) would be better.
+
+Bounded vector: defined in terms of unbounded vector.
+
+RM language for Move operation of unbounded forms: must state that capacity of
+source container is allowed to change. Should be described in terms of calling
+Reserve_Capacity with 0 capacity as value.
+
+Don't worry about tamper bits in bounded form (when assigning in tampering
+context), since it's a bounded error.
+
+The vector, list, and ordered containers have the following pair of
+operations:
+
+ procedure Assign (Target : in out Vector; Source : Vector);
+
+The semantics of Assign are as follows: if Target denotes same object as Source,
+then do nothing.
+
+ function Copy (Source : Vector; Capacity : Count_Type := 0) return Vector;
+
+The semantics of Copy are as follows: if capacity is larger than source
+container's length, than use that value as the capacity of LHS. Otherwise, use
+length of source as capacity.
+
+Hashed forms look like this:
+
+ function Copy (Container : Map;
+ Capacity : Count_Type := 0;
+ Modulus : Hash_Type := 0) return Map;
+
+As with other bounded forms, Capacity=0 means use container.length as capacity
+of target. Modulos=0 means use default_modulous(container.length).
+
+There's also a function (declared at end of spec):
+
+ function Default_Modulus (Capacity : Count_Type) return Hash_Type;
+
+This returns a "good" value for the backbone length for a given capacity.
+
+Shared pool idea: either generic formal object (of type Storage_Pool'Class) or
+nodes in package body; see adalib list on 2006/12/10 & 12.
+
+Bounded forms have Pure categorization.
+
+Brad Moore - has API with heavy use of synchronized interfaces
+
+
+Tue Sep 23 2008
+
+Blocking queue - the minimum we provide for a "protected container."
+
+bounded vs. unbounded
+signatures vs. interface
+
+dequeue from empty
+enqueue to full
+
+
+We discussed various ways of implementing a queue. We finally settled on
+using an abstract queue interface, with a pair of concrete children,
+reasoning that the interface could be used to implement class-wide message
+passing algorithms (see Andy Welling et al):
+
+generic
+ type Element_Type is private;
+
+package Ada.Containers.Queues is
+ pragma Pure;
+
+ type Queue is synchronized interface;
+
+ --??? param names OK?
+ procedure Enqueue (Q : in out Queue; New_Item : Element_Type) is
+abstract;
+ pragma Implemented (Enqueue, By_Entry); -- ???
+ -- see RM 9.5
+
+ procedure Deque (Q : in out Queue; Element : out Element_Type) is
+abstract;
+ pragma Implemented (Dequeue, By_Entry); -- ???
+
+ function Is_Empty (Q : Queue) return Boolean is abstract;
+
+ function Is_Full (Q : Queue) return Boolean is abstract;
+
+ function Length (Q : Queue) return Count_Type is abstract;
+ --??? do we need this? Does this over-specify the interface?
+
+ -- ??? other ops
+
+end Ada.Containers.Queues;
+
+generic
+package Queues.Bounded is --??? should this be Generic_Bounded?
+ pragma Pure; -- ???
+
+ type Queue (Capacity : Count_Type) is synchronized new Queues.Queue with
+private;
+
+private
+
+ protected type Queue (Capacity : Count_Type) is ...;
+
+end Queues.Bounded;
+
+
+generic
+package Queues.Unbounded is --??? should this be Generic_Unbounded?
+ pragma Preelaborate; -- ???
+
+ type Queue is synchronized new Queues.Queue with private;
+
+private
+
+ protected type Queue is ...;
+
+end Queues.Unbounded;
+
+
+We disussed limited containers. Bob D. and Tucker T. have an limited hash
+table that looks something like:
+
+generic
+ type Element_Type is limited private;
+ type Key_Type is private;
+
+package Limited_Hash_Tables -- per Bob Duff and Tucker
+
+ type Map is tagged limited private;
+
+ -- Ada95 version:
+ function Insert (M : Map; Key : Key_Type) return Elem_Ptr;
+
+ -- Ada05 version:
+ function Insert (M : not null access Map; Key : KT)
+ return not null access ET;
+
+ -- another idea to initialize element
+ procedure Insert (M : in out Map;
+ K : KT;
+ New_Item : not null access function Init return ET);
+
+ Lookup_Ptr (Map; Key) return Elem_Ptr;
+ Lookup_CPtr (Map; Key) return Elem_Const_Ptr;
+ Lookup_Optimal_Ptr (Map; Key) return Elem_Ptr
+ Insert_PTr return Elem_Ptr;
+ Insert_Or_Lookup_Ptr (Map; Key) return Elem_Ptr;
+
+ -- vector - not so useful for limited elems?
+ -- ET: bitwise copy isn't meaningful (e.g. it has internal ptrs)
+ -- so make it limited
+ -- how to handle the case when item is inserted in container
+ -- deleted from container
+
+private
+
+ type Map is ...;
+
+end Limited_Hash_Tables;
+
+
+Discussion of limited containers led to a discussion about initialization
+and finalization of limited elements. This led to a discussion abount
+memory management and initialize/finalization issues.
+
+We have identified two distinct issues. Tucker often creates long-lived
+data structures, that get populated but then the same elements remain for
+the life of the container. He argues that allocation and deallocation of
+nodes is at the wrong granularity, and he would like everything in the
+container to be finalized and then deallocated together.
+
+The other issue (identified by Bob and Matt) is initialization and
+finalization of the "inactive" elements in a container. This mostly applies
+to bounded forms (it also applies to an unbounded vector with more capacity
+than length). In a bounded form, the storage for elements isn't used
+immediately -- it's only used when an element is inserted into the container
+(made "active"). The issue is that if the element type has default
+initialization, or it's controlled, then when the container object is
+declared, there is a penalty because all of the (inactive) elements must be
+initialized. It would be nice if there were a way to defer initialization
+of the element until it is actually inserted.
+
+We spent the remainder of the day brainstorming changes to the language to
+address these issues. What follows is a rough sketch of what we discussed.
+
+Here are a couple of examples of binding a hash table to a pool:
+
+ type HT (Pool : not null access Subpool_Type) is ...;
+
+ H : HT(new Subpool_Type);
+ H2 : HT(Subpool_Object'Access);
+
+The memory management infrastructure would have to be able to distinguish
+between the case of allocating a new pool object (is this an example of
+"coextension"?) and binding to an existing pool object.
+
+You can get something like placement new by supplying the pool as an
+argument:
+
+procedure Insert (H : in out HT; K : KT) is
+ X : ... := new (H.Pool.all) Node_Type;
+ -- no new access type here
+begin
+
+Checks: ptr must not outlive designate object (RM 3.10.2).
+
+Subpool containing ptr must not outlive subpool containing designated object
+(D) (really, subpool or stack frame).
+
+Check when storing ptr into subpool (really, obj in subpool).
+
+temp := new (H.Subpool.all) Node_T
+ D
+
+heapobj.X := temp
+
+access value -> subpool that contains its designate object
+
+operation: Does_Not_Outlive (T, D)
+
+heapobj.X := temp;
+T
+
+T must not outlive D
+
+procedure May_Reference (A, B)
+ create dependence between subpools;
+ establishes partial order
+
+Finalization of a subpool ensures no references (must detect cycles)
+
+subpool handle -> subpool
+ counted reference to subpool
+
+
+another check on return that caller has handle on D
+ procedure May_Ref (A, B)
+
+weak ref = subpool + object_ptr
+ return null or counted ref (strong ptr)
+
+with strong ref, object doesn't go away
+
+cache has weak ref - can ask about object
+ result is either null (meaning obj has gone away) or strong ref
+
+subpool is master -> finalization of object???
+
+AI-111 Tucker
+ per-object storage pools
+
+masters vs. levels
+accessibility checks
+conversion from anon access type to named type?
+
+static subpools (on stackframe)
+ special case of more general mechanism
+
+subpool handle - limited
+ can be passed as arg to new
+
+each ht (or stack) is an instance of subpool
+
+[The rest of this stuff is the init/final idea. --MJH]
+
+X : LT := F;
+for X'Addr use XYZ;
+ but master of X is local
+ for X'Master ...;
+
+suppress default init
+T'Init_All
+T'Finalize_All
+
+stack of fixed length
+Finalize_All - to finalize elem
+
+ET'Init_All (H.Array(i), H.Master, F(X, Y)'Access);
+ET'Final_All(H.Array(i)); -- to remove from list
+
+pragma Supproess_Default_Init
+ creates extra space for links
+ always applies to a type
+ gives you ET'Init_All and ET'Final_All
+
+wrapper of ET - provides extra bit; to indicate whether init'd.
+
+discriminated record: discrim says whether init'd or not
+data is payload
+
+pragma Supress_Discrim_Check - to remove per-elem overhead
+
+model is that ET'Init is assignment to a discrim rec and changes value of
+discrim
+
+HT "contains" a master calls Finalize
+"gets finalized at same time"
+
+bounded form is sort of like a light-weight controlled object
+the HT is controlled because it has controlled elements
+
+what happens to a composite type with a component for which pragma
+Suppress_Default_Init is specified?
+
+limited bounded case, yes, but useful for non-limited types too
+
+useful to prevent vector array from init all junk (inactive) elements
+e.g. vector instantiated with access type, don't want to null all elements
+
+tucker's discrim type: another option to allow just discrim to change
+
+I had an idea to abstract-away some of support for light-weight
+controlled-ness. Just as we have a pkg like this:
+
+generic
+ type Object(<>) is limited private;
+package System.Address_To_Access_Conversions is
+ pragma Preelaborate(Address_To_Access_Conversions);
+ type Object_Pointer is access all Object;
+ function To_Pointer(Value : Address) return Object_Pointer;
+ function To_Address(Value : Object_Pointer) return Address;
+ pragma Convention(Intrinsic, To_Pointer);
+ pragma Convention(Intrinsic, To_Address);
+end System.Address_To_Access_Conversions;
+
+
+We could have a pkg something like:
+
+generic
+ type Object is limited private;
+package System.Initialization is
+
+ type Object_Storage is private;
+ -- has size and alignment of type Object
+ -- need separate versions for limited Obj vs. non-limited Obj?
+
+ type Object_Pointer is access all Object;
+ for Object_Pointer'Storage_Size use 0;
+
+ -- to default-init object
+ function New_Object (Storage : not null access Object_Storage)
+ return Object_Pointer;
+
+ -- to copy-assign the object
+ function New_Object
+ (Storage : not null access Object_Storage;
+ Value : Element_Type)
+ return Object_Pointer;
+
+ procedure Delete_Object (Storage : in out Object_Storage);
+
+private
+
+ type Object_Storage is ...;
+
+end System.Initialization;
+
+So now you could implement a bounded stack something like:
+
+with System.Initialization;
+generic
+ type ET is private;
+package Generic_Stacks is
+ type Stack (Capacity : Count_Type) is tagged private;
+ procedure Push (S : in out Stack; E : ET);
+ ...
+private
+ type Element_Array is array (Count_Type range <>)
+ of aliased Object_Storage;
+
+ type Stack (Capacity : Count_Type) is tagged record
+ Elements : Element_Array (1 .. Capacity);
+ Top : Count_Type := 0;
+ end record;
+end;
+
+package Generic_Stacks is
+ procedure Push (S : in out Stack; E : ET) is
+ I : constant Count_Type := S.Top + 1;
+
+ -- this is the part where you might have to pass S'Master, etc.
+ P : Object_Pointer := New_Object (S.Elements (I)'Access);
+ begin
+ P.all := E;
+ S.Top := I;
+ end;
+ ...
+end Generic_Stacks;
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Wednesday, October 22, 2008 12:10 AM
+
+Grein, Christoph (Fa. ESG) wrote:
+...
+
+> Is there some place where I can help? (If I find some spare time, of
+> course.)
+
+Yes, of course. The best place is to post to the adalib list.
+Otherwise, I can give you developer status in jean repository, which
+would allow you to edit (and check-in) sources directly.
+
+
+> 1.----------------------------------------------------------------------
+> [ARG]: Is there anything we want to say about the relationship between
+> the range of Index_Type and vector capacity? It's possible to declare a
+> vector object with a capacity smaller than the range of the index
+> subtype (and this makes sense for types as Positive, etc), but it's also
+> possible to declare a vector object with a capacity larger than the
+> range -- but we could never even add those elements, since the maximum
+> vector length is determined by the range of the index subtype. Should
+> we allow this? [END ARG]
+>
+> I think if someone asks for this, he gets what he asked for. A note in
+> the AARM (or, if this is only a secondary standard to the RM, in
+> something similar) could be added.
+
+OK, that makes sense. I don't think we made any explicit statement in
+the RM to handle this case for the unbounded forms, so maybe we don't
+need to worry about it.
+
+
+> 2.----------------------------------------------------------------------
+> Why is there a Reserve_Capacity? It's completely useless.
+
+Actually, I think that it has semantics identical to the unbounded form.
+ (But I have to think about it. Maybe I over-specified, in which case
+no discussion would even be necessary.)
+
+
+> Is it just for
+> compatibility with Ada.Containers.Vectors?
+
+Yes.
+
+
+> There are already operations
+> which are not in Ada.Containers.Vectors, so this breaks compatibility,
+> so why shouldn't there be some missing?
+
+I suspect that the operations we add to the bounded form will eventually
+migrate into the unbounded forms as well. (I think the only two
+operations are Assign and Copy. I forget -- were there others?)
+
+
+> 3.----------------------------------------------------------------------
+> My lightweight opinion wrt. Constraint_ vs. Storage_Error:
+> I think all bounded containers should raise the same exception in such
+> cases.
+> For vectors: Arrays raise CE; vectors are kind of arrays, so they also
+> should raise CE. Bounded strings raise CE.
+
+OK, that's a data point from a HI user. Reviewing my code I see that I
+raise both SE and CE, inconsistently. Thanks for the tip.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, October 23, 2008 9:55 PM
+
+A quick glance at this did not turn up any wording for Reserve_Capacity for
+bounded vectors and lists. I think you need to say somewhere that the capacity
+of the container cannot be changed, and an attempt to set it larger than
+specified will always fail with Storage_Error (if that what we decided??).
+Surely that needs to be mentioned (it's the whole point of bounded). I see you
+do mention it for Maps, but then say it is the same as Unbounded. But that's
+not quite true; Unbounded is supposed to try to expand the capacity (assuming
+it is expanding) and raise an exception only if that is not possible. Bounded
+is not supposed to try, just raise an exception for any attempted expansion
+(and do nothing for a shrinkage). That is a difference in intent. Surely we
+want to explain that somewhere, else these containers will not be obviously
+different.
+
+Also note that if Reserve_Capacity is properly documented, changing Insert, etc.
+isn't needed, because they all call Reserve_Capacity when they need to expand
+(and that will raise an exception).
+
+And I do think you need to mention (but perhaps only in an AARM implementation
+note) that the bounded forms are not expected to be controlled types. If there
+is any semantic ramifications of that, we need to change the wording as needed.
+
+I didn't read further than that (I have lots of ASIS work still to do).
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Friday, October 24, 2008 5:51 AM
+
+> A quick glance at this did not turn up any wording for
+> Reserve_Capacity for bounded vectors and lists.
+
+For Vector it's on line #105:
+
+"The semantics of Reserve_Capacity is as follows. If the specified Capacity
+is larger than the Container.Capacity, then it raises Storage_Error.
+Otherwise, the operation does nothing."
+
+There is none for lists, since the unbounded form doesn't have that.
+
+Bounded hashed map is on line #227:
+
+"The semantics of Reserve_Capacity is as follows. If the specified Capacity
+is larger than the Container.Capacity, then it raises Storage_Error.
+Otherwise, the operation does nothing."
+
+For the bounded hashed set it's on line #358:
+
+The semantics of Reserve_Capacity is as follows. If the specified Capacity
+is larger than the Container.Capacity, then it raises Storage_Error.
+Otherwise, the operation does nothing.
+
+
+> I think you need to say somewhere that the capacity of the container
+> cannot be changed, and an attempt to set it larger than specified will
+> always fail with Storage_Error (if that what we decided??). Surely
+> that needs to be mentioned (it's the whole point of bounded).
+
+Is this requirement satisfied by descriptions above?
+
+> I see you do mention it for Maps, but then say it is the same as
+> Unbounded.
+
+But that part was non-normative. It was in the form of a question to be
+answered by the ARG during our meeting:
+
+"[ARG]
+Actually, I think this has the same behavior as the unbounded form (since
+in principle the unbounded form could also raise an exception "if the
+specified capacity is larger than the container capacity". Since this API
+is just supposed to specify how the bounded form differs from the unbounded
+form, then do we need to mention Reserve_Capacity here?
+[END ARG]"
+
+> But that's not quite true; Unbounded is supposed to try to expand
+> the capacity (assuming it is expanding) and raise an exception only if that
+> is not possible. Bounded is not supposed to try, just raise an exception for
+> any attempted expansion (and do nothing for a shrinkage). That is a
+> difference in intent. Surely we want to explain that somewhere, else these
+> containers will not be obviously different.
+
+OK, that's fine by me. I was trying to minimize the amount of normative
+text, but if you think it's more clear to be explicit about behavior for
+bounded forms then we can leave it in.
+
+> Also note that if Reserve_Capacity is properly documented, changing Insert,
+> etc. isn't needed, because they all call Reserve_Capacity when they need to
+> expand (and that will raise an exception).
+
+Good point. I'll have to review all the spots where Reserve_Capacity is
+called indirectly, as a side-effect of insertion, etc.
+
+> And I do think you need to mention (but perhaps only in an AARM
+> implementation note) that the bounded forms are not expected to be
+> controlled types. If there is any semantic ramifications of that, we need to
+> change the wording as needed.
+
+Right, I asked that question on line #14:
+
+"[ARG] We agreed during the meeting on 2008/09/22 that the bounded forms
+would not be controlled. Do we need to say that? One consequence is
+this is that we cannot detect finalization of the container when it's in
+a tampering state, ..."
****************************************************************
Questions? Ask the ACAA Technical Agent