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