1 # SPDX-License-Identifier: GPL-2.0
20 def is_internal_node(node):  argument
22 …return ((node.cast(long_type) & constants.LX_RADIX_TREE_ENTRY_MASK) == constants.LX_RADIX_TREE_INT…
24 def entry_to_node(node):  argument
26     node_type = node.type
27     indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INTERNAL_NODE
30 def node_maxindex(node):  argument
31     return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
33 def lookup(root, index):  argument
34     if root.type == radix_tree_root_type.get_type().pointer():
35         node = root.dereference()
36     elif root.type != radix_tree_root_type.get_type():
38                            .format(radix_tree_root_type.get_type(), root.type))
40     node = root['xa_head']
41     if node == 0:
44     if not (is_internal_node(node)):
47         return node
49     node = entry_to_node(node)
50     maxindex = node_maxindex(node)
55     shift = node['shift'] + constants.LX_RADIX_TREE_MAP_SHIFT
58         offset = (index >> node['shift']) & constants.LX_RADIX_TREE_MAP_MASK
59         slot = node['slots'][offset]
64         node = slot.cast(node.type.pointer()).dereference()
65         if node == 0:
68         shift -= constants.LX_RADIX_TREE_MAP_SHIFT
72     return node
75     """ Lookup and return a node from a RadixTree.
77 $lx_radix_tree_lookup(root_node [, index]): Return the node at the given index.
78 If index is omitted, the root node is dereference and returned."""
83     def invoke(self, root, index=0):  argument
84         result = lookup(root, index)