------------------------------------------------------------------------------ -- -- -- GNAT COMPILER COMPONENTS -- -- -- -- G N A T . D Y N A M I C _ T A B L E S -- -- -- -- B o d y -- -- -- -- Copyright (C) 2000-2018, AdaCore -- -- -- -- GNAT is free software; you can redistribute it and/or modify it under -- -- terms of the GNU General Public License as published by the Free Soft- -- -- ware Foundation; either version 3, or (at your option) any later ver- -- -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- -- or FITNESS FOR A PARTICULAR PURPOSE. -- -- -- -- As a special exception under Section 7 of GPL version 3, you are granted -- -- additional permissions described in the GCC Runtime Library Exception, -- -- version 3.1, as published by the Free Software Foundation. -- -- -- -- You should have received a copy of the GNU General Public License and -- -- a copy of the GCC Runtime Library Exception along with this program; -- -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- -- . -- -- -- -- GNAT was originally developed by the GNAT team at New York University. -- -- Extensive contributions were provided by Ada Core Technologies Inc. -- -- -- ------------------------------------------------------------------------------ pragma Compiler_Unit_Warning; with GNAT.Heap_Sort_G; with Ada.Unchecked_Deallocation; with System; package body GNAT.Dynamic_Tables is ----------------------- -- Local Subprograms -- ----------------------- function Last_Allocated (T : Instance) return Table_Last_Type; pragma Inline (Last_Allocated); -- Return the index of the last allocated element procedure Grow (T : in out Instance; New_Last : Table_Last_Type); -- This is called when we are about to set the value of Last to a value -- that is larger than Last_Allocated. This reallocates the table to the -- larger size, as indicated by New_Last. At the time this is called, -- Last (T) is still the old value, and this does not modify it. -------------- -- Allocate -- -------------- procedure Allocate (T : in out Instance; Num : Integer := 1) is begin -- Note that Num can be negative pragma Assert (not T.Locked); Set_Last (T, Last (T) + Table_Index_Type'Base (Num)); end Allocate; ------------ -- Append -- ------------ procedure Append (T : in out Instance; New_Val : Table_Component_Type) is pragma Assert (not T.Locked); New_Last : constant Table_Last_Type := Last (T) + 1; begin if New_Last <= Last_Allocated (T) then -- Fast path T.P.Last := New_Last; T.Table (New_Last) := New_Val; else Set_Item (T, New_Last, New_Val); end if; end Append; ---------------- -- Append_All -- ---------------- procedure Append_All (T : in out Instance; New_Vals : Table_Type) is begin for J in New_Vals'Range loop Append (T, New_Vals (J)); end loop; end Append_All; -------------------- -- Decrement_Last -- -------------------- procedure Decrement_Last (T : in out Instance) is begin pragma Assert (not T.Locked); Allocate (T, -1); end Decrement_Last; ----------- -- First -- ----------- function First return Table_Index_Type is begin return Table_Low_Bound; end First; -------------- -- For_Each -- -------------- procedure For_Each (Table : Instance) is Quit : Boolean := False; begin for Index in First .. Last (Table) loop Action (Index, Table.Table (Index), Quit); exit when Quit; end loop; end For_Each; ---------- -- Grow -- ---------- procedure Grow (T : in out Instance; New_Last : Table_Last_Type) is -- Note: Type Alloc_Ptr below needs to be declared locally so we know -- the bounds. That means that the collection is local, so is finalized -- when leaving Grow. That's why this package doesn't support controlled -- types; the table elements would be finalized prematurely. An Ada -- implementation would also be within its rights to reclaim the -- storage. Fortunately, GNAT doesn't do that. pragma Assert (not T.Locked); pragma Assert (New_Last > Last_Allocated (T)); subtype Table_Length_Type is Table_Index_Type'Base range 0 .. Table_Index_Type'Base'Last; Old_Last_Allocated : constant Table_Last_Type := Last_Allocated (T); Old_Allocated_Length : constant Table_Length_Type := Old_Last_Allocated - First + 1; New_Length : constant Table_Length_Type := New_Last - First + 1; New_Allocated_Length : Table_Length_Type; begin if T.Table = Empty_Table_Ptr then New_Allocated_Length := Table_Length_Type (Table_Initial); else New_Allocated_Length := Table_Length_Type (Long_Long_Integer (Old_Allocated_Length) * (100 + Long_Long_Integer (Table_Increment)) / 100); end if; -- Make sure it really did grow if New_Allocated_Length <= Old_Allocated_Length then New_Allocated_Length := Old_Allocated_Length + 10; end if; if New_Allocated_Length <= New_Length then New_Allocated_Length := New_Length + 10; end if; pragma Assert (New_Allocated_Length > Old_Allocated_Length); pragma Assert (New_Allocated_Length > New_Length); T.P.Last_Allocated := First + New_Allocated_Length - 1; declare subtype Old_Alloc_Type is Table_Type (First .. Old_Last_Allocated); type Old_Alloc_Ptr is access all Old_Alloc_Type; procedure Free is new Ada.Unchecked_Deallocation (Old_Alloc_Type, Old_Alloc_Ptr); function To_Old_Alloc_Ptr is new Ada.Unchecked_Conversion (Table_Ptr, Old_Alloc_Ptr); subtype Alloc_Type is Table_Type (First .. First + New_Allocated_Length - 1); type Alloc_Ptr is access all Alloc_Type; function To_Table_Ptr is new Ada.Unchecked_Conversion (Alloc_Ptr, Table_Ptr); Old_Table : Old_Alloc_Ptr := To_Old_Alloc_Ptr (T.Table); New_Table : constant Alloc_Ptr := new Alloc_Type; begin if T.Table /= Empty_Table_Ptr then New_Table (First .. Last (T)) := Old_Table (First .. Last (T)); Free (Old_Table); end if; T.Table := To_Table_Ptr (New_Table); end; pragma Assert (New_Last <= Last_Allocated (T)); pragma Assert (T.Table /= null); pragma Assert (T.Table /= Empty_Table_Ptr); end Grow; -------------------- -- Increment_Last -- -------------------- procedure Increment_Last (T : in out Instance) is begin pragma Assert (not T.Locked); Allocate (T, 1); end Increment_Last; ---------- -- Init -- ---------- procedure Init (T : in out Instance) is pragma Assert (not T.Locked); subtype Alloc_Type is Table_Type (First .. Last_Allocated (T)); type Alloc_Ptr is access all Alloc_Type; procedure Free is new Ada.Unchecked_Deallocation (Alloc_Type, Alloc_Ptr); function To_Alloc_Ptr is new Ada.Unchecked_Conversion (Table_Ptr, Alloc_Ptr); Temp : Alloc_Ptr := To_Alloc_Ptr (T.Table); begin if T.Table = Empty_Table_Ptr then pragma Assert (T.P = (Last_Allocated | Last => First - 1)); null; else Free (Temp); T.Table := Empty_Table_Ptr; T.P := (Last_Allocated | Last => First - 1); end if; end Init; -------------- -- Is_Empty -- -------------- function Is_Empty (T : Instance) return Boolean is begin return Last (T) = First - 1; end Is_Empty; ---------- -- Last -- ---------- function Last (T : Instance) return Table_Last_Type is begin return T.P.Last; end Last; -------------------- -- Last_Allocated -- -------------------- function Last_Allocated (T : Instance) return Table_Last_Type is begin return T.P.Last_Allocated; end Last_Allocated; ---------- -- Move -- ---------- procedure Move (From, To : in out Instance) is begin pragma Assert (not From.Locked); pragma Assert (not To.Locked); pragma Assert (Is_Empty (To)); To := From; From.Table := Empty_Table_Ptr; From.Locked := False; From.P.Last_Allocated := First - 1; From.P.Last := First - 1; pragma Assert (Is_Empty (From)); end Move; ------------- -- Release -- ------------- procedure Release (T : in out Instance) is pragma Assert (not T.Locked); Old_Last_Allocated : constant Table_Last_Type := Last_Allocated (T); function New_Last_Allocated return Table_Last_Type; -- Compute the new value of Last_Allocated. This is normally equal to -- Last, but if Release_Threshold /= 0, then we need to take that into -- account. ------------------------ -- New_Last_Allocated -- ------------------------ function New_Last_Allocated return Table_Last_Type is subtype Table_Length_Type is Table_Index_Type'Base range 0 .. Table_Index_Type'Base'Last; Length : constant Table_Length_Type := Last (T) - First + 1; Comp_Size_In_Bytes : constant Table_Length_Type := Table_Type'Component_Size / System.Storage_Unit; Length_Threshold : constant Table_Length_Type := Table_Length_Type (Release_Threshold) / Comp_Size_In_Bytes; begin if Release_Threshold = 0 or else Length < Length_Threshold then return Last (T); else declare Extra_Length : constant Table_Length_Type := Length / 1000; begin return (Length + Extra_Length) - 1 + First; end; end if; end New_Last_Allocated; -- Local variables New_Last_Alloc : constant Table_Last_Type := New_Last_Allocated; -- Start of processing for Release begin if New_Last_Alloc < Last_Allocated (T) then pragma Assert (Last (T) < Last_Allocated (T)); pragma Assert (T.Table /= Empty_Table_Ptr); declare subtype Old_Alloc_Type is Table_Type (First .. Old_Last_Allocated); type Old_Alloc_Ptr is access all Old_Alloc_Type; procedure Free is new Ada.Unchecked_Deallocation (Old_Alloc_Type, Old_Alloc_Ptr); function To_Old_Alloc_Ptr is new Ada.Unchecked_Conversion (Table_Ptr, Old_Alloc_Ptr); subtype Alloc_Type is Table_Type (First .. New_Last_Alloc); type Alloc_Ptr is access all Alloc_Type; function To_Table_Ptr is new Ada.Unchecked_Conversion (Alloc_Ptr, Table_Ptr); Old_Table : Old_Alloc_Ptr := To_Old_Alloc_Ptr (T.Table); New_Table : constant Alloc_Ptr := new Alloc_Type; begin New_Table (First .. Last (T)) := Old_Table (First .. Last (T)); T.P.Last_Allocated := New_Last_Alloc; Free (Old_Table); T.Table := To_Table_Ptr (New_Table); end; end if; end Release; -------------- -- Set_Item -- -------------- procedure Set_Item (T : in out Instance; Index : Valid_Table_Index_Type; Item : Table_Component_Type) is begin pragma Assert (not T.Locked); -- If Set_Last is going to reallocate the table, we make a copy of Item, -- in case the call was "Set_Item (T, X, T.Table (Y));", and Item is -- passed by reference. Without the copy, we would deallocate the array -- containing Item, leaving a dangling pointer. if Index > Last_Allocated (T) then declare Item_Copy : constant Table_Component_Type := Item; begin Set_Last (T, Index); T.Table (Index) := Item_Copy; end; else if Index > Last (T) then Set_Last (T, Index); end if; T.Table (Index) := Item; end if; end Set_Item; -------------- -- Set_Last -- -------------- procedure Set_Last (T : in out Instance; New_Val : Table_Last_Type) is begin pragma Assert (not T.Locked); if New_Val > Last_Allocated (T) then Grow (T, New_Val); end if; T.P.Last := New_Val; end Set_Last; ---------------- -- Sort_Table -- ---------------- procedure Sort_Table (Table : in out Instance) is Temp : Table_Component_Type; -- A temporary position to simulate index 0 -- Local subprograms function Index_Of (Idx : Natural) return Table_Index_Type'Base; -- Return index of Idx'th element of table function Lower_Than (Op1, Op2 : Natural) return Boolean; -- Compare two components procedure Move (From : Natural; To : Natural); -- Move one component package Heap_Sort is new GNAT.Heap_Sort_G (Move, Lower_Than); -------------- -- Index_Of -- -------------- function Index_Of (Idx : Natural) return Table_Index_Type'Base is J : constant Integer'Base := Table_Index_Type'Base'Pos (First) + Idx - 1; begin return Table_Index_Type'Base'Val (J); end Index_Of; ---------- -- Move -- ---------- procedure Move (From : Natural; To : Natural) is begin if From = 0 then Table.Table (Index_Of (To)) := Temp; elsif To = 0 then Temp := Table.Table (Index_Of (From)); else Table.Table (Index_Of (To)) := Table.Table (Index_Of (From)); end if; end Move; ---------------- -- Lower_Than -- ---------------- function Lower_Than (Op1, Op2 : Natural) return Boolean is begin if Op1 = 0 then return Lt (Temp, Table.Table (Index_Of (Op2))); elsif Op2 = 0 then return Lt (Table.Table (Index_Of (Op1)), Temp); else return Lt (Table.Table (Index_Of (Op1)), Table.Table (Index_Of (Op2))); end if; end Lower_Than; -- Start of processing for Sort_Table begin Heap_Sort.Sort (Natural (Last (Table) - First) + 1); end Sort_Table; end GNAT.Dynamic_Tables;