2 * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
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:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
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
31 typedef struct AVL AVL
;
32 typedef struct AvlNode AvlNode
;
33 typedef struct AvlIter AvlIter
;
36 /* Create a new AVL tree sorted with the given comparison function. */
38 void avl_free(AVL
*avl
);
39 /* Free an AVL tree. */
41 void *avl_lookup(const AVL
*avl
, const struct sm_state
*sm
);
42 /* O(log n). Lookup a sm. Return NULL if the sm is not present. */
44 #define avl_member(avl, sm) (!!avl_lookup_node(avl, sm))
45 /* O(log n). See if a sm is present. */
47 size_t avl_count(const AVL
*avl
);
48 /* O(1). Return the number of elements in the tree. */
50 bool avl_insert(AVL
*avl
, const struct sm_state
*sm
);
52 * O(log n). Insert an sm or replace it if already present.
54 * Return false if the insertion replaced an existing sm.
57 bool avl_remove(AVL
*avl
, const struct sm_state
*sm
);
59 * O(log n). Remove an sm (if present).
61 * Return true if it was removed.
64 bool avl_check_invariants(AVL
*avl
);
65 /* For testing purposes. This function will always return true :-) */
68 /************************* Traversal *************************/
70 #define avl_foreach(iter, avl) avl_traverse(iter, avl, FORWARD)
72 * O(n). Traverse an AVL tree in order.
79 * printf("%s -> %s\n", i.sm->name, i.sm->state->name);
82 #define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
83 /* O(n). Traverse an AVL tree in reverse order. */
85 typedef enum AvlDirection
{FORWARD
= 0, BACKWARD
= 1} AvlDirection
;
94 AvlDirection direction
;
97 void avl_iter_begin(AvlIter
*iter
, AVL
*avl
, AvlDirection dir
);
98 void avl_iter_next(AvlIter
*iter
);
99 #define avl_traverse(iter, avl, direction) \
100 for (avl_iter_begin(&(iter), avl, direction); \
101 (iter).node != NULL; \
102 avl_iter_next(&iter))
105 /***************** Internal data structures ******************/
113 const struct sm_state
*sm
;
116 int balance
; /* -1, 0, or 1 */
119 AvlNode
*avl_lookup_node(const AVL
*avl
, const struct sm_state
*sm
);
120 /* O(log n). Lookup an AVL node by sm. Return NULL if not present. */