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 == elem); \ 110 return elem->ossl_list_ ## name.next; \ 111 } \ 112 static ossl_unused ossl_inline type * \ 113 ossl_list_##name##_prev(const type *elem) \ 114 { \ 115 assert(elem->ossl_list_ ## name.prev == NULL \ 116 || elem->ossl_list_ ## name.prev \ 117 ->ossl_list_ ## name.next == elem); \ 118 return elem->ossl_list_ ## name.prev; \ 119 } \ 120 static ossl_unused ossl_inline void \ 121 ossl_list_##name##_remove(OSSL_LIST(name) *list, type *elem) \ 122 { \ 123 assert(elem->ossl_list_ ## name.list == list); \ 124 OSSL_LIST_DBG(elem->ossl_list_ ## name.list = NULL) \ 125 if (list->alpha == elem) \ 126 list->alpha = elem->ossl_list_ ## name.next; \ 127 if (list->omega == elem) \ 128 list->omega = elem->ossl_list_ ## name.prev; \ 129 if (elem->ossl_list_ ## name.prev != NULL) \ 130 elem->ossl_list_ ## name.prev->ossl_list_ ## name.next = \ 131 elem->ossl_list_ ## name.next; \ 132 if (elem->ossl_list_ ## name.next != NULL) \ 133 elem->ossl_list_ ## name.next->ossl_list_ ## name.prev = \ 134 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
