118 lines · python
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-exception7#8# ===---------------------------------------------------------------------===//9 10tree_utils.py - A set of functions for examining binary11search trees, based on the example search tree defined in12dictionary.c. These functions contain calls to LLDB API13functions, and assume that the LLDB Python module has been14imported.15 16For a thorough explanation of how the DFS function works, and17for more information about dictionary.c go to18http://lldb.llvm.org/scripting.html19"""20 21 22def DFS(root, word, cur_path):23 """24 Recursively traverse a binary search tree containing25 words sorted alphabetically, searching for a particular26 word in the tree. Also maintains a string representing27 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 is32 the one defined in dictionary.c It uses LLDB API33 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 off43 # surrounding quotes (added by call to GetSummary).44 45 root_word = root_word_ptr.GetSummary()46 end = len(root_word) - 147 if root_word[0] == '"' and root_word[end] == '"':48 root_word = root_word[1:end]49 end = len(root_word) - 150 if root_word[0] == "'" and root_word[end] == "'":51 root_word = root_word[1:end]52 53 # Main depth first search54 55 if root_word == word:56 return cur_path57 elif word < root_word:58 # Check to see if left child is NULL59 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 NULL67 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 75def tree_size(root):76 """77 Recursively traverse a binary search tree, counting78 the nodes in the tree. Returns the final count.79 80 This function assumes the binary search tree is81 the one defined in dictionary.c It uses LLDB API82 functions to examine and traverse the tree nodes.83 """84 if root.GetValue is None:85 return 086 87 if int(root.GetValue(), 16) == 0:88 return 089 90 left_size = tree_size(root.GetChildAtIndex(1))91 right_size = tree_size(root.GetChildAtIndex(2))92 93 total_size = left_size + right_size + 194 return total_size95 96 97def print_tree(root):98 """99 Recursively traverse a binary search tree, printing out100 the words at the nodes in alphabetical order (the101 search order for the binary tree).102 103 This function assumes the binary search tree is104 the one defined in dictionary.c It uses LLDB API105 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) != 0109 ):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) != 0116 ):117 print_tree(root.GetChildAtIndex(2))118