| blob | bcf1e336a48f8713a47087b44edf10b34f127dc5 |
1 /******************************************************************************
2 *
3 * Copyright (C) 2008 Jason Evans <jasone@canonware.com>.
4 * All rights reserved.
5 *
6 * Copyright (C) 2010 David Barr <david.barr@cordelta.com>.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice(s), this list of conditions and the following disclaimer
14 * unmodified other than the allowable addition of one or more
15 * copyright notices.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice(s), this list of conditions and the following disclaimer in
18 * the documentation and/or other materials provided with the
19 * distribution.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
22 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
28 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
29 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
30 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
31 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 *
33 ******************************************************************************
34 *
35 * cpp macro implementation of treaps.
36 *
37 * Usage:
38 *
39 * (Optional, see assert(3).)
40 * #define NDEBUG
41 *
42 * (Required.)
43 * #include <stdint.h> (For uint32_t.)
44 * #include <assert.h>
45 * #include <trp.h>
46 * trp(...)
47 * trp_gen(...)
48 * ...
49 *
50 ******************************************************************************/
52 #ifndef TRP_H_
53 #define TRP_H_
55 /* Node structure. */
56 #define trp_node(a_type) \
57 struct { \
58 uint32_t trpn_left; \
59 uint32_t trpn_right; \
60 }
62 /* Root structure. */
63 #define trp(a_type) \
64 struct { \
65 uint32_t trp_root; \
66 }
68 /* Pointer/Offset conversion */
69 #define trpn_pointer(a_base, a_offset) \
70 (a_base##_pointer(a_offset))
71 #define trpn_offset(a_base, a_pointer) \
72 (a_base##_offset(a_pointer))
74 /* Left accessors. */
75 #define trp_left_get(a_base, a_type, a_field, a_node) \
76 trpn_pointer(a_base, (a_node)->a_field.trpn_left)
77 #define trp_left_set(a_base, a_type, a_field, a_node, a_left) do { \
78 (a_node)->a_field.trpn_left = trpn_offset(a_base, a_left); \
79 } while (0)
81 /* Right accessors. */
82 #define trp_right_get(a_base, a_type, a_field, a_node) \
83 trpn_pointer(a_base, (a_node)->a_field.trpn_right)
84 #define trp_right_set(a_base, a_type, a_field, a_node, a_right) do { \
85 (a_node)->a_field.trpn_right = trpn_offset(a_base, a_right); \
86 } while (0)
88 /* Priority accessors. */
89 #define trp_prio_get(a_type, a_field, a_node) \
90 (2654435761*(uint32_t)(uintptr_t)(a_node))
92 /* Node initializer. */
93 #define trp_node_new(a_base, a_type, a_field, a_trp, a_node) do { \
94 trp_left_set(a_base, a_type, a_field, (a_node), NULL); \
95 trp_right_set(a_base, a_type, a_field, (a_node), NULL); \
96 } while (0)
98 /* Tree initializer. */
99 #define trp_new(a_type, a_base, a_trp) do { \
100 (a_trp)->trp_root = trpn_offset(a_base, NULL); \
101 } while (0)
103 /* Internal utility macros. */
104 #define trpn_rotate_left(a_base, a_type, a_field, a_node, r_node) do { \
105 (r_node) = trp_right_get(a_base, a_type, a_field, (a_node)); \
106 trp_right_set(a_base, a_type, a_field, (a_node), \
107 trp_left_get(a_base, a_type, a_field, (r_node))); \
108 trp_left_set(a_base, a_type, a_field, (r_node), (a_node)); \
109 } while (0)
111 #define trpn_rotate_right(a_base, a_type, a_field, a_node, r_node) do { \
112 (r_node) = trp_left_get(a_base, a_type, a_field, (a_node)); \
113 trp_left_set(a_base, a_type, a_field, (a_node), \
114 trp_right_get(a_base, a_type, a_field, (r_node))); \
115 trp_right_set(a_base, a_type, a_field, (r_node), (a_node)); \
116 } while (0)
118 /*
119 * The trp_gen() macro generates a type-specific treap implementation,
120 * based on the above cpp macros.
121 *
122 * Arguments:
123 *
124 * a_attr : Function attribute for generated functions (ex: static).
125 * a_pre : Prefix for generated functions (ex: treap_).
126 * a_t_type : Type for treap data structure (ex: treap_t).
127 * a_type : Type for treap node data structure (ex: treap_node_t).
128 * a_field : Name of treap node linkage (ex: treap_link).
129 * a_base : Expression for the base pointer from which nodes are offset.
130 * a_cmp : Node comparison function name, with the following prototype:
131 * int (a_cmp *)(a_type *a_node, a_type *a_other);
132 * ^^^^^^
133 * or a_key
134 * Interpretation of comparision function return values:
135 * -1 : a_node < a_other
136 * 0 : a_node == a_other
137 * 1 : a_node > a_other
138 * In all cases, the a_node or a_key macro argument is the first
139 * argument to the comparison function, which makes it possible
140 * to write comparison functions that treat the first argument
141 * specially.
142 *
143 * Assuming the following setup:
144 *
145 * typedef struct ex_node_s ex_node_t;
146 * struct ex_node_s {
147 * trp_node(ex_node_t) ex_link;
148 * };
149 * typedef trp(ex_node_t) ex_t;
150 * static ex_node_t ex_base[MAX_NODES];
151 * trp_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_base, ex_cmp)
152 *
153 * The following API is generated:
154 *
155 * static void
156 * ex_new(ex_t *treap);
157 * Description: Initialize a treap structure.
158 * Args:
159 * treap: Pointer to an uninitialized treap object.
160 *
161 * static ex_node_t *
162 * ex_psearch(ex_t *treap, ex_node_t *key);
163 * Description: Search for node that matches key. If no match is found,
164 * return what would be key's successor/predecessor, were
165 * key in treap.
166 * Args:
167 * treap: Pointer to a initialized treap object.
168 * key : Search key.
169 * Ret: Node in treap that matches key, or if no match, hypothetical
170 * node's successor/predecessor (NULL if no successor/predecessor).
171 *
172 * static void
173 * ex_insert(ex_t *treap, ex_node_t *node);
174 * Description: Insert node into treap.
175 * Args:
176 * treap: Pointer to a initialized treap object.
177 * node : Node to be inserted into treap.
178 */
179 #define trp_gen(a_attr, a_pre, a_t_type, a_type, a_field, a_base, a_cmp)\
180 a_attr void \
181 a_pre##new(a_t_type *treap) { \
182 trp_new(a_type, a_base, treap); \
183 } \
184 a_attr a_type * \
185 a_pre##search(a_t_type *treap, a_type *key) { \
186 a_type *ret; \
187 int cmp; \
188 ret = trpn_pointer(a_base, treap->trp_root); \
189 while (ret != NULL \
190 && (cmp = (a_cmp)(key, ret)) != 0) { \
191 if (cmp < 0) { \
192 ret = trp_left_get(a_base, a_type, a_field, ret); \
193 } else { \
194 ret = trp_right_get(a_base, a_type, a_field, ret); \
195 } \
196 } \
197 return (ret); \
198 } \
199 a_attr a_type * \
200 a_pre##psearch(a_t_type *treap, a_type *key) { \
201 a_type *ret; \
202 a_type *tnode = trpn_pointer(a_base, treap->trp_root); \
203 ret = NULL; \
204 while (tnode != NULL) { \
205 int cmp = (a_cmp)(key, tnode); \
206 if (cmp < 0) { \
207 tnode = trp_left_get(a_base, a_type, a_field, tnode); \
208 } else if (cmp > 0) { \
209 ret = tnode; \
210 tnode = trp_right_get(a_base, a_type, a_field, tnode); \
211 } else { \
212 ret = tnode; \
213 break; \
214 } \
215 } \
216 return (ret); \
217 } \
218 a_attr a_type * \
219 a_pre##insert_recurse(a_type *cur_node, a_type *ins_node) { \
220 if (cur_node == NULL) { \
221 return (ins_node); \
222 } else { \
223 a_type *ret; \
224 int cmp = a_cmp(ins_node, cur_node); \
225 assert(cmp != 0); \
226 if (cmp < 0) { \
227 a_type *left = a_pre##insert_recurse(trp_left_get(a_base, \
228 a_type, a_field, cur_node), ins_node); \
229 trp_left_set(a_base, a_type, a_field, cur_node, left); \
230 if (trp_prio_get(a_type, a_field, left) < \
231 trp_prio_get(a_type, a_field, cur_node)) { \
232 trpn_rotate_right(a_base, a_type, a_field, cur_node, \
233 ret); \
234 } else { \
235 ret = cur_node; \
236 } \
237 } else { \
238 a_type *right = a_pre##insert_recurse(trp_right_get(a_base, \
239 a_type, a_field, cur_node), ins_node); \
240 trp_right_set(a_base, a_type, a_field, cur_node, right); \
241 if (trp_prio_get(a_type, a_field, right) < \
242 trp_prio_get(a_type, a_field, cur_node)) { \
243 trpn_rotate_left(a_base, a_type, a_field, cur_node, \
244 ret); \
245 } else { \
246 ret = cur_node; \
247 } \
248 } \
249 return (ret); \
250 } \
251 } \
252 a_attr void \
253 a_pre##insert(a_t_type *treap, a_type *node) { \
254 trp_node_new(a_base, a_type, a_field, treap, node); \
255 treap->trp_root = trpn_offset(a_base, a_pre##insert_recurse( \
256 trpn_pointer(a_base, treap->trp_root), node)); \
257 }