------------------------------------------------------------------------------
--                                                                          --
--                         GNAT COMPILER COMPONENTS                         --
--                                                                          --
--                             S E M _ M A P S                              --
--                                                                          --
--                                 B o d y                                  --
--                                                                          --
--          Copyright (C) 1996-2005, Free Software Foundation, Inc.         --
--                                                                          --
-- 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 2,  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.  See the GNU General Public License --
-- for  more details.  You should have  received  a copy of the GNU General --
-- Public License  distributed with GNAT;  see file COPYING.  If not, write --
-- to  the  Free Software Foundation,  51  Franklin  Street,  Fifth  Floor, --
-- Boston, MA 02110-1301, USA.                                              --
--                                                                          --
-- GNAT was originally developed  by the GNAT team at  New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc.      --
--                                                                          --
------------------------------------------------------------------------------

with Atree;  use Atree;
with Einfo;  use Einfo;
with Namet;  use Namet;
with Output; use Output;
with Sinfo;  use Sinfo;
with Uintp;  use Uintp;

package body Sem_Maps is

   -----------------------
   -- Local Subprograms --
   -----------------------

   function Find_Assoc (M : Map; E : Entity_Id) return Assoc_Index;
   --  Standard hash table search. M is the map to be searched, E is the
   --  entity to be searched for, and Assoc_Index is the resulting
   --  association, or is set to No_Assoc if there is no association.

   function Find_Header_Size (N : Int) return Header_Index;
   --  Find largest power of two smaller than the number of entries in
   --  the table. This load factor of 2 may be adjusted later if needed.

   procedure Write_Map (E : Entity_Id);
   pragma Warnings (Off, Write_Map);
   --  For debugging purposes

   ---------------------
   -- Add_Association --
   ---------------------

   procedure Add_Association
   --  LLVM local
     (M    : Map;
      O_Id : Entity_Id;
      N_Id : Entity_Id;
      Kind : Scope_Kind := S_Local)
   is
      Info : constant Map_Info      := Maps_Table.Table (M);
      Offh : constant Header_Index  := Info.Header_Offset;
      Offs : constant Header_Index  := Info.Header_Num;
      J    : constant Header_Index  := Header_Index (O_Id) mod Offs;
      K    : constant Assoc_Index   := Info.Assoc_Next;

   begin
      Associations_Table.Table (K) := (O_Id, N_Id, Kind, No_Assoc);
      Maps_Table.Table (M).Assoc_Next := K + 1;

      if Headers_Table.Table (Offh + J) /= No_Assoc then

         --  Place new association at head of chain

         Associations_Table.Table (K).Next := Headers_Table.Table (Offh + J);
      end if;

      Headers_Table.Table (Offh + J) := K;
   end Add_Association;

   ------------------------
   -- Build_Instance_Map --
   ------------------------

   function Build_Instance_Map (M : Map) return Map is
      Info    : constant Map_Info     := Maps_Table.Table (M);
      Res     : constant Map          := New_Map (Int (Info.Assoc_Num));
      Offh1   : constant Header_Index := Info.Header_Offset;
      Offa1   : constant Assoc_Index  := Info.Assoc_Offset;
      Offh2   : constant Header_Index := Maps_Table.Table (Res).Header_Offset;
      Offa2   : constant Assoc_Index  := Maps_Table.Table (Res).Assoc_Offset;
      A       : Assoc;
      A_Index : Assoc_Index;

   begin
      for J in 0 .. Info.Header_Num - 1 loop
         A_Index := Headers_Table.Table (Offh1 + J);

         if A_Index /= No_Assoc then
            Headers_Table.Table (Offh2 + J) := A_Index + (Offa2 - Offa1);
         end if;
      end loop;

      for J in 0 .. Info.Assoc_Num - 1 loop
         A  := Associations_Table.Table (Offa1 + J);

         --  For local entities that come from source, create the
         --  corresponding local entities in the instance. Entities that
         --  do not come from source are etypes, and new ones will be
         --  generated when analyzing the instance.

         if No (A.New_Id)
           and then A.Kind = S_Local
           and then Comes_From_Source (A.Old_Id)
         then
            A.New_Id := New_Copy (A.Old_Id);
            A.New_Id := New_Entity (Nkind (A.Old_Id), Sloc (A.Old_Id));
            Set_Chars (A.New_Id, Chars (A.Old_Id));
         end if;

         if A.Next /= No_Assoc then
            A.Next := A.Next + (Offa2 - Offa1);
         end if;

         Associations_Table.Table (Offa2 + J) := A;
      end loop;

      Maps_Table.Table (Res).Assoc_Next := Associations_Table.Last;
      return Res;
   end Build_Instance_Map;

   -------------
   -- Compose --
   -------------

   function Compose (Orig_Map : Map; New_Map : Map) return Map is
      Res : constant Map         := Copy (Orig_Map);
      Off : constant Assoc_Index := Maps_Table.Table (Res).Assoc_Offset;
      A   : Assoc;
      K   : Assoc_Index;

   begin
      --  Iterate over the contents of Orig_Map, looking for entities
      --  that are further mapped under New_Map.

      for J in 0 .. Maps_Table.Table (Res).Assoc_Num - 1  loop
         A := Associations_Table.Table (Off + J);
         K := Find_Assoc (New_Map, A.New_Id);

         if K /= No_Assoc then
            Associations_Table.Table (Off + J).New_Id
              := Associations_Table.Table (K).New_Id;
         end if;
      end loop;

      return Res;
   end Compose;

   ----------
   -- Copy --
   ----------

   function Copy (M : Map) return Map is
      Info    : constant Map_Info     := Maps_Table.Table (M);
      Res     : constant Map          := New_Map (Int (Info.Assoc_Num));
      Offh1   : constant Header_Index := Info.Header_Offset;
      Offa1   : constant Assoc_Index  := Info.Assoc_Offset;
      Offh2   : constant Header_Index := Maps_Table.Table (Res).Header_Offset;
      Offa2   : constant Assoc_Index  := Maps_Table.Table (Res).Assoc_Offset;
      A       : Assoc;
      A_Index : Assoc_Index;

   begin
      for J in 0 .. Info.Header_Num - 1 loop
         A_Index := Headers_Table.Table (Offh1 + J) + (Offa2 - Offa1);

         if A_Index /= No_Assoc then
            Headers_Table.Table (Offh2 + J) := A_Index + (Offa2 - Offa1);
         end if;
      end loop;

      for J in 0 .. Info.Assoc_Num - 1 loop
         A := Associations_Table.Table (Offa1 + J);
         A.Next := A.Next + (Offa2 - Offa1);
         Associations_Table.Table (Offa2 + J) := A;
      end loop;

      Maps_Table.Table (Res).Assoc_Next := Associations_Table.Last;
      return Res;
   end Copy;

   ----------------
   -- Find_Assoc --
   ----------------

   function Find_Assoc (M : Map; E : Entity_Id) return Assoc_Index is
      Offh    : constant Header_Index := Maps_Table.Table (M).Header_Offset;
      Offs    : constant Header_Index := Maps_Table.Table (M).Header_Num;
      J       : constant Header_Index := Header_Index (E) mod Offs;
      A       : Assoc;
      A_Index : Assoc_Index;

   begin
      A_Index := Headers_Table.Table (Offh + J);

      if A_Index = No_Assoc then
         return A_Index;

      else
         A := Associations_Table.Table (A_Index);

         while Present (A.Old_Id) loop

            if A.Old_Id = E then
               return A_Index;

            elsif A.Next = No_Assoc then
               return No_Assoc;

            else
               A_Index := A.Next;
               A := Associations_Table.Table (A.Next);
            end if;
         end loop;

         return No_Assoc;
      end if;
   end Find_Assoc;

   ----------------------
   -- Find_Header_Size --
   ----------------------

   function Find_Header_Size (N : Int) return Header_Index is
      Siz : Header_Index;

   begin
      Siz := 2;
      while 2 * Siz < Header_Index (N) loop
         Siz := 2 * Siz;
      end loop;

      return Siz;
   end Find_Header_Size;

   ------------
   -- Lookup --
   ------------

   function Lookup (M : Map; E : Entity_Id) return Entity_Id is
      Offh : constant Header_Index := Maps_Table.Table (M).Header_Offset;
      Offs : constant Header_Index := Maps_Table.Table (M).Header_Num;
      J    : constant Header_Index := Header_Index (E) mod Offs;
      A    : Assoc;

   begin
      if Headers_Table.Table (Offh + J) = No_Assoc then
         return Empty;

      else
         A := Associations_Table.Table (Headers_Table.Table (Offh + J));

         while Present (A.Old_Id) loop

            if A.Old_Id = E then
               return A.New_Id;

            elsif A.Next = No_Assoc then
               return Empty;

            else
               A := Associations_Table.Table (A.Next);
            end if;
         end loop;

         return Empty;
      end if;
   end Lookup;

   -------------
   -- New_Map --
   -------------

   function New_Map (Num_Assoc : Int) return Map is
      Header_Size : constant Header_Index := Find_Header_Size (Num_Assoc);
      Res         : Map_Info;

   begin
      --  Allocate the tables for the new map at the current end of the
      --  global tables.

      Associations_Table.Increment_Last;
      Headers_Table.Increment_Last;
      Maps_Table.Increment_Last;

      Res.Header_Offset := Headers_Table.Last;
      Res.Header_Num    := Header_Size;
      Res.Assoc_Offset  := Associations_Table.Last;
      Res.Assoc_Next    := Associations_Table.Last;
      Res.Assoc_Num     := Assoc_Index (Num_Assoc);

      Headers_Table.Set_Last (Headers_Table.Last + Header_Size);
      Associations_Table.Set_Last
        (Associations_Table.Last + Assoc_Index (Num_Assoc));
      Maps_Table.Table (Maps_Table.Last) := Res;

      for J in 1 .. Header_Size loop
         Headers_Table.Table (Headers_Table.Last - J) := No_Assoc;
      end loop;

      return Maps_Table.Last;
   end New_Map;

   ------------------------
   -- Update_Association --
   ------------------------

   procedure Update_Association
   --  LLVM local
     (M    : Map;
      O_Id : Entity_Id;
      N_Id : Entity_Id;
      Kind : Scope_Kind := S_Local)
   is
      J : constant Assoc_Index := Find_Assoc (M, O_Id);

   begin
      Associations_Table.Table (J).New_Id := N_Id;
      Associations_Table.Table (J).Kind := Kind;
   end Update_Association;

   ---------------
   -- Write_Map --
   ---------------

   procedure Write_Map (E : Entity_Id) is
      M    : constant Map          := Map (UI_To_Int (Renaming_Map (E)));
      Info : constant Map_Info     := Maps_Table.Table (M);
      Offh : constant Header_Index := Info.Header_Offset;
      Offa : constant Assoc_Index  := Info.Assoc_Offset;
      A    : Assoc;

   begin
      Write_Str ("Size : ");
      Write_Int (Int (Info.Assoc_Num));
      Write_Eol;

      Write_Str ("Headers");
      Write_Eol;

      for J in 0 .. Info.Header_Num - 1 loop
         Write_Int (Int (Offh + J));
         Write_Str (" : ");
         Write_Int (Int (Headers_Table.Table (Offh + J)));
         Write_Eol;
      end loop;

      for J in 0 .. Info.Assoc_Num - 1 loop
         A := Associations_Table.Table (Offa + J);
         Write_Int (Int (Offa + J));
         Write_Str (" : ");
         Write_Name (Chars (A.Old_Id));
         Write_Str ("  ");
         Write_Int (Int (A.Old_Id));
         Write_Str (" ==> ");
         Write_Int (Int (A.New_Id));
         Write_Str (" next = ");
         Write_Int (Int (A.Next));
         Write_Eol;
      end loop;
   end Write_Map;

end Sem_Maps;