11f5207bJohn Levon/*
21f5207bJohn Levon * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
31f5207bJohn Levon *
41f5207bJohn Levon * Permission is hereby granted, free of charge, to any person obtaining a copy
51f5207bJohn Levon * of this software and associated documentation files (the "Software"), to deal
61f5207bJohn Levon * in the Software without restriction, including without limitation the rights
71f5207bJohn Levon * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
81f5207bJohn Levon * copies of the Software, and to permit persons to whom the Software is
91f5207bJohn Levon * furnished to do so, subject to the following conditions:
101f5207bJohn Levon *
111f5207bJohn Levon * The above copyright notice and this permission notice shall be included in
121f5207bJohn Levon * all copies or substantial portions of the Software.
131f5207bJohn Levon *
141f5207bJohn Levon * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
151f5207bJohn Levon * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
161f5207bJohn Levon * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
171f5207bJohn Levon * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
181f5207bJohn Levon * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
191f5207bJohn Levon * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
201f5207bJohn Levon * THE SOFTWARE.
211f5207bJohn Levon */
221f5207bJohn Levon
231f5207bJohn Levon#ifndef CCAN_AVL_H
241f5207bJohn Levon#define CCAN_AVL_H
251f5207bJohn Levon
261f5207bJohn Levon#include <stdbool.h>
271f5207bJohn Levon#include <stddef.h>
281f5207bJohn Levon
291f5207bJohn Levonstruct sm_state;
301f5207bJohn Levon
311f5207bJohn Levontypedef struct AvlNode       AvlNode;
321f5207bJohn Levontypedef struct AvlIter       AvlIter;
331f5207bJohn Levon
341f5207bJohn Levonstruct stree {
351f5207bJohn Levon	AvlNode    *root;
361f5207bJohn Levon	struct stree *base_stree;
371f5207bJohn Levon	char *has_states;
381f5207bJohn Levon	size_t      count;
391f5207bJohn Levon	int stree_id;
401f5207bJohn Levon	int references;
411f5207bJohn Levon};
421f5207bJohn Levon
431f5207bJohn Levonvoid free_stree(struct stree **avl);
441f5207bJohn Levon	/* Free an stree tree. */
451f5207bJohn Levon
461f5207bJohn Levonstruct sm_state *avl_lookup(const struct stree *avl, const struct sm_state *sm);
471f5207bJohn Levon	/* O(log n). Lookup a sm.  Return NULL if the sm is not present. */
481f5207bJohn Levon
491f5207bJohn Levon#define avl_member(avl, sm) (!!avl_lookup_node(avl, sm))
501f5207bJohn Levon	/* O(log n). See if a sm is present. */
511f5207bJohn Levon
521f5207bJohn Levonsize_t stree_count(const struct stree *avl);
531f5207bJohn Levon	/* O(1). Return the number of elements in the tree. */
541f5207bJohn Levon
551f5207bJohn Levonbool avl_insert(struct stree **avl, const struct sm_state *sm);
561f5207bJohn Levon	/*
571f5207bJohn Levon	 * O(log n). Insert an sm or replace it if already present.
581f5207bJohn Levon	 *
591f5207bJohn Levon	 * Return false if the insertion replaced an existing sm.
601f5207bJohn Levon	 */
611f5207bJohn Levon
621f5207bJohn Levonbool avl_remove(struct stree **avl, const struct sm_state *sm);
631f5207bJohn Levon	/*
641f5207bJohn Levon	 * O(log n). Remove an sm (if present).
651f5207bJohn Levon	 *
661f5207bJohn Levon	 * Return true if it was removed.
671f5207bJohn Levon	 */
681f5207bJohn Levon
691f5207bJohn Levonbool avl_check_invariants(struct stree *avl);
701f5207bJohn Levon	/* For testing purposes.  This function will always return true :-) */
711f5207bJohn Levon
721f5207bJohn Levon
731f5207bJohn Levon/************************* Traversal *************************/
741f5207bJohn Levon
751f5207bJohn Levon#define avl_foreach(iter, avl)         avl_traverse(iter, avl, FORWARD)
761f5207bJohn Levon	/*
771f5207bJohn Levon	 * O(n). Traverse an stree tree in order.
781f5207bJohn Levon	 *
791f5207bJohn Levon	 * Example:
801f5207bJohn Levon	 *
811f5207bJohn Levon	 * AvlIter i;
821f5207bJohn Levon	 *
831f5207bJohn Levon	 * avl_foreach(i, avl)
841f5207bJohn Levon	 *     printf("%s -> %s\n", i.sm->name, i.sm->state->name);
851f5207bJohn Levon	 */
861f5207bJohn Levon
871f5207bJohn Levon#define FOR_EACH_SM(avl, _sm) {			\
881f5207bJohn Levon	AvlIter _i;				\
891f5207bJohn Levon	avl_foreach(_i, avl) {			\
901f5207bJohn Levon		_sm = _i.sm;
911f5207bJohn Levon
921f5207bJohn Levon#define END_FOR_EACH_SM(_sm) }}
931f5207bJohn Levon
941f5207bJohn Levon#define FOR_EACH_MY_SM(_owner, avl, _sm) {	\
951f5207bJohn Levon	AvlIter _i;				\
961f5207bJohn Levon	avl_foreach(_i, avl) {			\
971f5207bJohn Levon		_sm = _i.sm;			\
981f5207bJohn Levon		if (_sm->owner != _owner)	\
991f5207bJohn Levon			continue;		\
1001f5207bJohn Levon
1011f5207bJohn Levon#define avl_foreach_reverse(iter, avl) avl_traverse(iter, avl, BACKWARD)
1021f5207bJohn Levon	/* O(n). Traverse an stree tree in reverse order. */
1031f5207bJohn Levon
1041f5207bJohn Levontypedef enum AvlDirection {FORWARD = 0, BACKWARD = 1} AvlDirection;
1051f5207bJohn Levon
1061f5207bJohn Levonstruct AvlIter {
1071f5207bJohn Levon	struct sm_state *sm;
1081f5207bJohn Levon	AvlNode      *node;
1091f5207bJohn Levon
1101f5207bJohn Levon	/* private */
1111f5207bJohn Levon	AvlNode      *stack[100];
1121f5207bJohn Levon	int           stack_index;
1131f5207bJohn Levon	AvlDirection  direction;
1141f5207bJohn Levon};
1151f5207bJohn Levon
1161f5207bJohn Levonvoid avl_iter_begin(AvlIter *iter, struct stree *avl, AvlDirection dir);
1171f5207bJohn Levonvoid avl_iter_next(AvlIter *iter);
1181f5207bJohn Levon#define avl_traverse(iter, avl, direction)        \
1191f5207bJohn Levon	for (avl_iter_begin(&(iter), avl, direction); \
1201f5207bJohn Levon	     (iter).node != NULL;                     \
1211f5207bJohn Levon	     avl_iter_next(&iter))
1221f5207bJohn Levon
1231f5207bJohn Levon
1241f5207bJohn Levon/***************** Internal data structures ******************/
1251f5207bJohn Levon
1261f5207bJohn Levonstruct AvlNode {
1271f5207bJohn Levon	const struct sm_state *sm;
1281f5207bJohn Levon
1291f5207bJohn Levon	AvlNode    *lr[2];
1301f5207bJohn Levon	int         balance; /* -1, 0, or 1 */
1311f5207bJohn Levon};
1321f5207bJohn Levon
1331f5207bJohn LevonAvlNode *avl_lookup_node(const struct stree *avl, const struct sm_state *sm);
1341f5207bJohn Levon	/* O(log n). Lookup an stree node by sm.  Return NULL if not present. */
1351f5207bJohn Levon
1361f5207bJohn Levonstruct stree *clone_stree(struct stree *orig);
1371f5207bJohn Levon
1381f5207bJohn Levonvoid set_stree_id(struct stree **stree, int id);
1391f5207bJohn Levonint get_stree_id(struct stree *stree);
1401f5207bJohn Levon
1411f5207bJohn Levon#endif
142