rb_order_stats.c File Reference
#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_order_stats.c:

Go to the source code of this file.


HIDDEN struct bu_rb_node_rb_select (struct bu_rb_node *root, int order, int k)
void * bu_rb_select (struct bu_rb_tree *tree, int order, int k)
int bu_rb_rank (struct bu_rb_tree *tree, int order)

Detailed Description

Routines to support order-statistic operations for a red-black tree

Definition in file rb_order_stats.c.

Function Documentation

HIDDEN struct bu_rb_node* _rb_select ( struct bu_rb_node root,
int  order,
int  k 

Retrieve the element of rank k in one order of a red-black tree

This function has three parameters: the root of the tree to search, the order on which to do the searching, and the rank of interest. _rb_select() returns the discovered node. It is an implementation of the routine OS-SELECT on p. 282 of Cormen et al. (p. 341 in the paperback version of the 2009 edition).

Definition at line 41 of file rb_order_stats.c.

References BU_CKMAG, bu_log(), BU_RB_DEBUG_OS, BU_RB_NODE_MAGIC, RB_LEFT_CHILD, RB_RIGHT_CHILD, RB_SIZE, bu_rb_node::rbn_tree, bu_rb_tree::rbt_debug, and UNLIKELY.

Referenced by bu_rb_select().

Here is the call graph for this function: