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()