[Ada] General purpose doubly linked list for compiler and tool use

This patch adds unit GNAT.Lists which currently contains the
implementation of a general purpose doubly linked list intended for use
by the compiler and the tools around it.

2018-08-21  Hristian Kirtchev  <kirtchev@adacore.com>

gcc/ada/

	* impunit.adb: Add g-lists to the set of non-implementation
	units.
	* libgnat/g-lists.adb, libgnat/g-lists.ads: New unit.
	* Makefile.rtl: Add g-lists to the set of non-tasking units.
	* gcc-interface/Make-lang.in: Add g-lists to the set of files
	used by gnat1.

gcc/testsuite/

	* gnat.dg/linkedlist.adb: New testcase.

From-SVN: r263714

6 files changed, 892 insertions, 0 deletions

diff --git a/gcc/ada/ChangeLog b/gcc/ada/ChangeLog
index d90f01a..f21b11c 100644
--- a/gcc/ada/ChangeLog
+++ b/gcc/ada/ChangeLog
@@ -1,3 +1,12 @@
+2018-08-21  Hristian Kirtchev  <kirtchev@adacore.com>
+
+	* impunit.adb: Add g-lists to the set of non-implementation
+	units.
+	* libgnat/g-lists.adb, libgnat/g-lists.ads: New unit.
+	* Makefile.rtl: Add g-lists to the set of non-tasking units.
+	* gcc-interface/Make-lang.in: Add g-lists to the set of files
+	used by gnat1.
+
 2018-08-21  Ed Schonberg  <schonberg@adacore.com>
 
 	* exp_ch9.adb (Reset_Scopes): Do not recurse into type
diff --git a/gcc/ada/Makefile.rtl b/gcc/ada/Makefile.rtl
index 7eaa9ba..2e4ee8d 100644
--- a/gcc/ada/Makefile.rtl
+++ b/gcc/ada/Makefile.rtl
@@ -427,6 +427,7 @@ GNATRTL_NONTASKING_OBJS= \
   g-htable$(objext) \
   g-io$(objext) \
   g-io_aux$(objext) \
+  g-lists$(objext) \
   g-locfil$(objext) \
   g-mbdira$(objext) \
   g-mbflra$(objext) \
diff --git a/gcc/ada/gcc-interface/Make-lang.in b/gcc/ada/gcc-interface/Make-lang.in
index d51d397..d8dac73 100644
--- a/gcc/ada/gcc-interface/Make-lang.in
+++ b/gcc/ada/gcc-interface/Make-lang.in
@@ -319,6 +319,7 @@ GNAT_ADA_OBJS =	\
  ada/libgnat/g-dynhta.o	\
  ada/libgnat/g-hesora.o	\
  ada/libgnat/g-htable.o	\
+ ada/libgnat/g-lists.o \
  ada/libgnat/g-spchge.o	\
  ada/libgnat/g-speche.o	\
  ada/libgnat/g-u3spch.o	\
diff --git a/gcc/ada/impunit.adb b/gcc/ada/impunit.adb
index cfa1d5e..7d35902 100644
--- a/gcc/ada/impunit.adb
+++ b/gcc/ada/impunit.adb
@@ -281,6 +281,7 @@ package body Impunit is
     ("g-htable", F),  -- GNAT.Htable
     ("g-io    ", F),  -- GNAT.IO
     ("g-io_aux", F),  -- GNAT.IO_Aux
+    ("g-lists ", F),  -- GNAT.Lists
     ("g-locfil", F),  -- GNAT.Lock_Files
     ("g-mbdira", F),  -- GNAT.MBBS_Discrete_Random
     ("g-mbflra", F),  -- GNAT.MBBS_Float_Random
diff --git a/gcc/ada/libgnat/g-lists.adb b/gcc/ada/libgnat/g-lists.adb
new file mode 100644
index 0000000..a058f33
--- /dev/null
+++ b/gcc/ada/libgnat/g-lists.adb
@@ -0,0 +1,635 @@
+------------------------------------------------------------------------------
+--                                                                          --
+--                         GNAT RUN-TIME COMPONENTS                         --
+--                                                                          --
+--                            G N A T . L I S T S                           --
+--                                                                          --
+--                                 B o d y                                  --
+--                                                                          --
+--             Copyright (C) 2018, 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.      --
+--                                                                          --
+------------------------------------------------------------------------------
+
+with Ada.Unchecked_Deallocation;
+
+package body GNAT.Lists is
+
+   package body Doubly_Linked_List is
+      procedure Delete_Node (L : Instance; Nod : Node_Ptr);
+      pragma Inline (Delete_Node);
+      --  Detach and delete node Nod from list L
+
+      procedure Ensure_Circular (Head : Node_Ptr);
+      pragma Inline (Ensure_Circular);
+      --  Ensure that dummy head Head is circular with respect to itself
+
+      procedure Ensure_Created (L : Instance);
+      pragma Inline (Ensure_Created);
+      --  Verify that list L is created. Raise Not_Created if this is not the
+      --  case.
+
+      procedure Ensure_Full (L : Instance);
+      pragma Inline (Ensure_Full);
+      --  Verify that list L contains at least one element. Raise List_Empty if
+      --  this is not the case.
+
+      procedure Ensure_Unlocked (L : Instance);
+      pragma Inline (Ensure_Unlocked);
+      --  Verify that list L is unlocked. Raise List_Locked if this is not the
+      --  case.
+
+      function Find_Node
+        (Head : Node_Ptr;
+         Elem : Element_Type) return Node_Ptr;
+      pragma Inline (Find_Node);
+      --  Travers a list indicated by dummy head Head to determine whethe there
+      --  exists a node with element Elem. If such a node exists, return it,
+      --  otherwise return null;
+
+      procedure Free is new Ada.Unchecked_Deallocation (Linked_List, Instance);
+
+      procedure Free is new Ada.Unchecked_Deallocation (Node, Node_Ptr);
+
+      procedure Insert_Between
+        (L     : Instance;
+         Elem  : Element_Type;
+         Left  : Node_Ptr;
+         Right : Node_Ptr);
+      pragma Inline (Insert_Between);
+      --  Insert element Elem between nodes Left and Right of list L
+
+      function Is_Valid (Iter : Iterator) return Boolean;
+      pragma Inline (Is_Valid);
+      --  Determine whether iterator Iter refers to a valid element
+
+      function Is_Valid (Nod : Node_Ptr; Head : Node_Ptr) return Boolean;
+      pragma Inline (Is_Valid);
+      --  Determine whether node Nod is non-null and does not refer to dummy
+      --  head Head, thus making it valid.
+
+      procedure Lock (L : Instance);
+      pragma Inline (Lock);
+      --  Lock all mutation functionality of list L
+
+      procedure Unlock (L : Instance);
+      pragma Inline (Unlock);
+      --  Unlock all mutation functionality of list L
+
+      ------------
+      -- Append --
+      ------------
+
+      procedure Append (L : Instance; Elem : Element_Type) is
+         Head : Node_Ptr;
+
+      begin
+         Ensure_Created  (L);
+         Ensure_Unlocked (L);
+
+         --  Ensure that the dummy head of an empty list is circular with
+         --  respect to itself.
+
+         Head := L.Nodes'Access;
+         Ensure_Circular (Head);
+
+         --  Append the node by inserting it between the last node and the
+         --  dummy head.
+
+         Insert_Between
+           (L     => L,
+            Elem  => Elem,
+            Left  => Head.Prev,
+            Right => Head);
+      end Append;
+
+      ------------
+      -- Create --
+      ------------
+
+      function Create return Instance is
+      begin
+         return new Linked_List;
+      end Create;
+
+      --------------
+      -- Contains --
+      --------------
+
+      function Contains (L : Instance; Elem : Element_Type) return Boolean is
+         Head : Node_Ptr;
+         Nod  : Node_Ptr;
+
+      begin
+         Ensure_Created (L);
+
+         Head := L.Nodes'Access;
+         Nod  := Find_Node (Head, Elem);
+
+         return Is_Valid (Nod, Head);
+      end Contains;
+
+      ------------
+      -- Delete --
+      ------------
+
+      procedure Delete (L : Instance; Elem : Element_Type) is
+         Head : Node_Ptr;
+         Nod  : Node_Ptr;
+
+      begin
+         Ensure_Created  (L);
+         Ensure_Full     (L);
+         Ensure_Unlocked (L);
+
+         Head := L.Nodes'Access;
+         Nod  := Find_Node (Head, Elem);
+
+         if Is_Valid (Nod, Head) then
+            Delete_Node (L, Nod);
+         end if;
+      end Delete;
+
+      ------------------
+      -- Delete_First --
+      ------------------
+
+      procedure Delete_First (L : Instance) is
+         Head : Node_Ptr;
+         Nod  : Node_Ptr;
+
+      begin
+         Ensure_Created  (L);
+         Ensure_Full     (L);
+         Ensure_Unlocked (L);
+
+         Head := L.Nodes'Access;
+         Nod  := Head.Next;
+
+         if Is_Valid (Nod, Head) then
+            Delete_Node (L, Nod);
+         end if;
+      end Delete_First;
+
+      -----------------
+      -- Delete_Last --
+      -----------------
+
+      procedure Delete_Last (L : Instance) is
+         Head : Node_Ptr;
+         Nod  : Node_Ptr;
+
+      begin
+         Ensure_Created  (L);
+         Ensure_Full     (L);
+         Ensure_Unlocked (L);
+
+         Head := L.Nodes'Access;
+         Nod  := Head.Prev;
+
+         if Is_Valid (Nod, Head) then
+            Delete_Node (L, Nod);
+         end if;
+      end Delete_Last;
+
+      -----------------
+      -- Delete_Node --
+      -----------------
+
+      procedure Delete_Node (L : Instance; Nod : Node_Ptr) is
+         Ref : Node_Ptr := Nod;
+
+         pragma Assert (Ref /= null);
+
+         Next : constant Node_Ptr := Ref.Next;
+         Prev : constant Node_Ptr := Ref.Prev;
+
+      begin
+         pragma Assert (L    /= null);
+         pragma Assert (Next /= null);
+         pragma Assert (Prev /= null);
+
+         Prev.Next := Next;  --  Prev ---> Next
+         Next.Prev := Prev;  --  Prev <--> Next
+
+         Ref.Next := null;
+         Ref.Prev := null;
+
+         L.Elements := L.Elements - 1;
+
+         Free (Ref);
+      end Delete_Node;
+
+      -------------
+      -- Destroy --
+      -------------
+
+      procedure Destroy (L : in out Instance) is
+         Head : Node_Ptr;
+
+      begin
+         Ensure_Created  (L);
+         Ensure_Unlocked (L);
+
+         Head := L.Nodes'Access;
+
+         while Is_Valid (Head.Next, Head) loop
+            Delete_Node (L, Head.Next);
+         end loop;
+
+         Free (L);
+      end Destroy;
+
+      ---------------------
+      -- Ensure_Circular --
+      ---------------------
+
+      procedure Ensure_Circular (Head : Node_Ptr) is
+         pragma Assert (Head /= null);
+
+      begin
+         if Head.Next = null and then Head.Prev = null then
+            Head.Next := Head;
+            Head.Prev := Head;
+         end if;
+      end Ensure_Circular;
+
+      --------------------
+      -- Ensure_Created --
+      --------------------
+
+      procedure Ensure_Created (L : Instance) is
+      begin
+         if L = null then
+            raise Not_Created;
+         end if;
+      end Ensure_Created;
+
+      -----------------
+      -- Ensure_Full --
+      -----------------
+
+      procedure Ensure_Full (L : Instance) is
+      begin
+         pragma Assert (L /= null);
+
+         if L.Elements = 0 then
+            raise List_Empty;
+         end if;
+      end Ensure_Full;
+
+      ---------------------
+      -- Ensure_Unlocked --
+      ---------------------
+
+      procedure Ensure_Unlocked (L : Instance) is
+      begin
+         pragma Assert (L /= null);
+
+         --  The list has at least one outstanding iterator
+
+         if L.Locked > 0 then
+            raise List_Locked;
+         end if;
+      end Ensure_Unlocked;
+
+      ---------------
+      -- Find_Node --
+      ---------------
+
+      function Find_Node
+        (Head : Node_Ptr;
+         Elem : Element_Type) return Node_Ptr
+      is
+         pragma Assert (Head /= null);
+
+         Nod : Node_Ptr;
+
+      begin
+         --  Traverse the nodes of the list, looking for a matching element
+
+         Nod := Head.Next;
+         while Is_Valid (Nod, Head) loop
+            if Nod.Elem = Elem then
+               return Nod;
+            end if;
+
+            Nod := Nod.Next;
+         end loop;
+
+         return null;
+      end Find_Node;
+
+      -----------
+      -- First --
+      -----------
+
+      function First (L : Instance) return Element_Type is
+      begin
+         Ensure_Created (L);
+         Ensure_Full    (L);
+
+         return L.Nodes.Next.Elem;
+      end First;
+
+      --------------
+      -- Has_Next --
+      --------------
+
+      function Has_Next (Iter : Iterator) return Boolean is
+         Is_OK : constant Boolean := Is_Valid (Iter);
+
+      begin
+         --  The iterator is no longer valid which indicates that it has been
+         --  exhausted. Unlock all mutation functionality of the list because
+         --  the iterator cannot be advanced any further.
+
+         if not Is_OK then
+            Unlock (Iter.List);
+         end if;
+
+         return Is_OK;
+      end Has_Next;
+
+      ------------------
+      -- Insert_After --
+      ------------------
+
+      procedure Insert_After
+        (L     : Instance;
+         After : Element_Type;
+         Elem  : Element_Type)
+      is
+         Head : Node_Ptr;
+         Nod  : Node_Ptr;
+
+      begin
+         Ensure_Created  (L);
+         Ensure_Unlocked (L);
+
+         Head := L.Nodes'Access;
+         Nod  := Find_Node (Head, After);
+
+         if Is_Valid (Nod, Head) then
+            Insert_Between
+              (L     => L,
+               Elem  => Elem,
+               Left  => Nod,
+               Right => Nod.Next);
+         end if;
+      end Insert_After;
+
+      -------------------
+      -- Insert_Before --
+      -------------------
+
+      procedure Insert_Before
+        (L      : Instance;
+         Before : Element_Type;
+         Elem   : Element_Type)
+      is
+         Head : Node_Ptr;
+         Nod  : Node_Ptr;
+
+      begin
+         Ensure_Created  (L);
+         Ensure_Unlocked (L);
+
+         Head := L.Nodes'Access;
+         Nod  := Find_Node (Head, Before);
+
+         if Is_Valid (Nod, Head) then
+            Insert_Between
+              (L     => L,
+               Elem  => Elem,
+               Left  => Nod.Prev,
+               Right => Nod);
+         end if;
+      end Insert_Before;
+
+      --------------------
+      -- Insert_Between --
+      --------------------
+
+      procedure Insert_Between
+        (L     : Instance;
+         Elem  : Element_Type;
+         Left  : Node_Ptr;
+         Right : Node_Ptr)
+      is
+         pragma Assert (L     /= null);
+         pragma Assert (Left  /= null);
+         pragma Assert (Right /= null);
+
+         Nod : constant Node_Ptr :=
+                 new Node'(Elem => Elem,
+                           Next => Right,  --  Left      Nod ---> Right
+                           Prev => Left);  --  Left <--- Nod ---> Right
+
+      begin
+         Left.Next  := Nod;                --  Left <--> Nod ---> Right
+         Right.Prev := Nod;                --  Left <--> Nod <--> Right
+
+         L.Elements := L.Elements + 1;
+      end Insert_Between;
+
+      --------------
+      -- Is_Empty --
+      --------------
+
+      function Is_Empty (L : Instance) return Boolean is
+      begin
+         Ensure_Created (L);
+
+         return L.Elements = 0;
+      end Is_Empty;
+
+      --------------
+      -- Is_Valid --
+      --------------
+
+      function Is_Valid (Iter : Iterator) return Boolean is
+      begin
+         --  The invariant of Iterate and Next ensures that the iterator always
+         --  refers to a valid node if there exists one.
+
+         return Is_Valid (Iter.Nod, Iter.List.Nodes'Access);
+      end Is_Valid;
+
+      --------------
+      -- Is_Valid --
+      --------------
+
+      function Is_Valid (Nod : Node_Ptr; Head : Node_Ptr) return Boolean is
+      begin
+         --  A node is valid if it is non-null, and does not refer to the dummy
+         --  head of some list.
+
+         return Nod /= null and then Nod /= Head;
+      end Is_Valid;
+
+      -------------
+      -- Iterate --
+      -------------
+
+      function Iterate (L : Instance) return Iterator is
+      begin
+         Ensure_Created (L);
+
+         --  Lock all mutation functionality of the list while it is being
+         --  iterated on.
+
+         Lock (L);
+
+         return (List => L, Nod => L.Nodes.Next);
+      end Iterate;
+
+      ----------
+      -- Last --
+      ----------
+
+      function Last (L : Instance) return Element_Type is
+      begin
+         Ensure_Created (L);
+         Ensure_Full   (L);
+
+         return L.Nodes.Prev.Elem;
+      end Last;
+
+      ------------
+      -- Length --
+      ------------
+
+      function Length (L : Instance) return Element_Count_Type is
+      begin
+         Ensure_Created (L);
+
+         return L.Elements;
+      end Length;
+
+      ----------
+      -- Lock --
+      ----------
+
+      procedure Lock (L : Instance) is
+      begin
+         pragma Assert (L /= null);
+
+         --  The list may be locked multiple times if multiple iterators are
+         --  operating over it.
+
+         L.Locked := L.Locked + 1;
+      end Lock;
+
+      ----------
+      -- Next --
+      ----------
+
+      procedure Next
+        (Iter : in out Iterator;
+         Elem : out Element_Type)
+      is
+         Is_OK : constant Boolean  := Is_Valid (Iter);
+         Saved : constant Node_Ptr := Iter.Nod;
+
+      begin
+         --  The iterator is no linger valid which indicates that it has been
+         --  exhausted. Unlock all mutation functionality of the list as the
+         --  iterator cannot be advanced any further.
+
+         if not Is_OK then
+            Unlock (Iter.List);
+            raise Iterator_Exhausted;
+         end if;
+
+         --  Advance to the next node along the list
+
+         Iter.Nod := Iter.Nod.Next;
+         Elem     := Saved.Elem;
+      end Next;
+
+      -------------
+      -- Prepend --
+      -------------
+
+      procedure Prepend (L : Instance; Elem : Element_Type) is
+         Head : Node_Ptr;
+
+      begin
+         Ensure_Created  (L);
+         Ensure_Unlocked (L);
+
+         --  Ensure that the dummy head of an empty list is circular with
+         --  respect to itself.
+
+         Head := L.Nodes'Access;
+         Ensure_Circular (Head);
+
+         --  Append the node by inserting it between the dummy head and the
+         --  first node.
+
+         Insert_Between
+           (L     => L,
+            Elem  => Elem,
+            Left  => Head,
+            Right => Head.Next);
+      end Prepend;
+
+      -------------
+      -- Replace --
+      -------------
+
+      procedure Replace
+        (L        : Instance;
+         Old_Elem : Element_Type;
+         New_Elem : Element_Type)
+      is
+         Head : Node_Ptr;
+         Nod  : Node_Ptr;
+
+      begin
+         Ensure_Created  (L);
+         Ensure_Unlocked (L);
+
+         Head := L.Nodes'Access;
+         Nod  := Find_Node (Head, Old_Elem);
+
+         if Is_Valid (Nod, Head) then
+            Nod.Elem := New_Elem;
+         end if;
+      end Replace;
+
+      ------------
+      -- Unlock --
+      ------------
+
+      procedure Unlock (L : Instance) is
+      begin
+         pragma Assert (L /= null);
+
+         --  The list may be locked multiple times if multiple iterators are
+         --  operating over it.
+
+         L.Locked := L.Locked - 1;
+      end Unlock;
+   end Doubly_Linked_List;
+
+end GNAT.Lists;
diff --git a/gcc/ada/libgnat/g-lists.ads b/gcc/ada/libgnat/g-lists.ads
new file mode 100644
index 0000000..777b4f6
--- /dev/null
+++ b/gcc/ada/libgnat/g-lists.ads
@@ -0,0 +1,245 @@
+------------------------------------------------------------------------------
+--                                                                          --
+--                         GNAT RUN-TIME COMPONENTS                         --
+--                                                                          --
+--                            G N A T . L I S T S                           --
+--                                                                          --
+--                                 S p e c                                  --
+--                                                                          --
+--             Copyright (C) 2018, 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;
+
+package GNAT.Lists is
+
+   ------------------------
+   -- Doubly_Linked_List --
+   ------------------------
+
+   --  The following package offers a doubly linked list abstraction with the
+   --  following characteristics:
+   --
+   --    * Creation of multiple instances, of different sizes.
+   --    * Iterable elements.
+   --
+   --  The following use pattern must be employed with this list:
+   --
+   --    List : Instance := Create;
+   --
+   --    <various operations>
+   --
+   --    Destroy (List)
+   --
+   --  The destruction of the list reclaims all storage occupied by it.
+
+   --  The following type denotes the number of elements stored in a list
+
+   type Element_Count_Type is range 0 .. 2 ** 31 - 1;
+
+   generic
+      type Element_Type is private;
+
+      with function "="
+        (Left  : Element_Type;
+         Right : Element_Type) return Boolean;
+
+   package Doubly_Linked_List is
+
+      ---------------------
+      -- List operations --
+      ---------------------
+
+      type Instance is private;
+      Nil : constant Instance;
+
+      List_Empty : exception;
+      --  This exception is raised when the list is empty, and an attempt is
+      --  made to delete an element from it.
+
+      List_Locked : exception;
+      --  This exception is raised when the list is being iterated on, and an
+      --  attempt is made to mutate its state.
+
+      Not_Created : exception;
+      --  This exception is raised when the list has not been created by
+      --  routine Create, and an attempt is made to read or mutate its state.
+
+      procedure Append (L : Instance; Elem : Element_Type);
+      --  Insert element Elem at the end of list L. This action will raise
+      --  List_Locked if the list has outstanding iterators.
+
+      function Contains (L : Instance; Elem : Element_Type) return Boolean;
+      --  Determine whether list L contains element Elem
+
+      function Create return Instance;
+      --  Create a new list
+
+      procedure Delete (L : Instance; Elem : Element_Type);
+      --  Delete element Elem from list L. The routine has no effect if Elem is
+      --  not present. This action will raise
+      --
+      --    * List_Empty if the list is empty.
+      --    * List_Locked if the list has outstanding iterators.
+
+      procedure Delete_First (L : Instance);
+      --  Delete an element from the start of list L. This action will raise
+      --
+      --    * List_Empty if the list is empty.
+      --    * List_Locked if the list has outstanding iterators.
+
+      procedure Delete_Last (L : Instance);
+      --  Delete an element from the end of list L. This action will raise
+      --
+      --    * List_Empty if the list is empty.
+      --    * List_Locked if the list has outstanding iterators.
+
+      procedure Destroy (L : in out Instance);
+      --  Destroy the contents of list L. This routine must be called at the
+      --  end of a list's lifetime. This action will raise List_Locked if the
+      --  list has outstanding iterators.
+
+      function First (L : Instance) return Element_Type;
+      --  Obtain an element from the start of list L. This action will raise
+      --  List_Empty if the list is empty.
+
+      procedure Insert_After
+        (L     : Instance;
+         After : Element_Type;
+         Elem  : Element_Type);
+      --  Insert new element Elem after element After in list L. The routine
+      --  has no effect if After is not present. This action will raise
+      --  List_Locked if the list has outstanding iterators.
+
+      procedure Insert_Before
+        (L      : Instance;
+         Before : Element_Type;
+         Elem   : Element_Type);
+      --  Insert new element Elem before element Before in list L. The routine
+      --  has no effect if After is not present. This action will raise
+      --  List_Locked if the list has outstanding iterators.
+
+      function Is_Empty (L : Instance) return Boolean;
+      --  Determine whether list L is empty
+
+      function Last (L : Instance) return Element_Type;
+      --  Obtain an element from the end of list L. This action will raise
+      --  List_Empty if the list is empty.
+
+      function Length (L : Instance) return Element_Count_Type;
+      --  Obtain the number of elements in list L
+
+      procedure Prepend (L : Instance; Elem : Element_Type);
+      --  Insert element Elem at the start of list L. This action will raise
+      --  List_Locked if the list has outstanding iterators.
+
+      procedure Replace
+        (L        : Instance;
+         Old_Elem : Element_Type;
+         New_Elem : Element_Type);
+      --  Replace old element Old_Elem with new element New_Elem in list L. The
+      --  routine has no effect if Old_Elem is not present. This action will
+      --  raise List_Locked if the list has outstanding iterators.
+
+      -------------------------
+      -- Iterator operations --
+      -------------------------
+
+      --  The following type represents an element iterator. An iterator locks
+      --  all mutation operations, and ulocks them once it is exhausted. The
+      --  iterator must be used with the following pattern:
+      --
+      --    Iter := Iterate (My_List);
+      --    while Has_Next (Iter) loop
+      --       Next (Iter, Element);
+      --    end loop;
+      --
+      --  It is possible to advance the iterator by using Next only, however
+      --  this risks raising Iterator_Exhausted.
+
+      type Iterator is private;
+
+      Iterator_Exhausted : exception;
+      --  This exception is raised when an iterator is exhausted and further
+      --  attempts to advance it are made by calling routine Next.
+
+      function Iterate (L : Instance) return Iterator;
+      --  Obtain an iterator over the elements of list L. This action locks all
+      --  mutation functionality of the associated list.
+
+      function Has_Next (Iter : Iterator) return Boolean;
+      --  Determine whether iterator Iter has more elements to examine. If the
+      --  iterator has been exhausted, restore all mutation functionality of
+      --  the associated list.
+
+      procedure Next
+        (Iter : in out Iterator;
+         Elem : out Element_Type);
+      --  Return the current element referenced by iterator Iter and advance
+      --  to the next available element. If the iterator has been exhausted
+      --  and further attempts are made to advance it, this routine restores
+      --  mutation functionality of the associated list, and then raises
+      --  Iterator_Exhausted.
+
+   private
+      --  The following type represents a list node
+
+      type Node;
+      type Node_Ptr is access all Node;
+      type Node is record
+         Elem : Element_Type;
+
+         Next : Node_Ptr := null;
+         Prev : Node_Ptr := null;
+      end record;
+
+      --  The following type represents a list
+
+      type Linked_List is record
+         Elements : Element_Count_Type := 0;
+         --  The number of elements in the list
+
+         Locked : Natural := 0;
+         --  Number of outstanding iterators
+
+         Nodes : aliased Node;
+         --  The dummy head of the list
+      end record;
+
+      type Instance is access all Linked_List;
+      Nil : constant Instance := null;
+
+      --  The following type represents an element iterator
+
+      type Iterator is record
+         List : Instance := null;
+         --  Reference to the associated list
+
+         Nod : Node_Ptr := null;
+         --  Reference to the current node being examined. The invariant of the
+         --  iterator requires that this field always points to a valid node. A
+         --  value of null indicates that the iterator is exhausted.
+      end record;
+   end Doubly_Linked_List;
+
+end GNAT.Lists;