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
11tree_utils.py  - A set of functions for examining binary
12search trees, based on the example search tree defined in
13dictionary.c.  These functions contain calls to LLDB API
14functions, and assume that the LLDB Python module has been
15imported.
16
17For a thorough explanation of how the DFS function works, and
18for more information about dictionary.c go to
19http://lldb.llvm.org/scripting.html
20"""
21
22
23def 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
78def 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
100def 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