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