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