blob: 96ac16414701a82ae8f002f00a483e720b32b432 [file] [log] [blame]
------------------------------------------------------------------------------
-- --
-- GNAT LIBRARY COMPONENTS --
-- --
-- A D A . C O N T A I N E R S . H A S H E D _ M A P S --
-- --
-- S p e c --
-- --
-- Copyright (C) 2004-2022, Free Software Foundation, Inc. --
-- --
-- This specification is derived from the Ada Reference Manual for use with --
-- GNAT. The copyright notice above, and the license provisions that follow --
-- apply solely to the contents of the part following the private keyword. --
-- --
-- GNAT is free software; you can redistribute it and/or modify it under --
-- terms of the GNU General Public License as published by the Free Soft- --
-- ware Foundation; either version 3, or (at your option) any later ver- --
-- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. --
-- --
-- As a special exception under Section 7 of GPL version 3, you are granted --
-- additional permissions described in the GCC Runtime Library Exception, --
-- version 3.1, as published by the Free Software Foundation. --
-- --
-- You should have received a copy of the GNU General Public License and --
-- a copy of the GCC Runtime Library Exception along with this program; --
-- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
-- <http://www.gnu.org/licenses/>. --
-- --
-- This unit was originally developed by Matthew J Heaney. --
------------------------------------------------------------------------------
with Ada.Iterator_Interfaces;
private with Ada.Containers.Hash_Tables;
private with Ada.Finalization;
private with Ada.Streams;
private with Ada.Strings.Text_Buffers;
-- The language-defined generic package Containers.Hashed_Maps provides
-- 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.
--
-- 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.
--
-- 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.
generic
type Key_Type is private;
type Element_Type is private;
with function Hash (Key : Key_Type) return Hash_Type;
-- 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.
with function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
-- 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.
with function "=" (Left, Right : Element_Type) return Boolean is <>;
-- 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.
package Ada.Containers.Hashed_Maps with
SPARK_Mode => Off
is
pragma Annotate (CodePeer, Skip_Analysis);
pragma Preelaborate;
pragma Remote_Types;
type Map is tagged private
with
Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Aggregate => (Empty => Empty,
Add_Named => Insert);
pragma Preelaborable_Initialization (Map);
type Cursor is private;
pragma Preelaborable_Initialization (Cursor);
function "=" (Left, Right : Cursor) return Boolean;
-- The representation of cursors includes a component used to optimize
-- iteration over maps. This component may become unreliable after
-- multiple map insertions, and must be excluded from cursor equality,
-- so we need to provide an explicit definition for it, instead of
-- using predefined equality (as implied by a questionable comment
-- in the RM).
Empty_Map : constant Map;
-- Map objects declared without an initialization expression are
-- initialized to the value Empty_Map.
No_Element : constant Cursor;
-- Cursor objects declared without an initialization expression are
-- initialized to the value No_Element.
function Empty (Capacity : Count_Type := 1000) return Map;
function Has_Element (Position : Cursor) return Boolean;
-- Returns True if Position designates an element, and returns False
-- otherwise.
package Map_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
function "=" (Left, Right : Map) return Boolean;
-- 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.
function Capacity (Container : Map) return Count_Type;
-- Returns the current capacity of the map. Capacity is the maximum length
-- before which rehashing in guaranteed not to occur.
procedure Reserve_Capacity (Container : in out Map; Capacity : Count_Type);
-- Adjusts the current capacity, by allocating a new buckets array. If the
-- requested capacity is less than the current capacity, then the capacity
-- is contracted (to a value not less than the current length). If the
-- requested capacity is greater than the current capacity, then the
-- capacity is expanded (to a value not less than what is requested). In
-- either case, the nodes are rehashed from the old buckets array onto the
-- new buckets array (Hash is called once for each existing key in order to
-- compute the new index), and then the old buckets array is deallocated.
function Length (Container : Map) return Count_Type;
-- Returns the number of items in the map
function Is_Empty (Container : Map) return Boolean;
-- Equivalent to Length (Container) = 0
procedure Clear (Container : in out Map);
-- Removes all of the items from the map
function Key (Position : Cursor) return Key_Type;
-- Key returns the key component of the node designated by Position.
--
-- If Position equals No_Element, then Constraint_Error is propagated.
function Element (Position : Cursor) return Element_Type;
-- Element returns the element component of the node designated
-- by Position.
--
-- If Position equals No_Element, then Constraint_Error is propagated.
procedure Replace_Element
(Container : in out Map;
Position : Cursor;
New_Item : Element_Type);
-- Replace_Element assigns New_Item to the element of the node designated
-- by Position.
--
-- If Position equals No_Element, then Constraint_Error is propagated; if
-- Position does not designate an element in Container, then Program_Error
-- is propagated.
procedure Query_Element
(Position : Cursor;
Process : not null access
procedure (Key : Key_Type; Element : Element_Type));
-- Query_Element calls Process.all with the key and element from the node
-- designated by Position as the arguments.
--
-- If Position equals No_Element, then Constraint_Error is propagated.
--
-- 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 Update_Element
(Container : in out Map;
Position : Cursor;
Process : not null access
procedure (Key : Key_Type; Element : in out Element_Type));
-- Update_Element calls Process.all with the key and element from the node
-- designated by Position as the arguments.
--
-- If Position equals No_Element, then Constraint_Error is propagated; if
-- Position does not designate an element in Container, then Program_Error
-- is propagated.
--
-- 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.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with
Implicit_Dereference => Element;
type Reference_Type (Element : not null access Element_Type) is private
with
Implicit_Dereference => Element;
function Constant_Reference
(Container : aliased Map;
Position : Cursor) return Constant_Reference_Type;
pragma Inline (Constant_Reference);
-- 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.
-- Constant_Reference returns an object whose discriminant is an access
-- value that designates the element designated by Position.
--
-- If Position equals No_Element, then Constraint_Error is propagated; if
-- Position does not designate an element in Container, then Program_Error
-- is propagated.
--
-- Tampering with the elements of Container is prohibited
-- while the object returned by Constant_Reference exists and has not been
-- finalized.
function Reference
(Container : aliased in out Map;
Position : Cursor) return Reference_Type;
pragma Inline (Reference);
-- 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.
-- Reference returns an object whose discriminant is an access value that
-- designates the element designated by Position.
--
-- If Position equals No_Element, then Constraint_Error is propagated; if
-- Position does not designate an element in Container, then Program_Error
-- is propagated.
--
-- Tampering with the elements of Container is prohibited while the object
-- returned by Reference exists and has not been finalized.
function Constant_Reference
(Container : aliased Map;
Key : Key_Type) return Constant_Reference_Type;
pragma Inline (Constant_Reference);
-- Equivalent to Constant_Reference (Container, Find (Container, Key)).
function Reference
(Container : aliased in out Map;
Key : Key_Type) return Reference_Type;
pragma Inline (Reference);
-- Equivalent to Reference (Container, Find (Container, Key)).
procedure Assign (Target : in out Map; Source : Map);
-- 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.
function Copy (Source : Map; Capacity : Count_Type := 0) return Map;
procedure Move (Target : in out Map; Source : in out Map);
-- 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).
procedure Insert
(Container : in out Map;
Key : Key_Type;
New_Item : Element_Type;
Position : out Cursor;
Inserted : out Boolean);
-- 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.
procedure Insert
(Container : in out Map;
Key : Key_Type;
Position : out Cursor;
Inserted : out Boolean);
-- 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.
procedure Insert
(Container : in out Map;
Key : Key_Type;
New_Item : Element_Type);
-- 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.
procedure Include
(Container : in out Map;
Key : Key_Type;
New_Item : Element_Type);
-- 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.
procedure Replace
(Container : in out Map;
Key : Key_Type;
New_Item : Element_Type);
-- 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.
procedure Exclude (Container : in out Map; Key : Key_Type);
-- 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.
procedure Delete (Container : in out Map; Key : Key_Type);
-- 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);
-- Delete removes the node designated by Position from the map. Position is
-- set to No_Element on return.
--
-- If Position equals No_Element, then Constraint_Error is propagated. If
-- Position does not designate an element in Container, then Program_Error
-- is propagated.
function First (Container : Map) return Cursor;
-- If Length (Container) = 0, then First returns No_Element. Otherwise,
-- First returns a cursor that designates the first node in Container.
function Next (Position : Cursor) return Cursor;
-- 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.
procedure Next (Position : in out Cursor);
-- Equivalent to Position := Next (Position)
function Find (Container : Map; Key : Key_Type) return Cursor;
-- 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 Contains (Container : Map; Key : Key_Type) return Boolean;
-- Equivalent to Find (Container, Key) /= No_Element.
function Element (Container : Map; Key : Key_Type) return Element_Type;
-- Equivalent to Element (Find (Container, Key))
function Equivalent_Keys (Left, Right : Cursor) return Boolean;
-- Returns the result of calling Equivalent_Keys with the keys of the nodes
-- designated by cursors Left and Right.
function Equivalent_Keys (Left : Cursor; Right : Key_Type) return Boolean;
-- Returns the result of calling Equivalent_Keys with key of the node
-- designated by Left and key Right.
function Equivalent_Keys (Left : Key_Type; Right : Cursor) return Boolean;
-- Returns the result of calling Equivalent_Keys with key Left and the node
-- designated by Right.
procedure Iterate
(Container : Map;
Process : not null access procedure (Position : Cursor));
-- 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.
function Iterate
(Container : Map) return Map_Iterator_Interfaces.Forward_Iterator'Class;
private
pragma Inline ("=");
pragma Inline (Length);
pragma Inline (Is_Empty);
pragma Inline (Clear);
pragma Inline (Key);
pragma Inline (Element);
pragma Inline (Move);
pragma Inline (Contains);
pragma Inline (Capacity);
pragma Inline (Reserve_Capacity);
pragma Inline (Has_Element);
pragma Inline (Equivalent_Keys);
pragma Inline (Next);
type Node_Type;
type Node_Access is access Node_Type;
type Node_Type is limited record
Key : Key_Type;
Element : aliased Element_Type;
Next : Node_Access;
end record;
package HT_Types is
new Hash_Tables.Generic_Hash_Table_Types (Node_Type, Node_Access);
type Map is new Ada.Finalization.Controlled with record
HT : HT_Types.Hash_Table_Type;
end record with Put_Image => Put_Image;
procedure Put_Image
(S : in out Ada.Strings.Text_Buffers.Root_Buffer_Type'Class; V : Map);
overriding procedure Adjust (Container : in out Map);
overriding procedure Finalize (Container : in out Map);
use HT_Types, HT_Types.Implementation;
use Ada.Finalization;
use Ada.Streams;
procedure Write
(Stream : not null access Root_Stream_Type'Class;
Container : Map);
for Map'Write use Write;
procedure Read
(Stream : not null access Root_Stream_Type'Class;
Container : out Map);
for Map'Read use Read;
type Map_Access is access all Map;
for Map_Access'Storage_Size use 0;
type Cursor is record
Container : Map_Access;
-- Access to this cursor's container
Node : Node_Access;
-- Access to the node pointed to by this cursor
Position : Hash_Type := Hash_Type'Last;
-- Position of the node in the buckets of the container. If this is
-- equal to Hash_Type'Last, then it will not be used. Position is
-- not requried by the implementation, but improves the efficiency
-- of various operations.
--
-- However, this value must be maintained so that the predefined
-- equality operation acts as required by RM A.18.4-18/2, which
-- states: "The predefined "=" operator for type Cursor returns True
-- if both cursors are No_Element, or designate the same element
-- in the same container."
end record;
procedure Read
(Stream : not null access Root_Stream_Type'Class;
Item : out Cursor);
for Cursor'Read use Read;
procedure Write
(Stream : not null access Root_Stream_Type'Class;
Item : Cursor);
for Cursor'Write use Write;
subtype Reference_Control_Type is Implementation.Reference_Control_Type;
-- It is necessary to rename this here, so that the compiler can find it
type Constant_Reference_Type
(Element : not null access constant Element_Type) is
record
Control : Reference_Control_Type :=
raise Program_Error with "uninitialized reference";
-- The RM says, "The default initialization of an object of
-- type Constant_Reference_Type or Reference_Type propagates
-- Program_Error."
end record;
procedure Write
(Stream : not null access Root_Stream_Type'Class;
Item : Constant_Reference_Type);
for Constant_Reference_Type'Write use Write;
procedure Read
(Stream : not null access Root_Stream_Type'Class;
Item : out Constant_Reference_Type);
for Constant_Reference_Type'Read use Read;
type Reference_Type
(Element : not null access Element_Type) is
record
Control : Reference_Control_Type :=
raise Program_Error with "uninitialized reference";
-- The RM says, "The default initialization of an object of
-- type Constant_Reference_Type or Reference_Type propagates
-- Program_Error."
end record;
procedure Write
(Stream : not null access Root_Stream_Type'Class;
Item : Reference_Type);
for Reference_Type'Write use Write;
procedure Read
(Stream : not null access Root_Stream_Type'Class;
Item : out Reference_Type);
for Reference_Type'Read use Read;
-- Three operations are used to optimize in the expansion of "for ... of"
-- loops: the Next(Cursor) procedure in the visible part, and the following
-- Pseudo_Reference and Get_Element_Access functions. See Sem_Ch5 for
-- details.
function Pseudo_Reference
(Container : aliased Map'Class) return Reference_Control_Type;
pragma Inline (Pseudo_Reference);
-- Creates an object of type Reference_Control_Type pointing to the
-- container, and increments the Lock. Finalization of this object will
-- decrement the Lock.
type Element_Access is access all Element_Type with
Storage_Size => 0;
function Get_Element_Access
(Position : Cursor) return not null Element_Access;
-- Returns a pointer to the element designated by Position.
Empty_Map : constant Map := (Controlled with others => <>);
No_Element : constant Cursor := (Container => null, Node => null,
Position => Hash_Type'Last);
type Iterator is new Limited_Controlled and
Map_Iterator_Interfaces.Forward_Iterator with
record
Container : Map_Access;
end record
with Disable_Controlled => not T_Check;
overriding procedure Finalize (Object : in out Iterator);
overriding function First (Object : Iterator) return Cursor;
overriding function Next
(Object : Iterator;
Position : Cursor) return Cursor;
end Ada.Containers.Hashed_Maps;