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
13typedef 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
23char *strip(char **word) {
24 char *start = *word;
25 int len = strlen(s: 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
47void insert(tree_node *root, char *word) {
48 if (root == NULL)
49 return;
50
51 int compare_value = strcmp(s1: word, s2: root->word);
52
53 if (compare_value == 0)
54 return;
55
56 if (compare_value < 0) {
57 if (root->left != NULL)
58 insert(root: root->left, word);
59 else {
60 tree_node *new_node = (tree_node *)malloc(size: sizeof(tree_node));
61 new_node->word = strdup(s: 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: root->right, word);
69 else {
70 tree_node *new_node = (tree_node *)malloc(size: sizeof(tree_node));
71 new_node->word = strdup(s: 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
82void populate_dictionary(tree_node **dictionary, char *filename) {
83 FILE *in_file;
84 char word[1024];
85
86 in_file = fopen(filename: filename, modes: "r");
87 if (in_file) {
88 while (fscanf(stream: in_file, format: "%s", word) == 1) {
89 char *new_word = (strdup(s: word));
90 new_word = strip(word: &new_word);
91 if (*dictionary == NULL) {
92 tree_node *new_node = (tree_node *)malloc(size: 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(root: *dictionary, word: 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
106int find_word(tree_node *dictionary, char *word) {
107 if (!word || !dictionary)
108 return 0;
109
110 int compare_value = strcmp(s1: word, s2: dictionary->word);
111
112 if (compare_value == 0)
113 return 1;
114 else if (compare_value < 0)
115 return find_word(dictionary: dictionary->left, word);
116 else
117 return find_word(dictionary: dictionary->right, word);
118}
119
120/* Print out the words in the binary search tree, in sorted order. */
121
122void print_tree(tree_node *dictionary) {
123 if (!dictionary)
124 return;
125
126 if (dictionary->left)
127 print_tree(dictionary: dictionary->left);
128
129 printf(format: "%s\n", dictionary->word);
130
131 if (dictionary->right)
132 print_tree(dictionary: dictionary->right);
133}
134
135int 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: &dictionary, filename);
148 fprintf(stdout, format: "Dictionary loaded.\nEnter search word: ");
149 while (!done && fgets(s: buffer, n: sizeof(buffer), stdin)) {
150 char *word = buffer;
151 int len = strlen(s: word);
152 int i;
153
154 for (i = 0; i < len; ++i)
155 word[i] = tolower(c: 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, format: "Yes!\n");
164 else
165 fprintf(stdout, format: "No!\n");
166
167 fprintf(stdout, format: "Enter search word: ");
168 }
169
170 fprintf(stdout, format: "\n");
171 return 0;
172}
173

source code of lldb/examples/scripting/dictionary.c