![](/media/cache/profiles/debfdc81854eac26ec993b55a659c6e1.jpg.50x50_q85.jpg)
mbed client lightswitch demo
Dependencies: mbed Socket lwip-eth lwip-sys lwip
Fork of mbed-client-classic-example-lwip by
Diff: nanostack-libservice/mbed-client-libservice/ns_list.h
- Revision:
- 11:cada08fc8a70
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/nanostack-libservice/mbed-client-libservice/ns_list.h Thu Jun 09 17:08:36 2016 +0000 @@ -0,0 +1,736 @@ +/* + * Copyright (c) 2014-2015 ARM Limited. All rights reserved. + * SPDX-License-Identifier: Apache-2.0 + * Licensed under the Apache License, Version 2.0 (the License); you may + * not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an AS IS BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef NS_LIST_H_ +#define NS_LIST_H_ + +#include "ns_types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** \file + * \brief Linked list support library + * + * The ns_list.h file provides a doubly-linked list/queue, providing O(1) + * performance for all insertion/removal operations, and access to either + * end of the list. + * + * Memory footprint is two pointers for the list head, and two pointers in each + * list entry. It is similar in concept to BSD's TAILQ. + * + * Although the API is symmetrical and O(1) in both directions, due to internal + * pointer design, it is *slightly* more efficient to insert at the end when + * used as a queue, and to iterate forwards rather than backwards. + * + * Example of an entry type that can be stored to this list. + * ~~~ + * typedef struct example_entry + * { + * uint8_t *data; + * uint32_t data_count; + * ns_list_link_t link; + * } + * example_entry_t; + * + * static NS_LIST_HEAD(example_entry_t, link) my_list; + * ns_list_init(&my_list); + * ~~~ + * OR + * ~~~ + * NS_LIST_HEAD(example_entry_t, link) my_list = NS_LIST_INIT(my_list); + * ~~~ + * OR + * ~~~ + * static NS_LIST_DEFINE(my_list, example_entry_t, link); + * ~~~ + * OR + * ~~~ + * typedef NS_LIST_HEAD(example_entry_t, link) example_list_t; + * example_list_t NS_LIST_NAME_INIT(my_list); + * ~~~ + * NOTE: the link field SHALL NOT be accessed by the user. + * + * An entry can exist on multiple lists by having multiple link fields. + * + * All the list operations are implemented as macros, most of which are backed + * by optionally-inline functions. The macros do not evaluate any arguments more + * than once, unless documented. + * + * In macro documentation, `list_t` refers to a list type defined using + * NS_LIST_HEAD(), and `entry_t` to the entry type that was passed to it. + */ + +/** \brief Underlying generic linked list head. + * + * Users should not use this type directly, but use the NS_LIST_HEAD() macro. + */ +typedef struct ns_list { + void *first_entry; ///< Pointer to first entry, or NULL if list is empty + void **last_nextptr; ///< Pointer to last entry's `next` pointer, or + ///< to head's `first_entry` pointer if list is empty +} ns_list_t; + +/** \brief Declare a list head type + * + * This union stores the real list head, and also encodes as compile-time type + * information the offset of the link pointer, and the type of the entry. + * + * Note that type information is compiler-dependent; this means + * ns_list_get_first() could return either `void *`, or a pointer to the actual + * entry type. So `ns_list_get_first()->data` is not a portable construct - + * always assign returned entry pointers to a properly typed pointer variable. + * This assignment will be then type-checked where the compiler supports it, and + * will dereference correctly on compilers that don't support this extension. + * ~~~ + * NS_LIST_HEAD(example_entry_t, link) my_list; + * + * example_entry_t *entry = ns_list_get_first(&my_list); + * do_something(entry->data); + * ~~~ + * Each use of this macro generates a new anonymous union, so these two lists + * have different types: + * ~~~ + * NS_LIST_HEAD(example_entry_t, link) my_list1; + * NS_LIST_HEAD(example_entry_t, link) my_list2; + * ~~~ + * If you need to use a list type in multiple places, eg as a function + * parameter, use typedef: + * ~~~ + * typedef NS_LIST_HEAD(example_entry_t, link) example_list_t; + * + * void example_function(example_list_t *); + * ~~~ + */ +#define NS_LIST_HEAD(entry_type, field) \ + NS_LIST_HEAD_BY_OFFSET_(entry_type, offsetof(entry_type, field)) + +/** \brief Declare a list head type for an incomplete entry type. + * + * This declares a list head, similarly to NS_LIST_HEAD(), but unlike that + * this can be used in contexts where the entry type may be incomplete. + * + * To use this, the link pointer must be the first member in the + * actual complete structure. This is NOT checked - the definition of the + * element should probably test NS_STATIC_ASSERT(offsetof(type, link) == 0) + * if outside users are known to be using NS_LIST_HEAD_INCOMPLETE(). + * ~~~ + * struct opaque; + * NS_LIST_HEAD_INCOMPLETE(struct opaque) opaque_list; + * ~~~ + */ +#define NS_LIST_HEAD_INCOMPLETE(entry_type) \ + NS_LIST_HEAD_BY_OFFSET_(entry_type, 0) + +/// \privatesection +/** \brief Internal macro defining a list head, given the offset to the link pointer + * The +1 allows for link_offset being 0 - we can't declare a 0-size array + */ +#define NS_LIST_HEAD_BY_OFFSET_(entry_type, link_offset) \ +union \ +{ \ + ns_list_t slist; \ + NS_STATIC_ASSERT(link_offset <= UINT_FAST8_MAX, "link offset too large") \ + char (*offset)[link_offset + 1]; \ + entry_type *type; \ +} + +/** \brief Get offset of link field in entry. + * \return `(ns_list_offset_t)` The offset of the link field for entries on the specified list + */ +#define NS_LIST_OFFSET_(list) ((ns_list_offset_t) (sizeof *(list)->offset - 1)) + +/** \brief Get the entry pointer type. + * \def NS_LIST_PTR_TYPE_ + * + * \return An unqualified pointer type to an entry on the specified list. + * + * Only available if the compiler provides a "typeof" operator. + */ +#if defined __cplusplus && __cplusplus >= 201103L +#define NS_LIST_PTR_TYPE_(list) decltype((list)->type) +#elif defined __GNUC__ +#define NS_LIST_PTR_TYPE_(list) __typeof__((list)->type) +#endif + +/** \brief Check for compatible pointer types + * + * This test will produce a diagnostic about a pointer mismatch on + * the == inside the sizeof operator. For example ARM/Norcroft C gives the error: + * + * operand types are incompatible ("entry_t *" and "other_t *") + */ +#ifdef CPPCHECK +#define NS_PTR_MATCH_(a, b, str) ((void) 0) +#else +#define NS_PTR_MATCH_(a, b, str) ((void) sizeof ((a) == (b))) +#endif + +/** \brief Internal macro to cast returned entry pointers to correct type. + * + * Not portable in C, alas. With GCC or C++11, the "get entry" macros return + * correctly-typed pointers. Otherwise, the macros return `void *`. + * + * The attempt at a portable version would work if the C `?:` operator wasn't + * broken - `x ? (t *) : (void *)` should really have type `(t *)` in C, but + * it has type `(void *)`, which only makes sense for C++. The `?:` is left in, + * in case some day it works. Some compilers may still warn if this is + * assigned to a different type. + */ +#ifdef NS_LIST_PTR_TYPE_ +#define NS_LIST_TYPECAST_(list, val) ((NS_LIST_PTR_TYPE_(list)) (val)) +#else +#define NS_LIST_TYPECAST_(list, val) (0 ? (list)->type : (val)) +#endif + +/** \brief Internal macro to check types of input entry pointer. */ +#define NS_LIST_TYPECHECK_(list, entry) \ + (NS_PTR_MATCH_((list)->type, (entry), "incorrect entry type for list"), (entry)) + +/** \brief Type used to pass link offset to underlying functions + * + * We could use size_t, but it would be unnecessarily large on 8-bit systems, + * where we can be (pretty) confident we won't have next pointers more than + * 256 bytes into a structure. + */ +typedef uint_fast8_t ns_list_offset_t; + +/// \publicsection +/** \brief The type for the link member in the user's entry structure. + * + * Users should not access this member directly - just pass its name to the + * list head macros. The funny prev pointer simplifies common operations + * (eg insertion, removal), at the expense of complicating rare reverse iteration. + * + * NB - the list implementation relies on next being the first member. + */ +typedef struct ns_list_link { + void *next; ///< Pointer to next entry, or NULL if none + void **prev; ///< Pointer to previous entry's (or head's) next pointer +} ns_list_link_t; + +/** \brief "Poison" value placed in unattached entries' link pointers. + * \internal What are good values for this? Platform dependent, maybe just NULL + */ +#define NS_LIST_POISON ((void *) 0xDEADBEEF) + +/** \brief Initialiser for an entry's link member + * + * This initialiser is not required by the library, but a user may want an + * initialiser to include in their own entry initialiser. See + * ns_list_link_init() for more discussion. + */ +#define NS_LIST_LINK_INIT(name) \ + NS_FUNNY_INTPTR_OK \ + { NS_LIST_POISON, NS_LIST_POISON } \ + NS_FUNNY_INTPTR_RESTORE + +/** \hideinitializer \brief Initialise an entry's list link + * + * This "initialises" an unattached entry's link by filling the fields with + * poison. This is optional, as unattached entries field pointers are not + * meaningful, and it is not valid to call ns_list_get_next or similar on + * an unattached entry. + * + * \param entry Pointer to an entry + * \param field The name of the link member to initialise + */ +#define ns_list_link_init(entry, field) ns_list_link_init_(&(entry)->field) + +/** \hideinitializer \brief Initialise a list + * + * Initialise a list head before use. A list head must be initialised using this + * function or one of the NS_LIST_INIT()-type macros before use. A zero-initialised + * list head is *not* valid. + * + * If used on a list containing existing entries, those entries will + * become detached. (They are not modified, but their links are now effectively + * undefined). + * + * \param list Pointer to a NS_LIST_HEAD() structure. + */ +#define ns_list_init(list) ns_list_init_(&(list)->slist) + +/** \brief Initialiser for an empty list + * + * Usage in an enclosing initialiser: + * ~~~ + * static my_type_including_list_t x = { + * "Something", + * 23, + * NS_LIST_INIT(x), + * }; + * ~~~ + * NS_LIST_DEFINE() or NS_LIST_NAME_INIT() may provide a shorter alternative + * in simpler cases. + */ +#define NS_LIST_INIT(name) { { NULL, &(name).slist.first_entry } } + +/** \brief Name and initialiser for an empty list + * + * Usage: + * ~~~ + * list_t NS_LIST_NAME_INIT(foo); + * ~~~ + * acts as + * ~~~ + * list_t foo = { empty list }; + * ~~~ + * Also useful with designated initialisers: + * ~~~ + * .NS_LIST_NAME_INIT(foo), + * ~~~ + * acts as + * ~~~ + * .foo = { empty list }, + * ~~~ + */ +#define NS_LIST_NAME_INIT(name) name = NS_LIST_INIT(name) + +/** \brief Define a list, and initialise to empty. + * + * Usage: + * ~~~ + * static NS_LIST_DEFINE(my_list, entry_t, link); + * ~~~ + * acts as + * ~~~ + * static list_type my_list = { empty list }; + * ~~~ + */ +#define NS_LIST_DEFINE(name, type, field) \ + NS_LIST_HEAD(type, field) NS_LIST_NAME_INIT(name) + +/** \hideinitializer \brief Add an entry to the start of the linked list. + * + * ns_list_add_to_end() is *slightly* more efficient than ns_list_add_to_start(). + * + * \param list `(list_t *)` Pointer to list. + * \param entry `(entry_t * restrict)` Pointer to new entry to add. + */ +#define ns_list_add_to_start(list, entry) \ + ns_list_add_to_start_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, entry)) + +/** \hideinitializer \brief Add an entry to the end of the linked list. + * + * \param list `(list_t *)` Pointer to list. + * \param entry `(entry_t * restrict)` Pointer to new entry to add. + */ +#define ns_list_add_to_end(list, entry) \ + ns_list_add_to_end_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, entry)) + +/** \hideinitializer \brief Add an entry before a specified entry. + * + * \param list `(list_t *)` Pointer to list. + * \param before `(entry_t *)` Existing entry before which to place the new entry. + * \param entry `(entry_t * restrict)` Pointer to new entry to add. + */ +#define ns_list_add_before(list, before, entry) \ + ns_list_add_before_(NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, before), NS_LIST_TYPECHECK_(list, entry)) + +/** \hideinitializer \brief Add an entry after a specified entry. + * + * ns_list_add_before() is *slightly* more efficient than ns_list_add_after(). + * + * \param list `(list_t *)` Pointer to list. + * \param after `(entry_t *)` Existing entry after which to place the new entry. + * \param entry `(entry_t * restrict)` Pointer to new entry to add. + */ +#define ns_list_add_after(list, after, entry) \ + ns_list_add_after_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, after), NS_LIST_TYPECHECK_(list, entry)) + +/** \brief Check if a list is empty. + * + * \param list `(const list_t *)` Pointer to list. + * + * \return `(bool)` true if the list is empty. + */ +#define ns_list_is_empty(list) ((bool) ((list)->slist.first_entry == NULL)) + +/** \brief Get the first entry. + * + * \param list `(const list_t *)` Pointer to list. + * + * \return `(entry_t *)` Pointer to first entry. + * \return NULL if list is empty. + */ +#define ns_list_get_first(list) NS_LIST_TYPECAST_(list, (list)->slist.first_entry) + +/** \hideinitializer \brief Get the previous entry. + * + * \param list `(const list_t *)` Pointer to list. + * \param current `(const entry_t *)` Pointer to current entry. + * + * \return `(entry_t *)` Pointer to previous entry. + * \return NULL if current entry is first. + */ +#define ns_list_get_previous(list, current) \ + NS_LIST_TYPECAST_(list, ns_list_get_previous_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, current))) + +/** \hideinitializer \brief Get the next entry. + * + * \param list `(const list_t *)` Pointer to list. + * \param current `(const entry_t *)` Pointer to current entry. + * + * \return `(entry_t *)` Pointer to next entry. + * \return NULL if current entry is last. + */ +#define ns_list_get_next(list, current) \ + NS_LIST_TYPECAST_(list, ns_list_get_next_(NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, current))) + +/** \hideinitializer \brief Get the last entry. + * + * \param list `(const list_t *)` Pointer to list. + * + * \return `(entry_t *)` Pointer to last entry. + * \return NULL if list is empty. + */ +#define ns_list_get_last(list) \ + NS_LIST_TYPECAST_(list, ns_list_get_last_(&(list)->slist, NS_LIST_OFFSET_(list))) + +/** \hideinitializer \brief Remove an entry. + * + * \param list `(list_t *)` Pointer to list. + * \param entry `(entry_t *)` Entry on list to be removed. + */ +#define ns_list_remove(list, entry) \ + ns_list_remove_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, entry)) + +/** \hideinitializer \brief Replace an entry. + * + * \param list `(list_t *)` Pointer to list. + * \param current `(entry_t *)` Existing entry on list to be replaced. + * \param replacement `(entry_t * restrict)` New entry to be the replacement. + */ +#define ns_list_replace(list, current, replacement) \ + ns_list_replace_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, current), NS_LIST_TYPECHECK_(list, replacement)) + +/** \hideinitializer \brief Concatenate two lists. + * + * Attach the entries on the source list to the end of the destination + * list, leaving the source list empty. + * + * \param dst `(list_t *)` Pointer to destination list. + * \param src `(list_t *)` Pointer to source list. + * + */ +#define ns_list_concatenate(dst, src) \ + (NS_PTR_MATCH_(dst, src, "concatenating different list types"), \ + ns_list_concatenate_(&(dst)->slist, &(src)->slist, NS_LIST_OFFSET_(src))) + +/** \brief Iterate forwards over a list. + * + * Example: + * ~~~ + * ns_list_foreach(const my_entry_t, cur, &my_list) + * { + * printf("%s\n", cur->name); + * } + * ~~~ + * Deletion of the current entry is not permitted as its next is checked after + * running user code. + * + * The iteration pointer is declared inside the loop, using C99/C++, so it + * is not accessible after the loop. This encourages good code style, and + * matches the semantics of C++11's "ranged for", which only provides the + * declaration form: + * ~~~ + * for (const my_entry_t cur : my_list) + * ~~~ + * If you need to see the value of the iteration pointer after a `break`, + * you will need to assign it to a variable declared outside the loop before + * breaking: + * ~~~ + * my_entry_t *match = NULL; + * ns_list_foreach(my_entry_t, cur, &my_list) + * { + * if (cur->id == id) + * { + * match = cur; + * break; + * } + * } + * ~~~ + * + * The user has to specify the entry type for the pointer definition, as type + * extraction from the list argument isn't portable. On the other hand, this + * also permits const qualifiers, as in the example above, and serves as + * documentation. The entry type will be checked against the list type where the + * compiler supports it. + * + * \param type Entry type `([const] entry_t)`. + * \param e Name for iteration pointer to be defined + * inside the loop. + * \param list `(const list_t *)` Pointer to list - evaluated multiple times. + */ +#define ns_list_foreach(type, e, list) \ + for (type *e = ns_list_get_first(list); e; e = ns_list_get_next(list, e)) + +/** \brief Iterate forwards over a list, where user may delete. + * + * As ns_list_foreach(), but deletion of current entry is permitted as its + * next pointer is recorded before running user code. + * + * Example: + * ~~~ + * ns_list_foreach_safe(my_entry_t, cur, &my_list) + * { + * ns_list_remove(cur); + * } + * ~~~ + * \param type Entry type `(entry_t)`. + * \param e Name for iteration pointer to be defined + * inside the loop. + * \param list `(list_t *)` Pointer to list - evaluated multiple times. + */ +#define ns_list_foreach_safe(type, e, list) \ + for (type *e = ns_list_get_first(list), *_next; \ + e && (_next = ns_list_get_next(list, e), true); e = _next) + +/** \brief Iterate backwards over a list. + * + * As ns_list_foreach(), but going backwards - see its documentation. + * Iterating forwards is *slightly* more efficient. + */ +#define ns_list_foreach_reverse(type, e, list) \ + for (type *e = ns_list_get_last(list); e; e = ns_list_get_previous(list, e)) + +/** \brief Iterate backwards over a list, where user may delete. + * + * As ns_list_foreach_safe(), but going backwards - see its documentation. + * Iterating forwards is *slightly* more efficient. + */ +#define ns_list_foreach_reverse_safe(type, e, list) \ + for (type *e = ns_list_get_last(list), *_next; \ + e && (_next = ns_list_get_previous(list, e), true); e = _next) + +/** \hideinitializer \brief Count entries on a list + * + * Unlike other operations, this is O(n). Note: if list might contain over + * 65535 entries, this function **must not** be used to get the entry count. + * + * \param list `(const list_t *)` Pointer to list. + + * \return `(uint_fast16_t)` Number of entries that are stored in list. + */ +#define ns_list_count(list) ns_list_count_(&(list)->slist, NS_LIST_OFFSET_(list)) + +/** \privatesection + * Internal functions - designed to be accessed using corresponding macros above + */ +NS_INLINE void ns_list_init_(ns_list_t *list); +NS_INLINE void ns_list_link_init_(ns_list_link_t *link); +NS_INLINE void ns_list_add_to_start_(ns_list_t *list, ns_list_offset_t link_offset, void *restrict entry); +NS_INLINE void ns_list_add_to_end_(ns_list_t *list, ns_list_offset_t link_offset, void *restrict entry); +NS_INLINE void ns_list_add_before_(ns_list_offset_t link_offset, void *before, void *restrict entry); +NS_INLINE void ns_list_add_after_(ns_list_t *list, ns_list_offset_t link_offset, void *after, void *restrict entry); +NS_INLINE void *ns_list_get_next_(ns_list_offset_t link_offset, const void *current); +NS_INLINE void *ns_list_get_previous_(const ns_list_t *list, ns_list_offset_t link_offset, const void *current); +NS_INLINE void *ns_list_get_last_(const ns_list_t *list, ns_list_offset_t offset); +NS_INLINE void ns_list_remove_(ns_list_t *list, ns_list_offset_t link_offset, void *entry); +NS_INLINE void ns_list_replace_(ns_list_t *list, ns_list_offset_t link_offset, void *current, void *restrict replacement); +NS_INLINE void ns_list_concatenate_(ns_list_t *dst, ns_list_t *src, ns_list_offset_t offset); +NS_INLINE uint_fast16_t ns_list_count_(const ns_list_t *list, ns_list_offset_t link_offset); + +/* Provide definitions, either for inlining, or for ns_list.c */ +#if defined NS_ALLOW_INLINING || defined NS_LIST_FN +#ifndef NS_LIST_FN +#define NS_LIST_FN NS_INLINE +#endif + +/* Pointer to the link member in entry e */ +#define NS_LIST_LINK_(e, offset) ((ns_list_link_t *)((char *)(e) + offset)) + +/* Lvalue of the next link pointer in entry e */ +#define NS_LIST_NEXT_(e, offset) (NS_LIST_LINK_(e, offset)->next) + +/* Lvalue of the prev link pointer in entry e */ +#define NS_LIST_PREV_(e, offset) (NS_LIST_LINK_(e, offset)->prev) + +/* Convert a pointer to a link member back to the entry; + * works for linkptr either being a ns_list_link_t pointer, or its next pointer, + * as the next pointer is first in the ns_list_link_t */ +#define NS_LIST_ENTRY_(linkptr, offset) ((void *)((char *)(linkptr) - offset)) + +NS_LIST_FN void ns_list_init_(ns_list_t *list) +{ + list->first_entry = NULL; + list->last_nextptr = &list->first_entry; +} + +NS_LIST_FN void ns_list_link_init_(ns_list_link_t *link) +{ + NS_FUNNY_INTPTR_OK + link->next = NS_LIST_POISON; + link->prev = NS_LIST_POISON; + NS_FUNNY_INTPTR_RESTORE +} + +NS_LIST_FN void ns_list_add_to_start_(ns_list_t *list, ns_list_offset_t offset, void *restrict entry) +{ + void *next; + + NS_LIST_PREV_(entry, offset) = &list->first_entry; + NS_LIST_NEXT_(entry, offset) = next = list->first_entry; + + if (next) { + NS_LIST_PREV_(next, offset) = &NS_LIST_NEXT_(entry, offset); + } else { + list->last_nextptr = &NS_LIST_NEXT_(entry, offset); + } + + list->first_entry = entry; +} + +NS_LIST_FN void ns_list_add_after_(ns_list_t *list, ns_list_offset_t offset, void *current, void *restrict entry) +{ + void *next; + + NS_LIST_PREV_(entry, offset) = &NS_LIST_NEXT_(current, offset); + NS_LIST_NEXT_(entry, offset) = next = NS_LIST_NEXT_(current, offset); + + if (next) { + NS_LIST_PREV_(next, offset) = &NS_LIST_NEXT_(entry, offset); + } else { + list->last_nextptr = &NS_LIST_NEXT_(entry, offset); + } + + NS_LIST_NEXT_(current, offset) = entry; +} + +NS_LIST_FN void ns_list_add_before_(ns_list_offset_t offset, void *current, void *restrict entry) +{ + void **prev_nextptr; + + NS_LIST_NEXT_(entry, offset) = current; + NS_LIST_PREV_(entry, offset) = prev_nextptr = NS_LIST_PREV_(current, offset); + *prev_nextptr = entry; + NS_LIST_PREV_(current, offset) = &NS_LIST_NEXT_(entry, offset); +} + +NS_LIST_FN void ns_list_add_to_end_(ns_list_t *list, ns_list_offset_t offset, void *restrict entry) +{ + void **prev_nextptr; + + NS_LIST_NEXT_(entry, offset) = NULL; + NS_LIST_PREV_(entry, offset) = prev_nextptr = list->last_nextptr; + *prev_nextptr = entry; + list->last_nextptr = &NS_LIST_NEXT_(entry, offset); +} + +NS_LIST_FN void *ns_list_get_next_(ns_list_offset_t offset, const void *current) +{ + return NS_LIST_NEXT_(current, offset); +} + +NS_LIST_FN void *ns_list_get_previous_(const ns_list_t *list, ns_list_offset_t offset, const void *current) +{ + if (current == list->first_entry) { + return NULL; + } + + // Tricky. We don't have a direct previous pointer, but a pointer to the + // pointer that points to us - ie &head->first_entry OR &{prev}->next. + // This makes life easier on insertion and removal, but this is where we + // pay the price. + + // We have to check manually for being the first entry above, so we know it's + // a real link's next pointer. Then next is the first field of + // ns_list_link_t, so we can use the normal offset value. + + return NS_LIST_ENTRY_(NS_LIST_PREV_(current, offset), offset); +} + +NS_LIST_FN void *ns_list_get_last_(const ns_list_t *list, ns_list_offset_t offset) +{ + if (!list->first_entry) { + return NULL; + } + + // See comments in ns_list_get_previous_() + return NS_LIST_ENTRY_(list->last_nextptr, offset); +} + +NS_LIST_FN void ns_list_remove_(ns_list_t *list, ns_list_offset_t offset, void *removed) +{ + void *next; + void **prev_nextptr; + + next = NS_LIST_NEXT_(removed, offset); + prev_nextptr = NS_LIST_PREV_(removed, offset); + if (next) { + NS_LIST_PREV_(next, offset) = prev_nextptr; + } else { + list->last_nextptr = prev_nextptr; + } + *prev_nextptr = next; + + ns_list_link_init_(NS_LIST_LINK_(removed, offset)); +} + +NS_LIST_FN void ns_list_replace_(ns_list_t *list, ns_list_offset_t offset, void *current, void *restrict replacement) +{ + void *next; + void **prev_nextptr; + + NS_LIST_PREV_(replacement, offset) = prev_nextptr = NS_LIST_PREV_(current, offset); + NS_LIST_NEXT_(replacement, offset) = next = NS_LIST_NEXT_(current, offset); + + if (next) { + NS_LIST_PREV_(next, offset) = &NS_LIST_NEXT_(replacement, offset); + } else { + list->last_nextptr = &NS_LIST_NEXT_(replacement, offset); + } + *prev_nextptr = replacement; + + ns_list_link_init_(NS_LIST_LINK_(current, offset)); +} + +NS_LIST_FN void ns_list_concatenate_(ns_list_t *dst, ns_list_t *src, ns_list_offset_t offset) +{ + ns_list_link_t *src_first; + + src_first = src->first_entry; + if (!src_first) { + return; + } + + *dst->last_nextptr = src_first; + NS_LIST_PREV_(src_first, offset) = dst->last_nextptr; + dst->last_nextptr = src->last_nextptr; + + ns_list_init_(src); +} + +NS_LIST_FN uint_fast16_t ns_list_count_(const ns_list_t *list, ns_list_offset_t offset) +{ + uint_fast16_t count = 0; + + for (void *p = list->first_entry; p; p = NS_LIST_NEXT_(p, offset)) { + count++; + } + + return count; +} +#endif /* defined NS_ALLOW_INLINING || defined NS_LIST_FN */ + +#ifdef __cplusplus +} +#endif + +#endif /* NS_LIST_H_ */ +