mhd_dlinked_list.h (16213B)
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-2025 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-object pointers (named here @a links_name), while 46 * the list is held by the owner within the helper (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_assert.h" 56 #include "mhd_assume.h" 57 58 59 /* This header defines macros for handling doubly-linked lists of objects. 60 The pointers to the first and the last objects in the list are held in 61 the "owner". 62 The list member object links to each other via "next" and "prev" links. 63 Each member object can be part of several lists. For example, connections are 64 maintained in "all connections" and "need to process" lists simultaneously. 65 List member can be removed from the list or inserted to the list at any 66 moment. 67 Typically the name of the list (inside the "owner" object) is the same as 68 the name of inter-links. However, it is possible to use different names. 69 For example, connections can be removed from "all connections" list and 70 moved the "clean up" list using the same internal links "all connections". 71 As this is a doubly-linked list, it can be walked rom the beginning to the 72 end and in the opposite direction. 73 The list is designed to work with struct tags as a contained and container 74 objects. 75 */ 76 77 /* Helpers */ 78 79 #define mhd_DLNKDL_LIST_TYPE_(base_name) struct base_name ## _list 80 81 #define mhd_DLNKDL_LINKS_TYPE_(base_name) struct base_name ## _links 82 83 84 /* Names */ 85 86 /** 87 * The name of struct that holds the list in the owner object 88 */ 89 #define mhd_DLNKDL_LIST_TYPE(base_name) mhd_DLNKDL_LIST_TYPE_ (base_name) 90 91 /** 92 * The name of the struct that holds the links between list members 93 */ 94 #define mhd_DLNKDL_LINKS_TYPE(base_name) mhd_DLNKDL_LINKS_TYPE_ (base_name) 95 96 /* Definitions of the structures */ 97 98 /** 99 * Template for declaration of the list helper struct 100 * @param l_type the struct tag name of objects that list links 101 */ 102 #define mhd_DLINKEDL_LIST_DEF(l_type) \ 103 mhd_DLNKDL_LIST_TYPE (l_type) { /* Holds the list in the owner */ \ 104 struct l_type *first; /* The pointer to the first object in the list */ \ 105 struct l_type *last; /* The pointer to the last object in the list */ \ 106 } 107 108 /** 109 * Template for declaration of links helper struct 110 * @param l_type the struct tag name of objects that list links 111 */ 112 #define mhd_DLINKEDL_LINKS_DEF(l_type) \ 113 mhd_DLNKDL_LINKS_TYPE (l_type) { /* Holds the links in the members */ \ 114 struct l_type *prev; /* The pointer to the previous object in the list */ \ 115 struct l_type *next; /* The pointer to the next object in the list */ \ 116 } 117 118 119 /** 120 * Template for declaration of list helper structs 121 * @param l_type the struct tag name of objects that the list holds 122 */ 123 #define mhd_DLINKEDL_STRUCTS_DEFS(l_type) \ 124 mhd_DLINKEDL_LIST_DEF (l_type); mhd_DLINKEDL_LINKS_DEF (l_type) 125 126 /* Declarations for the list owners and the list members */ 127 128 /** 129 * Declare the owner's list member 130 */ 131 #define mhd_DLNKDL_LIST(l_type,list_name) \ 132 mhd_DLNKDL_LIST_TYPE (l_type) list_name 133 134 /** 135 * Declare the list object links member 136 */ 137 #define mhd_DLNKDL_LINKS(l_type,links_name) \ 138 mhd_DLNKDL_LINKS_TYPE (l_type) links_name 139 140 /* Direct work with the list */ 141 /* These macros directly use the pointer to the list and allow using 142 * names of the list object (within the owner object) different from the names 143 * of link object (in the list members). */ 144 145 /** 146 * Initialise the doubly linked list pointers in the list object using 147 * the direct pointer to the list 148 * @warning arguments are evaluated multiple times 149 * @param p_list the pointer to the list 150 */ 151 #define mhd_DLINKEDL_INIT_LIST_D(p_list) \ 152 do {(p_list)->first = NULL; (p_list)->last = NULL;} while (0) 153 154 /** 155 * Insert object into the first position in the list using direct pointer 156 * to the list 157 * @warning arguments are evaluated multiple times 158 * @param p_list the pointer to the list 159 * @param p_obj the pointer to the new list member object to insert to 160 * the @a links_name list 161 * @param links_name the name of the links member in the @a p_obj 162 */ 163 #define mhd_DLINKEDL_INS_FIRST_D(p_list,p_obj,links_name) do { \ 164 mhd_assert (NULL == (p_obj)->links_name.prev); \ 165 mhd_assert (NULL == (p_obj)->links_name.next); \ 166 mhd_assert ((p_obj) != (p_list)->first); \ 167 mhd_assert ((p_obj) != (p_list)->last); \ 168 if (NULL != (p_list)->first) \ 169 { mhd_assert (NULL == (p_list)->first->links_name.prev); \ 170 mhd_assert (NULL == (p_list)->last->links_name.next); \ 171 mhd_assert ((p_obj) != (p_list)->first->links_name.next); \ 172 mhd_assert (NULL != (p_list)->last); \ 173 ((p_obj)->links_name.next = (p_list)->first) \ 174 ->links_name.prev = (p_obj); } else \ 175 { mhd_assert (NULL == (p_list)->last); \ 176 (p_list)->last = (p_obj); } \ 177 (p_list)->first = (p_obj); } while (0) 178 179 /** 180 * Insert object into the last position in the list using direct pointer 181 * to the list 182 * @warning arguments are evaluated multiple times 183 * @param p_list the pointer to the list 184 * @param p_obj the pointer to the new list member object to insert to 185 * the @a links_name list 186 * @param links_name the name of the links member in the @a p_obj 187 */ 188 #define mhd_DLINKEDL_INS_LAST_D(p_list,p_obj,links_name) do { \ 189 mhd_assert (NULL == (p_obj)->links_name.prev); \ 190 mhd_assert (NULL == (p_obj)->links_name.next); \ 191 mhd_assert ((p_obj) != (p_list)->first); \ 192 mhd_assert ((p_obj) != (p_list)->last); \ 193 if (NULL != (p_list)->last) \ 194 { mhd_assert (NULL == (p_list)->last->links_name.next); \ 195 mhd_assert (NULL == (p_list)->first->links_name.prev); \ 196 mhd_assert ((p_obj) != (p_list)->last->links_name.prev); \ 197 mhd_assert (NULL != (p_list)->first); \ 198 ((p_obj)->links_name.prev = (p_list)->last) \ 199 ->links_name.next = (p_obj); } else \ 200 { mhd_assert (NULL == (p_list)->first); \ 201 (p_list)->first = (p_obj); } \ 202 (p_list)->last = (p_obj); } while (0) 203 204 /** 205 * Remove object from the list using direct pointer to the list 206 * @warning arguments are evaluated multiple times 207 * @param p_list the pointer to the list 208 * @param p_obj the pointer to the existing list member object 209 * to remove from the list 210 * @param links_name the name of the links member in the @a p_obj 211 */ 212 #define mhd_DLINKEDL_DEL_D(p_list,p_obj,links_name) do { \ 213 mhd_assert (NULL != (p_list)->first); \ 214 mhd_assert (NULL != (p_list)->last); \ 215 mhd_assert (NULL == (p_list)->first->links_name.prev); \ 216 mhd_assert (NULL == (p_list)->last->links_name.next); \ 217 mhd_assert ((p_obj) != (p_obj)->links_name.prev); \ 218 mhd_assert ((p_list)->last != (p_obj)->links_name.prev); \ 219 mhd_assert ((p_obj) != (p_obj)->links_name.next); \ 220 mhd_assert ((p_list)->first != (p_obj)->links_name.next); \ 221 if (NULL != (p_obj)->links_name.next) \ 222 { mhd_assert ((p_obj) == (p_obj)->links_name.next->links_name.prev); \ 223 mhd_assert ((p_obj) != (p_list)->last); \ 224 (p_obj)->links_name.next->links_name.prev = \ 225 (p_obj)->links_name.prev; } else \ 226 { mhd_assert ((p_obj) == (p_list)->last); \ 227 (p_list)->last = (p_obj)->links_name.prev; } \ 228 if (NULL != (p_obj)->links_name.prev) \ 229 { mhd_assert ((p_obj) == (p_obj)->links_name.prev->links_name.next); \ 230 mhd_assert ((p_obj) != (p_list)->first); \ 231 (p_obj)->links_name.prev->links_name.next = \ 232 (p_obj)->links_name.next; } else \ 233 { mhd_assert ((p_obj) == (p_list)->first); \ 234 (p_list)->first = (p_obj)->links_name.next; } \ 235 (p_obj)->links_name.prev = NULL; \ 236 (p_obj)->links_name.next = NULL; } while (0) 237 238 /** 239 * Get the first object in the list using direct pointer to the list 240 */ 241 #define mhd_DLINKEDL_GET_FIRST_D(p_list) ((p_list)->first) 242 243 /** 244 * Get the last object in the list using direct pointer to the list 245 */ 246 #define mhd_DLINKEDL_GET_LAST_D(p_list) ((p_list)->last) 247 248 /** 249 * Move the object within the list to the first position using a direct pointer 250 * to the list 251 * @warning arguments are evaluated multiple times 252 * @param p_list the pointer to the list 253 * @param p_obj the pointer to the existing list member object to move to the 254 * first position 255 * @param links_name the name of the links member in the @a p_obj 256 */ 257 #define mhd_DLINKEDL_MOVE_TO_FIRST_D(p_list,p_obj,links_name) do { \ 258 mhd_ASSUME (NULL != (p_list)->first); \ 259 mhd_ASSUME (NULL != (p_list)->last); \ 260 mhd_ASSUME ((p_obj) != (p_obj)->links_name.next); \ 261 mhd_ASSUME ((p_obj) != (p_obj)->links_name.prev); \ 262 if (NULL == (p_obj)->links_name.prev) \ 263 { mhd_ASSUME ((p_obj) == (p_list)->first); } else \ 264 { mhd_ASSUME ((p_obj) != (p_list)->first); \ 265 mhd_ASSUME ((p_obj) == \ 266 (p_obj)->links_name.prev->links_name.next); \ 267 (p_obj)->links_name.prev->links_name.next = \ 268 (p_obj)->links_name.next; \ 269 if (NULL == (p_obj)->links_name.next) \ 270 { mhd_ASSUME ((p_obj) == (p_list)->last); \ 271 (p_list)->last = (p_obj)->links_name.prev; } else \ 272 { mhd_ASSUME ((p_obj) != (p_list)->last); \ 273 mhd_ASSUME ((p_obj) == \ 274 (p_obj)->links_name.next->links_name.prev); \ 275 (p_obj)->links_name.next->links_name.prev = \ 276 (p_obj)->links_name.prev; } \ 277 (p_obj)->links_name.next = (p_list)->first; \ 278 (p_obj)->links_name.prev = NULL; \ 279 (p_list)->first->links_name.prev = (p_obj); \ 280 (p_list)->first = (p_obj); } } while (0) 281 282 283 /* ** The main interface ** */ 284 /* These macros use identical names for the list object itself (within the 285 * owner object) and the links object (within the list members). */ 286 287 /* Initialisers */ 288 289 /** 290 * Initialise the doubly linked list pointers in the owner object 291 * @warning arguments are evaluated multiple times 292 * @param p_own the pointer to the owner object with the @a list_name list 293 * @param list_name the name of the list 294 */ 295 #define mhd_DLINKEDL_INIT_LIST(p_own,list_name) \ 296 mhd_DLINKEDL_INIT_LIST_D (&((p_own)->list_name)) 297 298 /** 299 * Initialise the doubly linked list pointers in the list member object 300 * @warning arguments are evaluated multiple times 301 * @param p_obj the pointer to the future member object of 302 * the @a links_name list 303 * @param links_name the name of the links member in the @a p_obj 304 */ 305 #define mhd_DLINKEDL_INIT_LINKS(p_obj,links_name) \ 306 do {(p_obj)->links_name.prev = NULL; \ 307 (p_obj)->links_name.next = NULL;} while (0) 308 309 /* List manipulations */ 310 311 /** 312 * Insert object into the first position in the list 313 * @warning arguments are evaluated multiple times 314 * @param p_own the pointer to the owner object with the @a l_name list 315 * @param p_obj the pointer to the new list member object to insert to 316 * the @a l_name list 317 * @param l_name the same name for the list and the links 318 */ 319 #define mhd_DLINKEDL_INS_FIRST(p_own,p_obj,l_name) \ 320 mhd_DLINKEDL_INS_FIRST_D (&((p_own)->l_name),(p_obj),l_name) 321 322 /** 323 * Insert object into the last position in the list 324 * @warning arguments are evaluated multiple times 325 * @param p_own the pointer to the owner object with the @a l_name list 326 * @param p_obj the pointer to the new list member object to insert to 327 * the @a l_name list 328 * @param l_name the same name for the list and the links 329 */ 330 #define mhd_DLINKEDL_INS_LAST(p_own,p_obj,l_name) \ 331 mhd_DLINKEDL_INS_LAST_D (&((p_own)->l_name),(p_obj),l_name) 332 333 /** 334 * Remove object from the list 335 * @warning arguments are evaluated multiple times 336 * @param p_own the pointer to the owner object with the @a l_name list 337 * @param p_obj the pointer to the existing @a l_name list member object 338 * to remove from the list 339 * @param l_name the same name for the list and the links 340 */ 341 #define mhd_DLINKEDL_DEL(p_own,p_obj,l_name) \ 342 mhd_DLINKEDL_DEL_D (&((p_own)->l_name),(p_obj),l_name) 343 344 /* List iterations */ 345 346 /** 347 * Get the first object in the list 348 * @warning arguments are evaluated multiple times 349 * @param p_own the pointer to the owner object with the @a list_name list 350 * @param list_name the name of the list 351 */ 352 #define mhd_DLINKEDL_GET_FIRST(p_own,list_name) \ 353 mhd_DLINKEDL_GET_FIRST_D (&((p_own)->list_name)) 354 355 /** 356 * Get the last object in the list 357 * @warning arguments are evaluated multiple times 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_LAST(p_own,list_name) \ 362 mhd_DLINKEDL_GET_LAST_D (&((p_own)->list_name)) 363 364 /** 365 * Get the next object in the list 366 * @warning arguments are evaluated multiple times 367 * @param p_obj the pointer to the existing @a links_name list member object 368 * @param links_name the name of the links member in the @a p_obj 369 */ 370 #define mhd_DLINKEDL_GET_NEXT(p_obj,links_name) ((p_obj)->links_name.next) 371 372 /** 373 * Get the previous object in the list 374 * @warning arguments are evaluated multiple times 375 * @param p_obj the pointer to the existing @a links_name list member object 376 * @param links_name the name of the links member in the @a p_obj 377 */ 378 #define mhd_DLINKEDL_GET_PREV(p_obj,links_name) ((p_obj)->links_name.prev) 379 380 381 #endif /* ! MHD_DLINKED_LIST_H */