lib/gl_list.hh

   1 /* Abstract sequential list data type as a C++ class.
   2    Copyright (C) 2006-2020 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 element at a given position in the list.
 138      POSITION must be >= 0 and < gl_list_size (list).  */
 139   ELTYPE * get_at (size_t position) const
 140     { return static_cast<ELTYPE *>(gl_list_get_at (_ptr, position)); }
 141
 142   /* Returns the element at the first position in the list.
 143      The list must be non-empty.  */
 144   ELTYPE * get_first () const
 145     { return static_cast<ELTYPE *>(gl_list_get_first (_ptr)); }
 146
 147   /* Returns the element at the last position in the list.
 148      The list must be non-empty.  */
 149   ELTYPE * get_last () const
 150     { return static_cast<ELTYPE *>(gl_list_get_last (_ptr)); }
 151
 152   /* Searches whether an element is already in the list.
 153      Returns its node if found, or NULL if not present in the list.  */
 154   gl_list_node_t search (ELTYPE * elt) const
 155     { return gl_list_search (_ptr, elt); }
 156
 157   /* Searches whether an element is already in the list,
 158      at a position >= START_INDEX.
 159      Returns its node if found, or NULL if not present in the list.  */
 160   gl_list_node_t search_from (size_t start_index, ELTYPE * elt) const
 161     { return gl_list_search_from (_ptr, start_index, elt); }
 162
 163   /* Searches whether an element is already in the list,
 164      at a position >= START_INDEX and < END_INDEX.
 165      Returns its node if found, or NULL if not present in the list.  */
 166   gl_list_node_t search_from_to (size_t start_index, size_t end_index, ELTYPE * elt) const
 167     { return gl_list_search_from_to (_ptr, start_index, end_index, elt); }
 168
 169   /* Searches whether an element is already in the list.
 170      Returns its position if found, or (size_t)(-1) if not present in the list.  */
 171   size_t indexof (ELTYPE * elt) const
 172     { return gl_list_indexof (_ptr, elt); }
 173
 174   /* Searches whether an element is already in the list,
 175      at a position >= START_INDEX.
 176      Returns its position if found, or (size_t)(-1) if not present in the list.  */
 177   size_t indexof_from (size_t start_index, ELTYPE * elt) const
 178     { return gl_list_indexof_from (_ptr, start_index, elt); }
 179
 180   /* Searches whether an element is already in the list,
 181      at a position >= START_INDEX and < END_INDEX.
 182      Returns its position if found, or (size_t)(-1) if not present in the list.  */
 183   size_t indexof_from_to (size_t start_index, size_t end_index, ELTYPE * elt) const
 184     { return gl_list_indexof_from_to (_ptr, start_index, end_index, elt); }
 185
 186   // ----------------------- Modifying member functions -----------------------
 187
 188   /* Replaces the element value represented by a list node.  */
 189   void node_set_value (gl_list_node_t node, ELTYPE * elt)
 190     { gl_list_node_set_value (_ptr, node, elt); }
 191
 192   /* Replaces the element at a given position in the list.
 193      POSITION must be >= 0 and < gl_list_size (list).
 194      Returns its node.  */
 195   gl_list_node_t set_at (size_t position, ELTYPE * elt)
 196     { return gl_list_set_at (_ptr, position, elt); }
 197
 198   /* Replaces the element at the first position in the list.
 199      Returns its node.
 200      The list must be non-empty.  */
 201   gl_list_node_t set_first (ELTYPE * elt)
 202     { return gl_list_set_first (_ptr, elt); }
 203
 204   /* Replaces the element at the last position in the list.
 205      Returns its node.
 206      The list must be non-empty.  */
 207   gl_list_node_t set_last (ELTYPE * elt)
 208     { return gl_list_set_last (_ptr, elt); }
 209
 210   /* Adds an element as the first element of the list.
 211      Returns its node.  */
 212   gl_list_node_t add_first (ELTYPE * elt)
 213     { return gl_list_add_first (_ptr, elt); }
 214
 215   /* Adds an element as the last element of the list.
 216      Returns its node.  */
 217   gl_list_node_t add_last (ELTYPE * elt)
 218     { return gl_list_add_last (_ptr, elt); }
 219
 220   /* Adds an element before a given element node of the list.
 221      Returns its node.  */
 222   gl_list_node_t add_before (gl_list_node_t node, ELTYPE * elt)
 223     { return gl_list_add_before (_ptr, node, elt); }
 224
 225   /* Adds an element after a given element node of the list.
 226      Return its node.  */
 227   gl_list_node_t add_after (gl_list_node_t node, ELTYPE * elt)
 228     { return gl_list_add_after (_ptr, node, elt); }
 229
 230   /* Adds an element at a given position in the list.
 231      POSITION must be >= 0 and <= gl_list_size (list).  */
 232   gl_list_node_t add_at (size_t position, ELTYPE * elt)
 233     { return gl_list_add_at (_ptr, position, elt); }
 234
 235   /* Removes an element from the list.
 236      Returns true.  */
 237   bool remove_node (gl_list_node_t node)
 238     { return gl_list_remove_node (_ptr, node); }
 239
 240   /* Removes an element at a given position from the list.
 241      POSITION must be >= 0 and < gl_list_size (list).
 242      Returns true.  */
 243   bool remove_at (size_t position)
 244     { return gl_list_remove_at (_ptr, position); }
 245
 246   /* Removes the element at the first position from the list.
 247      Returns true if it was found and removed,
 248      or false if the list was empty.  */
 249   bool remove_first ()
 250     { return gl_list_remove_first (_ptr); }
 251
 252   /* Removes the element at the last position from the list.
 253      Returns true if it was found and removed,
 254      or false if the list was empty.  */
 255   bool remove_last ()
 256     { return gl_list_remove_last (_ptr); }
 257
 258   /* Searches and removes an element from the list.
 259      Returns true if it was found and removed.  */
 260   bool remove (ELTYPE * elt)
 261     { return gl_list_remove (_ptr, elt); }
 262
 263   /* Frees the entire list.
 264      (But this call does not free the elements of the list.  It only invokes
 265      the DISPOSE_FN on each of the elements of the list, and only if the list
 266      is not a sublist.)  */
 267   void free ()
 268     { gl_list_free (_ptr); _ptr = NULL; }
 269
 270   // -------------------- Member functions for sorted lists --------------------
 271
 272   /* The following functions are for lists without duplicates where the
 273      order is given by a sort criterion.  */
 274
 275   /* Searches whether an element is already in the list.
 276      The list is assumed to be sorted with COMPAR.
 277      Returns its node if found, or NULL if not present in the list.
 278      If the list contains several copies of ELT, the node of the leftmost one is
 279      returned.  */
 280   gl_list_node_t sortedlist_search (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 281                                     ELTYPE * elt)
 282     { return gl_sortedlist_search (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 283
 284   /* Searches whether an element is already in the list.
 285      The list is assumed to be sorted with COMPAR.
 286      Only list elements with indices >= START_INDEX and < END_INDEX are
 287      considered; the implementation uses these bounds to minimize the number
 288      of COMPAR invocations.
 289      Returns its node if found, or NULL if not present in the list.
 290      If the list contains several copies of ELT, the node of the leftmost one is
 291      returned.  */
 292   gl_list_node_t sortedlist_search_from_to (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 293                                             size_t start_index,
 294                                             size_t end_index,
 295                                             ELTYPE * elt)
 296     { return gl_sortedlist_search_from_to (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), start_index, end_index, elt); }
 297
 298   /* Searches whether an element is already in the list.
 299      The list is assumed to be sorted with COMPAR.
 300      Returns its position if found, or (size_t)(-1) if not present in the list.
 301      If the list contains several copies of ELT, the position of the leftmost one
 302      is returned.  */
 303   size_t sortedlist_indexof (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 304                              ELTYPE * elt)
 305     { return gl_sortedlist_indexof (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 306
 307   /* Searches whether an element is already in the list.
 308      The list is assumed to be sorted with COMPAR.
 309      Only list elements with indices >= START_INDEX and < END_INDEX are
 310      considered; the implementation uses these bounds to minimize the number
 311      of COMPAR invocations.
 312      Returns its position if found, or (size_t)(-1) if not present in the list.
 313      If the list contains several copies of ELT, the position of the leftmost one
 314      is returned.  */
 315   size_t sortedlist_indexof_from_to (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 316                                      size_t start_index,
 317                                      size_t end_index,
 318                                      ELTYPE * elt)
 319     { return gl_sortedlist_indexof_from_to (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), start_index, end_index, elt); }
 320
 321   /* Adds an element at the appropriate position in the list.
 322      The list is assumed to be sorted with COMPAR.
 323      Returns its node.  */
 324   gl_list_node_t sortedlist_add (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 325                                  ELTYPE * elt)
 326     { return gl_sortedlist_add (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 327
 328   /* Searches and removes an element from the list.
 329      The list is assumed to be sorted with COMPAR.
 330      Returns true if it was found and removed.
 331      If the list contains several copies of ELT, only the leftmost one is
 332      removed.  */
 333   bool sortedlist_remove (int (*compar) (ELTYPE * /*elt1*/, ELTYPE * /*elt2*/),
 334                           ELTYPE * elt)
 335     { return gl_sortedlist_remove (_ptr, reinterpret_cast<gl_listelement_compar_fn>(compar), elt); }
 336
 337   // ------------------------------ Private stuff ------------------------------
 338
 339 private:
 340   gl_list_t _ptr;
 341
 342 public:
 343   // -------------------------------- Iterators --------------------------------
 344   // Only a forward iterator.
 345   // Does not implement the STL operations (++, *, and != .end()), but a simpler
 346   // interface that needs only one virtual function call per iteration instead
 347   // of three.
 348
 349   class iterator {
 350   public:
 351
 352     /* If there is a next element, stores the next element in ELT, advances
 353        the iterator and returns true.
 354        Otherwise, returns false.  */
 355     bool next (ELTYPE *& elt)
 356       {
 357         const void *next_elt;
 358         bool has_next = gl_list_iterator_next (&_state, &next_elt, NULL);
 359         if (has_next)
 360           elt = static_cast<ELTYPE *>(next_elt);
 361         return has_next;
 362       }
 363
 364     /* If there is a next element, stores the next element in ELT, stores its
 365        node in *NODEP if NODEP is non-NULL, advances the iterator and returns true.
 366        Otherwise, returns false.  */
 367     bool next (ELTYPE *& elt, gl_list_node_t *nodep)
 368       {
 369         const void *next_elt;
 370         bool has_next = gl_list_iterator_next (&_state, &next_elt, nodep);
 371         if (has_next)
 372           elt = static_cast<ELTYPE *>(next_elt);
 373         return has_next;
 374       }
 375
 376     ~iterator ()
 377       { gl_list_iterator_free (&_state); }
 378
 379   #if defined __xlC__ || defined __HP_aCC || defined __SUNPRO_CC
 380   public:
 381   #else
 382   private:
 383     friend iterator gl_List::begin ();
 384   #endif
 385
 386     iterator (gl_list_t ptr)
 387       : _state (gl_list_iterator (ptr))
 388       {}
 389
 390     iterator (gl_list_t ptr, size_t start_index, size_t end_index)
 391       : _state (gl_list_iterator_from_to (ptr, start_index, end_index))
 392       {}
 393
 394   private:
 395
 396     gl_list_iterator_t _state;
 397   };
 398
 399   /* Creates an iterator traversing the list.
 400      The list contents must not be modified while the iterator is in use,
 401      except for replacing or removing the last returned element.  */
 402   iterator begin ()
 403     { return iterator (_ptr); }
 404
 405   /* Creates an iterator traversing the element with indices i,
 406      start_index <= i < end_index, of a list.
 407      The list contents must not be modified while the iterator is in use,
 408      except for replacing or removing the last returned element.  */
 409   iterator begin (size_t start_index, size_t end_index)
 410     { return iterator (_ptr, start_index, end_index); }
 411 };
 412
 413 #endif /* _GL_LIST_HH */