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