6 * btree - Efficient sorted associative container based on B-trees.
8 * This module provides an efficient in-memory lookup container that keeps a
9 * set of pointers sorted using a user-defined search function.
11 * This module supports insertion, removal, lookup, and traversal using an
12 * iterator system. Note that insertion and removal into/from a btree will
13 * invalidate all iterators pointing to it (including the one passed to the
14 * insertion or removal function).
16 * A B-tree (not to be confused with a binary tree) is a data structure that
17 * performs insertion, removal, and lookup in O(log n) time per operation.
18 * Although B-trees are typically used for databases and filesystems, this is
19 * an in-memory implementation.
21 * Unlike functions like qsort, bsearch, and tsearch, btree does not take a
22 * comparison function. It takes a binary search function, which is
23 * theoretically equivalent but faster. Writing a binary search function
24 * is more difficult than writing a comparison function, so a macro is provided
25 * to make it much easier than doing either manually.
28 * #include <ccan/btree/btree.h>
40 * //Define the ordering function order_by_letter_set
41 * static btree_search_implement
43 * order_by_letter_set,
45 * int c = strcmp(a->letter_set, b->letter_set),
50 * struct word *new_word(const char *line);
51 * char *chomp(char *str);
52 * char *make_letter_set(char *str);
54 * static void insert_word(struct btree *btree, struct word *word)
56 * btree_iterator iter;
58 * //Position iterator after existing words with this letter set.
59 * btree_find_last(btree, word, iter);
61 * //Insert new word at iterator position.
62 * btree_insert_at(iter, word);
65 * static void print_anagrams(struct btree *btree, char *line)
67 * btree_iterator iter, end;
70 * make_letter_set(line)
73 * //Find first matching word.
74 * if (!btree_find_first(btree, &key, iter)) {
75 * printf("\t(none)\n");
79 * btree_find_last(btree, &key, end);
81 * //Traverse matching words.
82 * for (; btree_deref(iter) && btree_cmp_iters(iter, end) < 0;
85 * struct word *word = iter->item;
86 * printf("\t%s\n", word->word);
90 * static int destroy_word(struct word *word, void *ctx)
95 * free(word->letter_set);
101 * static struct btree *read_dictionary(const char *filename)
106 * //Construct new btree with the ordering function order_by_letter_set .
107 * struct btree *btree = btree_new(order_by_letter_set);
109 * f = fopen(filename, "r");
113 * //Set the destroy callback so btree_free will automatically
114 * //free our items. Setting btree->destroy is optional.
115 * btree->destroy = (btree_action_t)destroy_word;
117 * while (fgets(line, sizeof(line), f)) {
118 * struct word *word = new_word(line);
121 * insert_word(btree, word);
134 * btree_delete(btree);
135 * fprintf(stderr, "%s: %s\n", filename, strerror(errno));
139 * int main(int argc, char *argv[])
141 * struct btree *btree;
146 * "Usage: %s dictionary-file\n"
148 * "\t%s /usr/share/dict/words\n"
150 * , argv[0], argv[0]);
154 * printf("Indexing...\n");
155 * btree = read_dictionary(argv[1]);
156 * printf("Dictionary has %ld words\n", (long)btree->count);
160 * if (!fgets(line, sizeof(line), stdin))
166 * printf("Anagrams of \"%s\":\n", line);
167 * print_anagrams(btree, line);
170 * printf("Cleaning up...\n");
171 * btree_delete(btree);
176 * struct word *new_word(const char *line)
179 * char *letter_set = make_letter_set(strdup(line));
181 * //Discard lines with no letters
182 * if (!*letter_set) {
187 * word = malloc(sizeof(struct word));
188 * word->word = chomp(strdup(line));
189 * word->letter_set = letter_set;
194 * //Remove trailing newline (if present).
195 * char *chomp(char *str)
197 * char *end = strchr(str, '\0') - 1;
198 * if (*str && *end == '\n')
203 * //Remove all characters but letters, make letters lowercase, and sort them.
204 * char *make_letter_set(char *str)
206 * size_t count[26] = {0};
210 * for (i=0; str[i]; i++) {
212 * if (c >= 'A' && c <= 'Z')
214 * if (c >= 'a' && c <= 'z')
218 * for (i = 0; i < 26; i++) {
219 * for (j = 0; j < count[i]; j++)
227 * Author: Joey Adams <joeyadams3.14159@gmail.com>
231 int main(int argc, char *argv[])
233 /* Expect exactly one argument */
237 if (strcmp(argv[1], "depends") == 0) {