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 119
