5 * btree - Efficient sorted associative container based on B-trees.
7 * This module provides an efficient in-memory lookup container that keeps a
8 * set of pointers sorted using a user-defined search function.
10 * This module supports insertion, removal, lookup, and traversal using an
11 * iterator system. Note that insertion and removal into/from a btree will
12 * invalidate all iterators pointing to it (including the one passed to the
13 * insertion or removal function).
15 * A B-tree (not to be confused with a binary tree) is a data structure that
16 * performs insertion, removal, and lookup in O(log n) time per operation.
17 * Although B-trees are typically used for databases and filesystems, this is
18 * an in-memory implementation.
20 * Unlike functions like qsort, bsearch, and tsearch, btree does not take a
21 * comparison function. It takes a binary search function, which is
22 * theoretically equivalent but faster. Writing a binary search function
23 * is more difficult than writing a comparison function, so a macro is provided
24 * to make it much easier than doing either manually.
27 * #include <ccan/btree/btree.h>
39 * //Define the ordering function order_by_letter_set
40 * btree_search_implement
42 * order_by_letter_set,
44 * int c = strcmp(a->letter_set, b->letter_set),
49 * struct word *new_word(const char *line);
50 * char *chomp(char *str);
51 * char *make_letter_set(char *str);
53 * void insert_word(struct btree *btree, struct word *word)
55 * btree_iterator iter;
57 * //Position iterator after existing words with this letter set.
58 * btree_find_last(btree, word, iter);
60 * //Insert new word at iterator position.
61 * btree_insert_at(iter, word);
64 * void print_anagrams(struct btree *btree, char *line)
66 * btree_iterator iter, end;
69 * make_letter_set(line)
72 * //Find first matching word.
73 * if (!btree_find_first(btree, &key, iter)) {
74 * printf("\t(none)\n");
78 * btree_find_last(btree, &key, end);
80 * //Traverse matching words.
81 * for (; btree_deref(iter) && btree_cmp_iters(iter, end) < 0;
84 * struct word *word = iter->item;
85 * printf("\t%s\n", word->word);
89 * int destroy_word(struct word *word, void *ctx)
94 * free(word->letter_set);
100 * struct btree *read_dictionary(const char *filename)
105 * //Construct new btree with the ordering function order_by_letter_set .
106 * struct btree *btree = btree_new(order_by_letter_set);
108 * f = fopen(filename, "r");
112 * //Set the destroy callback so btree_free will automatically
113 * //free our items. Setting btree->destroy is optional.
114 * btree->destroy = (btree_action_t)destroy_word;
116 * while (fgets(line, sizeof(line), f)) {
117 * struct word *word = new_word(line);
120 * insert_word(btree, word);
133 * btree_delete(btree);
134 * fprintf(stderr, "%s: %s\n", filename, strerror(errno));
138 * int main(int argc, char *argv[])
140 * struct btree *btree;
145 * "Usage: %s dictionary-file\n"
147 * "\t%s /usr/share/dict/words\n"
149 * , argv[0], argv[0]);
153 * printf("Indexing...\n");
154 * btree = read_dictionary(argv[1]);
155 * printf("Dictionary has %ld words\n", (long)btree->count);
159 * if (!fgets(line, sizeof(line), stdin))
165 * printf("Anagrams of \"%s\":\n", line);
166 * print_anagrams(btree, line);
169 * printf("Cleaning up...\n");
170 * btree_delete(btree);
175 * struct word *new_word(const char *line)
178 * char *letter_set = make_letter_set(strdup(line));
180 * //Discard lines with no letters
181 * if (!*letter_set) {
186 * word = malloc(sizeof(struct word));
187 * word->word = chomp(strdup(line));
188 * word->letter_set = letter_set;
193 * //Remove trailing newline (if present).
194 * char *chomp(char *str)
196 * char *end = strchr(str, '\0') - 1;
197 * if (*str && *end == '\n')
202 * //Remove all characters but letters, make letters lowercase, and sort them.
203 * char *make_letter_set(char *str)
205 * size_t count[26] = {0};
209 * for (i=0; str[i]; i++) {
211 * if (c >= 'A' && c <= 'Z')
213 * if (c >= 'a' && c <= 'z')
217 * for (i = 0; i < 26; i++) {
218 * for (j = 0; j < count[i]; j++)
230 int main(int argc, char *argv[])
232 /* Expect exactly one argument */
236 if (strcmp(argv[1], "depends") == 0) {