gcc/ada/libgnat/g-dyntab.adb

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT COMPILER COMPONENTS                         --
   4 --                                                                          --
   5 --                   G N A T . D Y N A M I C _ T A B L E S                  --
   6 --                                                                          --
   7 --                                 B o d y                                  --
   8 --                                                                          --
   9 --                     Copyright (C) 2000-2024, AdaCore                     --
  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 -- GNAT was originally developed  by the GNAT team at  New York University. --
  28 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
  29 --                                                                          --
  30 ------------------------------------------------------------------------------
  31
  32 with GNAT.Heap_Sort_G;
  33
  34 with Ada.Unchecked_Deallocation;
  35 with System;
  36
  37 package body GNAT.Dynamic_Tables is
  38
  39    -----------------------
  40    -- Local Subprograms --
  41    -----------------------
  42
  43    function Last_Allocated (T : Instance) return Table_Last_Type;
  44    pragma Inline (Last_Allocated);
  45    --  Return the index of the last allocated element
  46
  47    procedure Grow (T : in out Instance; New_Last : Table_Last_Type);
  48    --  This is called when we are about to set the value of Last to a value
  49    --  that is larger than Last_Allocated. This reallocates the table to the
  50    --  larger size, as indicated by New_Last. At the time this is called,
  51    --  Last (T) is still the old value, and this does not modify it.
  52
  53    --------------
  54    -- Allocate --
  55    --------------
  56
  57    procedure Allocate (T : in out Instance; Num : Integer := 1) is
  58    begin
  59       --  Note that Num can be negative
  60
  61       pragma Assert (not T.Locked);
  62       Set_Last (T, Last (T) + Table_Index_Type'Base (Num));
  63    end Allocate;
  64
  65    ------------
  66    -- Append --
  67    ------------
  68
  69    procedure Append (T : in out Instance; New_Val : Table_Component_Type) is
  70       pragma Assert (not T.Locked);
  71       New_Last : constant Table_Last_Type := Last (T) + 1;
  72
  73    begin
  74       if New_Last <= Last_Allocated (T) then
  75
  76          --  Fast path
  77
  78          T.P.Last := New_Last;
  79          T.Table (New_Last) := New_Val;
  80
  81       else
  82          Set_Item (T, New_Last, New_Val);
  83       end if;
  84    end Append;
  85
  86    ----------------
  87    -- Append_All --
  88    ----------------
  89
  90    procedure Append_All (T : in out Instance; New_Vals : Table_Type) is
  91    begin
  92       for J in New_Vals'Range loop
  93          Append (T, New_Vals (J));
  94       end loop;
  95    end Append_All;
  96
  97    --------------------
  98    -- Decrement_Last --
  99    --------------------
 100
 101    procedure Decrement_Last (T : in out Instance) is
 102    begin
 103       pragma Assert (not T.Locked);
 104       Allocate (T, -1);
 105    end Decrement_Last;
 106
 107    -----------
 108    -- First --
 109    -----------
 110
 111    function First return Table_Index_Type is
 112    begin
 113       return Table_Low_Bound;
 114    end First;
 115
 116    --------------
 117    -- For_Each --
 118    --------------
 119
 120    procedure For_Each (Table : Instance) is
 121       Quit : Boolean := False;
 122    begin
 123       for Index in First .. Last (Table) loop
 124          Action (Index, Table.Table (Index), Quit);
 125          exit when Quit;
 126       end loop;
 127    end For_Each;
 128
 129    ----------
 130    -- Grow --
 131    ----------
 132
 133    procedure Grow (T : in out Instance; New_Last : Table_Last_Type) is
 134
 135       --  Note: Type Alloc_Ptr below needs to be declared locally so we know
 136       --  the bounds. That means that the collection is local, so is finalized
 137       --  when leaving Grow. That's why this package doesn't support controlled
 138       --  types; the table elements would be finalized prematurely. An Ada
 139       --  implementation would also be within its rights to reclaim the
 140       --  storage. Fortunately, GNAT doesn't do that.
 141
 142       pragma Assert (not T.Locked);
 143       pragma Assert (New_Last > Last_Allocated (T));
 144
 145       subtype Table_Length_Type is Table_Index_Type'Base
 146         range 0 .. Table_Index_Type'Base'Last;
 147
 148       Old_Last_Allocated   : constant Table_Last_Type := Last_Allocated (T);
 149       Old_Allocated_Length : constant Table_Length_Type :=
 150                                Old_Last_Allocated - First + 1;
 151
 152       New_Length : constant Table_Length_Type := New_Last - First + 1;
 153       New_Allocated_Length : Table_Length_Type;
 154
 155    begin
 156       if T.Table = Empty_Table_Ptr then
 157          New_Allocated_Length := Table_Length_Type (Table_Initial);
 158       else
 159          New_Allocated_Length :=
 160            Table_Length_Type
 161              (Long_Long_Integer (Old_Allocated_Length) *
 162                (100 + Long_Long_Integer (Table_Increment)) / 100);
 163       end if;
 164
 165       --  Make sure it really did grow
 166
 167       if New_Allocated_Length <= Old_Allocated_Length then
 168          New_Allocated_Length := Old_Allocated_Length + 10;
 169       end if;
 170
 171       if New_Allocated_Length <= New_Length then
 172          New_Allocated_Length := New_Length + 10;
 173       end if;
 174
 175       pragma Assert (New_Allocated_Length > Old_Allocated_Length);
 176       pragma Assert (New_Allocated_Length > New_Length);
 177
 178       T.P.Last_Allocated := First + New_Allocated_Length - 1;
 179
 180       declare
 181          subtype Old_Alloc_Type is Table_Type (First .. Old_Last_Allocated);
 182          type Old_Alloc_Ptr is access all Old_Alloc_Type;
 183
 184          procedure Free is
 185            new Ada.Unchecked_Deallocation (Old_Alloc_Type, Old_Alloc_Ptr);
 186          function To_Old_Alloc_Ptr is
 187            new Ada.Unchecked_Conversion (Table_Ptr, Old_Alloc_Ptr);
 188
 189          subtype Alloc_Type is
 190            Table_Type (First .. First + New_Allocated_Length - 1);
 191          type Alloc_Ptr is access all Alloc_Type;
 192
 193          function To_Table_Ptr is
 194            new Ada.Unchecked_Conversion (Alloc_Ptr, Table_Ptr);
 195
 196          Old_Table : Old_Alloc_Ptr := To_Old_Alloc_Ptr (T.Table);
 197          New_Table : constant Alloc_Ptr := new Alloc_Type;
 198
 199       begin
 200          if T.Table /= Empty_Table_Ptr then
 201             New_Table (First .. Last (T)) := Old_Table (First .. Last (T));
 202             Free (Old_Table);
 203          end if;
 204
 205          T.Table := To_Table_Ptr (New_Table);
 206       end;
 207
 208       pragma Assert (New_Last <= Last_Allocated (T));
 209       pragma Assert (T.Table /= null);
 210       pragma Assert (T.Table /= Empty_Table_Ptr);
 211    end Grow;
 212
 213    --------------------
 214    -- Increment_Last --
 215    --------------------
 216
 217    procedure Increment_Last (T : in out Instance) is
 218    begin
 219       pragma Assert (not T.Locked);
 220       Allocate (T, 1);
 221    end Increment_Last;
 222
 223    ----------
 224    -- Init --
 225    ----------
 226
 227    procedure Init (T : in out Instance) is
 228       pragma Assert (not T.Locked);
 229       subtype Alloc_Type is Table_Type (First .. Last_Allocated (T));
 230       type Alloc_Ptr is access all Alloc_Type;
 231
 232       procedure Free is new Ada.Unchecked_Deallocation (Alloc_Type, Alloc_Ptr);
 233       function To_Alloc_Ptr is
 234         new Ada.Unchecked_Conversion (Table_Ptr, Alloc_Ptr);
 235
 236       Temp : Alloc_Ptr := To_Alloc_Ptr (T.Table);
 237
 238    begin
 239       if T.Table = Empty_Table_Ptr then
 240          pragma Assert (T.P = (Last_Allocated | Last => First - 1));
 241          null;
 242       else
 243          Free (Temp);
 244          T.Table := Empty_Table_Ptr;
 245          T.P := (Last_Allocated | Last => First - 1);
 246       end if;
 247    end Init;
 248
 249    --------------
 250    -- Is_Empty --
 251    --------------
 252
 253    function Is_Empty (T : Instance) return Boolean is
 254    begin
 255       return Last (T) = First - 1;
 256    end Is_Empty;
 257
 258    ----------
 259    -- Last --
 260    ----------
 261
 262    function Last (T : Instance) return Table_Last_Type is
 263    begin
 264       return T.P.Last;
 265    end Last;
 266
 267    --------------------
 268    -- Last_Allocated --
 269    --------------------
 270
 271    function Last_Allocated (T : Instance) return Table_Last_Type is
 272    begin
 273       return T.P.Last_Allocated;
 274    end Last_Allocated;
 275
 276    ----------
 277    -- Move --
 278    ----------
 279
 280    procedure Move (From, To : in out Instance) is
 281    begin
 282       pragma Assert (not From.Locked);
 283       pragma Assert (not To.Locked);
 284       pragma Assert (Is_Empty (To));
 285       To := From;
 286
 287       From.Table            := Empty_Table_Ptr;
 288       From.Locked           := False;
 289       From.P.Last_Allocated := First - 1;
 290       From.P.Last           := First - 1;
 291       pragma Assert (Is_Empty (From));
 292    end Move;
 293
 294    -------------
 295    -- Release --
 296    -------------
 297
 298    procedure Release (T : in out Instance) is
 299       pragma Assert (not T.Locked);
 300       Old_Last_Allocated : constant Table_Last_Type := Last_Allocated (T);
 301
 302       function New_Last_Allocated return Table_Last_Type;
 303       --  Compute the new value of Last_Allocated. This is normally equal to
 304       --  Last, but if Release_Threshold /= 0, then we need to take that into
 305       --  account.
 306
 307       ------------------------
 308       -- New_Last_Allocated --
 309       ------------------------
 310
 311       function New_Last_Allocated return Table_Last_Type is
 312          subtype Table_Length_Type is Table_Index_Type'Base
 313            range 0 .. Table_Index_Type'Base'Last;
 314
 315          Length : constant Table_Length_Type := Last (T) - First + 1;
 316
 317          Comp_Size_In_Bytes : constant Table_Length_Type :=
 318            Table_Type'Component_Size / System.Storage_Unit;
 319
 320          Length_Threshold : constant Table_Length_Type :=
 321            Table_Length_Type (Release_Threshold) / Comp_Size_In_Bytes;
 322
 323       begin
 324          if Release_Threshold = 0 or else Length < Length_Threshold then
 325             return Last (T);
 326          else
 327             declare
 328                Extra_Length : constant Table_Length_Type := Length / 1000;
 329             begin
 330                return (Length + Extra_Length) - 1 + First;
 331             end;
 332          end if;
 333       end New_Last_Allocated;
 334
 335       --  Local variables
 336
 337       New_Last_Alloc : constant Table_Last_Type := New_Last_Allocated;
 338
 339    --  Start of processing for Release
 340
 341    begin
 342       if New_Last_Alloc < Last_Allocated (T) then
 343          pragma Assert (Last (T) < Last_Allocated (T));
 344          pragma Assert (T.Table /= Empty_Table_Ptr);
 345
 346          declare
 347             subtype Old_Alloc_Type is Table_Type (First .. Old_Last_Allocated);
 348             type Old_Alloc_Ptr is access all Old_Alloc_Type;
 349
 350             procedure Free is
 351               new Ada.Unchecked_Deallocation (Old_Alloc_Type, Old_Alloc_Ptr);
 352             function To_Old_Alloc_Ptr is
 353               new Ada.Unchecked_Conversion (Table_Ptr, Old_Alloc_Ptr);
 354
 355             subtype Alloc_Type is Table_Type (First .. New_Last_Alloc);
 356             type Alloc_Ptr is access all Alloc_Type;
 357
 358             function To_Table_Ptr is
 359               new Ada.Unchecked_Conversion (Alloc_Ptr, Table_Ptr);
 360
 361             Old_Table : Old_Alloc_Ptr := To_Old_Alloc_Ptr (T.Table);
 362             New_Table : constant Alloc_Ptr := new Alloc_Type;
 363
 364          begin
 365             New_Table (First .. Last (T)) := Old_Table (First .. Last (T));
 366             T.P.Last_Allocated := New_Last_Alloc;
 367             Free (Old_Table);
 368             T.Table := To_Table_Ptr (New_Table);
 369          end;
 370       end if;
 371    end Release;
 372
 373    --------------
 374    -- Set_Item --
 375    --------------
 376
 377    procedure Set_Item
 378      (T     : in out Instance;
 379       Index : Valid_Table_Index_Type;
 380       Item  : Table_Component_Type)
 381    is
 382    begin
 383       pragma Assert (not T.Locked);
 384
 385       --  If Set_Last is going to reallocate the table, we make a copy of Item,
 386       --  in case the call was "Set_Item (T, X, T.Table (Y));", and Item is
 387       --  passed by reference. Without the copy, we would deallocate the array
 388       --  containing Item, leaving a dangling pointer.
 389
 390       if Index > Last_Allocated (T) then
 391          declare
 392             Item_Copy : constant Table_Component_Type := Item;
 393          begin
 394             Set_Last (T, Index);
 395             T.Table (Index) := Item_Copy;
 396          end;
 397
 398       else
 399          if Index > Last (T) then
 400             Set_Last (T, Index);
 401          end if;
 402
 403          T.Table (Index) := Item;
 404       end if;
 405    end Set_Item;
 406
 407    --------------
 408    -- Set_Last --
 409    --------------
 410
 411    procedure Set_Last (T : in out Instance; New_Val : Table_Last_Type) is
 412    begin
 413       pragma Assert (not T.Locked);
 414       if New_Val > Last_Allocated (T) then
 415          Grow (T, New_Val);
 416       end if;
 417
 418       T.P.Last := New_Val;
 419    end Set_Last;
 420
 421    ----------------
 422    -- Sort_Table --
 423    ----------------
 424
 425    procedure Sort_Table (Table : in out Instance) is
 426       Temp : Table_Component_Type;
 427       --  A temporary position to simulate index 0
 428
 429       --  Local subprograms
 430
 431       function Index_Of (Idx : Natural) return Table_Index_Type'Base;
 432       --  Return index of Idx'th element of table
 433
 434       function Lower_Than (Op1, Op2 : Natural) return Boolean;
 435       --  Compare two components
 436
 437       procedure Move (From : Natural; To : Natural);
 438       --  Move one component
 439
 440       package Heap_Sort is new GNAT.Heap_Sort_G (Move, Lower_Than);
 441
 442       --------------
 443       -- Index_Of --
 444       --------------
 445
 446       function Index_Of (Idx : Natural) return Table_Index_Type'Base is
 447          J : constant Integer'Base :=
 448                Table_Index_Type'Base'Pos (First) + Idx - 1;
 449       begin
 450          return Table_Index_Type'Base'Val (J);
 451       end Index_Of;
 452
 453       ----------
 454       -- Move --
 455       ----------
 456
 457       procedure Move (From : Natural; To : Natural) is
 458       begin
 459          if From = 0 then
 460             Table.Table (Index_Of (To)) := Temp;
 461
 462          elsif To = 0 then
 463             Temp := Table.Table (Index_Of (From));
 464
 465          else
 466             Table.Table (Index_Of (To)) :=
 467               Table.Table (Index_Of (From));
 468          end if;
 469       end Move;
 470
 471       ----------------
 472       -- Lower_Than --
 473       ----------------
 474
 475       function Lower_Than (Op1, Op2 : Natural) return Boolean is
 476       begin
 477          if Op1 = 0 then
 478             return Lt (Temp, Table.Table (Index_Of (Op2)));
 479
 480          elsif Op2 = 0 then
 481             return Lt (Table.Table (Index_Of (Op1)), Temp);
 482
 483          else
 484             return
 485               Lt (Table.Table (Index_Of (Op1)), Table.Table (Index_Of (Op2)));
 486          end if;
 487       end Lower_Than;
 488
 489    --  Start of processing for Sort_Table
 490
 491    begin
 492       Heap_Sort.Sort (Natural (Last (Table) - First) + 1);
 493    end Sort_Table;
 494
 495 end GNAT.Dynamic_Tables;