diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2019-08-20 18:01:57 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2019-08-20 18:01:57 +0000 |
commit | 88c643b6fec27eec436c8d138fee6346e92337d6 (patch) | |
tree | 82cd13b2f3cde1c9e5f79689ba4e6ba67694843f /examples/scripting | |
parent | 94994d372d014ce4c8758b9605d63fae651bd8aa (diff) |
Notes
Diffstat (limited to 'examples/scripting')
-rw-r--r-- | examples/scripting/dictionary.c | 173 | ||||
-rwxr-xr-x | examples/scripting/tree_utils.py | 118 |
2 files changed, 0 insertions, 291 deletions
diff --git a/examples/scripting/dictionary.c b/examples/scripting/dictionary.c deleted file mode 100644 index 260eab486e1b..000000000000 --- a/examples/scripting/dictionary.c +++ /dev/null @@ -1,173 +0,0 @@ -//===-- 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 <ctype.h> -#include <stdio.h> -#include <stdlib.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 deleted file mode 100755 index a4d1645d7350..000000000000 --- a/examples/scripting/tree_utils.py +++ /dev/null @@ -1,118 +0,0 @@ -""" -# ===-- 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() is 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() is 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 is 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() is not None) and ( - int(root.GetChildAtIndex(1).GetValue(), 16) != 0): - print_tree(root.GetChildAtIndex(1)) - - print root.GetChildAtIndex(0).GetSummary() - - if (root.GetChildAtIndex(2).GetValue() is not None) and ( - int(root.GetChildAtIndex(2).GetValue(), 16) != 0): - print_tree(root.GetChildAtIndex(2)) |