vcs-svn/trp.h

   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                 } \
  40         } while (0)
  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); \
  49         } while (0)
  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); \
  58         } while (0)
  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); \
  75         } while (0)
  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)); \
  93         } while (0)
  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)); \
 101         } while (0)
 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; \
 139         while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \
 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; \
 152         while (~ret && (cmp = (a_cmp)(key, trpn_pointer(a_base, ret)))) { \
 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) { \
 166                 return ins_node; \
 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                 } \
 188                 return ret; \
 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) \
 207                                 return ~0; \
 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); \
 212                         return ret; \
 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); \
 217                 return ret; \
 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); \
 222                 return cur_node; \
 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); \
 227                 return cur_node; \
 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