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

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