gcc/ada/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-2015, 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.) Program_Error is raised if the hash
 111    --  table is busy.
 112
 113    procedure Move (Target, Source : in out Hash_Table_Type);
 114    --  Moves (not copies) the buckets array and nodes from Source to
 115    --  Target. Program_Error is raised if Source is busy. The Target is first
 116    --  cleared to deallocate its nodes (implying that Program_Error is also
 117    --  raised if Target is busy). Source is empty following the move.
 118
 119    function Capacity (HT : Hash_Table_Type) return Count_Type;
 120    --  Returns the length of the buckets array
 121
 122    procedure Reserve_Capacity
 123      (HT : in out Hash_Table_Type;
 124       N  : Count_Type);
 125    --  If N is greater than the current capacity, then it expands the buckets
 126    --  array to at least the value N. If N is less than the current capacity,
 127    --  then it contracts the buckets array. In either case existing nodes are
 128    --  rehashed onto the new buckets array, and the old buckets array is
 129    --  deallocated. Program_Error is raised if the hash table is busy.
 130
 131    procedure Delete_Node_At_Index
 132      (HT   : in out Hash_Table_Type;
 133       Indx : Hash_Type;
 134       X    : in out Node_Access);
 135    --  Delete a node whose bucket position is known. Used to remove a node
 136    --  whose element has been modified through a key_preserving reference.
 137    --  We cannot use the value of the element precisely because the current
 138    --  value does not correspond to the hash code that determines the bucket.
 139
 140    procedure Delete_Node_Sans_Free
 141      (HT : in out Hash_Table_Type;
 142       X  : Node_Access);
 143    --  Removes node X from the hash table without deallocating the node
 144
 145    function First (HT : Hash_Table_Type) return Node_Access;
 146    --  Returns the head of the list in the first (lowest-index) non-empty
 147    --  bucket.
 148
 149    function Next
 150      (HT   : aliased in out Hash_Table_Type;
 151       Node : Node_Access) return Node_Access;
 152    --  Returns the node that immediately follows Node. This corresponds to
 153    --  either the next node in the same bucket, or (if Node is the last node in
 154    --  its bucket) the head of the list in the first non-empty bucket that
 155    --  follows.
 156
 157    generic
 158       with procedure Process (Node : Node_Access);
 159    procedure Generic_Iteration (HT : Hash_Table_Type);
 160    --  Calls Process for each node in hash table HT
 161
 162    generic
 163       use Ada.Streams;
 164       with procedure Write
 165         (Stream : not null access Root_Stream_Type'Class;
 166          Node   : Node_Access);
 167    procedure Generic_Write
 168      (Stream : not null access Root_Stream_Type'Class;
 169       HT     : Hash_Table_Type);
 170    --  Used to implement the streaming attribute for hashed containers. It
 171    --  calls Write for each node to write its value into Stream.
 172
 173    generic
 174       use Ada.Streams;
 175       with function New_Node
 176              (Stream : not null access Root_Stream_Type'Class)
 177               return Node_Access;
 178    procedure Generic_Read
 179      (Stream : not null access Root_Stream_Type'Class;
 180       HT     : out Hash_Table_Type);
 181    --  Used to implement the streaming attribute for hashed containers. It
 182    --  first clears hash table HT, then populates the hash table by calling
 183    --  New_Node for each item in Stream.
 184
 185    function New_Buckets (Length : Hash_Type) return Buckets_Access;
 186    pragma Inline (New_Buckets);
 187    --  Allocate a new Buckets_Type array with bounds 0 .. Length - 1
 188
 189    procedure Free_Buckets (Buckets : in out Buckets_Access);
 190    pragma Inline (Free_Buckets);
 191    --  Unchecked_Deallocate Buckets
 192
 193    --  Note: New_Buckets and Free_Buckets are needed because Buckets_Access has
 194    --  an empty pool.
 195
 196 end Ada.Containers.Hash_Tables.Generic_Operations;