root/maint/gnulib/lib/gl_list.hh

/* [previous][next][first][last][top][bottom][index][help] */

INCLUDED FROM


DEFINITIONS

This source file includes following definitions.
  1. node_value
  2. next_node
  3. previous_node
  4. first_node
  5. last_node
  6. get_at
  7. get_first
  8. get_last
  9. search
  10. search_from
  11. search_from_to
  12. indexof
  13. indexof_from
  14. indexof_from_to
  15. node_set_value
  16. set_at
  17. set_first
  18. set_last
  19. add_first
  20. add_last
  21. add_before
  22. add_after
  23. add_at
  24. remove_node
  25. remove_at
  26. remove_first
  27. remove_last
  28. remove
  29. free
  30. sortedlist_search
  31. sortedlist_search_from_to
  32. sortedlist_indexof
  33. sortedlist_indexof_from_to
  34. sortedlist_add
  35. sortedlist_remove
  36. next
  37. next
  38. begin
  39. begin

   1 /* Abstract sequential list data type as a C++ class.
   2    Copyright (C) 2006-2021 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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 ()
     /* [previous][next][first][last][top][bottom][index][help] */
 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 ()
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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 ()
     /* [previous][next][first][last][top][bottom][index][help] */
 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*/),
     /* [previous][next][first][last][top][bottom][index][help] */
 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*/),
     /* [previous][next][first][last][top][bottom][index][help] */
 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*/),
     /* [previous][next][first][last][top][bottom][index][help] */
 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*/),
     /* [previous][next][first][last][top][bottom][index][help] */
 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*/),
     /* [previous][next][first][last][top][bottom][index][help] */
 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*/),
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 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 ()
     /* [previous][next][first][last][top][bottom][index][help] */
 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)
     /* [previous][next][first][last][top][bottom][index][help] */
 418     { return iterator (_ptr, start_index, end_index); }
 419 };
 420 
 421 #endif /* _GL_LIST_HH */

/* [previous][next][first][last][top][bottom][index][help] */