libevent/WIN32-Code/tree.h

75 #define SPLAY_LEFT(elm, field)		(elm)->field.spe_left
76 #define SPLAY_RIGHT(elm, field)		(elm)->field.spe_right
81 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\
82 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\
83 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
87 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\
88 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\
89 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
93 #define SPLAY_LINKLEFT(head, tmp, field) do {				\
94 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
96 	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\
99 #define SPLAY_LINKRIGHT(head, tmp, field) do {				\
100 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
102 	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\
105 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\
106 	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\
107 	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
108 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\
109 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\
114 #define SPLAY_PROTOTYPE(name, type, field, cmp)				\
136 	if (SPLAY_RIGHT(elm, field) != NULL) {				\
137 		elm = SPLAY_RIGHT(elm, field);				\
138 		while (SPLAY_LEFT(elm, field) != NULL) {		\
139 			elm = SPLAY_LEFT(elm, field);			\
156 #define SPLAY_GENERATE(name, type, field, cmp)				\
161 	    SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;	\
167 		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
168 		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\
169 		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\
171 		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
172 		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
173 		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
189 		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
190 			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
192 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
193 			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
195 			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
208 	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
213 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
217 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
218 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
221 			SPLAY_LINKLEFT(head, __right, field);		\
223 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
227 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
228 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
231 			SPLAY_LINKRIGHT(head, __left, field);		\
234 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
244 	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
249 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
253 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
254 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
257 			SPLAY_LINKLEFT(head, __right, field);		\
259 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
263 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
264 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
267 			SPLAY_LINKRIGHT(head, __left, field);		\
270 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
313 #define RB_LEFT(elm, field)		(elm)->field.rbe_left
314 #define RB_RIGHT(elm, field)		(elm)->field.rbe_right
315 #define RB_PARENT(elm, field)		(elm)->field.rbe_parent
316 #define RB_COLOR(elm, field)		(elm)->field.rbe_color
320 #define RB_SET(elm, parent, field) do {					\
321 	RB_PARENT(elm, field) = parent;					\
322 	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
323 	RB_COLOR(elm, field) = RB_RED;					\
326 #define RB_SET_BLACKRED(black, red, field) do {				\
327 	RB_COLOR(black, field) = RB_BLACK;				\
328 	RB_COLOR(red, field) = RB_RED;					\
335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
336 	(tmp) = RB_RIGHT(elm, field);					\
337 	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {		\
338 		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
341 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
342 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
343 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
345 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
348 	RB_LEFT(tmp, field) = (elm);					\
349 	RB_PARENT(elm, field) = (tmp);					\
351 	if ((RB_PARENT(tmp, field)))					\
352 		RB_AUGMENT(RB_PARENT(tmp, field));			\
355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
356 	(tmp) = RB_LEFT(elm, field);					\
357 	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {		\
358 		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
361 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {		\
362 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
363 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
365 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
368 	RB_RIGHT(tmp, field) = (elm);					\
369 	RB_PARENT(elm, field) = (tmp);					\
371 	if ((RB_PARENT(tmp, field)))					\
372 		RB_AUGMENT(RB_PARENT(tmp, field));			\
376 #define RB_PROTOTYPE(name, type, field, cmp)				\
389 #define RB_GENERATE(name, type, field, cmp)				\
394 	while ((parent = RB_PARENT(elm, field)) &&			\
395 	    RB_COLOR(parent, field) == RB_RED) {			\
396 		gparent = RB_PARENT(parent, field);			\
397 		if (parent == RB_LEFT(gparent, field)) {		\
398 			tmp = RB_RIGHT(gparent, field);			\
399 			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
400 				RB_COLOR(tmp, field) = RB_BLACK;	\
401 				RB_SET_BLACKRED(parent, gparent, field);\
405 			if (RB_RIGHT(parent, field) == elm) {		\
406 				RB_ROTATE_LEFT(head, parent, tmp, field);\
411 			RB_SET_BLACKRED(parent, gparent, field);	\
412 			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
414 			tmp = RB_LEFT(gparent, field);			\
415 			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
416 				RB_COLOR(tmp, field) = RB_BLACK;	\
417 				RB_SET_BLACKRED(parent, gparent, field);\
421 			if (RB_LEFT(parent, field) == elm) {		\
422 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
427 			RB_SET_BLACKRED(parent, gparent, field);	\
428 			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
431 	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
438 	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&	\
440 		if (RB_LEFT(parent, field) == elm) {			\
441 			tmp = RB_RIGHT(parent, field);			\
442 			if (RB_COLOR(tmp, field) == RB_RED) {		\
443 				RB_SET_BLACKRED(tmp, parent, field);	\
444 				RB_ROTATE_LEFT(head, parent, tmp, field);\
445 				tmp = RB_RIGHT(parent, field);		\
447 			if ((RB_LEFT(tmp, field) == NULL ||		\
448 			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
449 			    (RB_RIGHT(tmp, field) == NULL ||		\
450 			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
451 				RB_COLOR(tmp, field) = RB_RED;		\
453 				parent = RB_PARENT(elm, field);		\
455 				if (RB_RIGHT(tmp, field) == NULL ||	\
456 				    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
458 					if ((oleft = RB_LEFT(tmp, field)))\
459 						RB_COLOR(oleft, field) = RB_BLACK;\
460 					RB_COLOR(tmp, field) = RB_RED;	\
461 					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
462 					tmp = RB_RIGHT(parent, field);	\
464 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
465 				RB_COLOR(parent, field) = RB_BLACK;	\
466 				if (RB_RIGHT(tmp, field))		\
467 					RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
468 				RB_ROTATE_LEFT(head, parent, tmp, field);\
473 			tmp = RB_LEFT(parent, field);			\
474 			if (RB_COLOR(tmp, field) == RB_RED) {		\
475 				RB_SET_BLACKRED(tmp, parent, field);	\
476 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
477 				tmp = RB_LEFT(parent, field);		\
479 			if ((RB_LEFT(tmp, field) == NULL ||		\
480 			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
481 			    (RB_RIGHT(tmp, field) == NULL ||		\
482 			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
483 				RB_COLOR(tmp, field) = RB_RED;		\
485 				parent = RB_PARENT(elm, field);		\
487 				if (RB_LEFT(tmp, field) == NULL ||	\
488 				    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
490 					if ((oright = RB_RIGHT(tmp, field)))\
491 						RB_COLOR(oright, field) = RB_BLACK;\
492 					RB_COLOR(tmp, field) = RB_RED;	\
493 					RB_ROTATE_LEFT(head, tmp, oright, field);\
494 					tmp = RB_LEFT(parent, field);	\
496 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
497 				RB_COLOR(parent, field) = RB_BLACK;	\
498 				if (RB_LEFT(tmp, field))		\
499 					RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
500 				RB_ROTATE_RIGHT(head, parent, tmp, field);\
507 		RB_COLOR(elm, field) = RB_BLACK;			\
515 	if (RB_LEFT(elm, field) == NULL)				\
516 		child = RB_RIGHT(elm, field);				\
517 	else if (RB_RIGHT(elm, field) == NULL)				\
518 		child = RB_LEFT(elm, field);				\
521 		elm = RB_RIGHT(elm, field);				\
522 		while ((left = RB_LEFT(elm, field)))			\
524 		child = RB_RIGHT(elm, field);				\
525 		parent = RB_PARENT(elm, field);				\
526 		color = RB_COLOR(elm, field);				\
528 			RB_PARENT(child, field) = parent;		\
530 			if (RB_LEFT(parent, field) == elm)		\
531 				RB_LEFT(parent, field) = child;		\
533 				RB_RIGHT(parent, field) = child;	\
537 		if (RB_PARENT(elm, field) == old)			\
539 		(elm)->field = (old)->field;				\
540 		if (RB_PARENT(old, field)) {				\
541 			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
542 				RB_LEFT(RB_PARENT(old, field), field) = elm;\
544 				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
545 			RB_AUGMENT(RB_PARENT(old, field));		\
548 		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
549 		if (RB_RIGHT(old, field))				\
550 			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
555 			} while ((left = RB_PARENT(left, field)));	\
559 	parent = RB_PARENT(elm, field);					\
560 	color = RB_COLOR(elm, field);					\
562 		RB_PARENT(child, field) = parent;			\
564 		if (RB_LEFT(parent, field) == elm)			\
565 			RB_LEFT(parent, field) = child;			\
567 			RB_RIGHT(parent, field) = child;		\
589 			tmp = RB_LEFT(tmp, field);			\
591 			tmp = RB_RIGHT(tmp, field);			\
595 	RB_SET(elm, parent, field);					\
598 			RB_LEFT(parent, field) = elm;			\
600 			RB_RIGHT(parent, field) = elm;			\
617 			tmp = RB_LEFT(tmp, field);			\
619 			tmp = RB_RIGHT(tmp, field);			\
629 	if (RB_RIGHT(elm, field)) {					\
630 		elm = RB_RIGHT(elm, field);				\
631 		while (RB_LEFT(elm, field))				\
632 			elm = RB_LEFT(elm, field);			\
634 		if (RB_PARENT(elm, field) &&				\
635 		    (elm == RB_LEFT(RB_PARENT(elm, field), field)))	\
636 			elm = RB_PARENT(elm, field);			\
638 			while (RB_PARENT(elm, field) &&			\
639 			    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
640 				elm = RB_PARENT(elm, field);		\
641 			elm = RB_PARENT(elm, field);			\
655 			tmp = RB_LEFT(tmp, field);			\
657 			tmp = RB_RIGHT(tmp, field);			\