gcc/ada/table.adb

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT COMPILER COMPONENTS                         --
   4 --                                                                          --
   5 --                                T A B L E                                 --
   6 --                                                                          --
   7 --                                 B o d y                                  --
   8 --                                                                          --
   9 --          Copyright (C) 1992-2020, 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.  See the GNU General Public License --
  17 -- for  more details.  You should have  received  a copy of the GNU General --
  18 -- Public License  distributed with GNAT; see file COPYING3.  If not, go to --
  19 -- http://www.gnu.org/licenses for a complete copy of the license.          --
  20 --                                                                          --
  21 -- GNAT was originally developed  by the GNAT team at  New York University. --
  22 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
  23 --                                                                          --
  24 ------------------------------------------------------------------------------
  25
  26 with Debug;   use Debug;
  27 with Opt;     use Opt;
  28 with Output;  use Output;
  29 with System;  use System;
  30
  31 with System.Memory; use System.Memory;
  32
  33 with Unchecked_Conversion;
  34
  35 pragma Elaborate_All (Output);
  36
  37 package body Table is
  38    package body Table is
  39
  40       Min : constant Int := Int (Table_Low_Bound);
  41       --  Subscript of the minimum entry in the currently allocated table
  42
  43       Length : Int := 0;
  44       --  Number of entries in currently allocated table. The value of zero
  45       --  ensures that we initially allocate the table.
  46
  47       -----------------------
  48       -- Local Subprograms --
  49       -----------------------
  50
  51       procedure Reallocate;
  52       --  Reallocate the existing table according to the current value stored
  53       --  in Max. Works correctly to do an initial allocation if the table
  54       --  is currently null.
  55
  56       pragma Warnings (Off);
  57       --  Turn off warnings. The following unchecked conversions are only used
  58       --  internally in this package, and cannot never result in any instances
  59       --  of improperly aliased pointers for the client of the package.
  60
  61       function To_Address is new Unchecked_Conversion (Table_Ptr, Address);
  62       function To_Pointer is new Unchecked_Conversion (Address, Table_Ptr);
  63
  64       pragma Warnings (On);
  65
  66       ------------
  67       -- Append --
  68       ------------
  69
  70       procedure Append (New_Val : Table_Component_Type) is
  71       begin
  72          pragma Assert (not Locked);
  73          Set_Item (Table_Index_Type (Last_Val + 1), New_Val);
  74       end Append;
  75
  76       ----------------
  77       -- Append_All --
  78       ----------------
  79
  80       procedure Append_All (New_Vals : Table_Type) is
  81       begin
  82          for J in New_Vals'Range loop
  83             Append (New_Vals (J));
  84          end loop;
  85       end Append_All;
  86
  87       --------------------
  88       -- Decrement_Last --
  89       --------------------
  90
  91       procedure Decrement_Last is
  92       begin
  93          Last_Val := Last_Val - 1;
  94       end Decrement_Last;
  95
  96       ----------
  97       -- Free --
  98       ----------
  99
 100       procedure Free is
 101       begin
 102          Free (To_Address (Table));
 103          Table := null;
 104          Length := 0;
 105       end Free;
 106
 107       --------------------
 108       -- Increment_Last --
 109       --------------------
 110
 111       procedure Increment_Last is
 112       begin
 113          pragma Assert (not Locked);
 114          Last_Val := Last_Val + 1;
 115
 116          if Last_Val > Max then
 117             Reallocate;
 118          end if;
 119       end Increment_Last;
 120
 121       ----------
 122       -- Init --
 123       ----------
 124
 125       procedure Init is
 126          Old_Length : constant Int := Length;
 127
 128       begin
 129          Locked   := False;
 130          Last_Val := Min - 1;
 131          Max      := Min + (Table_Initial * Table_Factor) - 1;
 132          Length   := Max - Min + 1;
 133
 134          --  If table is same size as before (happens when table is never
 135          --  expanded which is a common case), then simply reuse it. Note
 136          --  that this also means that an explicit Init call right after
 137          --  the implicit one in the package body is harmless.
 138
 139          if Old_Length = Length then
 140             return;
 141
 142          --  Otherwise we can use Reallocate to get a table of the right size.
 143          --  Note that Reallocate works fine to allocate a table of the right
 144          --  initial size when it is first allocated.
 145
 146          else
 147             Reallocate;
 148          end if;
 149       end Init;
 150
 151       ----------
 152       -- Last --
 153       ----------
 154
 155       function Last return Table_Index_Type is
 156       begin
 157          return Table_Index_Type (Last_Val);
 158       end Last;
 159
 160       ----------------
 161       -- Reallocate --
 162       ----------------
 163
 164       procedure Reallocate is
 165          New_Size   : Memory.size_t;
 166          New_Length : Long_Long_Integer;
 167
 168       begin
 169          if Max < Last_Val then
 170             pragma Assert (not Locked);
 171
 172             --  Make sure that we have at least the initial allocation. This
 173             --  is needed in cases where a zero length table is written out.
 174
 175             Length := Int'Max (Length, Table_Initial);
 176
 177             --  Now increment table length until it is sufficiently large. Use
 178             --  the increment value or 10, which ever is larger (the reason
 179             --  for the use of 10 here is to ensure that the table does really
 180             --  increase in size (which would not be the case for a table of
 181             --  length 10 increased by 3% for instance). Do the intermediate
 182             --  calculation in Long_Long_Integer to avoid overflow.
 183
 184             while Max < Last_Val loop
 185                New_Length :=
 186                  Long_Long_Integer (Length) *
 187                     (100 + Long_Long_Integer (Table_Increment)) / 100;
 188                Length := Int'Max (Int (New_Length), Length + 10);
 189                Max := Min + Length - 1;
 190             end loop;
 191
 192             if Debug_Flag_D then
 193                Write_Str ("--> Allocating new ");
 194                Write_Str (Table_Name);
 195                Write_Str (" table, size = ");
 196                Write_Int (Max - Min + 1);
 197                Write_Eol;
 198             end if;
 199          end if;
 200
 201          --  Do the intermediate calculation in size_t to avoid signed overflow
 202
 203          New_Size :=
 204            Memory.size_t (Max - Min + 1) *
 205                                     (Table_Type'Component_Size / Storage_Unit);
 206
 207          if Table = null then
 208             Table := To_Pointer (Alloc (New_Size));
 209
 210          elsif New_Size > 0 then
 211             Table :=
 212               To_Pointer (Realloc (Ptr  => To_Address (Table),
 213                                    Size => New_Size));
 214          end if;
 215
 216          if Length /= 0 and then Table = null then
 217             Set_Standard_Error;
 218             Write_Str ("available memory exhausted");
 219             Write_Eol;
 220             Set_Standard_Output;
 221             raise Unrecoverable_Error;
 222          end if;
 223       end Reallocate;
 224
 225       -------------
 226       -- Release --
 227       -------------
 228
 229       procedure Release is
 230          Extra_Length : Int;
 231          Size         : Memory.size_t;
 232
 233       begin
 234          Length := Last_Val - Int (Table_Low_Bound) + 1;
 235          Size   := Memory.size_t (Length) *
 236                      (Table_Type'Component_Size / Storage_Unit);
 237
 238          --  If the size of the table exceeds the release threshold then leave
 239          --  space to store as many extra elements as 0.1% of the table length.
 240
 241          if Release_Threshold > 0
 242            and then Size > Memory.size_t (Release_Threshold)
 243          then
 244             Extra_Length := Length / 1000;
 245             Length := Length + Extra_Length;
 246             Max    := Int (Table_Low_Bound) + Length - 1;
 247
 248             if Debug_Flag_D then
 249                Write_Str ("--> Release_Threshold reached (length=");
 250                Write_Int (Int (Size));
 251                Write_Str ("): leaving room space for ");
 252                Write_Int (Extra_Length);
 253                Write_Str (" components");
 254                Write_Eol;
 255             end if;
 256          else
 257             Max := Last_Val;
 258          end if;
 259
 260          Reallocate;
 261       end Release;
 262
 263       -------------
 264       -- Restore --
 265       -------------
 266
 267       procedure Restore (T : Saved_Table) is
 268       begin
 269          Free (To_Address (Table));
 270          Last_Val := T.Last_Val;
 271          Max      := T.Max;
 272          Table    := T.Table;
 273          Length   := Max - Min + 1;
 274       end Restore;
 275
 276       ----------
 277       -- Save --
 278       ----------
 279
 280       function Save return Saved_Table is
 281          Res : Saved_Table;
 282
 283       begin
 284          Res.Last_Val := Last_Val;
 285          Res.Max      := Max;
 286          Res.Table    := Table;
 287
 288          Table  := null;
 289          Length := 0;
 290          Init;
 291          return Res;
 292       end Save;
 293
 294       --------------
 295       -- Set_Item --
 296       --------------
 297
 298       procedure Set_Item
 299          (Index : Table_Index_Type;
 300           Item  : Table_Component_Type)
 301       is
 302          --  If Item is a value within the current allocation, and we are going
 303          --  to reallocate, then we must preserve an intermediate copy here
 304          --  before calling Increment_Last. Otherwise, if Table_Component_Type
 305          --  is passed by reference, we are going to end up copying from
 306          --  storage that might have been deallocated from Increment_Last
 307          --  calling Reallocate.
 308
 309          subtype Allocated_Table_T is
 310            Table_Type (Table'First .. Table_Index_Type (Max + 1));
 311          --  A constrained table subtype one element larger than the currently
 312          --  allocated table.
 313
 314          Allocated_Table_Address : constant System.Address :=
 315                                      Table.all'Address;
 316          --  Used for address clause below (we can't use non-static expression
 317          --  Table.all'Address directly in the clause because some older
 318          --  versions of the compiler do not allow it).
 319
 320          Allocated_Table : Allocated_Table_T;
 321          pragma Import (Ada, Allocated_Table);
 322          pragma Suppress (Range_Check, On => Allocated_Table);
 323          for Allocated_Table'Address use Allocated_Table_Address;
 324          --  Allocated_Table represents the currently allocated array, plus one
 325          --  element (the supplementary element is used to have a convenient
 326          --  way of computing the address just past the end of the current
 327          --  allocation). Range checks are suppressed because this unit
 328          --  uses direct calls to System.Memory for allocation, and this can
 329          --  yield misaligned storage (and we cannot rely on the bootstrap
 330          --  compiler supporting specifically disabling alignment checks, so we
 331          --  need to suppress all range checks). It is safe to suppress this
 332          --  check here because we know that a (possibly misaligned) object
 333          --  of that type does actually exist at that address.
 334          --  ??? We should really improve the allocation circuitry here to
 335          --  guarantee proper alignment.
 336
 337          Need_Realloc : constant Boolean := Int (Index) > Max;
 338          --  True if this operation requires storage reallocation (which may
 339          --  involve moving table contents around).
 340
 341       begin
 342          --  If we're going to reallocate, check whether Item references an
 343          --  element of the currently allocated table.
 344
 345          if Need_Realloc
 346            and then Allocated_Table'Address <= Item'Address
 347            and then Item'Address <
 348                       Allocated_Table (Table_Index_Type (Max + 1))'Address
 349          then
 350             --  If so, save a copy on the stack because Increment_Last will
 351             --  reallocate storage and might deallocate the current table.
 352
 353             declare
 354                Item_Copy : constant Table_Component_Type := Item;
 355             begin
 356                Set_Last (Index);
 357                Table (Index) := Item_Copy;
 358             end;
 359
 360          else
 361             --  Here we know that either we won't reallocate (case of Index <
 362             --  Max) or that Item is not in the currently allocated table.
 363
 364             if Int (Index) > Last_Val then
 365                Set_Last (Index);
 366             end if;
 367
 368             Table (Index) := Item;
 369          end if;
 370       end Set_Item;
 371
 372       --------------
 373       -- Set_Last --
 374       --------------
 375
 376       procedure Set_Last (New_Val : Table_Index_Type) is
 377       begin
 378          pragma Assert (Int (New_Val) <= Last_Val or else not Locked);
 379
 380          if Int (New_Val) < Last_Val then
 381             Last_Val := Int (New_Val);
 382
 383          else
 384             Last_Val := Int (New_Val);
 385
 386             if Last_Val > Max then
 387                Reallocate;
 388             end if;
 389          end if;
 390       end Set_Last;
 391
 392    begin
 393       Init;
 394    end Table;
 395 end Table;