diff options
Diffstat (limited to 'examples/scripting')
| -rw-r--r-- | examples/scripting/dictionary.c | 200 | ||||
| -rwxr-xr-x | examples/scripting/tree_utils.py | 118 |
2 files changed, 318 insertions, 0 deletions
diff --git a/examples/scripting/dictionary.c b/examples/scripting/dictionary.c new file mode 100644 index 000000000000..a7e1390ccebd --- /dev/null +++ b/examples/scripting/dictionary.c @@ -0,0 +1,200 @@ +//===-- dictionary.c ---------------------------------------------*- C -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===---------------------------------------------------------------------===// +#include <stdlib.h> +#include <stdio.h> +#include <ctype.h> +#include <string.h> + +typedef struct tree_node +{ + const char *word; + struct tree_node *left; + struct tree_node *right; +} tree_node; + +/* Given a char*, returns a substring that starts at the first + alphabet character and ends at the last alphabet character, i.e. it + strips off beginning or ending quotes, punctuation, etc. */ + +char * +strip (char **word) +{ + char *start = *word; + int len = strlen (start); + char *end = start + len - 1; + + while ((start < end) && (!isalpha (start[0]))) + start++; + + while ((end > start) && (!isalpha (end[0]))) + end--; + + if (start > end) + return NULL; + + end[1] = '\0'; + *word = start; + + return start; +} + +/* Given a binary search tree (sorted alphabetically by the word at + each node), and a new word, inserts the word at the appropriate + place in the tree. */ + +void +insert (tree_node *root, char *word) +{ + if (root == NULL) + return; + + int compare_value = strcmp (word, root->word); + + if (compare_value == 0) + return; + + if (compare_value < 0) + { + if (root->left != NULL) + insert (root->left, word); + else + { + tree_node *new_node = (tree_node *) malloc (sizeof (tree_node)); + new_node->word = strdup (word); + new_node->left = NULL; + new_node->right = NULL; + root->left = new_node; + } + } + else + { + if (root->right != NULL) + insert (root->right, word); + else + { + tree_node *new_node = (tree_node *) malloc (sizeof (tree_node)); + new_node->word = strdup (word); + new_node->left = NULL; + new_node->right = NULL; + root->right = new_node; + } + } +} + +/* Read in a text file and storea all the words from the file in a + binary search tree. */ + +void +populate_dictionary (tree_node **dictionary, char *filename) +{ + FILE *in_file; + char word[1024]; + + in_file = fopen (filename, "r"); + if (in_file) + { + while (fscanf (in_file, "%s", word) == 1) + { + char *new_word = (strdup (word)); + new_word = strip (&new_word); + if (*dictionary == NULL) + { + tree_node *new_node = (tree_node *) malloc (sizeof (tree_node)); + new_node->word = new_word; + new_node->left = NULL; + new_node->right = NULL; + *dictionary = new_node; + } + else + insert (*dictionary, new_word); + } + } +} + +/* Given a binary search tree and a word, search for the word + in the binary search tree. */ + +int +find_word (tree_node *dictionary, char *word) +{ + if (!word || !dictionary) + return 0; + + int compare_value = strcmp (word, dictionary->word); + + if (compare_value == 0) + return 1; + else if (compare_value < 0) + return find_word (dictionary->left, word); + else + return find_word (dictionary->right, word); +} + +/* Print out the words in the binary search tree, in sorted order. */ + +void +print_tree (tree_node *dictionary) +{ + if (!dictionary) + return; + + if (dictionary->left) + print_tree (dictionary->left); + + printf ("%s\n", dictionary->word); + + + if (dictionary->right) + print_tree (dictionary->right); +} + + +int +main (int argc, char **argv) +{ + tree_node *dictionary = NULL; + char buffer[1024]; + char *filename; + int done = 0; + + if (argc == 2) + filename = argv[1]; + + if (!filename) + return -1; + + populate_dictionary (&dictionary, filename); + fprintf (stdout, "Dictionary loaded.\nEnter search word: "); + while (!done && fgets (buffer, sizeof(buffer), stdin)) + { + char *word = buffer; + int len = strlen (word); + int i; + + for (i = 0; i < len; ++i) + word[i] = tolower (word[i]); + + if ((len > 0) && (word[len-1] == '\n')) + { + word[len-1] = '\0'; + len = len - 1; + } + + if (find_word (dictionary, word)) + fprintf (stdout, "Yes!\n"); + else + fprintf (stdout, "No!\n"); + + fprintf (stdout, "Enter search word: "); + } + + fprintf (stdout, "\n"); + return 0; +} + diff --git a/examples/scripting/tree_utils.py b/examples/scripting/tree_utils.py new file mode 100755 index 000000000000..e83f516ab580 --- /dev/null +++ b/examples/scripting/tree_utils.py @@ -0,0 +1,118 @@ +""" +# ===-- tree_utils.py ---------------------------------------*- Python -*-===// +# +# The LLVM Compiler Infrastructure +# +# This file is distributed under the University of Illinois Open Source +# License. See LICENSE.TXT for details. +# +# ===---------------------------------------------------------------------===// + +tree_utils.py - A set of functions for examining binary +search trees, based on the example search tree defined in +dictionary.c. These functions contain calls to LLDB API +functions, and assume that the LLDB Python module has been +imported. + +For a thorough explanation of how the DFS function works, and +for more information about dictionary.c go to +http://lldb.llvm.org/scripting.html +""" + + +def DFS (root, word, cur_path): + """ + Recursively traverse a binary search tree containing + words sorted alphabetically, searching for a particular + word in the tree. Also maintains a string representing + the path from the root of the tree to the current node. + If the word is found in the tree, return the path string. + Otherwise return an empty string. + + This function assumes the binary search tree is + the one defined in dictionary.c It uses LLDB API + functions to examine and traverse the tree nodes. + """ + + # Get pointer field values out of node 'root' + + root_word_ptr = root.GetChildMemberWithName ("word") + left_child_ptr = root.GetChildMemberWithName ("left") + right_child_ptr = root.GetChildMemberWithName ("right") + + # Get the word out of the word pointer and strip off + # surrounding quotes (added by call to GetSummary). + + root_word = root_word_ptr.GetSummary() + end = len (root_word) - 1 + if root_word[0] == '"' and root_word[end] == '"': + root_word = root_word[1:end] + end = len (root_word) - 1 + if root_word[0] == '\'' and root_word[end] == '\'': + root_word = root_word[1:end] + + # Main depth first search + + if root_word == word: + return cur_path + elif word < root_word: + + # Check to see if left child is NULL + + if left_child_ptr.GetValue() == None: + return "" + else: + cur_path = cur_path + "L" + return DFS (left_child_ptr, word, cur_path) + else: + + # Check to see if right child is NULL + + if right_child_ptr.GetValue() == None: + return "" + else: + cur_path = cur_path + "R" + return DFS (right_child_ptr, word, cur_path) + + +def tree_size (root): + """ + Recursively traverse a binary search tree, counting + the nodes in the tree. Returns the final count. + + This function assumes the binary search tree is + the one defined in dictionary.c It uses LLDB API + functions to examine and traverse the tree nodes. + """ + if (root.GetValue == None): + return 0 + + if (int (root.GetValue(), 16) == 0): + return 0 + + left_size = tree_size (root.GetChildAtIndex(1)); + right_size = tree_size (root.GetChildAtIndex(2)); + + total_size = left_size + right_size + 1 + return total_size + + +def print_tree (root): + """ + Recursively traverse a binary search tree, printing out + the words at the nodes in alphabetical order (the + search order for the binary tree). + + This function assumes the binary search tree is + the one defined in dictionary.c It uses LLDB API + functions to examine and traverse the tree nodes. + """ + if (root.GetChildAtIndex(1).GetValue() != None) and (int (root.GetChildAtIndex(1).GetValue(), 16) != 0): + print_tree (root.GetChildAtIndex(1)) + + print root.GetChildAtIndex(0).GetSummary() + + if (root.GetChildAtIndex(2).GetValue() != None) and (int (root.GetChildAtIndex(2).GetValue(), 16) != 0): + print_tree (root.GetChildAtIndex(2)) + + |