1 /******************************************************************************
3 * Copyright (C) 2008 Jason Evans <jasone@canonware.com>.
6 * Copyright (C) 2010 David Barr <david.barr@cordelta.com>.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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
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
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.
33 ******************************************************************************
35 * cpp macro implementation of treaps.
39 * (Optional, see assert(3).)
43 * #include <stdint.h> (For uint32_t.)
50 ******************************************************************************/
56 #define trp_node(a_type) \
59 uint32_t trpn_right; \
68 /* Pointer/Offset conversion */
69 #define trpn_pointer(a_base, a_offset) \
70 ((a_offset)==(~0)?NULL:&(a_base)[a_offset])
71 #define trpn_offset(a_type, a_base, a_pointer) \
72 ((a_pointer)==NULL?(~0):(a_type*)(a_pointer)-(a_base))
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_type, a_base, a_left); \
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_type, a_base, a_right);\
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); \
98 /* Tree initializer. */
99 #define trp_new(a_type, a_field, a_seed, a_trp) do { \
100 (a_trp)->trp_root = NULL; \
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)); \
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)); \
119 * The trp_gen() macro generates a type-specific treap implementation,
120 * based on the above cpp macros.
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);
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
143 * Assuming the following setup:
145 * typedef struct ex_node_s ex_node_t;
147 * trp_node(ex_node_t) ex_link;
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)
153 * The following API is generated:
156 * ex_new(ex_t *treap, uint32_t seed);
157 * Description: Initialize a treap structure.
159 * treap: Pointer to an uninitialized treap object.
160 * seed : Pseudo-random number generator seed. The seed value isn't
161 * very important, so if in doubt, pick a favorite number.
164 * ex_psearch(ex_t *treap, ex_node_t *key);
165 * Description: Search for node that matches key. If no match is found,
166 * return what would be key's successor/predecessor, were
169 * treap: Pointer to a initialized treap object.
171 * Ret: Node in treap that matches key, or if no match, hypothetical
172 * node's successor/predecessor (NULL if no successor/predecessor).
175 * ex_insert(ex_t *treap, ex_node_t *node);
176 * Description: Insert node into treap.
178 * treap: Pointer to a initialized treap object.
179 * node : Node to be inserted into treap.
181 #define trp_gen(a_attr, a_pre, a_t_type, a_type, a_field, a_base, a_cmp)\
183 a_pre##new(a_t_type *treap, uint32_t seed) { \
184 trp_new(a_type, a_field, seed, treap); \
187 a_pre##search(a_t_type *treap, a_type *key) { \
190 ret = treap->trp_root; \
192 && (cmp = (a_cmp)(key, ret)) != 0) { \
194 ret = trp_left_get(a_base, a_type, a_field, ret); \
196 ret = trp_right_get(a_base, a_type, a_field, ret); \
202 a_pre##psearch(a_t_type *treap, a_type *key) { \
204 a_type *tnode = treap->trp_root; \
206 while (tnode != NULL) { \
207 int cmp = (a_cmp)(key, tnode); \
209 tnode = trp_left_get(a_base, a_type, a_field, tnode); \
210 } else if (cmp > 0) { \
212 tnode = trp_right_get(a_base, a_type, a_field, tnode); \
221 a_pre##insert_recurse(a_type *cur_node, a_type *ins_node) { \
222 if (cur_node == NULL) { \
226 int cmp = a_cmp(ins_node, cur_node); \
229 a_type *left = a_pre##insert_recurse(trp_left_get(a_base, \
230 a_type, a_field, cur_node), ins_node); \
231 trp_left_set(a_base, a_type, a_field, cur_node, left); \
232 if (trp_prio_get(a_type, a_field, left) < \
233 trp_prio_get(a_type, a_field, cur_node)) { \
234 trpn_rotate_right(a_base, a_type, a_field, cur_node, \
240 a_type *right = a_pre##insert_recurse(trp_right_get(a_base, \
241 a_type, a_field, cur_node), ins_node); \
242 trp_right_set(a_base, a_type, a_field, cur_node, right); \
243 if (trp_prio_get(a_type, a_field, right) < \
244 trp_prio_get(a_type, a_field, cur_node)) { \
245 trpn_rotate_left(a_base, a_type, a_field, cur_node, \
255 a_pre##insert(a_t_type *treap, a_type *node) { \
256 trp_node_new(a_base, a_type, a_field, treap, node); \
257 treap->trp_root = a_pre##insert_recurse(treap->trp_root, node); \