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

   1 /*
   2  * Copyright (c) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #ifndef CCAN_AVL_H
  18 #define CCAN_AVL_H
  19
  20 #include <stdbool.h>
  21 #include <stddef.h>
  22
  23 typedef struct AVL           AVL;
  24 typedef struct AvlNode       AvlNode;
  25 typedef struct AvlIter       AvlIter;
  26
  27 typedef int (*AvlCompare)(const void *, const void *);
  28
  29 AVL *avl_new(AvlCompare compare);
  30         /* Create a new AVL tree sorted with the given comparison function. */
  31
  32 void avl_free(AVL *avl);
  33         /* Free an AVL tree. */
  34
  35 void *avl_lookup(const AVL *avl, const void *key);
  36         /* O(log n). Lookup a value at a key.  Return NULL if the key is not present. */
  37
  38 #define avl_member(avl, key) (!!avl_lookup_node(avl, key))
  39         /* O(log n). See if a key is present. */
  40
  41 size_t avl_count(const AVL *avl);
  42         /* O(1). Return the number of elements in the tree. */
  43
  44 bool avl_insert(AVL *avl, const void *key, const void *value);
  45         /*
  46          * O(log n). Insert a key/value pair, or replace it if already present.
  47          *
  48          * Return false if the insertion replaced an existing key/value.
  49          */
  50
  51 bool avl_remove(AVL *avl, const void *key);
  52         /*
  53          * O(log n). Remove a key/value pair (if present).
  54          *
  55          * Return true if it was removed.
  56          */
  57
  58 bool avl_check_invariants(AVL *avl);
  59         /* For testing purposes.  This function will always return true :-) */
  60
  61
  62 /************************* Traversal *************************/
  63
  64 #define avl_foreach(iter, avl)         avl_traverse(iter, avl, FORWARD)
  65         /*
  66          * O(n). Traverse an AVL tree in order.
  67          *
  68          * Example:
  69          *
  70          * AvlIter i;
  71          *
  72          * avl_foreach(i, avl)
  73          *     printf("%s -> %s\n", i.key, i.value);
  74          */
  75
  76 #define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
  77         /* O(n). Traverse an AVL tree in reverse order. */
  78
  79 typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
  80
  81 struct AvlIter {
  82         void         *key;
  83         void         *value;
  84         AvlNode      *node;
  85
  86         /* private */
  87         AvlNode      *stack[100];
  88         int           stack_index;
  89         AvlDirection  direction;
  90 };
  91
  92 void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir);
  93 void avl_iter_next(AvlIter *iter);
  94 #define avl_traverse(iter, avl, direction)        \
  95         for (avl_iter_begin(&(iter), avl, direction); \
  96              (iter).node != NULL;                     \
  97              avl_iter_next(&iter))
  98
  99
 100 /***************** Internal data structures ******************/
 101
 102 struct AVL {
 103         AvlCompare  compare;
 104         AvlNode    *root;
 105         size_t      count;
 106 };
 107
 108 struct AvlNode {
 109         const void *key;
 110         const void *value;
 111
 112         AvlNode    *lr[2];
 113         int         balance; /* -1, 0, or 1 */
 114 };
 115
 116 AvlNode *avl_lookup_node(const AVL *avl, const void *key);
 117         /* O(log n). Lookup an AVL node by key.  Return NULL if not present. */
 118
 119 #endif