A.18.4 Maps
{
AI95-00302-03}
The language-defined generic packages Containers.Hashed_Maps and Containers.Ordered_Maps
provide private types Map and Cursor, and a set of operations for each
type. A map container allows an arbitrary type to be used as a key to
find the element associated with that key. A hashed map uses a hash function
to organize the keys, while an ordered map orders the keys per a specified
relation.
{
AI95-00302-03}
{
AI05-0299-1}
This subclause describes the declarations that are common to both kinds
of maps. See
A.18.5 for a description of
the semantics specific to Containers.Hashed_Maps and
A.18.6
for a description of the semantics specific to Containers.Ordered_Maps.
Static Semantics
{
AI95-00302-03}
The actual function for the generic formal function "=" on
Element_Type values is expected to define a reflexive and symmetric relationship
and return the same result value each time it is called with a particular
pair of values. If it behaves in some other manner, the function "="
on map values returns an unspecified value. The exact arguments and number
of calls of this generic formal function by the function "="
on map values are unspecified.
Ramification: If the actual function
for "=" is not symmetric and consistent, the result returned
by "=" for Map objects cannot be predicted. The implementation
is not required to protect against "=" raising an exception,
or returning random results, or any other “bad” behavior.
And it can call "=" in whatever manner makes sense. But note
that only the result of "=" for Map objects is unspecified;
other subprograms are not allowed to break if "=" is bad (they
aren't expected to use "=").
{
AI95-00302-03}
The type Map is used to represent maps. The type Map needs finalization
(see
7.6).
{
AI95-00302-03}
A map contains pairs of keys and elements, called
nodes. Map cursors designate nodes, but also can be thought of
as designating an element (the element contained in the node) for consistency
with the other containers. There exists an equivalence relation on keys,
whose definition is different for hashed maps and ordered maps. A map
never contains two or more nodes with equivalent keys. The
length
of a map is the number of nodes it contains.
{
AI95-00302-03}
Each nonempty
map has two particular nodes called the
first node and the
last
node (which may be the same). Each node except for the last node
has a
successor node. If there are no other intervening operations,
starting with the first node and repeatedly going to the successor node
will visit each node in the map exactly once until the last node is reached.
The exact definition of these terms is different for hashed maps and
ordered maps.
{
AI95-00302-03}
{
AI12-0111-1}
{
AI12-0112-1}
[Some operations
check for “tampering
with cursors” of a container because they depend on the set of
elements of the container remaining constant, and others check for “tampering
with elements” of a container because they depend on elements of
the container not being replaced.] When tampering with cursors is
prohibited
for a particular map object
M, Program_Error
is propagated by the finalization of
M[, as well as by a call
that passes
M to certain of the operations of this package, as
indicated by the precondition of such an operation]. Similarly, when
tampering with elements is
prohibited for
M, Program_Error
is propagated by a call that passes
M to certain of the other
operations of this package, as indicated by the precondition of such
an operation.
Paragraphs 8 through
15 are removed as preconditions now describe these rules.
Ramification: We don't need to explicitly
mention
assignment_statement,
because that finalizes the target object as part of the operation, and
finalization of an object is already defined as tampering with cursors.
{
AI95-00302-03}
Empty_Map represents the empty Map object. It has a length of 0. If an
object of type Map is not otherwise initialized, it is initialized to
the same value as Empty_Map.
{
AI95-00302-03}
No_Element represents a cursor that designates no node. If an object
of type Cursor is not otherwise initialized, it is initialized to the
same value as No_Element.
{
AI95-00302-03}
{
AI12-0434-1}
The primitive "=" operator for type Cursor returns True if
both cursors are No_Element, or designate the same element in the same
container.
To be honest: {
AI12-0434-1}
“The primitive "=" operator” is the one with two
parameters of type Cursor which returns Boolean. We're not talking about
some other (hidden) primitive function named "=".
{
AI95-00302-03}
Execution of the default implementation of the Input, Output, Read, or
Write attribute of type Cursor raises Program_Error.
Reason: A cursor will probably be implemented
in terms of one or more access values, and the effects of streaming access
values is unspecified. Rather than letting the user stream junk by accident,
we mandate that streaming of cursors raise Program_Error by default.
The attributes can always be specified if there is a need to support
streaming.
{
AI05-0001-1}
{
AI05-0262-1}
{
AI12-0437-1}
Map'Write for a Map object
M writes Length(
M) elements
of the map to the stream. It may also write additional information about
the map.
{
AI05-0001-1}
{
AI05-0262-1}
Map'Read reads the representation of a map from the stream, and assigns
to
Item a map with the same length and elements as was written
by Map'Write.
Ramification: Streaming more elements
than the container length is wrong. For implementation implications of
this rule, see the Implementation Note in
A.18.2.
{
AI12-0112-1}
function Has_Element (Position : Cursor)
return Boolean
with Nonblocking, Global =>
in all, Use_Formal =>
null;
{
AI05-0212-1}
Returns True if Position designates an element, and returns False otherwise.
To be honest: {
AI05-0005-1}
{
AI05-0212-1}
This function might not detect cursors that designate deleted elements;
such cursors are invalid (see below) and the result of calling Has_Element
with an invalid cursor is unspecified (but not erroneous).
{
AI12-0112-1}
function Has_Element (Container : Map; Position : Cursor)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
Returns True if Position designates an element in Container, and returns
False otherwise.
Ramification: {
AI12-0112-1}
If Position is No_element, Has_Element returns False.
function "=" (Left, Right : Map) return Boolean;
{
AI95-00302-03}
If Left and Right denote the same map object, then the function returns
True. If Left and Right have different lengths, then the function returns
False. Otherwise, for each key
K in Left, the function returns
False if:
a key equivalent to K is not present
in Right; or
the element associated with K in
Left is not equal to the element associated with K in Right (using
the generic formal equality operator for elements).
If the function
has not returned a result after checking all of the keys, it returns
True. Any exception raised during evaluation of key equivalence or element
equality is propagated.
Implementation Note: This wording describes
the canonical semantics. However, the order and number of calls on the
formal equality function is unspecified for all of the operations that
use it in this package, so an implementation can call it as many or as
few times as it needs to get the correct answer. Specifically, there
is no requirement to call the formal equality additional times once the
answer has been determined.
function Tampering_With_Cursors_Prohibited
(Container : Map) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
{
AI12-0112-1}
Returns True if tampering with cursors or tampering with elements is
currently prohibited for Container, and returns False otherwise.
Reason: {
AI12-0112-1}
Prohibiting tampering with elements also needs to prohibit tampering
with cursors, as deleting an element is similar to replacing it.
Implementation Note: {
AI12-0112-1}
Various contracts elsewhere in this specification require that this function
be implemented with synchronized data. Moreover, it is possible for tampering
to be prohibited by multiple operations (sequentially or in parallel).
Therefore, tampering needs to be implemented with an atomic or protected
counter. The counter is initialized to zero, and is incremented when
tampering is prohibited, and decremented when leaving an area that prohibited
tampering. Function Tampering_With_Cursors_Prohibited returns True if
the counter is nonzero. (Note that any case where the result is not well-defined
for one task is incorrect use of shared variables and would be erroneous
by the rules of
9.10, so no special protection
is needed to read the counter.)
function Tampering_With_Elements_Prohibited
(Container : Map) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
{
AI12-0112-1}
Always returns False[, regardless of whether tampering with elements
is prohibited].
Reason: {
AI12-0111-1}
A definite element cannot change size, so we allow operations that tamper
with elements even when tampering with elements is prohibited. That's
not true for the indefinite containers, which is why this kind of tampering
exists.
{
AI12-0112-1}
function Length (Container : Map)
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
function Is_Empty (Container : Map) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);
{
AI12-0112-1}
procedure Clear (Container :
in out Map)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
function Key (Position : Cursor) return Key_Type
with Pre => Position /= No_Element
or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Key_Type;
function Key (Container : Map;
Position : Cursor) return Key_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Key_Type;
{
AI12-0112-1}
Key returns the key component of the node designated by Position.
function Element (Position : Cursor) return Element_Type
with Pre => Position /= No_Element
or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;
function Element (Container : Map;
Position : Cursor) return Element_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Element_Type;
{
AI12-0112-1}
Element returns the element component of the node designated by Position.
procedure Replace_Element (Container : in out Map;
Position : in Cursor;
New_item : in Element_Type)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI12-0112-1}
{
AI12-0196-1}
Replace_Element assigns New_Item to the element of the node designated
by Position. For the purposes of determining whether the parameters overlap
in a call to Replace_Element, the Container parameter is not considered
to overlap with any object [(including itself)].
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in Element_Type))
with Pre => Position /= No_Element
or else raise Constraint_Error,
Global => in all;
{
AI95-00302-03}
{
AI05-0021-1}
{
AI05-0265-1}
{
AI12-0112-1}
Query_Element calls Process.
all with the key and element from
the node designated by Position as the arguments. Tampering with the
elements of the map that contains the element designated by Position
is prohibited during the execution of the call on Process.
all.
Any exception raised by Process.
all is propagated.
procedure Query_Element
(Container : in Map;
Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
{
AI12-0112-1}
Query_Element calls Process.
all with the key and element from
the node designated by Position as the arguments. Tampering with the
elements of Container is prohibited during the execution of the call
on Process.
all. Any exception raised by Process.
all is
propagated.
procedure Update_Element
(Container : in out Map;
Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in out Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
{
AI95-00302-03}
{
AI05-0264-1}
{
AI05-0265-1}
{
AI12-0112-1}
Update_Element calls Process.
all with the key and element from
the node designated by Position as the arguments. Tampering with the
elements of Container is prohibited during the execution of the call
on Process.
all. Any exception raised by Process.
all is
propagated.
If Element_Type
is unconstrained and definite, then the actual Element parameter of Process.all
shall be unconstrained.
Ramification: This means that the elements
cannot be directly allocated from the heap; it must be possible to change
the discriminants of the element in place.
{
AI12-0112-1}
type Constant_Reference_Type
(Element :
not null access constant Element_Type)
is private
with Implicit_Dereference => Element,
Nonblocking, Global =>
in out synchronized,
Default_Initial_Condition => (
raise Program_Error);
{
AI12-0112-1}
type Reference_Type (Element :
not null access Element_Type)
is private
with Implicit_Dereference => Element,
Nonblocking, Global =>
in out synchronized,
Default_Initial_Condition => (
raise Program_Error);
{
AI05-0212-1}
The types Constant_Reference_Type and Reference_Type need finalization.
Reason: It is expected that Reference_Type
(and Constant_Reference_Type) will be a controlled type, for which finalization
will have some action to terminate the tampering check for the associated
container. If the object is created by default, however, there is no
associated container. Since this is useless, and supporting this case
would take extra work, we define it to raise an exception.
{
AI12-0112-1}
function Constant_Reference (Container :
aliased in Map;
Position :
in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI05-0212-1}
{
AI05-0269-1}
This function (combined with the Constant_Indexing and Implicit_Dereference
aspects) provides a convenient way to gain read access to an individual
element of a Map given a cursor.
{
AI05-0212-1}
{
AI05-0265-1}
{
AI12-0112-1}
Constant_Reference returns an object whose discriminant is an access
value that designates the element designated by Position. Tampering with
the elements of Container is prohibited while the object returned by
Constant_Reference exists and has not been finalized.
{
AI12-0112-1}
function Reference (Container :
aliased in out Map;
Position :
in Cursor)
return Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI05-0212-1}
{
AI05-0269-1}
This function (combined with the Variable_Indexing and Implicit_Dereference
aspects) provides a convenient way to gain read and write access to an
individual element of a Map given a cursor.
{
AI05-0212-1}
{
AI05-0265-1}
{
AI12-0112-1}
Reference returns an object whose discriminant is an access value that
designates the element designated by Position. Tampering with the elements
of Container is prohibited while the object returned by Reference exists
and has not been finalized.
{
AI12-0112-1}
function Constant_Reference (Container :
aliased in Map;
Key :
in Key_Type)
return Constant_Reference_Type
with Pre => Find (Container, Key) /= No_Element
or else raise Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI05-0212-1}
{
AI05-0269-1}
This function (combined with the Constant_Indexing and Implicit_Dereference
aspects) provides a convenient way to gain read access to an individual
element of a map given a key value.
Equivalent to Constant_Reference (Container, Find
(Container, Key)).
{
AI12-0112-1}
function Reference (Container :
aliased in out Map;
Key :
in Key_Type)
return Reference_Type
with Pre => Find (Container, Key) /= No_Element
or else raise Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI05-0212-1}
{
AI05-0269-1}
This function (combined with the Variable_Indexing and Implicit_Dereference
aspects) provides a convenient way to gain read and write access to an
individual element of a map given a key value.
Equivalent to Reference (Container, Find (Container,
Key)).
{
AI12-0112-1}
procedure Assign (Target :
in out Map; Source :
in Map)
with Pre =>
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target);
{
AI05-0001-1}
{
AI05-0248-1}
If Target denotes the same object as Source, the operation has no effect.
Otherwise, the key/element pairs of Source are copied to Target as for
an
assignment_statement
assigning Source to Target.
Discussion: {
AI05-0005-1}
This routine exists for compatibility with the bounded map containers.
For an unbounded map,
Assign(A, B) and
A := B behave
identically. For a bounded map, := will raise an exception if the container
capacities are different, while Assign will not raise an exception if
there is enough room in the target.
{
AI12-0112-1}
procedure Move (Target :
in out Map;
Source :
in out Map)
with Pre => (
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error)
and then
(
not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (
if not Target'Has_Same_Storage (Source)
then
Length (Target) = Length (Source'Old)
and then
Length (Source) = 0);
{
AI95-00302-03}
{
AI05-0001-1}
{
AI05-0248-1}
{
AI05-0262-1}
If Target denotes the same object as Source, then the operation has no
effect. Otherwise, the operation is equivalent to Assign (Target, Source)
followed by Clear (Source).
{
AI12-0112-1}
procedure Insert (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type;
Position :
out Cursor;
Inserted :
out Boolean)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (
declare
Original_Length :
constant Count_Type :=
Length (Container)'Old;
begin
Has_Element (Container, Position)
and then
(
if Inserted
then
Length (Container) = Original_Length + 1
else
Length (Container) = Original_Length));
{
AI95-00302-03}
Insert checks if a node with a key equivalent to Key is already present
in Container. If a match is found, Inserted is set to False and Position
designates the element with the matching key. Otherwise, Insert allocates
a new node, initializes it to Key and New_Item, and adds it to Container;
Inserted is set to True and Position designates the newly-inserted node.
Any exception raised during allocation is propagated and Container is
not modified.
{
AI12-0112-1}
procedure Insert (Container :
in out Map;
Key :
in Key_Type;
Position :
out Cursor;
Inserted :
out Boolean)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (
declare
Original_Length :
constant Count_Type :=
Length (Container)'Old;
begin
Has_Element (Container, Position)
and then
(
if Inserted
then
Length (Container) = Original_Length + 1
else
Length (Container) = Original_Length));
{
AI95-00302-03}
Insert inserts Key into Container as per the five-parameter Insert, with
the difference that an element initialized by default (see
3.3.1)
is inserted.
{
AI12-0112-1}
procedure Insert (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => Length (Container) = Length (Container)'Old + 1;
{
AI95-00302-03}
Insert inserts Key and New_Item into Container as per the five-parameter
Insert, with the difference that if a node with a key equivalent to Key
is already in the map, then Constraint_Error is propagated.
Ramification:
This is equivalent to:
declare
Inserted : Boolean; C : Cursor;
begin
Insert (Container, Key, New_Item, C, Inserted);
if not Inserted then
raise Constraint_Error;
end if;
end;
but doesn't require the hassle of out
parameters.
{
AI12-0112-1}
procedure Include (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type)
with Pre => (
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error)
and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (
declare
Original_Length :
constant Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in Original_Length | Original_Length + 1);
{
AI95-00302-03}
Include inserts Key and New_Item into Container as per the five-parameter
Insert, with the difference that if a node with a key equivalent to Key
is already in the map, then this operation assigns Key and New_Item to
the matching node. Any exception raised during assignment is propagated.
Ramification:
This is equivalent to:
declare
C : Cursor := Find (Container, Key);
begin
if C = No_Element then
Insert (Container, Key, New_Item);
else
Replace (Container, Key, New_Item);
end if;
end;
but this avoids doing the search twice.
{
AI12-0112-1}
procedure Replace (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = Length (Container)'Old;
{
AI95-00302-03}
Replace checks if a node with a key equivalent to Key is present in Container.
If a match is found, Replace assigns Key and New_Item to the matching
node; otherwise, Constraint_Error is propagated.
Discussion: We update the key as well
as the element, as the key might include additional information that
does not participate in equivalence. If only the element needs to be
updated, use Replace_Element (Find (Container, Key), New_Element).
{
AI12-0112-1}
procedure Exclude (Container :
in out Map;
Key :
in Key_Type)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (
declare
Original_Length :
constant Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in Original_Length - 1 | Original_Length);
{
AI95-00302-03}
Exclude checks if a node with a key equivalent to Key is present in Container.
If a match is found, Exclude removes the node from the map.
Ramification: Exclude should work on
an empty map; nothing happens in that case.
{
AI12-0112-1}
procedure Delete (Container :
in out Map;
Key :
in Key_Type)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = Length (Container)'Old - 1;
{
AI95-00302-03}
Delete checks if a node with a key equivalent to Key is present in Container.
If a match is found, Delete removes the node from the map; otherwise,
Constraint_Error is propagated.
procedure Delete (Container : in out Map;
Position : in out Cursor)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Length (Container) = Length (Container)'Old - 1 and then
Position = No_Element;
Ramification: The check on Position checks
that the cursor does not belong to some other map. This check implies
that a reference to the map is included in the cursor value. This wording
is not meant to require detection of dangling cursors; such cursors are
defined to be invalid, which means that execution is erroneous, and any
result is allowed (including not raising an exception).
{
AI12-0112-1}
function First (Container : Map)
return Cursor
with Nonblocking, Global =>
null, Use_Formal =>
null,
Post => (
if not Is_Empty (Container)
then Has_Element (Container, First'Result)
else First'Result = No_Element);
{
AI95-00302-03}
If Length (Container) = 0, then First returns No_Element. Otherwise,
First returns a cursor that designates the first node in Container.
{
AI12-0112-1}
function Next (Position : Cursor)
return Cursor
with Nonblocking, Global =>
in all, Use_Formal =>
null,
Post => (
if Position = No_Element
then Next'Result = No_Element);
{
AI95-00302-03}
Returns a cursor that designates the successor of the node designated
by Position. If Position designates the last node, then No_Element is
returned. If Position equals No_Element, then No_Element is returned.
function Next (Container : Map;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then Next'Result = No_Element
elsif Next'Result = No_Element then
Position = Last (Container)
else Has_Element (Container, Next'Result));
{
AI12-0112-1}
Returns a cursor designating the successor of the node designated by
Position in Container.
{
AI12-0112-1}
procedure Next (Position :
in out Cursor)
with Nonblocking, Global =>
in all, Use_Formal =>
null;
procedure Next (Container : in Map;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
{
AI12-0112-1}
Equivalent to Position := Next (Container, Position).
{
AI12-0112-1}
function Find (Container : Map;
Key : Key_Type)
return Cursor
with Post => (
if Find'Result = No_Element
then Has_Element (Container, Find'Result));
{
AI95-00302-03}
If Length (Container) equals 0, then Find returns No_Element. Otherwise,
Find checks if a node with a key equivalent to Key is present in Container.
If a match is found, a cursor designating the matching node is returned;
otherwise, No_Element is returned.
function Element (Container : Map;
Key : Key_Type) return Element_Type;
function Contains (Container : Map;
Key : Key_Type) return Boolean;
{
AI95-00302-03}
Equivalent to Find (Container, Key) /= No_Element.
Paragraphs 72
and 73 were moved above.
{
AI12-0112-1}
procedure Iterate
(Container :
in Map;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
AI95-00302-03}
{
AI05-0265-1}
Iterate calls Process.
all with a cursor that designates each node
in Container, starting with the first node and moving the cursor according
to the successor relation. Tampering with the cursors of Container is
prohibited during the execution of a call on Process.
all. Any
exception raised by Process.
all is propagated.
Implementation Note: The “tamper
with cursors” check takes place when the operations that insert
or delete elements, and so on, are called.
See Iterate for vectors (
A.18.2)
for a suggested implementation of the check.
{
AI12-0111-1}
The nested package Stable provides a type Stable.Map that represents
a
stable map,
which is one that cannot grow
and shrink. Such a map can be created by calling the Copy function, or
by establishing a
stabilized view of an ordinary map.
{
AI12-0111-1}
The subprograms of the map package that have a parameter or result of
type Map are included in the nested package Stable with the same specification,
except that the following are omitted:
Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited,
Assign, Move, Insert, Include, Clear, Delete, Exclude, (for Ordered_Maps)
Delete_First and Delete_Last, and (for Hashed_Maps) Reserve_Capacity
Ramification: The names Map and Cursor
mean the types declared in the nested package in these subprogram specifications.
Reason: The omitted routines are those
that tamper with cursors or elements (or test that state). The model
is that it is impossible to tamper with cursors or elements of a stable
view since no such operations are included. Thus tampering checks are
not needed for a stable view, and we omit the operations associated with
those checks.
{
AI12-0111-1}
The operations of this package are equivalent to those for ordinary maps,
except that the calls to Tampering_With_Cursors_Prohibited and Tampering_With_Elements_Prohibited
that occur in preconditions are replaced by False, and any that occur
in postconditions are replaced by True.
{
AI12-0111-1}
{
AI12-0439-1}
If a stable map is declared with the Base discriminant designating a
pre-existing ordinary map, the stable map represents a stabilized view
of the underlying ordinary map, and any operation on the stable map is
reflected on the underlying ordinary map. While a stabilized view exists,
any operation that tampers with elements performed on the underlying
map is prohibited. The finalization of a stable map that provides such
a view removes this restriction on the underlying ordinary map [(though
some other restriction can exist due to other concurrent iterations or
stabilized views)].
{
AI12-0111-1}
{
AI12-0438-1}
If a stable map is declared without specifying Base, the object is necessarily
initialized. The initializing expression of the stable map, [typically
a call on Copy], determines the Length of the map. The Length of a stable
map never changes after initialization.
Proof: {
AI12-0438-1}
Initialization is required as the type is indefinite, see
3.3.1.
Bounded (Run-Time) Errors
{
AI05-0022-1}
{
AI05-0248-1}
It is a bounded error for the actual function associated
with a generic formal subprogram, when called as part of an operation
of a map package, to tamper with elements of any map parameter of the
operation. Either Program_Error is raised, or the operation works as
defined on the value of the map either prior to, or subsequent to, some
or all of the modifications to the map.
{
AI05-0027-1}
It is a bounded error to call any subprogram declared
in the visible part of a map package when the associated container has
been finalized. If the operation takes Container as an
in out
parameter, then it raises Constraint_Error or Program_Error. Otherwise,
the operation either proceeds as it would for an empty container, or
it raises Constraint_Error
or Program_Error.
Erroneous Execution
{
AI95-00302-03}
A Cursor value is
invalid if any of the following have occurred
since it was created:
The map that contains the node it designates has
been finalized;
The map that contains the node it designates has
been used as the Source or Target of a call to Move; or
{
AI05-0160-1}
{
AI05-0262-1}
The node it designates has been removed from the map that previously
contained the node.
Ramification: {
AI05-0160-1}
This can happen directly via calls to Clear, Exclude, and Delete.
The result of "=" or Has_Element is unspecified
if these functions are called with an invalid cursor parameter.
Execution is erroneous if any other subprogram declared in Containers.Hashed_Maps
or Containers.Ordered_Maps is called with an invalid cursor parameter.
Discussion: The list above is intended
to be exhaustive. In other cases, a cursor value continues to designate
its original element. For instance, cursor values survive the insertion
and deletion of other nodes.
While it is possible to check for these cases,
in many cases the overhead necessary to make the check is substantial
in time or space. Implementations are encouraged to check for as many
of these cases as possible and raise Program_Error if detected.
{
AI05-0212-1}
Execution is erroneous if the map associated with the result of a call
to Reference or Constant_Reference is finalized before the result object
returned by the call to Reference or Constant_Reference is finalized.
Reason: Each object of Reference_Type
and Constant_Reference_Type probably contains some reference to the originating
container. If that container is prematurely finalized (which is only
possible via Unchecked_Deallocation, as accessibility checks prevent
passing a container to Reference that will not live as long as the result),
the finalization of the object of Reference_Type will try to access a
nonexistent object. This is a normal case of a dangling pointer created
by Unchecked_Deallocation; we have to explicitly mention it here as the
pointer in question is not visible in the specification of the type.
(This is the same reason we have to say this for invalid cursors.)
Implementation Requirements
{
AI95-00302-03}
{
AI05-0262-1}
The execution of an
assignment_statement
for a map shall have the effect of copying the elements from the source
map object to the target map object and changing the length of the target
object to that of the source object.
Implementation Note: {
AI05-0298-1}
An assignment of a Map is a “deep” copy; that is the elements
are copied as well as the data structures. We say “effect of”
in order to allow the implementation to avoid copying elements immediately
if it wishes. For instance, an implementation that avoided copying until
one of the containers is modified would be allowed. (Note that this implementation
would require care, see
A.18.2 for more.)
Implementation Advice
{
AI95-00302-03}
Move should not copy elements, and should minimize copying of internal
data structures.
Implementation Advice: Move for a map
should not copy elements, and should minimize copying of internal data
structures.
Implementation Note: Usually that can
be accomplished simply by moving the pointer(s) to the internal data
structures from the Source container to the Target container.
{
AI95-00302-03}
If an exception is propagated from a map operation, no storage should
be lost, nor any elements removed from a map unless specified by the
operation.
Implementation Advice: If an exception
is propagated from a map operation, no storage should be lost, nor any
elements removed from a map unless specified by the operation.
Reason: This is important so that programs
can recover from errors. But we don't want to require heroic efforts,
so we just require documentation of cases where this can't be accomplished.
Wording Changes from Ada 95
{
AI95-00302-03}
This description of maps is new; the extensions are documented with the
specific packages.
Extensions to Ada 2005
{
AI05-0212-1}
Added reference support to make map containers more
convenient to use.
Wording Changes from Ada 2005
{
AI05-0001-1}
Added procedure Assign; the extension and incompatibility is documented
with the specific packages.
{
AI05-0001-1}
Generalized the definition of Move. Specified which elements are read/written
by stream attributes.
{
AI05-0022-1}
Correction: Added a Bounded (Run-Time) Error to cover tampering
by generic actual subprograms.
{
AI05-0027-1}
Correction: Added a Bounded (Run-Time) Error to cover access to
finalized map containers.
{
AI05-0160-1}
Correction: Revised the definition of invalid cursors to cover
missing (and new) cases.
{
AI05-0265-1}
Correction: Defined when a container prohibits tampering in order
to more clearly define where the check is made and the exception raised.
Inconsistencies With Ada 2012
{
AI12-0111-1}
Correction: Tampering with elements is now
defined to be equivalent to tampering with cursors for ordinary containers.
If a program requires tampering detection to work, it might fail in Ada
2022. Needless to say, this shouldn't happen outside of test programs.
See Inconsistencies With Ada 2012 in
A.18.2
for more details.
Extensions to Ada 2012
{
AI12-0196-1}
Correction: Replace_Element is now defined
such that it can be used concurrently so long as it operates on different
elements. This allows some container operations to be used in parallel
without separate synchronization.
Wording Changes from Ada 2012
{
AI12-0110-1}
Correction: Clarified that tampering checks precede all other
checks made by a subprogram (but come after those associated with the
call).
{
AI12-0112-1}
Added contracts to this container. This includes describing some of the
semantics with pre- and postconditions, rather than English text. Note
that the preconditions can be Suppressed (see
11.5).
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
