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_extreme.c:

Go to the source code of this file.

Functions

HIDDEN struct bu_rb_node_rb_extreme (struct bu_rb_node *root, int order, int sense, struct bu_rb_node *empty_node)
 
void * bu_rb_extreme (struct bu_rb_tree *tree, int order, int sense)
 
struct bu_rb_noderb_neighbor (struct bu_rb_node *node, int order, int sense)
 
void * bu_rb_neighbor (struct bu_rb_tree *tree, int order, int sense)
 
void * bu_rb_curr (struct bu_rb_tree *tree, int order)
 

Detailed Description

Routines to extract mins, maxes, adjacent, and current nodes from a red-black tree

Definition in file rb_extreme.c.

Function Documentation

HIDDEN struct bu_rb_node* _rb_extreme ( struct bu_rb_node root,
int  order,
int  sense,
struct bu_rb_node empty_node 
)

Find the minimum or maximum node in one order of a red-black tree

This function has four parameters: the root of the tree, the order, the sense (min or max), and the address to be understood as the nil node pointer. rb_extreme() returns a pointer to the extreme node.

Definition at line 40 of file rb_extreme.c.

References BU_CKMAG, BU_RB_NODE_MAGIC, RB_CKORDER, RB_CURRENT, RB_LEFT_CHILD, RB_RIGHT_CHILD, bu_rb_node::rbn_tree, and SENSE_MIN.

Referenced by bu_rb_extreme(), and rb_neighbor().

struct bu_rb_node* rb_neighbor ( struct bu_rb_node node,
int  order,
int  sense 
)

Return a node adjacent to a given red-black node

This function has three parameters: the node of interest, the order on which to do the search, and the sense (min or max, which is to say predecessor or successor). rb_neighbor() returns a pointer to the adjacent node. This function is modeled after the routine TREE-SUCCESSOR on p. 249 of Cormen et al.

Definition at line 91 of file rb_extreme.c.

References _rb_extreme(), BU_CKMAG, BU_RB_NODE_MAGIC, RB_CHILD, RB_CKORDER, RB_CURRENT, RB_LEFT_CHILD, RB_NULL, RB_PARENT, RB_RIGHT_CHILD, bu_rb_node::rbn_tree, and SENSE_MIN.

Referenced by _rb_delete(), and bu_rb_neighbor().

Here is the call graph for this function: