]> git.ipfire.org Git - thirdparty/linux.git/blame - scripts/gdb/linux/rbtree.py
Merge tag 'io_uring-5.7-2020-05-22' of git://git.kernel.dk/linux-block
[thirdparty/linux.git] / scripts / gdb / linux / rbtree.py
CommitLineData
449ca0c9
SB
1# SPDX-License-Identifier: GPL-2.0
2#
3# Copyright 2019 Google LLC.
4
5import gdb
6
7from linux import utils
8
9rb_root_type = utils.CachedType("struct rb_root")
10rb_node_type = utils.CachedType("struct rb_node")
11
12
13def rb_first(root):
14 if root.type == rb_root_type.get_type():
50e36be1 15 node = root.address.cast(rb_root_type.get_type().pointer())
449ca0c9
SB
16 elif root.type != rb_root_type.get_type().pointer():
17 raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
18
19 node = root['rb_node']
20 if node is 0:
21 return None
22
23 while node['rb_left']:
24 node = node['rb_left']
25
26 return node
27
28
29def rb_last(root):
30 if root.type == rb_root_type.get_type():
50e36be1 31 node = root.address.cast(rb_root_type.get_type().pointer())
449ca0c9
SB
32 elif root.type != rb_root_type.get_type().pointer():
33 raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
34
35 node = root['rb_node']
36 if node is 0:
37 return None
38
39 while node['rb_right']:
40 node = node['rb_right']
41
42 return node
43
44
45def rb_parent(node):
46 parent = gdb.Value(node['__rb_parent_color'] & ~3)
47 return parent.cast(rb_node_type.get_type().pointer())
48
49
50def rb_empty_node(node):
51 return node['__rb_parent_color'] == node.address
52
53
54def rb_next(node):
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))
59
60 if rb_empty_node(node):
61 return None
62
63 if node['rb_right']:
64 node = node['rb_right']
65 while node['rb_left']:
66 node = node['rb_left']
67 return node
68
69 parent = rb_parent(node)
70 while parent and node == parent['rb_right']:
71 node = parent
72 parent = rb_parent(node)
73
74 return parent
75
76
77def rb_prev(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))
82
83 if rb_empty_node(node):
84 return None
85
86 if node['rb_left']:
87 node = node['rb_left']
88 while node['rb_right']:
89 node = node['rb_right']
90 return node.dereference()
91
92 parent = rb_parent(node)
93 while parent and node == parent['rb_left'].dereference():
94 node = parent
95 parent = rb_parent(node)
96
97 return parent
98
99
100class LxRbFirst(gdb.Function):
101 """Lookup and return a node from an RBTree
102
103$lx_rb_first(root): Return the node at the given index.
104If index is omitted, the root node is dereferenced and returned."""
105
106 def __init__(self):
107 super(LxRbFirst, self).__init__("lx_rb_first")
108
109 def invoke(self, root):
110 result = rb_first(root)
111 if result is None:
112 raise gdb.GdbError("No entry in tree")
113
114 return result
115
116
117LxRbFirst()
118
119
120class LxRbLast(gdb.Function):
121 """Lookup and return a node from an RBTree.
122
123$lx_rb_last(root): Return the node at the given index.
124If index is omitted, the root node is dereferenced and returned."""
125
126 def __init__(self):
127 super(LxRbLast, self).__init__("lx_rb_last")
128
129 def invoke(self, root):
130 result = rb_last(root)
131 if result is None:
132 raise gdb.GdbError("No entry in tree")
133
134 return result
135
136
137LxRbLast()
138
139
140class LxRbNext(gdb.Function):
141 """Lookup and return a node from an RBTree.
142
143$lx_rb_next(node): Return the node at the given index.
144If index is omitted, the root node is dereferenced and returned."""
145
146 def __init__(self):
147 super(LxRbNext, self).__init__("lx_rb_next")
148
149 def invoke(self, node):
150 result = rb_next(node)
151 if result is None:
152 raise gdb.GdbError("No entry in tree")
153
154 return result
155
156
157LxRbNext()
158
159
160class LxRbPrev(gdb.Function):
161 """Lookup and return a node from an RBTree.
162
163$lx_rb_prev(node): Return the node at the given index.
164If index is omitted, the root node is dereferenced and returned."""
165
166 def __init__(self):
167 super(LxRbPrev, self).__init__("lx_rb_prev")
168
169 def invoke(self, node):
170 result = rb_prev(node)
171 if result is None:
172 raise gdb.GdbError("No entry in tree")
173
174 return result
175
176
177LxRbPrev()