gcc/ada/a-cbhama.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT LIBRARY COMPONENTS                          --
   4 --                                                                          --
   5 --   A D A . C O N T A I N E R S . B O U N D E D _ H A S H E D _ M A P S    --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --          Copyright (C) 2004-2010, Free Software Foundation, Inc.         --
  10 --                                                                          --
  11 -- This specification is derived from the Ada Reference Manual for use with --
  12 -- GNAT. The copyright notice above, and the license provisions that follow --
  13 -- apply solely to the  contents of the part following the private keyword. --
  14 --                                                                          --
  15 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  16 -- terms of the  GNU General Public License as published  by the Free Soft- --
  17 -- ware  Foundation;  either version 3,  or (at your option) any later ver- --
  18 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  19 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  20 -- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
  21 --                                                                          --
  22 -- As a special exception under Section 7 of GPL version 3, you are granted --
  23 -- additional permissions described in the GCC Runtime Library Exception,   --
  24 -- version 3.1, as published by the Free Software Foundation.               --
  25 --                                                                          --
  26 -- You should have received a copy of the GNU General Public License and    --
  27 -- a copy of the GCC Runtime Library Exception along with this program;     --
  28 -- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
  29 -- <http://www.gnu.org/licenses/>.                                          --
  30 --                                                                          --
  31 -- This unit was originally developed by Matthew J Heaney.                  --
  32 ------------------------------------------------------------------------------
  33
  34 private with Ada.Containers.Hash_Tables;
  35 private with Ada.Streams;
  36
  37 generic
  38    type Key_Type is private;
  39    type Element_Type is private;
  40
  41    with function Hash (Key : Key_Type) return Hash_Type;
  42    with function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
  43    with function "=" (Left, Right : Element_Type) return Boolean is <>;
  44
  45 package Ada.Containers.Bounded_Hashed_Maps is
  46    pragma Pure;
  47    pragma Remote_Types;
  48
  49    type Map (Capacity : Count_Type; Modulus : Hash_Type) is tagged private;
  50    pragma Preelaborable_Initialization (Map);
  51
  52    type Cursor is private;
  53    pragma Preelaborable_Initialization (Cursor);
  54
  55    Empty_Map : constant Map;
  56    --  Map objects declared without an initialization expression are
  57    --  initialized to the value Empty_Map.
  58
  59    No_Element : constant Cursor;
  60    --  Cursor objects declared without an initialization expression are
  61    --  initialized to the value No_Element.
  62
  63    function "=" (Left, Right : Map) return Boolean;
  64    --  For each key/element pair in Left, equality attempts to find the key in
  65    --  Right; if a search fails the equality returns False. The search works by
  66    --  calling Hash to find the bucket in the Right map that corresponds to the
  67    --  Left key. If bucket is non-empty, then equality calls Equivalent_Keys
  68    --  to compare the key (in Left) to the key of each node in the bucket (in
  69    --  Right); if the keys are equivalent, then the equality test for this
  70    --  key/element pair (in Left) completes by calling the element equality
  71    --  operator to compare the element (in Left) to the element of the node
  72    --  (in Right) whose key matched.
  73
  74    function Capacity (Container : Map) return Count_Type;
  75    --  Returns the current capacity of the map. Capacity is the maximum length
  76    --  before which rehashing in guaranteed not to occur.
  77
  78    procedure Reserve_Capacity (Container : in out Map; Capacity : Count_Type);
  79    --  If the value of the Capacity actual parameter is less or equal to
  80    --  Container.Capacity, then the operation has no effect.  Otherwise it
  81    --  raises Capacity_Error (as no expansion of capacity is possible for a
  82    --  bounded form).
  83
  84    function Default_Modulus (Capacity : Count_Type) return Hash_Type;
  85    --  Returns a modulus value (hash table size) which is optimal for the
  86    --  specified capacity (which corresponds to the maximum number of items).
  87
  88    function Length (Container : Map) return Count_Type;
  89    --  Returns the number of items in the map
  90
  91    function Is_Empty (Container : Map) return Boolean;
  92    --  Equivalent to Length (Container) = 0
  93
  94    procedure Clear (Container : in out Map);
  95    --  Removes all of the items from the map
  96
  97    function Key (Position : Cursor) return Key_Type;
  98    --  Returns the key of the node designated by the cursor
  99
 100    function Element (Position : Cursor) return Element_Type;
 101    --  Returns the element of the node designated by the cursor
 102
 103    procedure Replace_Element
 104      (Container : in out Map;
 105       Position  : Cursor;
 106       New_Item  : Element_Type);
 107    --  Assigns the value New_Item to the element designated by the cursor
 108
 109    procedure Query_Element
 110      (Position : Cursor;
 111       Process  : not null access
 112                    procedure (Key : Key_Type; Element : Element_Type));
 113    --  Calls Process with the key and element (both having only a constant
 114    --  view) of the node designed by the cursor.
 115
 116    procedure Update_Element
 117      (Container : in out Map;
 118       Position  : Cursor;
 119       Process   : not null access
 120                     procedure (Key : Key_Type; Element : in out Element_Type));
 121    --  Calls Process with the key (with only a constant view) and element (with
 122    --  a variable view) of the node designed by the cursor.
 123
 124    procedure Assign (Target : in out Map; Source : Map);
 125    --  If Target denotes the same object as Source, then the operation has no
 126    --  effect. If the Target capacity is less then the Source length, then
 127    --  Assign raises Capacity_Error.  Otherwise, Assign clears Target and then
 128    --  copies the (active) elements from Source to Target.
 129
 130    function Copy
 131      (Source   : Map;
 132       Capacity : Count_Type := 0;
 133       Modulus  : Hash_Type := 0) return Map;
 134    --  Constructs a new set object whose elements correspond to Source.  If the
 135    --  Capacity parameter is 0, then the capacity of the result is the same as
 136    --  the length of Source. If the Capacity parameter is equal or greater than
 137    --  the length of Source, then the capacity of the result is the specified
 138    --  value. Otherwise, Copy raises Capacity_Error. If the Modulus parameter
 139    --  is 0, then the modulus of the result is the value returned by a call to
 140    --  Default_Modulus with the capacity parameter determined as above;
 141    --  otherwise the modulus of the result is the specified value.
 142
 143    procedure Move (Target : in out Map; Source : in out Map);
 144    --  Clears Target (if it's not empty), and then moves (not copies) the
 145    --  buckets array and nodes from Source to Target.
 146
 147    procedure Insert
 148      (Container : in out Map;
 149       Key       : Key_Type;
 150       New_Item  : Element_Type;
 151       Position  : out Cursor;
 152       Inserted  : out Boolean);
 153    --  Conditionally inserts New_Item into the map. If Key is already in the
 154    --  map, then Inserted returns False and Position designates the node
 155    --  containing the existing key/element pair (neither of which is modified).
 156    --  If Key is not already in the map, the Inserted returns True and Position
 157    --  designates the newly-inserted node container Key and New_Item. The
 158    --  search for the key works as follows. Hash is called to determine Key's
 159    --  bucket; if the bucket is non-empty, then Equivalent_Keys is called to
 160    --  compare Key to each node in that bucket. If the bucket is empty, or
 161    --  there were no matching keys in the bucket, the search "fails" and the
 162    --  key/item pair is inserted in the map (and Inserted returns True);
 163    --  otherwise, the search "succeeds" (and Inserted returns False).
 164
 165    procedure Insert
 166      (Container : in out Map;
 167       Key       : Key_Type;
 168       Position  : out Cursor;
 169       Inserted  : out Boolean);
 170    --  The same as the (conditional) Insert that accepts an element parameter,
 171    --  with the difference that if Inserted returns True, then the element of
 172    --  the newly-inserted node is initialized to its default value.
 173
 174    procedure Insert
 175      (Container : in out Map;
 176       Key       : Key_Type;
 177       New_Item  : Element_Type);
 178    --  Attempts to insert Key into the map, performing the usual search (which
 179    --  involves calling both Hash and Equivalent_Keys); if the search succeeds
 180    --  (because Key is already in the map), then it raises Constraint_Error.
 181    --  (This version of Insert is similar to Replace, but having the opposite
 182    --  exception behavior. It is intended for use when you want to assert that
 183    --  Key is not already in the map.)
 184
 185    procedure Include
 186      (Container : in out Map;
 187       Key       : Key_Type;
 188       New_Item  : Element_Type);
 189    --  Attempts to insert Key into the map. If Key is already in the map, then
 190    --  both the existing key and element are assigned the values of Key and
 191    --  New_Item, respectively. (This version of Insert only raises an exception
 192    --  if cursor tampering occurs. It is intended for use when you want to
 193    --  insert the key/element pair in the map, and you don't care whether Key
 194    --  is already present.)
 195
 196    procedure Replace
 197      (Container : in out Map;
 198       Key       : Key_Type;
 199       New_Item  : Element_Type);
 200    --  Searches for Key in the map; if the search fails (because Key was not in
 201    --  the map), then it raises Constraint_Error. Otherwise, both the existing
 202    --  key and element are assigned the values of Key and New_Item rsp. (This
 203    --  is similar to Insert, but with the opposite exception behavior. It is to
 204    --  be used when you want to assert that Key is already in the map.)
 205
 206    procedure Exclude (Container : in out Map; Key : Key_Type);
 207    --  Searches for Key in the map, and if found, removes its node from the map
 208    --  and then deallocates it. The search works as follows. The operation
 209    --  calls Hash to determine the key's bucket; if the bucket is not empty, it
 210    --  calls Equivalent_Keys to compare Key to each key in the bucket. (This is
 211    --  the deletion analog of Include. It is intended for use when you want to
 212    --  remove the item from the map, but don't care whether the key is already
 213    --  in the map.)
 214
 215    procedure Delete (Container : in out Map; Key : Key_Type);
 216    --  Searches for Key in the map (which involves calling both Hash and
 217    --  Equivalent_Keys). If the search fails, then the operation raises
 218    --  Constraint_Error. Otherwise it removes the node from the map and then
 219    --  deallocates it. (This is the deletion analog of non-conditional
 220    --  Insert. It is intended for use when you want to assert that the item is
 221    --  already in the map.)
 222
 223    procedure Delete (Container : in out Map; Position : in out Cursor);
 224    --  Removes the node designated by Position from the map, and then
 225    --  deallocates the node. The operation calls Hash to determine the bucket,
 226    --  and then compares Position to each node in the bucket until there's a
 227    --  match (it does not call Equivalent_Keys).
 228
 229    function First (Container : Map) return Cursor;
 230    --  Returns a cursor that designates the first non-empty bucket, by
 231    --  searching from the beginning of the buckets array.
 232
 233    function Next (Position : Cursor) return Cursor;
 234    --  Returns a cursor that designates the node that follows the current one
 235    --  designated by Position. If Position designates the last node in its
 236    --  bucket, the operation calls Hash to compute the index of this bucket,
 237    --  and searches the buckets array for the first non-empty bucket, starting
 238    --  from that index; otherwise, it simply follows the link to the next node
 239    --  in the same bucket.
 240
 241    procedure Next (Position : in out Cursor);
 242    --  Equivalent to Position := Next (Position)
 243
 244    function Find (Container : Map; Key : Key_Type) return Cursor;
 245    --  Searches for Key in the map. Find calls Hash to determine the key's
 246    --  bucket; if the bucket is not empty, it calls Equivalent_Keys to compare
 247    --  Key to each key in the bucket. If the search succeeds, Find returns a
 248    --  cursor designating the matching node; otherwise, it returns No_Element.
 249
 250    function Contains (Container : Map; Key : Key_Type) return Boolean;
 251    --  Equivalent to Find (Container, Key) /= No_Element
 252
 253    function Element (Container : Map; Key : Key_Type) return Element_Type;
 254    --  Equivalent to Element (Find (Container, Key))
 255
 256    function Has_Element (Position : Cursor) return Boolean;
 257    --  Equivalent to Position /= No_Element
 258
 259    function Equivalent_Keys (Left, Right : Cursor) return Boolean;
 260    --  Returns the result of calling Equivalent_Keys with the keys of the nodes
 261    --  designated by cursors Left and Right.
 262
 263    function Equivalent_Keys (Left : Cursor; Right : Key_Type) return Boolean;
 264    --  Returns the result of calling Equivalent_Keys with key of the node
 265    --  designated by Left and key Right.
 266
 267    function Equivalent_Keys (Left : Key_Type; Right : Cursor) return Boolean;
 268    --  Returns the result of calling Equivalent_Keys with key Left and the node
 269    --  designated by Right.
 270
 271    procedure Iterate
 272      (Container : Map;
 273       Process   : not null access procedure (Position : Cursor));
 274    --  Calls Process for each node in the map
 275
 276 private
 277    --  pragma Inline ("=");
 278    pragma Inline (Length);
 279    pragma Inline (Is_Empty);
 280    pragma Inline (Clear);
 281    pragma Inline (Key);
 282    pragma Inline (Element);
 283    pragma Inline (Move);
 284    pragma Inline (Contains);
 285    pragma Inline (Capacity);
 286    pragma Inline (Reserve_Capacity);
 287    pragma Inline (Has_Element);
 288    pragma Inline (Equivalent_Keys);
 289    pragma Inline (Next);
 290
 291    type Node_Type is record
 292       Key     : Key_Type;
 293       Element : Element_Type;
 294       Next    : Count_Type;
 295    end record;
 296
 297    package HT_Types is
 298      new Hash_Tables.Generic_Bounded_Hash_Table_Types (Node_Type);
 299
 300    type Map (Capacity : Count_Type; Modulus : Hash_Type) is
 301       new HT_Types.Hash_Table_Type (Capacity, Modulus) with null record;
 302
 303    use HT_Types;
 304    use Ada.Streams;
 305
 306    procedure Write
 307      (Stream    : not null access Root_Stream_Type'Class;
 308       Container : Map);
 309
 310    for Map'Write use Write;
 311
 312    procedure Read
 313      (Stream    : not null access Root_Stream_Type'Class;
 314       Container : out Map);
 315
 316    for Map'Read use Read;
 317
 318    type Map_Access is access all Map;
 319    for Map_Access'Storage_Size use 0;
 320
 321    type Cursor is record
 322       Container : Map_Access;
 323       Node      : Count_Type;
 324    end record;
 325
 326    procedure Read
 327      (Stream : not null access Root_Stream_Type'Class;
 328       Item   : out Cursor);
 329
 330    for Cursor'Read use Read;
 331
 332    procedure Write
 333      (Stream : not null access Root_Stream_Type'Class;
 334       Item   : Cursor);
 335
 336    for Cursor'Write use Write;
 337
 338    No_Element : constant Cursor := (Container => null, Node => 0);
 339
 340    Empty_Map : constant Map :=
 341      (Hash_Table_Type with Capacity => 0, Modulus => 0);
 342
 343 end Ada.Containers.Bounded_Hashed_Maps;