135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice""" 235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice# ===-- tree_utils.py ---------------------------------------*- Python -*-===// 335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice# 435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice# The LLVM Compiler Infrastructure 535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice# 635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice# This file is distributed under the University of Illinois Open Source 735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice# License. See LICENSE.TXT for details. 835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice# 935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice# ===---------------------------------------------------------------------===// 1035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 1135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticetree_utils.py - A set of functions for examining binary 1235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticesearch trees, based on the example search tree defined in 1335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticedictionary.c. These functions contain calls to LLDB API 1435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticefunctions, and assume that the LLDB Python module has been 1535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticeimported. 1635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 1735393b11cc554aa718a5745c8830c2b89a8ec857Caroline TiceFor a thorough explanation of how the DFS function works, and 1835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticefor more information about dictionary.c go to 1935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticehttp://lldb.llvm.org/scripting.html 2035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice""" 2135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 2235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 2335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticedef DFS (root, word, cur_path): 2435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice """ 2535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice Recursively traverse a binary search tree containing 2635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice words sorted alphabetically, searching for a particular 2735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice word in the tree. Also maintains a string representing 2835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice the path from the root of the tree to the current node. 2935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice If the word is found in the tree, return the path string. 3035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice Otherwise return an empty string. 3135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 3235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice This function assumes the binary search tree is 3335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice the one defined in dictionary.c It uses LLDB API 3435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice functions to examine and traverse the tree nodes. 3535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice """ 3635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 3735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice # Get pointer field values out of node 'root' 3835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 3935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice root_word_ptr = root.GetChildMemberWithName ("word") 4035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice left_child_ptr = root.GetChildMemberWithName ("left") 4135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice right_child_ptr = root.GetChildMemberWithName ("right") 4235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 4335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice # Get the word out of the word pointer and strip off 4435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice # surrounding quotes (added by call to GetSummary). 4535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 4635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice root_word = root_word_ptr.GetSummary() 4735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice end = len (root_word) - 1 4835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice if root_word[0] == '"' and root_word[end] == '"': 4935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice root_word = root_word[1:end] 5035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice end = len (root_word) - 1 5135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice if root_word[0] == '\'' and root_word[end] == '\'': 5235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice root_word = root_word[1:end] 5335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 5435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice # Main depth first search 5535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 5635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice if root_word == word: 5735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice return cur_path 5835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice elif word < root_word: 5935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 6035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice # Check to see if left child is NULL 6135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 6235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice if left_child_ptr.GetValue() == None: 6335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice return "" 6435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice else: 6535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice cur_path = cur_path + "L" 6635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice return DFS (left_child_ptr, word, cur_path) 6735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice else: 6835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 6935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice # Check to see if right child is NULL 7035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 7135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice if right_child_ptr.GetValue() == None: 7235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice return "" 7335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice else: 7435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice cur_path = cur_path + "R" 7535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice return DFS (right_child_ptr, word, cur_path) 7635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 7735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 7835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticedef tree_size (root): 7935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice """ 8035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice Recursively traverse a binary search tree, counting 8135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice the nodes in the tree. Returns the final count. 8235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 8335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice This function assumes the binary search tree is 8435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice the one defined in dictionary.c It uses LLDB API 8535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice functions to examine and traverse the tree nodes. 8635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice """ 8735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice if (root.GetValue == None): 8835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice return 0 8935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 9035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice if (int (root.GetValue(), 16) == 0): 9135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice return 0 9235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 9335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice left_size = tree_size (root.GetChildAtIndex(1)); 9435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice right_size = tree_size (root.GetChildAtIndex(2)); 9535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 9635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice total_size = left_size + right_size + 1 9735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice return total_size 9835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 9935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 10035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Ticedef print_tree (root): 10135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice """ 10235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice Recursively traverse a binary search tree, printing out 10335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice the words at the nodes in alphabetical order (the 10435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice search order for the binary tree). 10535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 10635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice This function assumes the binary search tree is 10735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice the one defined in dictionary.c It uses LLDB API 10835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice functions to examine and traverse the tree nodes. 10935393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice """ 11035393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice if (root.GetChildAtIndex(1).GetValue() != None) and (int (root.GetChildAtIndex(1).GetValue(), 16) != 0): 11135393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice print_tree (root.GetChildAtIndex(1)) 11235393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 11335393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice print root.GetChildAtIndex(0).GetSummary() 11435393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 11535393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice if (root.GetChildAtIndex(2).GetValue() != None) and (int (root.GetChildAtIndex(2).GetValue(), 16) != 0): 11635393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice print_tree (root.GetChildAtIndex(2)) 11735393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 11835393b11cc554aa718a5745c8830c2b89a8ec857Caroline Tice 119