mhd_dlinked_list.h (16842B)
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 /* Holds the inter-links in the list element */ \ 118 mhd_DLNKDL_LINKS_TYPE (l_type) { \ 119 struct l_type *prev; /* The pointer to the previous element in the list */ \ 120 struct l_type *next; /* The pointer to the next element in the list */ \ 121 } 122 123 /** 124 * Template for declaration of the list helper structs 125 * @param l_type the struct tag name of elements that the list holds 126 */ 127 #define mhd_DLINKEDL_STRUCTS_DEFS(l_type) \ 128 mhd_DLINKEDL_LIST_DEF (l_type); mhd_DLINKEDL_LINKS_DEF (l_type) 129 130 131 /* Declarations of the types for the list owners and the list elements */ 132 133 /** 134 * Declare the list field in the owner struct 135 */ 136 #define mhd_DLNKDL_LIST(l_type,list_name) \ 137 mhd_DLNKDL_LIST_TYPE (l_type) list_name 138 139 /** 140 * Declare the inter-links field in the list element 141 */ 142 #define mhd_DLNKDL_LINKS(l_type,links_name) \ 143 mhd_DLNKDL_LINKS_TYPE (l_type) links_name 144 145 /* Direct work with the list */ 146 /* These macros directly use the pointer to the list and allow using 147 * names of the list field (within the owner object) different from the 148 * names of the inter-links field (in the list elements). */ 149 150 /** 151 * Initialise the doubly linked list pointers in the list owner using 152 * the direct pointer to the list 153 * @warning arguments are evaluated multiple times 154 * @param p_list the pointer to the list 155 */ 156 #define mhd_DLINKEDL_INIT_LIST_D(p_list) \ 157 do {(p_list)->first = NULL; (p_list)->last = NULL;} while (0) 158 159 /** 160 * Insert new list element into the first position in the list using direct 161 * pointer to the list 162 * @warning arguments are evaluated multiple times 163 * @param p_list the pointer to the list 164 * @param p_obj the pointer to the new element to insert into the list, 165 * using @a links_name inter-links 166 * @param links_name the name of the inter-links field in the @a p_obj 167 */ 168 #define mhd_DLINKEDL_INS_FIRST_D(p_list,p_obj,links_name) do { \ 169 mhd_ASSUME (NULL == (p_obj)->links_name.prev); \ 170 mhd_ASSUME (NULL == (p_obj)->links_name.next); \ 171 mhd_ASSUME ((p_obj) != (p_list)->first); \ 172 mhd_ASSUME ((p_obj) != (p_list)->last); \ 173 if (NULL != (p_list)->first) \ 174 { mhd_ASSUME (NULL == (p_list)->first->links_name.prev); \ 175 mhd_ASSUME (NULL == (p_list)->last->links_name.next); \ 176 mhd_ASSUME ((p_obj) != (p_list)->first->links_name.next); \ 177 mhd_ASSUME (NULL != (p_list)->last); \ 178 ((p_obj)->links_name.next = (p_list)->first) \ 179 ->links_name.prev = (p_obj); } else \ 180 { mhd_ASSUME (NULL == (p_list)->last); \ 181 (p_list)->last = (p_obj); } \ 182 (p_list)->first = (p_obj); } while (0) 183 184 /** 185 * Insert new list element into the last position in the list using direct 186 * pointer to the list 187 * @warning arguments are evaluated multiple times 188 * @param p_list the pointer to the list 189 * @param p_obj the pointer to the new element to insert into the list, 190 * using @a links_name inter-links 191 * @param links_name the name of the inter-links field in the @a p_obj 192 */ 193 #define mhd_DLINKEDL_INS_LAST_D(p_list,p_obj,links_name) do { \ 194 mhd_ASSUME (NULL == (p_obj)->links_name.prev); \ 195 mhd_ASSUME (NULL == (p_obj)->links_name.next); \ 196 mhd_ASSUME ((p_obj) != (p_list)->first); \ 197 mhd_ASSUME ((p_obj) != (p_list)->last); \ 198 if (NULL != (p_list)->last) \ 199 { mhd_ASSUME (NULL == (p_list)->last->links_name.next); \ 200 mhd_ASSUME (NULL == (p_list)->first->links_name.prev); \ 201 mhd_ASSUME ((p_obj) != (p_list)->last->links_name.prev); \ 202 mhd_ASSUME (NULL != (p_list)->first); \ 203 ((p_obj)->links_name.prev = (p_list)->last) \ 204 ->links_name.next = (p_obj); } else \ 205 { mhd_ASSUME (NULL == (p_list)->first); \ 206 (p_list)->first = (p_obj); } \ 207 (p_list)->last = (p_obj); } while (0) 208 209 /** 210 * Remove list element from the list using direct pointer to the list 211 * @warning arguments are evaluated multiple times 212 * @param p_list the pointer to the list 213 * @param p_obj the pointer to the existing list element to remove from the list 214 * @param links_name the name of the inter-links field in the @a p_obj 215 */ 216 #define mhd_DLINKEDL_DEL_D(p_list,p_obj,links_name) do { \ 217 mhd_ASSUME (NULL != (p_list)->first); \ 218 mhd_ASSUME (NULL != (p_list)->last); \ 219 mhd_ASSUME (NULL == (p_list)->first->links_name.prev); \ 220 mhd_ASSUME (NULL == (p_list)->last->links_name.next); \ 221 mhd_ASSUME ((p_obj) != (p_obj)->links_name.prev); \ 222 mhd_ASSUME ((p_list)->last != (p_obj)->links_name.prev); \ 223 mhd_ASSUME ((p_obj) != (p_obj)->links_name.next); \ 224 mhd_ASSUME ((p_list)->first != (p_obj)->links_name.next); \ 225 if (NULL != (p_obj)->links_name.next) \ 226 { mhd_ASSUME ((p_obj) == (p_obj)->links_name.next->links_name.prev); \ 227 mhd_ASSUME ((p_obj) != (p_list)->last); \ 228 mhd_ASSUME ((p_obj)->links_name.next != \ 229 (p_obj)->links_name.prev); \ 230 (p_obj)->links_name.next->links_name.prev = \ 231 (p_obj)->links_name.prev; } else \ 232 { mhd_ASSUME ((p_obj) == (p_list)->last); \ 233 (p_list)->last = (p_obj)->links_name.prev; } \ 234 if (NULL != (p_obj)->links_name.prev) \ 235 { mhd_ASSUME ((p_obj) == (p_obj)->links_name.prev->links_name.next); \ 236 mhd_ASSUME ((p_obj) != (p_list)->first); \ 237 mhd_ASSUME ((p_obj)->links_name.next != \ 238 (p_obj)->links_name.prev); \ 239 (p_obj)->links_name.prev->links_name.next = \ 240 (p_obj)->links_name.next; } else \ 241 { mhd_ASSUME ((p_obj) == (p_list)->first); \ 242 (p_list)->first = (p_obj)->links_name.next; } \ 243 (p_obj)->links_name.prev = NULL; \ 244 (p_obj)->links_name.next = NULL; } while (0) 245 246 /** 247 * Get the first element in the list using direct pointer to the list 248 */ 249 #define mhd_DLINKEDL_GET_FIRST_D(p_list) ((p_list)->first) 250 251 /** 252 * Get the last element in the list using direct pointer to the list 253 */ 254 #define mhd_DLINKEDL_GET_LAST_D(p_list) ((p_list)->last) 255 256 /** 257 * Move the list element within the list to the first position using a direct 258 * pointer to the list 259 * @warning arguments are evaluated multiple times 260 * @param p_list the pointer to the list 261 * @param p_obj the pointer to the existing list element to move to the 262 * first position 263 * @param links_name the name of the inter-links field in the @a p_obj 264 */ 265 #define mhd_DLINKEDL_MOVE_TO_FIRST_D(p_list,p_obj,links_name) do { \ 266 mhd_ASSUME (NULL != (p_list)->first); \ 267 mhd_ASSUME (NULL != (p_list)->last); \ 268 mhd_ASSUME ((p_obj) != (p_obj)->links_name.next); \ 269 mhd_ASSUME ((p_obj) != (p_obj)->links_name.prev); \ 270 if (NULL == (p_obj)->links_name.prev) \ 271 { mhd_ASSUME ((p_obj) == (p_list)->first); } else \ 272 { mhd_ASSUME ((p_obj) != (p_list)->first); \ 273 mhd_ASSUME ((p_obj) == \ 274 (p_obj)->links_name.prev->links_name.next); \ 275 (p_obj)->links_name.prev->links_name.next = \ 276 (p_obj)->links_name.next; \ 277 if (NULL == (p_obj)->links_name.next) \ 278 { mhd_ASSUME ((p_obj) == (p_list)->last); \ 279 (p_list)->last = (p_obj)->links_name.prev; } else \ 280 { mhd_ASSUME ((p_obj) != (p_list)->last); \ 281 mhd_ASSUME ((p_obj) == \ 282 (p_obj)->links_name.next->links_name.prev); \ 283 (p_obj)->links_name.next->links_name.prev = \ 284 (p_obj)->links_name.prev; } \ 285 (p_obj)->links_name.next = (p_list)->first; \ 286 (p_obj)->links_name.prev = NULL; \ 287 (p_list)->first->links_name.prev = (p_obj); \ 288 (p_list)->first = (p_obj); } } while (0) 289 290 291 /* ** The main interface ** */ 292 /* These macros use identical names for the list field (within the owner 293 * object) and the inter-links field (within the list elements). */ 294 295 /* Initialisers */ 296 297 /** 298 * Initialise the doubly linked list pointers in the owner object 299 * @warning arguments are evaluated multiple times 300 * @param p_own the pointer to the owner object with the @a list_name list 301 * @param list_name the name of the list 302 */ 303 #define mhd_DLINKEDL_INIT_LIST(p_own,list_name) \ 304 mhd_DLINKEDL_INIT_LIST_D (&((p_own)->list_name)) 305 306 /** 307 * Initialise the doubly linked list pointers in the list element 308 * @warning arguments are evaluated multiple times 309 * @param p_obj the pointer to the future element of 310 * the @a links_name list 311 * @param links_name the name of the inter-links field in the @a p_obj 312 */ 313 #define mhd_DLINKEDL_INIT_LINKS(p_obj,links_name) \ 314 do {(p_obj)->links_name.prev = NULL; \ 315 (p_obj)->links_name.next = NULL;} while (0) 316 317 /* List manipulations */ 318 319 /** 320 * Insert new list element into the first position in the list 321 * @warning arguments are evaluated multiple times 322 * @param p_own the pointer to the owner object with the @a l_name list 323 * @param p_obj the pointer to the new list element to insert into 324 * the @a l_name list 325 * @param l_name the same name for the list field in the owner and 326 * the inter-links field in the list element 327 */ 328 #define mhd_DLINKEDL_INS_FIRST(p_own,p_obj,l_name) \ 329 mhd_DLINKEDL_INS_FIRST_D (&((p_own)->l_name),(p_obj),l_name) 330 331 /** 332 * Insert new list element into the last position in the list 333 * @warning arguments are evaluated multiple times 334 * @param p_own the pointer to the owner object with the @a l_name list 335 * @param p_obj the pointer to the new list element to insert into 336 * the @a l_name list 337 * @param l_name the same name for the list field in the owner and 338 * the inter-links field in the list element 339 */ 340 #define mhd_DLINKEDL_INS_LAST(p_own,p_obj,l_name) \ 341 mhd_DLINKEDL_INS_LAST_D (&((p_own)->l_name),(p_obj),l_name) 342 343 /** 344 * Remove list element from the list 345 * @warning arguments are evaluated multiple times 346 * @param p_own the pointer to the owner object with the @a l_name list 347 * @param p_obj the pointer to the existing @a l_name list element 348 * to remove from the list 349 * @param l_name the same name for the list field in the owner and 350 * the inter-links field in the list element 351 */ 352 #define mhd_DLINKEDL_DEL(p_own,p_obj,l_name) \ 353 mhd_DLINKEDL_DEL_D (&((p_own)->l_name),(p_obj),l_name) 354 355 /* List iterations */ 356 357 /** 358 * Get the first element in the list 359 * @param p_own the pointer to the owner object with the @a list_name list 360 * @param list_name the name of the list 361 */ 362 #define mhd_DLINKEDL_GET_FIRST(p_own,list_name) \ 363 mhd_DLINKEDL_GET_FIRST_D (&((p_own)->list_name)) 364 365 /** 366 * Get the last element in the list 367 * @param p_own the pointer to the owner object with the @a list_name list 368 * @param list_name the name of the list 369 */ 370 #define mhd_DLINKEDL_GET_LAST(p_own,list_name) \ 371 mhd_DLINKEDL_GET_LAST_D (&((p_own)->list_name)) 372 373 /** 374 * Get the next element in the list 375 * @param p_obj the pointer to the existing @a links_name list element 376 * @param links_name the name of the inter-links field in the @a p_obj 377 */ 378 #define mhd_DLINKEDL_GET_NEXT(p_obj,links_name) ((p_obj)->links_name.next) 379 380 /** 381 * Get the previous element in the list 382 * @param p_obj the pointer to the existing @a links_name list element 383 * @param links_name the name of the inter-links field in the @a p_obj 384 */ 385 #define mhd_DLINKEDL_GET_PREV(p_obj,links_name) ((p_obj)->links_name.prev) 386 387 388 #endif /* ! MHD_DLINKED_LIST_H */