Annotated Ada Reference ManualLegal Information
Contents   Index   References   Search   Previous   Next 

A.18.4 Maps

1/2
{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.
2/3
{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

3/2
{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.
3.a/2
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 "="). 
4/2
{AI95-00302-03} The type Map is used to represent maps. The type Map needs finalization (see 7.6).
5/2
{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.
6/2
{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.
7/2
{AI95-00302-03} [Some operations of these generic packages have access-to-subprogram parameters. To ensure such operations are well-defined, they guard against certain actions by the designated subprogram. In particular, 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.]
8/2
{AI95-00302-03} A subprogram is said to tamper with cursors of a map object M if:
9/2
it inserts or deletes elements of M, that is, it calls the Insert, Include, Clear, Delete, or Exclude procedures with M as a parameter; or
9.a/2
To be honest: Operations which are defined to be equivalent to a call on one of these operations also are included. Similarly, operations which call one of these as part of their definition are included. 
10/2
it finalizes M; or
10.1/3
{AI05-0001-1} it calls the Assign procedure with M as the Target parameter; or
10.a/3
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.
11/2
it calls the Move procedure with M as a parameter; or
12/2
it calls one of the operations defined to tamper with the cursors of M.
12.a/2
Ramification: Replace only modifies a key and element rather than rehashing, so it does not tamper with cursors.
13/2
{AI95-00302-03} A subprogram is said to tamper with elements of a map object M if:
14/2
it tampers with cursors of M; or
15/2
it replaces one or more elements of M, that is, it calls the Replace or Replace_Element procedures with M as a parameter.
15.a/2
Reason: Complete replacement of an element can cause its memory to be deallocated while another operation is holding onto a reference to it. That can't be allowed. However, a simple modification of (part of) an element is not a problem, so Update_Element does not cause a problem. 
15.1/4
  {AI05-0265-1} {AI12-0110-1} When tampering with cursors is prohibited for a particular map object M, Program_Error is propagated by a call of any language-defined subprogram that is defined to tamper with the cursors of M, leaving M unmodified. Similarly, when tampering with elements is prohibited for a particular map object M, Program_Error is propagated by a call of any language-defined subprogram that is defined to tamper with the elements of M [(or tamper with the cursors of M)], leaving M unmodified. These checks are made before any other defined behavior of the body of the language-defined subprogram. 
15.b/3
Proof: Tampering with elements includes tampering with cursors, so we mention it only from completeness in the second sentence. 
16/2
{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.
17/2
{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.
18/2
{AI95-00302-03} The predefined "=" operator for type Cursor returns True if both cursors are No_Element, or designate the same element in the same container.
19/2
{AI95-00302-03} Execution of the default implementation of the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.
19.a/2
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. 
19.1/3
  {AI05-0001-1} {AI05-0262-1} Map'Write for a Map object M writes Length(M) elements of the map to the stream. It also may write additional information about the map.
19.2/3
  {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.
19.b/3
Ramification: Streaming more elements than the container length is wrong. For implementation implications of this rule, see the Implementation Note in A.18.2.
19.3/3
function Has_Element (Position : Cursor) return Boolean;
19.4/3
{AI05-0212-1} Returns True if Position designates an element, and returns False otherwise.
19.c/3
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). 
20/2
function "=" (Left, Right : Map) return Boolean;
21/2
{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:
22/2
a key equivalent to K is not present in Right; or
23/2
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). 
24/2
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. 
24.a/2
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. 
25/2
function Length (Container : Map) return Count_Type;
26/2
{AI95-00302-03} Returns the number of nodes in Container.
27/2
function Is_Empty (Container : Map) return Boolean;
28/2
{AI95-00302-03} Equivalent to Length (Container) = 0.
29/2
procedure Clear (Container : in out Map);
30/2
{AI95-00302-03} Removes all the nodes from Container.
31/2
function Key (Position : Cursor) return Key_Type;
32/2
{AI95-00302-03} If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Key returns the key component of the node designated by Position.
33/2
function Element (Position : Cursor) return Element_Type;
34/2
{AI95-00302-03} If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Element returns the element component of the node designated by Position.
35/2
procedure Replace_Element (Container : in out Map;
                           Position  : in     Cursor;
                           New_Item  : in     Element_Type);
36/3
{AI95-00302-03} {AI05-0264-1} If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Replace_Element assigns New_Item to the element of the node designated by Position.
37/2
procedure Query_Element
  (Position : in Cursor;
   Process  : not null access procedure (Key     : in Key_Type;
                                         Element : in Element_Type));
38/3
{AI95-00302-03} {AI05-0021-1} {AI05-0265-1} If Position equals No_Element, then Constraint_Error is propagated. Otherwise, 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.
39/2
procedure Update_Element
  (Container : in out Map;
   Position  : in     Cursor;
   Process   : not null access procedure (Key     : in     Key_Type;
                                          Element : in out Element_Type));
40/3
{AI95-00302-03} {AI05-0264-1} {AI05-0265-1} If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, 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.
41/2
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
41.a/2
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. 
41.1/3
type Constant_Reference_Type
      (Element : not null access constant Element_Type) is private
   with Implicit_Dereference => Element;
41.2/3
type Reference_Type (Element : not null access Element_Type) is private
   with Implicit_Dereference => Element;
41.3/3
{AI05-0212-1} The types Constant_Reference_Type and Reference_Type need finalization.
41.4/3
The default initialization of an object of type Constant_Reference_Type or Reference_Type propagates Program_Error.
41.b/3
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. 
41.5/3
function Constant_Reference (Container : aliased in Map;
                             Position  : in Cursor)
   return Constant_Reference_Type;
41.6/3
{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.
41.7/3
{AI05-0212-1} {AI05-0265-1} If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, 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.
41.8/3
function Reference (Container : aliased in out Map;
                    Position  : in Cursor)
   return Reference_Type;
41.9/3
{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.
41.10/3
{AI05-0212-1} {AI05-0265-1} If Position equals No_Element, then Constraint_Error is propagated; if Position does not designate an element in Container, then Program_Error is propagated. Otherwise, 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.
41.11/3
function Constant_Reference (Container : aliased in Map;
                             Key       : in Key_Type)
   return Constant_Reference_Type;
41.12/3
{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.
41.13/3
Equivalent to Constant_Reference (Container, Find (Container, Key)).
41.14/3
function Reference (Container : aliased in out Map;
                    Key       : in Key_Type)
   return Reference_Type;
41.15/3
{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.
41.16/3
Equivalent to Reference (Container, Find (Container, Key)).
41.17/3
procedure Assign (Target : in out Map; Source : in Map);
41.18/3
{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. 
41.c/3
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. 
42/2
procedure Move (Target : in out Map;
                Source : in out Map);
43/3
{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).
44/2
procedure Insert (Container : in out Map;
                  Key       : in     Key_Type;
                  New_Item  : in     Element_Type;
                  Position  :    out Cursor;
                  Inserted  :    out Boolean);
45/2
{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.
46/2
procedure Insert (Container : in out Map;
                  Key       : in     Key_Type;
                  Position  :    out Cursor;
                  Inserted  :    out Boolean);
47/2
{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.
48/2
procedure Insert (Container : in out Map;
                  Key       : in     Key_Type;
                  New_Item  : in     Element_Type);
49/2
{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.
49.a/2
Ramification: This is equivalent to: 
49.b/2
declare
  Inserted : Boolean; C : Cursor;
begin
  Insert (Container, Key, New_Item, C, Inserted);
  if not Inserted then
     raise Constraint_Error;
  end if;
end;
49.c/2
but doesn't require the hassle of out parameters. 
50/2
procedure Include (Container : in out Map;
                   Key       : in     Key_Type;
                   New_Item  : in     Element_Type);
51/2
{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.
51.a/2
Ramification: This is equivalent to: 
51.b/2
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;
51.c/2
but this avoids doing the search twice. 
52/2
procedure Replace (Container : in out Map;
                   Key       : in     Key_Type;
                   New_Item  : in     Element_Type);
53/2
{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.
53.a/2
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). 
54/2
procedure Exclude (Container : in out Map;
                   Key       : in     Key_Type);
55/2
{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.
55.a/2
Ramification: Exclude should work on an empty map; nothing happens in that case. 
56/2
procedure Delete (Container : in out Map;
                  Key       : in     Key_Type);
57/2
{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.
58/2
procedure Delete (Container : in out Map;
                  Position  : in out Cursor);
59/2
{AI95-00302-03} If Position equals No_Element, then Constraint_Error is propagated. If Position does not designate an element in Container, then Program_Error is propagated. Otherwise, Delete removes the node designated by Position from the map. Position is set to No_Element on return.
59.a/2
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). 
60/2
function First (Container : Map) return Cursor;
61/2
{AI95-00302-03} If Length (Container) = 0, then First returns No_Element. Otherwise, First returns a cursor that designates the first node in Container.
62/2
function Next (Position  : Cursor) return Cursor;
63/2
{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.
64/2
procedure Next (Position  : in out Cursor);
65/2
{AI95-00302-03} Equivalent to Position := Next (Position).
66/2
function Find (Container : Map;
               Key       : Key_Type) return Cursor;
67/2
{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.
68/2
function Element (Container : Map;
                  Key       : Key_Type) return Element_Type;
69/2
{AI95-00302-03} Equivalent to Element (Find (Container, Key)).
70/2
function Contains (Container : Map;
                   Key       : Key_Type) return Boolean;
71/2
{AI95-00302-03} Equivalent to Find (Container, Key) /= No_Element.
Paragraphs 72 and 73 were moved above. 
74/2
procedure Iterate
  (Container : in Map;
   Process   : not null access procedure (Position : in Cursor));
75/3
{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.
75.a/2
Implementation Note: The “tamper with cursors” check takes place when the operations that insert or delete elements, and so on, are called.
75.b/2
See Iterate for vectors (A.18.2) for a suggested implementation of the check. 

Bounded (Run-Time) Errors

75.1/3
  {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.
75.2/3
  {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

76/2
{AI95-00302-03} A Cursor value is invalid if any of the following have occurred since it was created:
77/2
The map that contains the node it designates has been finalized;
77.1/3
{AI05-0160-1} The map that contains the node it designates has been used as the Target of a call to Assign, or as the target of an assignment_statement;
78/2
The map that contains the node it designates has been used as the Source or Target of a call to Move; or
79/3
{AI05-0160-1} {AI05-0262-1} The node it designates has been removed from the map that previously contained the node. 
79.a/3
Ramification: {AI05-0160-1} This can happen directly via calls to Clear, Exclude, and Delete. 
80/2
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.
80.a/2
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.
80.b/2
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. 
80.1/3
  {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.
80.c/3
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

81/2
{AI95-00302-03} No storage associated with a Map object shall be lost upon assignment or scope exit.
82/3
{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.
82.a/3
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

83/2
{AI95-00302-03} Move should not copy elements, and should minimize copying of internal data structures. 
83.a/2
Implementation Advice: Move for a map should not copy elements, and should minimize copying of internal data structures.
83.b/2
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. 
84/2
{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. 
84.a/2
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.
84.b/2
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

84.c/2
{AI95-00302-03} This description of maps is new; the extensions are documented with the specific packages. 

Extensions to Ada 2005

84.d/3
{AI05-0212-1} Added reference support to make map containers more convenient to use. 

Wording Changes from Ada 2005

84.e/3
{AI05-0001-1} Added procedure Assign; the extension and incompatibility is documented with the specific packages.
84.f/3
{AI05-0001-1} Generalized the definition of Move. Specified which elements are read/written by stream attributes.
84.g/3
{AI05-0022-1} Correction: Added a Bounded (Run-Time) Error to cover tampering by generic actual subprograms.
84.h/3
{AI05-0027-1} Correction: Added a Bounded (Run-Time) Error to cover access to finalized map containers.
84.i/3
{AI05-0160-1} Correction: Revised the definition of invalid cursors to cover missing (and new) cases.
84.j/3
{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.

Wording Changes from Ada 2012

84.k/4
{AI12-0110-1} Corrigendum: Clarified that tampering checks precede all other checks made by a subprogram (but come after those associated with the call). 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe