]>
git.ipfire.org Git - thirdparty/linux.git/blob - scripts/gdb/linux/rbtree.py
1 # SPDX-License-Identifier: GPL-2.0
3 # Copyright 2019 Google LLC.
7 from linux
import utils
9 rb_root_type
= utils
.CachedType("struct rb_root")
10 rb_node_type
= utils
.CachedType("struct rb_node")
14 if root
.type == rb_root_type
.get_type():
15 node
= node
.address
.cast(rb_root_type
.get_type().pointer())
16 elif root
.type != rb_root_type
.get_type().pointer():
17 raise gdb
.GdbError("Must be struct rb_root not {}".format(root
.type))
19 node
= root
['rb_node']
23 while node
['rb_left']:
24 node
= node
['rb_left']
30 if root
.type == rb_root_type
.get_type():
31 node
= node
.address
.cast(rb_root_type
.get_type().pointer())
32 elif root
.type != rb_root_type
.get_type().pointer():
33 raise gdb
.GdbError("Must be struct rb_root not {}".format(root
.type))
35 node
= root
['rb_node']
39 while node
['rb_right']:
40 node
= node
['rb_right']
46 parent
= gdb
.Value(node
['__rb_parent_color'] & ~
3)
47 return parent
.cast(rb_node_type
.get_type().pointer())
50 def rb_empty_node(node
):
51 return node
['__rb_parent_color'] == node
.address
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
):
64 node
= node
['rb_right']
65 while node
['rb_left']:
66 node
= node
['rb_left']
69 parent
= rb_parent(node
)
70 while parent
and node
== parent
['rb_right']:
72 parent
= rb_parent(node
)
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
):
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():
95 parent
= rb_parent(node
)
100 class LxRbFirst(gdb
.Function
):
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."""
107 super(LxRbFirst
, self
).__init
__("lx_rb_first")
109 def invoke(self
, root
):
110 result
= rb_first(root
)
112 raise gdb
.GdbError("No entry in tree")
120 class LxRbLast(gdb
.Function
):
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."""
127 super(LxRbLast
, self
).__init
__("lx_rb_last")
129 def invoke(self
, root
):
130 result
= rb_last(root
)
132 raise gdb
.GdbError("No entry in tree")
140 class LxRbNext(gdb
.Function
):
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."""
147 super(LxRbNext
, self
).__init
__("lx_rb_next")
149 def invoke(self
, node
):
150 result
= rb_next(node
)
152 raise gdb
.GdbError("No entry in tree")
160 class LxRbPrev(gdb
.Function
):
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."""
167 super(LxRbPrev
, self
).__init
__("lx_rb_prev")
169 def invoke(self
, node
):
170 result
= rb_prev(node
)
172 raise gdb
.GdbError("No entry in tree")