Joey's btree module.
[ccan] / ccan / btree / _info
1 #include <string.h>
2 #include "config.h"
3
4 /**
5  * btree - Efficient sorted associative container based on B-trees.
6  *
7  * This module provides an efficient in-memory lookup container that keeps a
8  * set of pointers sorted using a user-defined search function.
9  *
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).
14  *
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
21  * suggestions.
22  *
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.
27  *
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.
33  *
34  * Example:
35  * #include <ccan/btree/btree.h>
36  * 
37  * #include <errno.h>
38  * #include <stdlib.h>
39  * #include <stdio.h>
40  * #include <string.h>
41  * 
42  * struct word {
43  *      char *word;
44  *      char *letter_set;
45  * };
46  * 
47  * //Define the ordering function order_by_letter_set
48  * btree_search_implement
49  * (
50  *      order_by_letter_set,
51  *      struct word *,
52  *      int c = strcmp(a->letter_set, b->letter_set),
53  *      c == 0,
54  *      c < 0
55  * )
56  * 
57  * struct word *new_word(const char *line);
58  * char *chomp(char *str);
59  * char *make_letter_set(char *str);
60  * 
61  * void insert_word(struct btree *btree, struct word *word)
62  * {
63  *      btree_iterator iter;
64  *      
65  *      //Position iterator after existing words with this letter set.
66  *      btree_find_last(btree, word, iter);
67  *      
68  *      //Insert new word at iterator position.
69  *      btree_insert_at(iter, word);
70  * }
71  * 
72  * void print_anagrams(struct btree *btree, char *line)
73  * {
74  *      btree_iterator iter, end;
75  *      struct word key = {
76  *              NULL,
77  *              make_letter_set(line)
78  *      };
79  *      
80  *      //Find first matching word.
81  *      if (!btree_find_first(btree, &key, iter)) {
82  *              printf("\t(none)\n");
83  *              return;
84  *      }
85  *      
86  *      btree_find_last(btree, &key, end);
87  *      
88  *      //Traverse matching words.
89  *      for (; btree_deref(iter) && btree_cmp_iters(iter, end) < 0;
90  *             btree_next(iter))
91  *      {
92  *              struct word *word = iter->item;
93  *              printf("\t%s\n", word->word);
94  *      }
95  * }
96  * 
97  * int destroy_word(struct word *word, void *ctx)
98  * {
99  *      (void) ctx;
100  *      
101  *      free(word->word);
102  *      free(word->letter_set);
103  *      free(word);
104  *      
105  *      return 1;
106  * }
107  * 
108  * struct btree *read_dictionary(const char *filename)
109  * {
110  *      FILE *f;
111  *      char line[256];
112  *      
113  *      //Construct new btree with the ordering function order_by_letter_set .
114  *      struct btree *btree = btree_new(order_by_letter_set);
115  *      
116  *      f = fopen(filename, "r");
117  *      if (!f)
118  *              goto fail;
119  *      
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;
123  *      
124  *      while (fgets(line, sizeof(line), f)) {
125  *              struct word *word = new_word(line);
126  *              if (!word)
127  *                      continue;
128  *              insert_word(btree, word);
129  *      }
130  *      
131  *      if (ferror(f)) {
132  *              fclose(f);
133  *              goto fail;
134  *      }
135  *      if (fclose(f))
136  *              goto fail;
137  *      
138  *      return btree;
139  * 
140  * fail:
141  *      btree_delete(btree);
142  *      fprintf(stderr, "%s: %s\n", filename, strerror(errno));
143  *      return NULL;
144  * }
145  * 
146  * int main(int argc, char *argv[])
147  * {
148  *      struct btree *btree;
149  *      char line[256];
150  *      
151  *      if (argc != 2) {
152  *              fprintf(stderr,
153  *                      "Usage: %s dictionary-file\n"
154  *                      "Example:\n"
155  *                      "\t%s /usr/share/dict/words\n"
156  *                      "\n"
157  *                      , argv[0], argv[0]);
158  *              return 1;
159  *      }
160  *      
161  *      printf("Indexing...\n");
162  *      btree = read_dictionary(argv[1]);
163  *      printf("Dictionary has %ld words\n", (long)btree->count);
164  *      
165  *      for (;;) {
166  *              printf("> ");
167  *              if (!fgets(line, sizeof(line), stdin))
168  *                      break;
169  *              chomp(line);
170  *              if (!*line)
171  *                      break;
172  *              
173  *              printf("Anagrams of \"%s\":\n", line);
174  *              print_anagrams(btree, line);
175  *      }
176  *      
177  *      printf("Cleaning up...\n");
178  *      btree_delete(btree);
179  *      
180  *      return 0;
181  * }
182  * 
183  * struct word *new_word(const char *line)
184  * {
185  *      struct word *word;
186  *      char *letter_set = make_letter_set(strdup(line));
187  *      
188  *      //Discard lines with no letters
189  *      if (!*letter_set) {
190  *              free(letter_set);
191  *              return NULL;
192  *      }
193  *      
194  *      word = malloc(sizeof(struct word));
195  *      word->word = chomp(strdup(line));
196  *      word->letter_set = letter_set;
197  *      
198  *      return word;
199  * }
200  * 
201  * //Remove trailing newline (if present).
202  * char *chomp(char *str)
203  * {
204  *      char *end = strchr(str, '\0') - 1;
205  *      if (*str && *end == '\n')
206  *              *end = 0;
207  *      return str;
208  * }
209  * 
210  * //Remove all characters but letters, make letters lowercase, and sort them.
211  * char *make_letter_set(char *str)
212  * {
213  *      size_t count[26] = {0};
214  *      size_t i, j;
215  *      char *o = str;
216  *      
217  *      for (i=0; str[i]; i++) {
218  *              char c = str[i];
219  *              if (c >= 'A' && c <= 'Z')
220  *                      c += 'a'-'A';
221  *              if (c >= 'a' && c <= 'z')
222  *                      count[c - 'a']++;
223  *      }
224  *      
225  *      for (i = 0; i < 26; i++) {
226  *              for (j = 0; j < count[i]; j++)
227  *                      *o++ = 'a' + i;
228  *      }
229  *      *o = '\0';
230  *      
231  *      return str;
232  * }
233  *
234  * Author: Joey Adams
235  * Version: 0.1.0
236  * Licence: BSD
237  */
238 int main(int argc, char *argv[])
239 {
240         /* Expect exactly one argument */
241         if (argc != 2)
242                 return 1;
243
244         if (strcmp(argv[1], "depends") == 0) {
245                 /* Nothing */
246                 return 0;
247         }
248
249         return 1;
250 }