Rationale for Ada 2012

John Barnes
Contents   Index   References   Search   Previous   Next 

8.2 Bounded and unbounded containers

It is perhaps worth starting this discussion by summarizing the containers introduced in Ada 2005. First, there is a parent package Ada.Containers which simply declares the types Hash_Type and Count_Type.
Then there are six containers for definite objects, namely (abbreviating the prefix Ada.Containers to just A.C)
A.C.Vectors
A.C.Doubly_Linked_Lists
A.C.Hashed_Maps
A.C.Ordered_Maps
A.C.Hashed_Sets
A.C.Ordered_Sets
The declarations of these six containers all start with
generic
   ...
   type Element_Type is private;
   ...
package Ada.Containers.XXX...
and we see that the type Element_Type has to be definite. There are also containers for the manipulation of indefinite types whose names are
A.C.Indefinite_Vectors
A.C.Indefinite_Doubly_Linked_Lists
A.C.Indefinite_Hashed_Maps
A.C.Indefinite_Ordered_Maps
A.C.Indefinite_Hashed_Sets
A.C.Indefinite_Ordered_Sets
and these are very similar to the definite containers except that the formal type Element_Type is now declared as
   type Element_Type(<>) is private;
so that the actual type can be indefinite such as String.
Finally, there are two generic packages for sorting arrays namely
A.C.Generic_Array_Sort
A.C.Generic_Constrained_Array_Sort
which apply to unconstrained and constrained arrays respectively.
The first change in Ada 2012 is that the parent package Ada.Containers now includes the declaration of the exception Capacity_Error so that it becomes
package Ada.Containers is
   pragma Pure(Containers);
   type Hash_Type is mod implementation-defined;
   type Count_Type is range 0 .. implementation-defined;
   Capacity_Error: exception;
end Ada.Containers;
The names of the new containers with bounded storage capacity are
A.C.Bounded_Vectors
A.C.Bounded_Doubly_Linked_Lists
A.C.Bounded_Hashed_Maps
A.C.Bounded_Ordered_Maps
A.C.Bounded_Hashed_Sets
A.C.Bounded_Ordered_Sets
The facilities of the bounded containers are almost identical to those of the original unbounded ones so that converting a program using one form to the other is relatively straightforward. The key point of the bounded ones is that storage management is guaranteed (implementation advice really) not to use features such as pointers or dynamic allocation and therefore can be used in high-integrity or safety-critical applications.
The major differences between the packages naturally concern their capacity. In the case of the bounded packages the types such as Vector have discriminants thus
type Vector(Capacity: Count_Type) is tagged private;
whereas in the original packages the type Vector is simply
type Vector is tagged private;
The other types in the bounded packages are
type List(Capacity: Count_Type) is tagged private;
type Map (Capacity: Count_Type; Modulus: Hash_Type) is tagged private;
type Map(Capacity: Count_Type) is tagged private;
type Set (Capacity: Count_Type; Modulus: Hash_Type) is tagged private;
type Set(Capacity: Count_Type) is tagged private;
Note that the types for hashed maps and sets have an extra discriminant to set the modulus; this will be explained in a moment.
Remember that the types Count_Type and Hash_Type are declared in the parent package Ada.Containers shown above.
When a bounded container is declared, its capacity is set once and for all by the discriminant and cannot be changed. If we subsequently add more elements to the container than it can hold then the exception Capacity_Error is raised.
If we are using a bounded container and want to make it larger then we cannot. But what we can do is create another bounded container with a larger capacity and copy the values from the old container to the new one. Remember that we can check the number of items in a container by calling the function Length.
So we might have a sequence such as
My_List: List(100);
...    -- use my list
if Length(My_List) > 90 then    -- Gosh, nearly full
...
   declare
      My_Big_List: List := Copy(My_List, 200);
   begin
      ...
The specification of the function Copy is
function Copy
            (Source: List;
             Capacity: Count_Type := 0) return List;
If the parameter Capacity is not specified (or is given as zero) then the capacity of the copied list is the same as the length of Source.
If the given value of Capacity is larger than (or equal to) the length of the Source (as in our example) then the returned list has this capacity and the various elements are copied. If we foolishly supply a value which is less than the length of Source then Capacity_Error is naturally raised. Remember that a discriminant can be set by an initial value.
Note that if we write
declare
   My_Copied_List: List := My_List;
begin
then My_Copied_List will have the same capacity as My_List because discriminants are copied as well as the contents.
In order to make it easier to move from the bounded form to the unbounded form, a function Copy is added to the unbounded containers as well although it does not need a parameter Capacity in the case of lists and ordered maps and sets. So in the case of the list container it is simply
function Copy(Source: List) return List;  --unbounded
Similar unification between bounded and unbounded forms occurs with assignment. In Ada 2005, if we have two lists L and M, then we can simply write
L := M;
and the whole structure is copied (including all its management stuff). Note that this will almost certainly require that the value of L be finalized which might be a nuisance. Such an assignment with discriminated types needs to check the discriminants as well (and raises Constraint_Error if they are different). This is a nuisance because although the capacities might not be the same, the destination L might have plenty of room for the actual elements in the source M.
This is all rather bothersome and so procedures Assign are added to both unbounded and bounded containers which simply copy the element values. Thus in both case we have
procedure Assign(Target: in out List; Source: in List);
In the bounded case, if the length of Source is greater than the capacity of Target, then Capacity_Error is raised. In the unbounded case, the structure is automatically extended.
It might be recalled that in Ada 2005, lists and ordered maps and sets do not explicitly have a notion of capacity. It is in their very nature that they automatically extend as required. However, in the case of vectors and hashed maps and sets (which have a notion of indexing) taking a purely automatic approach could lead to lots of extensions and copying so the notion of capacity was introduced. The capacity can be set by calling
procedure Reserve_Capacity
            (Container: in out Vector;
             Capacity: in Count_Type);
and the current value of the capacity can be ascertained by calling
function Capacity(Container: Vector) return Count_Type;
which naturally returns the current capacity. Note that Length(V) cannot exceed Capacity(V) but might be much less.
If we add items to a vector whose length and capacity are the same then no harm is done. The capacity will be expanded automatically by effectively calling Reserve_Capacity internally. So the user does not need to set the capacity although not doing so might result in poorer performance.
The above refers to the existing unbounded forms and is unchanged in Ada 2012. For uniformity the new bounded forms for vectors and hashed maps and sets also declare a procedure Reserve_Capacity. However, since the capacity cannot be changed for the bounded forms it simply checks that the value of the parameter Capacity does not exceed the actual capacity of the container; if it does then Capacity_Error is raised and otherwise it does nothing. There is of course also a function Capacity for bounded vectors and hashed maps and sets which simply returns the fixed value of the capacity.
Many operations add elements to a container. For unbounded containers, they are automatically extended as necessary as just explained. For the bounded containers, if an operation would cause the capacity to be exceeded then Capacity_Error is raised.
There are a number of other differences between the unbounded and bounded containers. The original unbounded containers have pragma Preelaborate whereas the new bounded containers have pragma Pure.
The bounded containers for hashed maps and hashed sets are treated somewhat differently to those for the corresponding unbounded containers regarding hashing.
In the case of unbounded containers, the hashing function to be used is left to the user and is provided as an actual generic parameter. For example, in the case of hashed sets, the package specification begins
generic
   type Element_Type is private;
   with function Hash(Element: Element_Type) return Hash_Type;
   with function Equivalent_Elements(Left, Right: Element_Type)
            return Boolean;
   with function "=" (Left, Right: Element_Type) return Boolean is <>;
package Ada.Containers.Hashed_Sets is
   pragma Preelaborate(Hashed_Sets);
What the implementation actually does with the hash function is entirely up to the implementation The value returned is in the range of Hash_Type which is a modular type declared in the root package Ada.Containers. The implementation will typically then map this value onto the current range of the capacity in some way. If the unbounded container becomes nearly full then the capacity will be automatically extended and a new mapping will be required; this in turn is likely to require the existing contents to be rehashed. None of this is visible to the user.
In the case of the new bounded containers, these problems do not arise since the capacity is fixed. Moreover, the modulus to be used for the mapping is given when the container is declared since the type has discriminants thus
type Set(Capacity: Count_Type; Modulus: Hash_Type) is tagged private;
The user can then choose the modulus explicitly or alternatively can use the additional function Default_Modulus whose specification is
function Default_Modulus(Capacity: Count_Type)
            return Hash_Type;
This returns an implementation defined value for the number of distinct hash values to be used for the given capacity. Thus we can write
My_Set: Set(Capacity => My_Cap, Modulus => Default_Modulus(My_Cap));
Moreover, for these bounded hashed maps and sets, the function Copy has an extra parameter thus
function Copy
            (Source: Set;
             Capacity: Count_Type := 0;
             Modulus: Hash_Type := 0) return Set;
If the capacity is given as zero then the newly returned set has the same capacity as the length of Source as mentioned above. If the modulus is given as zero then the value to be used is obtained by applying Default_Modulus to the new capacity.
As mentioned in Section 7.5 on hashing and comparison, Ada 2012 introduces additional functions for hashing strings (fixed, bounded and unbounded) to provide for case insensitive, wide and wide wide situations.
Finally, note that there are no bounded containers for indefinite types. This is because the size of an object of an indefinite type (such as String) is generally not known and so indefinite types need some dynamic storage management. However, the whole point of introducing bounded containers was to avoid such management.

Contents   Index   References   Search   Previous   Next 
© 2011, 2012, 2013 John Barnes Informatics.
Sponsored in part by:
The Ada Resource Association:

    ARA
  AdaCore:


    AdaCore
and   Ada-Europe:

Ada-Europe