gdb/linux/rbtree.py

0001 # SPDX-License-Identifier: GPL-2.0
0002 #
0003 # Copyright 2019 Google LLC.
0004
0005 import gdb
0006
0007 from linux import utils
0008
0009 rb_root_type = utils.CachedType("struct rb_root")
0010 rb_node_type = utils.CachedType("struct rb_node")
0011
0012
0013 def rb_first(root):
0014     if root.type == rb_root_type.get_type():
0015         node = root.address.cast(rb_root_type.get_type().pointer())
0016     elif root.type != rb_root_type.get_type().pointer():
0017         raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
0018
0019     node = root['rb_node']
0020     if node == 0:
0021         return None
0022
0023     while node['rb_left']:
0024         node = node['rb_left']
0025
0026     return node
0027
0028
0029 def rb_last(root):
0030     if root.type == rb_root_type.get_type():
0031         node = root.address.cast(rb_root_type.get_type().pointer())
0032     elif root.type != rb_root_type.get_type().pointer():
0033         raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
0034
0035     node = root['rb_node']
0036     if node == 0:
0037         return None
0038
0039     while node['rb_right']:
0040         node = node['rb_right']
0041
0042     return node
0043
0044
0045 def rb_parent(node):
0046     parent = gdb.Value(node['__rb_parent_color'] & ~3)
0047     return parent.cast(rb_node_type.get_type().pointer())
0048
0049
0050 def rb_empty_node(node):
0051     return node['__rb_parent_color'] == node.address
0052
0053
0054 def rb_next(node):
0055     if node.type == rb_node_type.get_type():
0056         node = node.address.cast(rb_node_type.get_type().pointer())
0057     elif node.type != rb_node_type.get_type().pointer():
0058         raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
0059
0060     if rb_empty_node(node):
0061         return None
0062
0063     if node['rb_right']:
0064         node = node['rb_right']
0065         while node['rb_left']:
0066             node = node['rb_left']
0067         return node
0068
0069     parent = rb_parent(node)
0070     while parent and node == parent['rb_right']:
0071             node = parent
0072             parent = rb_parent(node)
0073
0074     return parent
0075
0076
0077 def rb_prev(node):
0078     if node.type == rb_node_type.get_type():
0079         node = node.address.cast(rb_node_type.get_type().pointer())
0080     elif node.type != rb_node_type.get_type().pointer():
0081         raise gdb.GdbError("Must be struct rb_node not {}".format(node.type))
0082
0083     if rb_empty_node(node):
0084         return None
0085
0086     if node['rb_left']:
0087         node = node['rb_left']
0088         while node['rb_right']:
0089             node = node['rb_right']
0090         return node.dereference()
0091
0092     parent = rb_parent(node)
0093     while parent and node == parent['rb_left'].dereference():
0094             node = parent
0095             parent = rb_parent(node)
0096
0097     return parent
0098
0099
0100 class LxRbFirst(gdb.Function):
0101     """Lookup and return a node from an RBTree
0102
0103 $lx_rb_first(root): Return the node at the given index.
0104 If index is omitted, the root node is dereferenced and returned."""
0105
0106     def __init__(self):
0107         super(LxRbFirst, self).__init__("lx_rb_first")
0108
0109     def invoke(self, root):
0110         result = rb_first(root)
0111         if result is None:
0112             raise gdb.GdbError("No entry in tree")
0113
0114         return result
0115
0116
0117 LxRbFirst()
0118
0119
0120 class LxRbLast(gdb.Function):
0121     """Lookup and return a node from an RBTree.
0122
0123 $lx_rb_last(root): Return the node at the given index.
0124 If index is omitted, the root node is dereferenced and returned."""
0125
0126     def __init__(self):
0127         super(LxRbLast, self).__init__("lx_rb_last")
0128
0129     def invoke(self, root):
0130         result = rb_last(root)
0131         if result is None:
0132             raise gdb.GdbError("No entry in tree")
0133
0134         return result
0135
0136
0137 LxRbLast()
0138
0139
0140 class LxRbNext(gdb.Function):
0141     """Lookup and return a node from an RBTree.
0142
0143 $lx_rb_next(node): Return the node at the given index.
0144 If index is omitted, the root node is dereferenced and returned."""
0145
0146     def __init__(self):
0147         super(LxRbNext, self).__init__("lx_rb_next")
0148
0149     def invoke(self, node):
0150         result = rb_next(node)
0151         if result is None:
0152             raise gdb.GdbError("No entry in tree")
0153
0154         return result
0155
0156
0157 LxRbNext()
0158
0159
0160 class LxRbPrev(gdb.Function):
0161     """Lookup and return a node from an RBTree.
0162
0163 $lx_rb_prev(node): Return the node at the given index.
0164 If index is omitted, the root node is dereferenced and returned."""
0165
0166     def __init__(self):
0167         super(LxRbPrev, self).__init__("lx_rb_prev")
0168
0169     def invoke(self, node):
0170         result = rb_prev(node)
0171         if result is None:
0172             raise gdb.GdbError("No entry in tree")
0173
0174         return result
0175
0176
0177 LxRbPrev()