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