git.ozlabs.org Git - ccan/blob - ccan/avl/_info

   1 #include "config.h"
   2 #include <stdio.h>
   3 #include <string.h>
   4
   5 /**
   6  * avl - Key-value dictionary based on AVL trees
   7  *
   8  * A simple, well-tested implementation of AVL trees for mapping
   9  * unique keys to values.  This implementation supports insertion,
  10  * removal, lookup, and traversal.
  11  *
  12  * An AVL tree is a self-balancing binary tree that performs
  13  * insertion, removal, and lookup in O(log n) time per operation.
  14  *
  15  * Example:
  16  * #include <ccan/avl/avl.h>
  17  *
  18  * #include <stdio.h>
  19  * #include <stdlib.h>
  20  * #include <string.h>
  21  *
  22  * struct tally {
  23  *      long count;
  24  * };
  25  * #define new_tally() calloc(1, sizeof(struct tally))
  26  *
  27  * static void chomp(char *str)
  28  * {
  29  *      char *end = strchr(str, 0);
  30  *      if (end > str && end[-1] == '\n')
  31  *              end[-1] = 0;
  32  * }
  33  *
  34  * int main(void)
  35  * {
  36  *      AVL          *avl = avl_new((total_order_noctx_cb) strcmp);
  37  *      AvlIter       i;
  38  *      struct tally *tally;
  39  *      char          line[256];
  40  *
  41  *      while (fgets(line, sizeof(line), stdin))
  42  *      {
  43  *              chomp(line);
  44  *
  45  *              tally = avl_lookup(avl, line);
  46  *              if (tally == NULL)
  47  *                      avl_insert(avl, strdup(line), tally = new_tally());
  48  *
  49  *              tally->count++;
  50  *      }
  51  *
  52  *      avl_foreach(i, avl) {
  53  *              char         *line  = i.key;
  54  *              struct tally *tally = i.value;
  55  *
  56  *              printf("% 5ld: %s\n", tally->count, line);
  57  *
  58  *              free(line);
  59  *              free(tally);
  60  *      }
  61  *
  62  *      avl_free(avl);
  63  *
  64  *      return 0;
  65  * }
  66  *
  67  * Author: Joey Adams <joeyadams3.14159@gmail.com>
  68  * License: MIT
  69  * Version: 0.1
  70  */
  71 int main(int argc, char *argv[])
  72 {
  73         /* Expect exactly one argument */
  74         if (argc != 2)
  75                 return 1;
  76
  77         if (strcmp(argv[1], "depends") == 0) {
  78                 printf("ccan/order\n");
  79                 return 0;
  80         }
  81
  82         return 1;
  83 }