examples/scripting/tree_utils.py

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