lib/typerb.h

   1 /*
   2  * The following Red-Black tree implementation is based off code with
   3  * original copyright:
   4  *
   5  * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
   6  *
   7  * Permission to use, copy, modify, and distribute this software for any
   8  * purpose with or without fee is hereby granted, provided that the above
   9  * copyright notice and this permission notice appear in all copies.
  10  *
  11  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  12  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  13  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  14  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  15  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  16  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  17  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  18  */
  19
  20 #ifndef _FRR_TYPERB_H
  21 #define _FRR_TYPERB_H
  22
  23 #include "typesafe.h"
  24
  25 #ifdef __cplusplus
  26 extern "C" {
  27 #endif
  28
  29 struct typed_rb_entry {
  30         struct typed_rb_entry *rbt_parent;
  31         struct typed_rb_entry *rbt_left;
  32         struct typed_rb_entry *rbt_right;
  33         unsigned int rbt_color;
  34 };
  35
  36 struct typed_rb_root {
  37         struct typed_rb_entry *rbt_root;
  38         size_t count;
  39 };
  40
  41 struct typed_rb_entry *typed_rb_insert(struct typed_rb_root *rbt,
  42                 struct typed_rb_entry *rbe,
  43                 int (*cmpfn)(
  44                         const struct typed_rb_entry *a,
  45                         const struct typed_rb_entry *b));
  46 struct typed_rb_entry *typed_rb_remove(struct typed_rb_root *rbt,
  47                                        struct typed_rb_entry *rbe);
  48 const struct typed_rb_entry *typed_rb_find(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 const struct typed_rb_entry *typed_rb_find_gteq(const struct typed_rb_root *rbt,
  54                 const struct typed_rb_entry *rbe,
  55                 int (*cmpfn)(
  56                         const struct typed_rb_entry *a,
  57                         const struct typed_rb_entry *b));
  58 const struct typed_rb_entry *typed_rb_find_lt(const struct typed_rb_root *rbt,
  59                 const struct typed_rb_entry *rbe,
  60                 int (*cmpfn)(
  61                         const struct typed_rb_entry *a,
  62                         const struct typed_rb_entry *b));
  63 struct typed_rb_entry *typed_rb_min(const struct typed_rb_root *rbt);
  64 struct typed_rb_entry *typed_rb_next(const struct typed_rb_entry *rbe);
  65
  66 #define _PREDECL_RBTREE(prefix)                                                \
  67 struct prefix ## _head { struct typed_rb_root rr; };                           \
  68 struct prefix ## _item { struct typed_rb_entry re; };                          \
  69 MACRO_REQUIRE_SEMICOLON() /* end */
  70
  71 #define INIT_RBTREE_UNIQ(var)           { }
  72 #define INIT_RBTREE_NONUNIQ(var)        { }
  73
  74 #define _DECLARE_RBTREE(prefix, type, field, cmpfn_nuq, cmpfn_uq)              \
  75                                                                                \
  76 macro_inline void prefix ## _init(struct prefix##_head *h)                     \
  77 {                                                                              \
  78         memset(h, 0, sizeof(*h));                                              \
  79 }                                                                              \
  80 macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
  81 {                                                                              \
  82         memset(h, 0, sizeof(*h));                                              \
  83 }                                                                              \
  84 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
  85 {                                                                              \
  86         struct typed_rb_entry *re;                                             \
  87         re = typed_rb_insert(&h->rr, &item->field.re, cmpfn_uq);               \
  88         return container_of_null(re, type, field.re);                          \
  89 }                                                                              \
  90 macro_inline const type *prefix ## _const_find_gteq(                           \
  91                 const struct prefix##_head *h, const type *item)               \
  92 {                                                                              \
  93         const struct typed_rb_entry *re;                                       \
  94         re = typed_rb_find_gteq(&h->rr, &item->field.re, cmpfn_nuq);           \
  95         return container_of_null(re, type, field.re);                          \
  96 }                                                                              \
  97 macro_inline const type *prefix ## _const_find_lt(                             \
  98                 const struct prefix##_head *h, const type *item)               \
  99 {                                                                              \
 100         const struct typed_rb_entry *re;                                       \
 101         re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq);             \
 102         return container_of_null(re, type, field.re);                          \
 103 }                                                                              \
 104 TYPESAFE_FIND_CMP(prefix, type)                                                \
 105 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 106 {                                                                              \
 107         struct typed_rb_entry *re;                                             \
 108         re = typed_rb_remove(&h->rr, &item->field.re);                         \
 109         return container_of_null(re, type, field.re);                          \
 110 }                                                                              \
 111 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 112 {                                                                              \
 113         struct typed_rb_entry *re;                                             \
 114         re = typed_rb_min(&h->rr);                                             \
 115         if (!re)                                                               \
 116                 return NULL;                                                   \
 117         typed_rb_remove(&h->rr, re);                                           \
 118         return container_of(re, type, field.re);                               \
 119 }                                                                              \
 120 TYPESAFE_SWAP_ALL_SIMPLE(prefix)                                               \
 121 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
 122 {                                                                              \
 123         const struct typed_rb_entry *re;                                       \
 124         re = typed_rb_min(&h->rr);                                             \
 125         return container_of_null(re, type, field.re);                          \
 126 }                                                                              \
 127 macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
 128                                              const type *item)                 \
 129 {                                                                              \
 130         const struct typed_rb_entry *re;                                       \
 131         re = typed_rb_next(&item->field.re);                                   \
 132         return container_of_null(re, type, field.re);                          \
 133 }                                                                              \
 134 TYPESAFE_FIRST_NEXT(prefix, type)                                              \
 135 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 136 {                                                                              \
 137         struct typed_rb_entry *re;                                             \
 138         re = item ? typed_rb_next(&item->field.re) : NULL;                     \
 139         return container_of_null(re, type, field.re);                          \
 140 }                                                                              \
 141 macro_pure size_t prefix ## _count(const struct prefix##_head *h)              \
 142 {                                                                              \
 143         return h->rr.count;                                                    \
 144 }                                                                              \
 145 MACRO_REQUIRE_SEMICOLON() /* end */
 146
 147 #define PREDECL_RBTREE_UNIQ(prefix)                                            \
 148         _PREDECL_RBTREE(prefix)
 149 #define DECLARE_RBTREE_UNIQ(prefix, type, field, cmpfn)                        \
 150                                                                                \
 151 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a,               \
 152                 const struct typed_rb_entry *b)                                \
 153 {                                                                              \
 154         return cmpfn(container_of(a, type, field.re),                          \
 155                         container_of(b, type, field.re));                      \
 156 }                                                                              \
 157 macro_inline const type *prefix ## _const_find(const struct prefix##_head *h,  \
 158                                                const type *item)               \
 159 {                                                                              \
 160         const struct typed_rb_entry *re;                                       \
 161         re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp);         \
 162         return container_of_null(re, type, field.re);                          \
 163 }                                                                              \
 164 TYPESAFE_FIND(prefix, type)                                                    \
 165                                                                                \
 166 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp);        \
 167 MACRO_REQUIRE_SEMICOLON() /* end */
 168
 169 #define PREDECL_RBTREE_NONUNIQ(prefix)                                         \
 170         _PREDECL_RBTREE(prefix)
 171 #define DECLARE_RBTREE_NONUNIQ(prefix, type, field, cmpfn)                     \
 172                                                                                \
 173 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a,               \
 174                 const struct typed_rb_entry *b)                                \
 175 {                                                                              \
 176         return cmpfn(container_of(a, type, field.re),                          \
 177                         container_of(b, type, field.re));                      \
 178 }                                                                              \
 179 macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a,            \
 180                 const struct typed_rb_entry *b)                                \
 181 {                                                                              \
 182         int cmpval = cmpfn(container_of(a, type, field.re),                    \
 183                         container_of(b, type, field.re));                      \
 184         if (cmpval)                                                            \
 185                 return cmpval;                                                 \
 186         if (a < b)                                                             \
 187                 return -1;                                                     \
 188         if (a > b)                                                             \
 189                 return 1;                                                      \
 190         return 0;                                                              \
 191 }                                                                              \
 192                                                                                \
 193 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq);     \
 194 MACRO_REQUIRE_SEMICOLON() /* end */
 195
 196 #ifdef __cplusplus
 197 }
 198 #endif
 199
 200 #endif /* _FRR_TYPERB_H */