xref: /openssl/include/internal/list.h (revision c4ec708b)
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