BRL-CAD
#include "common.h"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "bu/rb.h"
#include "./rb_internals.h"
Include dependency graph for rb_delete.c:

Go to the source code of this file.

Functions

HIDDEN void _rb_fixup (struct bu_rb_tree *tree, struct bu_rb_node *node, int order)
 
HIDDEN void _rb_delete (struct bu_rb_tree *tree, struct bu_rb_node *node, int order)
 
void bu_rb_delete (struct bu_rb_tree *tree, int order)
 

Detailed Description

Routines to delete a node from a red-black tree

Definition in file rb_delete.c.

Function Documentation

HIDDEN void _rb_fixup ( struct bu_rb_tree tree,
struct bu_rb_node node,
int  order 
)

Restore the red-black properties of a red-black tree after the splicing out of a node

This function has three parameters: the tree to be fixed up, the node where the trouble occurs, and the order. _rb_fixup() is an implementation of the routine RB-DELETE-FIXUP on p. 274 of Cormen et al. (p. 326 in the paperback version of the 2009 edition).

Definition at line 41 of file rb_delete.c.

References BU_CKMAG, BU_RB_NODE_MAGIC, BU_RB_TREE_MAGIC, RB_BLK, RB_CHILD, RB_CKORDER, RB_GET_COLOR, RB_LEFT, RB_LEFT_CHILD, RB_OTHER_CHILD, RB_OTHER_ROTATE, RB_PARENT, RB_RED, RB_RIGHT, RB_ROOT, RB_ROTATE, and RB_SET_COLOR.

Referenced by _rb_delete().

HIDDEN void _rb_delete ( struct bu_rb_tree tree,
struct bu_rb_node node,
int  order 
)

Delete a node from one order of a red-black tree

This function has three parameters: a tree, the node to delete, and the order from which to delete it. _rb_delete() is an implementation of the routine RB-DELETE on p. 273 of Cormen et al. (p. 324 in the paperback version of the 2009 edition).

Definition at line 99 of file rb_delete.c.

References _rb_fixup(), BU_CKMAG, bu_log(), BU_RB_DEBUG_DELETE, BU_RB_NODE_MAGIC, BU_RB_TREE_MAGIC, RB_BLK, RB_CKORDER, RB_DATA, rb_free_node(), RB_GET_COLOR, RB_LEFT_CHILD, rb_neighbor(), RB_NULL, RB_PARENT, RB_RIGHT_CHILD, RB_ROOT, bu_rb_node::rbn_package, bu_rb_node::rbn_pkg_refs, bu_rb_tree::rbt_debug, SENSE_MAX, and UNLIKELY.

Referenced by bu_rb_delete().

Here is the call graph for this function: