lib/typerb.h

   1 // SPDX-License-Identifier: ISC
   2 /*
   3  * The following Red-Black tree implementation is based off code with
   4  * original copyright:
   5  *
   6  * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
   7  */
   8
   9 #ifndef _FRR_TYPERB_H
  10 #define _FRR_TYPERB_H
  11
  12 #include <string.h>
  13 #include "typesafe.h"
  14
  15 #ifdef __cplusplus
  16 extern "C" {
  17 #endif
  18
  19 struct typed_rb_entry {
  20         struct typed_rb_entry *rbt_parent;
  21         struct typed_rb_entry *rbt_left;
  22         struct typed_rb_entry *rbt_right;
  23         unsigned int rbt_color;
  24 };
  25
  26 struct typed_rb_root {
  27         struct typed_rb_entry *rbt_root;
  28         size_t count;
  29 };
  30
  31 struct typed_rb_entry *typed_rb_insert(struct typed_rb_root *rbt,
  32                 struct typed_rb_entry *rbe,
  33                 int (*cmpfn)(
  34                         const struct typed_rb_entry *a,
  35                         const struct typed_rb_entry *b));
  36 struct typed_rb_entry *typed_rb_remove(struct typed_rb_root *rbt,
  37                                        struct typed_rb_entry *rbe);
  38 const struct typed_rb_entry *typed_rb_find(const struct typed_rb_root *rbt,
  39                 const struct typed_rb_entry *rbe,
  40                 int (*cmpfn)(
  41                         const struct typed_rb_entry *a,
  42                         const struct typed_rb_entry *b));
  43 const struct typed_rb_entry *typed_rb_find_gteq(const struct typed_rb_root *rbt,
  44                 const struct typed_rb_entry *rbe,
  45                 int (*cmpfn)(
  46                         const struct typed_rb_entry *a,
  47                         const struct typed_rb_entry *b));
  48 const struct typed_rb_entry *typed_rb_find_lt(const struct typed_rb_root *rbt,
  49                 const struct typed_rb_entry *rbe,
  50                 int (*cmpfn)(
  51                         const struct typed_rb_entry *a,
  52                         const struct typed_rb_entry *b));
  53 struct typed_rb_entry *typed_rb_min(const struct typed_rb_root *rbt);
  54 struct typed_rb_entry *typed_rb_max(const struct typed_rb_root *rbt);
  55 struct typed_rb_entry *typed_rb_prev(const struct typed_rb_entry *rbe);
  56 struct typed_rb_entry *typed_rb_next(const struct typed_rb_entry *rbe);
  57 bool typed_rb_member(const struct typed_rb_root *rbt,
  58                      const struct typed_rb_entry *rbe);
  59
  60 #define _PREDECL_RBTREE(prefix)                                                \
  61 struct prefix ## _head { struct typed_rb_root rr; };                           \
  62 struct prefix ## _item { struct typed_rb_entry re; };                          \
  63 MACRO_REQUIRE_SEMICOLON() /* end */
  64
  65 #define INIT_RBTREE_UNIQ(var)           { }
  66 #define INIT_RBTREE_NONUNIQ(var)        { }
  67
  68 #define _DECLARE_RBTREE(prefix, type, field, cmpfn_nuq, cmpfn_uq)              \
  69                                                                                \
  70 macro_inline void prefix ## _init(struct prefix##_head *h)                     \
  71 {                                                                              \
  72         memset(h, 0, sizeof(*h));                                              \
  73 }                                                                              \
  74 macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
  75 {                                                                              \
  76         memset(h, 0, sizeof(*h));                                              \
  77 }                                                                              \
  78 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
  79 {                                                                              \
  80         struct typed_rb_entry *re;                                             \
  81         re = typed_rb_insert(&h->rr, &item->field.re, cmpfn_uq);               \
  82         return container_of_null(re, type, field.re);                          \
  83 }                                                                              \
  84 macro_inline const type *prefix ## _const_find_gteq(                           \
  85                 const struct prefix##_head *h, const type *item)               \
  86 {                                                                              \
  87         const struct typed_rb_entry *re;                                       \
  88         re = typed_rb_find_gteq(&h->rr, &item->field.re, cmpfn_nuq);           \
  89         return container_of_null(re, type, field.re);                          \
  90 }                                                                              \
  91 macro_inline const type *prefix ## _const_find_lt(                             \
  92                 const struct prefix##_head *h, const type *item)               \
  93 {                                                                              \
  94         const struct typed_rb_entry *re;                                       \
  95         re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq);             \
  96         return container_of_null(re, type, field.re);                          \
  97 }                                                                              \
  98 TYPESAFE_FIND_CMP(prefix, type)                                                \
  99 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 100 {                                                                              \
 101         struct typed_rb_entry *re;                                             \
 102         re = typed_rb_remove(&h->rr, &item->field.re);                         \
 103         return container_of_null(re, type, field.re);                          \
 104 }                                                                              \
 105 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 106 {                                                                              \
 107         struct typed_rb_entry *re;                                             \
 108         re = typed_rb_min(&h->rr);                                             \
 109         if (!re)                                                               \
 110                 return NULL;                                                   \
 111         typed_rb_remove(&h->rr, re);                                           \
 112         return container_of(re, type, field.re);                               \
 113 }                                                                              \
 114 TYPESAFE_SWAP_ALL_SIMPLE(prefix)                                               \
 115 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 116 {                                                                              \
 117         const struct typed_rb_entry *re;                                       \
 118         re = typed_rb_min(&h->rr);                                             \
 119         return container_of_null(re, type, field.re);                          \
 120 }                                                                              \
 121 macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
 122                                              const type *item)                 \
 123 {                                                                              \
 124         const struct typed_rb_entry *re;                                       \
 125         re = typed_rb_next(&item->field.re);                                   \
 126         return container_of_null(re, type, field.re);                          \
 127 }                                                                              \
 128 TYPESAFE_FIRST_NEXT(prefix, type)                                              \
 129 macro_pure const type *prefix ## _const_last(const struct prefix##_head *h)    \
 130 {                                                                              \
 131         const struct typed_rb_entry *re;                                       \
 132         re = typed_rb_max(&h->rr);                                             \
 133         return container_of_null(re, type, field.re);                          \
 134 }                                                                              \
 135 macro_pure const type *prefix ## _const_prev(const struct prefix##_head *h,    \
 136                                              const type *item)                 \
 137 {                                                                              \
 138         const struct typed_rb_entry *re;                                       \
 139         re = typed_rb_prev(&item->field.re);                                   \
 140         return container_of_null(re, type, field.re);                          \
 141 }                                                                              \
 142 TYPESAFE_LAST_PREV(prefix, type)                                               \
 143 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 144 {                                                                              \
 145         struct typed_rb_entry *re;                                             \
 146         re = item ? typed_rb_next(&item->field.re) : NULL;                     \
 147         return container_of_null(re, type, field.re);                          \
 148 }                                                                              \
 149 macro_pure type *prefix ## _prev_safe(struct prefix##_head *h, type *item)     \
 150 {                                                                              \
 151         struct typed_rb_entry *re;                                             \
 152         re = item ? typed_rb_prev(&item->field.re) : NULL;                     \
 153         return container_of_null(re, type, field.re);                          \
 154 }                                                                              \
 155 macro_pure size_t prefix ## _count(const struct prefix##_head *h)              \
 156 {                                                                              \
 157         return h->rr.count;                                                    \
 158 }                                                                              \
 159 macro_pure bool prefix ## _member(const struct prefix##_head *h,               \
 160                                   const type *item)                            \
 161 {                                                                              \
 162         return typed_rb_member(&h->rr, &item->field.re);                       \
 163 }                                                                              \
 164 MACRO_REQUIRE_SEMICOLON() /* end */
 165
 166 #define PREDECL_RBTREE_UNIQ(prefix)                                            \
 167         _PREDECL_RBTREE(prefix)
 168 #define DECLARE_RBTREE_UNIQ(prefix, type, field, cmpfn)                        \
 169                                                                                \
 170 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a,               \
 171                 const struct typed_rb_entry *b)                                \
 172 {                                                                              \
 173         return cmpfn(container_of(a, type, field.re),                          \
 174                         container_of(b, type, field.re));                      \
 175 }                                                                              \
 176 macro_inline const type *prefix ## _const_find(const struct prefix##_head *h,  \
 177                                                const type *item)               \
 178 {                                                                              \
 179         const struct typed_rb_entry *re;                                       \
 180         re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp);         \
 181         return container_of_null(re, type, field.re);                          \
 182 }                                                                              \
 183 TYPESAFE_FIND(prefix, type)                                                    \
 184                                                                                \
 185 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp);        \
 186 MACRO_REQUIRE_SEMICOLON() /* end */
 187
 188 #define PREDECL_RBTREE_NONUNIQ(prefix)                                         \
 189         _PREDECL_RBTREE(prefix)
 190 #define DECLARE_RBTREE_NONUNIQ(prefix, type, field, cmpfn)                     \
 191                                                                                \
 192 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a,               \
 193                 const struct typed_rb_entry *b)                                \
 194 {                                                                              \
 195         return cmpfn(container_of(a, type, field.re),                          \
 196                         container_of(b, type, field.re));                      \
 197 }                                                                              \
 198 macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a,            \
 199                 const struct typed_rb_entry *b)                                \
 200 {                                                                              \
 201         int cmpval = cmpfn(container_of(a, type, field.re),                    \
 202                         container_of(b, type, field.re));                      \
 203         if (cmpval)                                                            \
 204                 return cmpval;                                                 \
 205         if (a < b)                                                             \
 206                 return -1;                                                     \
 207         if (a > b)                                                             \
 208                 return 1;                                                      \
 209         return 0;                                                              \
 210 }                                                                              \
 211                                                                                \
 212 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq);     \
 213 MACRO_REQUIRE_SEMICOLON() /* end */
 214
 215 #ifdef __cplusplus
 216 }
 217 #endif
 218
 219 #endif /* _FRR_TYPERB_H */