A.18.5 The Generic Package Containers.Hashed_Maps
Static Semantics
{
AI95-00302-03}
The generic library package Containers.Hashed_Maps has the following
declaration:
{
AI05-0084-1}
{
AI05-0212-1}
{
AI12-0112-1}
with Ada.Iterator_Interfaces;
generic
type Key_Type
is private;
type Element_Type
is private;
with function Hash (Key : Key_Type)
return Hash_Type;
with function Equivalent_Keys (Left, Right : Key_Type)
return Boolean;
with function "=" (Left, Right : Element_Type)
return Boolean
is <>;
package Ada.Containers.Hashed_Maps
with Preelaborate, Remote_Types,
Nonblocking, Global =>
in out synchronized isDiscussion: {
AI12-0112-1}
For discussion on the reasons and meaning of the specifications of the
Global and Nonblocking aspects in this generic package, see the notes
on the equivalent operations in the specification of the Containers.Vectors
package (see
A.18.2).
{
AI05-0212-1}
{
AI12-0111-1}
{
AI12-0112-1}
{
AI12-0212-1}
{
AI12-0339-1}
{
AI12-0339-1}
type Map
is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Iterator_View => Stable.Map,
Aggregate => (Empty => Empty,
Add_Named => Insert),
Stable_Properties => (Length,
Tampering_With_Cursors_Prohibited,
Tampering_With_Elements_Prohibited),
Default_Initial_Condition =>
Length (Map) = 0
and then
(
not Tampering_With_Cursors_Prohibited (Map))
and then
(
not Tampering_With_Elements_Prohibited (Map)),
Preelaborable_Initialization;
Discussion: {
AI12-0112-1}
Unlike a Vector, the Stable_Properties of a Hashed_Map do not include
the Capacity. If we had included it, some of the otherwise shared definitions
would need different postconditions for Hashed_Maps and Ordered_Maps.
If we were starting these containers from scratch, we probably would
have approached the sharing of definitions differently so that we could
avoid issues like this, but a major reorganization of this existing material
would be too much change.
{
AI12-0399-1}
type Cursor
is private
with Preelaborable_Initialization;
Empty_Map :
constant Map;
No_Element :
constant Cursor;
{
AI05-0212-1}
{
AI12-0112-1}
function Has_Element (Position : Cursor)
return Boolean
with Nonblocking, Global =>
in all, Use_Formal =>
null;
{
AI12-0112-1}
function Has_Element (Container : Map; Position : Cursor)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI05-0212-1}
package Map_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
function "=" (Left, Right : Map) return Boolean;
{
AI12-0112-1}
function Tampering_With_Cursors_Prohibited
(Container : Map)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
function Tampering_With_Elements_Prohibited
(Container : Map)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0339-1}
function Empty (Capacity : Count_Type :=
implementation-defined)
return Map
with Post =>
Capacity (Empty'Result) >= Capacity
and then
not Tampering_With_Elements_Prohibited (Empty'Result)
and then
not Tampering_With_Cursors_Prohibited (Empty'Result)
and then
Length (Empty'Result) = 0;
{
AI12-0112-1}
function Capacity (Container : Map)
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
procedure Reserve_Capacity (Container :
in out Map;
Capacity :
in Count_Type)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Container.Capacity >= Capacity;
{
AI12-0112-1}
function Length (Container : Map)
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
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 => Capacity (Container) = Capacity (Container)'Old
and then
Length (Container) = 0;
{
AI12-0112-1}
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;
{
AI12-0112-1}
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}
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;
{
AI12-0112-1}
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}
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);
{
AI12-0112-1}
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;
{
AI12-0112-1}
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}
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);
{
AI05-0212-1}
{
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);
{
AI05-0212-1}
{
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}
{
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}
{
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}
{
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}
{
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-0001-1}
{
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)
and then
Capacity (Target) >= Length (Source);
{
AI05-0001-1}
{
AI12-0112-1}
function Copy (Source : Map; Capacity : Count_Type := 0)
return Map
with Pre => Capacity = 0
or else Capacity >= Length (Source)
or else raise Capacity_Error,
Post =>
Length (Copy'Result) = Length (Source)
and then
not Tampering_With_Elements_Prohibited (Copy'Result)
and then
not Tampering_With_Cursors_Prohibited (Copy'Result)
and then
Copy'Result.Capacity = (
if Capacity = 0
then
Length (Source)
else Capacity);
{
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);
{
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))
and then
Capacity (Container) >= Length (Container);
{
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))
and then
Capacity (Container) >= Length (Container);
{
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
and then
Capacity (Container) >= Length (Container);
{
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)
and then
Capacity (Container) >= Length (Container);
{
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;
{
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);
{
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;
{
AI12-0112-1}
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;
{
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);
{
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);
{
AI12-0112-1}
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}
procedure Next (Position :
in out Cursor)
with Nonblocking, Global =>
in all, Use_Formal =>
null;
{
AI12-0112-1}
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}
function Find (Container : Map;
Key : Key_Type)
return Cursor
with Post => (
if Find'Result /= No_Element
then Has_Element (Container, Find'Result));
function Element (Container : Map;
Key : Key_Type)
return Element_Type;
function Contains (Container : Map;
Key : Key_Type)
return Boolean;
{
AI12-0112-1}
function Equivalent_Keys (Left, Right : Cursor)
return Boolean
with Pre => (Left /= No_Element
and then Right /= No_Element)
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function Equivalent_Keys (Left : Cursor;
Right : Key_Type)
return Boolean
with Pre => Left /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function Equivalent_Keys (Left : Key_Type;
Right : Cursor)
return Boolean
with Pre => Right /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
procedure Iterate
(Container :
in Map;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
AI05-0212-1}
{
AI12-0112-1}
{
AI12-0266-1}
function Iterate (Container :
in Map)
return Map_Iterator_Interfaces.Parallel_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
{
AI12-0111-1}
{
AI12-0339-1}
{
AI12-0399-1}
{
AI12-0407-1}
type Map (Base :
not null access Hashed_Maps.Map)
is
tagged limited private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Length),
Global =>
null,
Default_Initial_Condition => Length (Map) = 0,
Preelaborable_Initialization;
{
AI12-0111-1}
function Has_Element (Position : Cursor)
return Boolean
with Nonblocking, Global =>
in all, Use_Formal =>
null;
{
AI12-0111-1}
package Map_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
{
AI12-0111-1}
procedure Assign (Target :
in out Hashed_Maps.Map;
Source :
in Map)
with Post => Length (Source) = Length (Target);
{
AI12-0111-1}
function Copy (Source : Hashed_Maps.Map)
return Map
with Post => Length (Copy'Result) = Length (Source);
{
AI12-0111-1}
type Constant_Reference_Type
(Element :
not null access constant Element_Type)
is private
with Implicit_Dereference => Element,
Nonblocking, Global =>
null, Use_Formal =>
null,
Default_Initial_Condition => (
raise Program_Error);
{
AI12-0111-1}
type Reference_Type
(Element :
not null access Element_Type)
is private
with Implicit_Dereference => Element,
Nonblocking, Global =>
null, Use_Formal =>
null,
Default_Initial_Condition => (
raise Program_Error);
{
AI12-0111-1}
--
Additional subprograms as described in the text
--
are declared here.private
... -- not specified by the language
end Ada.Containers.Hashed_Maps;
{
AI95-00302-03}
An object of type Map contains an expandable hash table, which is used
to provide direct access to nodes. The
capacity of an object of
type Map is the maximum number of nodes that can be inserted into the
hash table prior to it being automatically expanded.
Implementation Note: The expected implementation
for a Map uses a hash table which is grown when it is too small, with
linked lists hanging off of each bucket. Note that in that implementation
a cursor needs a back pointer to the Map object to implement iteration;
that could either be in the nodes, or in the cursor object. To provide
an average O(1) access time, capacity would typically equal the
number of buckets in such an implementation, so that the average bucket
linked list length would be no more than 1.0.
There is no defined relationship between elements
in a hashed map. Typically, iteration will return elements in the order
that they are hashed in.
{
AI95-00302-03}
Two keys
K1 and
K2 are defined to be
equivalent if Equivalent_Keys (
K1,
K2) returns True.
{
AI95-00302-03}
The actual function for the generic formal function Hash is expected
to return the same value each time it is called with a particular key
value. For any two equivalent key values, the actual for Hash is expected
to return the same value. If the actual for Hash behaves in some other
manner, the behavior of this package is unspecified. Which subprograms
of this package call Hash, and how many times they call it, is unspecified.
Implementation Note: The implementation
is not required to protect against Hash raising an exception, or returning
random numbers, or any other “bad” behavior. It's not practical
to do so, and a broken Hash function makes the container unusable.
The implementation can call Hash whenever it
is needed; we don't want to specify how often that happens. The result
must remain the same (this is logically a pure function), or the behavior
is unspecified.
{
AI95-00302-03}
The actual function for the generic formal function Equivalent_Keys on
Key_Type values is expected to return the same value each time it is
called with a particular pair of key values. It should define an equivalence
relationship, that is, be reflexive, symmetric, and transitive. If the
actual for Equivalent_Keys behaves in some other manner, the behavior
of this package is unspecified. Which subprograms of this package call
Equivalent_Keys, and how many times they call it, is unspecified.
Implementation Note: As with Hash, the
implementation is not required to protect against Equivalent_Keys raising
an exception or returning random results. Similarly, the implementation
can call this operation whenever it is needed. The result must remain
the same (this is a logically pure function), or the behavior is unspecified.
{
AI95-00302-03}
If the value of a key stored in a node of a map is changed other than
by an operation in this package such that at least one of Hash or Equivalent_Keys
give different results, the behavior of this package is unspecified.
Implementation Note: The implementation
is not required to protect against changes to key values other than via
the operations declared in the Hashed_Maps package.
To see how this
could happen, imagine an instance of Hashed_Maps where the key type is
an access-to-variable type and Hash returns a value derived from the
components of the designated object. Then, any operation that has a key
value could modify those components and change the hash value:
Key (Map).Some_Component := New_Value;
This is really a design error on the part of
the user of the map; it shouldn't be possible to modify keys stored in
a map. But we can't prevent this error anymore than we can prevent someone
passing as Hash a random number generator.
{
AI95-00302-03}
Which nodes
are the first node and the last node of a map, and which node is the
successor of a given node, are unspecified, other than the general semantics
described in
A.18.4.
Implementation Note: Typically the first
node will be the first node in the first bucket, the last node will be
the last node in the last bucket, and the successor will be obtained
by following the collision list, and going to the next bucket at the
end of each bucket.
function Empty (Capacity : Count_Type := implementation-defined)
return Map
with Post =>
Capacity (Empty'Result) >= Capacity and then
not Tampering_With_Elements_Prohibited (Empty'Result) and then
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Length (Empty'Result) = 0;
{
AI12-0112-1}
function Capacity (Container : Map)
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
procedure Reserve_Capacity (Container :
in out Map;
Capacity :
in Count_Type)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Container.Capacity >= Capacity;
{
AI95-00302-03}
Reserve_Capacity allocates a new hash table such that the length of the
resulting map can become at least the value Capacity without requiring
an additional call to Reserve_Capacity, and is large enough to hold the
current length of Container. Reserve_Capacity then rehashes the nodes
in Container onto the new hash table. It replaces the old hash table
with the new hash table, and then deallocates the old hash table. Any
exception raised during allocation is propagated and Container is not
modified.
Implementation Note: This routine is
used to preallocate the internal hash table to the specified capacity
such that future Inserts do not require expansion of the hash table.
Therefore, the implementation should allocate the needed memory to make
that true at this point, even though the visible semantics could be preserved
by waiting until enough elements are inserted.
{
AI05-0005-1}
While Reserve_Capacity can be used to reduce the capacity of a map, we
do not specify whether an implementation actually supports reduction
of the capacity. Since the actual capacity can be anything greater than
or equal to Capacity, an implementation never has to reduce the capacity.
Reserve_Capacity tampers with the cursors, as
rehashing probably will change the order that elements are stored in
the map.
{
AI12-0112-1}
procedure Clear (Container :
in out Map)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Capacity (Container) = Capacity (Container)'Old
and then
Length (Container) = 0;
{
AI95-00302-03}
In addition to the semantics described in
A.18.4,
Clear does not affect the capacity of Container.
{
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)
and then
Capacity (Target) >= Length (Source);
{
AI05-0001-1}
{
AI05-0248-1}
In addition to the semantics described in
A.18.4,
if the length of Source is greater than the capacity of Target, Reserve_Capacity
(Target, Length (Source)) is called before assigning any elements.
function Copy (Source : Map; Capacity : Count_Type := 0)
return Map
with Pre => Capacity = 0 or else Capacity >= Length (Source)
or else raise Capacity_Error,
Post =>
Length (Copy'Result) = Length (Source) and then
not Tampering_With_Elements_Prohibited (Copy'Result) and then
not Tampering_With_Cursors_Prohibited (Copy'Result) and then
Copy'Result.Capacity = (if Capacity = 0 then
Length (Source) else Capacity);
{
AI05-0001-1}
{
AI12-0112-1}
Returns a map whose keys and elements are initialized from the keys and
elements of Source.
Implementation
Note: In:
procedure Move (Target : in out Map;
Source : in out Map);
The intended implementation is that the internal
hash table of Target is first deallocated; then the internal hash table
is removed from Source and moved to Target.
{
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))
and then
Capacity (Container) >= Length (Container);
{
AI95-00302-03}
In addition to the semantics described in
A.18.4,
if Length (Container) equals Capacity (Container), then Insert first
calls Reserve_Capacity to increase the capacity of Container to some
larger value.
Implementation Note: Insert should only
compare keys that hash to the same bucket in the hash table.
We specify when Reserve_Capacity is called to
bound the overhead of capacity expansion operations (which are potentially
expensive). Moreover, expansion can be predicted by comparing Capacity(Map)
to Length(Map). Since we don't specify by how much the hash table is
expanded, this only can be used to predict the next expansion, not later
ones.
Implementation
Note: In:
procedure Exclude (Container : in out Map;
Key : in Key_Type);
Exclude should only compare keys that hash to
the same bucket in the hash table.
Implementation
Note: In:
procedure Delete (Container : in out Map;
Key : in Key_Type);
Delete should only compare keys that hash to
the same bucket in the hash table. The node containing the element may
be deallocated now, or it may be saved and reused later.
Implementation
Note: In:
function First (Container : Map) return Cursor;
In a typical implementation, this will be the
first node in the lowest numbered hash bucket that contains a node.
Implementation
Note: In:
function Next (Position : Cursor) return Cursor;
In a typical implementation, this will return
the next node in a bucket; if Position is the last node in a bucket,
this will return the first node in the next nonempty bucket.
A typical implementation will need to a keep
a pointer at the map container in the cursor in order to implement this
function.
Implementation
Note: In:
function Find (Container : Map;
Key : Key_Type) return Cursor;
Find should only compare keys that hash to the
same bucket in the hash table.
{
AI12-0112-1}
function Equivalent_Keys (Left, Right : Cursor)
return Boolean
with Pre => (Left /= No_Element
and then Right /= No_Element)
or else raise Constraint_Error,
Global =>
in all;
{
AI95-00302-03}
Equivalent to Equivalent_Keys (Key (Left), Key (Right)).
{
AI12-0112-1}
function Equivalent_Keys (Left : Cursor;
Right : Key_Type)
return Boolean
with Pre => Left /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI95-00302-03}
Equivalent to Equivalent_Keys (Key (Left), Right).
{
AI12-0112-1}
function Equivalent_Keys (Left : Key_Type;
Right : Cursor)
return Boolean
with Pre => Right /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI95-00302-03}
Equivalent to Equivalent_Keys (Left, Key (Right)).
{
AI12-0112-1}
{
AI12-0266-1}
function Iterate (Container :
in Map)
return Map_Iterator_Interfaces.Parallel_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
{
AI05-0212-1}
{
AI05-0265-1}
{
AI05-0269-1}
{
AI12-0266-1}
Iterate returns an iterator object (see
5.5.1)
that will generate a value for a loop parameter (see
5.5.2)
designating each node in Container, starting with the first node and
moving the cursor according to the successor relation when used as a
forward iterator, and processing all nodes concurrently when used as
a parallel iterator. Tampering with the cursors of Container is prohibited
while the iterator object exists (in particular, in the
sequence_of_statements
of the
loop_statement
whose
iterator_specification
denotes this object). The iterator object needs finalization.
Implementation Advice
{
AI95-00302-03}
If
N is the length of a map, the average time complexity of the
subprograms Element, Insert, Include, Replace, Delete, Exclude, and Find
that take a key parameter should be
O(log
N). The average
time complexity of the subprograms that take a cursor parameter should
be
O(1). The average time complexity of Reserve_Capacity should
be
O(
N).
Implementation Advice: The average time
complexity of Element, Insert, Include, Replace, Delete, Exclude, and
Find operations that take a key parameter for Containers.Hashed_Maps
should be O(log N). The average time complexity of the
subprograms of Containers.Hashed_Maps that take a cursor parameter should
be O(1). The average time complexity of Containers.Hashed_Maps.Reserve_Capacity
should be O(N).
Reason: We do not mean to overly constrain
implementation strategies here. However, it is important for portability
that the performance of large containers has roughly the same factors
on different implementations. If a program is moved to an implementation
for which Find is O(N), that program could be unusable
when the maps are large. We allow O(log N) access because
the proportionality constant and caching effects are likely to be larger
than the log factor, and we don't want to discourage innovative implementations.
Extensions to Ada 95
{
AI95-00302-03}
The generic package Containers.Hashed_Maps is new.
Incompatibilities With Ada 2005
{
AI05-0001-1}
Subprograms Assign and Copy are added to Containers.Hashed_Maps.
If an instance of Containers.Hashed_Maps is referenced in a
use_clause,
and an entity
E with the same
defining_identifier
as a new entity in Containers.Hashed_Maps is defined in a package that
is also referenced in a
use_clause,
the entity
E may no longer be use-visible, resulting in errors.
This should be rare and is easily fixed if it does occur.
Extensions to Ada 2005
{
AI05-0212-1}
Added iterator and indexing support to make hashed
map containers more convenient to use.
Wording Changes from Ada 2005
{
AI05-0084-1}
Correction: Added a pragma Remote_Types so that containers can
be used in distributed programs.
Incompatibilities With Ada 2012
{
AI12-0111-1}
{
AI12-0112-1}
{
AI12-0339-1}
A number of new subprograms, types, and even a nested
package were added to Containers.Hashed_Maps to better support contracts
and stable views. Therefore, a use clause conflict is possible; see the
introduction of
Annex A for more on this topic.
Extensions to Ada 2012
{
AI12-0212-1}
Maps now support named container aggregates, so
aggregate
syntax can be used to create Maps.
{
AI12-0266-1}
The iterator for the container now can return a parallel iterator which
can be used to process the container in parallel.
Wording Changes from Ada 2012
{
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
