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 10tree_utils.py - A set of functions for examining binary 11search trees, based on the example search tree defined in 12dictionary.c. These functions contain calls to LLDB API 13functions, and assume that the LLDB Python module has been 14imported. 15 16For a thorough explanation of how the DFS function works, and 17for more information about dictionary.c go to 18http://lldb.llvm.org/scripting.html 19""" 20 21 22def 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 59 # Check to see if left child is NULL 60 61 if left_child_ptr.GetValue() is None: 62 return "" 63 else: 64 cur_path = cur_path + "L" 65 return DFS(left_child_ptr, word, cur_path) 66 else: 67 68 # Check to see if right child is NULL 69 70 if right_child_ptr.GetValue() is None: 71 return "" 72 else: 73 cur_path = cur_path + "R" 74 return DFS(right_child_ptr, word, cur_path) 75 76 77def tree_size(root): 78 """ 79 Recursively traverse a binary search tree, counting 80 the nodes in the tree. Returns the final count. 81 82 This function assumes the binary search tree is 83 the one defined in dictionary.c It uses LLDB API 84 functions to examine and traverse the tree nodes. 85 """ 86 if (root.GetValue is None): 87 return 0 88 89 if (int(root.GetValue(), 16) == 0): 90 return 0 91 92 left_size = tree_size(root.GetChildAtIndex(1)) 93 right_size = tree_size(root.GetChildAtIndex(2)) 94 95 total_size = left_size + right_size + 1 96 return total_size 97 98 99def print_tree(root): 100 """ 101 Recursively traverse a binary search tree, printing out 102 the words at the nodes in alphabetical order (the 103 search order for the binary tree). 104 105 This function assumes the binary search tree is 106 the one defined in dictionary.c It uses LLDB API 107 functions to examine and traverse the tree nodes. 108 """ 109 if (root.GetChildAtIndex(1).GetValue() is not None) and ( 110 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() is not None) and ( 116 int(root.GetChildAtIndex(2).GetValue(), 16) != 0): 117 print_tree(root.GetChildAtIndex(2)) 118