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