| blob | 8566899c9a8d1da1d04a134c2e29297e9093e80d |
1 /******************************************************************************
2 *
3 * cpp macro implementation of treaps.
4 *
5 * Usage:
6 *
7 * #include <trp.h>
8 * trp(...)
9 * trp_gen(...)
10 * ...
11 *
12 ******************************************************************************/
14 #ifndef TRP_H_
15 #define TRP_H_
17 #include <stdint.h>
19 /* Node structure. */
20 #define trp_node(a_type) \
21 struct { \
22 uint32_t trpn_left; \
23 uint32_t trpn_right; \
24 }
26 /* Root structure. */
27 #define trp(a_type) \
28 struct { \
29 uint32_t trp_root; \
30 }
32 /* Pointer/Offset conversion */
33 #define trpn_pointer(a_base, a_offset) \
34 (a_base##_pointer(a_offset))
35 #define trpn_offset(a_base, a_pointer) \
36 (a_base##_offset(a_pointer))
38 /* Left accessors. */
39 #define trp_left_get(a_base, a_type, a_field, a_node) \
40 trpn_pointer(a_base, (a_node)->a_field.trpn_left)
41 #define trp_left_set(a_base, a_type, a_field, a_node, a_left) do { \
42 (a_node)->a_field.trpn_left = trpn_offset(a_base, a_left); \
43 } while (0)
45 /* Right accessors. */
46 #define trp_right_get(a_base, a_type, a_field, a_node) \
47 trpn_pointer(a_base, (a_node)->a_field.trpn_right)
48 #define trp_right_set(a_base, a_type, a_field, a_node, a_right) do { \
49 (a_node)->a_field.trpn_right = trpn_offset(a_base, a_right); \
50 } while (0)
52 /* Priority accessors. */
53 #define trp_prio_get(a_type, a_field, a_node) \
54 (2654435761u*(uint32_t)(uintptr_t)(a_node))
56 /* Node initializer. */
57 #define trp_node_new(a_base, a_type, a_field, a_trp, a_node) do { \
58 trp_left_set(a_base, a_type, a_field, (a_node), NULL); \
59 trp_right_set(a_base, a_type, a_field, (a_node), NULL); \
60 } while (0)
62 /* Tree initializer. */
63 #define trp_new(a_type, a_base, a_trp) do { \
64 (a_trp)->trp_root = trpn_offset(a_base, NULL); \
65 } while (0)
67 /* Internal utility macros. */
68 #define trpn_rotate_left(a_base, a_type, a_field, a_node, r_node) do { \
69 (r_node) = trp_right_get(a_base, a_type, a_field, (a_node)); \
70 trp_right_set(a_base, a_type, a_field, (a_node), \
71 trp_left_get(a_base, a_type, a_field, (r_node))); \
72 trp_left_set(a_base, a_type, a_field, (r_node), (a_node)); \
73 } while (0)
75 #define trpn_rotate_right(a_base, a_type, a_field, a_node, r_node) do { \
76 (r_node) = trp_left_get(a_base, a_type, a_field, (a_node)); \
77 trp_left_set(a_base, a_type, a_field, (a_node), \
78 trp_right_get(a_base, a_type, a_field, (r_node))); \
79 trp_right_set(a_base, a_type, a_field, (r_node), (a_node)); \
80 } while (0)
82 /*
83 * The trp_gen() macro generates a type-specific treap implementation,
84 * based on the above cpp macros.
85 *
86 * Arguments:
87 *
88 * a_attr : Function attribute for generated functions (ex: static).
89 * a_pre : Prefix for generated functions (ex: treap_).
90 * a_t_type : Type for treap data structure (ex: treap_t).
91 * a_type : Type for treap node data structure (ex: treap_node_t).
92 * a_field : Name of treap node linkage (ex: treap_link).
93 * a_base : Expression for the base pointer from which nodes are offset.
94 * a_cmp : Node comparison function name, with the following prototype:
95 * int (a_cmp *)(a_type *a_node, a_type *a_other);
96 * ^^^^^^
97 * or a_key
98 * Interpretation of comparision function return values:
99 * -1 : a_node < a_other
100 * 0 : a_node == a_other
101 * 1 : a_node > a_other
102 * In all cases, the a_node or a_key macro argument is the first
103 * argument to the comparison function, which makes it possible
104 * to write comparison functions that treat the first argument
105 * specially.
106 *
107 * Assuming the following setup:
108 *
109 * typedef struct ex_node_s ex_node_t;
110 * struct ex_node_s {
111 * trp_node(ex_node_t) ex_link;
112 * };
113 * typedef trp(ex_node_t) ex_t;
114 * static ex_node_t ex_base[MAX_NODES];
115 * trp_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_base, ex_cmp)
116 *
117 * The following API is generated:
118 *
119 * static void
120 * ex_new(ex_t *treap);
121 * Description: Initialize a treap structure.
122 * Args:
123 * treap: Pointer to an uninitialized treap object.
124 *
125 * static ex_node_t *
126 * ex_psearch(ex_t *treap, ex_node_t *key);
127 * Description: Search for node that matches key. If no match is found,
128 * return what would be key's successor/predecessor, were
129 * key in treap.
130 * Args:
131 * treap: Pointer to a initialized treap object.
132 * key : Search key.
133 * Ret: Node in treap that matches key, or if no match, hypothetical
134 * node's successor/predecessor (NULL if no successor/predecessor).
135 *
136 * static void
137 * ex_insert(ex_t *treap, ex_node_t *node);
138 * Description: Insert node into treap.
139 * Args:
140 * treap: Pointer to a initialized treap object.
141 * node : Node to be inserted into treap.
142 */
143 #define trp_gen(a_attr, a_pre, a_t_type, a_type, a_field, a_base, a_cmp)\
144 a_attr void \
145 a_pre##new(a_t_type *treap) { \
146 trp_new(a_type, a_base, treap); \
147 } \
148 a_attr a_type * \
149 a_pre##search(a_t_type *treap, a_type *key) { \
150 a_type *ret; \
151 int cmp; \
152 ret = trpn_pointer(a_base, treap->trp_root); \
153 while (ret != NULL \
154 && (cmp = (a_cmp)(key, ret)) != 0) { \
155 if (cmp < 0) { \
156 ret = trp_left_get(a_base, a_type, a_field, ret); \
157 } else { \
158 ret = trp_right_get(a_base, a_type, a_field, ret); \
159 } \
160 } \
161 return (ret); \
162 } \
163 a_attr a_type * \
164 a_pre##psearch(a_t_type *treap, a_type *key) { \
165 a_type *ret; \
166 a_type *tnode = trpn_pointer(a_base, treap->trp_root); \
167 ret = NULL; \
168 while (tnode != NULL) { \
169 int cmp = (a_cmp)(key, tnode); \
170 if (cmp < 0) { \
171 tnode = trp_left_get(a_base, a_type, a_field, tnode); \
172 } else if (cmp > 0) { \
173 ret = tnode; \
174 tnode = trp_right_get(a_base, a_type, a_field, tnode); \
175 } else { \
176 ret = tnode; \
177 break; \
178 } \
179 } \
180 return (ret); \
181 } \
182 a_attr a_type * \
183 a_pre##insert_recurse(a_type *cur_node, a_type *ins_node) { \
184 if (cur_node == NULL) { \
185 return (ins_node); \
186 } else { \
187 a_type *ret; \
188 int cmp = a_cmp(ins_node, cur_node); \
189 if (cmp < 0) { \
190 a_type *left = a_pre##insert_recurse(trp_left_get(a_base, \
191 a_type, a_field, cur_node), ins_node); \
192 trp_left_set(a_base, a_type, a_field, cur_node, left); \
193 if (trp_prio_get(a_type, a_field, left) < \
194 trp_prio_get(a_type, a_field, cur_node)) { \
195 trpn_rotate_right(a_base, a_type, a_field, cur_node, \
196 ret); \
197 } else { \
198 ret = cur_node; \
199 } \
200 } else { \
201 a_type *right = a_pre##insert_recurse(trp_right_get(a_base, \
202 a_type, a_field, cur_node), ins_node); \
203 trp_right_set(a_base, a_type, a_field, cur_node, right); \
204 if (trp_prio_get(a_type, a_field, right) < \
205 trp_prio_get(a_type, a_field, cur_node)) { \
206 trpn_rotate_left(a_base, a_type, a_field, cur_node, \
207 ret); \
208 } else { \
209 ret = cur_node; \
210 } \
211 } \
212 return (ret); \
213 } \
214 } \
215 a_attr void \
216 a_pre##insert(a_t_type *treap, a_type *node) { \
217 trp_node_new(a_base, a_type, a_field, treap, node); \
218 treap->trp_root = trpn_offset(a_base, a_pre##insert_recurse( \
219 trpn_pointer(a_base, treap->trp_root), node)); \
220 }