X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fbtree%2F_info;fp=ccan%2Fbtree%2F_info;h=2b81dafbe4e0cd6f7f3e016e24ca186ad7470876;hb=8f7447e48f6405a083919f3d6b591eb7dfbc6a9f;hp=0000000000000000000000000000000000000000;hpb=5008de765e1c1550aad1b3697713f7549774a9c9;p=ccan diff --git a/ccan/btree/_info b/ccan/btree/_info new file mode 100644 index 00000000..2b81dafb --- /dev/null +++ b/ccan/btree/_info @@ -0,0 +1,250 @@ +#include +#include "config.h" + +/** + * btree - Efficient sorted associative container based on B-trees. + * + * This module provides an efficient in-memory lookup container that keeps a + * set of pointers sorted using a user-defined search function. + * + * This module supports insertion, removal, lookup, and traversal using an + * iterator system. Note that insertion and removal into/from a btree will + * invalidate all iterators pointing to it (including the one passed to the + * insertion or removal function). + * + * btree currently doesn't have convenience functions for the simple tasks of + * "look up by key", "insert a key", and "remove a key". To insert or remove, + * you first have use btree_find* to position an iterator on the + * insertion/removal point, then call btree_insert_at or btree_remove_at using + * that iterator. Since a btree can hold multiple items with the same key, + * it isn't clear how the convenience functions should work yet. I'm open to + * suggestions. + * + * A B-tree (not to be confused with a binary tree) is a data structure that + * performs insertion, removal, and lookup in O(log n) time per operation. + * Although B-trees are typically used for databases and filesystems, this is + * an in-memory implementation. + * + * Unlike functions like qsort, bsearch, and tsearch, btree does not take a + * comparison function. It takes a binary search function, which is + * theoretically equivalent but faster. Writing a binary search function + * is more difficult than writing a comparison function, so a macro is provided + * to make it much easier than doing either manually. + * + * Example: + * #include + * + * #include + * #include + * #include + * #include + * + * struct word { + * char *word; + * char *letter_set; + * }; + * + * //Define the ordering function order_by_letter_set + * btree_search_implement + * ( + * order_by_letter_set, + * struct word *, + * int c = strcmp(a->letter_set, b->letter_set), + * c == 0, + * c < 0 + * ) + * + * struct word *new_word(const char *line); + * char *chomp(char *str); + * char *make_letter_set(char *str); + * + * void insert_word(struct btree *btree, struct word *word) + * { + * btree_iterator iter; + * + * //Position iterator after existing words with this letter set. + * btree_find_last(btree, word, iter); + * + * //Insert new word at iterator position. + * btree_insert_at(iter, word); + * } + * + * void print_anagrams(struct btree *btree, char *line) + * { + * btree_iterator iter, end; + * struct word key = { + * NULL, + * make_letter_set(line) + * }; + * + * //Find first matching word. + * if (!btree_find_first(btree, &key, iter)) { + * printf("\t(none)\n"); + * return; + * } + * + * btree_find_last(btree, &key, end); + * + * //Traverse matching words. + * for (; btree_deref(iter) && btree_cmp_iters(iter, end) < 0; + * btree_next(iter)) + * { + * struct word *word = iter->item; + * printf("\t%s\n", word->word); + * } + * } + * + * int destroy_word(struct word *word, void *ctx) + * { + * (void) ctx; + * + * free(word->word); + * free(word->letter_set); + * free(word); + * + * return 1; + * } + * + * struct btree *read_dictionary(const char *filename) + * { + * FILE *f; + * char line[256]; + * + * //Construct new btree with the ordering function order_by_letter_set . + * struct btree *btree = btree_new(order_by_letter_set); + * + * f = fopen(filename, "r"); + * if (!f) + * goto fail; + * + * //Set the destroy callback so btree_free will automatically + * //free our items. Setting btree->destroy is optional. + * btree->destroy = (btree_action_t)destroy_word; + * + * while (fgets(line, sizeof(line), f)) { + * struct word *word = new_word(line); + * if (!word) + * continue; + * insert_word(btree, word); + * } + * + * if (ferror(f)) { + * fclose(f); + * goto fail; + * } + * if (fclose(f)) + * goto fail; + * + * return btree; + * + * fail: + * btree_delete(btree); + * fprintf(stderr, "%s: %s\n", filename, strerror(errno)); + * return NULL; + * } + * + * int main(int argc, char *argv[]) + * { + * struct btree *btree; + * char line[256]; + * + * if (argc != 2) { + * fprintf(stderr, + * "Usage: %s dictionary-file\n" + * "Example:\n" + * "\t%s /usr/share/dict/words\n" + * "\n" + * , argv[0], argv[0]); + * return 1; + * } + * + * printf("Indexing...\n"); + * btree = read_dictionary(argv[1]); + * printf("Dictionary has %ld words\n", (long)btree->count); + * + * for (;;) { + * printf("> "); + * if (!fgets(line, sizeof(line), stdin)) + * break; + * chomp(line); + * if (!*line) + * break; + * + * printf("Anagrams of \"%s\":\n", line); + * print_anagrams(btree, line); + * } + * + * printf("Cleaning up...\n"); + * btree_delete(btree); + * + * return 0; + * } + * + * struct word *new_word(const char *line) + * { + * struct word *word; + * char *letter_set = make_letter_set(strdup(line)); + * + * //Discard lines with no letters + * if (!*letter_set) { + * free(letter_set); + * return NULL; + * } + * + * word = malloc(sizeof(struct word)); + * word->word = chomp(strdup(line)); + * word->letter_set = letter_set; + * + * return word; + * } + * + * //Remove trailing newline (if present). + * char *chomp(char *str) + * { + * char *end = strchr(str, '\0') - 1; + * if (*str && *end == '\n') + * *end = 0; + * return str; + * } + * + * //Remove all characters but letters, make letters lowercase, and sort them. + * char *make_letter_set(char *str) + * { + * size_t count[26] = {0}; + * size_t i, j; + * char *o = str; + * + * for (i=0; str[i]; i++) { + * char c = str[i]; + * if (c >= 'A' && c <= 'Z') + * c += 'a'-'A'; + * if (c >= 'a' && c <= 'z') + * count[c - 'a']++; + * } + * + * for (i = 0; i < 26; i++) { + * for (j = 0; j < count[i]; j++) + * *o++ = 'a' + i; + * } + * *o = '\0'; + * + * return str; + * } + * + * Author: Joey Adams + * Version: 0.1.0 + * Licence: BSD + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + /* Nothing */ + return 0; + } + + return 1; +}