1 /*************************************************************************************************** 2 3 Zyan Core Library (Zycore-C) 4 5 Original Author : Florian Bernd 6 7 * Permission is hereby granted, free of charge, to any person obtaining a copy 8 * of this software and associated documentation files (the "Software"), to deal 9 * in the Software without restriction, including without limitation the rights 10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 11 * copies of the Software, and to permit persons to whom the Software is 12 * furnished to do so, subject to the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be included in all 15 * copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 23 * SOFTWARE. 24 25 ***************************************************************************************************/ 26 27 /** 28 * @file 29 * Implements a doubly linked list. 30 */ 31 32 #ifndef ZYCORE_LIST_H 33 #define ZYCORE_LIST_H 34 35 #include <Zycore/Allocator.h> 36 #include <Zycore/Object.h> 37 #include <Zycore/Status.h> 38 #include <Zycore/Types.h> 39 40 #ifdef __cplusplus 41 extern "C" { 42 #endif 43 44 /* ============================================================================================== */ 45 /* Enums and types */ 46 /* ============================================================================================== */ 47 48 /** 49 * Defines the `ZyanListNode` struct. 50 * 51 * All fields in this struct should be considered as "private". Any changes may lead to unexpected 52 * behavior. 53 */ 54 typedef struct ZyanListNode_ 55 { 56 /** 57 * A pointer to the previous list node. 58 */ 59 struct ZyanListNode_* prev; 60 /** 61 * A pointer to the next list node. 62 */ 63 struct ZyanListNode_* next; 64 } ZyanListNode; 65 66 /** 67 * Defines the `ZyanList` struct. 68 * 69 * All fields in this struct should be considered as "private". Any changes may lead to unexpected 70 * behavior. 71 */ 72 typedef struct ZyanList_ 73 { 74 /** 75 * The memory allocator. 76 */ 77 ZyanAllocator* allocator; 78 /** 79 * The current number of elements in the list. 80 */ 81 ZyanUSize size; 82 /** 83 * The size of a single element in bytes. 84 */ 85 ZyanUSize element_size; 86 /** 87 * The element destructor callback. 88 */ 89 ZyanMemberProcedure destructor; 90 /** 91 * The head node. 92 */ 93 ZyanListNode* head; 94 /** 95 * The tail node. 96 */ 97 ZyanListNode* tail; 98 /** 99 * The data buffer. 100 * 101 * Only used for instances created by `ZyanListInitCustomBuffer`. 102 */ 103 void* buffer; 104 /** 105 * The data buffer capacity (number of bytes). 106 * 107 * Only used for instances created by `ZyanListInitCustomBuffer`. 108 */ 109 ZyanUSize capacity; 110 /** 111 * The first unused node. 112 * 113 * When removing a node, the first-unused value is updated to point at the removed node and the 114 * next node of the removed node will be updated to point at the old first-unused node. 115 * 116 * When appending the memory of the first unused-node is recycled to store the new node. The 117 * value of the first-unused node is then updated to point at the reused nodes next node. 118 * 119 * If the first-unused value is `ZYAN_NULL`, any new node will be "allocated" behind the tail 120 * node (if there is enough space left in the fixed size buffer). 121 * 122 * Only used for instances created by `ZyanListInitCustomBuffer`. 123 */ 124 ZyanListNode* first_unused; 125 } ZyanList; 126 127 /* ============================================================================================== */ 128 /* Macros */ 129 /* ============================================================================================== */ 130 131 /* ---------------------------------------------------------------------------------------------- */ 132 /* General */ 133 /* ---------------------------------------------------------------------------------------------- */ 134 135 /** 136 * Defines an uninitialized `ZyanList` instance. 137 */ 138 #define ZYAN_LIST_INITIALIZER \ 139 { \ 140 /* allocator */ ZYAN_NULL, \ 141 /* size */ 0, \ 142 /* element_size */ 0, \ 143 /* head */ ZYAN_NULL, \ 144 /* destructor */ ZYAN_NULL, \ 145 /* tail */ ZYAN_NULL, \ 146 /* buffer */ ZYAN_NULL, \ 147 /* capacity */ 0, \ 148 /* first_unused */ ZYAN_NULL \ 149 } 150 151 /* ---------------------------------------------------------------------------------------------- */ 152 /* Helper macros */ 153 /* ---------------------------------------------------------------------------------------------- */ 154 155 /** 156 * Returns the data value of the given `node`. 157 * 158 * @param type The desired value type. 159 * @param node A pointer to the `ZyanListNode` struct. 160 * 161 * @result The data value of the given `node`. 162 * 163 * Note that this function is unsafe and might dereference a null-pointer. 164 */ 165 #ifdef __cplusplus 166 #define ZYAN_LIST_GET(type, node) \ 167 (*reinterpret_cast<const type*>(ZyanListGetNodeData(node))) 168 #else 169 #define ZYAN_LIST_GET(type, node) \ 170 (*(const type*)ZyanListGetNodeData(node)) 171 #endif 172 173 /* ---------------------------------------------------------------------------------------------- */ 174 175 /* ============================================================================================== */ 176 /* Exported functions */ 177 /* ============================================================================================== */ 178 179 /* ---------------------------------------------------------------------------------------------- */ 180 /* Constructor and destructor */ 181 /* ---------------------------------------------------------------------------------------------- */ 182 183 #ifndef ZYAN_NO_LIBC 184 185 /** 186 * Initializes the given `ZyanList` instance. 187 * 188 * @param list A pointer to the `ZyanList` instance. 189 * @param element_size The size of a single element in bytes. 190 * @param destructor A destructor callback that is invoked every time an item is deleted, or 191 * `ZYAN_NULL` if not needed. 192 * 193 * @return A zyan status code. 194 * 195 * The memory for the list elements is dynamically allocated by the default allocator. 196 * 197 * Finalization with `ZyanListDestroy` is required for all instances created by this function. 198 */ 199 ZYCORE_EXPORT ZYAN_REQUIRES_LIBC ZyanStatus ZyanListInit(ZyanList* list, ZyanUSize element_size, 200 ZyanMemberProcedure destructor); 201 202 #endif // ZYAN_NO_LIBC 203 204 /** 205 * Initializes the given `ZyanList` instance and sets a custom `allocator`. 206 * 207 * @param list A pointer to the `ZyanList` instance. 208 * @param element_size The size of a single element in bytes. 209 * @param destructor A destructor callback that is invoked every time an item is deleted, or 210 * `ZYAN_NULL` if not needed. 211 * @param allocator A pointer to a `ZyanAllocator` instance. 212 * 213 * @return A zyan status code. 214 * 215 * Finalization with `ZyanListDestroy` is required for all instances created by this function. 216 */ 217 ZYCORE_EXPORT ZyanStatus ZyanListInitEx(ZyanList* list, ZyanUSize element_size, 218 ZyanMemberProcedure destructor, ZyanAllocator* allocator); 219 220 /** 221 * Initializes the given `ZyanList` instance and configures it to use a custom user 222 * defined buffer with a fixed size. 223 * 224 * @param list A pointer to the `ZyanList` instance. 225 * @param element_size The size of a single element in bytes. 226 * @param destructor A destructor callback that is invoked every time an item is deleted, or 227 * `ZYAN_NULL` if not needed. 228 * @param buffer A pointer to the buffer that is used as storage for the elements. 229 * @param capacity The maximum capacity (number of bytes) of the buffer including the 230 * space required for the list-nodes. 231 * 232 * @return A zyan status code. 233 * 234 * The buffer capacity required to store `n` elements of type `T` is be calculated by: 235 * `size = n * sizeof(ZyanListNode) + n * sizeof(T)` 236 * 237 * Finalization is not required for instances created by this function. 238 */ 239 ZYCORE_EXPORT ZyanStatus ZyanListInitCustomBuffer(ZyanList* list, ZyanUSize element_size, 240 ZyanMemberProcedure destructor, void* buffer, ZyanUSize capacity); 241 242 /** 243 * Destroys the given `ZyanList` instance. 244 * 245 * @param list A pointer to the `ZyanList` instance. 246 * 247 * @return A zyan status code. 248 */ 249 ZYCORE_EXPORT ZyanStatus ZyanListDestroy(ZyanList* list); 250 251 /* ---------------------------------------------------------------------------------------------- */ 252 /* Duplication */ 253 /* ---------------------------------------------------------------------------------------------- */ 254 255 #ifndef ZYAN_NO_LIBC 256 257 /** 258 * Initializes a new `ZyanList` instance by duplicating an existing list. 259 * 260 * @param destination A pointer to the (uninitialized) destination `ZyanList` instance. 261 * @param source A pointer to the source list. 262 * 263 * @return A zyan status code. 264 * 265 * The memory for the list is dynamically allocated by the default allocator. 266 * 267 * Finalization with `ZyanListDestroy` is required for all instances created by this function. 268 */ 269 ZYCORE_EXPORT ZYAN_REQUIRES_LIBC ZyanStatus ZyanListDuplicate(ZyanList* destination, 270 const ZyanList* source); 271 272 #endif // ZYAN_NO_LIBC 273 274 /** 275 * Initializes a new `ZyanList` instance by duplicating an existing list and sets a 276 * custom `allocator`. 277 * 278 * @param destination A pointer to the (uninitialized) destination `ZyanList` instance. 279 * @param source A pointer to the source list. 280 * @param allocator A pointer to a `ZyanAllocator` instance. 281 * 282 * @return A zyan status code. 283 284 * Finalization with `ZyanListDestroy` is required for all instances created by this function. 285 */ 286 ZYCORE_EXPORT ZyanStatus ZyanListDuplicateEx(ZyanList* destination, const ZyanList* source, 287 ZyanAllocator* allocator); 288 289 /** 290 * Initializes a new `ZyanList` instance by duplicating an existing list and 291 * configures it to use a custom user defined buffer with a fixed size. 292 * 293 * @param destination A pointer to the (uninitialized) destination `ZyanList` instance. 294 * @param source A pointer to the source list. 295 * @param buffer A pointer to the buffer that is used as storage for the elements. 296 * @param capacity The maximum capacity (number of bytes) of the buffer including the 297 * space required for the list-nodes. 298 299 * This function will fail, if the capacity of the buffer is not sufficient 300 * to store all elements of the source list. 301 * 302 * @return A zyan status code. 303 * 304 * The buffer capacity required to store `n` elements of type `T` is be calculated by: 305 * `size = n * sizeof(ZyanListNode) + n * sizeof(T)` 306 * 307 * Finalization is not required for instances created by this function. 308 */ 309 ZYCORE_EXPORT ZyanStatus ZyanListDuplicateCustomBuffer(ZyanList* destination, 310 const ZyanList* source, void* buffer, ZyanUSize capacity); 311 312 /* ---------------------------------------------------------------------------------------------- */ 313 /* Item access */ 314 /* ---------------------------------------------------------------------------------------------- */ 315 316 /** 317 * Returns a pointer to the first `ZyanListNode` struct of the given list. 318 * 319 * @param list A pointer to the `ZyanList` instance. 320 * @param node Receives a pointer to the first `ZyanListNode` struct of the list. 321 * 322 * @return A zyan status code. 323 */ 324 ZYCORE_EXPORT ZyanStatus ZyanListGetHeadNode(const ZyanList* list, const ZyanListNode** node); 325 326 /** 327 * Returns a pointer to the last `ZyanListNode` struct of the given list. 328 * 329 * @param list A pointer to the `ZyanList` instance. 330 * @param node Receives a pointer to the last `ZyanListNode` struct of the list. 331 * 332 * @return A zyan status code. 333 */ 334 ZYCORE_EXPORT ZyanStatus ZyanListGetTailNode(const ZyanList* list, const ZyanListNode** node); 335 336 /** 337 * Receives a pointer to the previous `ZyanListNode` struct linked to the passed one. 338 * 339 * @param node Receives a pointer to the previous `ZyanListNode` struct linked to the passed 340 * one. 341 * 342 * @return A zyan status code. 343 */ 344 ZYCORE_EXPORT ZyanStatus ZyanListGetPrevNode(const ZyanListNode** node); 345 346 /** 347 * Receives a pointer to the next `ZyanListNode` struct linked to the passed one. 348 * 349 * @param node Receives a pointer to the next `ZyanListNode` struct linked to the passed one. 350 * 351 * @return A zyan status code. 352 */ 353 ZYCORE_EXPORT ZyanStatus ZyanListGetNextNode(const ZyanListNode** node); 354 355 /** 356 * Returns a constant pointer to the data of the given `node`. 357 * 358 * @param node A pointer to the `ZyanListNode` struct. 359 * 360 * @return A constant pointer to the the data of the given `node` or `ZYAN_NULL`, if an error 361 * occured. 362 * 363 * Take a look at `ZyanListGetNodeDataEx`, if you need a function that returns a zyan status code. 364 */ 365 ZYCORE_EXPORT const void* ZyanListGetNodeData(const ZyanListNode* node); 366 367 /** 368 * Returns a constant pointer to the data of the given `node`.. 369 * 370 * @param node A pointer to the `ZyanListNode` struct. 371 * @param value Receives a constant pointer to the data of the given `node`. 372 * 373 * Take a look at `ZyanListGetNodeData`, if you need a function that directly returns a pointer. 374 * 375 * @return A zyan status code. 376 */ 377 ZYCORE_EXPORT ZyanStatus ZyanListGetNodeDataEx(const ZyanListNode* node, const void** value); 378 379 /** 380 * Returns a mutable pointer to the data of the given `node`. 381 * 382 * @param node A pointer to the `ZyanListNode` struct. 383 * 384 * @return A mutable pointer to the the data of the given `node` or `ZYAN_NULL`, if an error 385 * occured. 386 * 387 * Take a look at `ZyanListGetPointerMutableEx` instead, if you need a function that returns a 388 * zyan status code. 389 */ 390 ZYCORE_EXPORT void* ZyanListGetNodeDataMutable(const ZyanListNode* node); 391 392 /** 393 * Returns a mutable pointer to the data of the given `node`.. 394 * 395 * @param node A pointer to the `ZyanListNode` struct. 396 * @param value Receives a mutable pointer to the data of the given `node`. 397 * 398 * Take a look at `ZyanListGetNodeDataMutable`, if you need a function that directly returns a 399 * pointer. 400 * 401 * @return A zyan status code. 402 */ 403 ZYCORE_EXPORT ZyanStatus ZyanListGetNodeDataMutableEx(const ZyanListNode* node, void** value); 404 405 /** 406 * Assigns a new data value to the given `node`. 407 * 408 * @param list A pointer to the `ZyanList` instance. 409 * @param node A pointer to the `ZyanListNode` struct. 410 * @param value The value to assign. 411 * 412 * @return A zyan status code. 413 */ 414 ZYCORE_EXPORT ZyanStatus ZyanListSetNodeData(const ZyanList* list, const ZyanListNode* node, 415 const void* value); 416 417 /* ---------------------------------------------------------------------------------------------- */ 418 /* Insertion */ 419 /* ---------------------------------------------------------------------------------------------- */ 420 421 /** 422 * Adds a new `item` to the end of the list. 423 * 424 * @param list A pointer to the `ZyanList` instance. 425 * @param item A pointer to the item to add. 426 * 427 * @return A zyan status code. 428 */ 429 ZYCORE_EXPORT ZyanStatus ZyanListPushBack(ZyanList* list, const void* item); 430 431 /** 432 * Adds a new `item` to the beginning of the list. 433 * 434 * @param list A pointer to the `ZyanList` instance. 435 * @param item A pointer to the item to add. 436 * 437 * @return A zyan status code. 438 */ 439 ZYCORE_EXPORT ZyanStatus ZyanListPushFront(ZyanList* list, const void* item); 440 441 /** 442 * Constructs an `item` in-place at the end of the list. 443 * 444 * @param list A pointer to the `ZyanList` instance. 445 * @param item Receives a pointer to the new item. 446 * @param constructor The constructor callback or `ZYAN_NULL`. The new item will be in 447 * undefined state, if no constructor was passed. 448 * 449 * @return A zyan status code. 450 */ 451 ZYCORE_EXPORT ZyanStatus ZyanListEmplaceBack(ZyanList* list, void** item, 452 ZyanMemberFunction constructor); 453 454 /** 455 * Constructs an `item` in-place at the beginning of the list. 456 * 457 * @param list A pointer to the `ZyanList` instance. 458 * @param item Receives a pointer to the new item. 459 * @param constructor The constructor callback or `ZYAN_NULL`. The new item will be in 460 * undefined state, if no constructor was passed. 461 * 462 * @return A zyan status code. 463 */ 464 ZYCORE_EXPORT ZyanStatus ZyanListEmplaceFront(ZyanList* list, void** item, 465 ZyanMemberFunction constructor); 466 467 /* ---------------------------------------------------------------------------------------------- */ 468 /* Deletion */ 469 /* ---------------------------------------------------------------------------------------------- */ 470 471 /** 472 * Removes the last element of the list. 473 * 474 * @param list A pointer to the `ZyanList` instance. 475 * 476 * @return A zyan status code. 477 */ 478 ZYCORE_EXPORT ZyanStatus ZyanListPopBack(ZyanList* list); 479 480 /** 481 * Removes the firstelement of the list. 482 * 483 * @param list A pointer to the `ZyanList` instance. 484 * 485 * @return A zyan status code. 486 */ 487 ZYCORE_EXPORT ZyanStatus ZyanListPopFront(ZyanList* list); 488 489 /** 490 * Removes the given `node` from the list. 491 * 492 * @param list A pointer to the `ZyanList` instance. 493 * @param node A pointer to the `ZyanListNode` struct. 494 * 495 * @return A zyan status code. 496 */ 497 ZYCORE_EXPORT ZyanStatus ZyanListRemove(ZyanList* list, const ZyanListNode* node); 498 499 /** 500 * Removes multiple nodes from the list. 501 * 502 * @param list A pointer to the `ZyanList` instance. 503 * @param first A pointer to the first node. 504 * @param last A pointer to the last node. 505 * 506 * @return A zyan status code. 507 */ 508 ZYCORE_EXPORT ZyanStatus ZyanListRemoveRange(ZyanList* list, const ZyanListNode* first, 509 const ZyanListNode* last); 510 511 /** 512 * Erases all elements of the list. 513 * 514 * @param list A pointer to the `ZyanList` instance. 515 * 516 * @return A zyan status code. 517 */ 518 ZYCORE_EXPORT ZyanStatus ZyanListClear(ZyanList* list); 519 520 /* ---------------------------------------------------------------------------------------------- */ 521 /* Searching */ 522 /* ---------------------------------------------------------------------------------------------- */ 523 524 // TODO: 525 526 /* ---------------------------------------------------------------------------------------------- */ 527 /* Memory management */ 528 /* ---------------------------------------------------------------------------------------------- */ 529 530 /** 531 * Resizes the given `ZyanList` instance. 532 * 533 * @param list A pointer to the `ZyanList` instance. 534 * @param size The new size of the list. 535 * 536 * @return A zyan status code. 537 */ 538 ZYCORE_EXPORT ZyanStatus ZyanListResize(ZyanList* list, ZyanUSize size); 539 540 /** 541 * Resizes the given `ZyanList` instance. 542 * 543 * @param list A pointer to the `ZyanList` instance. 544 * @param size The new size of the list. 545 * @param initializer A pointer to a value to be used as initializer for new items. 546 * 547 * @return A zyan status code. 548 */ 549 ZYCORE_EXPORT ZyanStatus ZyanListResizeEx(ZyanList* list, ZyanUSize size, const void* initializer); 550 551 /* ---------------------------------------------------------------------------------------------- */ 552 /* Information */ 553 /* ---------------------------------------------------------------------------------------------- */ 554 555 /** 556 * Returns the current size of the list. 557 * 558 * @param list A pointer to the `ZyanList` instance. 559 * @param size Receives the size of the list. 560 * 561 * @return A zyan status code. 562 */ 563 ZYCORE_EXPORT ZyanStatus ZyanListGetSize(const ZyanList* list, ZyanUSize* size); 564 565 /* ---------------------------------------------------------------------------------------------- */ 566 567 /* ============================================================================================== */ 568 569 #ifdef __cplusplus 570 } 571 #endif 572 573 #endif /* ZYCORE_VECTOR_H */ 574