-
Notifications
You must be signed in to change notification settings - Fork 9
/
Copy pathrb.txt
133 lines (98 loc) · 4.96 KB
/
rb.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
RBTREE(3) NetBSD Library Functions Manual RBTREE(3)
*NAME*
*rbtree* -- red-black tree
*LIBRARY*
Standard C Library (libc, -lc)
*SYNOPSIS*
*#include* *<sys/rbtree.h>*
void
*rb_tree_init*(rb_tree_t *, const rb_tree_ops_t *);
void *
*rb_tree_insert_node*(rb_tree_t *, void *);
void
*rb_tree_remove_node*(rb_tree_t *, void *);
void *
*rb_tree_find_node*(rb_tree_t *, const void *);
void *
*rb_tree_find_node_geq*(rb_tree_t *, const void *);
void *
*rb_tree_find_node_leq*(rb_tree_t *, const void *);
void *
*rb_tree_iterate*(rb_tree_t *, void *, const unsigned int);
*DESCRIPTION*
*rbtree* provides red-black trees. A red-black tree is a binary search
tree with the node color as an extra attribute. It fulfills a set of
conditions:
1. Every search path from the root to a leaf consists of the same
number of black nodes.
2. Each red node (except for the root) has a black parent.
3. Each leaf node is black.
Every operation on a red-black tree is bounded as O(lg n). The maximum
height of a red-black tree is 2lg (n+1).
*TYPES*
rb_tree_t
A red-black tree.
typedef signed int (* rbto_compare_nodes_fn)(void *, const void *, const void *);
The node-comparison operator. Defines an ordering on nodes.
Returns a negative value if the first node precedes the second
node. Returns a positive value if the first node follows the
second node. Returns 0 if the first node and the second are
identical according to the ordering.
typedef signed int (* rbto_compare_key_fn)(void *, const void *, const void *);
The node-key comparison operator. Defines the order of nodes
and keys. Returns a negative value if the node precedes the
key. Returns a positive value if the node follows the key.
Returns 0 if the node is identical to the key according to the
ordering.
rb_tree_ops_t
Defines the operator for comparing two nodes in the same tree,
the operator for comparing a node in the tree with a key, the
offset of member rb_node_t within a node, and the opaque context
passed to the operators. Members of rb_tree_ops_t are
rbto_compare_nodes_fn rbto_compare_nodes;
rbto_compare_key_fn rbto_compare_key;
size_t rbto_node_offset;
void *rbto_context;
rb_node_t
A node in a red-black tree has this structure as a member.
*FUNCTIONS*
*rb_tree_init*(rbt, ops)
Initialize the red-black tree rbt. Let the comparison operators
given by ops define the order of nodes in the tree for the pur-
poses of insertion, search, and iteration. *rb_tree_init*()
always succeeds.
*rb_tree_insert_node*(rbt, rb)
Insert the node rb into the tree rbt. Return inserted node on
success, already existing node on failure.
*rb_tree_remove_node*(rbt, rb)
Remove the node rb from the tree rbt.
*rb_tree_find_node*(rbt, key)
Search the tree rbt for a node exactly matching key. If no such
node is in the tree, return NULL. Otherwise, return the match-
ing node.
*rb_tree_find_node_geq*(rbt, key)
Search the tree rbt for a node that exactly matches key and
return it. If no such node is present, return the first node
following key or, if no such node is in the tree, return NULL.
*rb_tree_find_node_leq*(rbt, key)
Search the tree rbt for a node that exactly matches key and
return it. If no such node is present, return the first node
preceding key or, if no such node is in the tree, return NULL.
*rb_tree_iterate*(rbt, rb, direction)
If direction is RB_DIR_LEFT, return the node in the tree rbt
immediately preceding the node rb or, if rb is NULL, return the
last node in rbt or, if the tree is empty, return NULL.
If direction is RB_DIR_RIGHT, return the node in the tree rbt
immediately following the node rb or, if rb is NULL, return the
first node in rbt or, if the tree is empty, return NULL.
*CODE* *REFERENCES*
The *rbtree* interface is implemented in common/lib/libc/gen/rb.c.
*SEE* *ALSO*
queue(3) <queue.3.html>, tree(3) <tree.3.html>
*HISTORY*
The *rbtree* interface first appeared in NetBSD 6.0.
*AUTHORS*
Matt Thomas <[email protected]> wrote *rbtree*.
Niels Provos <[email protected]> wrote the tree(3) <tree.3> manual page.
Portions of this page derive from that page.
NetBSD 5.0 February 17, 2012 NetBSD 5.0