utf8: don't allow NUL in decoded strings.
[ccan] / ccan / btree / _info
1 #include "config.h"
2 #include <stdio.h>
3 #include <string.h>
4
5 /**
6  * btree - Efficient sorted associative container based on B-trees.
7  *
8  * This module provides an efficient in-memory lookup container that keeps a
9  * set of pointers sorted using a user-defined search function.
10  *
11  * This module supports insertion, removal, lookup, and traversal using an
12  * iterator system.  Note that insertion and removal into/from a btree will
13  * invalidate all iterators pointing to it (including the one passed to the
14  * insertion or removal function).
15  *
16  * A B-tree (not to be confused with a binary tree) is a data structure that
17  * performs insertion, removal, and lookup in O(log n) time per operation.
18  * Although B-trees are typically used for databases and filesystems, this is
19  * an in-memory implementation.
20  *
21  * Unlike functions like qsort, bsearch, and tsearch, btree does not take a
22  * comparison function.  It takes a binary search function, which is
23  * theoretically equivalent but faster.  Writing a binary search function
24  * is more difficult than writing a comparison function, so a macro is provided
25  * to make it much easier than doing either manually.
26  *
27  * Example:
28  * #include <ccan/btree/btree.h>
29  * 
30  * #include <errno.h>
31  * #include <stdlib.h>
32  * #include <stdio.h>
33  * #include <string.h>
34  * 
35  * struct word {
36  *      char *word;
37  *      char *letter_set;
38  * };
39  * 
40  * //Define the ordering function order_by_letter_set
41  * static btree_search_implement
42  * (
43  *      order_by_letter_set,
44  *      struct word *,
45  *      int c = strcmp(a->letter_set, b->letter_set),
46  *      c == 0,
47  *      c < 0
48  * )
49  * 
50  * struct word *new_word(const char *line);
51  * char *chomp(char *str);
52  * char *make_letter_set(char *str);
53  * 
54  * static void insert_word(struct btree *btree, struct word *word)
55  * {
56  *      btree_iterator iter;
57  *      
58  *      //Position iterator after existing words with this letter set.
59  *      btree_find_last(btree, word, iter);
60  *      
61  *      //Insert new word at iterator position.
62  *      btree_insert_at(iter, word);
63  * }
64  * 
65  * static void print_anagrams(struct btree *btree, char *line)
66  * {
67  *      btree_iterator iter, end;
68  *      struct word key = {
69  *              NULL,
70  *              make_letter_set(line)
71  *      };
72  *      
73  *      //Find first matching word.
74  *      if (!btree_find_first(btree, &key, iter)) {
75  *              printf("\t(none)\n");
76  *              return;
77  *      }
78  *      
79  *      btree_find_last(btree, &key, end);
80  *      
81  *      //Traverse matching words.
82  *      for (; btree_deref(iter) && btree_cmp_iters(iter, end) < 0;
83  *             btree_next(iter))
84  *      {
85  *              struct word *word = iter->item;
86  *              printf("\t%s\n", word->word);
87  *      }
88  * }
89  * 
90  * static int destroy_word(struct word *word, void *ctx)
91  * {
92  *      (void) ctx;
93  *      
94  *      free(word->word);
95  *      free(word->letter_set);
96  *      free(word);
97  *      
98  *      return 1;
99  * }
100  * 
101  * static struct btree *read_dictionary(const char *filename)
102  * {
103  *      FILE *f;
104  *      char line[256];
105  *      
106  *      //Construct new btree with the ordering function order_by_letter_set .
107  *      struct btree *btree = btree_new(order_by_letter_set);
108  *      
109  *      f = fopen(filename, "r");
110  *      if (!f)
111  *              goto fail;
112  *      
113  *      //Set the destroy callback so btree_free will automatically
114  *      //free our items.  Setting btree->destroy is optional.
115  *      btree->destroy = (btree_action_t)destroy_word;
116  *      
117  *      while (fgets(line, sizeof(line), f)) {
118  *              struct word *word = new_word(line);
119  *              if (!word)
120  *                      continue;
121  *              insert_word(btree, word);
122  *      }
123  *      
124  *      if (ferror(f)) {
125  *              fclose(f);
126  *              goto fail;
127  *      }
128  *      if (fclose(f))
129  *              goto fail;
130  *      
131  *      return btree;
132  * 
133  *   fail:
134  *      btree_delete(btree);
135  *      fprintf(stderr, "%s: %s\n", filename, strerror(errno));
136  *      return NULL;
137  * }
138  * 
139  * int main(int argc, char *argv[])
140  * {
141  *      struct btree *btree;
142  *      char line[256];
143  *      
144  *      if (argc != 2) {
145  *              fprintf(stderr,
146  *                      "Usage: %s dictionary-file\n"
147  *                      "Example:\n"
148  *                      "\t%s /usr/share/dict/words\n"
149  *                      "\n"
150  *                      , argv[0], argv[0]);
151  *              return 1;
152  *      }
153  *      
154  *      printf("Indexing...\n");
155  *      btree = read_dictionary(argv[1]);
156  *      printf("Dictionary has %ld words\n", (long)btree->count);
157  *      
158  *      for (;;) {
159  *              printf("> ");
160  *              if (!fgets(line, sizeof(line), stdin))
161  *                      break;
162  *              chomp(line);
163  *              if (!*line)
164  *                      break;
165  *              
166  *              printf("Anagrams of \"%s\":\n", line);
167  *              print_anagrams(btree, line);
168  *      }
169  *      
170  *      printf("Cleaning up...\n");
171  *      btree_delete(btree);
172  *      
173  *      return 0;
174  * }
175  * 
176  * struct word *new_word(const char *line)
177  * {
178  *      struct word *word;
179  *      char *letter_set = make_letter_set(strdup(line));
180  *      
181  *      //Discard lines with no letters
182  *      if (!*letter_set) {
183  *              free(letter_set);
184  *              return NULL;
185  *      }
186  *      
187  *      word = malloc(sizeof(struct word));
188  *      word->word = chomp(strdup(line));
189  *      word->letter_set = letter_set;
190  *      
191  *      return word;
192  * }
193  * 
194  * //Remove trailing newline (if present).
195  * char *chomp(char *str)
196  * {
197  *      char *end = strchr(str, '\0') - 1;
198  *      if (*str && *end == '\n')
199  *              *end = 0;
200  *      return str;
201  * }
202  * 
203  * //Remove all characters but letters, make letters lowercase, and sort them.
204  * char *make_letter_set(char *str)
205  * {
206  *      size_t count[26] = {0};
207  *      size_t i, j;
208  *      char *o = str;
209  *      
210  *      for (i=0; str[i]; i++) {
211  *              char c = str[i];
212  *              if (c >= 'A' && c <= 'Z')
213  *                      c += 'a'-'A';
214  *              if (c >= 'a' && c <= 'z')
215  *                      count[c - 'a']++;
216  *      }
217  *      
218  *      for (i = 0; i < 26; i++) {
219  *              for (j = 0; j < count[i]; j++)
220  *                      *o++ = 'a' + i;
221  *      }
222  *      *o = '\0';
223  *      
224  *      return str;
225  * }
226  *
227  * Author: Joey Adams <joeyadams3.14159@gmail.com>
228  * License: MIT
229  * Version: 0.2
230  */
231 int main(int argc, char *argv[])
232 {
233         /* Expect exactly one argument */
234         if (argc != 2)
235                 return 1;
236
237         if (strcmp(argv[1], "depends") == 0) {
238                 /* Nothing */
239                 return 0;
240         }
241
242         return 1;
243 }