Austin Blackstone / Mbed 2 deprecated client-lwip-lightswitch-demo-expanded

mbed client lightswitch demo

Dependencies:   mbed Socket lwip-eth lwip-sys lwip

Fork of mbed-client-classic-example-lwip by Austin Blackstone

nanostack-libservice/mbed-client-libservice/ns_list.h@11:cada08fc8a70, 2016-06-09 (annotated)

Committer:
mbedAustin
Date:
Thu Jun 09 17:08:36 2016 +0000
Revision:
11:cada08fc8a70
Commit for public Consumption

Who changed what in which revision?

UserRevisionLine numberNew contents of line
mbedAustin 11:cada08fc8a70 1 /*
mbedAustin 11:cada08fc8a70 2 * Copyright (c) 2014-2015 ARM Limited. All rights reserved.
mbedAustin 11:cada08fc8a70 3 * SPDX-License-Identifier: Apache-2.0
mbedAustin 11:cada08fc8a70 4 * Licensed under the Apache License, Version 2.0 (the License); you may
mbedAustin 11:cada08fc8a70 5 * not use this file except in compliance with the License.
mbedAustin 11:cada08fc8a70 6 * You may obtain a copy of the License at
mbedAustin 11:cada08fc8a70 7 *
mbedAustin 11:cada08fc8a70 8 * http://www.apache.org/licenses/LICENSE-2.0
mbedAustin 11:cada08fc8a70 9 *
mbedAustin 11:cada08fc8a70 10 * Unless required by applicable law or agreed to in writing, software
mbedAustin 11:cada08fc8a70 11 * distributed under the License is distributed on an AS IS BASIS, WITHOUT
mbedAustin 11:cada08fc8a70 12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
mbedAustin 11:cada08fc8a70 13 * See the License for the specific language governing permissions and
mbedAustin 11:cada08fc8a70 14 * limitations under the License.
mbedAustin 11:cada08fc8a70 15 */
mbedAustin 11:cada08fc8a70 16
mbedAustin 11:cada08fc8a70 17 #ifndef NS_LIST_H_
mbedAustin 11:cada08fc8a70 18 #define NS_LIST_H_
mbedAustin 11:cada08fc8a70 19
mbedAustin 11:cada08fc8a70 20 #include "ns_types.h"
mbedAustin 11:cada08fc8a70 21
mbedAustin 11:cada08fc8a70 22 #ifdef __cplusplus
mbedAustin 11:cada08fc8a70 23 extern "C" {
mbedAustin 11:cada08fc8a70 24 #endif
mbedAustin 11:cada08fc8a70 25
mbedAustin 11:cada08fc8a70 26 /** \file
mbedAustin 11:cada08fc8a70 27 * \brief Linked list support library
mbedAustin 11:cada08fc8a70 28 *
mbedAustin 11:cada08fc8a70 29 * The ns_list.h file provides a doubly-linked list/queue, providing O(1)
mbedAustin 11:cada08fc8a70 30 * performance for all insertion/removal operations, and access to either
mbedAustin 11:cada08fc8a70 31 * end of the list.
mbedAustin 11:cada08fc8a70 32 *
mbedAustin 11:cada08fc8a70 33 * Memory footprint is two pointers for the list head, and two pointers in each
mbedAustin 11:cada08fc8a70 34 * list entry. It is similar in concept to BSD's TAILQ.
mbedAustin 11:cada08fc8a70 35 *
mbedAustin 11:cada08fc8a70 36 * Although the API is symmetrical and O(1) in both directions, due to internal
mbedAustin 11:cada08fc8a70 37 * pointer design, it is *slightly* more efficient to insert at the end when
mbedAustin 11:cada08fc8a70 38 * used as a queue, and to iterate forwards rather than backwards.
mbedAustin 11:cada08fc8a70 39 *
mbedAustin 11:cada08fc8a70 40 * Example of an entry type that can be stored to this list.
mbedAustin 11:cada08fc8a70 41 * ~~~
mbedAustin 11:cada08fc8a70 42 * typedef struct example_entry
mbedAustin 11:cada08fc8a70 43 * {
mbedAustin 11:cada08fc8a70 44 * uint8_t *data;
mbedAustin 11:cada08fc8a70 45 * uint32_t data_count;
mbedAustin 11:cada08fc8a70 46 * ns_list_link_t link;
mbedAustin 11:cada08fc8a70 47 * }
mbedAustin 11:cada08fc8a70 48 * example_entry_t;
mbedAustin 11:cada08fc8a70 49 *
mbedAustin 11:cada08fc8a70 50 * static NS_LIST_HEAD(example_entry_t, link) my_list;
mbedAustin 11:cada08fc8a70 51 * ns_list_init(&my_list);
mbedAustin 11:cada08fc8a70 52 * ~~~
mbedAustin 11:cada08fc8a70 53 * OR
mbedAustin 11:cada08fc8a70 54 * ~~~
mbedAustin 11:cada08fc8a70 55 * NS_LIST_HEAD(example_entry_t, link) my_list = NS_LIST_INIT(my_list);
mbedAustin 11:cada08fc8a70 56 * ~~~
mbedAustin 11:cada08fc8a70 57 * OR
mbedAustin 11:cada08fc8a70 58 * ~~~
mbedAustin 11:cada08fc8a70 59 * static NS_LIST_DEFINE(my_list, example_entry_t, link);
mbedAustin 11:cada08fc8a70 60 * ~~~
mbedAustin 11:cada08fc8a70 61 * OR
mbedAustin 11:cada08fc8a70 62 * ~~~
mbedAustin 11:cada08fc8a70 63 * typedef NS_LIST_HEAD(example_entry_t, link) example_list_t;
mbedAustin 11:cada08fc8a70 64 * example_list_t NS_LIST_NAME_INIT(my_list);
mbedAustin 11:cada08fc8a70 65 * ~~~
mbedAustin 11:cada08fc8a70 66 * NOTE: the link field SHALL NOT be accessed by the user.
mbedAustin 11:cada08fc8a70 67 *
mbedAustin 11:cada08fc8a70 68 * An entry can exist on multiple lists by having multiple link fields.
mbedAustin 11:cada08fc8a70 69 *
mbedAustin 11:cada08fc8a70 70 * All the list operations are implemented as macros, most of which are backed
mbedAustin 11:cada08fc8a70 71 * by optionally-inline functions. The macros do not evaluate any arguments more
mbedAustin 11:cada08fc8a70 72 * than once, unless documented.
mbedAustin 11:cada08fc8a70 73 *
mbedAustin 11:cada08fc8a70 74 * In macro documentation, `list_t` refers to a list type defined using
mbedAustin 11:cada08fc8a70 75 * NS_LIST_HEAD(), and `entry_t` to the entry type that was passed to it.
mbedAustin 11:cada08fc8a70 76 */
mbedAustin 11:cada08fc8a70 77
mbedAustin 11:cada08fc8a70 78 /** \brief Underlying generic linked list head.
mbedAustin 11:cada08fc8a70 79 *
mbedAustin 11:cada08fc8a70 80 * Users should not use this type directly, but use the NS_LIST_HEAD() macro.
mbedAustin 11:cada08fc8a70 81 */
mbedAustin 11:cada08fc8a70 82 typedef struct ns_list {
mbedAustin 11:cada08fc8a70 83 void *first_entry; ///< Pointer to first entry, or NULL if list is empty
mbedAustin 11:cada08fc8a70 84 void **last_nextptr; ///< Pointer to last entry's `next` pointer, or
mbedAustin 11:cada08fc8a70 85 ///< to head's `first_entry` pointer if list is empty
mbedAustin 11:cada08fc8a70 86 } ns_list_t;
mbedAustin 11:cada08fc8a70 87
mbedAustin 11:cada08fc8a70 88 /** \brief Declare a list head type
mbedAustin 11:cada08fc8a70 89 *
mbedAustin 11:cada08fc8a70 90 * This union stores the real list head, and also encodes as compile-time type
mbedAustin 11:cada08fc8a70 91 * information the offset of the link pointer, and the type of the entry.
mbedAustin 11:cada08fc8a70 92 *
mbedAustin 11:cada08fc8a70 93 * Note that type information is compiler-dependent; this means
mbedAustin 11:cada08fc8a70 94 * ns_list_get_first() could return either `void *`, or a pointer to the actual
mbedAustin 11:cada08fc8a70 95 * entry type. So `ns_list_get_first()->data` is not a portable construct -
mbedAustin 11:cada08fc8a70 96 * always assign returned entry pointers to a properly typed pointer variable.
mbedAustin 11:cada08fc8a70 97 * This assignment will be then type-checked where the compiler supports it, and
mbedAustin 11:cada08fc8a70 98 * will dereference correctly on compilers that don't support this extension.
mbedAustin 11:cada08fc8a70 99 * ~~~
mbedAustin 11:cada08fc8a70 100 * NS_LIST_HEAD(example_entry_t, link) my_list;
mbedAustin 11:cada08fc8a70 101 *
mbedAustin 11:cada08fc8a70 102 * example_entry_t *entry = ns_list_get_first(&my_list);
mbedAustin 11:cada08fc8a70 103 * do_something(entry->data);
mbedAustin 11:cada08fc8a70 104 * ~~~
mbedAustin 11:cada08fc8a70 105 * Each use of this macro generates a new anonymous union, so these two lists
mbedAustin 11:cada08fc8a70 106 * have different types:
mbedAustin 11:cada08fc8a70 107 * ~~~
mbedAustin 11:cada08fc8a70 108 * NS_LIST_HEAD(example_entry_t, link) my_list1;
mbedAustin 11:cada08fc8a70 109 * NS_LIST_HEAD(example_entry_t, link) my_list2;
mbedAustin 11:cada08fc8a70 110 * ~~~
mbedAustin 11:cada08fc8a70 111 * If you need to use a list type in multiple places, eg as a function
mbedAustin 11:cada08fc8a70 112 * parameter, use typedef:
mbedAustin 11:cada08fc8a70 113 * ~~~
mbedAustin 11:cada08fc8a70 114 * typedef NS_LIST_HEAD(example_entry_t, link) example_list_t;
mbedAustin 11:cada08fc8a70 115 *
mbedAustin 11:cada08fc8a70 116 * void example_function(example_list_t *);
mbedAustin 11:cada08fc8a70 117 * ~~~
mbedAustin 11:cada08fc8a70 118 */
mbedAustin 11:cada08fc8a70 119 #define NS_LIST_HEAD(entry_type, field) \
mbedAustin 11:cada08fc8a70 120 NS_LIST_HEAD_BY_OFFSET_(entry_type, offsetof(entry_type, field))
mbedAustin 11:cada08fc8a70 121
mbedAustin 11:cada08fc8a70 122 /** \brief Declare a list head type for an incomplete entry type.
mbedAustin 11:cada08fc8a70 123 *
mbedAustin 11:cada08fc8a70 124 * This declares a list head, similarly to NS_LIST_HEAD(), but unlike that
mbedAustin 11:cada08fc8a70 125 * this can be used in contexts where the entry type may be incomplete.
mbedAustin 11:cada08fc8a70 126 *
mbedAustin 11:cada08fc8a70 127 * To use this, the link pointer must be the first member in the
mbedAustin 11:cada08fc8a70 128 * actual complete structure. This is NOT checked - the definition of the
mbedAustin 11:cada08fc8a70 129 * element should probably test NS_STATIC_ASSERT(offsetof(type, link) == 0)
mbedAustin 11:cada08fc8a70 130 * if outside users are known to be using NS_LIST_HEAD_INCOMPLETE().
mbedAustin 11:cada08fc8a70 131 * ~~~
mbedAustin 11:cada08fc8a70 132 * struct opaque;
mbedAustin 11:cada08fc8a70 133 * NS_LIST_HEAD_INCOMPLETE(struct opaque) opaque_list;
mbedAustin 11:cada08fc8a70 134 * ~~~
mbedAustin 11:cada08fc8a70 135 */
mbedAustin 11:cada08fc8a70 136 #define NS_LIST_HEAD_INCOMPLETE(entry_type) \
mbedAustin 11:cada08fc8a70 137 NS_LIST_HEAD_BY_OFFSET_(entry_type, 0)
mbedAustin 11:cada08fc8a70 138
mbedAustin 11:cada08fc8a70 139 /// \privatesection
mbedAustin 11:cada08fc8a70 140 /** \brief Internal macro defining a list head, given the offset to the link pointer
mbedAustin 11:cada08fc8a70 141 * The +1 allows for link_offset being 0 - we can't declare a 0-size array
mbedAustin 11:cada08fc8a70 142 */
mbedAustin 11:cada08fc8a70 143 #define NS_LIST_HEAD_BY_OFFSET_(entry_type, link_offset) \
mbedAustin 11:cada08fc8a70 144 union \
mbedAustin 11:cada08fc8a70 145 { \
mbedAustin 11:cada08fc8a70 146 ns_list_t slist; \
mbedAustin 11:cada08fc8a70 147 NS_STATIC_ASSERT(link_offset <= UINT_FAST8_MAX, "link offset too large") \
mbedAustin 11:cada08fc8a70 148 char (*offset)[link_offset + 1]; \
mbedAustin 11:cada08fc8a70 149 entry_type *type; \
mbedAustin 11:cada08fc8a70 150 }
mbedAustin 11:cada08fc8a70 151
mbedAustin 11:cada08fc8a70 152 /** \brief Get offset of link field in entry.
mbedAustin 11:cada08fc8a70 153 * \return `(ns_list_offset_t)` The offset of the link field for entries on the specified list
mbedAustin 11:cada08fc8a70 154 */
mbedAustin 11:cada08fc8a70 155 #define NS_LIST_OFFSET_(list) ((ns_list_offset_t) (sizeof *(list)->offset - 1))
mbedAustin 11:cada08fc8a70 156
mbedAustin 11:cada08fc8a70 157 /** \brief Get the entry pointer type.
mbedAustin 11:cada08fc8a70 158 * \def NS_LIST_PTR_TYPE_
mbedAustin 11:cada08fc8a70 159 *
mbedAustin 11:cada08fc8a70 160 * \return An unqualified pointer type to an entry on the specified list.
mbedAustin 11:cada08fc8a70 161 *
mbedAustin 11:cada08fc8a70 162 * Only available if the compiler provides a "typeof" operator.
mbedAustin 11:cada08fc8a70 163 */
mbedAustin 11:cada08fc8a70 164 #if defined __cplusplus && __cplusplus >= 201103L
mbedAustin 11:cada08fc8a70 165 #define NS_LIST_PTR_TYPE_(list) decltype((list)->type)
mbedAustin 11:cada08fc8a70 166 #elif defined __GNUC__
mbedAustin 11:cada08fc8a70 167 #define NS_LIST_PTR_TYPE_(list) __typeof__((list)->type)
mbedAustin 11:cada08fc8a70 168 #endif
mbedAustin 11:cada08fc8a70 169
mbedAustin 11:cada08fc8a70 170 /** \brief Check for compatible pointer types
mbedAustin 11:cada08fc8a70 171 *
mbedAustin 11:cada08fc8a70 172 * This test will produce a diagnostic about a pointer mismatch on
mbedAustin 11:cada08fc8a70 173 * the == inside the sizeof operator. For example ARM/Norcroft C gives the error:
mbedAustin 11:cada08fc8a70 174 *
mbedAustin 11:cada08fc8a70 175 * operand types are incompatible ("entry_t *" and "other_t *")
mbedAustin 11:cada08fc8a70 176 */
mbedAustin 11:cada08fc8a70 177 #ifdef CPPCHECK
mbedAustin 11:cada08fc8a70 178 #define NS_PTR_MATCH_(a, b, str) ((void) 0)
mbedAustin 11:cada08fc8a70 179 #else
mbedAustin 11:cada08fc8a70 180 #define NS_PTR_MATCH_(a, b, str) ((void) sizeof ((a) == (b)))
mbedAustin 11:cada08fc8a70 181 #endif
mbedAustin 11:cada08fc8a70 182
mbedAustin 11:cada08fc8a70 183 /** \brief Internal macro to cast returned entry pointers to correct type.
mbedAustin 11:cada08fc8a70 184 *
mbedAustin 11:cada08fc8a70 185 * Not portable in C, alas. With GCC or C++11, the "get entry" macros return
mbedAustin 11:cada08fc8a70 186 * correctly-typed pointers. Otherwise, the macros return `void *`.
mbedAustin 11:cada08fc8a70 187 *
mbedAustin 11:cada08fc8a70 188 * The attempt at a portable version would work if the C `?:` operator wasn't
mbedAustin 11:cada08fc8a70 189 * broken - `x ? (t *) : (void *)` should really have type `(t *)` in C, but
mbedAustin 11:cada08fc8a70 190 * it has type `(void *)`, which only makes sense for C++. The `?:` is left in,
mbedAustin 11:cada08fc8a70 191 * in case some day it works. Some compilers may still warn if this is
mbedAustin 11:cada08fc8a70 192 * assigned to a different type.
mbedAustin 11:cada08fc8a70 193 */
mbedAustin 11:cada08fc8a70 194 #ifdef NS_LIST_PTR_TYPE_
mbedAustin 11:cada08fc8a70 195 #define NS_LIST_TYPECAST_(list, val) ((NS_LIST_PTR_TYPE_(list)) (val))
mbedAustin 11:cada08fc8a70 196 #else
mbedAustin 11:cada08fc8a70 197 #define NS_LIST_TYPECAST_(list, val) (0 ? (list)->type : (val))
mbedAustin 11:cada08fc8a70 198 #endif
mbedAustin 11:cada08fc8a70 199
mbedAustin 11:cada08fc8a70 200 /** \brief Internal macro to check types of input entry pointer. */
mbedAustin 11:cada08fc8a70 201 #define NS_LIST_TYPECHECK_(list, entry) \
mbedAustin 11:cada08fc8a70 202 (NS_PTR_MATCH_((list)->type, (entry), "incorrect entry type for list"), (entry))
mbedAustin 11:cada08fc8a70 203
mbedAustin 11:cada08fc8a70 204 /** \brief Type used to pass link offset to underlying functions
mbedAustin 11:cada08fc8a70 205 *
mbedAustin 11:cada08fc8a70 206 * We could use size_t, but it would be unnecessarily large on 8-bit systems,
mbedAustin 11:cada08fc8a70 207 * where we can be (pretty) confident we won't have next pointers more than
mbedAustin 11:cada08fc8a70 208 * 256 bytes into a structure.
mbedAustin 11:cada08fc8a70 209 */
mbedAustin 11:cada08fc8a70 210 typedef uint_fast8_t ns_list_offset_t;
mbedAustin 11:cada08fc8a70 211
mbedAustin 11:cada08fc8a70 212 /// \publicsection
mbedAustin 11:cada08fc8a70 213 /** \brief The type for the link member in the user's entry structure.
mbedAustin 11:cada08fc8a70 214 *
mbedAustin 11:cada08fc8a70 215 * Users should not access this member directly - just pass its name to the
mbedAustin 11:cada08fc8a70 216 * list head macros. The funny prev pointer simplifies common operations
mbedAustin 11:cada08fc8a70 217 * (eg insertion, removal), at the expense of complicating rare reverse iteration.
mbedAustin 11:cada08fc8a70 218 *
mbedAustin 11:cada08fc8a70 219 * NB - the list implementation relies on next being the first member.
mbedAustin 11:cada08fc8a70 220 */
mbedAustin 11:cada08fc8a70 221 typedef struct ns_list_link {
mbedAustin 11:cada08fc8a70 222 void *next; ///< Pointer to next entry, or NULL if none
mbedAustin 11:cada08fc8a70 223 void **prev; ///< Pointer to previous entry's (or head's) next pointer
mbedAustin 11:cada08fc8a70 224 } ns_list_link_t;
mbedAustin 11:cada08fc8a70 225
mbedAustin 11:cada08fc8a70 226 /** \brief "Poison" value placed in unattached entries' link pointers.
mbedAustin 11:cada08fc8a70 227 * \internal What are good values for this? Platform dependent, maybe just NULL
mbedAustin 11:cada08fc8a70 228 */
mbedAustin 11:cada08fc8a70 229 #define NS_LIST_POISON ((void *) 0xDEADBEEF)
mbedAustin 11:cada08fc8a70 230
mbedAustin 11:cada08fc8a70 231 /** \brief Initialiser for an entry's link member
mbedAustin 11:cada08fc8a70 232 *
mbedAustin 11:cada08fc8a70 233 * This initialiser is not required by the library, but a user may want an
mbedAustin 11:cada08fc8a70 234 * initialiser to include in their own entry initialiser. See
mbedAustin 11:cada08fc8a70 235 * ns_list_link_init() for more discussion.
mbedAustin 11:cada08fc8a70 236 */
mbedAustin 11:cada08fc8a70 237 #define NS_LIST_LINK_INIT(name) \
mbedAustin 11:cada08fc8a70 238 NS_FUNNY_INTPTR_OK \
mbedAustin 11:cada08fc8a70 239 { NS_LIST_POISON, NS_LIST_POISON } \
mbedAustin 11:cada08fc8a70 240 NS_FUNNY_INTPTR_RESTORE
mbedAustin 11:cada08fc8a70 241
mbedAustin 11:cada08fc8a70 242 /** \hideinitializer \brief Initialise an entry's list link
mbedAustin 11:cada08fc8a70 243 *
mbedAustin 11:cada08fc8a70 244 * This "initialises" an unattached entry's link by filling the fields with
mbedAustin 11:cada08fc8a70 245 * poison. This is optional, as unattached entries field pointers are not
mbedAustin 11:cada08fc8a70 246 * meaningful, and it is not valid to call ns_list_get_next or similar on
mbedAustin 11:cada08fc8a70 247 * an unattached entry.
mbedAustin 11:cada08fc8a70 248 *
mbedAustin 11:cada08fc8a70 249 * \param entry Pointer to an entry
mbedAustin 11:cada08fc8a70 250 * \param field The name of the link member to initialise
mbedAustin 11:cada08fc8a70 251 */
mbedAustin 11:cada08fc8a70 252 #define ns_list_link_init(entry, field) ns_list_link_init_(&(entry)->field)
mbedAustin 11:cada08fc8a70 253
mbedAustin 11:cada08fc8a70 254 /** \hideinitializer \brief Initialise a list
mbedAustin 11:cada08fc8a70 255 *
mbedAustin 11:cada08fc8a70 256 * Initialise a list head before use. A list head must be initialised using this
mbedAustin 11:cada08fc8a70 257 * function or one of the NS_LIST_INIT()-type macros before use. A zero-initialised
mbedAustin 11:cada08fc8a70 258 * list head is *not* valid.
mbedAustin 11:cada08fc8a70 259 *
mbedAustin 11:cada08fc8a70 260 * If used on a list containing existing entries, those entries will
mbedAustin 11:cada08fc8a70 261 * become detached. (They are not modified, but their links are now effectively
mbedAustin 11:cada08fc8a70 262 * undefined).
mbedAustin 11:cada08fc8a70 263 *
mbedAustin 11:cada08fc8a70 264 * \param list Pointer to a NS_LIST_HEAD() structure.
mbedAustin 11:cada08fc8a70 265 */
mbedAustin 11:cada08fc8a70 266 #define ns_list_init(list) ns_list_init_(&(list)->slist)
mbedAustin 11:cada08fc8a70 267
mbedAustin 11:cada08fc8a70 268 /** \brief Initialiser for an empty list
mbedAustin 11:cada08fc8a70 269 *
mbedAustin 11:cada08fc8a70 270 * Usage in an enclosing initialiser:
mbedAustin 11:cada08fc8a70 271 * ~~~
mbedAustin 11:cada08fc8a70 272 * static my_type_including_list_t x = {
mbedAustin 11:cada08fc8a70 273 * "Something",
mbedAustin 11:cada08fc8a70 274 * 23,
mbedAustin 11:cada08fc8a70 275 * NS_LIST_INIT(x),
mbedAustin 11:cada08fc8a70 276 * };
mbedAustin 11:cada08fc8a70 277 * ~~~
mbedAustin 11:cada08fc8a70 278 * NS_LIST_DEFINE() or NS_LIST_NAME_INIT() may provide a shorter alternative
mbedAustin 11:cada08fc8a70 279 * in simpler cases.
mbedAustin 11:cada08fc8a70 280 */
mbedAustin 11:cada08fc8a70 281 #define NS_LIST_INIT(name) { { NULL, &(name).slist.first_entry } }
mbedAustin 11:cada08fc8a70 282
mbedAustin 11:cada08fc8a70 283 /** \brief Name and initialiser for an empty list
mbedAustin 11:cada08fc8a70 284 *
mbedAustin 11:cada08fc8a70 285 * Usage:
mbedAustin 11:cada08fc8a70 286 * ~~~
mbedAustin 11:cada08fc8a70 287 * list_t NS_LIST_NAME_INIT(foo);
mbedAustin 11:cada08fc8a70 288 * ~~~
mbedAustin 11:cada08fc8a70 289 * acts as
mbedAustin 11:cada08fc8a70 290 * ~~~
mbedAustin 11:cada08fc8a70 291 * list_t foo = { empty list };
mbedAustin 11:cada08fc8a70 292 * ~~~
mbedAustin 11:cada08fc8a70 293 * Also useful with designated initialisers:
mbedAustin 11:cada08fc8a70 294 * ~~~
mbedAustin 11:cada08fc8a70 295 * .NS_LIST_NAME_INIT(foo),
mbedAustin 11:cada08fc8a70 296 * ~~~
mbedAustin 11:cada08fc8a70 297 * acts as
mbedAustin 11:cada08fc8a70 298 * ~~~
mbedAustin 11:cada08fc8a70 299 * .foo = { empty list },
mbedAustin 11:cada08fc8a70 300 * ~~~
mbedAustin 11:cada08fc8a70 301 */
mbedAustin 11:cada08fc8a70 302 #define NS_LIST_NAME_INIT(name) name = NS_LIST_INIT(name)
mbedAustin 11:cada08fc8a70 303
mbedAustin 11:cada08fc8a70 304 /** \brief Define a list, and initialise to empty.
mbedAustin 11:cada08fc8a70 305 *
mbedAustin 11:cada08fc8a70 306 * Usage:
mbedAustin 11:cada08fc8a70 307 * ~~~
mbedAustin 11:cada08fc8a70 308 * static NS_LIST_DEFINE(my_list, entry_t, link);
mbedAustin 11:cada08fc8a70 309 * ~~~
mbedAustin 11:cada08fc8a70 310 * acts as
mbedAustin 11:cada08fc8a70 311 * ~~~
mbedAustin 11:cada08fc8a70 312 * static list_type my_list = { empty list };
mbedAustin 11:cada08fc8a70 313 * ~~~
mbedAustin 11:cada08fc8a70 314 */
mbedAustin 11:cada08fc8a70 315 #define NS_LIST_DEFINE(name, type, field) \
mbedAustin 11:cada08fc8a70 316 NS_LIST_HEAD(type, field) NS_LIST_NAME_INIT(name)
mbedAustin 11:cada08fc8a70 317
mbedAustin 11:cada08fc8a70 318 /** \hideinitializer \brief Add an entry to the start of the linked list.
mbedAustin 11:cada08fc8a70 319 *
mbedAustin 11:cada08fc8a70 320 * ns_list_add_to_end() is *slightly* more efficient than ns_list_add_to_start().
mbedAustin 11:cada08fc8a70 321 *
mbedAustin 11:cada08fc8a70 322 * \param list `(list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 323 * \param entry `(entry_t * restrict)` Pointer to new entry to add.
mbedAustin 11:cada08fc8a70 324 */
mbedAustin 11:cada08fc8a70 325 #define ns_list_add_to_start(list, entry) \
mbedAustin 11:cada08fc8a70 326 ns_list_add_to_start_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, entry))
mbedAustin 11:cada08fc8a70 327
mbedAustin 11:cada08fc8a70 328 /** \hideinitializer \brief Add an entry to the end of the linked list.
mbedAustin 11:cada08fc8a70 329 *
mbedAustin 11:cada08fc8a70 330 * \param list `(list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 331 * \param entry `(entry_t * restrict)` Pointer to new entry to add.
mbedAustin 11:cada08fc8a70 332 */
mbedAustin 11:cada08fc8a70 333 #define ns_list_add_to_end(list, entry) \
mbedAustin 11:cada08fc8a70 334 ns_list_add_to_end_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, entry))
mbedAustin 11:cada08fc8a70 335
mbedAustin 11:cada08fc8a70 336 /** \hideinitializer \brief Add an entry before a specified entry.
mbedAustin 11:cada08fc8a70 337 *
mbedAustin 11:cada08fc8a70 338 * \param list `(list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 339 * \param before `(entry_t *)` Existing entry before which to place the new entry.
mbedAustin 11:cada08fc8a70 340 * \param entry `(entry_t * restrict)` Pointer to new entry to add.
mbedAustin 11:cada08fc8a70 341 */
mbedAustin 11:cada08fc8a70 342 #define ns_list_add_before(list, before, entry) \
mbedAustin 11:cada08fc8a70 343 ns_list_add_before_(NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, before), NS_LIST_TYPECHECK_(list, entry))
mbedAustin 11:cada08fc8a70 344
mbedAustin 11:cada08fc8a70 345 /** \hideinitializer \brief Add an entry after a specified entry.
mbedAustin 11:cada08fc8a70 346 *
mbedAustin 11:cada08fc8a70 347 * ns_list_add_before() is *slightly* more efficient than ns_list_add_after().
mbedAustin 11:cada08fc8a70 348 *
mbedAustin 11:cada08fc8a70 349 * \param list `(list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 350 * \param after `(entry_t *)` Existing entry after which to place the new entry.
mbedAustin 11:cada08fc8a70 351 * \param entry `(entry_t * restrict)` Pointer to new entry to add.
mbedAustin 11:cada08fc8a70 352 */
mbedAustin 11:cada08fc8a70 353 #define ns_list_add_after(list, after, entry) \
mbedAustin 11:cada08fc8a70 354 ns_list_add_after_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, after), NS_LIST_TYPECHECK_(list, entry))
mbedAustin 11:cada08fc8a70 355
mbedAustin 11:cada08fc8a70 356 /** \brief Check if a list is empty.
mbedAustin 11:cada08fc8a70 357 *
mbedAustin 11:cada08fc8a70 358 * \param list `(const list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 359 *
mbedAustin 11:cada08fc8a70 360 * \return `(bool)` true if the list is empty.
mbedAustin 11:cada08fc8a70 361 */
mbedAustin 11:cada08fc8a70 362 #define ns_list_is_empty(list) ((bool) ((list)->slist.first_entry == NULL))
mbedAustin 11:cada08fc8a70 363
mbedAustin 11:cada08fc8a70 364 /** \brief Get the first entry.
mbedAustin 11:cada08fc8a70 365 *
mbedAustin 11:cada08fc8a70 366 * \param list `(const list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 367 *
mbedAustin 11:cada08fc8a70 368 * \return `(entry_t *)` Pointer to first entry.
mbedAustin 11:cada08fc8a70 369 * \return NULL if list is empty.
mbedAustin 11:cada08fc8a70 370 */
mbedAustin 11:cada08fc8a70 371 #define ns_list_get_first(list) NS_LIST_TYPECAST_(list, (list)->slist.first_entry)
mbedAustin 11:cada08fc8a70 372
mbedAustin 11:cada08fc8a70 373 /** \hideinitializer \brief Get the previous entry.
mbedAustin 11:cada08fc8a70 374 *
mbedAustin 11:cada08fc8a70 375 * \param list `(const list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 376 * \param current `(const entry_t *)` Pointer to current entry.
mbedAustin 11:cada08fc8a70 377 *
mbedAustin 11:cada08fc8a70 378 * \return `(entry_t *)` Pointer to previous entry.
mbedAustin 11:cada08fc8a70 379 * \return NULL if current entry is first.
mbedAustin 11:cada08fc8a70 380 */
mbedAustin 11:cada08fc8a70 381 #define ns_list_get_previous(list, current) \
mbedAustin 11:cada08fc8a70 382 NS_LIST_TYPECAST_(list, ns_list_get_previous_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, current)))
mbedAustin 11:cada08fc8a70 383
mbedAustin 11:cada08fc8a70 384 /** \hideinitializer \brief Get the next entry.
mbedAustin 11:cada08fc8a70 385 *
mbedAustin 11:cada08fc8a70 386 * \param list `(const list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 387 * \param current `(const entry_t *)` Pointer to current entry.
mbedAustin 11:cada08fc8a70 388 *
mbedAustin 11:cada08fc8a70 389 * \return `(entry_t *)` Pointer to next entry.
mbedAustin 11:cada08fc8a70 390 * \return NULL if current entry is last.
mbedAustin 11:cada08fc8a70 391 */
mbedAustin 11:cada08fc8a70 392 #define ns_list_get_next(list, current) \
mbedAustin 11:cada08fc8a70 393 NS_LIST_TYPECAST_(list, ns_list_get_next_(NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, current)))
mbedAustin 11:cada08fc8a70 394
mbedAustin 11:cada08fc8a70 395 /** \hideinitializer \brief Get the last entry.
mbedAustin 11:cada08fc8a70 396 *
mbedAustin 11:cada08fc8a70 397 * \param list `(const list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 398 *
mbedAustin 11:cada08fc8a70 399 * \return `(entry_t *)` Pointer to last entry.
mbedAustin 11:cada08fc8a70 400 * \return NULL if list is empty.
mbedAustin 11:cada08fc8a70 401 */
mbedAustin 11:cada08fc8a70 402 #define ns_list_get_last(list) \
mbedAustin 11:cada08fc8a70 403 NS_LIST_TYPECAST_(list, ns_list_get_last_(&(list)->slist, NS_LIST_OFFSET_(list)))
mbedAustin 11:cada08fc8a70 404
mbedAustin 11:cada08fc8a70 405 /** \hideinitializer \brief Remove an entry.
mbedAustin 11:cada08fc8a70 406 *
mbedAustin 11:cada08fc8a70 407 * \param list `(list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 408 * \param entry `(entry_t *)` Entry on list to be removed.
mbedAustin 11:cada08fc8a70 409 */
mbedAustin 11:cada08fc8a70 410 #define ns_list_remove(list, entry) \
mbedAustin 11:cada08fc8a70 411 ns_list_remove_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, entry))
mbedAustin 11:cada08fc8a70 412
mbedAustin 11:cada08fc8a70 413 /** \hideinitializer \brief Replace an entry.
mbedAustin 11:cada08fc8a70 414 *
mbedAustin 11:cada08fc8a70 415 * \param list `(list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 416 * \param current `(entry_t *)` Existing entry on list to be replaced.
mbedAustin 11:cada08fc8a70 417 * \param replacement `(entry_t * restrict)` New entry to be the replacement.
mbedAustin 11:cada08fc8a70 418 */
mbedAustin 11:cada08fc8a70 419 #define ns_list_replace(list, current, replacement) \
mbedAustin 11:cada08fc8a70 420 ns_list_replace_(&(list)->slist, NS_LIST_OFFSET_(list), NS_LIST_TYPECHECK_(list, current), NS_LIST_TYPECHECK_(list, replacement))
mbedAustin 11:cada08fc8a70 421
mbedAustin 11:cada08fc8a70 422 /** \hideinitializer \brief Concatenate two lists.
mbedAustin 11:cada08fc8a70 423 *
mbedAustin 11:cada08fc8a70 424 * Attach the entries on the source list to the end of the destination
mbedAustin 11:cada08fc8a70 425 * list, leaving the source list empty.
mbedAustin 11:cada08fc8a70 426 *
mbedAustin 11:cada08fc8a70 427 * \param dst `(list_t *)` Pointer to destination list.
mbedAustin 11:cada08fc8a70 428 * \param src `(list_t *)` Pointer to source list.
mbedAustin 11:cada08fc8a70 429 *
mbedAustin 11:cada08fc8a70 430 */
mbedAustin 11:cada08fc8a70 431 #define ns_list_concatenate(dst, src) \
mbedAustin 11:cada08fc8a70 432 (NS_PTR_MATCH_(dst, src, "concatenating different list types"), \
mbedAustin 11:cada08fc8a70 433 ns_list_concatenate_(&(dst)->slist, &(src)->slist, NS_LIST_OFFSET_(src)))
mbedAustin 11:cada08fc8a70 434
mbedAustin 11:cada08fc8a70 435 /** \brief Iterate forwards over a list.
mbedAustin 11:cada08fc8a70 436 *
mbedAustin 11:cada08fc8a70 437 * Example:
mbedAustin 11:cada08fc8a70 438 * ~~~
mbedAustin 11:cada08fc8a70 439 * ns_list_foreach(const my_entry_t, cur, &my_list)
mbedAustin 11:cada08fc8a70 440 * {
mbedAustin 11:cada08fc8a70 441 * printf("%s\n", cur->name);
mbedAustin 11:cada08fc8a70 442 * }
mbedAustin 11:cada08fc8a70 443 * ~~~
mbedAustin 11:cada08fc8a70 444 * Deletion of the current entry is not permitted as its next is checked after
mbedAustin 11:cada08fc8a70 445 * running user code.
mbedAustin 11:cada08fc8a70 446 *
mbedAustin 11:cada08fc8a70 447 * The iteration pointer is declared inside the loop, using C99/C++, so it
mbedAustin 11:cada08fc8a70 448 * is not accessible after the loop. This encourages good code style, and
mbedAustin 11:cada08fc8a70 449 * matches the semantics of C++11's "ranged for", which only provides the
mbedAustin 11:cada08fc8a70 450 * declaration form:
mbedAustin 11:cada08fc8a70 451 * ~~~
mbedAustin 11:cada08fc8a70 452 * for (const my_entry_t cur : my_list)
mbedAustin 11:cada08fc8a70 453 * ~~~
mbedAustin 11:cada08fc8a70 454 * If you need to see the value of the iteration pointer after a `break`,
mbedAustin 11:cada08fc8a70 455 * you will need to assign it to a variable declared outside the loop before
mbedAustin 11:cada08fc8a70 456 * breaking:
mbedAustin 11:cada08fc8a70 457 * ~~~
mbedAustin 11:cada08fc8a70 458 * my_entry_t *match = NULL;
mbedAustin 11:cada08fc8a70 459 * ns_list_foreach(my_entry_t, cur, &my_list)
mbedAustin 11:cada08fc8a70 460 * {
mbedAustin 11:cada08fc8a70 461 * if (cur->id == id)
mbedAustin 11:cada08fc8a70 462 * {
mbedAustin 11:cada08fc8a70 463 * match = cur;
mbedAustin 11:cada08fc8a70 464 * break;
mbedAustin 11:cada08fc8a70 465 * }
mbedAustin 11:cada08fc8a70 466 * }
mbedAustin 11:cada08fc8a70 467 * ~~~
mbedAustin 11:cada08fc8a70 468 *
mbedAustin 11:cada08fc8a70 469 * The user has to specify the entry type for the pointer definition, as type
mbedAustin 11:cada08fc8a70 470 * extraction from the list argument isn't portable. On the other hand, this
mbedAustin 11:cada08fc8a70 471 * also permits const qualifiers, as in the example above, and serves as
mbedAustin 11:cada08fc8a70 472 * documentation. The entry type will be checked against the list type where the
mbedAustin 11:cada08fc8a70 473 * compiler supports it.
mbedAustin 11:cada08fc8a70 474 *
mbedAustin 11:cada08fc8a70 475 * \param type Entry type `([const] entry_t)`.
mbedAustin 11:cada08fc8a70 476 * \param e Name for iteration pointer to be defined
mbedAustin 11:cada08fc8a70 477 * inside the loop.
mbedAustin 11:cada08fc8a70 478 * \param list `(const list_t *)` Pointer to list - evaluated multiple times.
mbedAustin 11:cada08fc8a70 479 */
mbedAustin 11:cada08fc8a70 480 #define ns_list_foreach(type, e, list) \
mbedAustin 11:cada08fc8a70 481 for (type *e = ns_list_get_first(list); e; e = ns_list_get_next(list, e))
mbedAustin 11:cada08fc8a70 482
mbedAustin 11:cada08fc8a70 483 /** \brief Iterate forwards over a list, where user may delete.
mbedAustin 11:cada08fc8a70 484 *
mbedAustin 11:cada08fc8a70 485 * As ns_list_foreach(), but deletion of current entry is permitted as its
mbedAustin 11:cada08fc8a70 486 * next pointer is recorded before running user code.
mbedAustin 11:cada08fc8a70 487 *
mbedAustin 11:cada08fc8a70 488 * Example:
mbedAustin 11:cada08fc8a70 489 * ~~~
mbedAustin 11:cada08fc8a70 490 * ns_list_foreach_safe(my_entry_t, cur, &my_list)
mbedAustin 11:cada08fc8a70 491 * {
mbedAustin 11:cada08fc8a70 492 * ns_list_remove(cur);
mbedAustin 11:cada08fc8a70 493 * }
mbedAustin 11:cada08fc8a70 494 * ~~~
mbedAustin 11:cada08fc8a70 495 * \param type Entry type `(entry_t)`.
mbedAustin 11:cada08fc8a70 496 * \param e Name for iteration pointer to be defined
mbedAustin 11:cada08fc8a70 497 * inside the loop.
mbedAustin 11:cada08fc8a70 498 * \param list `(list_t *)` Pointer to list - evaluated multiple times.
mbedAustin 11:cada08fc8a70 499 */
mbedAustin 11:cada08fc8a70 500 #define ns_list_foreach_safe(type, e, list) \
mbedAustin 11:cada08fc8a70 501 for (type *e = ns_list_get_first(list), *_next; \
mbedAustin 11:cada08fc8a70 502 e && (_next = ns_list_get_next(list, e), true); e = _next)
mbedAustin 11:cada08fc8a70 503
mbedAustin 11:cada08fc8a70 504 /** \brief Iterate backwards over a list.
mbedAustin 11:cada08fc8a70 505 *
mbedAustin 11:cada08fc8a70 506 * As ns_list_foreach(), but going backwards - see its documentation.
mbedAustin 11:cada08fc8a70 507 * Iterating forwards is *slightly* more efficient.
mbedAustin 11:cada08fc8a70 508 */
mbedAustin 11:cada08fc8a70 509 #define ns_list_foreach_reverse(type, e, list) \
mbedAustin 11:cada08fc8a70 510 for (type *e = ns_list_get_last(list); e; e = ns_list_get_previous(list, e))
mbedAustin 11:cada08fc8a70 511
mbedAustin 11:cada08fc8a70 512 /** \brief Iterate backwards over a list, where user may delete.
mbedAustin 11:cada08fc8a70 513 *
mbedAustin 11:cada08fc8a70 514 * As ns_list_foreach_safe(), but going backwards - see its documentation.
mbedAustin 11:cada08fc8a70 515 * Iterating forwards is *slightly* more efficient.
mbedAustin 11:cada08fc8a70 516 */
mbedAustin 11:cada08fc8a70 517 #define ns_list_foreach_reverse_safe(type, e, list) \
mbedAustin 11:cada08fc8a70 518 for (type *e = ns_list_get_last(list), *_next; \
mbedAustin 11:cada08fc8a70 519 e && (_next = ns_list_get_previous(list, e), true); e = _next)
mbedAustin 11:cada08fc8a70 520
mbedAustin 11:cada08fc8a70 521 /** \hideinitializer \brief Count entries on a list
mbedAustin 11:cada08fc8a70 522 *
mbedAustin 11:cada08fc8a70 523 * Unlike other operations, this is O(n). Note: if list might contain over
mbedAustin 11:cada08fc8a70 524 * 65535 entries, this function **must not** be used to get the entry count.
mbedAustin 11:cada08fc8a70 525 *
mbedAustin 11:cada08fc8a70 526 * \param list `(const list_t *)` Pointer to list.
mbedAustin 11:cada08fc8a70 527
mbedAustin 11:cada08fc8a70 528 * \return `(uint_fast16_t)` Number of entries that are stored in list.
mbedAustin 11:cada08fc8a70 529 */
mbedAustin 11:cada08fc8a70 530 #define ns_list_count(list) ns_list_count_(&(list)->slist, NS_LIST_OFFSET_(list))
mbedAustin 11:cada08fc8a70 531
mbedAustin 11:cada08fc8a70 532 /** \privatesection
mbedAustin 11:cada08fc8a70 533 * Internal functions - designed to be accessed using corresponding macros above
mbedAustin 11:cada08fc8a70 534 */
mbedAustin 11:cada08fc8a70 535 NS_INLINE void ns_list_init_(ns_list_t *list);
mbedAustin 11:cada08fc8a70 536 NS_INLINE void ns_list_link_init_(ns_list_link_t *link);
mbedAustin 11:cada08fc8a70 537 NS_INLINE void ns_list_add_to_start_(ns_list_t *list, ns_list_offset_t link_offset, void *restrict entry);
mbedAustin 11:cada08fc8a70 538 NS_INLINE void ns_list_add_to_end_(ns_list_t *list, ns_list_offset_t link_offset, void *restrict entry);
mbedAustin 11:cada08fc8a70 539 NS_INLINE void ns_list_add_before_(ns_list_offset_t link_offset, void *before, void *restrict entry);
mbedAustin 11:cada08fc8a70 540 NS_INLINE void ns_list_add_after_(ns_list_t *list, ns_list_offset_t link_offset, void *after, void *restrict entry);
mbedAustin 11:cada08fc8a70 541 NS_INLINE void *ns_list_get_next_(ns_list_offset_t link_offset, const void *current);
mbedAustin 11:cada08fc8a70 542 NS_INLINE void *ns_list_get_previous_(const ns_list_t *list, ns_list_offset_t link_offset, const void *current);
mbedAustin 11:cada08fc8a70 543 NS_INLINE void *ns_list_get_last_(const ns_list_t *list, ns_list_offset_t offset);
mbedAustin 11:cada08fc8a70 544 NS_INLINE void ns_list_remove_(ns_list_t *list, ns_list_offset_t link_offset, void *entry);
mbedAustin 11:cada08fc8a70 545 NS_INLINE void ns_list_replace_(ns_list_t *list, ns_list_offset_t link_offset, void *current, void *restrict replacement);
mbedAustin 11:cada08fc8a70 546 NS_INLINE void ns_list_concatenate_(ns_list_t *dst, ns_list_t *src, ns_list_offset_t offset);
mbedAustin 11:cada08fc8a70 547 NS_INLINE uint_fast16_t ns_list_count_(const ns_list_t *list, ns_list_offset_t link_offset);
mbedAustin 11:cada08fc8a70 548
mbedAustin 11:cada08fc8a70 549 /* Provide definitions, either for inlining, or for ns_list.c */
mbedAustin 11:cada08fc8a70 550 #if defined NS_ALLOW_INLINING || defined NS_LIST_FN
mbedAustin 11:cada08fc8a70 551 #ifndef NS_LIST_FN
mbedAustin 11:cada08fc8a70 552 #define NS_LIST_FN NS_INLINE
mbedAustin 11:cada08fc8a70 553 #endif
mbedAustin 11:cada08fc8a70 554
mbedAustin 11:cada08fc8a70 555 /* Pointer to the link member in entry e */
mbedAustin 11:cada08fc8a70 556 #define NS_LIST_LINK_(e, offset) ((ns_list_link_t *)((char *)(e) + offset))
mbedAustin 11:cada08fc8a70 557
mbedAustin 11:cada08fc8a70 558 /* Lvalue of the next link pointer in entry e */
mbedAustin 11:cada08fc8a70 559 #define NS_LIST_NEXT_(e, offset) (NS_LIST_LINK_(e, offset)->next)
mbedAustin 11:cada08fc8a70 560
mbedAustin 11:cada08fc8a70 561 /* Lvalue of the prev link pointer in entry e */
mbedAustin 11:cada08fc8a70 562 #define NS_LIST_PREV_(e, offset) (NS_LIST_LINK_(e, offset)->prev)
mbedAustin 11:cada08fc8a70 563
mbedAustin 11:cada08fc8a70 564 /* Convert a pointer to a link member back to the entry;
mbedAustin 11:cada08fc8a70 565 * works for linkptr either being a ns_list_link_t pointer, or its next pointer,
mbedAustin 11:cada08fc8a70 566 * as the next pointer is first in the ns_list_link_t */
mbedAustin 11:cada08fc8a70 567 #define NS_LIST_ENTRY_(linkptr, offset) ((void *)((char *)(linkptr) - offset))
mbedAustin 11:cada08fc8a70 568
mbedAustin 11:cada08fc8a70 569 NS_LIST_FN void ns_list_init_(ns_list_t *list)
mbedAustin 11:cada08fc8a70 570 {
mbedAustin 11:cada08fc8a70 571 list->first_entry = NULL;
mbedAustin 11:cada08fc8a70 572 list->last_nextptr = &list->first_entry;
mbedAustin 11:cada08fc8a70 573 }
mbedAustin 11:cada08fc8a70 574
mbedAustin 11:cada08fc8a70 575 NS_LIST_FN void ns_list_link_init_(ns_list_link_t *link)
mbedAustin 11:cada08fc8a70 576 {
mbedAustin 11:cada08fc8a70 577 NS_FUNNY_INTPTR_OK
mbedAustin 11:cada08fc8a70 578 link->next = NS_LIST_POISON;
mbedAustin 11:cada08fc8a70 579 link->prev = NS_LIST_POISON;
mbedAustin 11:cada08fc8a70 580 NS_FUNNY_INTPTR_RESTORE
mbedAustin 11:cada08fc8a70 581 }
mbedAustin 11:cada08fc8a70 582
mbedAustin 11:cada08fc8a70 583 NS_LIST_FN void ns_list_add_to_start_(ns_list_t *list, ns_list_offset_t offset, void *restrict entry)
mbedAustin 11:cada08fc8a70 584 {
mbedAustin 11:cada08fc8a70 585 void *next;
mbedAustin 11:cada08fc8a70 586
mbedAustin 11:cada08fc8a70 587 NS_LIST_PREV_(entry, offset) = &list->first_entry;
mbedAustin 11:cada08fc8a70 588 NS_LIST_NEXT_(entry, offset) = next = list->first_entry;
mbedAustin 11:cada08fc8a70 589
mbedAustin 11:cada08fc8a70 590 if (next) {
mbedAustin 11:cada08fc8a70 591 NS_LIST_PREV_(next, offset) = &NS_LIST_NEXT_(entry, offset);
mbedAustin 11:cada08fc8a70 592 } else {
mbedAustin 11:cada08fc8a70 593 list->last_nextptr = &NS_LIST_NEXT_(entry, offset);
mbedAustin 11:cada08fc8a70 594 }
mbedAustin 11:cada08fc8a70 595
mbedAustin 11:cada08fc8a70 596 list->first_entry = entry;
mbedAustin 11:cada08fc8a70 597 }
mbedAustin 11:cada08fc8a70 598
mbedAustin 11:cada08fc8a70 599 NS_LIST_FN void ns_list_add_after_(ns_list_t *list, ns_list_offset_t offset, void *current, void *restrict entry)
mbedAustin 11:cada08fc8a70 600 {
mbedAustin 11:cada08fc8a70 601 void *next;
mbedAustin 11:cada08fc8a70 602
mbedAustin 11:cada08fc8a70 603 NS_LIST_PREV_(entry, offset) = &NS_LIST_NEXT_(current, offset);
mbedAustin 11:cada08fc8a70 604 NS_LIST_NEXT_(entry, offset) = next = NS_LIST_NEXT_(current, offset);
mbedAustin 11:cada08fc8a70 605
mbedAustin 11:cada08fc8a70 606 if (next) {
mbedAustin 11:cada08fc8a70 607 NS_LIST_PREV_(next, offset) = &NS_LIST_NEXT_(entry, offset);
mbedAustin 11:cada08fc8a70 608 } else {
mbedAustin 11:cada08fc8a70 609 list->last_nextptr = &NS_LIST_NEXT_(entry, offset);
mbedAustin 11:cada08fc8a70 610 }
mbedAustin 11:cada08fc8a70 611
mbedAustin 11:cada08fc8a70 612 NS_LIST_NEXT_(current, offset) = entry;
mbedAustin 11:cada08fc8a70 613 }
mbedAustin 11:cada08fc8a70 614
mbedAustin 11:cada08fc8a70 615 NS_LIST_FN void ns_list_add_before_(ns_list_offset_t offset, void *current, void *restrict entry)
mbedAustin 11:cada08fc8a70 616 {
mbedAustin 11:cada08fc8a70 617 void **prev_nextptr;
mbedAustin 11:cada08fc8a70 618
mbedAustin 11:cada08fc8a70 619 NS_LIST_NEXT_(entry, offset) = current;
mbedAustin 11:cada08fc8a70 620 NS_LIST_PREV_(entry, offset) = prev_nextptr = NS_LIST_PREV_(current, offset);
mbedAustin 11:cada08fc8a70 621 *prev_nextptr = entry;
mbedAustin 11:cada08fc8a70 622 NS_LIST_PREV_(current, offset) = &NS_LIST_NEXT_(entry, offset);
mbedAustin 11:cada08fc8a70 623 }
mbedAustin 11:cada08fc8a70 624
mbedAustin 11:cada08fc8a70 625 NS_LIST_FN void ns_list_add_to_end_(ns_list_t *list, ns_list_offset_t offset, void *restrict entry)
mbedAustin 11:cada08fc8a70 626 {
mbedAustin 11:cada08fc8a70 627 void **prev_nextptr;
mbedAustin 11:cada08fc8a70 628
mbedAustin 11:cada08fc8a70 629 NS_LIST_NEXT_(entry, offset) = NULL;
mbedAustin 11:cada08fc8a70 630 NS_LIST_PREV_(entry, offset) = prev_nextptr = list->last_nextptr;
mbedAustin 11:cada08fc8a70 631 *prev_nextptr = entry;
mbedAustin 11:cada08fc8a70 632 list->last_nextptr = &NS_LIST_NEXT_(entry, offset);
mbedAustin 11:cada08fc8a70 633 }
mbedAustin 11:cada08fc8a70 634
mbedAustin 11:cada08fc8a70 635 NS_LIST_FN void *ns_list_get_next_(ns_list_offset_t offset, const void *current)
mbedAustin 11:cada08fc8a70 636 {
mbedAustin 11:cada08fc8a70 637 return NS_LIST_NEXT_(current, offset);
mbedAustin 11:cada08fc8a70 638 }
mbedAustin 11:cada08fc8a70 639
mbedAustin 11:cada08fc8a70 640 NS_LIST_FN void *ns_list_get_previous_(const ns_list_t *list, ns_list_offset_t offset, const void *current)
mbedAustin 11:cada08fc8a70 641 {
mbedAustin 11:cada08fc8a70 642 if (current == list->first_entry) {
mbedAustin 11:cada08fc8a70 643 return NULL;
mbedAustin 11:cada08fc8a70 644 }
mbedAustin 11:cada08fc8a70 645
mbedAustin 11:cada08fc8a70 646 // Tricky. We don't have a direct previous pointer, but a pointer to the
mbedAustin 11:cada08fc8a70 647 // pointer that points to us - ie &head->first_entry OR &{prev}->next.
mbedAustin 11:cada08fc8a70 648 // This makes life easier on insertion and removal, but this is where we
mbedAustin 11:cada08fc8a70 649 // pay the price.
mbedAustin 11:cada08fc8a70 650
mbedAustin 11:cada08fc8a70 651 // We have to check manually for being the first entry above, so we know it's
mbedAustin 11:cada08fc8a70 652 // a real link's next pointer. Then next is the first field of
mbedAustin 11:cada08fc8a70 653 // ns_list_link_t, so we can use the normal offset value.
mbedAustin 11:cada08fc8a70 654
mbedAustin 11:cada08fc8a70 655 return NS_LIST_ENTRY_(NS_LIST_PREV_(current, offset), offset);
mbedAustin 11:cada08fc8a70 656 }
mbedAustin 11:cada08fc8a70 657
mbedAustin 11:cada08fc8a70 658 NS_LIST_FN void *ns_list_get_last_(const ns_list_t *list, ns_list_offset_t offset)
mbedAustin 11:cada08fc8a70 659 {
mbedAustin 11:cada08fc8a70 660 if (!list->first_entry) {
mbedAustin 11:cada08fc8a70 661 return NULL;
mbedAustin 11:cada08fc8a70 662 }
mbedAustin 11:cada08fc8a70 663
mbedAustin 11:cada08fc8a70 664 // See comments in ns_list_get_previous_()
mbedAustin 11:cada08fc8a70 665 return NS_LIST_ENTRY_(list->last_nextptr, offset);
mbedAustin 11:cada08fc8a70 666 }
mbedAustin 11:cada08fc8a70 667
mbedAustin 11:cada08fc8a70 668 NS_LIST_FN void ns_list_remove_(ns_list_t *list, ns_list_offset_t offset, void *removed)
mbedAustin 11:cada08fc8a70 669 {
mbedAustin 11:cada08fc8a70 670 void *next;
mbedAustin 11:cada08fc8a70 671 void **prev_nextptr;
mbedAustin 11:cada08fc8a70 672
mbedAustin 11:cada08fc8a70 673 next = NS_LIST_NEXT_(removed, offset);
mbedAustin 11:cada08fc8a70 674 prev_nextptr = NS_LIST_PREV_(removed, offset);
mbedAustin 11:cada08fc8a70 675 if (next) {
mbedAustin 11:cada08fc8a70 676 NS_LIST_PREV_(next, offset) = prev_nextptr;
mbedAustin 11:cada08fc8a70 677 } else {
mbedAustin 11:cada08fc8a70 678 list->last_nextptr = prev_nextptr;
mbedAustin 11:cada08fc8a70 679 }
mbedAustin 11:cada08fc8a70 680 *prev_nextptr = next;
mbedAustin 11:cada08fc8a70 681
mbedAustin 11:cada08fc8a70 682 ns_list_link_init_(NS_LIST_LINK_(removed, offset));
mbedAustin 11:cada08fc8a70 683 }
mbedAustin 11:cada08fc8a70 684
mbedAustin 11:cada08fc8a70 685 NS_LIST_FN void ns_list_replace_(ns_list_t *list, ns_list_offset_t offset, void *current, void *restrict replacement)
mbedAustin 11:cada08fc8a70 686 {
mbedAustin 11:cada08fc8a70 687 void *next;
mbedAustin 11:cada08fc8a70 688 void **prev_nextptr;
mbedAustin 11:cada08fc8a70 689
mbedAustin 11:cada08fc8a70 690 NS_LIST_PREV_(replacement, offset) = prev_nextptr = NS_LIST_PREV_(current, offset);
mbedAustin 11:cada08fc8a70 691 NS_LIST_NEXT_(replacement, offset) = next = NS_LIST_NEXT_(current, offset);
mbedAustin 11:cada08fc8a70 692
mbedAustin 11:cada08fc8a70 693 if (next) {
mbedAustin 11:cada08fc8a70 694 NS_LIST_PREV_(next, offset) = &NS_LIST_NEXT_(replacement, offset);
mbedAustin 11:cada08fc8a70 695 } else {
mbedAustin 11:cada08fc8a70 696 list->last_nextptr = &NS_LIST_NEXT_(replacement, offset);
mbedAustin 11:cada08fc8a70 697 }
mbedAustin 11:cada08fc8a70 698 *prev_nextptr = replacement;
mbedAustin 11:cada08fc8a70 699
mbedAustin 11:cada08fc8a70 700 ns_list_link_init_(NS_LIST_LINK_(current, offset));
mbedAustin 11:cada08fc8a70 701 }
mbedAustin 11:cada08fc8a70 702
mbedAustin 11:cada08fc8a70 703 NS_LIST_FN void ns_list_concatenate_(ns_list_t *dst, ns_list_t *src, ns_list_offset_t offset)
mbedAustin 11:cada08fc8a70 704 {
mbedAustin 11:cada08fc8a70 705 ns_list_link_t *src_first;
mbedAustin 11:cada08fc8a70 706
mbedAustin 11:cada08fc8a70 707 src_first = src->first_entry;
mbedAustin 11:cada08fc8a70 708 if (!src_first) {
mbedAustin 11:cada08fc8a70 709 return;
mbedAustin 11:cada08fc8a70 710 }
mbedAustin 11:cada08fc8a70 711
mbedAustin 11:cada08fc8a70 712 *dst->last_nextptr = src_first;
mbedAustin 11:cada08fc8a70 713 NS_LIST_PREV_(src_first, offset) = dst->last_nextptr;
mbedAustin 11:cada08fc8a70 714 dst->last_nextptr = src->last_nextptr;
mbedAustin 11:cada08fc8a70 715
mbedAustin 11:cada08fc8a70 716 ns_list_init_(src);
mbedAustin 11:cada08fc8a70 717 }
mbedAustin 11:cada08fc8a70 718
mbedAustin 11:cada08fc8a70 719 NS_LIST_FN uint_fast16_t ns_list_count_(const ns_list_t *list, ns_list_offset_t offset)
mbedAustin 11:cada08fc8a70 720 {
mbedAustin 11:cada08fc8a70 721 uint_fast16_t count = 0;
mbedAustin 11:cada08fc8a70 722
mbedAustin 11:cada08fc8a70 723 for (void *p = list->first_entry; p; p = NS_LIST_NEXT_(p, offset)) {
mbedAustin 11:cada08fc8a70 724 count++;
mbedAustin 11:cada08fc8a70 725 }
mbedAustin 11:cada08fc8a70 726
mbedAustin 11:cada08fc8a70 727 return count;
mbedAustin 11:cada08fc8a70 728 }
mbedAustin 11:cada08fc8a70 729 #endif /* defined NS_ALLOW_INLINING || defined NS_LIST_FN */
mbedAustin 11:cada08fc8a70 730
mbedAustin 11:cada08fc8a70 731 #ifdef __cplusplus
mbedAustin 11:cada08fc8a70 732 }
mbedAustin 11:cada08fc8a70 733 #endif
mbedAustin 11:cada08fc8a70 734
mbedAustin 11:cada08fc8a70 735 #endif /* NS_LIST_H_ */
mbedAustin 11:cada08fc8a70 736