purge_Exp()

#define EXP_STACKSIZE 1000
static void push_elist(E_list *s[], int *i, E_list *e)
{
	assert(*i < EXP_STACKSIZE, "push_elist(): Index overflow (=%d)\n", *i);
	s[(*i)++] = e;
}
static E_list *pop_elist(E_list *s[], int *i)
{
	//assert(*i > 0, "pop_elist() called with index=%d\n", *i);
	return s[--(*i)];
}
static E_list *pick_elist(E_list *s[], int i)
{
	return s[i];
}
static void setstack_elist(E_list *s[], int *i, int j)
{
	*i = j;
}

/**
 * Find the list head of the given element.
 * (Max. 2 iterations, as this is the max. E_list chain length).
 */
static int find_context(E_list *s[], int i)
{
	/* topmost element is at (i-1) */
	while (i-- >= 0)
	{
		if (s[i]->e->mark) break;
	}

	//assert(i >= 0, "find_context: Internal error\n");
	return i;
}

/**
 * Must be called with a non-null expression.
 * Return NULL iff the expression has no disjuncts.
 */
static Exp* purge_Exp(Exp *e)
{
	E_list exp_head = { NULL, e }; /* make the expression look like E_list */
	bool discard = false; /* discard next element */
	int si;
	E_list *s[EXP_STACKSIZE];

	s[0] = &exp_head;
	si = 1;
	e->mark = false; /* see comment at start of loop */

	while (si > 0)
	{
		/* State variables:
		 *
		 * 1. Expression mark field:
		 * If TRUE, it is for operation (AND or OR) context only. An element
		 * so marked is ignored when popped up (unless "discard", see (2)
		 * below). For next expression tree elements - set their mark to
		 * FALSE when pushed (so they will not be ignored).
		 *
		 * 2. Local variable "discard":
		 * If TRUE, the popped up element should be discarded from the
		 * expression tree (along with all of its decedents).
		 */
		E_list *p = pop_elist(s, &si);     /* current E_list */
		Exp *t = p->e;                     /* current expression */

		if (!discard && (t->type != CONNECTOR_type))
		{
			if (t->mark) continue;
			/* Retain it in the stack - for operator context. */
			t->mark = true;
			push_elist(s, &si, p);

			/* Push its E_list elements. */
			for (E_list *l = t->u.l; l != NULL; l = l->next)
			{
				l->e->mark = false;
				push_elist(s, &si, l);
			}
		}

		/* Process each E_List element "p" ("t" is its expression). */

		if (discard || ((CONNECTOR_type == t->type) && (NULL == t->u.condesc)))
		{
			if (0 == si)
			{
				/* The topmost element has been discarded. */
				free_Exp(t);
				e = NULL;
				break;
			}

			/* Find the root of this E_list. */
			int context = find_context(s, si);
			E_list *root = pick_elist(s, context);
			discard = false;

			if (AND_type == root->e->type)
			{
				/* Discard all the E_list elements of the root. */
				setstack_elist(s, &si, context+1);
				discard = true;    /* discard the AND root */
			}
			else /* OR_type */
			{
				/* Discard the element; first skip it, then free it. */
				E_list *el = pick_elist(s, si-1); /* previous element */
				E_list **n = (si-1 == context) ? &el->e->u.l : &el->next;
				*n = p->next;      /* skip the current element */
				free_E_list(p);    /* free it */

				if (NULL == root->e->u.l) /* all the OR elements got discarded */
					discard = true; /* discard the OR root */
			}
		}
	}

	return e;
}