1 # SPDX-License-Identifier: GPL-2.0
12 def rb_inorder_for_each(root):  argument
13     def inorder(node):  argument
14         if node:
15             yield from inorder(node['rb_left'])
16             yield node
17             yield from inorder(node['rb_right'])
19     yield from inorder(root['rb_node'])
21 def rb_inorder_for_each_entry(root, gdbtype, member):  argument
22     for node in rb_inorder_for_each(root):
23         yield utils.container_of(node, gdbtype, member)
25 def rb_first(root):  argument
26     if root.type == rb_root_type.get_type():
27         node = root.address.cast(rb_root_type.get_type().pointer())
28     elif root.type != rb_root_type.get_type().pointer():
29         raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
31     node = root['rb_node']
32     if node == 0:
35     while node['rb_left']:
36         node = node['rb_left']
38     return node
41 def rb_last(root):  argument
42     if root.type == rb_root_type.get_type():
43         node = root.address.cast(rb_root_type.get_type().pointer())
44     elif root.type != rb_root_type.get_type().pointer():
45         raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
47     node = root['rb_node']
48     if node == 0:
51     while node['rb_right']:
52         node = node['rb_right']
54     return node
57 def rb_parent(node):  argument
58     parent = gdb.Value(node['__rb_parent_color'] & ~3)
62 def rb_empty_node(node):  argument
63     return node['__rb_parent_color'] == node.address
66 def rb_next(node):  argument
67     if node.type == rb_node_type.get_type():
68         node = node.address.cast(rb_node_type.get_type().pointer())
69     elif node.type != rb_node_type.get_type().pointer():
70         raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
72     if rb_empty_node(node):
75     if node['rb_right']:
76         node = node['rb_right']
77         while node['rb_left']:
78             node = node['rb_left']
79         return node
81     parent = rb_parent(node)
82     while parent and node == parent['rb_right']:
83             node = parent
84             parent = rb_parent(node)
89 def rb_prev(node):  argument
90     if node.type == rb_node_type.get_type():
91         node = node.address.cast(rb_node_type.get_type().pointer())
92     elif node.type != rb_node_type.get_type().pointer():
93         raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
95     if rb_empty_node(node):
98     if node['rb_left']:
99         node = node['rb_left']
100         while node['rb_right']:
101             node = node['rb_right']
102         return node.dereference()
104     parent = rb_parent(node)
105     while parent and node == parent['rb_left'].dereference():
106             node = parent
107             parent = rb_parent(node)
113     """Lookup and return a node from an RBTree
115 $lx_rb_first(root): Return the node at the given index.
116 If index is omitted, the root node is dereferenced and returned."""
121     def invoke(self, root):  argument
122         result = rb_first(root)
133     """Lookup and return a node from an RBTree.
135 $lx_rb_last(root): Return the node at the given index.
136 If index is omitted, the root node is dereferenced and returned."""
141     def invoke(self, root):  argument
142         result = rb_last(root)
153     """Lookup and return a node from an RBTree.
155 $lx_rb_next(node): Return the node at the given index.
156 If index is omitted, the root node is dereferenced and returned."""
161     def invoke(self, node):  argument
162         result = rb_next(node)
173     """Lookup and return a node from an RBTree.
175 $lx_rb_prev(node): Return the node at the given index.
176 If index is omitted, the root node is dereferenced and returned."""
181     def invoke(self, node):  argument
182         result = rb_prev(node)