avl.h

   1 /*
   2  * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20  * THE SOFTWARE.
  21  */
  22
  23 #ifndef CCAN_AVL_H
  24 #define CCAN_AVL_H
  25
  26 #include <stdbool.h>
  27 #include <stddef.h>
  28
  29 typedef struct AVL           AVL;
  30 typedef struct AvlNode       AvlNode;
  31 typedef struct AvlIter       AvlIter;
  32
  33 AVL *avl_new(void);
  34         /* Create a new AVL tree sorted with the given comparison function. */
  35
  36 void avl_free(AVL *avl);
  37         /* Free an AVL tree. */
  38
  39 void *avl_lookup(const AVL *avl, const void *key);
  40         /* O(log n). Lookup a value at a key.  Return NULL if the key is not present. */
  41
  42 #define avl_member(avl, key) (!!avl_lookup_node(avl, key))
  43         /* O(log n). See if a key is present. */
  44
  45 size_t avl_count(const AVL *avl);
  46         /* O(1). Return the number of elements in the tree. */
  47
  48 bool avl_insert(AVL *avl, const void *key, const void *value);
  49         /*
  50          * O(log n). Insert a key/value pair, or replace it if already present.
  51          *
  52          * Return false if the insertion replaced an existing key/value.
  53          */
  54
  55 bool avl_remove(AVL *avl, const void *key);
  56         /*
  57          * O(log n). Remove a key/value pair (if present).
  58          *
  59          * Return true if it was removed.
  60          */
  61
  62 bool avl_check_invariants(AVL *avl);
  63         /* For testing purposes.  This function will always return true :-) */
  64
  65
  66 /************************* Traversal *************************/
  67
  68 #define avl_foreach(iter, avl)         avl_traverse(iter, avl, FORWARD)
  69         /*
  70          * O(n). Traverse an AVL tree in order.
  71          *
  72          * Example:
  73          *
  74          * AvlIter i;
  75          *
  76          * avl_foreach(i, avl)
  77          *     printf("%s -> %s\n", i.key, i.value);
  78          */
  79
  80 #define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
  81         /* O(n). Traverse an AVL tree in reverse order. */
  82
  83 typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
  84
  85 struct AvlIter {
  86         void         *key;
  87         void         *value;
  88         AvlNode      *node;
  89
  90         /* private */
  91         AvlNode      *stack[100];
  92         int           stack_index;
  93         AvlDirection  direction;
  94 };
  95
  96 void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir);
  97 void avl_iter_next(AvlIter *iter);
  98 #define avl_traverse(iter, avl, direction)        \
  99         for (avl_iter_begin(&(iter), avl, direction); \
 100              (iter).node != NULL;                     \
 101              avl_iter_next(&iter))
 102
 103
 104 /***************** Internal data structures ******************/
 105
 106 struct AVL {
 107         AvlNode    *root;
 108         size_t      count;
 109 };
 110
 111 struct AvlNode {
 112         const void *key;
 113         const void *value;
 114
 115         AvlNode    *lr[2];
 116         int         balance; /* -1, 0, or 1 */
 117 };
 118
 119 AvlNode *avl_lookup_node(const AVL *avl, const void *key);
 120         /* O(log n). Lookup an AVL node by key.  Return NULL if not present. */
 121
 122 #endif