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 /* */ 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 */