gcc/ada/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-2016, 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 pragma Compiler_Unit_Warning;
  33
  34 with GNAT.Heap_Sort_G;
  35
  36 with Ada.Unchecked_Deallocation;
  37
  38 package body GNAT.Dynamic_Tables is
  39
  40    Empty : constant Table_Ptr :=
  41              Empty_Table_Array_Ptr_To_Table_Ptr (Empty_Table_Array'Access);
  42
  43    -----------------------
  44    -- Local Subprograms --
  45    -----------------------
  46
  47    procedure Grow (T : in out Instance; New_Last : Table_Count_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    --  T.P.Last is still the old value.
  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       Set_Last (T, T.P.Last + Table_Index_Type'Base (Num));
  62    end Allocate;
  63
  64    ------------
  65    -- Append --
  66    ------------
  67
  68    procedure Append (T : in out Instance; New_Val : Table_Component_Type) is
  69    begin
  70       Set_Item (T, T.P.Last + 1, New_Val);
  71    end Append;
  72
  73    ----------------
  74    -- Append_All --
  75    ----------------
  76
  77    procedure Append_All (T : in out Instance; New_Vals : Table_Type) is
  78    begin
  79       for J in New_Vals'Range loop
  80          Append (T, New_Vals (J));
  81       end loop;
  82    end Append_All;
  83
  84    --------------------
  85    -- Decrement_Last --
  86    --------------------
  87
  88    procedure Decrement_Last (T : in out Instance) is
  89    begin
  90       Allocate (T, -1);
  91    end Decrement_Last;
  92
  93    -----------
  94    -- First --
  95    -----------
  96
  97    function First return Table_Index_Type is
  98    begin
  99       return Table_Low_Bound;
 100    end First;
 101
 102    --------------
 103    -- For_Each --
 104    --------------
 105
 106    procedure For_Each (Table : Instance) is
 107       Quit : Boolean := False;
 108    begin
 109       for Index in Table_Low_Bound .. Table.P.Last loop
 110          Action (Index, Table.Table (Index), Quit);
 111          exit when Quit;
 112       end loop;
 113    end For_Each;
 114
 115    ----------
 116    -- Free --
 117    ----------
 118
 119    procedure Free (T : in out Instance) is
 120       subtype Alloc_Type is Table_Type (First .. T.P.Last_Allocated);
 121       type Alloc_Ptr is access all Alloc_Type;
 122
 123       procedure Free is new Ada.Unchecked_Deallocation (Alloc_Type, Alloc_Ptr);
 124       function To_Alloc_Ptr is
 125         new Ada.Unchecked_Conversion (Table_Ptr, Alloc_Ptr);
 126
 127       Temp : Alloc_Ptr := To_Alloc_Ptr (T.Table);
 128
 129    begin
 130       if T.Table = Empty then
 131          pragma Assert (T.P.Last_Allocated = First - 1);
 132          pragma Assert (T.P.Last = First - 1);
 133          null;
 134       else
 135          Free (Temp);
 136          T.Table := Empty;
 137          T.P.Last_Allocated := First - 1;
 138          T.P.Last := First - 1;
 139       end if;
 140    end Free;
 141
 142    ----------
 143    -- Grow --
 144    ----------
 145
 146    procedure Grow (T : in out Instance; New_Last : Table_Count_Type) is
 147
 148       --  Note: Type Alloc_Ptr below needs to be declared locally so we know
 149       --  the bounds. That means that the collection is local, so is finalized
 150       --  when leaving Grow. That's why this package doesn't support controlled
 151       --  types; the table elements would be finalized prematurely. An Ada
 152       --  implementation would also be within its rights to reclaim the
 153       --  storage. Fortunately, GNAT doesn't do that.
 154
 155       pragma Assert (not T.Locked);
 156       pragma Assert (New_Last > T.P.Last_Allocated);
 157
 158       subtype Table_Length_Type is Table_Index_Type'Base
 159         range 0 .. Table_Index_Type'Base'Last;
 160
 161       Old_Last_Allocated   : constant Table_Count_Type  := T.P.Last_Allocated;
 162       Old_Allocated_Length : constant Table_Length_Type :=
 163                                Old_Last_Allocated - First + 1;
 164
 165       New_Length : constant Table_Length_Type := New_Last - First + 1;
 166       New_Allocated_Length : Table_Length_Type;
 167
 168    begin
 169       if T.Table = Empty then
 170          New_Allocated_Length := Table_Length_Type (Table_Initial);
 171       else
 172          New_Allocated_Length :=
 173            Table_Length_Type
 174              (Long_Long_Integer (Old_Allocated_Length) *
 175                (100 + Long_Long_Integer (Table_Increment)) / 100);
 176       end if;
 177
 178       --  Make sure it really did grow
 179
 180       if New_Allocated_Length <= Old_Allocated_Length then
 181          New_Allocated_Length := Old_Allocated_Length + 10;
 182       end if;
 183
 184       if New_Allocated_Length <= New_Length then
 185          New_Allocated_Length := New_Length + 10;
 186       end if;
 187
 188       pragma Assert (New_Allocated_Length > Old_Allocated_Length);
 189       pragma Assert (New_Allocated_Length > New_Length);
 190
 191       T.P.Last_Allocated := First + New_Allocated_Length - 1;
 192
 193       declare
 194          subtype Old_Alloc_Type is Table_Type (First .. Old_Last_Allocated);
 195          type Old_Alloc_Ptr is access all Old_Alloc_Type;
 196
 197          procedure Free is
 198            new Ada.Unchecked_Deallocation (Old_Alloc_Type, Old_Alloc_Ptr);
 199          function To_Old_Alloc_Ptr is
 200            new Ada.Unchecked_Conversion (Table_Ptr, Old_Alloc_Ptr);
 201
 202          subtype Alloc_Type is
 203            Table_Type (First .. First + New_Allocated_Length - 1);
 204          type Alloc_Ptr is access all Alloc_Type;
 205
 206          function To_Table_Ptr is
 207            new Ada.Unchecked_Conversion (Alloc_Ptr, Table_Ptr);
 208
 209          Old_Table : Old_Alloc_Ptr := To_Old_Alloc_Ptr (T.Table);
 210          New_Table : constant Alloc_Ptr := new Alloc_Type;
 211
 212       begin
 213          if T.Table /= Empty then
 214             New_Table (First .. T.P.Last) := Old_Table (First .. T.P.Last);
 215             Free (Old_Table);
 216          end if;
 217
 218          T.Table := To_Table_Ptr (New_Table);
 219       end;
 220
 221       pragma Assert (New_Last <= T.P.Last_Allocated);
 222       pragma Assert (T.Table /= null);
 223       pragma Assert (T.Table /= Empty);
 224    end Grow;
 225
 226    --------------------
 227    -- Increment_Last --
 228    --------------------
 229
 230    procedure Increment_Last (T : in out Instance) is
 231    begin
 232       Allocate (T, 1);
 233    end Increment_Last;
 234
 235    ----------
 236    -- Init --
 237    ----------
 238
 239    procedure Init (T : in out Instance) is
 240    begin
 241       Free (T);
 242    end Init;
 243
 244    ----------
 245    -- Last --
 246    ----------
 247
 248    function Last (T : Instance) return Table_Count_Type is
 249    begin
 250       return T.P.Last;
 251    end Last;
 252
 253    -------------
 254    -- Release --
 255    -------------
 256
 257    procedure Release (T : in out Instance) is
 258       pragma Assert (not T.Locked);
 259       Old_Last_Allocated : constant Table_Count_Type := T.P.Last_Allocated;
 260    begin
 261       if T.P.Last /= T.P.Last_Allocated then
 262          pragma Assert (T.P.Last < T.P.Last_Allocated);
 263          pragma Assert (T.Table /= Empty);
 264
 265          declare
 266             subtype Old_Alloc_Type is Table_Type (First .. Old_Last_Allocated);
 267             type Old_Alloc_Ptr is access all Old_Alloc_Type;
 268
 269             procedure Free is
 270               new Ada.Unchecked_Deallocation (Old_Alloc_Type, Old_Alloc_Ptr);
 271             function To_Old_Alloc_Ptr is
 272               new Ada.Unchecked_Conversion (Table_Ptr, Old_Alloc_Ptr);
 273
 274             subtype Alloc_Type is
 275               Table_Type (First .. First + T.P.Last - 1);
 276             type Alloc_Ptr is access all Alloc_Type;
 277
 278             function To_Table_Ptr is
 279               new Ada.Unchecked_Conversion (Alloc_Ptr, Table_Ptr);
 280
 281             Old_Table : Old_Alloc_Ptr := To_Old_Alloc_Ptr (T.Table);
 282             New_Table : constant Alloc_Ptr := new Alloc_Type'(Old_Table.all);
 283          begin
 284             T.P.Last_Allocated := T.P.Last;
 285             Free (Old_Table);
 286             T.Table := To_Table_Ptr (New_Table);
 287          end;
 288       end if;
 289
 290       pragma Assert (T.P.Last = T.P.Last_Allocated);
 291    end Release;
 292
 293    --------------
 294    -- Set_Item --
 295    --------------
 296
 297    procedure Set_Item
 298      (T     : in out Instance;
 299       Index : Valid_Table_Index_Type;
 300       Item  : Table_Component_Type)
 301    is
 302       Item_Copy : constant Table_Component_Type := Item;
 303    begin
 304       --  If Set_Last is going to reallocate the table, we make a copy of Item,
 305       --  in case the call was "Set_Item (T, X, T.Table (Y));", and Item is
 306       --  passed by reference. Without the copy, we would deallocate the array
 307       --  containing Item, leaving a dangling pointer.
 308
 309       if Index > T.P.Last_Allocated then
 310          declare
 311             Item_Copy : constant Table_Component_Type := Item;
 312          begin
 313             Set_Last (T, Index);
 314             T.Table (Index) := Item_Copy;
 315          end;
 316
 317          return;
 318       end if;
 319
 320       if Index > T.P.Last then
 321          Set_Last (T, Index);
 322       end if;
 323
 324       T.Table (Index) := Item_Copy;
 325    end Set_Item;
 326
 327    --------------
 328    -- Set_Last --
 329    --------------
 330
 331    procedure Set_Last (T : in out Instance; New_Val : Table_Count_Type) is
 332       pragma Assert (not T.Locked);
 333    begin
 334       if New_Val > T.P.Last_Allocated then
 335          Grow (T, New_Val);
 336       end if;
 337
 338       T.P.Last := New_Val;
 339    end Set_Last;
 340
 341    ----------------
 342    -- Sort_Table --
 343    ----------------
 344
 345    procedure Sort_Table (Table : in out Instance) is
 346       Temp : Table_Component_Type;
 347       --  A temporary position to simulate index 0
 348
 349       --  Local subprograms
 350
 351       function Index_Of (Idx : Natural) return Table_Index_Type'Base;
 352       --  Return index of Idx'th element of table
 353
 354       function Lower_Than (Op1, Op2 : Natural) return Boolean;
 355       --  Compare two components
 356
 357       procedure Move (From : Natural; To : Natural);
 358       --  Move one component
 359
 360       package Heap_Sort is new GNAT.Heap_Sort_G (Move, Lower_Than);
 361
 362       --------------
 363       -- Index_Of --
 364       --------------
 365
 366       function Index_Of (Idx : Natural) return Table_Index_Type'Base is
 367          J : constant Integer'Base :=
 368                Table_Index_Type'Base'Pos (First) + Idx - 1;
 369       begin
 370          return Table_Index_Type'Base'Val (J);
 371       end Index_Of;
 372
 373       ----------
 374       -- Move --
 375       ----------
 376
 377       procedure Move (From : Natural; To : Natural) is
 378       begin
 379          if From = 0 then
 380             Table.Table (Index_Of (To)) := Temp;
 381
 382          elsif To = 0 then
 383             Temp := Table.Table (Index_Of (From));
 384
 385          else
 386             Table.Table (Index_Of (To)) :=
 387               Table.Table (Index_Of (From));
 388          end if;
 389       end Move;
 390
 391       ----------------
 392       -- Lower_Than --
 393       ----------------
 394
 395       function Lower_Than (Op1, Op2 : Natural) return Boolean is
 396       begin
 397          if Op1 = 0 then
 398             return Lt (Temp, Table.Table (Index_Of (Op2)));
 399
 400          elsif Op2 = 0 then
 401             return Lt (Table.Table (Index_Of (Op1)), Temp);
 402
 403          else
 404             return
 405               Lt (Table.Table (Index_Of (Op1)), Table.Table (Index_Of (Op2)));
 406          end if;
 407       end Lower_Than;
 408
 409    --  Start of processing for Sort_Table
 410
 411    begin
 412       Heap_Sort.Sort (Natural (Last (Table) - First) + 1);
 413    end Sort_Table;
 414
 415 end GNAT.Dynamic_Tables;