bowen liu / Mbed OS mbed-os-example-blinky

ex

Fork of mbed-os-example-mbed5-blinky by mbed-os-examples

DuerOS-Light-SDK-v1.1.0/duer-os-light/src/iot-baidu-ca/source/ns_list.h@47:9e361da97763, 2017-07-18 (annotated)

Committer:
TMBOY
Date:
Tue Jul 18 16:54:45 2017 +0800
Revision:
47:9e361da97763
?

Who changed what in which revision?

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