src/cx/list.h

Mon, 18 Apr 2022 15:29:52 +0200

author
Mike Becker <universe@uap-core.de>
date
Mon, 18 Apr 2022 15:29:52 +0200
changeset 524
e98b09018d32
parent 519
79d14e821b3a
child 525
536646d1575b
permissions
-rw-r--r--

remove list destructor

universe@390 1 /*
universe@390 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@390 3 *
universe@390 4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
universe@390 5 *
universe@390 6 * Redistribution and use in source and binary forms, with or without
universe@390 7 * modification, are permitted provided that the following conditions are met:
universe@390 8 *
universe@390 9 * 1. Redistributions of source code must retain the above copyright
universe@390 10 * notice, this list of conditions and the following disclaimer.
universe@390 11 *
universe@390 12 * 2. Redistributions in binary form must reproduce the above copyright
universe@390 13 * notice, this list of conditions and the following disclaimer in the
universe@390 14 * documentation and/or other materials provided with the distribution.
universe@390 15 *
universe@390 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@390 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@390 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@390 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@390 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@390 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@390 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@390 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@390 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@390 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@390 26 * POSSIBILITY OF SUCH DAMAGE.
universe@390 27 */
universe@453 28 /**
universe@453 29 * \file list.h
universe@453 30 * \brief Interface for list implementations.
universe@453 31 * \author Mike Becker
universe@453 32 * \author Olaf Wintermann
universe@453 33 * \version 3.0
universe@453 34 * \copyright 2-Clause BSD License
universe@453 35 */
universe@390 36
universe@390 37 #ifndef UCX_LIST_H
universe@390 38 #define UCX_LIST_H
universe@390 39
universe@484 40 #include "common.h"
universe@398 41 #include "allocator.h"
universe@494 42 #include "iterator.h"
universe@398 43
universe@415 44 #ifdef __cplusplus
universe@415 45 extern "C" {
universe@415 46 #endif
universe@415 47
universe@464 48 /**
universe@464 49 * A comparator function comparing two list elements.
universe@464 50 */
universe@489 51 typedef int(*CxListComparator)(
universe@489 52 void const *left,
universe@489 53 void const *right
universe@489 54 );
universe@398 55
universe@464 56 /**
universe@500 57 * List class type.
universe@464 58 */
universe@500 59 typedef struct cx_list_class_s cx_list_class;
universe@435 60
universe@464 61 /**
universe@464 62 * Structure for holding the base data of a list.
universe@464 63 */
universe@435 64 struct cx_list_s {
universe@464 65 /**
universe@464 66 * The list class definition.
universe@464 67 */
universe@435 68 cx_list_class *cl;
universe@464 69 /**
universe@464 70 * The allocator to use.
universe@464 71 */
universe@508 72 CxAllocator const *allocator;
universe@464 73 /**
universe@503 74 * An optional destructor for the list contents.
universe@503 75 */
universe@503 76 cx_destructor_func content_destructor;
universe@503 77 /**
universe@464 78 * The comparator function for the elements.
universe@464 79 */
universe@398 80 CxListComparator cmpfunc;
universe@464 81 /**
universe@464 82 * The size of each element (payload only).
universe@464 83 */
universe@401 84 size_t itemsize;
universe@464 85 /**
universe@464 86 * The size of the list (number of currently stored elements).
universe@464 87 */
universe@401 88 size_t size;
universe@464 89 /**
universe@464 90 * The capacity of the list (maximum number of elements).
universe@464 91 */
universe@401 92 size_t capacity;
universe@503 93 /**
universe@503 94 * Flag indicating whether cxListDestroy() shall free each list element,
universe@503 95 * even if cx_list_s.content_destructor did not do that.
universe@503 96 */
universe@503 97 bool autofree_contents;
universe@435 98 };
universe@398 99
universe@464 100 /**
universe@500 101 * The class definition for arbitrary lists.
universe@500 102 */
universe@500 103 struct cx_list_class_s {
universe@500 104 /**
universe@524 105 * Destructor function.
universe@524 106 */
universe@524 107 void (*destructor)(struct cx_list_s *list);
universe@524 108
universe@524 109 /**
universe@500 110 * Member function for adding an element.
universe@500 111 */
universe@500 112 int (*add)(
universe@500 113 struct cx_list_s *list,
universe@500 114 void const *elem
universe@500 115 );
universe@500 116
universe@500 117 /**
universe@500 118 * Member function for inserting an element.
universe@500 119 */
universe@500 120 int (*insert)(
universe@500 121 struct cx_list_s *list,
universe@500 122 size_t index,
universe@500 123 void const *elem
universe@500 124 );
universe@500 125
universe@500 126 /**
universe@500 127 * Member function for inserting an element relative to an iterator position.
universe@500 128 */
universe@500 129 int (*insert_iter)(
universe@500 130 struct cx_iterator_s *iter,
universe@500 131 void const *elem,
universe@500 132 int prepend
universe@500 133 );
universe@500 134
universe@500 135 /**
universe@500 136 * Member function for removing an element.
universe@500 137 */
universe@500 138 int (*remove)(
universe@500 139 struct cx_list_s *list,
universe@500 140 size_t index
universe@500 141 );
universe@500 142
universe@500 143 /**
universe@500 144 * Member function for element lookup.
universe@500 145 */
universe@500 146 void *(*at)(
universe@500 147 struct cx_list_s const *list,
universe@500 148 size_t index
universe@500 149 );
universe@500 150
universe@500 151 /**
universe@500 152 * Member function for finding an element.
universe@500 153 */
universe@500 154 size_t (*find)(
universe@500 155 struct cx_list_s const *list,
universe@500 156 void const *elem
universe@500 157 );
universe@500 158
universe@500 159 /**
universe@500 160 * Member function for sorting the list in place.
universe@500 161 */
universe@500 162 void (*sort)(struct cx_list_s *list);
universe@500 163
universe@500 164 /**
universe@500 165 * Member function for comparing this list to another list of the same type.
universe@500 166 */
universe@500 167 int (*compare)(
universe@500 168 struct cx_list_s const *list,
universe@500 169 struct cx_list_s const *other
universe@500 170 );
universe@500 171
universe@500 172 /**
universe@500 173 * Member function for reversing the order of the items.
universe@500 174 */
universe@500 175 void (*reverse)(struct cx_list_s *list);
universe@500 176
universe@500 177 /**
universe@500 178 * Returns an iterator pointing to the specified index.
universe@500 179 */
universe@500 180 struct cx_iterator_s (*iterator)(
universe@500 181 struct cx_list_s *list,
universe@500 182 size_t index
universe@500 183 );
universe@500 184 };
universe@500 185
universe@500 186 /**
universe@464 187 * Common type for all list implementations.
universe@464 188 */
universe@500 189 typedef struct cx_list_s CxList;
universe@398 190
universe@464 191 /**
universe@464 192 * Adds an item to the end of the list.
universe@464 193 *
universe@464 194 * @param list the list
universe@464 195 * @param elem a pointer to the element to add
universe@464 196 * @return zero on success, non-zero on memory allocation failure
universe@464 197 */
universe@508 198 __attribute__((__nonnull__))
universe@489 199 static inline int cxListAdd(
universe@500 200 CxList *list,
universe@489 201 void const *elem
universe@489 202 ) {
universe@469 203 return list->cl->add(list, elem);
universe@469 204 }
universe@398 205
universe@464 206 /**
universe@464 207 * Inserts an item at the specified index.
universe@464 208 *
universe@464 209 * If \p index equals the list \c size, this is effectively cxListAdd().
universe@464 210 *
universe@464 211 * @param list the list
universe@464 212 * @param index the index the element shall have
universe@464 213 * @param elem a pointer to the element to add
universe@464 214 * @return zero on success, non-zero on memory allocation failure
universe@464 215 * or when the index is out of bounds
universe@499 216 * @see cxListInsertAfter()
universe@499 217 * @see cxListInsertBefore()
universe@464 218 */
universe@508 219 __attribute__((__nonnull__))
universe@489 220 static inline int cxListInsert(
universe@500 221 CxList *list,
universe@489 222 size_t index,
universe@489 223 void const *elem
universe@489 224 ) {
universe@469 225 return list->cl->insert(list, index, elem);
universe@469 226 }
universe@398 227
universe@464 228 /**
universe@499 229 * Inserts an element after the current location of the specified iterator.
universe@499 230 *
universe@499 231 * The used iterator remains operational, but all other active iterators should
universe@499 232 * be considered invalidated.
universe@499 233 *
universe@499 234 * If \p iter is not a list iterator, the behavior is undefined.
universe@499 235 * If \p iter is a past-the-end iterator, the new element gets appended to the list.
universe@499 236 *
universe@499 237 * @param iter an iterator
universe@499 238 * @param elem the element to insert
universe@499 239 * @return zero on success, non-zero on memory allocation failure
universe@499 240 * @see cxListInsert()
universe@499 241 * @see cxListInsertBefore()
universe@499 242 */
universe@508 243 __attribute__((__nonnull__))
universe@499 244 static inline int cxListInsertAfter(
universe@499 245 CxIterator *iter,
universe@499 246 void const *elem
universe@499 247 ) {
universe@500 248 return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
universe@499 249 }
universe@499 250
universe@499 251 /**
universe@499 252 * Inserts an element before the current location of the specified iterator.
universe@499 253 *
universe@499 254 * The used iterator remains operational, but all other active iterators should
universe@499 255 * be considered invalidated.
universe@499 256 *
universe@499 257 * If \p iter is not a list iterator, the behavior is undefined.
universe@499 258 * If \p iter is a past-the-end iterator, the new element gets appended to the list.
universe@499 259 *
universe@499 260 * @param iter an iterator
universe@499 261 * @param elem the element to insert
universe@499 262 * @return zero on success, non-zero on memory allocation failure
universe@499 263 * @see cxListInsert()
universe@499 264 * @see cxListInsertAfter()
universe@499 265 */
universe@508 266 __attribute__((__nonnull__))
universe@499 267 static inline int cxListInsertBefore(
universe@499 268 CxIterator *iter,
universe@499 269 void const *elem
universe@499 270 ) {
universe@500 271 return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
universe@499 272 }
universe@499 273
universe@499 274 /**
universe@464 275 * Removes the element at the specified index.
universe@464 276 * @param list the list
universe@464 277 * @param index the index of the element
universe@464 278 * @return zero on success, non-zero if the index is out of bounds
universe@464 279 */
universe@508 280 __attribute__((__nonnull__))
universe@489 281 static inline int cxListRemove(
universe@500 282 CxList *list,
universe@489 283 size_t index
universe@489 284 ) {
universe@469 285 return list->cl->remove(list, index);
universe@469 286 }
universe@398 287
universe@464 288 /**
universe@464 289 * Returns a pointer to the element at the specified index.
universe@464 290 *
universe@464 291 * @param list the list
universe@464 292 * @param index the index of the element
universe@464 293 * @return a pointer to the element or \c NULL if the index is out of bounds
universe@464 294 */
universe@508 295 __attribute__((__nonnull__))
universe@489 296 static inline void *cxListAt(
universe@500 297 CxList *list,
universe@489 298 size_t index
universe@489 299 ) {
universe@469 300 return list->cl->at(list, index);
universe@469 301 }
universe@439 302
universe@464 303 /**
universe@494 304 * Returns an iterator pointing to the item at the specified index.
universe@494 305 *
universe@494 306 * The returned iterator is position-aware.
universe@494 307 *
universe@494 308 * If the index is out of range, a past-the-end iterator will be returned.
universe@494 309 *
universe@494 310 * @param list the list
universe@494 311 * @param index the index where the iterator shall point at
universe@494 312 * @return a new iterator
universe@494 313 */
universe@508 314 __attribute__((__nonnull__, __warn_unused_result__))
universe@494 315 static inline CxIterator cxListIterator(
universe@500 316 CxList *list,
universe@494 317 size_t index
universe@494 318 ) {
universe@494 319 return list->cl->iterator(list, index);
universe@494 320 }
universe@494 321
universe@494 322 /**
universe@494 323 * Returns an iterator pointing to the first item of the list.
universe@494 324 *
universe@494 325 * The returned iterator is position-aware.
universe@494 326 *
universe@494 327 * If the list is empty, a past-the-end iterator will be returned.
universe@494 328 *
universe@494 329 * @param list the list
universe@494 330 * @return a new iterator
universe@494 331 */
universe@508 332 __attribute__((__nonnull__, __warn_unused_result__))
universe@500 333 static inline CxIterator cxListBegin(CxList *list) {
universe@494 334 return list->cl->iterator(list, 0);
universe@494 335 }
universe@494 336
universe@494 337 /**
universe@464 338 * Returns the index of the first element that equals \p elem.
universe@464 339 *
universe@464 340 * Determining equality is performed by the list's comparator function.
universe@464 341 *
universe@464 342 * @param list the list
universe@464 343 * @param elem the element to find
universe@464 344 * @return the index of the element or \c (size+1) if the element is not found
universe@464 345 */
universe@508 346 __attribute__((__nonnull__))
universe@489 347 static inline size_t cxListFind(
universe@500 348 CxList *list,
universe@489 349 void const *elem
universe@489 350 ) {
universe@469 351 return list->cl->find(list, elem);
universe@469 352 }
universe@398 353
universe@464 354 /**
universe@469 355 * Sorts the list in place.
universe@469 356 *
universe@469 357 * \remark The underlying sort algorithm is implementation defined.
universe@469 358 *
universe@469 359 * @param list the list
universe@469 360 */
universe@508 361 __attribute__((__nonnull__))
universe@500 362 static inline void cxListSort(CxList *list) {
universe@469 363 list->cl->sort(list);
universe@469 364 }
universe@404 365
universe@488 366 /**
universe@490 367 * Reverses the order of the items.
universe@490 368 *
universe@490 369 * @param list the list
universe@490 370 */
universe@508 371 __attribute__((__nonnull__))
universe@500 372 static inline void cxListReverse(CxList *list) {
universe@490 373 list->cl->reverse(list);
universe@490 374 }
universe@490 375
universe@490 376 /**
universe@488 377 * Compares a list to another list of the same type.
universe@488 378 *
universe@488 379 * First, the list sizes are compared. If they match, the lists are compared element-wise.
universe@488 380 *
universe@488 381 * @param list the list
universe@488 382 * @param other the list to compare to
universe@488 383 * @return zero, if both lists are equal element wise, negative if the first list is smaller, zero if the first list is larger
universe@488 384 */
universe@508 385 __attribute__((__nonnull__))
universe@488 386 static inline int cxListCompare(
universe@500 387 CxList *list,
universe@500 388 CxList *other
universe@488 389 ) {
universe@488 390 return list->cl->compare(list, other);
universe@488 391 }
universe@488 392
universe@503 393 /**
universe@503 394 * Calls the list's destructor function for every element.
universe@503 395 * If CxList.autofree_content is \c true, the elements are automatically free'd
universe@503 396 * unless the content destructor function did not already do that.
universe@503 397 * Similarly, if CxList.autofree is \c true, the list structure is free'd, unless
universe@503 398 * the list destructor function did not already do that.
universe@503 399 *
universe@503 400 * This function itself is a destructor function for the CxList.
universe@503 401 *
universe@503 402 * @param list the list which contents shall be destroyed
universe@508 403 * @return \p list if the list structure has not been free'd during the process
universe@503 404 */
universe@503 405 __attribute__((__nonnull__))
universe@503 406 CxList *cxListDestroy(CxList *list);
universe@503 407
universe@415 408 #ifdef __cplusplus
universe@415 409 } /* extern "C" */
universe@415 410 #endif
universe@415 411
universe@393 412 #endif /* UCX_LIST_H */

mercurial