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_MY_SM(_owner, avl, _sm) { \ 95 AvlIter _i; \ 96 avl_foreach(_i, avl) { \ 97 _sm = _i.sm; \ 98 if (_sm->owner != _owner) \ 99 continue; \ 100 101 #define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD) 102 /* O(n). Traverse an stree tree in reverse order. */ 103 104 typedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection; 105 106 struct AvlIter { 107 struct sm_state *sm; 108 AvlNode *node; 109 110 /* private */ 111 AvlNode *stack[100]; 112 int stack_index; 113 AvlDirection direction; 114 }; 115 116 void avl_iter_begin(AvlIter *iter, struct stree *avl, AvlDirection dir); 117 void avl_iter_next(AvlIter *iter); 118 #define avl_traverse(iter, avl, direction) \ 119 for (avl_iter_begin(&(iter), avl, direction); \ 120 (iter).node != NULL; \ 121 avl_iter_next(&iter)) 122 123 124 /***************** Internal data structures ******************/ 125 126 struct AvlNode { 127 const struct sm_state *sm; 128 129 AvlNode *lr[2]; 130 int balance; /* -1, 0, or 1 */ 131 }; 132 133 AvlNode *avl_lookup_node(const struct stree *avl, const struct sm_state *sm); 134 /* O(log n). Lookup an stree node by sm. Return NULL if not present. */ 135 136 struct stree *clone_stree(struct stree *orig); 137 138 void set_stree_id(struct stree **stree, int id); 139 int get_stree_id(struct stree *stree); 140 141 #endif 142