lib/gl_list.hh

   1 /* Abstract sequential list data type as a C++ class.
   2    Copyright (C) 2006-2024 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation, either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #ifndef _GL_LIST_HH
  19 #define _GL_LIST_HH
  20
  21 #include "gl_list.h"
  22 #include "gl_xlist.h"
  23 #include "gl_sublist.h"
  24 #include "gl_xsublist.h"
  25
  26 #include <stdlib.h>     /* because Gnulib's <stdlib.h> may '#define free ...' */
  27
  28 /* gl_List is a C++ wrapper around the gl_list data type.
  29    Its element type is 'ELTYPE *'.
  30
  31    It is merely a pointer, not a smart pointer. In other words:
  32    it does NOT do reference-counting, and the destructor does nothing.  */
  33
  34 template <class T> class gl_List;
  35
  36 template <class ELTYPE>
  37 class gl_List<ELTYPE *>
  38 {
  39 public:
  40   // ------------------------------ Constructors ------------------------------
  41
  42   gl_List ()
  43     : _ptr (NULL)
  44     {}
  45
  46   /* Creates an empty list.
  47      IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
  48      GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
  49      GL_RBTREEHASH_LIST.
  50      EQUALS_FN is an element comparison function or NULL.
  51      HASHCODE_FN is an element hash code function or NULL.
  52      DISPOSE_FN is an element disposal function or NULL.
  53      ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
  54      the list. The implementation may verify this at runtime.  */
  55   gl_List (gl_list_implementation_t implementation,
  56            bool (*equals_fn) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
  57            size_t (*hashcode_fn) (ELTYPE *),
  58            void (*dispose_fn) (ELTYPE *),
  59            bool allow_duplicates)
  60     : _ptr (gl_list_create_empty (implementation,
  61                                   reinterpret_cast<gl_listelement_equals_fn>(equals_fn),
  62                                   reinterpret_cast<gl_listelement_hashcode_fn>(hashcode_fn),
  63                                   reinterpret_cast<gl_listelement_dispose_fn>(dispose_fn),
  64                                   allow_duplicates))
  65     {}
  66
  67   /* Creates a list with given contents.
  68      IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST,
  69      GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST,
  70      GL_RBTREEHASH_LIST.
  71      EQUALS_FN is an element comparison function or NULL.
  72      HASHCODE_FN is an element hash code function or NULL.
  73      DISPOSE_FN is an element disposal function or NULL.
  74      ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in
  75      the list. The implementation may verify this at runtime.
  76      COUNT is the number of initial elements.
  77      CONTENTS[0..COUNT-1] is the initial contents.  */
  78   gl_List (gl_list_implementation_t implementation,
  79            bool (*equals_fn) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
  80            size_t (*hashcode_fn) (ELTYPE *),
  81            void (*dispose_fn) (ELTYPE *),
  82            bool allow_duplicates,
  83            size_t count, ELTYPE **contents)
  84     : _ptr (gl_list_create (implementation,
  85                             reinterpret_cast<gl_listelement_equals_fn>(equals_fn),
  86                             reinterpret_cast<gl_listelement_hashcode_fn>(hashcode_fn),
  87                             reinterpret_cast<gl_listelement_dispose_fn>(dispose_fn),
  88                             allow_duplicates,
  89                             count, contents))
  90     {}
  91
  92   /* Creates a sublist of a given list.
  93      This is the list of elements with indices i, start_index <= i < end_index.
  94      The sublist is backed by the given list, which means:
  95        - Modifications to the sublist affect the whole list.
  96        - Modifications to the whole list are immediately visible in the sublist.
  97        - The sublist is only valid as long as the whole list is valid.
  98        - The sublist must not be passed to the gl_list_sortedlist_add() function.
  99    */
 100   gl_List (const gl_List& whole_list, size_t start_index, size_t end_index)
 101     : _ptr (gl_sublist_create (whole_list._ptr, start_index, end_index))
 102     {}
 103
 104   /* Copy constructor.  */
 105   gl_List (const gl_List& x)
 106     { _ptr = x._ptr; }
 107
 108   /* Assignment operator.  */
 109   gl_List& operator= (const gl_List& x)
 110     { _ptr = x._ptr; return *this; }
 111
 112   // ------------------------------- Destructor -------------------------------
 113
 114   ~gl_List ()
 115     { _ptr = NULL; }
 116
 117   // ----------------------- Read-only member functions -----------------------
 118
 119   /* Returns the current number of elements in the list.  */
 120   size_t size () const
 121     { return gl_list_size (_ptr); }
 122
 123   /* Returns the element value represented by a list node.  */
 124   ELTYPE * node_value (gl_list_node_t node) const
 125     { return static_cast<ELTYPE *>(gl_list_node_value (_ptr, node)); }
 126
 127   /* Returns the node immediately after the given node in the list, or NULL
 128      if the given node is the last (rightmost) one in the list.  */
 129   gl_list_node_t next_node (gl_list_node_t node) const
 130     { return gl_list_next_node (_ptr, node); }
 131
 132   /* Returns the node immediately before the given node in the list, or NULL
 133      if the given node is the first (leftmost) one in the list.  */
 134   gl_list_node_t previous_node (gl_list_node_t node) const
 135     { return gl_list_previous_node (_ptr, node); }
 136
 137   /* Returns the first node in the list, or NULL if the list is empty.  */
 138   gl_list_node_t first_node () const
 139     { return gl_list_first_node (_ptr); }
 140
 141   /* Returns the last node in the list, or NULL if the list is empty.  */
 142   gl_list_node_t last_node () const
 143     { return gl_list_last_node (_ptr); }
 144
 145   /* Returns the element at a given position in the list.
 146      POSITION must be >= 0 and < gl_list_size (list).  */
 147   ELTYPE * get_at (size_t position) const
 148     { return static_cast<ELTYPE *>(gl_list_get_at (_ptr, position)); }
 149
 150   /* Returns the element at the first position in the list.
 151      The list must be non-empty.  */
 152   ELTYPE * get_first () const
 153     { return static_cast<ELTYPE *>(gl_list_get_first (_ptr)); }
 154
 155   /* Returns the element at the last position in the list.
 156      The list must be non-empty.  */
 157   ELTYPE * get_last () const
 158     { return static_cast<ELTYPE *>(gl_list_get_last (_ptr)); }
 159
 160   /* Searches whether an element is already in the list.
 161      Returns its node if found, or NULL if not present in the list.  */
 162   gl_list_node_t search (ELTYPE * elt) const
 163     { return gl_list_search (_ptr, elt); }
 164
 165   /* Searches whether an element is already in the list,
 166      at a position >= START_INDEX.
 167      Returns its node if found, or NULL if not present in the list.  */
 168   gl_list_node_t search_from (size_t start_index, ELTYPE * elt) const
 169     { return gl_list_search_from (_ptr, start_index, elt); }
 170
 171   /* Searches whether an element is already in the list,
 172      at a position >= START_INDEX and < END_INDEX.
 173      Returns its node if found, or NULL if not present in the list.  */
 174   gl_list_node_t search_from_to (size_t start_index, size_t end_index, ELTYPE * elt) const
 175     { return gl_list_search_from_to (_ptr, start_index, end_index, elt); }
 176
 177   /* Searches whether an element is already in the list.
 178      Returns its position if found, or (size_t)(-1) if not present in the list.  */
 179   size_t indexof (ELTYPE * elt) const
 180     { return gl_list_indexof (_ptr, elt); }
 181
 182   /* Searches whether an element is already in the list,
 183      at a position >= START_INDEX.
 184      Returns its position if found, or (size_t)(-1) if not present in the list.  */
 185   size_t indexof_from (size_t start_index, ELTYPE * elt) const
 186     { return gl_list_indexof_from (_ptr, start_index, elt); }
 187
 188   /* Searches whether an element is already in the list,
 189      at a position >= START_INDEX and < END_INDEX.
 190      Returns its position if found, or (size_t)(-1) if not present in the list.  */
 191   size_t indexof_from_to (size_t start_index, size_t end_index, ELTYPE * elt) const
 192     { return gl_list_indexof_from_to (_ptr, start_index, end_index, elt); }
 193
 194   // ----------------------- Modifying member functions -----------------------
 195
 196   /* Replaces the element value represented by a list node.  */
 197   void node_set_value (gl_list_node_t node, ELTYPE * elt)
 198     { gl_list_node_set_value (_ptr, node, elt); }
 199
 200   /* Replaces the element at a given position in the list.
 201      POSITION must be >= 0 and < gl_list_size (list).
 202      Returns its node.  */
 203   gl_list_node_t set_at (size_t position, ELTYPE * elt)
 204     { return gl_list_set_at (_ptr, position, elt); }
 205
 206   /* Replaces the element at the first position in the list.
 207      Returns its node.
 208      The list must be non-empty.  */
 209   gl_list_node_t set_first (ELTYPE * elt)
 210     { return gl_list_set_first (_ptr, elt); }
 211
 212   /* Replaces the element at the last position in the list.
 213      Returns its node.
 214      The list must be non-empty.  */
 215   gl_list_node_t set_last (ELTYPE * elt)
 216     { return gl_list_set_last (_ptr, elt); }
 217
 218   /* Adds an element as the first element of the list.
 219      Returns its node.  */
 220   gl_list_node_t add_first (ELTYPE * elt)
 221     { return gl_list_add_first (_ptr, elt); }
 222
 223   /* Adds an element as the last element of the list.
 224      Returns its node.  */
 225   gl_list_node_t add_last (ELTYPE * elt)
 226     { return gl_list_add_last (_ptr, elt); }
 227
 228   /* Adds an element before a given element node of the list.
 229      Returns its node.  */
 230   gl_list_node_t add_before (gl_list_node_t node, ELTYPE * elt)
 231     { return gl_list_add_before (_ptr, node, elt); }
 232
 233   /* Adds an element after a given element node of the list.
 234      Return its node.  */
 235   gl_list_node_t add_after (gl_list_node_t node, ELTYPE * elt)
 236     { return gl_list_add_after (_ptr, node, elt); }
 237
 238   /* Adds an element at a given position in the list.
 239      POSITION must be >= 0 and <= gl_list_size (list).  */
 240   gl_list_node_t add_at (size_t position, ELTYPE * elt)
 241     { return gl_list_add_at (_ptr, position, elt); }
 242
 243   /* Removes an element from the list.
 244      Returns true.  */
 245   bool remove_node (gl_list_node_t node)
 246     { return gl_list_remove_node (_ptr, node); }
 247
 248   /* Removes an element at a given position from the list.
 249      POSITION must be >= 0 and < gl_list_size (list).
 250      Returns true.  */
 251   bool remove_at (size_t position)
 252     { return gl_list_remove_at (_ptr, position); }
 253
 254   /* Removes the element at the first position from the list.
 255      Returns true if it was found and removed,
 256      or false if the list was empty.  */
 257   bool remove_first ()
 258     { return gl_list_remove_first (_ptr); }
 259
 260   /* Removes the element at the last position from the list.
 261      Returns true if it was found and removed,
 262      or false if the list was empty.  */
 263   bool remove_last ()
 264     { return gl_list_remove_last (_ptr); }
 265
 266   /* Searches and removes an element from the list.
 267      Returns true if it was found and removed.  */
 268   bool remove (ELTYPE * elt)
 269     { return gl_list_remove (_ptr, elt); }
 270
 271   /* Frees the entire list.
 272      (But this call does not free the elements of the list.  It only invokes
 273      the DISPOSE_FN on each of the elements of the list, and only if the list
 274      is not a sublist.)  */
 275   void free ()
 276     { gl_list_free (_ptr); _ptr = NULL; }
 277
 278   // -------------------- Member functions for sorted lists --------------------
 279
 280   /* The following functions are for lists without duplicates where the
 281      order is given by a sort criterion.  */
 282
 283   /* Searches whether an element is already in the list.
 284      The list is assumed to be sorted with COMPAR.
 285      Returns its node if found, or NULL if not present in the list.
 286      If the list contains several copies of ELT, the node of the leftmost one is
 287      returned.  */
 288   gl_list_node_t sortedlist_search (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 289                                     ELTYPE * elt)
 290     { return gl_sortedlist_search (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 291
 292   /* Searches whether an element is already in the list.
 293      The list is assumed to be sorted with COMPAR.
 294      Only list elements with indices >= START_INDEX and < END_INDEX are
 295      considered; the implementation uses these bounds to minimize the number
 296      of COMPAR invocations.
 297      Returns its node if found, or NULL if not present in the list.
 298      If the list contains several copies of ELT, the node of the leftmost one is
 299      returned.  */
 300   gl_list_node_t sortedlist_search_from_to (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 301                                             size_t start_index,
 302                                             size_t end_index,
 303                                             ELTYPE * elt)
 304     { return gl_sortedlist_search_from_to (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), start_index, end_index, elt); }
 305
 306   /* Searches whether an element is already in the list.
 307      The list is assumed to be sorted with COMPAR.
 308      Returns its position if found, or (size_t)(-1) if not present in the list.
 309      If the list contains several copies of ELT, the position of the leftmost one
 310      is returned.  */
 311   size_t sortedlist_indexof (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 312                              ELTYPE * elt)
 313     { return gl_sortedlist_indexof (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 314
 315   /* Searches whether an element is already in the list.
 316      The list is assumed to be sorted with COMPAR.
 317      Only list elements with indices >= START_INDEX and < END_INDEX are
 318      considered; the implementation uses these bounds to minimize the number
 319      of COMPAR invocations.
 320      Returns its position if found, or (size_t)(-1) if not present in the list.
 321      If the list contains several copies of ELT, the position of the leftmost one
 322      is returned.  */
 323   size_t sortedlist_indexof_from_to (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 324                                      size_t start_index,
 325                                      size_t end_index,
 326                                      ELTYPE * elt)
 327     { return gl_sortedlist_indexof_from_to (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), start_index, end_index, elt); }
 328
 329   /* Adds an element at the appropriate position in the list.
 330      The list is assumed to be sorted with COMPAR.
 331      Returns its node.  */
 332   gl_list_node_t sortedlist_add (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 333                                  ELTYPE * elt)
 334     { return gl_sortedlist_add (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 335
 336   /* Searches and removes an element from the list.
 337      The list is assumed to be sorted with COMPAR.
 338      Returns true if it was found and removed.
 339      If the list contains several copies of ELT, only the leftmost one is
 340      removed.  */
 341   bool sortedlist_remove (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 342                           ELTYPE * elt)
 343     { return gl_sortedlist_remove (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 344
 345   // ------------------------------ Private stuff ------------------------------
 346
 347 private:
 348   gl_list_t _ptr;
 349
 350 public:
 351   // -------------------------------- Iterators --------------------------------
 352   // Only a forward iterator.
 353   // Does not implement the STL operations (++, *, and != .end()), but a simpler
 354   // interface that needs only one virtual function call per iteration instead
 355   // of three.
 356
 357   class iterator {
 358   public:
 359
 360     /* If there is a next element, stores the next element in ELT, advances
 361        the iterator and returns true.
 362        Otherwise, returns false.  */
 363     bool next (ELTYPE *& elt)
 364       {
 365         const void *next_elt;
 366         bool has_next = gl_list_iterator_next (&_state, &next_elt, NULL);
 367         if (has_next)
 368           elt = static_cast<ELTYPE *>(next_elt);
 369         return has_next;
 370       }
 371
 372     /* If there is a next element, stores the next element in ELT, stores its
 373        node in *NODEP if NODEP is non-NULL, advances the iterator and returns true.
 374        Otherwise, returns false.  */
 375     bool next (ELTYPE *& elt, gl_list_node_t *nodep)
 376       {
 377         const void *next_elt;
 378         bool has_next = gl_list_iterator_next (&_state, &next_elt, nodep);
 379         if (has_next)
 380           elt = static_cast<ELTYPE *>(next_elt);
 381         return has_next;
 382       }
 383
 384     ~iterator ()
 385       { gl_list_iterator_free (&_state); }
 386
 387   #if defined __xlC__ || defined __HP_aCC || defined __SUNPRO_CC
 388   public:
 389   #else
 390   private:
 391     friend iterator gl_List::begin ();
 392   #endif
 393
 394     iterator (gl_list_t ptr)
 395       : _state (gl_list_iterator (ptr))
 396       {}
 397
 398     iterator (gl_list_t ptr, size_t start_index, size_t end_index)
 399       : _state (gl_list_iterator_from_to (ptr, start_index, end_index))
 400       {}
 401
 402   private:
 403
 404     gl_list_iterator_t _state;
 405   };
 406
 407   /* Creates an iterator traversing the list.
 408      The list contents must not be modified while the iterator is in use,
 409      except for replacing or removing the last returned element.  */
 410   iterator begin ()
 411     { return iterator (_ptr); }
 412
 413   /* Creates an iterator traversing the element with indices i,
 414      start_index <= i < end_index, of a list.
 415      The list contents must not be modified while the iterator is in use,
 416      except for replacing or removing the last returned element.  */
 417   iterator begin (size_t start_index, size_t end_index)
 418     { return iterator (_ptr, start_index, end_index); }
 419 };
 420
 421 #endif /* _GL_LIST_HH */