include/internal/list.h

   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 LIST_FOREACH_FROM(p, name, init)                                   \
  24     for ((p) = (init);                                                      \
  25          (p) != NULL;                                                       \
  26          (p) = ossl_list_##name##_next(p))
  27 # define LIST_FOREACH(p, name, l)                                           \
  28     LIST_FOREACH_FROM(p, name, ossl_list_##name##_head(l))
  29
  30 # define LIST_FOREACH_REV_FROM(p, name, init)                               \
  31     for ((p) = (init);                                                      \
  32          (p) != NULL;                                                       \
  33          (p) = ossl_list_##name##_prev(p))
  34 # define LIST_FOREACH_REV(p, name, l)                                       \
  35     LIST_FOREACH_FROM(p, name, ossl_list_##name##_tail(l))
  36
  37 # define 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 LIST_FOREACH_DELSAFE(p, pn, name, l)                                \
  42     LIST_FOREACH_DELSAFE_FROM(p, pn, name, ossl_list_##name##_head(l))
  43
  44 # define 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 LIST_FOREACH_REV_DELSAFE(p, pn, name, l)                           \
  49     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