Merge branch 'jk/no-textconv-symlink' into maint
[git] / 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