47 /** Node colour black */
49 /** Node colour red */
52 /** the NULL node, global alloc */
62 static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
64 static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
65 /** Fixup node colours when insert happened */
66 static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
67 /** Fixup node colours when delete happened */
104  * Rotates the node to the left.
108 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)  in rbtree_rotate_left()  argument
110 	rbnode_type *right = node->right;  in rbtree_rotate_left()
111 	node->right = right->left;  in rbtree_rotate_left()
113 		right->left->parent = node;  in rbtree_rotate_left()
115 	right->parent = node->parent;  in rbtree_rotate_left()
117 	if (node->parent != RBTREE_NULL) {  in rbtree_rotate_left()
118 		if (node == node->parent->left) {  in rbtree_rotate_left()
119 			node->parent->left = right;  in rbtree_rotate_left()
121 			node->parent->right = right;  in rbtree_rotate_left()
126 	right->left = node;  in rbtree_rotate_left()
127 	node->parent = right;  in rbtree_rotate_left()
131  * Rotates the node to the right.
135 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)  in rbtree_rotate_right()  argument
137 	rbnode_type *left = node->left;  in rbtree_rotate_right()
138 	node->left = left->right;  in rbtree_rotate_right()
140 		left->right->parent = node;  in rbtree_rotate_right()
142 	left->parent = node->parent;  in rbtree_rotate_right()
144 	if (node->parent != RBTREE_NULL) {  in rbtree_rotate_right()
145 		if (node == node->parent->right) {  in rbtree_rotate_right()
146 			node->parent->right = left;  in rbtree_rotate_right()
148 			node->parent->left = left;  in rbtree_rotate_right()
153 	left->right = node;  in rbtree_rotate_right()
154 	node->parent = left;  in rbtree_rotate_right()
158 rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)  in rbtree_insert_fixup()  argument
163 	while (node != rbtree->root && node->parent->color == RED) {  in rbtree_insert_fixup()
165 		if (node->parent == node->parent->parent->left) {  in rbtree_insert_fixup()
166 			uncle = node->parent->parent->right;  in rbtree_insert_fixup()
171 				node->parent->color = BLACK;  in rbtree_insert_fixup()
175 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
178 				node = node->parent->parent;  in rbtree_insert_fixup()
181 				if (node == node->parent->right) {  in rbtree_insert_fixup()
182 					node = node->parent;  in rbtree_insert_fixup()
183 					rbtree_rotate_left(rbtree, node);  in rbtree_insert_fixup()
186 				node->parent->color = BLACK;  in rbtree_insert_fixup()
187 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
188 				rbtree_rotate_right(rbtree, node->parent->parent);  in rbtree_insert_fixup()
191 			uncle = node->parent->parent->left;  in rbtree_insert_fixup()
196 				node->parent->color = BLACK;  in rbtree_insert_fixup()
200 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
203 				node = node->parent->parent;  in rbtree_insert_fixup()
206 				if (node == node->parent->left) {  in rbtree_insert_fixup()
207 					node = node->parent;  in rbtree_insert_fixup()
208 					rbtree_rotate_right(rbtree, node);  in rbtree_insert_fixup()
211 				node->parent->color = BLACK;  in rbtree_insert_fixup()
212 				node->parent->parent->color = RED;  in rbtree_insert_fixup()
213 				rbtree_rotate_left(rbtree, node->parent->parent);  in rbtree_insert_fixup()
222  * Inserts a node into a red black tree.
224  * Returns NULL on failure or the pointer to the newly added node
234 	rbnode_type	*node = rbtree->root;  in rbtree_insert()  local
239 	while (node != RBTREE_NULL) {  in rbtree_insert()
241 		if ((r = rbtree->cmp(data->key, node->key)) == 0) {  in rbtree_insert()
244 		parent = node;  in rbtree_insert()
247 			node = node->left;  in rbtree_insert()
249 			node = node->right;  in rbtree_insert()
253 	/* Initialize the new node */  in rbtree_insert()
283 	rbnode_type *node;  in rbtree_search()  local
285 	if (rbtree_find_less_equal(rbtree, key, &node)) {  in rbtree_search()
286 		return node;  in rbtree_search()
292 /** helpers for delete: swap node colours */
298 /** helpers for delete: swap node pointers */
319 /** Update parent pointer of a node 'child' */
389 		/* if node is red then the child (black) can be swapped in */  in rbtree_delete()
393 		/* change child to BLACK, removing a RED node is no problem */  in rbtree_delete()
412 	/* determine sibling to the node that is one-black short */  in rbtree_delete_fixup()
515 	rbnode_type *node;  in rbtree_find_less_equal()  local
520 	node = rbtree->root;  in rbtree_find_less_equal()
526 	while (node != RBTREE_NULL) {  in rbtree_find_less_equal()
527 		r = rbtree->cmp(key, node->key);  in rbtree_find_less_equal()
530 			*result = node;  in rbtree_find_less_equal()
534 			node = node->left;  in rbtree_find_less_equal()
537 			*result = node;  in rbtree_find_less_equal()
538 			node = node->right;  in rbtree_find_less_equal()
551 	rbnode_type *node;  in rbtree_first()  local
553 	for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);  in rbtree_first()
554 	return node;  in rbtree_first()
560 	rbnode_type *node;  in rbtree_last()  local
562 	for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);  in rbtree_last()
563 	return node;  in rbtree_last()
567  * Returns the next node...
571 rbtree_next (rbnode_type *node)  in rbtree_next()  argument
575 	if (node->right != RBTREE_NULL) {  in rbtree_next()
577 		for (node = node->right; node->left != RBTREE_NULL; node = node->left);  in rbtree_next()
579 		parent = node->parent;  in rbtree_next()
580 		while (parent != RBTREE_NULL && node == parent->right) {  in rbtree_next()
581 			node = parent;  in rbtree_next()
584 		node = parent;  in rbtree_next()
586 	return node;  in rbtree_next()
590 rbtree_previous(rbnode_type *node)  in rbtree_previous()  argument
594 	if (node->left != RBTREE_NULL) {  in rbtree_previous()
596 		for (node = node->left; node->right != RBTREE_NULL; node = node->right);  in rbtree_previous()
598 		parent = node->parent;  in rbtree_previous()
599 		while (parent != RBTREE_NULL && node == parent->left) {  in rbtree_previous()
600 			node = parent;  in rbtree_previous()
603 		node = parent;  in rbtree_previous()
605 	return node;  in rbtree_previous()
610 traverse_post(void (*func)(rbnode_type*, void*), void* arg, rbnode_type* node)  in traverse_post()  argument
612 	if(!node || node == RBTREE_NULL)  in traverse_post()
615 	traverse_post(func, arg, node->left);  in traverse_post()
616 	traverse_post(func, arg, node->right);  in traverse_post()
618 	(*func)(node, arg);  in traverse_post()