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():
15        node = root.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))
18
19    node = root['rb_node']
20    if node == 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():
31        node = root.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))
34
35    node = root['rb_node']
36    if node == 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()
178