Lines Matching refs:field
73 #define RB_LEFT(elm, field) (elm)->field.rbe_left argument
74 #define RB_RIGHT(elm, field) (elm)->field.rbe_right argument
75 #define RB_PARENT(elm, field) (elm)->field.rbe_parent argument
76 #define RB_COLOR(elm, field) (elm)->field.rbe_color argument
80 #define RB_SET(elm, parent, field) do { \ argument
81 RB_PARENT(elm, field) = parent; \
82 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
83 RB_COLOR(elm, field) = RB_RED; \
86 #define RB_SET_BLACKRED(black, red, field) do { \ argument
87 RB_COLOR(black, field) = RB_BLACK; \
88 RB_COLOR(red, field) = RB_RED; \
95 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ argument
96 (tmp) = RB_RIGHT(elm, field); \
97 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
98 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
101 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
102 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
103 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
105 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
108 RB_LEFT(tmp, field) = (elm); \
109 RB_PARENT(elm, field) = (tmp); \
111 if ((RB_PARENT(tmp, field))) \
112 RB_AUGMENT(RB_PARENT(tmp, field)); \
115 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ argument
116 (tmp) = RB_LEFT(elm, field); \
117 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
118 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
121 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
122 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
123 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
125 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
128 RB_RIGHT(tmp, field) = (elm); \
129 RB_PARENT(elm, field) = (tmp); \
131 if ((RB_PARENT(tmp, field))) \
132 RB_AUGMENT(RB_PARENT(tmp, field)); \
136 #define RB_PROTOTYPE(name, type, field, cmp) \ argument
137 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
138 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ argument
139 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static)
140 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ argument
155 #define RB_GENERATE(name, type, field, cmp) \ argument
156 RB_GENERATE_INTERNAL(name, type, field, cmp,)
157 #define RB_GENERATE_STATIC(name, type, field, cmp) \ argument
158 RB_GENERATE_INTERNAL(name, type, field, cmp, UV__UNUSED static)
159 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ argument
164 while ((parent = RB_PARENT(elm, field)) != NULL && \
165 RB_COLOR(parent, field) == RB_RED) { \
166 gparent = RB_PARENT(parent, field); \
167 if (parent == RB_LEFT(gparent, field)) { \
168 tmp = RB_RIGHT(gparent, field); \
169 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
170 RB_COLOR(tmp, field) = RB_BLACK; \
171 RB_SET_BLACKRED(parent, gparent, field); \
175 if (RB_RIGHT(parent, field) == elm) { \
176 RB_ROTATE_LEFT(head, parent, tmp, field); \
181 RB_SET_BLACKRED(parent, gparent, field); \
182 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
184 tmp = RB_LEFT(gparent, field); \
185 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
186 RB_COLOR(tmp, field) = RB_BLACK; \
187 RB_SET_BLACKRED(parent, gparent, field); \
191 if (RB_LEFT(parent, field) == elm) { \
192 RB_ROTATE_RIGHT(head, parent, tmp, field); \
197 RB_SET_BLACKRED(parent, gparent, field); \
198 RB_ROTATE_LEFT(head, gparent, tmp, field); \
201 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
209 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
211 if (RB_LEFT(parent, field) == elm) { \
212 tmp = RB_RIGHT(parent, field); \
213 if (RB_COLOR(tmp, field) == RB_RED) { \
214 RB_SET_BLACKRED(tmp, parent, field); \
215 RB_ROTATE_LEFT(head, parent, tmp, field); \
216 tmp = RB_RIGHT(parent, field); \
218 if ((RB_LEFT(tmp, field) == NULL || \
219 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \
220 (RB_RIGHT(tmp, field) == NULL || \
221 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \
222 RB_COLOR(tmp, field) = RB_RED; \
224 parent = RB_PARENT(elm, field); \
226 if (RB_RIGHT(tmp, field) == NULL || \
227 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \
229 if ((oleft = RB_LEFT(tmp, field)) \
231 RB_COLOR(oleft, field) = RB_BLACK; \
232 RB_COLOR(tmp, field) = RB_RED; \
233 RB_ROTATE_RIGHT(head, tmp, oleft, field); \
234 tmp = RB_RIGHT(parent, field); \
236 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
237 RB_COLOR(parent, field) = RB_BLACK; \
238 if (RB_RIGHT(tmp, field)) \
239 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \
240 RB_ROTATE_LEFT(head, parent, tmp, field); \
245 tmp = RB_LEFT(parent, field); \
246 if (RB_COLOR(tmp, field) == RB_RED) { \
247 RB_SET_BLACKRED(tmp, parent, field); \
248 RB_ROTATE_RIGHT(head, parent, tmp, field); \
249 tmp = RB_LEFT(parent, field); \
251 if ((RB_LEFT(tmp, field) == NULL || \
252 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \
253 (RB_RIGHT(tmp, field) == NULL || \
254 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \
255 RB_COLOR(tmp, field) = RB_RED; \
257 parent = RB_PARENT(elm, field); \
259 if (RB_LEFT(tmp, field) == NULL || \
260 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \
262 if ((oright = RB_RIGHT(tmp, field)) \
264 RB_COLOR(oright, field) = RB_BLACK; \
265 RB_COLOR(tmp, field) = RB_RED; \
266 RB_ROTATE_LEFT(head, tmp, oright, field); \
267 tmp = RB_LEFT(parent, field); \
269 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \
270 RB_COLOR(parent, field) = RB_BLACK; \
271 if (RB_LEFT(tmp, field)) \
272 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \
273 RB_ROTATE_RIGHT(head, parent, tmp, field); \
280 RB_COLOR(elm, field) = RB_BLACK; \
288 if (RB_LEFT(elm, field) == NULL) \
289 child = RB_RIGHT(elm, field); \
290 else if (RB_RIGHT(elm, field) == NULL) \
291 child = RB_LEFT(elm, field); \
294 elm = RB_RIGHT(elm, field); \
295 while ((left = RB_LEFT(elm, field)) != NULL) \
297 child = RB_RIGHT(elm, field); \
298 parent = RB_PARENT(elm, field); \
299 color = RB_COLOR(elm, field); \
301 RB_PARENT(child, field) = parent; \
303 if (RB_LEFT(parent, field) == elm) \
304 RB_LEFT(parent, field) = child; \
306 RB_RIGHT(parent, field) = child; \
310 if (RB_PARENT(elm, field) == old) \
312 (elm)->field = (old)->field; \
313 if (RB_PARENT(old, field)) { \
314 if (RB_LEFT(RB_PARENT(old, field), field) == old) \
315 RB_LEFT(RB_PARENT(old, field), field) = elm; \
317 RB_RIGHT(RB_PARENT(old, field), field) = elm; \
318 RB_AUGMENT(RB_PARENT(old, field)); \
321 RB_PARENT(RB_LEFT(old, field), field) = elm; \
322 if (RB_RIGHT(old, field)) \
323 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
328 } while ((left = RB_PARENT(left, field)) != NULL); \
332 parent = RB_PARENT(elm, field); \
333 color = RB_COLOR(elm, field); \
335 RB_PARENT(child, field) = parent; \
337 if (RB_LEFT(parent, field) == elm) \
338 RB_LEFT(parent, field) = child; \
340 RB_RIGHT(parent, field) = child; \
362 tmp = RB_LEFT(tmp, field); \
364 tmp = RB_RIGHT(tmp, field); \
368 RB_SET(elm, parent, field); \
371 RB_LEFT(parent, field) = elm; \
373 RB_RIGHT(parent, field) = elm; \
390 tmp = RB_LEFT(tmp, field); \
392 tmp = RB_RIGHT(tmp, field); \
410 tmp = RB_LEFT(tmp, field); \
413 tmp = RB_RIGHT(tmp, field); \
424 if (RB_RIGHT(elm, field)) { \
425 elm = RB_RIGHT(elm, field); \
426 while (RB_LEFT(elm, field)) \
427 elm = RB_LEFT(elm, field); \
429 if (RB_PARENT(elm, field) && \
430 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
431 elm = RB_PARENT(elm, field); \
433 while (RB_PARENT(elm, field) && \
434 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
435 elm = RB_PARENT(elm, field); \
436 elm = RB_PARENT(elm, field); \
446 if (RB_LEFT(elm, field)) { \
447 elm = RB_LEFT(elm, field); \
448 while (RB_RIGHT(elm, field)) \
449 elm = RB_RIGHT(elm, field); \
451 if (RB_PARENT(elm, field) && \
452 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
453 elm = RB_PARENT(elm, field); \
455 while (RB_PARENT(elm, field) && \
456 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
457 elm = RB_PARENT(elm, field); \
458 elm = RB_PARENT(elm, field); \
472 tmp = RB_LEFT(tmp, field); \
474 tmp = RB_RIGHT(tmp, field); \
