Lines Matching refs:elm
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; \
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); \
100 RB_AUGMENT(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); \
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); \
120 RB_AUGMENT(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); \
161 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
164 while ((parent = RB_PARENT(elm, field)) != NULL && \
172 elm = gparent; \
175 if (RB_RIGHT(parent, field) == elm) { \
178 parent = elm; \
179 elm = tmp; \
188 elm = gparent; \
191 if (RB_LEFT(parent, field) == elm) { \
194 parent = elm; \
195 elm = tmp; \
206 struct type *elm) \
209 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
210 elm != RB_ROOT(head)) { \
211 if (RB_LEFT(parent, field) == elm) { \
223 elm = parent; \
224 parent = RB_PARENT(elm, field); \
241 elm = RB_ROOT(head); \
256 elm = parent; \
257 parent = RB_PARENT(elm, field); \
274 elm = RB_ROOT(head); \
279 if (elm) \
280 RB_COLOR(elm, field) = RB_BLACK; \
284 name##_RB_REMOVE(struct name *head, struct type *elm) \
286 struct type *child, *parent, *old = elm; \
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) \
296 elm = left; \
297 child = RB_RIGHT(elm, field); \
298 parent = RB_PARENT(elm, field); \
299 color = RB_COLOR(elm, field); \
303 if (RB_LEFT(parent, field) == elm) \
310 if (RB_PARENT(elm, field) == old) \
311 parent = elm; \
312 (elm)->field = (old)->field; \
315 RB_LEFT(RB_PARENT(old, field), field) = elm; \
317 RB_RIGHT(RB_PARENT(old, field), field) = elm; \
320 RB_ROOT(head) = elm; \
321 RB_PARENT(RB_LEFT(old, field), field) = elm; \
323 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
332 parent = RB_PARENT(elm, field); \
333 color = RB_COLOR(elm, field); \
337 if (RB_LEFT(parent, field) == elm) \
352 name##_RB_INSERT(struct name *head, struct type *elm) \
360 comp = (cmp)(elm, parent); \
368 RB_SET(elm, parent, field); \
371 RB_LEFT(parent, field) = elm; \
373 RB_RIGHT(parent, field) = elm; \
376 RB_ROOT(head) = elm; \
377 name##_RB_INSERT_COLOR(head, elm); \
383 name##_RB_FIND(struct name *head, struct type *elm) \
388 comp = cmp(elm, tmp); \
401 name##_RB_NFIND(struct name *head, struct type *elm) \
407 comp = cmp(elm, tmp); \
422 name##_RB_NEXT(struct type *elm) \
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); \
439 return (elm); \
444 name##_RB_PREV(struct type *elm) \
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); \
461 return (elm); \
