Rationale for Ada 2012
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.
© 2011, 2012, 2013 John Barnes Informatics.
Sponsored in part by: