15         node = root.address.cast(rb_root_type.get_type().pointer())
19     node = root['rb_node']
20     if node == 0:
23     while node['rb_left']:
24         node = node['rb_left']
26     return node
31         node = root.address.cast(rb_root_type.get_type().pointer())
35     node = root['rb_node']
36     if node == 0:
39     while node['rb_right']:
40         node = node['rb_right']
42     return node
45 def rb_parent(node):  argument
46     parent = gdb.Value(node['__rb_parent_color'] & ~3)
50 def rb_empty_node(node):  argument
51     return node['__rb_parent_color'] == node.address
54 def rb_next(node):  argument
55     if node.type == rb_node_type.get_type():
56         node = node.address.cast(rb_node_type.get_type().pointer())
57     elif node.type != rb_node_type.get_type().pointer():
58         raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
60     if rb_empty_node(node):
63     if node['rb_right']:
64         node = node['rb_right']
65         while node['rb_left']:
66             node = node['rb_left']
67         return node
69     parent = rb_parent(node)
70     while parent and node == parent['rb_right']:
71             node = parent
72             parent = rb_parent(node)
77 def rb_prev(node):  argument
78     if node.type == rb_node_type.get_type():
79         node = node.address.cast(rb_node_type.get_type().pointer())
80     elif node.type != rb_node_type.get_type().pointer():
81         raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
83     if rb_empty_node(node):
86     if node['rb_left']:
87         node = node['rb_left']
88         while node['rb_right']:
89             node = node['rb_right']
90         return node.dereference()
92     parent = rb_parent(node)
93     while parent and node == parent['rb_left'].dereference():
94             node = parent
95             parent = rb_parent(node)
101     """Lookup and return a node from an RBTree
103 $lx_rb_first(root): Return the node at the given index.
104 If index is omitted, the root node is dereferenced and returned."""
121     """Lookup and return a node from an RBTree.
123 $lx_rb_last(root): Return the node at the given index.
124 If index is omitted, the root node is dereferenced and returned."""
141     """Lookup and return a node from an RBTree.
143 $lx_rb_next(node): Return the node at the given index.
144 If index is omitted, the root node is dereferenced and returned."""
149     def invoke(self, node):  argument
150         result = rb_next(node)
161     """Lookup and return a node from an RBTree.
163 $lx_rb_prev(node): Return the node at the given index.
164 If index is omitted, the root node is dereferenced and returned."""
169     def invoke(self, node):  argument
170         result = rb_prev(node)