nsd/dist/rbtree.c

281 	rbnode_type *to_delete;
283 	if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
287 	if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
290 		rbnode_type *smright = to_delete->right;
293 		/* swap the smright and to_delete elements in the tree,
299 		swap_int8(&to_delete->color, &smright->color);
301 		/* swap child pointers in parents of smright/to_delete */
302 		change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
303 		if(to_delete->right != smright)
304 			change_parent_ptr(rbtree, smright->parent, smright, to_delete);
306 		/* swap parent pointers in children of smright/to_delete */
307 		change_child_ptr(smright->left, smright, to_delete);
308 		change_child_ptr(smright->left, smright, to_delete);
309 		change_child_ptr(smright->right, smright, to_delete);
310 		change_child_ptr(smright->right, smright, to_delete);
311 		change_child_ptr(to_delete->left, to_delete, smright);
312 		if(to_delete->right != smright)
313 			change_child_ptr(to_delete->right, to_delete, smright);
314 		if(to_delete->right == smright)
317 			to_delete->right = to_delete;
321 		/* swap pointers in to_delete/smright nodes */
322 		swap_np(&to_delete->parent, &smright->parent);
323 		swap_np(&to_delete->left, &smright->left);
324 		swap_np(&to_delete->right, &smright->right);
326 		/* now delete to_delete (which is at the location where the smright previously was) */
328 	assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);
330 	if(to_delete->left != RBTREE_NULL) child = to_delete->left;
331 	else child = to_delete->right;
333 	/* unlink to_delete from the tree, replace to_delete with child */
334 	change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
335 	change_child_ptr(child, to_delete, to_delete->parent);
337 	if(to_delete->color == RED)
346 	else rbtree_delete_fixup(rbtree, child, to_delete->parent);
349 	to_delete->parent = RBTREE_NULL;
350 	to_delete->left = RBTREE_NULL;
351 	to_delete->right = RBTREE_NULL;
352 	to_delete->color = BLACK;
353 	return to_delete;