ns_list.h

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