28 static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
29 static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
30 static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
64 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)  in rbtree_rotate_left()  argument
66 	rbnode_type *right = node->right;  in rbtree_rotate_left()
67 	node->right = right->left;  in rbtree_rotate_left()
69 		right->left->parent = node;  in rbtree_rotate_left()
71 	right->parent = node->parent;  in rbtree_rotate_left()
73 	if (node->parent != RBTREE_NULL) {  in rbtree_rotate_left()
74 		if (node == node->parent->left) {  in rbtree_rotate_left()
75 			node->parent->left = right;  in rbtree_rotate_left()
77 			node->parent->right = right;  in rbtree_rotate_left()
82 	right->left = node;  in rbtree_rotate_left()
83 	node->parent = right;  in rbtree_rotate_left()
91 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)  in rbtree_rotate_right()  argument
93 	rbnode_type *left = node->left;  in rbtree_rotate_right()
94 	node->left = left->right;  in rbtree_rotate_right()
96 		left->right->parent = node;  in rbtree_rotate_right()
98 	left->parent = node->parent;  in rbtree_rotate_right()
100 	if (node->parent != RBTREE_NULL) {  in rbtree_rotate_right()
101 		if (node == node->parent->right) {  in rbtree_rotate_right()
102 			node->parent->right = left;  in rbtree_rotate_right()
104 			node->parent->left = left;  in rbtree_rotate_right()
109 	left->right = node;  in rbtree_rotate_right()
110 	node->parent = left;  in rbtree_rotate_right()
114 rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)  in rbtree_insert_fixup()  argument
119 	while (node != rbtree->root && node->parent->color == RED) {  in rbtree_insert_fixup()
121 		if (node->parent == node->parent->parent->left) {  in rbtree_insert_fixup()
122 			uncle = node->parent->parent->right;  in rbtree_insert_fixup()
127 				node->parent->color = BLACK;  in rbtree_insert_fixup()
131 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
134 				node = node->parent->parent;  in rbtree_insert_fixup()
137 				if (node == node->parent->right) {  in rbtree_insert_fixup()
138 					node = node->parent;  in rbtree_insert_fixup()
139 					rbtree_rotate_left(rbtree, node);  in rbtree_insert_fixup()
142 				node->parent->color = BLACK;  in rbtree_insert_fixup()
143 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
144 				rbtree_rotate_right(rbtree, node->parent->parent);  in rbtree_insert_fixup()
147 			uncle = node->parent->parent->left;  in rbtree_insert_fixup()
152 				node->parent->color = BLACK;  in rbtree_insert_fixup()
156 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
159 				node = node->parent->parent;  in rbtree_insert_fixup()
162 				if (node == node->parent->left) {  in rbtree_insert_fixup()
163 					node = node->parent;  in rbtree_insert_fixup()
164 					rbtree_rotate_right(rbtree, node);  in rbtree_insert_fixup()
167 				node->parent->color = BLACK;  in rbtree_insert_fixup()
168 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
169 				rbtree_rotate_left(rbtree, node->parent->parent);  in rbtree_insert_fixup()
190 	rbnode_type	*node = rbtree->root;  in rbtree_insert()  local
194 	while (node != RBTREE_NULL) {  in rbtree_insert()
196 		if ((r = rbtree->cmp(data->key, node->key)) == 0) {  in rbtree_insert()
199 		parent = node;  in rbtree_insert()
202 			node = node->left;  in rbtree_insert()
204 			node = node->right;  in rbtree_insert()
238 	rbnode_type *node;  in rbtree_search()  local
240 	if (rbtree_find_less_equal(rbtree, key, &node)) {  in rbtree_search()
241 		return node;  in rbtree_search()
463 	rbnode_type *node;  in rbtree_find_less_equal()  local
468 	node = rbtree->root;  in rbtree_find_less_equal()
473 	while (node != RBTREE_NULL) {  in rbtree_find_less_equal()
474 		r = rbtree->cmp(key, node->key);  in rbtree_find_less_equal()
477 			*result = node;  in rbtree_find_less_equal()
481 			node = node->left;  in rbtree_find_less_equal()
484 			*result = node;  in rbtree_find_less_equal()
485 			node = node->right;  in rbtree_find_less_equal()
498 	rbnode_type *node;  in rbtree_first()  local
500 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);  in rbtree_first()
501 	return node;  in rbtree_first()
507 	rbnode_type *node;  in rbtree_last()  local
509 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);  in rbtree_last()
510 	return node;  in rbtree_last()
518 rbtree_next (rbnode_type *node)  in rbtree_next()  argument
522 	if (node->right != RBTREE_NULL) {  in rbtree_next()
524 		for (node = node->right; node->left != RBTREE_NULL; node = node->left);  in rbtree_next()
526 		parent = node->parent;  in rbtree_next()
527 		while (parent != RBTREE_NULL && node == parent->right) {  in rbtree_next()
528 			node = parent;  in rbtree_next()
531 		node = parent;  in rbtree_next()
533 	return node;  in rbtree_next()
537 rbtree_previous(rbnode_type *node)  in rbtree_previous()  argument
541 	if (node->left != RBTREE_NULL) {  in rbtree_previous()
543 		for (node = node->left; node->right != RBTREE_NULL; node = node->right);  in rbtree_previous()
545 		parent = node->parent;  in rbtree_previous()
546 		while (parent != RBTREE_NULL && node == parent->left) {  in rbtree_previous()
547 			node = parent;  in rbtree_previous()
550 		node = parent;  in rbtree_previous()
552 	return node;  in rbtree_previous()