lldb/examples/scripting/dictionary.c

   1 //===-- dictionary.c ---------------------------------------------*- C -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===---------------------------------------------------------------------===//
   8 #include <ctype.h>
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12
  13 typedef struct tree_node {
  14   const char *word;
  15   struct tree_node *left;
  16   struct tree_node *right;
  17 } tree_node;
  18
  19 /* Given a char*, returns a substring that starts at the first
  20    alphabet character and ends at the last alphabet character, i.e. it
  21    strips off beginning or ending quotes, punctuation, etc. */
  22
  23 char *strip(char **word) {
  24   char *start = *word;
  25   int len = strlen(start);
  26   char *end = start + len - 1;
  27
  28   while ((start < end) && (!isalpha(start[0])))
  29     start++;
  30
  31   while ((end > start) && (!isalpha(end[0])))
  32     end--;
  33
  34   if (start > end)
  35     return NULL;
  36
  37   end[1] = '\0';
  38   *word = start;
  39
  40   return start;
  41 }
  42
  43 /* Given a binary search tree (sorted alphabetically by the word at
  44    each node), and a new word, inserts the word at the appropriate
  45    place in the tree.  */
  46
  47 void insert(tree_node *root, char *word) {
  48   if (root == NULL)
  49     return;
  50
  51   int compare_value = strcmp(word, root->word);
  52
  53   if (compare_value == 0)
  54     return;
  55
  56   if (compare_value < 0) {
  57     if (root->left != NULL)
  58       insert(root->left, word);
  59     else {
  60       tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
  61       new_node->word = strdup(word);
  62       new_node->left = NULL;
  63       new_node->right = NULL;
  64       root->left = new_node;
  65     }
  66   } else {
  67     if (root->right != NULL)
  68       insert(root->right, word);
  69     else {
  70       tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
  71       new_node->word = strdup(word);
  72       new_node->left = NULL;
  73       new_node->right = NULL;
  74       root->right = new_node;
  75     }
  76   }
  77 }
  78
  79 /* Read in a text file and storea all the words from the file in a
  80    binary search tree.  */
  81
  82 void populate_dictionary(tree_node **dictionary, char *filename) {
  83   FILE *in_file;
  84   char word[1024];
  85
  86   in_file = fopen(filename, "r");
  87   if (in_file) {
  88     while (fscanf(in_file, "%s", word) == 1) {
  89       char *new_word = (strdup(word));
  90       new_word = strip(&new_word);
  91       if (*dictionary == NULL) {
  92         tree_node *new_node = (tree_node *)malloc(sizeof(tree_node));
  93         new_node->word = new_word;
  94         new_node->left = NULL;
  95         new_node->right = NULL;
  96         *dictionary = new_node;
  97       } else
  98         insert(*dictionary, new_word);
  99     }
 100   }
 101 }
 102
 103 /* Given a binary search tree and a word, search for the word
 104    in the binary search tree.  */
 105
 106 int find_word(tree_node *dictionary, char *word) {
 107   if (!word || !dictionary)
 108     return 0;
 109
 110   int compare_value = strcmp(word, dictionary->word);
 111
 112   if (compare_value == 0)
 113     return 1;
 114   else if (compare_value < 0)
 115     return find_word(dictionary->left, word);
 116   else
 117     return find_word(dictionary->right, word);
 118 }
 119
 120 /* Print out the words in the binary search tree, in sorted order.  */
 121
 122 void print_tree(tree_node *dictionary) {
 123   if (!dictionary)
 124     return;
 125
 126   if (dictionary->left)
 127     print_tree(dictionary->left);
 128
 129   printf("%s\n", dictionary->word);
 130
 131   if (dictionary->right)
 132     print_tree(dictionary->right);
 133 }
 134
 135 int main(int argc, char **argv) {
 136   tree_node *dictionary = NULL;
 137   char buffer[1024];
 138   char *filename;
 139   int done = 0;
 140
 141   if (argc == 2)
 142     filename = argv[1];
 143
 144   if (!filename)
 145     return -1;
 146
 147   populate_dictionary(&dictionary, filename);
 148   fprintf(stdout, "Dictionary loaded.\nEnter search word: ");
 149   while (!done && fgets(buffer, sizeof(buffer), stdin)) {
 150     char *word = buffer;
 151     int len = strlen(word);
 152     int i;
 153
 154     for (i = 0; i < len; ++i)
 155       word[i] = tolower(word[i]);
 156
 157     if ((len > 0) && (word[len - 1] == '\n')) {
 158       word[len - 1] = '\0';
 159       len = len - 1;
 160     }
 161
 162     if (find_word(dictionary, word))
 163       fprintf(stdout, "Yes!\n");
 164     else
 165       fprintf(stdout, "No!\n");
 166
 167     fprintf(stdout, "Enter search word: ");
 168   }
 169
 170   fprintf(stdout, "\n");
 171   return 0;
 172 }