Simple interface for Mbed Cloud Client
Embed:
(wiki syntax)
Show/hide line numbers
ns_list.h
Go to the documentation of this file.
00001 /* 00002 * Copyright (c) 2014-2015 ARM Limited. All rights reserved. 00003 * SPDX-License-Identifier: Apache-2.0 00004 * Licensed under the Apache License, Version 2.0 (the License); you may 00005 * not use this file except in compliance with the License. 00006 * You may obtain a copy of the License at 00007 * 00008 * http://www.apache.org/licenses/LICENSE-2.0 00009 * 00010 * Unless required by applicable law or agreed to in writing, software 00011 * distributed under the License is distributed on an AS IS BASIS, WITHOUT 00012 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00013 * See the License for the specific language governing permissions and 00014 * limitations under the License. 00015 */ 00016 00017 #ifndef NS_LIST_H_ 00018 #define NS_LIST_H_ 00019 00020 #include "ns_types.h" 00021 00022 #ifdef __cplusplus 00023 extern "C" { 00024 #endif 00025 00026 /** \file 00027 * \brief Linked list support library 00028 * 00029 * The ns_list.h file provides a doubly-linked list/queue, providing O(1) 00030 * performance for all insertion/removal operations, and access to either 00031 * end of the list. 00032 * 00033 * Memory footprint is two pointers for the list head, and two pointers in each 00034 * list entry. It is similar in concept to BSD's TAILQ. 00035 * 00036 * Although the API is symmetrical and O(1) in both directions, due to internal 00037 * pointer design, it is *slightly* more efficient to insert at the end when 00038 * used as a queue, and to iterate forwards rather than backwards. 00039 * 00040 * Example of an entry type that can be stored to this list. 00041 * ~~~ 00042 * typedef struct example_entry 00043 * { 00044 * uint8_t *data; 00045 * uint32_t data_count; 00046 * ns_list_link_t link; 00047 * } 00048 * example_entry_t; 00049 * 00050 * static NS_LIST_HEAD(example_entry_t, link) my_list; 00051 * ns_list_init(&my_list); 00052 * ~~~ 00053 * OR 00054 * ~~~ 00055 * NS_LIST_HEAD(example_entry_t, link) my_list = NS_LIST_INIT(my_list); 00056 * ~~~ 00057 * OR 00058 * ~~~ 00059 * static NS_LIST_DEFINE(my_list, example_entry_t, link); 00060 * ~~~ 00061 * OR 00062 * ~~~ 00063 * typedef NS_LIST_HEAD(example_entry_t, link) example_list_t; 00064 * example_list_t NS_LIST_NAME_INIT(my_list); 00065 * ~~~ 00066 * NOTE: the link field SHALL NOT be accessed by the user. 00067 * 00068 * An entry can exist on multiple lists by having multiple link fields. 00069 * 00070 * All the list operations are implemented as macros, most of which are backed 00071 * by optionally-inline functions. The macros do not evaluate any arguments more 00072 * than once, unless documented. 00073 * 00074 * In macro documentation, `list_t` refers to a list type defined using 00075 * NS_LIST_HEAD(), and `entry_t` to the entry type that was passed to it. 00076 */ 00077 00078 /** \brief Underlying generic linked list head. 00079 * 00080 * Users should not use this type directly, but use the NS_LIST_HEAD() macro. 00081 */ 00082 typedef struct ns_list { 00083 void *first_entry; ///< Pointer to first entry, or NULL if list is empty 00084 void **last_nextptr; ///< Pointer to last entry's `next` pointer, or 00085 ///< to head's `first_entry` pointer if list is empty 00086 } ns_list_t; 00087 00088 /** \brief Declare a list head type 00089 * 00090 * This union stores the real list head, and also encodes as compile-time type 00091 * information the offset of the link pointer, and the type of the entry. 00092 * 00093 * Note that type information is compiler-dependent; this means 00094 * ns_list_get_first() could return either `void *`, or a pointer to the actual 00095 * entry type. So `ns_list_get_first()->data` is not a portable construct - 00096 * always assign returned entry pointers to a properly typed pointer variable. 00097 * This assignment will be then type-checked where the compiler supports it, and 00098 * will dereference correctly on compilers that don't support this extension. 00099 * ~~~ 00100 * NS_LIST_HEAD(example_entry_t, link) my_list; 00101 * 00102 * example_entry_t *entry = ns_list_get_first(&my_list); 00103 * do_something(entry->data); 00104 * ~~~ 00105 * Each use of this macro generates a new anonymous union, so these two lists 00106 * have different types: 00107 * ~~~ 00108 * NS_LIST_HEAD(example_entry_t, link) my_list1; 00109 * NS_LIST_HEAD(example_entry_t, link) my_list2; 00110 * ~~~ 00111 * If you need to use a list type in multiple places, eg as a function 00112 * parameter, use typedef: 00113 * ~~~ 00114 * typedef NS_LIST_HEAD(example_entry_t, link) example_list_t; 00115 * 00116 * void example_function(example_list_t *); 00117 * ~~~ 00118 */ 00119 #define NS_LIST_HEAD(entry_type, field) \ 00120 NS_LIST_HEAD_BY_OFFSET_(entry_type, offsetof(entry_type, field)) 00121 00122 /** \brief Declare a list head type for an incomplete entry type. 00123 * 00124 * This declares a list head, similarly to NS_LIST_HEAD(), but unlike that 00125 * this can be used in contexts where the entry type may be incomplete. 00126 * 00127 * To use this, the link pointer must be the first member in the 00128 * actual complete structure. This is NOT checked - the definition of the 00129 * element should probably test NS_STATIC_ASSERT(offsetof(type, link) == 0) 00130 * if outside users are known to be using NS_LIST_HEAD_INCOMPLETE(). 00131 * ~~~ 00132 * struct opaque; 00133 * NS_LIST_HEAD_INCOMPLETE(struct opaque) opaque_list; 00134 * ~~~ 00135 */ 00136 #define NS_LIST_HEAD_INCOMPLETE(entry_type) \ 00137 NS_LIST_HEAD_BY_OFFSET_(entry_type, 0) 00138 00139 /// \privatesection 00140 /** \brief Internal macro defining a list head, given the offset to the link pointer 00141 * The +1 allows for link_offset being 0 - we can't declare a 0-size array 00142 */ 00143 #define NS_LIST_HEAD_BY_OFFSET_(entry_type, link_offset) \ 00144 union \ 00145 { \ 00146 ns_list_t slist; \ 00147 NS_FUNNY_COMPARE_OK \ 00148 NS_STATIC_ASSERT(link_offset <= UINT_FAST8_MAX, "link offset too large") \ 00149 NS_FUNNY_COMPARE_RESTORE \ 00150 char (*offset)[link_offset + 1]; \ 00151 entry_type *type; \ 00152 } 00153 00154 /** \brief Get offset of link field in entry. 00155 * \return `(ns_list_offset_t)` The offset of the link field for entries on the specified list 00156 */ 00157 #define NS_LIST_OFFSET_(list) ((ns_list_offset_t) (sizeof *(list)->offset - 1)) 00158 00159 /** \brief Get the entry pointer type. 00160 * \def NS_LIST_PTR_TYPE_ 00161 * 00162 * \return An unqualified pointer type to an entry on the specified list. 00163 * 00164 * Only available if the compiler provides a "typeof" operator. 00165 */ 00166 #if defined __cplusplus && __cplusplus >= 201103L 00167 #define NS_LIST_PTR_TYPE_(list) decltype((list)->type) 00168 #elif defined __GNUC__ 00169 #define NS_LIST_PTR_TYPE_(list) __typeof__((list)->type) 00170 #endif 00171 00172 /** \brief Check for compatible pointer types 00173 * 00174 * This test will produce a diagnostic about a pointer mismatch on 00175 * the == inside the sizeof operator. For example ARM/Norcroft C gives the error: 00176 * 00177 * operand types are incompatible ("entry_t *" and "other_t *") 00178 */ 00179 #ifdef CPPCHECK 00180 #define NS_PTR_MATCH_(a, b, str) ((void) 0) 00181 #else 00182 #define NS_PTR_MATCH_(a, b, str) ((void) sizeof ((a) == (b))) 00183 #endif 00184 00185 /** \brief Internal macro to cast returned entry pointers to correct type. 00186 * 00187 * Not portable in C, alas. With GCC or C++11, the "get entry" macros return 00188 * correctly-typed pointers. Otherwise, the macros return `void *`. 00189 * 00190 * The attempt at a portable version would work if the C `?:` operator wasn't 00191 * broken - `x ? (t *) : (void *)` should really have type `(t *)` in C, but 00192 * it has type `(void *)`, which only makes sense for C++. The `?:` is left in, 00193 * in case some day it works. Some compilers may still warn if this is 00194 * assigned to a different type. 00195 */ 00196 #ifdef NS_LIST_PTR_TYPE_ 00197 #define NS_LIST_TYPECAST_(list, val) ((NS_LIST_PTR_TYPE_(list)) (val)) 00198 #else 00199 #define NS_LIST_TYPECAST_(list, val) (0 ? (list)->type : (val)) 00200 #endif 00201 00202 /** \brief Internal macro to check types of input entry pointer. */ 00203 #define NS_LIST_TYPECHECK_(list, entry) \ 00204 (NS_PTR_MATCH_((list)->type, (entry), "incorrect entry type for list"), (entry)) 00205 00206 /** \brief Type used to pass link offset to underlying functions 00207 * 00208 * We could use size_t, but it would be unnecessarily large on 8-bit systems, 00209 * where we can be (pretty) confident we won't have next pointers more than 00210 * 256 bytes into a structure. 00211 */ 00212 typedef uint_fast8_t ns_list_offset_t; 00213 00214 /// \publicsection 00215 /** \brief The type for the link member in the user's entry structure. 00216 * 00217 * Users should not access this member directly - just pass its name to the 00218 * list head macros. The funny prev pointer simplifies common operations 00219 * (eg insertion, removal), at the expense of complicating rare reverse iteration. 00220 * 00221 * NB - the list implementation relies on next being the first member. 00222 */ 00223 typedef struct ns_list_link { 00224 void *next; ///< Pointer to next entry, or NULL if none 00225 void **prev; ///< Pointer to previous entry's (or head's) next pointer 00226 } ns_list_link_t; 00227 00228 /** \brief "Poison" value placed in unattached entries' link pointers. 00229 * \internal What are good values for this? Platform dependent, maybe just NULL 00230 */ 00231 #define NS_LIST_POISON ((void *) 0xDEADBEEF) 00232 00233 /** \brief Initialiser for an entry's link member 00234 * 00235 * This initialiser is not required by the library, but a user may want an 00236 * initialiser to include in their own entry initialiser. See 00237 * ns_list_link_init() for more discussion. 00238 */ 00239 #define NS_LIST_LINK_INIT(name) \ 00240 NS_FUNNY_INTPTR_OK \ 00241 { NS_LIST_POISON, NS_LIST_POISON } \ 00242 NS_FUNNY_INTPTR_RESTORE 00243 00244 /** \hideinitializer \brief Initialise an entry's list link 00245 * 00246 * This "initialises" an unattached entry's link by filling the fields with 00247 * poison. This is optional, as unattached entries field pointers are not 00248 * meaningful, and it is not valid to call ns_list_get_next or similar on 00249 * an unattached entry. 00250 * 00251 * \param entry Pointer to an entry 00252 * \param field The name of the link member to initialise 00253 */ 00254 #define ns_list_link_init(entry, field) ns_list_link_init_(&(entry)->field) 00255 00256 /** \hideinitializer \brief Initialise a list 00257 * 00258 * Initialise a list head before use. A list head must be initialised using this 00259 * function or one of the NS_LIST_INIT()-type macros before use. A zero-initialised 00260 * list head is *not* valid. 00261 * 00262 * If used on a list containing existing entries, those entries will 00263 * become detached. (They are not modified, but their links are now effectively 00264 * undefined). 00265 * 00266 * \param list Pointer to a NS_LIST_HEAD() structure. 00267 */ 00268 #define ns_list_init(list) ns_list_init_(&(list)->slist) 00269 00270 /** \brief Initialiser for an empty list 00271 * 00272 * Usage in an enclosing initialiser: 00273 * ~~~ 00274 * static my_type_including_list_t x = { 00275 * "Something", 00276 * 23, 00277 * NS_LIST_INIT(x), 00278 * }; 00279 * ~~~ 00280 * NS_LIST_DEFINE() or NS_LIST_NAME_INIT() may provide a shorter alternative 00281 * in simpler cases. 00282 */ 00283 #define NS_LIST_INIT(name) { { NULL, &(name).slist.first_entry } } 00284 00285 /** \brief Name and initialiser for an empty list 00286 * 00287 * Usage: 00288 * ~~~ 00289 * list_t NS_LIST_NAME_INIT(foo); 00290 * ~~~ 00291 * acts as 00292 * ~~~ 00293 * list_t foo = { empty list }; 00294 * ~~~ 00295 * Also useful with designated initialisers: 00296 * ~~~ 00297 * .NS_LIST_NAME_INIT(foo), 00298 * ~~~ 00299 * acts as 00300 * ~~~ 00301 * .foo = { empty list }, 00302 * ~~~ 00303 */ 00304 #define NS_LIST_NAME_INIT(name) name = NS_LIST_INIT(name) 00305 00306 /** \brief Define a list, and initialise to empty. 00307 * 00308 * Usage: 00309 * ~~~ 00310 * static NS_LIST_DEFINE(my_list, entry_t, link); 00311 * ~~~ 00312 * acts as 00313 * ~~~ 00314 * static list_type my_list = { empty list }; 00315 * ~~~ 00316 */ 00317 #define NS_LIST_DEFINE(name, type, field) \ 00318 NS_LIST_HEAD(type, field) NS_LIST_NAME_INIT(name) 00319 00320 /** \hideinitializer \brief Add an entry to the start of the linked list. 00321 * 00322 * ns_list_add_to_end() is *slightly* more efficient than ns_list_add_to_start(). 00323 * 00324 * \param list `(list_t *)` Pointer to list. 00325 * \param entry `(entry_t * restrict)` Pointer to new entry to add. 00326 */ 00327 #define ns_list_add_to_start(list, entry) \ 00328 ns_list_add_to_start_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, entry)) 00329 00330 /** \hideinitializer \brief Add an entry to the end of the linked list. 00331 * 00332 * \param list `(list_t *)` Pointer to list. 00333 * \param entry `(entry_t * restrict)` Pointer to new entry to add. 00334 */ 00335 #define ns_list_add_to_end(list, entry) \ 00336 ns_list_add_to_end_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, entry)) 00337 00338 /** \hideinitializer \brief Add an entry before a specified entry. 00339 * 00340 * \param list `(list_t *)` Pointer to list. 00341 * \param before `(entry_t *)` Existing entry before which to place the new entry. 00342 * \param entry `(entry_t * restrict)` Pointer to new entry to add. 00343 */ 00344 #define ns_list_add_before(list, before, entry) \ 00345 ns_list_add_before_(NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, before), NS_LIST_TYPECHECK_(list, entry)) 00346 00347 /** \hideinitializer \brief Add an entry after a specified entry. 00348 * 00349 * ns_list_add_before() is *slightly* more efficient than ns_list_add_after(). 00350 * 00351 * \param list `(list_t *)` Pointer to list. 00352 * \param after `(entry_t *)` Existing entry after which to place the new entry. 00353 * \param entry `(entry_t * restrict)` Pointer to new entry to add. 00354 */ 00355 #define ns_list_add_after(list, after, entry) \ 00356 ns_list_add_after_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, after), NS_LIST_TYPECHECK_(list, entry)) 00357 00358 /** \brief Check if a list is empty. 00359 * 00360 * \param list `(const list_t *)` Pointer to list. 00361 * 00362 * \return `(bool)` true if the list is empty. 00363 */ 00364 #define ns_list_is_empty(list) ((bool) ((list)->slist.first_entry == NULL)) 00365 00366 /** \brief Get the first entry. 00367 * 00368 * \param list `(const list_t *)` Pointer to list. 00369 * 00370 * \return `(entry_t *)` Pointer to first entry. 00371 * \return NULL if list is empty. 00372 */ 00373 #define ns_list_get_first(list) NS_LIST_TYPECAST_(list, (list)->slist.first_entry) 00374 00375 /** \hideinitializer \brief Get the previous entry. 00376 * 00377 * \param list `(const list_t *)` Pointer to list. 00378 * \param current `(const entry_t *)` Pointer to current entry. 00379 * 00380 * \return `(entry_t *)` Pointer to previous entry. 00381 * \return NULL if current entry is first. 00382 */ 00383 #define ns_list_get_previous(list, current) \ 00384 NS_LIST_TYPECAST_(list, ns_list_get_previous_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, current))) 00385 00386 /** \hideinitializer \brief Get the next entry. 00387 * 00388 * \param list `(const list_t *)` Pointer to list. 00389 * \param current `(const entry_t *)` Pointer to current entry. 00390 * 00391 * \return `(entry_t *)` Pointer to next entry. 00392 * \return NULL if current entry is last. 00393 */ 00394 #define ns_list_get_next(list, current) \ 00395 NS_LIST_TYPECAST_(list, ns_list_get_next_(NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, current))) 00396 00397 /** \hideinitializer \brief Get the last entry. 00398 * 00399 * \param list `(const list_t *)` Pointer to list. 00400 * 00401 * \return `(entry_t *)` Pointer to last entry. 00402 * \return NULL if list is empty. 00403 */ 00404 #define ns_list_get_last(list) \ 00405 NS_LIST_TYPECAST_(list, ns_list_get_last_(&(list)->slist, NS_LIST_OFFSET_(list))) 00406 00407 /** \hideinitializer \brief Remove an entry. 00408 * 00409 * \param list `(list_t *)` Pointer to list. 00410 * \param entry `(entry_t *)` Entry on list to be removed. 00411 */ 00412 #define ns_list_remove(list, entry) \ 00413 ns_list_remove_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, entry)) 00414 00415 /** \hideinitializer \brief Replace an entry. 00416 * 00417 * \param list `(list_t *)` Pointer to list. 00418 * \param current `(entry_t *)` Existing entry on list to be replaced. 00419 * \param replacement `(entry_t * restrict)` New entry to be the replacement. 00420 */ 00421 #define ns_list_replace(list, current, replacement) \ 00422 ns_list_replace_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, current), NS_LIST_TYPECHECK_(list, replacement)) 00423 00424 /** \hideinitializer \brief Concatenate two lists. 00425 * 00426 * Attach the entries on the source list to the end of the destination 00427 * list, leaving the source list empty. 00428 * 00429 * \param dst `(list_t *)` Pointer to destination list. 00430 * \param src `(list_t *)` Pointer to source list. 00431 * 00432 */ 00433 #define ns_list_concatenate(dst, src) \ 00434 (NS_PTR_MATCH_(dst, src, "concatenating different list types"), \ 00435 ns_list_concatenate_(&(dst)->slist, &(src)->slist, NS_LIST_OFFSET_(src))) 00436 00437 /** \brief Iterate forwards over a list. 00438 * 00439 * Example: 00440 * ~~~ 00441 * ns_list_foreach(const my_entry_t, cur, &my_list) 00442 * { 00443 * printf("%s\n", cur->name); 00444 * } 00445 * ~~~ 00446 * Deletion of the current entry is not permitted as its next is checked after 00447 * running user code. 00448 * 00449 * The iteration pointer is declared inside the loop, using C99/C++, so it 00450 * is not accessible after the loop. This encourages good code style, and 00451 * matches the semantics of C++11's "ranged for", which only provides the 00452 * declaration form: 00453 * ~~~ 00454 * for (const my_entry_t cur : my_list) 00455 * ~~~ 00456 * If you need to see the value of the iteration pointer after a `break`, 00457 * you will need to assign it to a variable declared outside the loop before 00458 * breaking: 00459 * ~~~ 00460 * my_entry_t *match = NULL; 00461 * ns_list_foreach(my_entry_t, cur, &my_list) 00462 * { 00463 * if (cur->id == id) 00464 * { 00465 * match = cur; 00466 * break; 00467 * } 00468 * } 00469 * ~~~ 00470 * 00471 * The user has to specify the entry type for the pointer definition, as type 00472 * extraction from the list argument isn't portable. On the other hand, this 00473 * also permits const qualifiers, as in the example above, and serves as 00474 * documentation. The entry type will be checked against the list type where the 00475 * compiler supports it. 00476 * 00477 * \param type Entry type `([const] entry_t)`. 00478 * \param e Name for iteration pointer to be defined 00479 * inside the loop. 00480 * \param list `(const list_t *)` Pointer to list - evaluated multiple times. 00481 */ 00482 #define ns_list_foreach(type, e, list) \ 00483 for (type *e = ns_list_get_first(list); e; e = ns_list_get_next(list, e)) 00484 00485 /** \brief Iterate forwards over a list, where user may delete. 00486 * 00487 * As ns_list_foreach(), but deletion of current entry is permitted as its 00488 * next pointer is recorded before running user code. 00489 * 00490 * Example: 00491 * ~~~ 00492 * ns_list_foreach_safe(my_entry_t, cur, &my_list) 00493 * { 00494 * ns_list_remove(cur); 00495 * } 00496 * ~~~ 00497 * \param type Entry type `(entry_t)`. 00498 * \param e Name for iteration pointer to be defined 00499 * inside the loop. 00500 * \param list `(list_t *)` Pointer to list - evaluated multiple times. 00501 */ 00502 #define ns_list_foreach_safe(type, e, list) \ 00503 for (type *e = ns_list_get_first(list), *_next##e; \ 00504 e && (_next##e = ns_list_get_next(list, e), true); e = _next##e) 00505 00506 /** \brief Iterate backwards over a list. 00507 * 00508 * As ns_list_foreach(), but going backwards - see its documentation. 00509 * Iterating forwards is *slightly* more efficient. 00510 */ 00511 #define ns_list_foreach_reverse(type, e, list) \ 00512 for (type *e = ns_list_get_last(list); e; e = ns_list_get_previous(list, e)) 00513 00514 /** \brief Iterate backwards over a list, where user may delete. 00515 * 00516 * As ns_list_foreach_safe(), but going backwards - see its documentation. 00517 * Iterating forwards is *slightly* more efficient. 00518 */ 00519 #define ns_list_foreach_reverse_safe(type, e, list) \ 00520 for (type *e = ns_list_get_last(list), *_next##e; \ 00521 e && (_next##e = ns_list_get_previous(list, e), true); e = _next##e) 00522 00523 /** \hideinitializer \brief Count entries on a list 00524 * 00525 * Unlike other operations, this is O(n). Note: if list might contain over 00526 * 65535 entries, this function **must not** be used to get the entry count. 00527 * 00528 * \param list `(const list_t *)` Pointer to list. 00529 00530 * \return `(uint_fast16_t)` Number of entries that are stored in list. 00531 */ 00532 #define ns_list_count(list) ns_list_count_(&(list)->slist, NS_LIST_OFFSET_(list)) 00533 00534 /** \privatesection 00535 * Internal functions - designed to be accessed using corresponding macros above 00536 */ 00537 NS_INLINE void ns_list_init_(ns_list_t *list); 00538 NS_INLINE void ns_list_link_init_(ns_list_link_t *link); 00539 NS_INLINE void ns_list_add_to_start_(ns_list_t *list, ns_list_offset_t link_offset, void *restrict entry); 00540 NS_INLINE void ns_list_add_to_end_(ns_list_t *list, ns_list_offset_t link_offset, void *restrict entry); 00541 NS_INLINE void ns_list_add_before_(ns_list_offset_t link_offset, void *before, void *restrict entry); 00542 NS_INLINE void ns_list_add_after_(ns_list_t *list, ns_list_offset_t link_offset, void *after, void *restrict entry); 00543 NS_INLINE void *ns_list_get_next_(ns_list_offset_t link_offset, const void *current); 00544 NS_INLINE void *ns_list_get_previous_(const ns_list_t *list, ns_list_offset_t link_offset, const void *current); 00545 NS_INLINE void *ns_list_get_last_(const ns_list_t *list, ns_list_offset_t offset); 00546 NS_INLINE void ns_list_remove_(ns_list_t *list, ns_list_offset_t link_offset, void *entry); 00547 NS_INLINE void ns_list_replace_(ns_list_t *list, ns_list_offset_t link_offset, void *current, void *restrict replacement); 00548 NS_INLINE void ns_list_concatenate_(ns_list_t *dst, ns_list_t *src, ns_list_offset_t offset); 00549 NS_INLINE uint_fast16_t ns_list_count_(const ns_list_t *list, ns_list_offset_t link_offset); 00550 00551 /* Provide definitions, either for inlining, or for ns_list.c */ 00552 #if defined NS_ALLOW_INLINING || defined NS_LIST_FN 00553 #ifndef NS_LIST_FN 00554 #define NS_LIST_FN NS_INLINE 00555 #endif 00556 00557 /* Pointer to the link member in entry e */ 00558 #define NS_LIST_LINK_(e, offset) ((ns_list_link_t *)((char *)(e) + offset)) 00559 00560 /* Lvalue of the next link pointer in entry e */ 00561 #define NS_LIST_NEXT_(e, offset) (NS_LIST_LINK_(e, offset)->next) 00562 00563 /* Lvalue of the prev link pointer in entry e */ 00564 #define NS_LIST_PREV_(e, offset) (NS_LIST_LINK_(e, offset)->prev) 00565 00566 /* Convert a pointer to a link member back to the entry; 00567 * works for linkptr either being a ns_list_link_t pointer, or its next pointer, 00568 * as the next pointer is first in the ns_list_link_t */ 00569 #define NS_LIST_ENTRY_(linkptr, offset) ((void *)((char *)(linkptr) - offset)) 00570 00571 NS_LIST_FN void ns_list_init_(ns_list_t *list) 00572 { 00573 list->first_entry = NULL; 00574 list->last_nextptr = &list->first_entry; 00575 } 00576 00577 NS_LIST_FN void ns_list_link_init_(ns_list_link_t *link) 00578 { 00579 NS_FUNNY_INTPTR_OK 00580 link->next = NS_LIST_POISON; 00581 link->prev = NS_LIST_POISON; 00582 NS_FUNNY_INTPTR_RESTORE 00583 } 00584 00585 NS_LIST_FN void ns_list_add_to_start_(ns_list_t *list, ns_list_offset_t offset, void *restrict entry) 00586 { 00587 void *next; 00588 00589 NS_LIST_PREV_(entry, offset) = &list->first_entry; 00590 NS_LIST_NEXT_(entry, offset) = next = list->first_entry; 00591 00592 if (next) { 00593 NS_LIST_PREV_(next, offset) = &NS_LIST_NEXT_(entry, offset); 00594 } else { 00595 list->last_nextptr = &NS_LIST_NEXT_(entry, offset); 00596 } 00597 00598 list->first_entry = entry; 00599 } 00600 00601 NS_LIST_FN void ns_list_add_after_(ns_list_t *list, ns_list_offset_t offset, void *current, void *restrict entry) 00602 { 00603 void *next; 00604 00605 NS_LIST_PREV_(entry, offset) = &NS_LIST_NEXT_(current, offset); 00606 NS_LIST_NEXT_(entry, offset) = next = NS_LIST_NEXT_(current, offset); 00607 00608 if (next) { 00609 NS_LIST_PREV_(next, offset) = &NS_LIST_NEXT_(entry, offset); 00610 } else { 00611 list->last_nextptr = &NS_LIST_NEXT_(entry, offset); 00612 } 00613 00614 NS_LIST_NEXT_(current, offset) = entry; 00615 } 00616 00617 NS_LIST_FN void ns_list_add_before_(ns_list_offset_t offset, void *current, void *restrict entry) 00618 { 00619 void **prev_nextptr; 00620 00621 NS_LIST_NEXT_(entry, offset) = current; 00622 NS_LIST_PREV_(entry, offset) = prev_nextptr = NS_LIST_PREV_(current, offset); 00623 *prev_nextptr = entry; 00624 NS_LIST_PREV_(current, offset) = &NS_LIST_NEXT_(entry, offset); 00625 } 00626 00627 NS_LIST_FN void ns_list_add_to_end_(ns_list_t *list, ns_list_offset_t offset, void *restrict entry) 00628 { 00629 void **prev_nextptr; 00630 00631 NS_LIST_NEXT_(entry, offset) = NULL; 00632 NS_LIST_PREV_(entry, offset) = prev_nextptr = list->last_nextptr; 00633 *prev_nextptr = entry; 00634 list->last_nextptr = &NS_LIST_NEXT_(entry, offset); 00635 } 00636 00637 NS_LIST_FN void *ns_list_get_next_(ns_list_offset_t offset, const void *current) 00638 { 00639 return NS_LIST_NEXT_(current, offset); 00640 } 00641 00642 NS_LIST_FN void *ns_list_get_previous_(const ns_list_t *list, ns_list_offset_t offset, const void *current) 00643 { 00644 if (current == list->first_entry) { 00645 return NULL; 00646 } 00647 00648 // Tricky. We don't have a direct previous pointer, but a pointer to the 00649 // pointer that points to us - ie &head->first_entry OR &{prev}->next. 00650 // This makes life easier on insertion and removal, but this is where we 00651 // pay the price. 00652 00653 // We have to check manually for being the first entry above, so we know it's 00654 // a real link's next pointer. Then next is the first field of 00655 // ns_list_link_t, so we can use the normal offset value. 00656 00657 return NS_LIST_ENTRY_(NS_LIST_PREV_(current, offset), offset); 00658 } 00659 00660 NS_LIST_FN void *ns_list_get_last_(const ns_list_t *list, ns_list_offset_t offset) 00661 { 00662 if (!list->first_entry) { 00663 return NULL; 00664 } 00665 00666 // See comments in ns_list_get_previous_() 00667 return NS_LIST_ENTRY_(list->last_nextptr, offset); 00668 } 00669 00670 NS_LIST_FN void ns_list_remove_(ns_list_t *list, ns_list_offset_t offset, void *removed) 00671 { 00672 void *next; 00673 void **prev_nextptr; 00674 00675 next = NS_LIST_NEXT_(removed, offset); 00676 prev_nextptr = NS_LIST_PREV_(removed, offset); 00677 if (next) { 00678 NS_LIST_PREV_(next, offset) = prev_nextptr; 00679 } else { 00680 list->last_nextptr = prev_nextptr; 00681 } 00682 *prev_nextptr = next; 00683 00684 ns_list_link_init_(NS_LIST_LINK_(removed, offset)); 00685 } 00686 00687 NS_LIST_FN void ns_list_replace_(ns_list_t *list, ns_list_offset_t offset, void *current, void *restrict replacement) 00688 { 00689 void *next; 00690 void **prev_nextptr; 00691 00692 NS_LIST_PREV_(replacement, offset) = prev_nextptr = NS_LIST_PREV_(current, offset); 00693 NS_LIST_NEXT_(replacement, offset) = next = NS_LIST_NEXT_(current, offset); 00694 00695 if (next) { 00696 NS_LIST_PREV_(next, offset) = &NS_LIST_NEXT_(replacement, offset); 00697 } else { 00698 list->last_nextptr = &NS_LIST_NEXT_(replacement, offset); 00699 } 00700 *prev_nextptr = replacement; 00701 00702 ns_list_link_init_(NS_LIST_LINK_(current, offset)); 00703 } 00704 00705 NS_LIST_FN void ns_list_concatenate_(ns_list_t *dst, ns_list_t *src, ns_list_offset_t offset) 00706 { 00707 ns_list_link_t *src_first; 00708 00709 src_first = src->first_entry; 00710 if (!src_first) { 00711 return; 00712 } 00713 00714 *dst->last_nextptr = src_first; 00715 NS_LIST_PREV_(src_first, offset) = dst->last_nextptr; 00716 dst->last_nextptr = src->last_nextptr; 00717 00718 ns_list_init_(src); 00719 } 00720 00721 NS_LIST_FN uint_fast16_t ns_list_count_(const ns_list_t *list, ns_list_offset_t offset) 00722 { 00723 uint_fast16_t count = 0; 00724 00725 for (void *p = list->first_entry; p; p = NS_LIST_NEXT_(p, offset)) { 00726 count++; 00727 } 00728 00729 return count; 00730 } 00731 #endif /* defined NS_ALLOW_INLINING || defined NS_LIST_FN */ 00732 00733 #ifdef __cplusplus 00734 } 00735 #endif 00736 00737 #endif /* NS_LIST_H_ */ 00738
Generated on Tue Jul 12 2022 19:01:35 by 1.7.2