Jason Evans | 0b2368a | 2010-01-03 11:59:14 -0800 | [diff] [blame] | 1 | /*- |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 2 | ******************************************************************************* |
| 3 | * |
| 4 | * cpp macro implementation of left-leaning 2-3 red-black trees. Parent |
| 5 | * pointers are not used, and color bits are stored in the least significant |
| 6 | * bit of right-child pointers (if RB_COMPACT is defined), thus making node |
| 7 | * linkage as compact as is possible for red-black trees. |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 8 | * |
| 9 | * Usage: |
| 10 | * |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 11 | * #include <stdint.h> |
| 12 | * #include <stdbool.h> |
| 13 | * #define NDEBUG // (Optional, see assert(3).) |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 14 | * #include <assert.h> |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 15 | * #define RB_COMPACT // (Optional, embed color bits in right-child pointers.) |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 16 | * #include <rb.h> |
| 17 | * ... |
| 18 | * |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 19 | ******************************************************************************* |
| 20 | */ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 21 | |
| 22 | #ifndef RB_H_ |
| 23 | #define RB_H_ |
| 24 | |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 25 | #ifdef RB_COMPACT |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 26 | /* Node structure. */ |
| 27 | #define rb_node(a_type) \ |
| 28 | struct { \ |
| 29 | a_type *rbn_left; \ |
| 30 | a_type *rbn_right_red; \ |
| 31 | } |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 32 | #else |
| 33 | #define rb_node(a_type) \ |
| 34 | struct { \ |
| 35 | a_type *rbn_left; \ |
| 36 | a_type *rbn_right; \ |
| 37 | bool rbn_red; \ |
| 38 | } |
| 39 | #endif |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 40 | |
| 41 | /* Root structure. */ |
| 42 | #define rb_tree(a_type) \ |
| 43 | struct { \ |
| 44 | a_type *rbt_root; \ |
| 45 | a_type rbt_nil; \ |
| 46 | } |
| 47 | |
| 48 | /* Left accessors. */ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 49 | #define rbtn_left_get(a_type, a_field, a_node) \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 50 | ((a_node)->a_field.rbn_left) |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 51 | #define rbtn_left_set(a_type, a_field, a_node, a_left) do { \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 52 | (a_node)->a_field.rbn_left = a_left; \ |
| 53 | } while (0) |
| 54 | |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 55 | #ifdef RB_COMPACT |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 56 | /* Right accessors. */ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 57 | #define rbtn_right_get(a_type, a_field, a_node) \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 58 | ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \ |
| 59 | & ((ssize_t)-2))) |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 60 | #define rbtn_right_set(a_type, a_field, a_node, a_right) do { \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 61 | (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \ |
| 62 | | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1))); \ |
| 63 | } while (0) |
| 64 | |
| 65 | /* Color accessors. */ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 66 | #define rbtn_red_get(a_type, a_field, a_node) \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 67 | ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red) \ |
| 68 | & ((size_t)1))) |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 69 | #define rbtn_color_set(a_type, a_field, a_node, a_red) do { \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 70 | (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \ |
| 71 | (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)) \ |
| 72 | | ((ssize_t)a_red)); \ |
| 73 | } while (0) |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 74 | #define rbtn_red_set(a_type, a_field, a_node) do { \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 75 | (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \ |
| 76 | (a_node)->a_field.rbn_right_red) | ((size_t)1)); \ |
| 77 | } while (0) |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 78 | #define rbtn_black_set(a_type, a_field, a_node) do { \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 79 | (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \ |
| 80 | (a_node)->a_field.rbn_right_red) & ((ssize_t)-2)); \ |
| 81 | } while (0) |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 82 | #else |
| 83 | /* Right accessors. */ |
| 84 | #define rbtn_right_get(a_type, a_field, a_node) \ |
| 85 | ((a_node)->a_field.rbn_right) |
| 86 | #define rbtn_right_set(a_type, a_field, a_node, a_right) do { \ |
| 87 | (a_node)->a_field.rbn_right = a_right; \ |
| 88 | } while (0) |
| 89 | |
| 90 | /* Color accessors. */ |
| 91 | #define rbtn_red_get(a_type, a_field, a_node) \ |
| 92 | ((a_node)->a_field.rbn_red) |
| 93 | #define rbtn_color_set(a_type, a_field, a_node, a_red) do { \ |
| 94 | (a_node)->a_field.rbn_red = (a_red); \ |
| 95 | } while (0) |
| 96 | #define rbtn_red_set(a_type, a_field, a_node) do { \ |
| 97 | (a_node)->a_field.rbn_red = true; \ |
| 98 | } while (0) |
| 99 | #define rbtn_black_set(a_type, a_field, a_node) do { \ |
| 100 | (a_node)->a_field.rbn_red = false; \ |
| 101 | } while (0) |
| 102 | #endif |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 103 | |
| 104 | /* Node initializer. */ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 105 | #define rbt_node_new(a_type, a_field, a_rbt, a_node) do { \ |
| 106 | rbtn_left_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \ |
| 107 | rbtn_right_set(a_type, a_field, (a_node), &(a_rbt)->rbt_nil); \ |
| 108 | rbtn_red_set(a_type, a_field, (a_node)); \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 109 | } while (0) |
| 110 | |
| 111 | /* Tree initializer. */ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 112 | #define rb_new(a_type, a_field, a_rbt) do { \ |
| 113 | (a_rbt)->rbt_root = &(a_rbt)->rbt_nil; \ |
| 114 | rbt_node_new(a_type, a_field, a_rbt, &(a_rbt)->rbt_nil); \ |
| 115 | rbtn_black_set(a_type, a_field, &(a_rbt)->rbt_nil); \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 116 | } while (0) |
| 117 | |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 118 | /* Internal utility macros. */ |
| 119 | #define rbtn_first(a_type, a_field, a_rbt, a_root, r_node) do { \ |
| 120 | (r_node) = (a_root); \ |
| 121 | if ((r_node) != &(a_rbt)->rbt_nil) { \ |
| 122 | for (; \ |
| 123 | rbtn_left_get(a_type, a_field, (r_node)) != &(a_rbt)->rbt_nil;\ |
| 124 | (r_node) = rbtn_left_get(a_type, a_field, (r_node))) { \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 125 | } \ |
| 126 | } \ |
| 127 | } while (0) |
| 128 | |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 129 | #define rbtn_last(a_type, a_field, a_rbt, a_root, r_node) do { \ |
| 130 | (r_node) = (a_root); \ |
| 131 | if ((r_node) != &(a_rbt)->rbt_nil) { \ |
| 132 | for (; rbtn_right_get(a_type, a_field, (r_node)) != \ |
| 133 | &(a_rbt)->rbt_nil; (r_node) = rbtn_right_get(a_type, a_field, \ |
| 134 | (r_node))) { \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 135 | } \ |
| 136 | } \ |
| 137 | } while (0) |
| 138 | |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 139 | #define rbtn_rotate_left(a_type, a_field, a_node, r_node) do { \ |
| 140 | (r_node) = rbtn_right_get(a_type, a_field, (a_node)); \ |
| 141 | rbtn_right_set(a_type, a_field, (a_node), \ |
| 142 | rbtn_left_get(a_type, a_field, (r_node))); \ |
| 143 | rbtn_left_set(a_type, a_field, (r_node), (a_node)); \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 144 | } while (0) |
| 145 | |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 146 | #define rbtn_rotate_right(a_type, a_field, a_node, r_node) do { \ |
| 147 | (r_node) = rbtn_left_get(a_type, a_field, (a_node)); \ |
| 148 | rbtn_left_set(a_type, a_field, (a_node), \ |
| 149 | rbtn_right_get(a_type, a_field, (r_node))); \ |
| 150 | rbtn_right_set(a_type, a_field, (r_node), (a_node)); \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 151 | } while (0) |
| 152 | |
| 153 | /* |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 154 | * The rb_proto() macro generates function prototypes that correspond to the |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 155 | * functions generated by an equivalently parameterized call to rb_gen(). |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 156 | */ |
| 157 | |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 158 | #define rb_proto(a_attr, a_prefix, a_rbt_type, a_type) \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 159 | a_attr void \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 160 | a_prefix##new(a_rbt_type *rbtree); \ |
Jason Evans | 1628e86 | 2014-08-19 01:28:49 -0700 | [diff] [blame] | 161 | a_attr bool \ |
| 162 | a_prefix##empty(a_rbt_type *rbtree); \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 163 | a_attr a_type * \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 164 | a_prefix##first(a_rbt_type *rbtree); \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 165 | a_attr a_type * \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 166 | a_prefix##last(a_rbt_type *rbtree); \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 167 | a_attr a_type * \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 168 | a_prefix##next(a_rbt_type *rbtree, a_type *node); \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 169 | a_attr a_type * \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 170 | a_prefix##prev(a_rbt_type *rbtree, a_type *node); \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 171 | a_attr a_type * \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 172 | a_prefix##search(a_rbt_type *rbtree, a_type *key); \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 173 | a_attr a_type * \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 174 | a_prefix##nsearch(a_rbt_type *rbtree, a_type *key); \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 175 | a_attr a_type * \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 176 | a_prefix##psearch(a_rbt_type *rbtree, a_type *key); \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 177 | a_attr void \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 178 | a_prefix##insert(a_rbt_type *rbtree, a_type *node); \ |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 179 | a_attr void \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 180 | a_prefix##remove(a_rbt_type *rbtree, a_type *node); \ |
| 181 | a_attr a_type * \ |
| 182 | a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ |
| 183 | a_rbt_type *, a_type *, void *), void *arg); \ |
| 184 | a_attr a_type * \ |
| 185 | a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ |
| 186 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg); |
Jason Evans | e476f8a | 2010-01-16 09:53:50 -0800 | [diff] [blame] | 187 | |
| 188 | /* |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 189 | * The rb_gen() macro generates a type-specific red-black tree implementation, |
| 190 | * based on the above cpp macros. |
| 191 | * |
| 192 | * Arguments: |
| 193 | * |
| 194 | * a_attr : Function attribute for generated functions (ex: static). |
Jason Evans | 74025c8 | 2010-02-28 15:23:17 -0800 | [diff] [blame] | 195 | * a_prefix : Prefix for generated functions (ex: ex_). |
| 196 | * a_rb_type : Type for red-black tree data structure (ex: ex_t). |
| 197 | * a_type : Type for red-black tree node data structure (ex: ex_node_t). |
| 198 | * a_field : Name of red-black tree node linkage (ex: ex_link). |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 199 | * a_cmp : Node comparison function name, with the following prototype: |
| 200 | * int (a_cmp *)(a_type *a_node, a_type *a_other); |
| 201 | * ^^^^^^ |
| 202 | * or a_key |
| 203 | * Interpretation of comparision function return values: |
| 204 | * -1 : a_node < a_other |
| 205 | * 0 : a_node == a_other |
| 206 | * 1 : a_node > a_other |
| 207 | * In all cases, the a_node or a_key macro argument is the first |
| 208 | * argument to the comparison function, which makes it possible |
| 209 | * to write comparison functions that treat the first argument |
| 210 | * specially. |
| 211 | * |
| 212 | * Assuming the following setup: |
| 213 | * |
| 214 | * typedef struct ex_node_s ex_node_t; |
| 215 | * struct ex_node_s { |
| 216 | * rb_node(ex_node_t) ex_link; |
| 217 | * }; |
Jason Evans | 74025c8 | 2010-02-28 15:23:17 -0800 | [diff] [blame] | 218 | * typedef rb_tree(ex_node_t) ex_t; |
| 219 | * rb_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_cmp) |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 220 | * |
| 221 | * The following API is generated: |
| 222 | * |
| 223 | * static void |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 224 | * ex_new(ex_t *tree); |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 225 | * Description: Initialize a red-black tree structure. |
| 226 | * Args: |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 227 | * tree: Pointer to an uninitialized red-black tree object. |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 228 | * |
Jason Evans | 1628e86 | 2014-08-19 01:28:49 -0700 | [diff] [blame] | 229 | * static bool |
| 230 | * ex_empty(ex_t *tree); |
| 231 | * Description: Determine whether tree is empty. |
| 232 | * Args: |
| 233 | * tree: Pointer to an initialized red-black tree object. |
| 234 | * Ret: True if tree is empty, false otherwise. |
| 235 | * |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 236 | * static ex_node_t * |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 237 | * ex_first(ex_t *tree); |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 238 | * static ex_node_t * |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 239 | * ex_last(ex_t *tree); |
| 240 | * Description: Get the first/last node in tree. |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 241 | * Args: |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 242 | * tree: Pointer to an initialized red-black tree object. |
| 243 | * Ret: First/last node in tree, or NULL if tree is empty. |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 244 | * |
| 245 | * static ex_node_t * |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 246 | * ex_next(ex_t *tree, ex_node_t *node); |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 247 | * static ex_node_t * |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 248 | * ex_prev(ex_t *tree, ex_node_t *node); |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 249 | * Description: Get node's successor/predecessor. |
| 250 | * Args: |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 251 | * tree: Pointer to an initialized red-black tree object. |
| 252 | * node: A node in tree. |
| 253 | * Ret: node's successor/predecessor in tree, or NULL if node is |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 254 | * last/first. |
| 255 | * |
| 256 | * static ex_node_t * |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 257 | * ex_search(ex_t *tree, ex_node_t *key); |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 258 | * Description: Search for node that matches key. |
| 259 | * Args: |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 260 | * tree: Pointer to an initialized red-black tree object. |
| 261 | * key : Search key. |
| 262 | * Ret: Node in tree that matches key, or NULL if no match. |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 263 | * |
| 264 | * static ex_node_t * |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 265 | * ex_nsearch(ex_t *tree, ex_node_t *key); |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 266 | * static ex_node_t * |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 267 | * ex_psearch(ex_t *tree, ex_node_t *key); |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 268 | * Description: Search for node that matches key. If no match is found, |
| 269 | * return what would be key's successor/predecessor, were |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 270 | * key in tree. |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 271 | * Args: |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 272 | * tree: Pointer to an initialized red-black tree object. |
| 273 | * key : Search key. |
| 274 | * Ret: Node in tree that matches key, or if no match, hypothetical node's |
| 275 | * successor/predecessor (NULL if no successor/predecessor). |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 276 | * |
| 277 | * static void |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 278 | * ex_insert(ex_t *tree, ex_node_t *node); |
| 279 | * Description: Insert node into tree. |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 280 | * Args: |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 281 | * tree: Pointer to an initialized red-black tree object. |
| 282 | * node: Node to be inserted into tree. |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 283 | * |
| 284 | * static void |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 285 | * ex_remove(ex_t *tree, ex_node_t *node); |
| 286 | * Description: Remove node from tree. |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 287 | * Args: |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 288 | * tree: Pointer to an initialized red-black tree object. |
| 289 | * node: Node in tree to be removed. |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 290 | * |
| 291 | * static ex_node_t * |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 292 | * ex_iter(ex_t *tree, ex_node_t *start, ex_node_t *(*cb)(ex_t *, |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 293 | * ex_node_t *, void *), void *arg); |
| 294 | * static ex_node_t * |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 295 | * ex_reverse_iter(ex_t *tree, ex_node_t *start, ex_node *(*cb)(ex_t *, |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 296 | * ex_node_t *, void *), void *arg); |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 297 | * Description: Iterate forward/backward over tree, starting at node. If |
| 298 | * tree is modified, iteration must be immediately |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 299 | * terminated by the callback function that causes the |
| 300 | * modification. |
| 301 | * Args: |
Jason Evans | da9dde0 | 2011-11-01 20:48:31 -0700 | [diff] [blame] | 302 | * tree : Pointer to an initialized red-black tree object. |
| 303 | * start: Node at which to start iteration, or NULL to start at |
| 304 | * first/last node. |
| 305 | * cb : Callback function, which is called for each node during |
| 306 | * iteration. Under normal circumstances the callback function |
| 307 | * should return NULL, which causes iteration to continue. If a |
| 308 | * callback function returns non-NULL, iteration is immediately |
| 309 | * terminated and the non-NULL return value is returned by the |
| 310 | * iterator. This is useful for re-starting iteration after |
| 311 | * modifying tree. |
| 312 | * arg : Opaque pointer passed to cb(). |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 313 | * Ret: NULL if iteration completed, or the non-NULL callback return value |
| 314 | * that caused termination of the iteration. |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 315 | */ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 316 | #define rb_gen(a_attr, a_prefix, a_rbt_type, a_type, a_field, a_cmp) \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 317 | a_attr void \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 318 | a_prefix##new(a_rbt_type *rbtree) { \ |
| 319 | rb_new(a_type, a_field, rbtree); \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 320 | } \ |
Jason Evans | 1628e86 | 2014-08-19 01:28:49 -0700 | [diff] [blame] | 321 | a_attr bool \ |
| 322 | a_prefix##empty(a_rbt_type *rbtree) { \ |
| 323 | return (rbtree->rbt_root == &rbtree->rbt_nil); \ |
| 324 | } \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 325 | a_attr a_type * \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 326 | a_prefix##first(a_rbt_type *rbtree) { \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 327 | a_type *ret; \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 328 | rbtn_first(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ |
| 329 | if (ret == &rbtree->rbt_nil) { \ |
| 330 | ret = NULL; \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 331 | } \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 332 | return (ret); \ |
| 333 | } \ |
| 334 | a_attr a_type * \ |
| 335 | a_prefix##last(a_rbt_type *rbtree) { \ |
| 336 | a_type *ret; \ |
| 337 | rbtn_last(a_type, a_field, rbtree, rbtree->rbt_root, ret); \ |
| 338 | if (ret == &rbtree->rbt_nil) { \ |
| 339 | ret = NULL; \ |
| 340 | } \ |
| 341 | return (ret); \ |
| 342 | } \ |
| 343 | a_attr a_type * \ |
| 344 | a_prefix##next(a_rbt_type *rbtree, a_type *node) { \ |
| 345 | a_type *ret; \ |
| 346 | if (rbtn_right_get(a_type, a_field, node) != &rbtree->rbt_nil) { \ |
| 347 | rbtn_first(a_type, a_field, rbtree, rbtn_right_get(a_type, \ |
| 348 | a_field, node), ret); \ |
| 349 | } else { \ |
| 350 | a_type *tnode = rbtree->rbt_root; \ |
| 351 | assert(tnode != &rbtree->rbt_nil); \ |
| 352 | ret = &rbtree->rbt_nil; \ |
| 353 | while (true) { \ |
| 354 | int cmp = (a_cmp)(node, tnode); \ |
| 355 | if (cmp < 0) { \ |
| 356 | ret = tnode; \ |
| 357 | tnode = rbtn_left_get(a_type, a_field, tnode); \ |
| 358 | } else if (cmp > 0) { \ |
| 359 | tnode = rbtn_right_get(a_type, a_field, tnode); \ |
| 360 | } else { \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 361 | break; \ |
| 362 | } \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 363 | assert(tnode != &rbtree->rbt_nil); \ |
| 364 | } \ |
| 365 | } \ |
| 366 | if (ret == &rbtree->rbt_nil) { \ |
| 367 | ret = (NULL); \ |
| 368 | } \ |
| 369 | return (ret); \ |
| 370 | } \ |
| 371 | a_attr a_type * \ |
| 372 | a_prefix##prev(a_rbt_type *rbtree, a_type *node) { \ |
| 373 | a_type *ret; \ |
| 374 | if (rbtn_left_get(a_type, a_field, node) != &rbtree->rbt_nil) { \ |
| 375 | rbtn_last(a_type, a_field, rbtree, rbtn_left_get(a_type, \ |
| 376 | a_field, node), ret); \ |
| 377 | } else { \ |
| 378 | a_type *tnode = rbtree->rbt_root; \ |
| 379 | assert(tnode != &rbtree->rbt_nil); \ |
| 380 | ret = &rbtree->rbt_nil; \ |
| 381 | while (true) { \ |
| 382 | int cmp = (a_cmp)(node, tnode); \ |
| 383 | if (cmp < 0) { \ |
| 384 | tnode = rbtn_left_get(a_type, a_field, tnode); \ |
| 385 | } else if (cmp > 0) { \ |
| 386 | ret = tnode; \ |
| 387 | tnode = rbtn_right_get(a_type, a_field, tnode); \ |
| 388 | } else { \ |
| 389 | break; \ |
| 390 | } \ |
| 391 | assert(tnode != &rbtree->rbt_nil); \ |
| 392 | } \ |
| 393 | } \ |
| 394 | if (ret == &rbtree->rbt_nil) { \ |
| 395 | ret = (NULL); \ |
| 396 | } \ |
| 397 | return (ret); \ |
| 398 | } \ |
| 399 | a_attr a_type * \ |
| 400 | a_prefix##search(a_rbt_type *rbtree, a_type *key) { \ |
| 401 | a_type *ret; \ |
| 402 | int cmp; \ |
| 403 | ret = rbtree->rbt_root; \ |
| 404 | while (ret != &rbtree->rbt_nil \ |
| 405 | && (cmp = (a_cmp)(key, ret)) != 0) { \ |
| 406 | if (cmp < 0) { \ |
| 407 | ret = rbtn_left_get(a_type, a_field, ret); \ |
| 408 | } else { \ |
| 409 | ret = rbtn_right_get(a_type, a_field, ret); \ |
| 410 | } \ |
| 411 | } \ |
| 412 | if (ret == &rbtree->rbt_nil) { \ |
| 413 | ret = (NULL); \ |
| 414 | } \ |
| 415 | return (ret); \ |
| 416 | } \ |
| 417 | a_attr a_type * \ |
| 418 | a_prefix##nsearch(a_rbt_type *rbtree, a_type *key) { \ |
| 419 | a_type *ret; \ |
| 420 | a_type *tnode = rbtree->rbt_root; \ |
| 421 | ret = &rbtree->rbt_nil; \ |
| 422 | while (tnode != &rbtree->rbt_nil) { \ |
| 423 | int cmp = (a_cmp)(key, tnode); \ |
| 424 | if (cmp < 0) { \ |
| 425 | ret = tnode; \ |
| 426 | tnode = rbtn_left_get(a_type, a_field, tnode); \ |
| 427 | } else if (cmp > 0) { \ |
| 428 | tnode = rbtn_right_get(a_type, a_field, tnode); \ |
| 429 | } else { \ |
| 430 | ret = tnode; \ |
| 431 | break; \ |
| 432 | } \ |
| 433 | } \ |
| 434 | if (ret == &rbtree->rbt_nil) { \ |
| 435 | ret = (NULL); \ |
| 436 | } \ |
| 437 | return (ret); \ |
| 438 | } \ |
| 439 | a_attr a_type * \ |
| 440 | a_prefix##psearch(a_rbt_type *rbtree, a_type *key) { \ |
| 441 | a_type *ret; \ |
| 442 | a_type *tnode = rbtree->rbt_root; \ |
| 443 | ret = &rbtree->rbt_nil; \ |
| 444 | while (tnode != &rbtree->rbt_nil) { \ |
| 445 | int cmp = (a_cmp)(key, tnode); \ |
| 446 | if (cmp < 0) { \ |
| 447 | tnode = rbtn_left_get(a_type, a_field, tnode); \ |
| 448 | } else if (cmp > 0) { \ |
| 449 | ret = tnode; \ |
| 450 | tnode = rbtn_right_get(a_type, a_field, tnode); \ |
| 451 | } else { \ |
| 452 | ret = tnode; \ |
| 453 | break; \ |
| 454 | } \ |
| 455 | } \ |
| 456 | if (ret == &rbtree->rbt_nil) { \ |
| 457 | ret = (NULL); \ |
| 458 | } \ |
| 459 | return (ret); \ |
| 460 | } \ |
| 461 | a_attr void \ |
| 462 | a_prefix##insert(a_rbt_type *rbtree, a_type *node) { \ |
| 463 | struct { \ |
| 464 | a_type *node; \ |
| 465 | int cmp; \ |
| 466 | } path[sizeof(void *) << 4], *pathp; \ |
| 467 | rbt_node_new(a_type, a_field, rbtree, node); \ |
| 468 | /* Wind. */ \ |
| 469 | path->node = rbtree->rbt_root; \ |
| 470 | for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \ |
| 471 | int cmp = pathp->cmp = a_cmp(node, pathp->node); \ |
| 472 | assert(cmp != 0); \ |
| 473 | if (cmp < 0) { \ |
| 474 | pathp[1].node = rbtn_left_get(a_type, a_field, \ |
| 475 | pathp->node); \ |
| 476 | } else { \ |
| 477 | pathp[1].node = rbtn_right_get(a_type, a_field, \ |
| 478 | pathp->node); \ |
| 479 | } \ |
| 480 | } \ |
| 481 | pathp->node = node; \ |
| 482 | /* Unwind. */ \ |
| 483 | for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ |
| 484 | a_type *cnode = pathp->node; \ |
| 485 | if (pathp->cmp < 0) { \ |
| 486 | a_type *left = pathp[1].node; \ |
| 487 | rbtn_left_set(a_type, a_field, cnode, left); \ |
| 488 | if (rbtn_red_get(a_type, a_field, left)) { \ |
| 489 | a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ |
| 490 | if (rbtn_red_get(a_type, a_field, leftleft)) { \ |
| 491 | /* Fix up 4-node. */ \ |
| 492 | a_type *tnode; \ |
| 493 | rbtn_black_set(a_type, a_field, leftleft); \ |
| 494 | rbtn_rotate_right(a_type, a_field, cnode, tnode); \ |
| 495 | cnode = tnode; \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 496 | } \ |
| 497 | } else { \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 498 | return; \ |
| 499 | } \ |
| 500 | } else { \ |
| 501 | a_type *right = pathp[1].node; \ |
| 502 | rbtn_right_set(a_type, a_field, cnode, right); \ |
| 503 | if (rbtn_red_get(a_type, a_field, right)) { \ |
| 504 | a_type *left = rbtn_left_get(a_type, a_field, cnode); \ |
| 505 | if (rbtn_red_get(a_type, a_field, left)) { \ |
| 506 | /* Split 4-node. */ \ |
| 507 | rbtn_black_set(a_type, a_field, left); \ |
| 508 | rbtn_black_set(a_type, a_field, right); \ |
| 509 | rbtn_red_set(a_type, a_field, cnode); \ |
| 510 | } else { \ |
| 511 | /* Lean left. */ \ |
| 512 | a_type *tnode; \ |
| 513 | bool tred = rbtn_red_get(a_type, a_field, cnode); \ |
| 514 | rbtn_rotate_left(a_type, a_field, cnode, tnode); \ |
| 515 | rbtn_color_set(a_type, a_field, tnode, tred); \ |
| 516 | rbtn_red_set(a_type, a_field, cnode); \ |
| 517 | cnode = tnode; \ |
| 518 | } \ |
| 519 | } else { \ |
| 520 | return; \ |
| 521 | } \ |
| 522 | } \ |
| 523 | pathp->node = cnode; \ |
| 524 | } \ |
| 525 | /* Set root, and make it black. */ \ |
| 526 | rbtree->rbt_root = path->node; \ |
| 527 | rbtn_black_set(a_type, a_field, rbtree->rbt_root); \ |
| 528 | } \ |
| 529 | a_attr void \ |
| 530 | a_prefix##remove(a_rbt_type *rbtree, a_type *node) { \ |
| 531 | struct { \ |
| 532 | a_type *node; \ |
| 533 | int cmp; \ |
| 534 | } *pathp, *nodep, path[sizeof(void *) << 4]; \ |
| 535 | /* Wind. */ \ |
| 536 | nodep = NULL; /* Silence compiler warning. */ \ |
| 537 | path->node = rbtree->rbt_root; \ |
| 538 | for (pathp = path; pathp->node != &rbtree->rbt_nil; pathp++) { \ |
| 539 | int cmp = pathp->cmp = a_cmp(node, pathp->node); \ |
| 540 | if (cmp < 0) { \ |
| 541 | pathp[1].node = rbtn_left_get(a_type, a_field, \ |
| 542 | pathp->node); \ |
| 543 | } else { \ |
| 544 | pathp[1].node = rbtn_right_get(a_type, a_field, \ |
| 545 | pathp->node); \ |
| 546 | if (cmp == 0) { \ |
| 547 | /* Find node's successor, in preparation for swap. */ \ |
| 548 | pathp->cmp = 1; \ |
| 549 | nodep = pathp; \ |
| 550 | for (pathp++; pathp->node != &rbtree->rbt_nil; \ |
| 551 | pathp++) { \ |
| 552 | pathp->cmp = -1; \ |
| 553 | pathp[1].node = rbtn_left_get(a_type, a_field, \ |
| 554 | pathp->node); \ |
| 555 | } \ |
| 556 | break; \ |
| 557 | } \ |
| 558 | } \ |
| 559 | } \ |
| 560 | assert(nodep->node == node); \ |
| 561 | pathp--; \ |
| 562 | if (pathp->node != node) { \ |
| 563 | /* Swap node with its successor. */ \ |
| 564 | bool tred = rbtn_red_get(a_type, a_field, pathp->node); \ |
| 565 | rbtn_color_set(a_type, a_field, pathp->node, \ |
| 566 | rbtn_red_get(a_type, a_field, node)); \ |
| 567 | rbtn_left_set(a_type, a_field, pathp->node, \ |
| 568 | rbtn_left_get(a_type, a_field, node)); \ |
| 569 | /* If node's successor is its right child, the following code */\ |
| 570 | /* will do the wrong thing for the right child pointer. */\ |
| 571 | /* However, it doesn't matter, because the pointer will be */\ |
| 572 | /* properly set when the successor is pruned. */\ |
| 573 | rbtn_right_set(a_type, a_field, pathp->node, \ |
| 574 | rbtn_right_get(a_type, a_field, node)); \ |
| 575 | rbtn_color_set(a_type, a_field, node, tred); \ |
| 576 | /* The pruned leaf node's child pointers are never accessed */\ |
| 577 | /* again, so don't bother setting them to nil. */\ |
| 578 | nodep->node = pathp->node; \ |
| 579 | pathp->node = node; \ |
| 580 | if (nodep == path) { \ |
| 581 | rbtree->rbt_root = nodep->node; \ |
| 582 | } else { \ |
| 583 | if (nodep[-1].cmp < 0) { \ |
| 584 | rbtn_left_set(a_type, a_field, nodep[-1].node, \ |
| 585 | nodep->node); \ |
| 586 | } else { \ |
| 587 | rbtn_right_set(a_type, a_field, nodep[-1].node, \ |
| 588 | nodep->node); \ |
| 589 | } \ |
| 590 | } \ |
| 591 | } else { \ |
| 592 | a_type *left = rbtn_left_get(a_type, a_field, node); \ |
| 593 | if (left != &rbtree->rbt_nil) { \ |
| 594 | /* node has no successor, but it has a left child. */\ |
| 595 | /* Splice node out, without losing the left child. */\ |
Jason Evans | 551ebc4 | 2014-10-03 10:16:09 -0700 | [diff] [blame] | 596 | assert(!rbtn_red_get(a_type, a_field, node)); \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 597 | assert(rbtn_red_get(a_type, a_field, left)); \ |
| 598 | rbtn_black_set(a_type, a_field, left); \ |
| 599 | if (pathp == path) { \ |
| 600 | rbtree->rbt_root = left; \ |
| 601 | } else { \ |
| 602 | if (pathp[-1].cmp < 0) { \ |
| 603 | rbtn_left_set(a_type, a_field, pathp[-1].node, \ |
| 604 | left); \ |
| 605 | } else { \ |
| 606 | rbtn_right_set(a_type, a_field, pathp[-1].node, \ |
| 607 | left); \ |
| 608 | } \ |
| 609 | } \ |
| 610 | return; \ |
| 611 | } else if (pathp == path) { \ |
| 612 | /* The tree only contained one node. */ \ |
| 613 | rbtree->rbt_root = &rbtree->rbt_nil; \ |
| 614 | return; \ |
| 615 | } \ |
| 616 | } \ |
| 617 | if (rbtn_red_get(a_type, a_field, pathp->node)) { \ |
| 618 | /* Prune red node, which requires no fixup. */ \ |
| 619 | assert(pathp[-1].cmp < 0); \ |
| 620 | rbtn_left_set(a_type, a_field, pathp[-1].node, \ |
| 621 | &rbtree->rbt_nil); \ |
| 622 | return; \ |
| 623 | } \ |
| 624 | /* The node to be pruned is black, so unwind until balance is */\ |
| 625 | /* restored. */\ |
| 626 | pathp->node = &rbtree->rbt_nil; \ |
| 627 | for (pathp--; (uintptr_t)pathp >= (uintptr_t)path; pathp--) { \ |
| 628 | assert(pathp->cmp != 0); \ |
| 629 | if (pathp->cmp < 0) { \ |
| 630 | rbtn_left_set(a_type, a_field, pathp->node, \ |
| 631 | pathp[1].node); \ |
Jason Evans | 551ebc4 | 2014-10-03 10:16:09 -0700 | [diff] [blame] | 632 | assert(!rbtn_red_get(a_type, a_field, pathp[1].node)); \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 633 | if (rbtn_red_get(a_type, a_field, pathp->node)) { \ |
| 634 | a_type *right = rbtn_right_get(a_type, a_field, \ |
| 635 | pathp->node); \ |
| 636 | a_type *rightleft = rbtn_left_get(a_type, a_field, \ |
| 637 | right); \ |
| 638 | a_type *tnode; \ |
| 639 | if (rbtn_red_get(a_type, a_field, rightleft)) { \ |
| 640 | /* In the following diagrams, ||, //, and \\ */\ |
| 641 | /* indicate the path to the removed node. */\ |
| 642 | /* */\ |
| 643 | /* || */\ |
| 644 | /* pathp(r) */\ |
| 645 | /* // \ */\ |
| 646 | /* (b) (b) */\ |
| 647 | /* / */\ |
| 648 | /* (r) */\ |
| 649 | /* */\ |
| 650 | rbtn_black_set(a_type, a_field, pathp->node); \ |
| 651 | rbtn_rotate_right(a_type, a_field, right, tnode); \ |
| 652 | rbtn_right_set(a_type, a_field, pathp->node, tnode);\ |
| 653 | rbtn_rotate_left(a_type, a_field, pathp->node, \ |
| 654 | tnode); \ |
| 655 | } else { \ |
| 656 | /* || */\ |
| 657 | /* pathp(r) */\ |
| 658 | /* // \ */\ |
| 659 | /* (b) (b) */\ |
| 660 | /* / */\ |
| 661 | /* (b) */\ |
| 662 | /* */\ |
| 663 | rbtn_rotate_left(a_type, a_field, pathp->node, \ |
| 664 | tnode); \ |
| 665 | } \ |
| 666 | /* Balance restored, but rotation modified subtree */\ |
| 667 | /* root. */\ |
| 668 | assert((uintptr_t)pathp > (uintptr_t)path); \ |
| 669 | if (pathp[-1].cmp < 0) { \ |
| 670 | rbtn_left_set(a_type, a_field, pathp[-1].node, \ |
| 671 | tnode); \ |
| 672 | } else { \ |
| 673 | rbtn_right_set(a_type, a_field, pathp[-1].node, \ |
| 674 | tnode); \ |
| 675 | } \ |
| 676 | return; \ |
| 677 | } else { \ |
| 678 | a_type *right = rbtn_right_get(a_type, a_field, \ |
| 679 | pathp->node); \ |
| 680 | a_type *rightleft = rbtn_left_get(a_type, a_field, \ |
| 681 | right); \ |
| 682 | if (rbtn_red_get(a_type, a_field, rightleft)) { \ |
| 683 | /* || */\ |
| 684 | /* pathp(b) */\ |
| 685 | /* // \ */\ |
| 686 | /* (b) (b) */\ |
| 687 | /* / */\ |
| 688 | /* (r) */\ |
| 689 | a_type *tnode; \ |
| 690 | rbtn_black_set(a_type, a_field, rightleft); \ |
| 691 | rbtn_rotate_right(a_type, a_field, right, tnode); \ |
| 692 | rbtn_right_set(a_type, a_field, pathp->node, tnode);\ |
| 693 | rbtn_rotate_left(a_type, a_field, pathp->node, \ |
| 694 | tnode); \ |
| 695 | /* Balance restored, but rotation modified */\ |
| 696 | /* subree root, which may actually be the tree */\ |
| 697 | /* root. */\ |
| 698 | if (pathp == path) { \ |
| 699 | /* Set root. */ \ |
| 700 | rbtree->rbt_root = tnode; \ |
| 701 | } else { \ |
| 702 | if (pathp[-1].cmp < 0) { \ |
| 703 | rbtn_left_set(a_type, a_field, \ |
| 704 | pathp[-1].node, tnode); \ |
| 705 | } else { \ |
| 706 | rbtn_right_set(a_type, a_field, \ |
| 707 | pathp[-1].node, tnode); \ |
| 708 | } \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 709 | } \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 710 | return; \ |
| 711 | } else { \ |
| 712 | /* || */\ |
| 713 | /* pathp(b) */\ |
| 714 | /* // \ */\ |
| 715 | /* (b) (b) */\ |
| 716 | /* / */\ |
| 717 | /* (b) */\ |
| 718 | a_type *tnode; \ |
| 719 | rbtn_red_set(a_type, a_field, pathp->node); \ |
| 720 | rbtn_rotate_left(a_type, a_field, pathp->node, \ |
| 721 | tnode); \ |
| 722 | pathp->node = tnode; \ |
| 723 | } \ |
| 724 | } \ |
| 725 | } else { \ |
| 726 | a_type *left; \ |
| 727 | rbtn_right_set(a_type, a_field, pathp->node, \ |
| 728 | pathp[1].node); \ |
| 729 | left = rbtn_left_get(a_type, a_field, pathp->node); \ |
| 730 | if (rbtn_red_get(a_type, a_field, left)) { \ |
| 731 | a_type *tnode; \ |
| 732 | a_type *leftright = rbtn_right_get(a_type, a_field, \ |
| 733 | left); \ |
| 734 | a_type *leftrightleft = rbtn_left_get(a_type, a_field, \ |
| 735 | leftright); \ |
| 736 | if (rbtn_red_get(a_type, a_field, leftrightleft)) { \ |
| 737 | /* || */\ |
| 738 | /* pathp(b) */\ |
| 739 | /* / \\ */\ |
| 740 | /* (r) (b) */\ |
| 741 | /* \ */\ |
| 742 | /* (b) */\ |
| 743 | /* / */\ |
| 744 | /* (r) */\ |
| 745 | a_type *unode; \ |
| 746 | rbtn_black_set(a_type, a_field, leftrightleft); \ |
| 747 | rbtn_rotate_right(a_type, a_field, pathp->node, \ |
| 748 | unode); \ |
| 749 | rbtn_rotate_right(a_type, a_field, pathp->node, \ |
| 750 | tnode); \ |
| 751 | rbtn_right_set(a_type, a_field, unode, tnode); \ |
| 752 | rbtn_rotate_left(a_type, a_field, unode, tnode); \ |
| 753 | } else { \ |
| 754 | /* || */\ |
| 755 | /* pathp(b) */\ |
| 756 | /* / \\ */\ |
| 757 | /* (r) (b) */\ |
| 758 | /* \ */\ |
| 759 | /* (b) */\ |
| 760 | /* / */\ |
| 761 | /* (b) */\ |
| 762 | assert(leftright != &rbtree->rbt_nil); \ |
| 763 | rbtn_red_set(a_type, a_field, leftright); \ |
| 764 | rbtn_rotate_right(a_type, a_field, pathp->node, \ |
| 765 | tnode); \ |
| 766 | rbtn_black_set(a_type, a_field, tnode); \ |
| 767 | } \ |
| 768 | /* Balance restored, but rotation modified subtree */\ |
| 769 | /* root, which may actually be the tree root. */\ |
| 770 | if (pathp == path) { \ |
| 771 | /* Set root. */ \ |
| 772 | rbtree->rbt_root = tnode; \ |
| 773 | } else { \ |
| 774 | if (pathp[-1].cmp < 0) { \ |
| 775 | rbtn_left_set(a_type, a_field, pathp[-1].node, \ |
| 776 | tnode); \ |
| 777 | } else { \ |
| 778 | rbtn_right_set(a_type, a_field, pathp[-1].node, \ |
| 779 | tnode); \ |
| 780 | } \ |
| 781 | } \ |
| 782 | return; \ |
| 783 | } else if (rbtn_red_get(a_type, a_field, pathp->node)) { \ |
| 784 | a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ |
| 785 | if (rbtn_red_get(a_type, a_field, leftleft)) { \ |
| 786 | /* || */\ |
| 787 | /* pathp(r) */\ |
| 788 | /* / \\ */\ |
| 789 | /* (b) (b) */\ |
| 790 | /* / */\ |
| 791 | /* (r) */\ |
| 792 | a_type *tnode; \ |
| 793 | rbtn_black_set(a_type, a_field, pathp->node); \ |
| 794 | rbtn_red_set(a_type, a_field, left); \ |
| 795 | rbtn_black_set(a_type, a_field, leftleft); \ |
| 796 | rbtn_rotate_right(a_type, a_field, pathp->node, \ |
| 797 | tnode); \ |
| 798 | /* Balance restored, but rotation modified */\ |
| 799 | /* subtree root. */\ |
| 800 | assert((uintptr_t)pathp > (uintptr_t)path); \ |
| 801 | if (pathp[-1].cmp < 0) { \ |
| 802 | rbtn_left_set(a_type, a_field, pathp[-1].node, \ |
| 803 | tnode); \ |
| 804 | } else { \ |
| 805 | rbtn_right_set(a_type, a_field, pathp[-1].node, \ |
| 806 | tnode); \ |
| 807 | } \ |
| 808 | return; \ |
| 809 | } else { \ |
| 810 | /* || */\ |
| 811 | /* pathp(r) */\ |
| 812 | /* / \\ */\ |
| 813 | /* (b) (b) */\ |
| 814 | /* / */\ |
| 815 | /* (b) */\ |
| 816 | rbtn_red_set(a_type, a_field, left); \ |
| 817 | rbtn_black_set(a_type, a_field, pathp->node); \ |
| 818 | /* Balance restored. */ \ |
| 819 | return; \ |
| 820 | } \ |
| 821 | } else { \ |
| 822 | a_type *leftleft = rbtn_left_get(a_type, a_field, left);\ |
| 823 | if (rbtn_red_get(a_type, a_field, leftleft)) { \ |
| 824 | /* || */\ |
| 825 | /* pathp(b) */\ |
| 826 | /* / \\ */\ |
| 827 | /* (b) (b) */\ |
| 828 | /* / */\ |
| 829 | /* (r) */\ |
| 830 | a_type *tnode; \ |
| 831 | rbtn_black_set(a_type, a_field, leftleft); \ |
| 832 | rbtn_rotate_right(a_type, a_field, pathp->node, \ |
| 833 | tnode); \ |
| 834 | /* Balance restored, but rotation modified */\ |
| 835 | /* subtree root, which may actually be the tree */\ |
| 836 | /* root. */\ |
| 837 | if (pathp == path) { \ |
| 838 | /* Set root. */ \ |
| 839 | rbtree->rbt_root = tnode; \ |
| 840 | } else { \ |
| 841 | if (pathp[-1].cmp < 0) { \ |
| 842 | rbtn_left_set(a_type, a_field, \ |
| 843 | pathp[-1].node, tnode); \ |
| 844 | } else { \ |
| 845 | rbtn_right_set(a_type, a_field, \ |
| 846 | pathp[-1].node, tnode); \ |
| 847 | } \ |
| 848 | } \ |
| 849 | return; \ |
| 850 | } else { \ |
| 851 | /* || */\ |
| 852 | /* pathp(b) */\ |
| 853 | /* / \\ */\ |
| 854 | /* (b) (b) */\ |
| 855 | /* / */\ |
| 856 | /* (b) */\ |
| 857 | rbtn_red_set(a_type, a_field, left); \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 858 | } \ |
| 859 | } \ |
| 860 | } \ |
| 861 | } \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 862 | /* Set root. */ \ |
| 863 | rbtree->rbt_root = path->node; \ |
Jason Evans | 551ebc4 | 2014-10-03 10:16:09 -0700 | [diff] [blame] | 864 | assert(!rbtn_red_get(a_type, a_field, rbtree->rbt_root)); \ |
Jason Evans | f3ff752 | 2010-02-28 15:00:18 -0800 | [diff] [blame] | 865 | } \ |
| 866 | a_attr a_type * \ |
| 867 | a_prefix##iter_recurse(a_rbt_type *rbtree, a_type *node, \ |
| 868 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ |
| 869 | if (node == &rbtree->rbt_nil) { \ |
| 870 | return (&rbtree->rbt_nil); \ |
| 871 | } else { \ |
| 872 | a_type *ret; \ |
| 873 | if ((ret = a_prefix##iter_recurse(rbtree, rbtn_left_get(a_type, \ |
| 874 | a_field, node), cb, arg)) != &rbtree->rbt_nil \ |
| 875 | || (ret = cb(rbtree, node, arg)) != NULL) { \ |
| 876 | return (ret); \ |
| 877 | } \ |
| 878 | return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ |
| 879 | a_field, node), cb, arg)); \ |
| 880 | } \ |
| 881 | } \ |
| 882 | a_attr a_type * \ |
| 883 | a_prefix##iter_start(a_rbt_type *rbtree, a_type *start, a_type *node, \ |
| 884 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ |
| 885 | int cmp = a_cmp(start, node); \ |
| 886 | if (cmp < 0) { \ |
| 887 | a_type *ret; \ |
| 888 | if ((ret = a_prefix##iter_start(rbtree, start, \ |
| 889 | rbtn_left_get(a_type, a_field, node), cb, arg)) != \ |
| 890 | &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ |
| 891 | return (ret); \ |
| 892 | } \ |
| 893 | return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ |
| 894 | a_field, node), cb, arg)); \ |
| 895 | } else if (cmp > 0) { \ |
| 896 | return (a_prefix##iter_start(rbtree, start, \ |
| 897 | rbtn_right_get(a_type, a_field, node), cb, arg)); \ |
| 898 | } else { \ |
| 899 | a_type *ret; \ |
| 900 | if ((ret = cb(rbtree, node, arg)) != NULL) { \ |
| 901 | return (ret); \ |
| 902 | } \ |
| 903 | return (a_prefix##iter_recurse(rbtree, rbtn_right_get(a_type, \ |
| 904 | a_field, node), cb, arg)); \ |
| 905 | } \ |
| 906 | } \ |
| 907 | a_attr a_type * \ |
| 908 | a_prefix##iter(a_rbt_type *rbtree, a_type *start, a_type *(*cb)( \ |
| 909 | a_rbt_type *, a_type *, void *), void *arg) { \ |
| 910 | a_type *ret; \ |
| 911 | if (start != NULL) { \ |
| 912 | ret = a_prefix##iter_start(rbtree, start, rbtree->rbt_root, \ |
| 913 | cb, arg); \ |
| 914 | } else { \ |
| 915 | ret = a_prefix##iter_recurse(rbtree, rbtree->rbt_root, cb, arg);\ |
| 916 | } \ |
| 917 | if (ret == &rbtree->rbt_nil) { \ |
| 918 | ret = NULL; \ |
| 919 | } \ |
| 920 | return (ret); \ |
| 921 | } \ |
| 922 | a_attr a_type * \ |
| 923 | a_prefix##reverse_iter_recurse(a_rbt_type *rbtree, a_type *node, \ |
| 924 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ |
| 925 | if (node == &rbtree->rbt_nil) { \ |
| 926 | return (&rbtree->rbt_nil); \ |
| 927 | } else { \ |
| 928 | a_type *ret; \ |
| 929 | if ((ret = a_prefix##reverse_iter_recurse(rbtree, \ |
| 930 | rbtn_right_get(a_type, a_field, node), cb, arg)) != \ |
| 931 | &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ |
| 932 | return (ret); \ |
| 933 | } \ |
| 934 | return (a_prefix##reverse_iter_recurse(rbtree, \ |
| 935 | rbtn_left_get(a_type, a_field, node), cb, arg)); \ |
| 936 | } \ |
| 937 | } \ |
| 938 | a_attr a_type * \ |
| 939 | a_prefix##reverse_iter_start(a_rbt_type *rbtree, a_type *start, \ |
| 940 | a_type *node, a_type *(*cb)(a_rbt_type *, a_type *, void *), \ |
| 941 | void *arg) { \ |
| 942 | int cmp = a_cmp(start, node); \ |
| 943 | if (cmp > 0) { \ |
| 944 | a_type *ret; \ |
| 945 | if ((ret = a_prefix##reverse_iter_start(rbtree, start, \ |
| 946 | rbtn_right_get(a_type, a_field, node), cb, arg)) != \ |
| 947 | &rbtree->rbt_nil || (ret = cb(rbtree, node, arg)) != NULL) { \ |
| 948 | return (ret); \ |
| 949 | } \ |
| 950 | return (a_prefix##reverse_iter_recurse(rbtree, \ |
| 951 | rbtn_left_get(a_type, a_field, node), cb, arg)); \ |
| 952 | } else if (cmp < 0) { \ |
| 953 | return (a_prefix##reverse_iter_start(rbtree, start, \ |
| 954 | rbtn_left_get(a_type, a_field, node), cb, arg)); \ |
| 955 | } else { \ |
| 956 | a_type *ret; \ |
| 957 | if ((ret = cb(rbtree, node, arg)) != NULL) { \ |
| 958 | return (ret); \ |
| 959 | } \ |
| 960 | return (a_prefix##reverse_iter_recurse(rbtree, \ |
| 961 | rbtn_left_get(a_type, a_field, node), cb, arg)); \ |
| 962 | } \ |
| 963 | } \ |
| 964 | a_attr a_type * \ |
| 965 | a_prefix##reverse_iter(a_rbt_type *rbtree, a_type *start, \ |
| 966 | a_type *(*cb)(a_rbt_type *, a_type *, void *), void *arg) { \ |
| 967 | a_type *ret; \ |
| 968 | if (start != NULL) { \ |
| 969 | ret = a_prefix##reverse_iter_start(rbtree, start, \ |
| 970 | rbtree->rbt_root, cb, arg); \ |
| 971 | } else { \ |
| 972 | ret = a_prefix##reverse_iter_recurse(rbtree, rbtree->rbt_root, \ |
| 973 | cb, arg); \ |
| 974 | } \ |
| 975 | if (ret == &rbtree->rbt_nil) { \ |
| 976 | ret = NULL; \ |
| 977 | } \ |
| 978 | return (ret); \ |
Jason Evans | 289053c | 2009-06-22 12:08:42 -0700 | [diff] [blame] | 979 | } |
| 980 | |
| 981 | #endif /* RB_H_ */ |