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
21from __future__ import print_function
22
23
24def DFS(root, word, cur_path):
25    """
26    Recursively traverse a binary search tree containing
27    words sorted alphabetically, searching for a particular
28    word in the tree.  Also maintains a string representing
29    the path from the root of the tree to the current node.
30    If the word is found in the tree, return the path string.
31    Otherwise return an empty string.
32
33    This function assumes the binary search tree is
34    the one defined in dictionary.c  It uses LLDB API
35    functions to examine and traverse the tree nodes.
36    """
37
38    # Get pointer field values out of node 'root'
39
40    root_word_ptr = root.GetChildMemberWithName("word")
41    left_child_ptr = root.GetChildMemberWithName("left")
42    right_child_ptr = root.GetChildMemberWithName("right")
43
44    # Get the word out of the word pointer and strip off
45    # surrounding quotes (added by call to GetSummary).
46
47    root_word = root_word_ptr.GetSummary()
48    end = len(root_word) - 1
49    if root_word[0] == '"' and root_word[end] == '"':
50        root_word = root_word[1:end]
51    end = len(root_word) - 1
52    if root_word[0] == '\'' and root_word[end] == '\'':
53        root_word = root_word[1:end]
54
55    # Main depth first search
56
57    if root_word == word:
58        return cur_path
59    elif word < root_word:
60
61        # Check to see if left child is NULL
62
63        if left_child_ptr.GetValue() is None:
64            return ""
65        else:
66            cur_path = cur_path + "L"
67            return DFS(left_child_ptr, word, cur_path)
68    else:
69
70        # Check to see if right child is NULL
71
72        if right_child_ptr.GetValue() is None:
73            return ""
74        else:
75            cur_path = cur_path + "R"
76            return DFS(right_child_ptr, word, cur_path)
77
78
79def tree_size(root):
80    """
81    Recursively traverse a binary search tree, counting
82    the nodes in the tree.  Returns the final count.
83
84    This function assumes the binary search tree is
85    the one defined in dictionary.c  It uses LLDB API
86    functions to examine and traverse the tree nodes.
87    """
88    if (root.GetValue is None):
89        return 0
90
91    if (int(root.GetValue(), 16) == 0):
92        return 0
93
94    left_size = tree_size(root.GetChildAtIndex(1))
95    right_size = tree_size(root.GetChildAtIndex(2))
96
97    total_size = left_size + right_size + 1
98    return total_size
99
100
101def print_tree(root):
102    """
103    Recursively traverse a binary search tree, printing out
104    the words at the nodes in alphabetical order (the
105    search order for the binary tree).
106
107    This function assumes the binary search tree is
108    the one defined in dictionary.c  It uses LLDB API
109    functions to examine and traverse the tree nodes.
110    """
111    if (root.GetChildAtIndex(1).GetValue() is not None) and (
112            int(root.GetChildAtIndex(1).GetValue(), 16) != 0):
113        print_tree(root.GetChildAtIndex(1))
114
115    print(root.GetChildAtIndex(0).GetSummary())
116
117    if (root.GetChildAtIndex(2).GetValue() is not None) and (
118            int(root.GetChildAtIndex(2).GetValue(), 16) != 0):
119        print_tree(root.GetChildAtIndex(2))
120