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 * btree currently doesn't have convenience functions for the simple tasks of
16 * "look up by key", "insert a key", and "remove a key". To insert or remove,
17 * you first have use btree_find* to position an iterator on the
18 * insertion/removal point, then call btree_insert_at or btree_remove_at using
19 * that iterator. Since a btree can hold multiple items with the same key,
20 * it isn't clear how the convenience functions should work yet. I'm open to
23 * A B-tree (not to be confused with a binary tree) is a data structure that
24 * performs insertion, removal, and lookup in O(log n) time per operation.
25 * Although B-trees are typically used for databases and filesystems, this is
26 * an in-memory implementation.
28 * Unlike functions like qsort, bsearch, and tsearch, btree does not take a
29 * comparison function. It takes a binary search function, which is
30 * theoretically equivalent but faster. Writing a binary search function
31 * is more difficult than writing a comparison function, so a macro is provided
32 * to make it much easier than doing either manually.
35 * #include <ccan/btree/btree.h>
47 * //Define the ordering function order_by_letter_set
48 * btree_search_implement
50 * order_by_letter_set,
52 * int c = strcmp(a->letter_set, b->letter_set),
57 * struct word *new_word(const char *line);
58 * char *chomp(char *str);
59 * char *make_letter_set(char *str);
61 * void insert_word(struct btree *btree, struct word *word)
63 * btree_iterator iter;
65 * //Position iterator after existing words with this letter set.
66 * btree_find_last(btree, word, iter);
68 * //Insert new word at iterator position.
69 * btree_insert_at(iter, word);
72 * void print_anagrams(struct btree *btree, char *line)
74 * btree_iterator iter, end;
77 * make_letter_set(line)
80 * //Find first matching word.
81 * if (!btree_find_first(btree, &key, iter)) {
82 * printf("\t(none)\n");
86 * btree_find_last(btree, &key, end);
88 * //Traverse matching words.
89 * for (; btree_deref(iter) && btree_cmp_iters(iter, end) < 0;
92 * struct word *word = iter->item;
93 * printf("\t%s\n", word->word);
97 * int destroy_word(struct word *word, void *ctx)
102 * free(word->letter_set);
108 * struct btree *read_dictionary(const char *filename)
113 * //Construct new btree with the ordering function order_by_letter_set .
114 * struct btree *btree = btree_new(order_by_letter_set);
116 * f = fopen(filename, "r");
120 * //Set the destroy callback so btree_free will automatically
121 * //free our items. Setting btree->destroy is optional.
122 * btree->destroy = (btree_action_t)destroy_word;
124 * while (fgets(line, sizeof(line), f)) {
125 * struct word *word = new_word(line);
128 * insert_word(btree, word);
141 * btree_delete(btree);
142 * fprintf(stderr, "%s: %s\n", filename, strerror(errno));
146 * int main(int argc, char *argv[])
148 * struct btree *btree;
153 * "Usage: %s dictionary-file\n"
155 * "\t%s /usr/share/dict/words\n"
157 * , argv[0], argv[0]);
161 * printf("Indexing...\n");
162 * btree = read_dictionary(argv[1]);
163 * printf("Dictionary has %ld words\n", (long)btree->count);
167 * if (!fgets(line, sizeof(line), stdin))
173 * printf("Anagrams of \"%s\":\n", line);
174 * print_anagrams(btree, line);
177 * printf("Cleaning up...\n");
178 * btree_delete(btree);
183 * struct word *new_word(const char *line)
186 * char *letter_set = make_letter_set(strdup(line));
188 * //Discard lines with no letters
189 * if (!*letter_set) {
194 * word = malloc(sizeof(struct word));
195 * word->word = chomp(strdup(line));
196 * word->letter_set = letter_set;
201 * //Remove trailing newline (if present).
202 * char *chomp(char *str)
204 * char *end = strchr(str, '\0') - 1;
205 * if (*str && *end == '\n')
210 * //Remove all characters but letters, make letters lowercase, and sort them.
211 * char *make_letter_set(char *str)
213 * size_t count[26] = {0};
217 * for (i=0; str[i]; i++) {
219 * if (c >= 'A' && c <= 'Z')
221 * if (c >= 'a' && c <= 'z')
225 * for (i = 0; i < 26; i++) {
226 * for (j = 0; j < count[i]; j++)
238 int main(int argc, char *argv[])
240 /* Expect exactly one argument */
244 if (strcmp(argv[1], "depends") == 0) {