Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 1 | /* |
| 2 | * C macro implementation of treaps. |
| 3 | * |
| 4 | * Usage: |
| 5 | * #include <stdint.h> |
| 6 | * #include "trp.h" |
| 7 | * trp_gen(...) |
| 8 | * |
| 9 | * Licensed under a two-clause BSD-style license. |
| 10 | * See LICENSE for details. |
| 11 | */ |
| 12 | |
| 13 | #ifndef TRP_H_ |
| 14 | #define TRP_H_ |
| 15 | |
| 16 | #define MAYBE_UNUSED __attribute__((__unused__)) |
| 17 | |
| 18 | /* Node structure. */ |
| 19 | struct trp_node { |
| 20 | uint32_t trpn_left; |
| 21 | uint32_t trpn_right; |
| 22 | }; |
| 23 | |
| 24 | /* Root structure. */ |
| 25 | struct trp_root { |
| 26 | uint32_t trp_root; |
| 27 | }; |
| 28 | |
| 29 | /* Pointer/Offset conversion. */ |
| 30 | #define trpn_pointer(a_base, a_offset) (a_base##_pointer(a_offset)) |
| 31 | #define trpn_offset(a_base, a_pointer) (a_base##_offset(a_pointer)) |
| 32 | #define trpn_modify(a_base, a_offset) \ |
| 33 | do { \ |
| 34 | if ((a_offset) < a_base##_pool.committed) { \ |
| 35 | uint32_t old_offset = (a_offset);\ |
| 36 | (a_offset) = a_base##_alloc(1); \ |
| 37 | *trpn_pointer(a_base, a_offset) = \ |
| 38 | *trpn_pointer(a_base, old_offset); \ |
| 39 | } \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 40 | } while (0) |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 41 | |
| 42 | /* Left accessors. */ |
| 43 | #define trp_left_get(a_base, a_field, a_node) \ |
| 44 | (trpn_pointer(a_base, a_node)->a_field.trpn_left) |
| 45 | #define trp_left_set(a_base, a_field, a_node, a_left) \ |
| 46 | do { \ |
| 47 | trpn_modify(a_base, a_node); \ |
| 48 | trp_left_get(a_base, a_field, a_node) = (a_left); \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 49 | } while (0) |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 50 | |
| 51 | /* Right accessors. */ |
| 52 | #define trp_right_get(a_base, a_field, a_node) \ |
| 53 | (trpn_pointer(a_base, a_node)->a_field.trpn_right) |
| 54 | #define trp_right_set(a_base, a_field, a_node, a_right) \ |
| 55 | do { \ |
| 56 | trpn_modify(a_base, a_node); \ |
| 57 | trp_right_get(a_base, a_field, a_node) = (a_right); \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 58 | } while (0) |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 59 | |
| 60 | /* |
| 61 | * Fibonacci hash function. |
| 62 | * The multiplier is the nearest prime to (2^32 times (√5 - 1)/2). |
| 63 | * See Knuth §6.4: volume 3, 3rd ed, p518. |
| 64 | */ |
| 65 | #define trpn_hash(a_node) (uint32_t) (2654435761u * (a_node)) |
| 66 | |
| 67 | /* Priority accessors. */ |
| 68 | #define trp_prio_get(a_node) trpn_hash(a_node) |
| 69 | |
| 70 | /* Node initializer. */ |
| 71 | #define trp_node_new(a_base, a_field, a_node) \ |
| 72 | do { \ |
| 73 | trp_left_set(a_base, a_field, (a_node), ~0); \ |
| 74 | trp_right_set(a_base, a_field, (a_node), ~0); \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 75 | } while (0) |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 76 | |
| 77 | /* Internal utility macros. */ |
| 78 | #define trpn_first(a_base, a_field, a_root, r_node) \ |
| 79 | do { \ |
| 80 | (r_node) = (a_root); \ |
| 81 | if ((r_node) == ~0) \ |
| 82 | return NULL; \ |
| 83 | while (~trp_left_get(a_base, a_field, (r_node))) \ |
| 84 | (r_node) = trp_left_get(a_base, a_field, (r_node)); \ |
| 85 | } while (0) |
| 86 | |
| 87 | #define trpn_rotate_left(a_base, a_field, a_node, r_node) \ |
| 88 | do { \ |
| 89 | (r_node) = trp_right_get(a_base, a_field, (a_node)); \ |
| 90 | trp_right_set(a_base, a_field, (a_node), \ |
| 91 | trp_left_get(a_base, a_field, (r_node))); \ |
| 92 | trp_left_set(a_base, a_field, (r_node), (a_node)); \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 93 | } while (0) |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 94 | |
| 95 | #define trpn_rotate_right(a_base, a_field, a_node, r_node) \ |
| 96 | do { \ |
| 97 | (r_node) = trp_left_get(a_base, a_field, (a_node)); \ |
| 98 | trp_left_set(a_base, a_field, (a_node), \ |
| 99 | trp_right_get(a_base, a_field, (r_node))); \ |
| 100 | trp_right_set(a_base, a_field, (r_node), (a_node)); \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 101 | } while (0) |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 102 | |
| 103 | #define trp_gen(a_attr, a_pre, a_type, a_field, a_base, a_cmp) \ |
| 104 | a_attr a_type MAYBE_UNUSED *a_pre##first(struct trp_root *treap) \ |
| 105 | { \ |
| 106 | uint32_t ret; \ |
| 107 | trpn_first(a_base, a_field, treap->trp_root, ret); \ |
| 108 | return trpn_pointer(a_base, ret); \ |
| 109 | } \ |
| 110 | a_attr a_type MAYBE_UNUSED *a_pre##next(struct trp_root *treap, a_type *node) \ |
| 111 | { \ |
| 112 | uint32_t ret; \ |
| 113 | uint32_t offset = trpn_offset(a_base, node); \ |
| 114 | if (~trp_right_get(a_base, a_field, offset)) { \ |
| 115 | trpn_first(a_base, a_field, \ |
| 116 | trp_right_get(a_base, a_field, offset), ret); \ |
| 117 | } else { \ |
| 118 | uint32_t tnode = treap->trp_root; \ |
| 119 | ret = ~0; \ |
| 120 | while (1) { \ |
| 121 | int cmp = (a_cmp)(trpn_pointer(a_base, offset), \ |
| 122 | trpn_pointer(a_base, tnode)); \ |
| 123 | if (cmp < 0) { \ |
| 124 | ret = tnode; \ |
| 125 | tnode = trp_left_get(a_base, a_field, tnode); \ |
| 126 | } else if (cmp > 0) { \ |
| 127 | tnode = trp_right_get(a_base, a_field, tnode); \ |
| 128 | } else { \ |
| 129 | break; \ |
| 130 | } \ |
| 131 | } \ |
| 132 | } \ |
| 133 | return trpn_pointer(a_base, ret); \ |
| 134 | } \ |
| 135 | a_attr a_type MAYBE_UNUSED *a_pre##search(struct trp_root *treap, a_type *key) \ |
| 136 | { \ |
| 137 | int cmp; \ |
| 138 | uint32_t ret = treap->trp_root; \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 139 | while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \ |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 140 | if (cmp < 0) { \ |
| 141 | ret = trp_left_get(a_base, a_field, ret); \ |
| 142 | } else { \ |
| 143 | ret = trp_right_get(a_base, a_field, ret); \ |
| 144 | } \ |
| 145 | } \ |
| 146 | return trpn_pointer(a_base, ret); \ |
| 147 | } \ |
| 148 | a_attr a_type MAYBE_UNUSED *a_pre##nsearch(struct trp_root *treap, a_type *key) \ |
| 149 | { \ |
| 150 | int cmp; \ |
| 151 | uint32_t ret = treap->trp_root; \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 152 | while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \ |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 153 | if (cmp < 0) { \ |
| 154 | if (!~trp_left_get(a_base, a_field, ret)) \ |
| 155 | break; \ |
| 156 | ret = trp_left_get(a_base, a_field, ret); \ |
| 157 | } else { \ |
| 158 | ret = trp_right_get(a_base, a_field, ret); \ |
| 159 | } \ |
| 160 | } \ |
| 161 | return trpn_pointer(a_base, ret); \ |
| 162 | } \ |
| 163 | a_attr uint32_t MAYBE_UNUSED a_pre##insert_recurse(uint32_t cur_node, uint32_t ins_node) \ |
| 164 | { \ |
| 165 | if (cur_node == ~0) { \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 166 | return ins_node; \ |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 167 | } else { \ |
| 168 | uint32_t ret; \ |
| 169 | int cmp = (a_cmp)(trpn_pointer(a_base, ins_node), \ |
| 170 | trpn_pointer(a_base, cur_node)); \ |
| 171 | if (cmp < 0) { \ |
| 172 | uint32_t left = a_pre##insert_recurse( \ |
| 173 | trp_left_get(a_base, a_field, cur_node), ins_node); \ |
| 174 | trp_left_set(a_base, a_field, cur_node, left); \ |
| 175 | if (trp_prio_get(left) < trp_prio_get(cur_node)) \ |
| 176 | trpn_rotate_right(a_base, a_field, cur_node, ret); \ |
| 177 | else \ |
| 178 | ret = cur_node; \ |
| 179 | } else { \ |
| 180 | uint32_t right = a_pre##insert_recurse( \ |
| 181 | trp_right_get(a_base, a_field, cur_node), ins_node); \ |
| 182 | trp_right_set(a_base, a_field, cur_node, right); \ |
| 183 | if (trp_prio_get(right) < trp_prio_get(cur_node)) \ |
| 184 | trpn_rotate_left(a_base, a_field, cur_node, ret); \ |
| 185 | else \ |
| 186 | ret = cur_node; \ |
| 187 | } \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 188 | return ret; \ |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 189 | } \ |
| 190 | } \ |
| 191 | a_attr void MAYBE_UNUSED a_pre##insert(struct trp_root *treap, a_type *node) \ |
| 192 | { \ |
| 193 | uint32_t offset = trpn_offset(a_base, node); \ |
| 194 | trp_node_new(a_base, a_field, offset); \ |
| 195 | treap->trp_root = a_pre##insert_recurse(treap->trp_root, offset); \ |
| 196 | } \ |
| 197 | a_attr uint32_t MAYBE_UNUSED a_pre##remove_recurse(uint32_t cur_node, uint32_t rem_node) \ |
| 198 | { \ |
| 199 | int cmp = a_cmp(trpn_pointer(a_base, rem_node), \ |
| 200 | trpn_pointer(a_base, cur_node)); \ |
| 201 | if (cmp == 0) { \ |
| 202 | uint32_t ret; \ |
| 203 | uint32_t left = trp_left_get(a_base, a_field, cur_node); \ |
| 204 | uint32_t right = trp_right_get(a_base, a_field, cur_node); \ |
| 205 | if (left == ~0) { \ |
| 206 | if (right == ~0) \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 207 | return ~0; \ |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 208 | } else if (right == ~0 || trp_prio_get(left) < trp_prio_get(right)) { \ |
| 209 | trpn_rotate_right(a_base, a_field, cur_node, ret); \ |
| 210 | right = a_pre##remove_recurse(cur_node, rem_node); \ |
| 211 | trp_right_set(a_base, a_field, ret, right); \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 212 | return ret; \ |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 213 | } \ |
| 214 | trpn_rotate_left(a_base, a_field, cur_node, ret); \ |
| 215 | left = a_pre##remove_recurse(cur_node, rem_node); \ |
| 216 | trp_left_set(a_base, a_field, ret, left); \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 217 | return ret; \ |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 218 | } else if (cmp < 0) { \ |
| 219 | uint32_t left = a_pre##remove_recurse( \ |
| 220 | trp_left_get(a_base, a_field, cur_node), rem_node); \ |
| 221 | trp_left_set(a_base, a_field, cur_node, left); \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 222 | return cur_node; \ |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 223 | } else { \ |
| 224 | uint32_t right = a_pre##remove_recurse( \ |
| 225 | trp_right_get(a_base, a_field, cur_node), rem_node); \ |
| 226 | trp_right_set(a_base, a_field, cur_node, right); \ |
Jonathan Nieder | 6ad263c | 2010-08-12 17:02:57 -0500 | [diff] [blame] | 227 | return cur_node; \ |
Jason Evans | 951f316 | 2010-08-09 17:17:34 -0500 | [diff] [blame] | 228 | } \ |
| 229 | } \ |
| 230 | a_attr void MAYBE_UNUSED a_pre##remove(struct trp_root *treap, a_type *node) \ |
| 231 | { \ |
| 232 | treap->trp_root = a_pre##remove_recurse(treap->trp_root, \ |
| 233 | trpn_offset(a_base, node)); \ |
| 234 | } \ |
| 235 | |
| 236 | #endif |