]>
Commit | Line | Data |
---|---|---|
449ca0c9 SB |
1 | # SPDX-License-Identifier: GPL-2.0 |
2 | # | |
3 | # Copyright 2019 Google LLC. | |
4 | ||
5 | import gdb | |
6 | ||
7 | from linux import utils | |
8 | ||
9 | rb_root_type = utils.CachedType("struct rb_root") | |
10 | rb_node_type = utils.CachedType("struct rb_node") | |
11 | ||
12 | ||
13 | def 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 | ||
29 | def 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 | ||
45 | def rb_parent(node): | |
46 | parent = gdb.Value(node['__rb_parent_color'] & ~3) | |
47 | return parent.cast(rb_node_type.get_type().pointer()) | |
48 | ||
49 | ||
50 | def rb_empty_node(node): | |
51 | return node['__rb_parent_color'] == node.address | |
52 | ||
53 | ||
54 | def 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 | ||
77 | def 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 | ||
100 | class 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. | |
104 | If 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 | ||
117 | LxRbFirst() | |
118 | ||
119 | ||
120 | class 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. | |
124 | If 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 | ||
137 | LxRbLast() | |
138 | ||
139 | ||
140 | class 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. | |
144 | If 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 | ||
157 | LxRbNext() | |
158 | ||
159 | ||
160 | class 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. | |
164 | If 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 | ||
177 | LxRbPrev() |