1 /* Jitter: doubly linked list as CPP macros: header. 2 3 Copyright (C) 2018, 2020 Luca Saiu 4 Written by Luca Saiu 5 6 This file is part of Jitter. 7 8 Jitter is free software: you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation, either version 3 of the License, or 11 (at your option) any later version. 12 13 Jitter is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with Jitter. If not, see <http://www.gnu.org/licenses/>. */ 20 21 22 #ifndef JITTER_LIST_H_ 23 #define JITTER_LIST_H_ 24 25 #include <jitter/jitter.h> 26 27 28 29 30 /* Doubly linked lists as CPP macros. 31 * ************************************************************************** */ 32 33 /* This is an efficient implementation of a bidirectional linked list data 34 structure using CPP macros. 35 36 Linked lists by themselves are not complex, but it's easy to get some detail 37 wrong in linking and unlinking operations. They deserve to be abstracted 38 without compromising on efficiency or generality. 39 40 The idea is that the same linking and unlinking macros, independent from 41 allocation, can be reused for multiple more complex data structures, 42 including some fundamental ones more primitive than heap allocation. 43 44 One use case for this in Jitter is heap allocation and deallocation on 45 mmapped executable memory; in the same way, each block of mmapped memory can 46 be linked with a predecessor and a successor in a doubly linked list, using 47 the memory from the blocks itself for the data structure, without relying on 48 malloc. 49 if in the future I needed to link hash tables elements to one another to make 50 hash iteration faster, I would reuse this. At some point I would like to run 51 Jittery VMs, and epsilon, in kernel mode. The same heap implementation used 52 for mmapped executable memory would work as a malloc replacement as well. */ 53 54 /* General assumptions: 55 - Linked lists are not circular or cyclic in any other way; 56 - each item (as per pointer equality) is allowed to be contained in each 57 list at most once; 58 - each item is allowed to be included in multiple independent linked lists, 59 by containing multiple fields of type struct jitter_list_links; 60 - each item being linked to a list by one of the macros here is not allowed 61 to be already contained in the same list; 62 - each item being removed from a list by one of the macros here must be 63 contained in the list before the macro expansion is executed; 64 - an item being unlinked from a list may be left with invalid "previous" 65 and "next" pointers after the macro expansion is executed, or with 66 pointers which would conflict with the order established by the items 67 remaining in the list; 68 - each item being linked or unlinked from a list, passed via pointer, 69 is never NULL; 70 - memory allocation is *not* handled here: unlinking an item does not 71 automatically release its memory. */ 72 73 74 /* A struct defining doubly linked list pointers within a list elementx. This 75 struct should be always be contained within another struct called the "item" 76 struct, as a named field. 77 Link structures ("previous", "next", "first", "last") point to items, and 78 not directly to each other. However, given a pointer to an item, the 79 corresponding pointer to its link element can be obtained by adding a 80 constant offset known at compile time. */ 81 struct jitter_list_links 82 { 83 /* A pointer to the next item, or NULL for the first object in the list. */ 84 void *previous; 85 86 /* A pointer to the next item, or NULL for the last object in the list. */ 87 void *next; 88 }; 89 90 /* A struct implementing a doubly linked list header. */ 91 struct jitter_list_header 92 { 93 /* A pointer to the first list item, or NULL if the list is empty. Equal to 94 last and non-NULL only when the list has exactly one element. */ 95 void *first; 96 97 /* A pointer to the last list item, or NULL if the list is empty. Equal to 98 first and non-NULL only when the list has exactly one element. */ 99 void *last; 100 }; 101 102 /* The following macros all expand to C statements which evaluate their 103 expression arguments at most once. */ // FIXME: exactly once? 104 // FIXME: comment about struct and field names as macro arguments. 105 // The list is assumed never to contain duplicate (by address) elements, either 106 // before macros calls or because of their effect. 107 108 /* Macros whose names end in _NONEMPTY assume that a list is "always-nonempty". 109 A list being "always-nonempty" in this context means that: 110 - the list is never empty either before or after the macro calls, and that 111 - the first and last items in the list are special elements, not 112 changed by the macros. 113 In practice every "always-nonempty" list has always at least two elements 114 the first and the last, which can't change. 115 The "always-nonempty" assumption allows for much more efficient list 116 updates using straight-line code, without any conditionals. 117 118 Macros whose name end in _POSSIBLY_AWNE macros are for internal use only. 119 Their first argument is always a constant boolean expression, and their 120 second argument may be evaluated multiple times. */ 121 122 /* Expand to a sequence of local variable declarations for links and headers, to 123 be used in other macros here. The expansion is meant as part of a larger 124 block, and not protected with do..while (false). */ 125 #define _JITTER_LIST_LOCALS_(item_struct_name, item_field_name, header_p, \ 126 item_p) \ 127 struct item_struct_name * const _item __attribute__ ((unused)) \ 128 = (item_p); \ 129 struct item_struct_name * const _old_previous __attribute__ ((unused)) \ 130 = _item->item_field_name.previous; \ 131 struct item_struct_name * const _old_next __attribute__ ((unused)) \ 132 = _item->item_field_name.next; \ 133 struct jitter_list_header * const _header __attribute__ ((unused)) \ 134 = (header_p); \ 135 struct item_struct_name * const _old_first __attribute__ ((unused)) \ 136 = _header->first; \ 137 struct item_struct_name * const _old_last __attribute__ ((unused)) \ 138 = _header->last; 139 140 #define JITTER_LIST_INITIALIZE_HEADER(header_p) \ 141 do \ 142 { \ 143 struct jitter_list_header * const _header = (header_p); \ 144 _header->first = NULL; \ 145 _header->last = NULL; \ 146 } \ 147 while (false) 148 149 // Assume that the pointed item does not belong to the list already. 150 #define JITTER_LIST_LINK_FIRST(item_struct_name, item_field_name, header_p, \ 151 item_p) \ 152 do \ 153 { \ 154 _JITTER_LIST_LOCALS_ (item_struct_name, item_field_name, header_p, \ 155 item_p); \ 156 _item->item_field_name.previous = NULL; \ 157 _item->item_field_name.next = _old_first; \ 158 if (_old_first != NULL) \ 159 _old_first->item_field_name.previous = _item; \ 160 if (_old_last == NULL) \ 161 _header->last = _item; \ 162 _header->first = _item; \ 163 } \ 164 while (false) 165 166 // Assume that the pointed item does not belong to the list already. 167 #define JITTER_LIST_LINK_LAST(item_struct_name, item_field_name, header_p, \ 168 item_p) \ 169 do \ 170 { \ 171 _JITTER_LIST_LOCALS_ (item_struct_name, item_field_name, header_p, \ 172 item_p); \ 173 _item->item_field_name.previous = _old_last; \ 174 _item->item_field_name.next = NULL; \ 175 if (_old_last != NULL) \ 176 _old_last->item_field_name.next = _item; \ 177 if (_old_first == NULL) \ 178 _header->first = _item; \ 179 _header->last = _item; \ 180 } \ 181 while (false) 182 183 // Assume that the pointed item does belong to the list. 184 #define JITTER_LIST_UNLINK_POSSIBLY_AWNE(always_nonempty, item_struct_name, \ 185 item_field_name, header_p, item_p) \ 186 do \ 187 { \ 188 _JITTER_LIST_LOCALS_ (item_struct_name, item_field_name, header_p, \ 189 item_p); \ 190 if ((always_nonempty) || _old_previous != NULL) \ 191 _old_previous->item_field_name.next = _old_next; \ 192 if ((always_nonempty) || _old_next != NULL) \ 193 _old_next->item_field_name.previous = _old_previous; \ 194 if (! (always_nonempty) && _old_first == _item) \ 195 _header->first = _old_next; \ 196 if (! (always_nonempty) && _old_last == _item) \ 197 _header->last = _old_previous; \ 198 } \ 199 while (false) 200 201 #define JITTER_LIST_UNLINK(item_struct_name, item_field_name, header_p, item_p) \ 202 JITTER_LIST_UNLINK_POSSIBLY_AWNE(false, item_struct_name, \ 203 item_field_name, header_p, item_p) 204 205 /* Same as JITTER_LIST_UNLINK, but assume that the list is always-nonempty. A 206 useful property of JITTER_LIST_UNLINK_NONEMPTY not satisfied by 207 JITTER_LIST_UNLINK is that it is possible to unlink a *copy* of an element 208 which belongs to the list: item_p is allowed not to belong to the list, as 209 long as a copy of it does; in this case the expansion unlinks its copy. 210 JITTER_LIST_UNLINK does not allow to do this when the element to be unlinked 211 is a copy of the first or the last of the list, which would not compare as 212 equal to item_p . */ 213 #define JITTER_LIST_UNLINK_NONEMPTY(item_struct_name, item_field_name, \ 214 header_p, item_p) \ 215 JITTER_LIST_UNLINK_POSSIBLY_AWNE(true, item_struct_name, \ 216 item_field_name, header_p, item_p) 217 218 // Assume that the pointed item does belong to the list, and that the pointed 219 // new items does not. 220 // The old item and the new item *are* allowed to share memory. 221 #define JITTER_LIST_REPLACE_POSSIBLY_AWNE(always_nonempty, item_struct_name, \ 222 item_field_name, header_p, item_p, \ 223 new_item_p) \ 224 do \ 225 { \ 226 _JITTER_LIST_LOCALS_ (item_struct_name, item_field_name, header_p, \ 227 item_p); \ 228 struct item_struct_name * const _new_item = (new_item_p); \ 229 _new_item->item_field_name.previous = _old_previous; \ 230 _new_item->item_field_name.next = _old_next; \ 231 if ((always_nonempty) || _old_previous != NULL) \ 232 _old_previous->item_field_name.next = _new_item; \ 233 if ((always_nonempty) || _old_next != NULL) \ 234 _old_next->item_field_name.previous = _new_item; \ 235 if (! (always_nonempty) && _old_first == _item) \ 236 _header->first = _new_item; \ 237 if (! (always_nonempty) && _old_last == _item) \ 238 _header->last = _new_item; \ 239 } \ 240 while (false) 241 242 #define JITTER_LIST_REPLACE(item_struct_name, item_field_name, header_p, \ 243 item_p, new_item_p) \ 244 JITTER_LIST_REPLACE_POSSIBLY_AWNE(false, item_struct_name, \ 245 item_field_name, header_p, item_p, \ 246 new_item_p) 247 248 /* Same as JITTER_LIST_REPLACE, but assume that the list is always-nonempty. */ 249 #define JITTER_LIST_REPLACE_NONEMPTY(allow_empty, item_struct_name, \ 250 item_field_name, header_p, item_p, \ 251 new_item_p) \ 252 JITTER_LIST_REPLACE_POSSIBLY_AWNE(true, item_struct_name, \ 253 item_field_name, header_p, item_p, \ 254 new_item_p) 255 256 #define JITTER_LIST_LINK_BEFORE_POSSIBLY_AWNE(always_nonempty, \ 257 item_struct_name, \ 258 item_field_name, header_p, \ 259 item_p, new_item_p) \ 260 do \ 261 { \ 262 _JITTER_LIST_LOCALS_ (item_struct_name, item_field_name, header_p, \ 263 item_p); \ 264 struct item_struct_name * const _new_item = (new_item_p); \ 265 if ((always_nonempty) || _old_previous != NULL) \ 266 _old_previous->item_field_name.next = _new_item; \ 267 _new_item->item_field_name.previous = _old_previous; \ 268 _new_item->item_field_name.next = _item; \ 269 _item->item_field_name.previous = _new_item; \ 270 if (! (always_nonempty) && _old_first == _item) \ 271 _header->first = _new_item; \ 272 } \ 273 while (false) 274 275 #define JITTER_LIST_LINK_BEFORE(item_struct_name, item_field_name, header_p, \ 276 item_p, new_item_p) \ 277 JITTER_LIST_LINK_BEFORE_POSSIBLY_AWNE(false, item_struct_name, \ 278 item_field_name, header_p, item_p, \ 279 new_item_p) 280 281 /* Same as JITTER_LIST_LINK_BEFORE, but assume that the list is 282 always-nonempty. */ 283 #define JITTER_LIST_LINK_BEFORE_NONEMPTY(item_struct_name, item_field_name, \ 284 header_p, item_p, new_item_p) \ 285 JITTER_LIST_LINK_BEFORE_POSSIBLY_AWNE(true, item_struct_name, \ 286 item_field_name, header_p, item_p, \ 287 new_item_p) 288 289 290 #define JITTER_LIST_LINK_AFTER_POSSIBLY_AWNE(always_nonempty, \ 291 item_struct_name, \ 292 item_field_name, header_p, \ 293 item_p, new_item_p) \ 294 do \ 295 { \ 296 _JITTER_LIST_LOCALS_ (item_struct_name, item_field_name, header_p, \ 297 item_p); \ 298 struct item_struct_name * const _new_item = (new_item_p); \ 299 _item->item_field_name.next = _new_item; \ 300 _new_item->item_field_name.previous = _item; \ 301 _new_item->item_field_name.next = _old_next; \ 302 if ((always_nonempty) || _old_next != NULL) \ 303 _old_next->item_field_name.previous = _new_item; \ 304 if (! (always_nonempty) && _old_last == _item) \ 305 _header->last = _new_item; \ 306 } \ 307 while (false) 308 309 #define JITTER_LIST_LINK_AFTER(item_struct_name, item_field_name, header_p, \ 310 item_p, new_item_p) \ 311 JITTER_LIST_LINK_AFTER_POSSIBLY_AWNE(false, item_struct_name, \ 312 item_field_name, header_p, item_p, \ 313 new_item_p) 314 315 /* Same as JITTER_LIST_LINK_AFTER, but assume that the list is 316 always-nonempty. */ 317 #define JITTER_LIST_LINK_AFTER_NONEMPTY(item_struct_name, item_field_name, \ 318 header_p, item_p, new_item_p) \ 319 JITTER_LIST_LINK_AFTER_POSSIBLY_AWNE(true, item_struct_name, \ 320 item_field_name, header_p, item_p, \ 321 new_item_p) 322 323 /* Expand to a sequence of local variable declarations initialised to the 324 header, first and last items, each for one of a "to" and a "from" list; the 325 expansion is meant as part of a larger block, and not protected with 326 do..while (false). */ 327 #define _JITTER_TWO_LISTS_LOCALS_(item_struct_name, item_field_name, \ 328 to_header_p, from_header_p) \ 329 struct jitter_list_header * const _jitter_to_header __attribute__ ((unused)) \ 330 = (to_header_p); \ 331 struct item_struct_name * const _jitter_to_first __attribute__ ((unused)) \ 332 = _jitter_to_header->first; \ 333 struct item_struct_name * const _jitter_to_last __attribute__ ((unused)) \ 334 = _jitter_to_header->last; \ 335 struct jitter_list_header * const _jitter_from_header __attribute__ ((unused))\ 336 = (from_header_p); \ 337 struct item_struct_name * const _jitter_from_first __attribute__ ((unused)) \ 338 = _jitter_from_header->first; \ 339 struct item_struct_name * const _jitter_from_last __attribute__ ((unused)) \ 340 = _jitter_from_header->last; 341 342 /* Make the from list empty, moving all of its elements to the beginning 343 of the to list. */ 344 #define JITTER_LIST_PREPEND_LIST(item_struct_name, item_field_name, \ 345 to_header_p, from_header_p) \ 346 do \ 347 { \ 348 _JITTER_TWO_LISTS_LOCALS_ (item_struct_name, item_field_name, \ 349 (to_header_p), (from_header_p)); \ 350 /* At the end from is empty. The final configuration of to is: \ 351 from_first .. from_last , to_first .. to_last */ \ 352 struct item_struct_name * _jitter_new_first = _jitter_from_first; \ 353 if (_jitter_new_first == NULL) \ 354 _jitter_new_first = _jitter_to_first; \ 355 struct item_struct_name * _jitter_new_last = _jitter_to_last; \ 356 if (_jitter_new_last == NULL) \ 357 _jitter_new_last = _jitter_from_last; \ 358 if (_jitter_from_last != NULL) \ 359 _jitter_from_last->item_field_name.next = _jitter_to_first; \ 360 if (_jitter_to_first != NULL) \ 361 _jitter_to_first->item_field_name.previous = _jitter_from_last; \ 362 _jitter_to_header->first = _jitter_new_first; \ 363 _jitter_to_header->last = _jitter_new_last; \ 364 _jitter_from_header->first = NULL; \ 365 _jitter_from_header->last = NULL; \ 366 } \ 367 while (false) 368 369 /* Make the from list empty, moving all of its elements to the end of the 370 to list. */ 371 #define JITTER_LIST_APPEND_LIST(item_struct_name, item_field_name, \ 372 to_header_p, from_header_p) \ 373 do \ 374 { \ 375 _JITTER_TWO_LISTS_LOCALS_ (item_struct_name, item_field_name, \ 376 (to_header_p), (from_header_p)); \ 377 /* At the end from is empty. The final configuration of to is: \ 378 to_first .. to_last , from_first .. from_last */ \ 379 struct item_struct_name * _jitter_new_first = _jitter_to_first; \ 380 if (_jitter_new_first == NULL) \ 381 _jitter_new_first = _jitter_from_first; \ 382 struct item_struct_name * _jitter_new_last = _jitter_from_last; \ 383 if (_jitter_new_last == NULL) \ 384 _jitter_new_last = _jitter_to_last; \ 385 if (_jitter_to_last != NULL) \ 386 _jitter_to_last->item_field_name.next = _jitter_from_first; \ 387 if (_jitter_from_first != NULL) \ 388 _jitter_from_first->item_field_name.previous = _jitter_to_last; \ 389 _jitter_to_header->first = _jitter_new_first; \ 390 _jitter_to_header->last = _jitter_new_last; \ 391 _jitter_from_header->first = NULL; \ 392 _jitter_from_header->last = NULL; \ 393 } \ 394 while (false) 395 396 #endif // #ifndef JITTER_LIST_H_ 397