gcc/ada/libgnat/g-lists.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT RUN-TIME COMPONENTS                         --
   4 --                                                                          --
   5 --                            G N A T . L I S T S                           --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --             Copyright (C) 2018-2020, Free Software Foundation, Inc.      --
  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 package GNAT.Lists is
  35
  36    ------------------------
  37    -- Doubly_Linked_List --
  38    ------------------------
  39
  40    --  The following package offers a doubly linked list abstraction with the
  41    --  following characteristics:
  42    --
  43    --    * Creation of multiple instances, of different sizes
  44    --    * Iterable elements
  45    --
  46    --  The following use pattern must be employed with this list:
  47    --
  48    --    List : Doubly_Linked_List := Create;
  49    --
  50    --    <various operations>
  51    --
  52    --    Destroy (List);
  53    --
  54    --  The destruction of the list reclaims all storage occupied by it.
  55
  56    generic
  57       type Element_Type is private;
  58
  59       with function "="
  60         (Left  : Element_Type;
  61          Right : Element_Type) return Boolean;
  62
  63       with procedure Destroy_Element (Elem : in out Element_Type);
  64       --  Element destructor
  65
  66    package Doubly_Linked_Lists is
  67
  68       ---------------------
  69       -- List operations --
  70       ---------------------
  71
  72       type Doubly_Linked_List is private;
  73       Nil : constant Doubly_Linked_List;
  74
  75       --  The following exception is raised when the list is empty, and an
  76       --  attempt is made to delete an element from it.
  77
  78       List_Empty : exception;
  79
  80       procedure Append
  81         (L    : Doubly_Linked_List;
  82          Elem : Element_Type);
  83       --  Insert element Elem at the end of list L. This action will raise
  84       --  Iterated if the list has outstanding iterators.
  85
  86       function Contains
  87         (L    : Doubly_Linked_List;
  88          Elem : Element_Type) return Boolean;
  89       --  Determine whether list L contains element Elem
  90
  91       function Create return Doubly_Linked_List;
  92       --  Create a new list
  93
  94       procedure Delete
  95         (L    : Doubly_Linked_List;
  96          Elem : Element_Type);
  97       --  Delete element Elem from list L. The routine has no effect if Elem is
  98       --  not present. This action will raise
  99       --
 100       --    * List_Empty if the list is empty.
 101       --    * Iterated if the list has outstanding iterators.
 102
 103       procedure Delete_First (L : Doubly_Linked_List);
 104       --  Delete an element from the start of list L. This action will raise
 105       --
 106       --    * List_Empty if the list is empty.
 107       --    * Iterated if the list has outstanding iterators.
 108
 109       procedure Delete_Last (L : Doubly_Linked_List);
 110       --  Delete an element from the end of list L. This action will raise
 111       --
 112       --    * List_Empty if the list is empty.
 113       --    * Iterated if the list has outstanding iterators.
 114
 115       procedure Destroy (L : in out Doubly_Linked_List);
 116       --  Destroy the contents of list L. This routine must be called at the
 117       --  end of a list's lifetime. This action will raise Iterated if the
 118       --  list has outstanding iterators.
 119
 120       function Equal
 121         (Left  : Doubly_Linked_List;
 122          Right : Doubly_Linked_List) return Boolean;
 123       --  Determine whether lists Left and Right have the same characteristics
 124       --  and contain the same elements.
 125
 126       function First (L : Doubly_Linked_List) return Element_Type;
 127       --  Obtain an element from the start of list L. This action will raise
 128       --  List_Empty if the list is empty.
 129
 130       procedure Insert_After
 131         (L     : Doubly_Linked_List;
 132          After : Element_Type;
 133          Elem  : Element_Type);
 134       --  Insert new element Elem after element After in list L. The routine
 135       --  has no effect if After is not present. This action will raise
 136       --  Iterated if the list has outstanding iterators.
 137
 138       procedure Insert_Before
 139         (L      : Doubly_Linked_List;
 140          Before : Element_Type;
 141          Elem   : Element_Type);
 142       --  Insert new element Elem before element Before in list L. The routine
 143       --  has no effect if After is not present. This action will raise
 144       --  Iterated if the list has outstanding iterators.
 145
 146       function Is_Empty (L : Doubly_Linked_List) return Boolean;
 147       --  Determine whether list L is empty
 148
 149       function Last (L : Doubly_Linked_List) return Element_Type;
 150       --  Obtain an element from the end of list L. This action will raise
 151       --  List_Empty if the list is empty.
 152
 153       procedure Prepend
 154         (L    : Doubly_Linked_List;
 155          Elem : Element_Type);
 156       --  Insert element Elem at the start of list L. This action will raise
 157       --  Iterated if the list has outstanding iterators.
 158
 159       function Present (L : Doubly_Linked_List) return Boolean;
 160       --  Determine whether list L exists
 161
 162       procedure Replace
 163         (L        : Doubly_Linked_List;
 164          Old_Elem : Element_Type;
 165          New_Elem : Element_Type);
 166       --  Replace old element Old_Elem with new element New_Elem in list L. The
 167       --  routine has no effect if Old_Elem is not present. This action will
 168       --  raise Iterated if the list has outstanding iterators.
 169
 170       function Size (L : Doubly_Linked_List) return Natural;
 171       --  Obtain the number of elements in list L
 172
 173       -------------------------
 174       -- Iterator operations --
 175       -------------------------
 176
 177       --  The following type represents an element iterator. An iterator locks
 178       --  all mutation operations, and ulocks them once it is exhausted. The
 179       --  iterator must be used with the following pattern:
 180       --
 181       --    Iter := Iterate (My_List);
 182       --    while Has_Next (Iter) loop
 183       --       Next (Iter, Element);
 184       --    end loop;
 185       --
 186       --  It is possible to advance the iterator by using Next only, however
 187       --  this risks raising Iterator_Exhausted.
 188
 189       type Iterator is private;
 190
 191       function Has_Next (Iter : Iterator) return Boolean;
 192       --  Determine whether iterator Iter has more elements to examine. If the
 193       --  iterator has been exhausted, restore all mutation functionality of
 194       --  the associated list.
 195
 196       function Iterate (L : Doubly_Linked_List) return Iterator;
 197       --  Obtain an iterator over the elements of list L. This action locks all
 198       --  mutation functionality of the associated list.
 199
 200       procedure Next
 201         (Iter : in out Iterator;
 202          Elem : out Element_Type);
 203       --  Return the current element referenced by iterator Iter and advance
 204       --  to the next available element. If the iterator has been exhausted
 205       --  and further attempts are made to advance it, this routine restores
 206       --  mutation functionality of the associated list, and then raises
 207       --  Iterator_Exhausted.
 208
 209    private
 210       --  The following type represents a list node
 211
 212       type Node;
 213       type Node_Ptr is access all Node;
 214       type Node is record
 215          Elem : Element_Type;
 216
 217          Next : Node_Ptr := null;
 218          Prev : Node_Ptr := null;
 219       end record;
 220
 221       --  The following type represents a list
 222
 223       type Doubly_Linked_List_Attributes is record
 224          Elements : Natural := 0;
 225          --  The number of elements in the list
 226
 227          Iterators : Natural := 0;
 228          --  Number of outstanding iterators
 229
 230          Nodes : aliased Node;
 231          --  The dummy head of the list
 232       end record;
 233
 234       type Doubly_Linked_List is access all Doubly_Linked_List_Attributes;
 235       Nil : constant Doubly_Linked_List := null;
 236
 237       --  The following type represents an element iterator
 238
 239       type Iterator is record
 240          Curr_Nod : Node_Ptr := null;
 241          --  Reference to the current node being examined. The invariant of the
 242          --  iterator requires that this field always points to a valid node. A
 243          --  value of null indicates that the iterator is exhausted.
 244
 245          List : Doubly_Linked_List := null;
 246          --  Reference to the associated list
 247       end record;
 248    end Doubly_Linked_Lists;
 249
 250 end GNAT.Lists;