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 struct typed_rb_entry {
  26         struct typed_rb_entry *rbt_parent;
  27         struct typed_rb_entry *rbt_left;
  28         struct typed_rb_entry *rbt_right;
  29         unsigned int rbt_color;
  30 };
  31
  32 struct typed_rb_root {
  33         struct typed_rb_entry *rbt_root;
  34         size_t count;
  35 };
  36
  37 struct typed_rb_entry *typed_rb_insert(struct typed_rb_root *,
  38                 struct typed_rb_entry *rbe,
  39                 int (*cmpfn)(
  40                         const struct typed_rb_entry *a,
  41                         const struct typed_rb_entry *b));
  42 void typed_rb_remove(struct typed_rb_root *, struct typed_rb_entry *rbe);
  43 struct typed_rb_entry *typed_rb_find(struct typed_rb_root *,
  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 struct typed_rb_entry *typed_rb_find_gteq(struct typed_rb_root *,
  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_find_lt(struct typed_rb_root *,
  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 struct typed_rb_entry *typed_rb_min(struct typed_rb_root *);
  59 struct typed_rb_entry *typed_rb_next(struct typed_rb_entry *);
  60
  61 #define _PREDECL_RBTREE(prefix)                                                \
  62 struct prefix ## _head { struct typed_rb_root rr; };                           \
  63 struct prefix ## _item { struct typed_rb_entry re; };
  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 type *prefix ## _find_gteq(struct prefix##_head *h,               \
  85                 const type *item)                                              \
  86 {                                                                              \
  87         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 type *prefix ## _find_lt(struct prefix##_head *h,                 \
  92                 const type *item)                                              \
  93 {                                                                              \
  94         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 macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
  99 {                                                                              \
 100         typed_rb_remove(&h->rr, &item->field.re);                              \
 101 }                                                                              \
 102 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 103 {                                                                              \
 104         struct typed_rb_entry *re;                                             \
 105         re = typed_rb_min(&h->rr);                                             \
 106         if (!re)                                                               \
 107                 return NULL;                                                   \
 108         typed_rb_remove(&h->rr, re);                                           \
 109         return container_of(re, type, field.re);                               \
 110 }                                                                              \
 111 macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
 112 {                                                                              \
 113         struct typed_rb_entry *re;                                             \
 114         re = typed_rb_min(&h->rr);                                             \
 115         return container_of_null(re, type, field.re);                          \
 116 }                                                                              \
 117 macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
 118 {                                                                              \
 119         struct typed_rb_entry *re;                                             \
 120         re = typed_rb_next(&item->field.re);                                   \
 121         return container_of_null(re, type, field.re);                          \
 122 }                                                                              \
 123 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 124 {                                                                              \
 125         struct typed_rb_entry *re;                                             \
 126         re = item ? typed_rb_next(&item->field.re) : NULL;                     \
 127         return container_of_null(re, type, field.re);                          \
 128 }                                                                              \
 129 macro_pure size_t prefix ## _count(struct prefix##_head *h)                    \
 130 {                                                                              \
 131         return h->rr.count;                                                    \
 132 }                                                                              \
 133 /* ... */
 134
 135 #define PREDECL_RBTREE_UNIQ(prefix)                                            \
 136         _PREDECL_RBTREE(prefix)
 137 #define DECLARE_RBTREE_UNIQ(prefix, type, field, cmpfn)                        \
 138                                                                                \
 139 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a,               \
 140                 const struct typed_rb_entry *b)                                \
 141 {                                                                              \
 142         return cmpfn(container_of(a, type, field.re),                          \
 143                         container_of(b, type, field.re));                      \
 144 }                                                                              \
 145 macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
 146 {                                                                              \
 147         struct typed_rb_entry *re;                                             \
 148         re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp);         \
 149         return container_of_null(re, type, field.re);                          \
 150 }                                                                              \
 151                                                                                \
 152 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp)         \
 153 /* ... */
 154
 155 #define PREDECL_RBTREE_NONUNIQ(prefix)                                         \
 156         _PREDECL_RBTREE(prefix)
 157 #define DECLARE_RBTREE_NONUNIQ(prefix, type, field, cmpfn)                     \
 158                                                                                \
 159 macro_inline int prefix ## __cmp(const struct typed_rb_entry *a,               \
 160                 const struct typed_rb_entry *b)                                \
 161 {                                                                              \
 162         return cmpfn(container_of(a, type, field.re),                          \
 163                         container_of(b, type, field.re));                      \
 164 }                                                                              \
 165 macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a,            \
 166                 const struct typed_rb_entry *b)                                \
 167 {                                                                              \
 168         int cmpval = cmpfn(container_of(a, type, field.re),                    \
 169                         container_of(b, type, field.re));                      \
 170         if (cmpval)                                                            \
 171                 return cmpval;                                                 \
 172         if (a < b)                                                             \
 173                 return -1;                                                     \
 174         if (a > b)                                                             \
 175                 return 1;                                                      \
 176         return 0;                                                              \
 177 }                                                                              \
 178                                                                                \
 179 _DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq)      \
 180 /* ... */
 181
 182 #endif /* _FRR_TYPERB_H */