lldb/examples/scripting/tree_utils.py

   1 """
   2 # ===-- tree_utils.py ---------------------------------------*- Python -*-===//
   3 #
   4 # Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 # See https://llvm.org/LICENSE.txt for license information.
   6 # SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 #
   8 # ===---------------------------------------------------------------------===//
   9
  10 tree_utils.py  - A set of functions for examining binary
  11 search trees, based on the example search tree defined in
  12 dictionary.c.  These functions contain calls to LLDB API
  13 functions, and assume that the LLDB Python module has been
  14 imported.
  15
  16 For a thorough explanation of how the DFS function works, and
  17 for more information about dictionary.c go to
  18 http://lldb.llvm.org/scripting.html
  19 """
  20
  21
  22 def DFS(root, word, cur_path):
  23     """
  24     Recursively traverse a binary search tree containing
  25     words sorted alphabetically, searching for a particular
  26     word in the tree.  Also maintains a string representing
  27     the path from the root of the tree to the current node.
  28     If the word is found in the tree, return the path string.
  29     Otherwise return an empty string.
  30
  31     This function assumes the binary search tree is
  32     the one defined in dictionary.c  It uses LLDB API
  33     functions to examine and traverse the tree nodes.
  34     """
  35
  36     # Get pointer field values out of node 'root'
  37
  38     root_word_ptr = root.GetChildMemberWithName("word")
  39     left_child_ptr = root.GetChildMemberWithName("left")
  40     right_child_ptr = root.GetChildMemberWithName("right")
  41
  42     # Get the word out of the word pointer and strip off
  43     # surrounding quotes (added by call to GetSummary).
  44
  45     root_word = root_word_ptr.GetSummary()
  46     end = len(root_word) - 1
  47     if root_word[0] == '"' and root_word[end] == '"':
  48         root_word = root_word[1:end]
  49     end = len(root_word) - 1
  50     if root_word[0] == "'" and root_word[end] == "'":
  51         root_word = root_word[1:end]
  52
  53     # Main depth first search
  54
  55     if root_word == word:
  56         return cur_path
  57     elif word < root_word:
  58         # Check to see if left child is NULL
  59
  60         if left_child_ptr.GetValue() is None:
  61             return ""
  62         else:
  63             cur_path = cur_path + "L"
  64             return DFS(left_child_ptr, word, cur_path)
  65     else:
  66         # Check to see if right child is NULL
  67
  68         if right_child_ptr.GetValue() is None:
  69             return ""
  70         else:
  71             cur_path = cur_path + "R"
  72             return DFS(right_child_ptr, word, cur_path)
  73
  74
  75 def tree_size(root):
  76     """
  77     Recursively traverse a binary search tree, counting
  78     the nodes in the tree.  Returns the final count.
  79
  80     This function assumes the binary search tree is
  81     the one defined in dictionary.c  It uses LLDB API
  82     functions to examine and traverse the tree nodes.
  83     """
  84     if root.GetValue is None:
  85         return 0
  86
  87     if int(root.GetValue(), 16) == 0:
  88         return 0
  89
  90     left_size = tree_size(root.GetChildAtIndex(1))
  91     right_size = tree_size(root.GetChildAtIndex(2))
  92
  93     total_size = left_size + right_size + 1
  94     return total_size
  95
  96
  97 def print_tree(root):
  98     """
  99     Recursively traverse a binary search tree, printing out
 100     the words at the nodes in alphabetical order (the
 101     search order for the binary tree).
 102
 103     This function assumes the binary search tree is
 104     the one defined in dictionary.c  It uses LLDB API
 105     functions to examine and traverse the tree nodes.
 106     """
 107     if (root.GetChildAtIndex(1).GetValue() is not None) and (
 108         int(root.GetChildAtIndex(1).GetValue(), 16) != 0
 109     ):
 110         print_tree(root.GetChildAtIndex(1))
 111
 112     print(root.GetChildAtIndex(0).GetSummary())
 113
 114     if (root.GetChildAtIndex(2).GetValue() is not None) and (
 115         int(root.GetChildAtIndex(2).GetValue(), 16) != 0
 116     ):
 117         print_tree(root.GetChildAtIndex(2))