gcc/ada/libgnat/a-chtgop.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT LIBRARY COMPONENTS                          --
   4 --                                                                          --
   5 --              ADA.CONTAINERS.HASH_TABLES.GENERIC_OPERATIONS               --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --          Copyright (C) 2004-2024, Free Software Foundation, Inc.         --
  10 --                                                                          --
  11 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  12 -- terms of the  GNU General Public License as published  by the Free Soft- --
  13 -- ware  Foundation;  either version 3,  or (at your option) any later ver- --
  14 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  15 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  16 -- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
  17 --                                                                          --
  18 -- As a special exception under Section 7 of GPL version 3, you are granted --
  19 -- additional permissions described in the GCC Runtime Library Exception,   --
  20 -- version 3.1, as published by the Free Software Foundation.               --
  21 --                                                                          --
  22 -- You should have received a copy of the GNU General Public License and    --
  23 -- a copy of the GCC Runtime Library Exception along with this program;     --
  24 -- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
  25 -- <http://www.gnu.org/licenses/>.                                          --
  26 --                                                                          --
  27 -- This unit was originally developed by Matthew J Heaney.                  --
  28 ------------------------------------------------------------------------------
  29
  30 --  Hash_Table_Type is used to implement hashed containers. This package
  31 --  declares hash-table operations that do not depend on keys.
  32
  33 with Ada.Streams;
  34
  35 generic
  36
  37    with package HT_Types is
  38      new Generic_Hash_Table_Types (<>);
  39
  40    use HT_Types, HT_Types.Implementation;
  41
  42    with function Hash_Node (Node : Node_Access) return Hash_Type;
  43
  44    with function Next (Node : Node_Access) return Node_Access;
  45
  46    with procedure Set_Next
  47      (Node : Node_Access;
  48       Next : Node_Access);
  49
  50     with function Copy_Node (Source : Node_Access) return Node_Access;
  51
  52    with procedure Free (X : in out Node_Access);
  53
  54 package Ada.Containers.Hash_Tables.Generic_Operations is
  55    pragma Preelaborate;
  56
  57    procedure Free_Hash_Table (Buckets : in out Buckets_Access);
  58    --  First frees the nodes in all non-null buckets of Buckets, and then frees
  59    --  the Buckets array itself.
  60
  61    function Index
  62      (Buckets : Buckets_Type;
  63       Node    : Node_Access) return Hash_Type;
  64    pragma Inline (Index);
  65    --  Uses the hash value of Node to compute its Buckets array index
  66
  67    function Index
  68      (Hash_Table : Hash_Table_Type;
  69       Node       : Node_Access) return Hash_Type;
  70    pragma Inline (Index);
  71    --  Uses the hash value of Node to compute its Hash_Table buckets array
  72    --  index.
  73
  74    function Checked_Index
  75      (Hash_Table : aliased in out Hash_Table_Type;
  76       Buckets    : Buckets_Type;
  77       Node       : Node_Access) return Hash_Type;
  78    --  Calls Index, but also locks and unlocks the container, per AI05-0022, in
  79    --  order to detect element tampering by the generic actual Hash function.
  80
  81    function Checked_Index
  82      (Hash_Table : aliased in out Hash_Table_Type;
  83       Node       : Node_Access) return Hash_Type;
  84    --  Calls Checked_Index using Hash_Table's buckets array.
  85
  86    procedure Adjust (HT : in out Hash_Table_Type);
  87    --  Used to implement controlled Adjust. It is assumed that HT has the value
  88    --  of the bit-wise copy that immediately follows controlled Finalize.
  89    --  Adjust first allocates a new buckets array for HT (having the same
  90    --  length as the source), and then allocates a copy of each node of source.
  91
  92    procedure Finalize (HT : in out Hash_Table_Type);
  93    --  Used to implement controlled Finalize. It first calls Clear to
  94    --  deallocate any remaining nodes, and then deallocates the buckets array.
  95
  96    generic
  97       with function Find
  98         (HT  : Hash_Table_Type;
  99          Key : Node_Access) return Boolean;
 100    function Generic_Equal
 101      (L, R : Hash_Table_Type) return Boolean;
 102    --  Used to implement hashed container equality. For each node in hash table
 103    --  L, it calls Find to search for an equivalent item in hash table R. If
 104    --  Find returns False for any node then Generic_Equal terminates
 105    --  immediately and returns False. Otherwise if Find returns True for every
 106    --  node then Generic_Equal returns True.
 107
 108    procedure Clear (HT : in out Hash_Table_Type);
 109    --  Deallocates each node in hash table HT. (Note that it only deallocates
 110    --  the nodes, not the buckets array. Also note that for bounded containers,
 111    --  the buckets array is not dynamically allocated). Program_Error is raised
 112    --  if the hash table is busy.
 113
 114    procedure Move (Target, Source : in out Hash_Table_Type);
 115    --  Moves (not copies) the buckets array and nodes from Source to
 116    --  Target. Program_Error is raised if Source is busy. The Target is first
 117    --  cleared to deallocate its nodes (implying that Program_Error is also
 118    --  raised if Target is busy). Source is empty following the move.
 119
 120    function Capacity (HT : Hash_Table_Type) return Count_Type;
 121    --  Returns the length of the buckets array
 122
 123    procedure Reserve_Capacity
 124      (HT : in out Hash_Table_Type;
 125       N  : Count_Type);
 126    --  If N is greater than the current capacity, then it expands the buckets
 127    --  array to at least the value N. If N is less than the current capacity,
 128    --  then it contracts the buckets array. In either case existing nodes are
 129    --  rehashed onto the new buckets array, and the old buckets array is
 130    --  deallocated. Program_Error is raised if the hash table is busy.
 131
 132    procedure Delete_Node_At_Index
 133      (HT   : in out Hash_Table_Type;
 134       Indx : Hash_Type;
 135       X    : in out Node_Access);
 136    --  Delete a node whose bucket position is known. Used to remove a node
 137    --  whose element has been modified through a key_preserving reference.
 138    --  We cannot use the value of the element precisely because the current
 139    --  value does not correspond to the hash code that determines the bucket.
 140
 141    procedure Delete_Node_Sans_Free
 142      (HT : in out Hash_Table_Type;
 143       X  : Node_Access);
 144    --  Removes node X from the hash table without deallocating the node
 145
 146    function First
 147      (HT       : Hash_Table_Type) return Node_Access;
 148    function First
 149      (HT       : Hash_Table_Type;
 150       Position : out Hash_Type) return Node_Access;
 151    --  Returns the head of the list in the first (lowest-index) non-empty
 152    --  bucket. Position will be the index of the bucket of the first node.
 153    --  It is provided so that clients can implement efficient iterators.
 154
 155    function Next
 156      (HT   : aliased in out Hash_Table_Type;
 157       Node : Node_Access) return Node_Access;
 158    function Next
 159      (HT       : aliased in out Hash_Table_Type;
 160       Node     : Node_Access;
 161       Position : in out Hash_Type) return Node_Access;
 162    --  Returns the node that immediately follows Node. This corresponds to
 163    --  either the next node in the same bucket, or (if Node is the last node in
 164    --  its bucket) the head of the list in the first non-empty bucket that
 165    --  follows.
 166    --
 167    --  If Node_Position is supplied, then it will be used as a starting point
 168    --  for iteration (Node_Position must be the index of Node's buckets). If it
 169    --  is not supplied, it will be recomputed. It is provided so that clients
 170    --  can implement efficient iterators.
 171
 172    generic
 173       with procedure Process (Node : Node_Access; Position : Hash_Type);
 174    procedure Generic_Iteration_With_Position (HT : Hash_Table_Type);
 175    --  Calls Process for each node in hash table HT
 176
 177    generic
 178       with procedure Process (Node : Node_Access);
 179    procedure Generic_Iteration (HT : Hash_Table_Type);
 180    --  Calls Process for each node in hash table HT
 181
 182    generic
 183       use Ada.Streams;
 184       with procedure Write
 185         (Stream : not null access Root_Stream_Type'Class;
 186          Node   : Node_Access);
 187    procedure Generic_Write
 188      (Stream : not null access Root_Stream_Type'Class;
 189       HT     : Hash_Table_Type);
 190    --  Used to implement the streaming attribute for hashed containers. It
 191    --  calls Write for each node to write its value into Stream.
 192
 193    generic
 194       use Ada.Streams;
 195       with function New_Node
 196              (Stream : not null access Root_Stream_Type'Class)
 197               return Node_Access;
 198    procedure Generic_Read
 199      (Stream : not null access Root_Stream_Type'Class;
 200       HT     : out Hash_Table_Type);
 201    --  Used to implement the streaming attribute for hashed containers. It
 202    --  first clears hash table HT, then populates the hash table by calling
 203    --  New_Node for each item in Stream.
 204
 205    function New_Buckets (Length : Hash_Type) return Buckets_Access;
 206    pragma Inline (New_Buckets);
 207    --  Allocate a new Buckets_Type array with bounds 0 .. Length - 1
 208
 209    procedure Free_Buckets (Buckets : in out Buckets_Access);
 210    pragma Inline (Free_Buckets);
 211    --  Unchecked_Deallocate Buckets
 212
 213    --  Note: New_Buckets and Free_Buckets are needed because Buckets_Access has
 214    --  an empty pool.
 215
 216 end Ada.Containers.Hash_Tables.Generic_Operations;