--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/ada/libgnat/g-graphs.ads	Thu Feb 13 11:34:05 2020 +0900
@@ -0,0 +1,536 @@
+------------------------------------------------------------------------------
+--                                                                          --
+--                         GNAT RUN-TIME COMPONENTS                         --
+--                                                                          --
+--                           G N A T . G R A P H S                          --
+--                                                                          --
+--                                 S p e c                                  --
+--                                                                          --
+--             Copyright (C) 2018-2019, 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 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    --
+-- <http://www.gnu.org/licenses/>.                                          --
+--                                                                          --
+-- 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.Dynamic_HTables; use GNAT.Dynamic_HTables;
+with GNAT.Lists;           use GNAT.Lists;
+with GNAT.Sets;            use GNAT.Sets;
+
+package GNAT.Graphs is
+
+   ---------------
+   -- Component --
+   ---------------
+
+   --  The following type denotes a strongly connected component handle
+   --  (referred to as simply "component") in a graph.
+
+   type Component_Id is new Natural;
+   No_Component : constant Component_Id := Component_Id'First;
+
+   function Hash_Component (Comp : Component_Id) return Bucket_Range_Type;
+   --  Map component Comp into the range of buckets
+
+   function Present (Comp : Component_Id) return Boolean;
+   --  Determine whether component Comp exists
+
+   ---------------------
+   -- Directed_Graphs --
+   ---------------------
+
+   --  The following package offers a directed graph abstraction with the
+   --  following characteristics:
+   --
+   --    * Dynamic resizing based on number of vertices and edges
+   --    * Creation of multiple instances, of different sizes
+   --    * Discovery of strongly connected components
+   --    * Iterable attributes
+   --
+   --  The following use pattern must be employed when operating this graph:
+   --
+   --    Graph : Directed_Graph := Create (<some size>, <some size>);
+   --
+   --    <various operations>
+   --
+   --    Destroy (Graph);
+   --
+   --  The destruction of the graph reclaims all storage occupied by it.
+
+   generic
+
+      --------------
+      -- Vertices --
+      --------------
+
+      type Vertex_Id is private;
+      --  The handle of a vertex
+
+      No_Vertex : Vertex_Id;
+      --  An indicator for a nonexistent vertex
+
+      with function Hash_Vertex (V : Vertex_Id) return Bucket_Range_Type;
+      --  Map vertex V into the range of buckets
+
+      with function Same_Vertex
+             (Left  : Vertex_Id;
+              Right : Vertex_Id) return Boolean;
+      --  Compare vertex Left to vertex Right for identity
+
+      -----------
+      -- Edges --
+      -----------
+
+      type Edge_Id is private;
+      --  The handle of an edge
+
+      No_Edge : Edge_Id;
+      --  An indicator for a nonexistent edge
+
+      with function Hash_Edge (E : Edge_Id) return Bucket_Range_Type;
+      --  Map edge E into the range of buckets
+
+      with function Same_Edge
+             (Left  : Edge_Id;
+              Right : Edge_Id) return Boolean;
+      --  Compare edge Left to edge Right for identity
+
+   package Directed_Graphs is
+
+      --  The following exceptions are raised when an attempt is made to add
+      --  the same edge or vertex in a graph.
+
+      Duplicate_Edge   : exception;
+      Duplicate_Vertex : exception;
+
+      --  The following exceptions are raised when an attempt is made to delete
+      --  or reference a nonexistent component, edge, or vertex in a graph.
+
+      Missing_Component : exception;
+      Missing_Edge      : exception;
+      Missing_Vertex    : exception;
+
+      ----------------------
+      -- Graph operations --
+      ----------------------
+
+      --  The following type denotes a graph handle. Each instance must be
+      --  created using routine Create.
+
+      type Directed_Graph is private;
+      Nil : constant Directed_Graph;
+
+      procedure Add_Edge
+        (G           : Directed_Graph;
+         E           : Edge_Id;
+         Source      : Vertex_Id;
+         Destination : Vertex_Id);
+      --  Add edge E to graph G which links vertex source Source and desination
+      --  vertex Destination. The edge is "owned" by vertex Source. This action
+      --  raises the following exceptions:
+      --
+      --    * Duplicate_Edge, when the edge is already present in the graph
+      --
+      --    * Iterated, when the graph has an outstanding edge iterator
+      --
+      --    * Missing_Vertex, when either the source or desination are not
+      --      present in the graph.
+
+      procedure Add_Vertex
+        (G : Directed_Graph;
+         V : Vertex_Id);
+      --  Add vertex V to graph G. This action raises the following exceptions:
+      --
+      --    * Duplicate_Vertex, when the vertex is already present in the graph
+      --
+      --    * Iterated, when the graph has an outstanding vertex iterator
+
+      function Component
+        (G : Directed_Graph;
+         V : Vertex_Id) return Component_Id;
+      --  Obtain the component where vertex V of graph G resides. This action
+      --  raises the following exceptions:
+      --
+      --    * Missing_Vertex, when the vertex is not present in the graph
+
+      function Contains_Component
+        (G    : Directed_Graph;
+         Comp : Component_Id) return Boolean;
+      --  Determine whether graph G contains component Comp
+
+      function Contains_Edge
+        (G : Directed_Graph;
+         E : Edge_Id) return Boolean;
+      --  Determine whether graph G contains edge E
+
+      function Contains_Vertex
+        (G : Directed_Graph;
+         V : Vertex_Id) return Boolean;
+      --  Determine whether graph G contains vertex V
+
+      function Create
+        (Initial_Vertices : Positive;
+         Initial_Edges    : Positive) return Directed_Graph;
+      --  Create a new graph with vertex capacity Initial_Vertices and edge
+      --  capacity Initial_Edges. This routine must be called at the start of
+      --  a graph's lifetime.
+
+      procedure Delete_Edge
+        (G : Directed_Graph;
+         E : Edge_Id);
+      --  Delete edge E from graph G. This action raises these exceptions:
+      --
+      --    * Iterated, when the graph has an outstanding edge iterator
+      --
+      --    * Missing_Edge, when the edge is not present in the graph
+      --
+      --    * Missing_Vertex, when the source vertex that "owns" the edge is
+      --      not present in the graph.
+
+      function Destination_Vertex
+        (G : Directed_Graph;
+         E : Edge_Id) return Vertex_Id;
+      --  Obtain the destination vertex of edge E of graph G. This action
+      --  raises the following exceptions:
+      --
+      --    * Missing_Edge, when the edge is not present in the graph
+
+      procedure Destroy (G : in out Directed_Graph);
+      --  Destroy the contents of graph G, rendering it unusable. This routine
+      --  must be called at the end of a graph's lifetime. This action raises
+      --  the following exceptions:
+      --
+      --    * Iterated, if the graph has any outstanding iterator
+
+      procedure Find_Components (G : Directed_Graph);
+      --  Find all components of graph G. This action raises the following
+      --  exceptions:
+      --
+      --    * Iterated, when the components or vertices of the graph have an
+      --      outstanding iterator.
+
+      function Is_Empty (G : Directed_Graph) return Boolean;
+      --  Determine whether graph G is empty
+
+      function Number_Of_Component_Vertices
+        (G    : Directed_Graph;
+         Comp : Component_Id) return Natural;
+      --  Obtain the total number of vertices of component Comp of graph G
+
+      function Number_Of_Components (G : Directed_Graph) return Natural;
+      --  Obtain the total number of components of graph G
+
+      function Number_Of_Edges (G : Directed_Graph) return Natural;
+      --  Obtain the total number of edges of graph G
+
+      function Number_Of_Outgoing_Edges
+        (G : Directed_Graph;
+         V : Vertex_Id) return Natural;
+      --  Obtain the total number of outgoing edges of vertex V of graph G
+
+      function Number_Of_Vertices (G : Directed_Graph) return Natural;
+      --  Obtain the total number of vertices of graph G
+
+      function Present (G : Directed_Graph) return Boolean;
+      --  Determine whether graph G exists
+
+      function Source_Vertex
+        (G : Directed_Graph;
+         E : Edge_Id) return Vertex_Id;
+      --  Obtain the source vertex that "owns" edge E of graph G. This action
+      --  raises the following exceptions:
+      --
+      --    * Missing_Edge, when the edge is not present in the graph
+
+      -------------------------
+      -- Iterator operations --
+      -------------------------
+
+      --  The following types represent iterators over various attributes of a
+      --  graph. Each iterator locks all mutation operations of its associated
+      --  attribute, and unlocks them once it is exhausted. The iterators must
+      --  be used with the following pattern:
+      --
+      --    Iter : Iterate_XXX (Graph);
+      --    while Has_Next (Iter) loop
+      --       Next (Iter, Element);
+      --    end loop;
+      --
+      --  It is possible to advance the iterators by using Next only, however
+      --  this risks raising Iterator_Exhausted.
+
+      --  The following type represents an iterator over all edges of a graph
+
+      type All_Edge_Iterator is private;
+
+      function Has_Next (Iter : All_Edge_Iterator) return Boolean;
+      --  Determine whether iterator Iter has more edges to examine
+
+      function Iterate_All_Edges (G : Directed_Graph) return All_Edge_Iterator;
+      --  Obtain an iterator over all edges of graph G
+
+      procedure Next
+        (Iter : in out All_Edge_Iterator;
+         E    : out Edge_Id);
+      --  Return the current edge referenced by iterator Iter and advance to
+      --  the next available edge. This action raises the following exceptions:
+      --
+      --    * Iterator_Exhausted, when the iterator has been exhausted and
+      --      further attempts are made to advance it.
+
+      --  The following type represents an iterator over all vertices of a
+      --  graph.
+
+      type All_Vertex_Iterator is private;
+
+      function Has_Next (Iter : All_Vertex_Iterator) return Boolean;
+      --  Determine whether iterator Iter has more vertices to examine
+
+      function Iterate_All_Vertices
+        (G : Directed_Graph) return All_Vertex_Iterator;
+      --  Obtain an iterator over all vertices of graph G
+
+      procedure Next
+        (Iter : in out All_Vertex_Iterator;
+         V    : out Vertex_Id);
+      --  Return the current vertex referenced by iterator Iter and advance
+      --  to the next available vertex. This action raises the following
+      --  exceptions:
+      --
+      --    * Iterator_Exhausted, when the iterator has been exhausted and
+      --      further attempts are made to advance it.
+
+      --  The following type represents an iterator over all components of a
+      --  graph.
+
+      type Component_Iterator is private;
+
+      function Has_Next (Iter : Component_Iterator) return Boolean;
+      --  Determine whether iterator Iter has more components to examine
+
+      function Iterate_Components
+        (G : Directed_Graph) return Component_Iterator;
+      --  Obtain an iterator over all components of graph G
+
+      procedure Next
+        (Iter : in out Component_Iterator;
+         Comp : out Component_Id);
+      --  Return the current component referenced by iterator Iter and advance
+      --  to the next component. This action raises the following exceptions:
+      --
+      --    * Iterator_Exhausted, when the iterator has been exhausted and
+      --      further attempts are made to advance it.
+
+      --  The following type prepresents an iterator over all vertices of a
+      --  component.
+
+      type Component_Vertex_Iterator is private;
+
+      function Has_Next (Iter : Component_Vertex_Iterator) return Boolean;
+      --  Determine whether iterator Iter has more vertices to examine
+
+      function Iterate_Component_Vertices
+        (G    : Directed_Graph;
+         Comp : Component_Id) return Component_Vertex_Iterator;
+      --  Obtain an iterator over all vertices that comprise component Comp of
+      --  graph G.
+
+      procedure Next
+        (Iter : in out Component_Vertex_Iterator;
+         V    : out Vertex_Id);
+      --  Return the current vertex referenced by iterator Iter and advance to
+      --  the next vertex. This action raises the following exceptions:
+      --
+      --    * Iterator_Exhausted, when the iterator has been exhausted and
+      --      further attempts are made to advance it.
+
+      --  The following type represents an iterator over all outgoing edges of
+      --  a vertex.
+
+      type Outgoing_Edge_Iterator is private;
+
+      function Has_Next (Iter : Outgoing_Edge_Iterator) return Boolean;
+      --  Determine whether iterator Iter has more outgoing edges to examine
+
+      function Iterate_Outgoing_Edges
+        (G : Directed_Graph;
+         V : Vertex_Id) return Outgoing_Edge_Iterator;
+      --  Obtain an iterator over all the outgoing edges "owned" by vertex V of
+      --  graph G.
+
+      procedure Next
+        (Iter : in out Outgoing_Edge_Iterator;
+         E    : out Edge_Id);
+      --  Return the current outgoing edge referenced by iterator Iter and
+      --  advance to the next available outgoing edge. This action raises the
+      --  following exceptions:
+      --
+      --    * Iterator_Exhausted, when the iterator has been exhausted and
+      --      further attempts are made to advance it.
+
+   private
+      pragma Unreferenced (No_Edge);
+
+      --------------
+      -- Edge_Map --
+      --------------
+
+      type Edge_Attributes is record
+         Destination : Vertex_Id := No_Vertex;
+         --  The target of a directed edge
+
+         Source : Vertex_Id := No_Vertex;
+         --  The origin of a directed edge. The source vertex "owns" the edge.
+      end record;
+
+      No_Edge_Attributes : constant Edge_Attributes :=
+        (Destination => No_Vertex,
+         Source      => No_Vertex);
+
+      procedure Destroy_Edge_Attributes (Attrs : in out Edge_Attributes);
+      --  Destroy the contents of attributes Attrs
+
+      package Edge_Map is new Dynamic_Hash_Tables
+        (Key_Type              => Edge_Id,
+         Value_Type            => Edge_Attributes,
+         No_Value              => No_Edge_Attributes,
+         Expansion_Threshold   => 1.5,
+         Expansion_Factor      => 2,
+         Compression_Threshold => 0.3,
+         Compression_Factor    => 2,
+         "="                   => Same_Edge,
+         Destroy_Value         => Destroy_Edge_Attributes,
+         Hash                  => Hash_Edge);
+
+      --------------
+      -- Edge_Set --
+      --------------
+
+      package Edge_Set is new Membership_Sets
+        (Element_Type => Edge_Id,
+         "="          => "=",
+         Hash         => Hash_Edge);
+
+      -----------------
+      -- Vertex_List --
+      -----------------
+
+      procedure Destroy_Vertex (V : in out Vertex_Id);
+      --  Destroy the contents of a vertex
+
+      package Vertex_List is new Doubly_Linked_Lists
+        (Element_Type    => Vertex_Id,
+         "="             => Same_Vertex,
+         Destroy_Element => Destroy_Vertex);
+
+      ----------------
+      -- Vertex_Map --
+      ----------------
+
+      type Vertex_Attributes is record
+         Component : Component_Id := No_Component;
+         --  The component where a vertex lives
+
+         Outgoing_Edges : Edge_Set.Membership_Set := Edge_Set.Nil;
+         --  The set of edges that extend out from a vertex
+      end record;
+
+      No_Vertex_Attributes : constant Vertex_Attributes :=
+        (Component      => No_Component,
+         Outgoing_Edges => Edge_Set.Nil);
+
+      procedure Destroy_Vertex_Attributes (Attrs : in out Vertex_Attributes);
+      --  Destroy the contents of attributes Attrs
+
+      package Vertex_Map is new Dynamic_Hash_Tables
+        (Key_Type              => Vertex_Id,
+         Value_Type            => Vertex_Attributes,
+         No_Value              => No_Vertex_Attributes,
+         Expansion_Threshold   => 1.5,
+         Expansion_Factor      => 2,
+         Compression_Threshold => 0.3,
+         Compression_Factor    => 2,
+         "="                   => Same_Vertex,
+         Destroy_Value         => Destroy_Vertex_Attributes,
+         Hash                  => Hash_Vertex);
+
+      -------------------
+      -- Component_Map --
+      -------------------
+
+      type Component_Attributes is record
+         Vertices : Vertex_List.Doubly_Linked_List := Vertex_List.Nil;
+      end record;
+
+      No_Component_Attributes : constant Component_Attributes :=
+        (Vertices => Vertex_List.Nil);
+
+      procedure Destroy_Component_Attributes
+        (Attrs : in out Component_Attributes);
+      --  Destroy the contents of attributes Attrs
+
+      package Component_Map is new Dynamic_Hash_Tables
+        (Key_Type              => Component_Id,
+         Value_Type            => Component_Attributes,
+         No_Value              => No_Component_Attributes,
+         Expansion_Threshold   => 1.5,
+         Expansion_Factor      => 2,
+         Compression_Threshold => 0.3,
+         Compression_Factor    => 2,
+         "="                   => "=",
+         Destroy_Value         => Destroy_Component_Attributes,
+         Hash                  => Hash_Component);
+
+      -----------
+      -- Graph --
+      -----------
+
+      type Directed_Graph_Attributes is record
+         All_Edges : Edge_Map.Dynamic_Hash_Table := Edge_Map.Nil;
+         --  The map of edge -> edge attributes for all edges in the graph
+
+         All_Vertices : Vertex_Map.Dynamic_Hash_Table := Vertex_Map.Nil;
+         --  The map of vertex -> vertex attributes for all vertices in the
+         --  graph.
+
+         Components : Component_Map.Dynamic_Hash_Table := Component_Map.Nil;
+         --  The map of component -> component attributes for all components
+         --  in the graph.
+      end record;
+
+      type Directed_Graph is access Directed_Graph_Attributes;
+      Nil : constant Directed_Graph := null;
+
+      ---------------
+      -- Iterators --
+      ---------------
+
+      type All_Edge_Iterator         is new Edge_Map.Iterator;
+      type All_Vertex_Iterator       is new Vertex_Map.Iterator;
+      type Component_Iterator        is new Component_Map.Iterator;
+      type Component_Vertex_Iterator is new Vertex_List.Iterator;
+      type Outgoing_Edge_Iterator    is new Edge_Set.Iterator;
+   end Directed_Graphs;
+
+private
+   First_Component : constant Component_Id := No_Component + 1;
+
+end GNAT.Graphs;