1 /* 2 * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #ifndef OSSL_INTERNAL_LIST_H 11 #define OSSL_INTERNAL_LIST_H 12 #pragma once 13 14 #include <string.h> 15 #include <assert.h> 16 17 #ifdef NDEBUG 18 #define OSSL_LIST_DBG(x) 19 #else 20 #define OSSL_LIST_DBG(x) x; 21 #endif 22 23 #define OSSL_LIST_FOREACH_FROM(p, name, init) \ 24 for ((p) = (init); \ 25 (p) != NULL; \ 26 (p) = ossl_list_##name##_next(p)) 27 #define OSSL_LIST_FOREACH(p, name, l) \ 28 OSSL_LIST_FOREACH_FROM(p, name, ossl_list_##name##_head(l)) 29 30 #define OSSL_LIST_FOREACH_REV_FROM(p, name, init) \ 31 for ((p) = (init); \ 32 (p) != NULL; \ 33 (p) = ossl_list_##name##_prev(p)) 34 #define OSSL_LIST_FOREACH_REV(p, name, l) \ 35 OSSL_LIST_FOREACH_FROM(p, name, ossl_list_##name##_tail(l)) 36 37 #define OSSL_LIST_FOREACH_DELSAFE_FROM(p, pn, name, init) \ 38 for ((p) = (init); \ 39 (p) != NULL && (((pn) = ossl_list_##name##_next(p)), 1); \ 40 (p) = (pn)) 41 #define OSSL_LIST_FOREACH_DELSAFE(p, pn, name, l) \ 42 OSSL_LIST_FOREACH_DELSAFE_FROM(p, pn, name, ossl_list_##name##_head(l)) 43 44 #define OSSL_LIST_FOREACH_REV_DELSAFE_FROM(p, pn, name, init) \ 45 for ((p) = (init); \ 46 (p) != NULL && (((pn) = ossl_list_##name##_prev(p)), 1); \ 47 (p) = (pn)) 48 #define OSSL_LIST_FOREACH_REV_DELSAFE(p, pn, name, l) \ 49 OSSL_LIST_FOREACH_REV_DELSAFE_FROM(p, pn, name, ossl_list_##name##_tail(l)) 50 51 /* Define a list structure */ 52 #define OSSL_LIST(name) OSSL_LIST_##name 53 54 /* Define fields to include an element of a list */ 55 #define OSSL_LIST_MEMBER(name, type) \ 56 struct { \ 57 type *next, *prev; \ 58 OSSL_LIST_DBG(struct ossl_list_st_##name *list) \ 59 } ossl_list_##name 60 61 #define DECLARE_LIST_OF(name, type) \ 62 typedef struct ossl_list_st_##name OSSL_LIST(name); \ 63 struct ossl_list_st_##name { \ 64 type *alpha, *omega; \ 65 size_t num_elems; \ 66 } 67 68 #define DEFINE_LIST_OF_IMPL(name, type) \ 69 static ossl_unused ossl_inline void \ 70 ossl_list_##name##_init(OSSL_LIST(name) * list) \ 71 { \ 72 memset(list, 0, sizeof(*list)); \ 73 } \ 74 static ossl_unused ossl_inline void \ 75 ossl_list_##name##_init_elem(type *elem) \ 76 { \ 77 memset(&elem->ossl_list_##name, 0, \ 78 sizeof(elem->ossl_list_##name)); \ 79 } \ 80 static ossl_unused ossl_inline int \ 81 ossl_list_##name##_is_empty(const OSSL_LIST(name) * list) \ 82 { \ 83 return list->num_elems == 0; \ 84 } \ 85 static ossl_unused ossl_inline size_t \ 86 ossl_list_##name##_num(const OSSL_LIST(name) * list) \ 87 { \ 88 return list->num_elems; \ 89 } \ 90 static ossl_unused ossl_inline type * \ 91 ossl_list_##name##_head(const OSSL_LIST(name) * list) \ 92 { \ 93 assert(list->alpha == NULL \ 94 || list->alpha->ossl_list_##name.list == list); \ 95 return list->alpha; \ 96 } \ 97 static ossl_unused ossl_inline type * \ 98 ossl_list_##name##_tail(const OSSL_LIST(name) * list) \ 99 { \ 100 assert(list->omega == NULL \ 101 || list->omega->ossl_list_##name.list == list); \ 102 return list->omega; \ 103 } \ 104 static ossl_unused ossl_inline type * \ 105 ossl_list_##name##_next(const type *elem) \ 106 { \ 107 assert(elem->ossl_list_##name.next == NULL \ 108 || elem->ossl_list_##name.next \ 109 ->ossl_list_##name.prev \ 110 == elem); \ 111 return elem->ossl_list_##name.next; \ 112 } \ 113 static ossl_unused ossl_inline type * \ 114 ossl_list_##name##_prev(const type *elem) \ 115 { \ 116 assert(elem->ossl_list_##name.prev == NULL \ 117 || elem->ossl_list_##name.prev \ 118 ->ossl_list_##name.next \ 119 == elem); \ 120 return elem->ossl_list_##name.prev; \ 121 } \ 122 static ossl_unused ossl_inline void \ 123 ossl_list_##name##_remove(OSSL_LIST(name) * list, type * elem) \ 124 { \ 125 assert(elem->ossl_list_##name.list == list); \ 126 OSSL_LIST_DBG(elem->ossl_list_##name.list = NULL) \ 127 if (list->alpha == elem) \ 128 list->alpha = elem->ossl_list_##name.next; \ 129 if (list->omega == elem) \ 130 list->omega = elem->ossl_list_##name.prev; \ 131 if (elem->ossl_list_##name.prev != NULL) \ 132 elem->ossl_list_##name.prev->ossl_list_##name.next = elem->ossl_list_##name.next; \ 133 if (elem->ossl_list_##name.next != NULL) \ 134 elem->ossl_list_##name.next->ossl_list_##name.prev = elem->ossl_list_##name.prev; \ 135 list->num_elems--; \ 136 memset(&elem->ossl_list_##name, 0, \ 137 sizeof(elem->ossl_list_##name)); \ 138 } \ 139 static ossl_unused ossl_inline void \ 140 ossl_list_##name##_insert_head(OSSL_LIST(name) * list, type * elem) \ 141 { \ 142 assert(elem->ossl_list_##name.list == NULL); \ 143 OSSL_LIST_DBG(elem->ossl_list_##name.list = list) \ 144 if (list->alpha != NULL) \ 145 list->alpha->ossl_list_##name.prev = elem; \ 146 elem->ossl_list_##name.next = list->alpha; \ 147 elem->ossl_list_##name.prev = NULL; \ 148 list->alpha = elem; \ 149 if (list->omega == NULL) \ 150 list->omega = elem; \ 151 list->num_elems++; \ 152 } \ 153 static ossl_unused ossl_inline void \ 154 ossl_list_##name##_insert_tail(OSSL_LIST(name) * list, type * elem) \ 155 { \ 156 assert(elem->ossl_list_##name.list == NULL); \ 157 OSSL_LIST_DBG(elem->ossl_list_##name.list = list) \ 158 if (list->omega != NULL) \ 159 list->omega->ossl_list_##name.next = elem; \ 160 elem->ossl_list_##name.prev = list->omega; \ 161 elem->ossl_list_##name.next = NULL; \ 162 list->omega = elem; \ 163 if (list->alpha == NULL) \ 164 list->alpha = elem; \ 165 list->num_elems++; \ 166 } \ 167 static ossl_unused ossl_inline void \ 168 ossl_list_##name##_insert_before(OSSL_LIST(name) * list, type * e, \ 169 type * elem) \ 170 { \ 171 assert(elem->ossl_list_##name.list == NULL); \ 172 OSSL_LIST_DBG(elem->ossl_list_##name.list = list) \ 173 elem->ossl_list_##name.next = e; \ 174 elem->ossl_list_##name.prev = e->ossl_list_##name.prev; \ 175 if (e->ossl_list_##name.prev != NULL) \ 176 e->ossl_list_##name.prev->ossl_list_##name.next = elem; \ 177 e->ossl_list_##name.prev = elem; \ 178 if (list->alpha == e) \ 179 list->alpha = elem; \ 180 list->num_elems++; \ 181 } \ 182 static ossl_unused ossl_inline void \ 183 ossl_list_##name##_insert_after(OSSL_LIST(name) * list, type * e, \ 184 type * elem) \ 185 { \ 186 assert(elem->ossl_list_##name.list == NULL); \ 187 OSSL_LIST_DBG(elem->ossl_list_##name.list = list) \ 188 elem->ossl_list_##name.prev = e; \ 189 elem->ossl_list_##name.next = e->ossl_list_##name.next; \ 190 if (e->ossl_list_##name.next != NULL) \ 191 e->ossl_list_##name.next->ossl_list_##name.prev = elem; \ 192 e->ossl_list_##name.next = elem; \ 193 if (list->omega == e) \ 194 list->omega = elem; \ 195 list->num_elems++; \ 196 } \ 197 struct ossl_list_st_##name 198 199 #define DEFINE_LIST_OF(name, type) \ 200 DECLARE_LIST_OF(name, type); \ 201 DEFINE_LIST_OF_IMPL(name, type) 202 203 #endif 204