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#include <assert.h>
241f5207bJohn Levon#include <stdlib.h>
251f5207bJohn Levon
261f5207bJohn Levon#include "smatch.h"
271f5207bJohn Levon#include "smatch_slist.h"
281f5207bJohn Levon
291f5207bJohn Levonstatic AvlNode *mkNode(const struct sm_state *sm);
301f5207bJohn Levonstatic void freeNode(AvlNode *node);
311f5207bJohn Levon
321f5207bJohn Levonstatic AvlNode *lookup(const struct stree *avl, AvlNode *node, const struct sm_state *sm);
331f5207bJohn Levon
341f5207bJohn Levonstatic bool insert_sm(struct stree *avl, AvlNode **p, const struct sm_state *sm);
351f5207bJohn Levonstatic bool remove_sm(struct stree *avl, AvlNode **p, const struct sm_state *sm, AvlNode **ret);
361f5207bJohn Levonstatic bool removeExtremum(AvlNode **p, int side, AvlNode **ret);
371f5207bJohn Levon
381f5207bJohn Levonstatic int sway(AvlNode **p, int sway);
391f5207bJohn Levonstatic void balance(AvlNode **p, int side);
401f5207bJohn Levon
411f5207bJohn Levonstatic bool checkBalances(AvlNode *node, int *height);
421f5207bJohn Levonstatic bool checkOrder(struct stree *avl);
431f5207bJohn Levonstatic size_t countNode(AvlNode *node);
441f5207bJohn Levon
451f5207bJohn Levonint unfree_stree;
461f5207bJohn Levon
471f5207bJohn Levon/*
481f5207bJohn Levon * Utility macros for converting between
491f5207bJohn Levon * "balance" values (-1 or 1) and "side" values (0 or 1).
501f5207bJohn Levon *
511f5207bJohn Levon * bal(0)   == -1
521f5207bJohn Levon * bal(1)   == +1
531f5207bJohn Levon * side(-1) == 0
541f5207bJohn Levon * side(+1) == 1
551f5207bJohn Levon */
561f5207bJohn Levon#define bal(side) ((side) == 0 ? -1 : 1)
571f5207bJohn Levon#define side(bal) ((bal)  == 1 ?  1 : 0)
581f5207bJohn Levon
591f5207bJohn Levonstatic struct stree *avl_new(void)
601f5207bJohn Levon{
611f5207bJohn Levon	struct stree *avl = malloc(sizeof(*avl));
621f5207bJohn Levon
631f5207bJohn Levon	unfree_stree++;
641f5207bJohn Levon	assert(avl != NULL);
651f5207bJohn Levon
661f5207bJohn Levon	avl->root = NULL;
671f5207bJohn Levon	avl->base_stree = NULL;
681f5207bJohn Levon	avl->has_states = calloc(num_checks + 1, sizeof(char));
691f5207bJohn Levon	avl->count = 0;
701f5207bJohn Levon	avl->stree_id = 0;
711f5207bJohn Levon	avl->references = 1;
721f5207bJohn Levon	return avl;
731f5207bJohn Levon}
741f5207bJohn Levon
751f5207bJohn Levonvoid free_stree(struct stree **avl)
761f5207bJohn Levon{
771f5207bJohn Levon	if (!*avl)
781f5207bJohn Levon		return;
791f5207bJohn Levon
801f5207bJohn Levon	assert((*avl)->references > 0);
811f5207bJohn Levon
821f5207bJohn Levon	(*avl)->references--;
831f5207bJohn Levon	if ((*avl)->references != 0) {
841f5207bJohn Levon		*avl = NULL;
851f5207bJohn Levon		return;
861f5207bJohn Levon	}
871f5207bJohn Levon
881f5207bJohn Levon	unfree_stree--;
891f5207bJohn Levon
901f5207bJohn Levon	freeNode((*avl)->root);
911f5207bJohn Levon	free(*avl);
921f5207bJohn Levon	*avl = NULL;
931f5207bJohn Levon}
941f5207bJohn Levon
951f5207bJohn Levonstruct sm_state *avl_lookup(const struct stree *avl, const struct sm_state *sm)
961f5207bJohn Levon{
971f5207bJohn Levon	AvlNode *found;
981f5207bJohn Levon
991f5207bJohn Levon	if (!avl)
1001f5207bJohn Levon		return NULL;
1011f5207bJohn Levon	if (sm->owner != USHRT_MAX &&
1021f5207bJohn Levon	    !avl->has_states[sm->owner])
1031f5207bJohn Levon		return NULL;
1041f5207bJohn Levon	found = lookup(avl, avl->root, sm);
1051f5207bJohn Levon	if (!found)
1061f5207bJohn Levon		return NULL;
1071f5207bJohn Levon	return (struct sm_state *)found->sm;
1081f5207bJohn Levon}
1091f5207bJohn Levon
1101f5207bJohn LevonAvlNode *avl_lookup_node(const struct stree *avl, const struct sm_state *sm)
1111f5207bJohn Levon{
1121f5207bJohn Levon	return lookup(avl, avl->root, sm);
1131f5207bJohn Levon}
1141f5207bJohn Levon
1151f5207bJohn Levonsize_t stree_count(const struct stree *avl)
1161f5207bJohn Levon{
1171f5207bJohn Levon	if (!avl)
1181f5207bJohn Levon		return 0;
1191f5207bJohn Levon	return avl->count;
1201f5207bJohn Levon}
1211f5207bJohn Levon
1221f5207bJohn Levonstatic struct stree *clone_stree_real(struct stree *orig)
1231f5207bJohn Levon{
1241f5207bJohn Levon	struct stree *new = avl_new();
1251f5207bJohn Levon	AvlIter i;
1261f5207bJohn Levon
1271f5207bJohn Levon	avl_foreach(i, orig)
1281f5207bJohn Levon		avl_insert(&new, i.sm);
1291f5207bJohn Levon
1301f5207bJohn Levon	new->base_stree = orig->base_stree;
1311f5207bJohn Levon	return new;
1321f5207bJohn Levon}
1331f5207bJohn Levon
1341f5207bJohn Levonbool avl_insert(struct stree **avl, const struct sm_state *sm)
1351f5207bJohn Levon{
1361f5207bJohn Levon	size_t old_count;
1371f5207bJohn Levon
1381f5207bJohn Levon	if (!*avl)
1391f5207bJohn Levon		*avl = avl_new();
1401f5207bJohn Levon	if ((*avl)->references > 1) {
1411f5207bJohn Levon		(*avl)->references--;
1421f5207bJohn Levon		*avl = clone_stree_real(*avl);
1431f5207bJohn Levon	}
1441f5207bJohn Levon	old_count = (*avl)->count;
1451f5207bJohn Levon	/* fortunately we never call get_state() on "unnull_path" */
1461f5207bJohn Levon	if (sm->owner != USHRT_MAX)
1471f5207bJohn Levon		(*avl)->has_states[sm->owner] = 1;
1481f5207bJohn Levon	insert_sm(*avl, &(*avl)->root, sm);
1491f5207bJohn Levon	return (*avl)->count != old_count;
1501f5207bJohn Levon}
1511f5207bJohn Levon
1521f5207bJohn Levonbool avl_remove(struct stree **avl, const struct sm_state *sm)
1531f5207bJohn Levon{
1541f5207bJohn Levon	AvlNode *node = NULL;
1551f5207bJohn Levon
1561f5207bJohn Levon	if (!*avl)
1571f5207bJohn Levon		return false;
1581f5207bJohn Levon	/* it's fairly rare for smatch to call avl_remove */
1591f5207bJohn Levon	if ((*avl)->references > 1) {
1601f5207bJohn Levon		(*avl)->references--;
1611f5207bJohn Levon		*avl = clone_stree_real(*avl);
1621f5207bJohn Levon	}
1631f5207bJohn Levon
1641f5207bJohn Levon	remove_sm(*avl, &(*avl)->root, sm, &node);
1651f5207bJohn Levon
1661f5207bJohn Levon	if ((*avl)->count == 0)
1671f5207bJohn Levon		free_stree(avl);
1681f5207bJohn Levon
1691f5207bJohn Levon	if (node == NULL) {
1701f5207bJohn Levon		return false;
1711f5207bJohn Levon	} else {
1721f5207bJohn Levon		free(node);
1731f5207bJohn Levon		return true;
1741f5207bJohn Levon	}
1751f5207bJohn Levon}
1761f5207bJohn Levon
1771f5207bJohn Levonstatic AvlNode *mkNode(const struct sm_state *sm)
1781f5207bJohn Levon{
1791f5207bJohn Levon	AvlNode *node = malloc(sizeof(*node));
1801f5207bJohn Levon
1811f5207bJohn Levon	assert(node != NULL);
1821f5207bJohn Levon
1831f5207bJohn Levon	node->sm = sm;
1841f5207bJohn Levon	node->lr[0] = NULL;
1851f5207bJohn Levon	node->lr[1] = NULL;
1861f5207bJohn Levon	node->balance = 0;
1871f5207bJohn Levon	return node;
1881f5207bJohn Levon}
1891f5207bJohn Levon
1901f5207bJohn Levonstatic void freeNode(AvlNode *node)
1911f5207bJohn Levon{
1921f5207bJohn Levon	if (node) {
1931f5207bJohn Levon		freeNode(node->lr[0]);
1941f5207bJohn Levon		freeNode(node->lr[1]);
1951f5207bJohn Levon		free(node);
1961f5207bJohn Levon	}
1971f5207bJohn Levon}
1981f5207bJohn Levon
1991f5207bJohn Levonstatic AvlNode *lookup(const struct stree *avl, AvlNode *node, const struct sm_state *sm)
2001f5207bJohn Levon{
2011f5207bJohn Levon	int cmp;
2021f5207bJohn Levon
2031f5207bJohn Levon	if (node == NULL)
2041f5207bJohn Levon		return NULL;
2051f5207bJohn Levon
2061f5207bJohn Levon	cmp = cmp_tracker(sm, node->sm);
2071f5207bJohn Levon
2081f5207bJohn Levon	if (cmp < 0)
2091f5207bJohn Levon		return lookup(avl, node->lr[0], sm);
2101f5207bJohn Levon	if (cmp > 0)
2111f5207bJohn Levon		return lookup(avl, node->lr[1], sm);
2121f5207bJohn Levon	return node;
2131f5207bJohn Levon}
2141f5207bJohn Levon
2151f5207bJohn Levon/*
2161f5207bJohn Levon * Insert an sm into a subtree, rebalancing if necessary.
2171f5207bJohn Levon *
2181f5207bJohn Levon * Return true if the subtree's height increased.
2191f5207bJohn Levon */
2201f5207bJohn Levonstatic bool insert_sm(struct stree *avl, AvlNode **p, const struct sm_state *sm)
2211f5207bJohn Levon{
2221f5207bJohn Levon	if (*p == NULL) {
2231f5207bJohn Levon		*p = mkNode(sm);
2241f5207bJohn Levon		avl->count++;
2251f5207bJohn Levon		return true;
2261f5207bJohn Levon	} else {
2271f5207bJohn Levon		AvlNode *node = *p;
2281f5207bJohn Levon		int      cmp  = cmp_tracker(sm, node->sm);
2291f5207bJohn Levon
2301f5207bJohn Levon		if (cmp == 0) {
2311f5207bJohn Levon			node->sm = sm;
2321f5207bJohn Levon			return false;
2331f5207bJohn Levon		}
2341f5207bJohn Levon
2351f5207bJohn Levon		if (!insert_sm(avl, &node->lr[side(cmp)], sm))
2361f5207bJohn Levon			return false;
2371f5207bJohn Levon
2381f5207bJohn Levon		/* If tree's balance became -1 or 1, it means the tree's height grew due to insertion. */
2391f5207bJohn Levon		return sway(p, cmp) != 0;
2401f5207bJohn Levon	}
2411f5207bJohn Levon}
2421f5207bJohn Levon
2431f5207bJohn Levon/*
2441f5207bJohn Levon * Remove the node matching the given sm.
2451f5207bJohn Levon * If present, return the removed node through *ret .
2461f5207bJohn Levon * The returned node's lr and balance are meaningless.
2471f5207bJohn Levon *
2481f5207bJohn Levon * Return true if the subtree's height decreased.
2491f5207bJohn Levon */
2501f5207bJohn Levonstatic bool remove_sm(struct stree *avl, AvlNode **p, const struct sm_state *sm, AvlNode **ret)
2511f5207bJohn Levon{
2521f5207bJohn Levon	if (p == NULL || *p == NULL) {
2531f5207bJohn Levon		return false;
2541f5207bJohn Levon	} else {
2551f5207bJohn Levon		AvlNode *node = *p;
2561f5207bJohn Levon		int      cmp  = cmp_tracker(sm, node->sm);
2571f5207bJohn Levon
2581f5207bJohn Levon		if (cmp == 0) {
2591f5207bJohn Levon			*ret = node;
2601f5207bJohn Levon			avl->count--;
2611f5207bJohn Levon
2621f5207bJohn Levon			if (node->lr[0] != NULL && node->lr[1] != NULL) {
2631f5207bJohn Levon				AvlNode *replacement;
2641f5207bJohn Levon				int      side;
2651f5207bJohn Levon				bool     shrunk;
2661f5207bJohn Levon
2671f5207bJohn Levon				/* Pick a subtree to pull the replacement from such that
2681f5207bJohn Levon				 * this node doesn't have to be rebalanced. */
2691f5207bJohn Levon				side = node->balance <= 0 ? 0 : 1;
2701f5207bJohn Levon
2711f5207bJohn Levon				shrunk = removeExtremum(&node->lr[side], 1 - side, &replacement);
2721f5207bJohn Levon
2731f5207bJohn Levon				replacement->lr[0]   = node->lr[0];
2741f5207bJohn Levon				replacement->lr[1]   = node->lr[1];
2751f5207bJohn Levon				replacement->balance = node->balance;
2761f5207bJohn Levon				*p = replacement;
2771f5207bJohn Levon
2781f5207bJohn Levon				if (!shrunk)
2791f5207bJohn Levon					return false;
2801f5207bJohn Levon
2811f5207bJohn Levon				replacement->balance -= bal(side);
2821f5207bJohn Levon
2831f5207bJohn Levon				/* If tree's balance became 0, it means the tree's height shrank due to removal. */
2841f5207bJohn Levon				return replacement->balance == 0;
2851f5207bJohn Levon			}
2861f5207bJohn Levon
2871f5207bJohn Levon			if (node->lr[0] != NULL)
2881f5207bJohn Levon				*p = node->lr[0];
2891f5207bJohn Levon			else
2901f5207bJohn Levon				*p = node->lr[1];
2911f5207bJohn Levon
2921f5207bJohn Levon			return true;
2931f5207bJohn Levon
2941f5207bJohn Levon		} else {
2951f5207bJohn Levon			if (!remove_sm(avl, &node->lr[side(cmp)], sm, ret))
2961f5207bJohn Levon				return false;
2971f5207bJohn Levon
2981f5207bJohn Levon			/* If tree's balance became 0, it means the tree's height shrank due to removal. */
2991f5207bJohn Levon			return sway(p, -cmp) == 0;
3001f5207bJohn Levon		}
3011f5207bJohn Levon	}
3021f5207bJohn Levon}
3031f5207bJohn Levon
3041f5207bJohn Levon/*
3051f5207bJohn Levon * Remove either the left-most (if side == 0) or right-most (if side == 1)
3061f5207bJohn Levon * node in a subtree, returning the removed node through *ret .
3071f5207bJohn Levon * The returned node's lr and balance are meaningless.
3081f5207bJohn Levon *
3091f5207bJohn Levon * The subtree must not be empty (i.e. *p must not be NULL).
3101f5207bJohn Levon *
3111f5207bJohn Levon * Return true if the subtree's height decreased.
3121f5207bJohn Levon */
3131f5207bJohn Levonstatic bool removeExtremum(AvlNode **p, int side, AvlNode **ret)
3141f5207bJohn Levon{
3151f5207bJohn Levon	AvlNode *node = *p;
3161f5207bJohn Levon
3171f5207bJohn Levon	if (node->lr[side] == NULL) {
3181f5207bJohn Levon		*ret = node;
3191f5207bJohn Levon		*p = node->lr[1 - side];
3201f5207bJohn Levon		return true;
3211f5207bJohn Levon	}
3221f5207bJohn Levon
3231f5207bJohn Levon	if (!removeExtremum(&node->lr[side], side, ret))
3241f5207bJohn Levon		return false;
3251f5207bJohn Levon
3261f5207bJohn Levon	/* If tree's balance became 0, it means the tree's height shrank due to removal. */
3271f5207bJohn Levon	return sway(p, -bal(side)) == 0;
3281f5207bJohn Levon}
3291f5207bJohn Levon
3301f5207bJohn Levon/*
3311f5207bJohn Levon * Rebalance a node if necessary.  Think of this function
3321f5207bJohn Levon * as a higher-level interface to balance().
3331f5207bJohn Levon *
3341f5207bJohn Levon * sway must be either -1 or 1, and indicates what was added to
3351f5207bJohn Levon * the balance of this node by a prior operation.
3361f5207bJohn Levon *
3371f5207bJohn Levon * Return the new balance of the subtree.
3381f5207bJohn Levon */
3391f5207bJohn Levonstatic int sway(AvlNode **p, int sway)
3401f5207bJohn Levon{
3411f5207bJohn Levon	if ((*p)->balance != sway)
3421f5207bJohn Levon		(*p)->balance += sway;
3431f5207bJohn Levon	else
3441f5207bJohn Levon		balance(p, side(sway));
3451f5207bJohn Levon
3461f5207bJohn Levon	return (*p)->balance;
3471f5207bJohn Levon}
3481f5207bJohn Levon
3491f5207bJohn Levon/*
3501f5207bJohn Levon * Perform tree rotations on an unbalanced node.
3511f5207bJohn Levon *
3521f5207bJohn Levon * side == 0 means the node's balance is -2 .
3531f5207bJohn Levon * side == 1 means the node's balance is +2 .
3541f5207bJohn Levon */
3551f5207bJohn Levonstatic void balance(AvlNode **p, int side)
3561f5207bJohn Levon{
3571f5207bJohn Levon	AvlNode  *node  = *p,
3581f5207bJohn Levon	         *child = node->lr[side];
3591f5207bJohn Levon	int opposite    = 1 - side;
3601f5207bJohn Levon	int bal         = bal(side);
3611f5207bJohn Levon
3621f5207bJohn Levon	if (child->balance != -bal) {
3631f5207bJohn Levon		/* Left-left (side == 0) or right-right (side == 1) */
3641f5207bJohn Levon		node->lr[side]      = child->lr[opposite];
3651f5207bJohn Levon		child->lr[opposite] = node;
3661f5207bJohn Levon		*p = child;
3671f5207bJohn Levon
3681f5207bJohn Levon		child->balance -= bal;
3691f5207bJohn Levon		node->balance = -child->balance;
3701f5207bJohn Levon
3711f5207bJohn Levon	} else {
3721f5207bJohn Levon		/* Left-right (side == 0) or right-left (side == 1) */
3731f5207bJohn Levon		AvlNode *grandchild = child->lr[opposite];
3741f5207bJohn Levon
3751f5207bJohn Levon		node->lr[side]           = grandchild->lr[opposite];
3761f5207bJohn Levon		child->lr[opposite]      = grandchild->lr[side];
3771f5207bJohn Levon		grandchild->lr[side]     = child;
3781f5207bJohn Levon		grandchild->lr[opposite] = node;
3791f5207bJohn Levon		*p = grandchild;
3801f5207bJohn Levon
3811f5207bJohn Levon		node->balance       = 0;
3821f5207bJohn Levon		child->balance      = 0;
3831f5207bJohn Levon
3841f5207bJohn Levon		if (grandchild->balance == bal)
3851f5207bJohn Levon			node->balance  = -bal;
3861f5207bJohn Levon		else if (grandchild->balance == -bal)
3871f5207bJohn Levon			child->balance = bal;
3881f5207bJohn Levon
3891f5207bJohn Levon		grandchild->balance = 0;
3901f5207bJohn Levon	}
3911f5207bJohn Levon}
3921f5207bJohn Levon
3931f5207bJohn Levon
3941f5207bJohn Levon/************************* avl_check_invariants() *************************/
3951f5207bJohn Levon
3961f5207bJohn Levonbool avl_check_invariants(struct stree *avl)
3971f5207bJohn Levon{
3981f5207bJohn Levon	int    dummy;
3991f5207bJohn Levon
4001f5207bJohn Levon	return checkBalances(avl->root, &dummy)
4011f5207bJohn Levon	    && checkOrder(avl)
4021f5207bJohn Levon	    && countNode(avl->root) == avl->count;
4031f5207bJohn Levon}
4041f5207bJohn Levon
4051f5207bJohn Levonstatic bool checkBalances(AvlNode *node, int *height)
4061f5207bJohn Levon{
4071f5207bJohn Levon	if (node) {
4081f5207bJohn Levon		int h0, h1;
4091f5207bJohn Levon
4101f5207bJohn Levon		if (!checkBalances(node->lr[0], &h0))
4111f5207bJohn Levon			return false;
4121f5207bJohn Levon		if (!checkBalances(node->lr[1], &h1))
4131f5207bJohn Levon			return false;
4141f5207bJohn Levon
4151f5207bJohn Levon		if (node->balance != h1 - h0 || node->balance < -1 || node->balance > 1)
4161f5207bJohn Levon			return false;
4171f5207bJohn Levon
4181f5207bJohn Levon		*height = (h0 > h1 ? h0 : h1) + 1;
4191f5207bJohn Levon		return true;
4201f5207bJohn Levon	} else {
4211f5207bJohn Levon		*height = 0;
4221f5207bJohn Levon		return true;
4231f5207bJohn Levon	}
4241f5207bJohn Levon}
4251f5207bJohn Levon
4261f5207bJohn Levonstatic bool checkOrder(struct stree *avl)
4271f5207bJohn Levon{
4281f5207bJohn Levon	AvlIter     i;
4291f5207bJohn Levon	const struct sm_state *last = NULL;
4301f5207bJohn Levon	bool        last_set = false;
4311f5207bJohn Levon
4321f5207bJohn Levon	avl_foreach(i, avl) {
4331f5207bJohn Levon		if (last_set && cmp_tracker(last, i.sm) >= 0)
4341f5207bJohn Levon			return false;
4351f5207bJohn Levon		last     = i.sm;
4361f5207bJohn Levon		last_set = true;
4371f5207bJohn Levon	}
4381f5207bJohn Levon
4391f5207bJohn Levon	return true;
4401f5207bJohn Levon}
4411f5207bJohn Levon
4421f5207bJohn Levonstatic size_t countNode(AvlNode *node)
4431f5207bJohn Levon{
4441f5207bJohn Levon	if (node)
4451f5207bJohn Levon		return 1 + countNode(node->lr[0]) + countNode(node->lr[1]);
4461f5207bJohn Levon	else
4471f5207bJohn Levon		return 0;
4481f5207bJohn Levon}
4491f5207bJohn Levon
4501f5207bJohn Levon
4511f5207bJohn Levon/************************* Traversal *************************/
4521f5207bJohn Levon
4531f5207bJohn Levonvoid avl_iter_begin(AvlIter *iter, struct stree *avl, AvlDirection dir)
4541f5207bJohn Levon{
4551f5207bJohn Levon	AvlNode *node;
4561f5207bJohn Levon
4571f5207bJohn Levon	iter->stack_index = 0;
4581f5207bJohn Levon	iter->direction   = dir;
4591f5207bJohn Levon
4601f5207bJohn Levon	if (!avl || !avl->root) {
4611f5207bJohn Levon		iter->sm      = NULL;
4621f5207bJohn Levon		iter->node     = NULL;
4631f5207bJohn Levon		return;
4641f5207bJohn Levon	}
4651f5207bJohn Levon	node = avl->root;
4661f5207bJohn Levon
4671f5207bJohn Levon	while (node->lr[dir] != NULL) {
4681f5207bJohn Levon		iter->stack[iter->stack_index++] = node;
4691f5207bJohn Levon		node = node->lr[dir];
4701f5207bJohn Levon	}
4711f5207bJohn Levon
4721f5207bJohn Levon	iter->sm   = (struct sm_state *) node->sm;
4731f5207bJohn Levon	iter->node  = node;
4741f5207bJohn Levon}
4751f5207bJohn Levon
4761f5207bJohn Levonvoid avl_iter_next(AvlIter *iter)
4771f5207bJohn Levon{
4781f5207bJohn Levon	AvlNode     *node = iter->node;
4791f5207bJohn Levon	AvlDirection dir  = iter->direction;
4801f5207bJohn Levon
4811f5207bJohn Levon	if (node == NULL)
4821f5207bJohn Levon		return;
4831f5207bJohn Levon
4841f5207bJohn Levon	node = node->lr[1 - dir];
4851f5207bJohn Levon	if (node != NULL) {
4861f5207bJohn Levon		while (node->lr[dir] != NULL) {
4871f5207bJohn Levon			iter->stack[iter->stack_index++] = node;
4881f5207bJohn Levon			node = node->lr[dir];
4891f5207bJohn Levon		}
4901f5207bJohn Levon	} else if (iter->stack_index > 0) {
4911f5207bJohn Levon		node = iter->stack[--iter->stack_index];
4921f5207bJohn Levon	} else {
4931f5207bJohn Levon		iter->sm      = NULL;
4941f5207bJohn Levon		iter->node     = NULL;
4951f5207bJohn Levon		return;
4961f5207bJohn Levon	}
4971f5207bJohn Levon
4981f5207bJohn Levon	iter->node  = node;
4991f5207bJohn Levon	iter->sm   = (struct sm_state *) node->sm;
5001f5207bJohn Levon}
5011f5207bJohn Levon
5021f5207bJohn Levonstruct stree *clone_stree(struct stree *orig)
5031f5207bJohn Levon{
5041f5207bJohn Levon	if (!orig)
5051f5207bJohn Levon		return NULL;
5061f5207bJohn Levon
5071f5207bJohn Levon	orig->references++;
5081f5207bJohn Levon	return orig;
5091f5207bJohn Levon}
5101f5207bJohn Levon
5111f5207bJohn Levonvoid set_stree_id(struct stree **stree, int stree_id)
5121f5207bJohn Levon{
5131f5207bJohn Levon	if ((*stree)->stree_id != 0)
5141f5207bJohn Levon		*stree = clone_stree_real(*stree);
5151f5207bJohn Levon
5161f5207bJohn Levon	(*stree)->stree_id = stree_id;
5171f5207bJohn Levon}
5181f5207bJohn Levon
5191f5207bJohn Levonint get_stree_id(struct stree *stree)
5201f5207bJohn Levon{
5211f5207bJohn Levon	if (!stree)
5221f5207bJohn Levon		return -1;
5231f5207bJohn Levon	return stree->stree_id;
5241f5207bJohn Levon}
525