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