mhd_dlinked_list.h (16629B)
1 /* SPDX-License-Identifier: LGPL-2.1-or-later OR (GPL-2.0-or-later WITH eCos-exception-2.0) */ 2 /* 3 This file is part of GNU libmicrohttpd. 4 Copyright (C) 2024-2026 Evgeny Grin (Karlson2k) 5 6 GNU libmicrohttpd is free software; you can redistribute it and/or 7 modify it under the terms of the GNU Lesser General Public 8 License as published by the Free Software Foundation; either 9 version 2.1 of the License, or (at your option) any later version. 10 11 GNU libmicrohttpd is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 Lesser General Public License for more details. 15 16 Alternatively, you can redistribute GNU libmicrohttpd and/or 17 modify it under the terms of the GNU General Public License as 18 published by the Free Software Foundation; either version 2 of 19 the License, or (at your option) any later version, together 20 with the eCos exception, as follows: 21 22 As a special exception, if other files instantiate templates or 23 use macros or inline functions from this file, or you compile this 24 file and link it with other works to produce a work based on this 25 file, this file does not by itself cause the resulting work to be 26 covered by the GNU General Public License. However the source code 27 for this file must still be made available in accordance with 28 section (3) of the GNU General Public License v2. 29 30 This exception does not invalidate any other reasons why a work 31 based on this file might be covered by the GNU General Public 32 License. 33 34 You should have received copies of the GNU Lesser General Public 35 License and the GNU General Public License along with this library; 36 if not, see <https://www.gnu.org/licenses/>. 37 */ 38 39 /** 40 * @file src/mhd2/mhd_dlinked_list.h 41 * @brief Doubly-linked list macros and declarations 42 * @author Karlson2k (Evgeny Grin) 43 * 44 * Doubly-linked list macros help create and manage the chain of objects 45 * connected via inter-link pointers (named here @a links_name), while 46 * the list is held by the owner in the helper struct (named here @a list_name). 47 */ 48 49 #ifndef MHD_DLINKED_LIST_H 50 #define MHD_DLINKED_LIST_H 1 51 52 #include "mhd_sys_options.h" 53 54 #include "sys_null_macro.h" 55 #include "mhd_assume.h" 56 57 58 /* This header defines macros for handling doubly-linked lists of objects 59 (list elements). The pointers to the first and the last elements in the 60 list are held in the list "owner". 61 The list elements connect to each other via "next" and "prev" inter-links. 62 Each element can be part of several lists at the same time, if referenced 63 by differently named fields with inter-links. For example, connections are 64 maintained in "all connections" and "need to be processed" lists 65 simultaneously. 66 A list element can be removed from the list (if it is already in the list) 67 or inserted into the list (if it is NOT in the list) at any moment. 68 Typically the name of the list (the field inside the "owner" object) is 69 the same as the name of field with inter-links. However, it is possible to 70 use different names. For example, connections can be removed from "all 71 connections" list and moved to the "clean up" list using the same internal 72 inter-links field "all connections". 73 As this is a doubly-linked list, it can be walked from the beginning to 74 the end and in the opposite direction. 75 The list is designed to work with struct tags as contained and container 76 objects. 77 */ 78 79 /* Helpers */ 80 81 #define mhd_DLNKDL_LIST_TYPE_(base_name) struct base_name ## _list 82 83 #define mhd_DLNKDL_LINKS_TYPE_(base_name) struct base_name ## _links 84 85 86 /* Names */ 87 88 /** 89 * The name of the struct (struct tag) that holds the list in the owner object 90 */ 91 #define mhd_DLNKDL_LIST_TYPE(base_name) mhd_DLNKDL_LIST_TYPE_ (base_name) 92 93 /** 94 * The name of the struct (struct tag) that holds the inter-links between list 95 * elements 96 */ 97 #define mhd_DLNKDL_LINKS_TYPE(base_name) mhd_DLNKDL_LINKS_TYPE_ (base_name) 98 99 100 /* Definitions of the structures */ 101 102 /** 103 * Template for declaration of the list helper struct 104 * @param l_type the struct tag name of elements that the list holds 105 */ 106 #define mhd_DLINKEDL_LIST_DEF(l_type) \ 107 mhd_DLNKDL_LIST_TYPE (l_type) { /* Holds the list in the owner */ \ 108 struct l_type *first; /* The pointer to the first element in the list */ \ 109 struct l_type *last; /* The pointer to the last element in the list */ \ 110 } 111 112 /** 113 * Template for declaration of the inter-links helper struct 114 * @param l_type the struct tag name of elements linked by the inter-links 115 */ 116 #define mhd_DLINKEDL_LINKS_DEF(l_type) \ 117 mhd_DLNKDL_LINKS_TYPE (l_type) { /* The inter-links in the list element */ \ 118 struct l_type *prev; /* The previous element in the list */ \ 119 struct l_type *next; /* The next element in the list */ \ 120 } 121 122 /** 123 * Template for declaration of the list helper structs 124 * @param l_type the struct tag name of elements that the list holds 125 */ 126 #define mhd_DLINKEDL_STRUCTS_DEFS(l_type) \ 127 mhd_DLINKEDL_LIST_DEF (l_type); mhd_DLINKEDL_LINKS_DEF (l_type) 128 129 130 /* Declarations of the types for the list owners and the list elements */ 131 132 /** 133 * Declare the list field in the owner struct 134 */ 135 #define mhd_DLNKDL_LIST(l_type, list_name) \ 136 mhd_DLNKDL_LIST_TYPE (l_type) list_name 137 138 /** 139 * Declare the inter-links field in the list element 140 */ 141 #define mhd_DLNKDL_LINKS(l_type, links_name) \ 142 mhd_DLNKDL_LINKS_TYPE (l_type) links_name 143 144 /* Direct work with the list */ 145 /* These macros directly use the pointer to the list and allow using 146 * names of the list field (within the owner object) different from the 147 * names of the inter-links field (in the list elements). */ 148 149 /** 150 * Initialise the doubly linked list pointers in the list owner using 151 * the direct pointer to the list 152 * @warning arguments are evaluated multiple times 153 * @param p_list the pointer to the list 154 */ 155 #define mhd_DLINKEDL_INIT_LIST_D(p_list) \ 156 do {(p_list)->first = NULL; (p_list)->last = NULL;} while (0) 157 158 /** 159 * Insert new list element into the first position in the list using direct 160 * pointer to the list 161 * @warning arguments are evaluated multiple times 162 * @param p_list the pointer to the list 163 * @param p_obj the pointer to the new element to insert into the list, 164 * using @a links_name inter-links 165 * @param links_name the name of the inter-links field in the @a p_obj 166 */ 167 #define mhd_DLINKEDL_INS_FIRST_D(p_list, p_obj, links_name) do { \ 168 mhd_ASSUME (NULL == (p_obj)->links_name.prev); \ 169 mhd_ASSUME (NULL == (p_obj)->links_name.next); \ 170 mhd_ASSUME ((p_obj) != (p_list)->first); \ 171 mhd_ASSUME ((p_obj) != (p_list)->last); \ 172 if (NULL != (p_list)->first) \ 173 { mhd_ASSUME (NULL == (p_list)->first->links_name.prev); \ 174 mhd_ASSUME (NULL == (p_list)->last->links_name.next); \ 175 mhd_ASSUME ((p_obj) != (p_list)->first->links_name.next); \ 176 mhd_ASSUME (NULL != (p_list)->last); \ 177 ((p_obj)->links_name.next = (p_list)->first) \ 178 ->links_name.prev = (p_obj); } else \ 179 { mhd_ASSUME (NULL == (p_list)->last); \ 180 (p_list)->last = (p_obj); } \ 181 (p_list)->first = (p_obj); } while (0) 182 183 /** 184 * Insert new list element into the last position in the list using direct 185 * pointer to the list 186 * @warning arguments are evaluated multiple times 187 * @param p_list the pointer to the list 188 * @param p_obj the pointer to the new element to insert into the list, 189 * using @a links_name inter-links 190 * @param links_name the name of the inter-links field in the @a p_obj 191 */ 192 #define mhd_DLINKEDL_INS_LAST_D(p_list, p_obj, links_name) do { \ 193 mhd_ASSUME (NULL == (p_obj)->links_name.prev); \ 194 mhd_ASSUME (NULL == (p_obj)->links_name.next); \ 195 mhd_ASSUME ((p_obj) != (p_list)->first); \ 196 mhd_ASSUME ((p_obj) != (p_list)->last); \ 197 if (NULL != (p_list)->last) \ 198 { mhd_ASSUME (NULL == (p_list)->last->links_name.next); \ 199 mhd_ASSUME (NULL == (p_list)->first->links_name.prev); \ 200 mhd_ASSUME ((p_obj) != (p_list)->last->links_name.prev); \ 201 mhd_ASSUME (NULL != (p_list)->first); \ 202 ((p_obj)->links_name.prev = (p_list)->last) \ 203 ->links_name.next = (p_obj); } else \ 204 { mhd_ASSUME (NULL == (p_list)->first); \ 205 (p_list)->first = (p_obj); } \ 206 (p_list)->last = (p_obj); } while (0) 207 208 /** 209 * Remove list element from the list using direct pointer to the list 210 * @warning arguments are evaluated multiple times 211 * @param p_list the pointer to the list 212 * @param p_obj the pointer to the existing list element to remove from the list 213 * @param links_name the name of the inter-links field in the @a p_obj 214 */ 215 #define mhd_DLINKEDL_DEL_D(p_list, p_obj, links_name) do { \ 216 mhd_ASSUME (NULL != (p_list)->first); \ 217 mhd_ASSUME (NULL != (p_list)->last); \ 218 mhd_ASSUME (NULL == (p_list)->first->links_name.prev); \ 219 mhd_ASSUME (NULL == (p_list)->last->links_name.next); \ 220 mhd_ASSUME ((p_obj) != (p_obj)->links_name.prev); \ 221 mhd_ASSUME ((p_list)->last != (p_obj)->links_name.prev); \ 222 mhd_ASSUME ((p_obj) != (p_obj)->links_name.next); \ 223 mhd_ASSUME ((p_list)->first != (p_obj)->links_name.next); \ 224 if (NULL != (p_obj)->links_name.next) \ 225 { mhd_ASSUME ((p_obj) == (p_obj)->links_name.next->links_name.prev); \ 226 mhd_ASSUME ((p_obj) != (p_list)->last); \ 227 mhd_ASSUME ((p_obj)->links_name.next != \ 228 (p_obj)->links_name.prev); \ 229 (p_obj)->links_name.next->links_name.prev = \ 230 (p_obj)->links_name.prev; } else \ 231 { mhd_ASSUME ((p_obj) == (p_list)->last); \ 232 (p_list)->last = (p_obj)->links_name.prev; } \ 233 if (NULL != (p_obj)->links_name.prev) \ 234 { mhd_ASSUME ((p_obj) == (p_obj)->links_name.prev->links_name.next); \ 235 mhd_ASSUME ((p_obj) != (p_list)->first); \ 236 mhd_ASSUME ((p_obj)->links_name.next != \ 237 (p_obj)->links_name.prev); \ 238 (p_obj)->links_name.prev->links_name.next = \ 239 (p_obj)->links_name.next; } else \ 240 { mhd_ASSUME ((p_obj) == (p_list)->first); \ 241 (p_list)->first = (p_obj)->links_name.next; } \ 242 (p_obj)->links_name.prev = NULL; \ 243 (p_obj)->links_name.next = NULL; } while (0) 244 245 /** 246 * Get the first element in the list using direct pointer to the list 247 */ 248 #define mhd_DLINKEDL_GET_FIRST_D(p_list) ((p_list)->first) 249 250 /** 251 * Get the last element in the list using direct pointer to the list 252 */ 253 #define mhd_DLINKEDL_GET_LAST_D(p_list) ((p_list)->last) 254 255 /** 256 * Move the list element within the list to the first position using a direct 257 * pointer to the list 258 * @warning arguments are evaluated multiple times 259 * @param p_list the pointer to the list 260 * @param p_obj the pointer to the existing list element to move to the 261 * first position 262 * @param links_name the name of the inter-links field in the @a p_obj 263 */ 264 #define mhd_DLINKEDL_MOVE_TO_FIRST_D(p_list, p_obj, links_name) do { \ 265 mhd_ASSUME (NULL != (p_list)->first); \ 266 mhd_ASSUME (NULL != (p_list)->last); \ 267 mhd_ASSUME ((p_obj) != (p_obj)->links_name.next); \ 268 mhd_ASSUME ((p_obj) != (p_obj)->links_name.prev); \ 269 if (NULL == (p_obj)->links_name.prev) \ 270 { mhd_ASSUME ((p_obj) == (p_list)->first); } else \ 271 { mhd_ASSUME ((p_obj) != (p_list)->first); \ 272 mhd_ASSUME ((p_obj) == \ 273 (p_obj)->links_name.prev->links_name.next); \ 274 (p_obj)->links_name.prev->links_name.next = \ 275 (p_obj)->links_name.next; \ 276 if (NULL == (p_obj)->links_name.next) \ 277 { mhd_ASSUME ((p_obj) == (p_list)->last); \ 278 (p_list)->last = (p_obj)->links_name.prev; } else \ 279 { mhd_ASSUME ((p_obj) != (p_list)->last); \ 280 mhd_ASSUME ((p_obj) == \ 281 (p_obj)->links_name.next->links_name.prev); \ 282 (p_obj)->links_name.next->links_name.prev = \ 283 (p_obj)->links_name.prev; } \ 284 (p_obj)->links_name.next = (p_list)->first; \ 285 (p_obj)->links_name.prev = NULL; \ 286 (p_list)->first->links_name.prev = (p_obj); \ 287 (p_list)->first = (p_obj); } } while (0) 288 289 290 /* ** The main interface ** */ 291 /* These macros use identical names for the list field (within the owner 292 * object) and the inter-links field (within the list elements). */ 293 294 /* Initialisers */ 295 296 /** 297 * Initialise the doubly linked list pointers in the owner object 298 * @warning arguments are evaluated multiple times 299 * @param p_own the pointer to the owner object with the @a list_name list 300 * @param list_name the name of the list 301 */ 302 #define mhd_DLINKEDL_INIT_LIST(p_own, list_name) \ 303 mhd_DLINKEDL_INIT_LIST_D (&((p_own)->list_name)) 304 305 /** 306 * Initialise the doubly linked list pointers in the list element 307 * @warning arguments are evaluated multiple times 308 * @param p_obj the pointer to the future element of 309 * the @a links_name list 310 * @param links_name the name of the inter-links field in the @a p_obj 311 */ 312 #define mhd_DLINKEDL_INIT_LINKS(p_obj, links_name) \ 313 do {(p_obj)->links_name.prev = NULL; \ 314 (p_obj)->links_name.next = NULL;} while (0) 315 316 /* List manipulations */ 317 318 /** 319 * Insert new list element into the first position in the list 320 * @warning arguments are evaluated multiple times 321 * @param p_own the pointer to the owner object with the @a l_name list 322 * @param p_obj the pointer to the new list element to insert into 323 * the @a l_name list 324 * @param l_name the same name for the list field in the owner and 325 * the inter-links field in the list element 326 */ 327 #define mhd_DLINKEDL_INS_FIRST(p_own, p_obj, l_name) \ 328 mhd_DLINKEDL_INS_FIRST_D (&((p_own)->l_name),(p_obj),l_name) 329 330 /** 331 * Insert new list element into the last position in the list 332 * @warning arguments are evaluated multiple times 333 * @param p_own the pointer to the owner object with the @a l_name list 334 * @param p_obj the pointer to the new list element to insert into 335 * the @a l_name list 336 * @param l_name the same name for the list field in the owner and 337 * the inter-links field in the list element 338 */ 339 #define mhd_DLINKEDL_INS_LAST(p_own, p_obj, l_name) \ 340 mhd_DLINKEDL_INS_LAST_D (&((p_own)->l_name),(p_obj),l_name) 341 342 /** 343 * Remove list element from the list 344 * @warning arguments are evaluated multiple times 345 * @param p_own the pointer to the owner object with the @a l_name list 346 * @param p_obj the pointer to the existing @a l_name list element 347 * to remove from the list 348 * @param l_name the same name for the list field in the owner and 349 * the inter-links field in the list element 350 */ 351 #define mhd_DLINKEDL_DEL(p_own, p_obj, l_name) \ 352 mhd_DLINKEDL_DEL_D (&((p_own)->l_name),(p_obj),l_name) 353 354 /* List iterations */ 355 356 /** 357 * Get the first element in the list 358 * @param p_own the pointer to the owner object with the @a list_name list 359 * @param list_name the name of the list 360 */ 361 #define mhd_DLINKEDL_GET_FIRST(p_own, list_name) \ 362 mhd_DLINKEDL_GET_FIRST_D (&((p_own)->list_name)) 363 364 /** 365 * Get the last element in the list 366 * @param p_own the pointer to the owner object with the @a list_name list 367 * @param list_name the name of the list 368 */ 369 #define mhd_DLINKEDL_GET_LAST(p_own, list_name) \ 370 mhd_DLINKEDL_GET_LAST_D (&((p_own)->list_name)) 371 372 /** 373 * Get the next element in the list 374 * @param p_obj the pointer to the existing @a links_name list element 375 * @param links_name the name of the inter-links field in the @a p_obj 376 */ 377 #define mhd_DLINKEDL_GET_NEXT(p_obj, links_name) ((p_obj)->links_name.next) 378 379 /** 380 * Get the previous element in the list 381 * @param p_obj the pointer to the existing @a links_name list element 382 * @param links_name the name of the inter-links field in the @a p_obj 383 */ 384 #define mhd_DLINKEDL_GET_PREV(p_obj, links_name) ((p_obj)->links_name.prev) 385 386 387 #endif /* ! MHD_DLINKED_LIST_H */