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