openbsd_wlan/sys/tree.h

52  *	- each red node (except for the root) has a black parent,
311 	struct type *rbe_parent;	/* parent element */		\
322 #define RB_SET(elm, parent, field) do {					\
323 	RB_PARENT(elm, field) = parent;					\
405 	struct type *parent, *gparent, *tmp;				\
406 	while ((parent = RB_PARENT(elm, field)) &&			\
407 	    RB_COLOR(parent, field) == RB_RED) {			\
408 		gparent = RB_PARENT(parent, field);			\
409 		if (parent == RB_LEFT(gparent, field)) {		\
413 				RB_SET_BLACKRED(parent, gparent, field);\
417 			if (RB_RIGHT(parent, field) == elm) {		\
418 				RB_ROTATE_LEFT(head, parent, tmp, field);\
419 				tmp = parent;				\
420 				parent = elm;				\
423 			RB_SET_BLACKRED(parent, gparent, field);	\
429 				RB_SET_BLACKRED(parent, gparent, field);\
433 			if (RB_LEFT(parent, field) == elm) {		\
434 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
435 				tmp = parent;				\
436 				parent = elm;				\
439 			RB_SET_BLACKRED(parent, gparent, field);	\
447 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
452 		if (RB_LEFT(parent, field) == elm) {			\
453 			tmp = RB_RIGHT(parent, field);			\
455 				RB_SET_BLACKRED(tmp, parent, field);	\
456 				RB_ROTATE_LEFT(head, parent, tmp, field);\
457 				tmp = RB_RIGHT(parent, field);		\
464 				elm = parent;				\
465 				parent = RB_PARENT(elm, field);		\
474 					tmp = RB_RIGHT(parent, field);	\
476 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
477 				RB_COLOR(parent, field) = RB_BLACK;	\
480 				RB_ROTATE_LEFT(head, parent, tmp, field);\
485 			tmp = RB_LEFT(parent, field);			\
487 				RB_SET_BLACKRED(tmp, parent, field);	\
488 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
489 				tmp = RB_LEFT(parent, field);		\
496 				elm = parent;				\
497 				parent = RB_PARENT(elm, field);		\
506 					tmp = RB_LEFT(parent, field);	\
508 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
509 				RB_COLOR(parent, field) = RB_BLACK;	\
512 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
525 	struct type *child, *parent, *old = elm;			\
537 		parent = RB_PARENT(elm, field);				\
540 			RB_PARENT(child, field) = parent;		\
541 		if (parent) {						\
542 			if (RB_LEFT(parent, field) == elm)		\
543 				RB_LEFT(parent, field) = child;		\
545 				RB_RIGHT(parent, field) = child;	\
546 			RB_AUGMENT(parent);				\
550 			parent = elm;					\
563 		if (parent) {						\
564 			left = parent;					\
571 	parent = RB_PARENT(elm, field);					\
574 		RB_PARENT(child, field) = parent;			\
575 	if (parent) {							\
576 		if (RB_LEFT(parent, field) == elm)			\
577 			RB_LEFT(parent, field) = child;			\
579 			RB_RIGHT(parent, field) = child;		\
580 		RB_AUGMENT(parent);					\
585 		name##_RB_REMOVE_COLOR(head, parent, child);		\
594 	struct type *parent = NULL;					\
598 		parent = tmp;						\
599 		comp = (cmp)(elm, parent);				\
607 	RB_SET(elm, parent, field);					\
608 	if (parent != NULL) {						\
610 			RB_LEFT(parent, field) = elm;			\
612 			RB_RIGHT(parent, field) = elm;			\
613 		RB_AUGMENT(parent);					\
707 	struct type *parent = NULL;					\
709 		parent = tmp;						\
715 	return (parent);						\
923 _name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent)		\
925 	_rb_set_parent(_name##_RBT_TYPE, elm, parent);			\