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 struct sm_state;
  30
  31 typedef struct AVL           AVL;
  32 typedef struct AvlNode       AvlNode;
  33 typedef struct AvlIter       AvlIter;
  34
  35 void avl_free(AVL **avl);
  36         /* Free an AVL tree. */
  37
  38 struct sm_state *avl_lookup(const AVL *avl, const struct sm_state *sm);
  39         /* O(log n). Lookup a sm.  Return NULL if the sm is not present. */
  40
  41 #define avl_member(avl, sm) (!!avl_lookup_node(avl, sm))
  42         /* O(log n). See if a sm is present. */
  43
  44 size_t avl_count(const AVL *avl);
  45         /* O(1). Return the number of elements in the tree. */
  46
  47 bool avl_insert(AVL **avl, const struct sm_state *sm);
  48         /*
  49          * O(log n). Insert an sm or replace it if already present.
  50          *
  51          * Return false if the insertion replaced an existing sm.
  52          */
  53
  54 bool avl_remove(AVL **avl, const struct sm_state *sm);
  55         /*
  56          * O(log n). Remove an sm (if present).
  57          *
  58          * Return true if it was removed.
  59          */
  60
  61 bool avl_check_invariants(AVL *avl);
  62         /* For testing purposes.  This function will always return true :-) */
  63
  64
  65 /************************* Traversal *************************/
  66
  67 #define avl_foreach(iter, avl)         avl_traverse(iter, avl, FORWARD)
  68         /*
  69          * O(n). Traverse an AVL tree in order.
  70          *
  71          * Example:
  72          *
  73          * AvlIter i;
  74          *
  75          * avl_foreach(i, avl)
  76          *     printf("%s -> %s\n", i.sm->name, i.sm->state->name);
  77          */
  78
  79 #define FOR_EACH_SM(avl, _sm) {                 \
  80         AvlIter _i;                             \
  81         avl_foreach(_i, avl) {                  \
  82                 _sm = _i.sm;
  83
  84 #define END_FOR_EACH_SM(_sm) }}
  85
  86 #define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
  87         /* O(n). Traverse an AVL tree in reverse order. */
  88
  89 typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
  90
  91 struct AvlIter {
  92         struct sm_state *sm;
  93         AvlNode      *node;
  94
  95         /* private */
  96         AvlNode      *stack[100];
  97         int           stack_index;
  98         AvlDirection  direction;
  99 };
 100
 101 void avl_iter_begin(AvlIter *iter, AVL *avl, AvlDirection dir);
 102 void avl_iter_next(AvlIter *iter);
 103 #define avl_traverse(iter, avl, direction)        \
 104         for (avl_iter_begin(&(iter), avl, direction); \
 105              (iter).node != NULL;                     \
 106              avl_iter_next(&iter))
 107
 108
 109 /***************** Internal data structures ******************/
 110
 111 struct AVL {
 112         AvlNode    *root;
 113         size_t      count;
 114 };
 115
 116 struct AvlNode {
 117         const struct sm_state *sm;
 118
 119         AvlNode    *lr[2];
 120         int         balance; /* -1, 0, or 1 */
 121 };
 122
 123 AvlNode *avl_lookup_node(const AVL *avl, const struct sm_state *sm);
 124         /* O(log n). Lookup an AVL node by sm.  Return NULL if not present. */
 125
 126 AVL *avl_clone(AVL *orig);
 127 #define clone_stree avl_clone
 128
 129 #endif