git.ozlabs.org Git - ccan/blob - 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  * 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  * 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  * 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  * 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  * 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 }