/*
 * This routine does an exhaustive check on the groups file.
 * It weeds out:
 *
 * all redundant additions.
 * all !groups that don't filter anything.
 * all groups that don't match any of the actives.
 *
 * Any such groups are deleted.
 *
 * CP is not considered an issue...
 */

#include "gup.h"


/* Remove all superfluous groups */

void
prune(active_list, group_list)

    LIST	*active_list;
    LIST	*group_list;

{
    GROUP	*gp;
    GROUP	*ap;

#ifndef OLD_PRUNE
    /* tag the active list */
    TRAVERSE(active_list, ap) {
	ap->u.tag = NULL;

	TRAVERSE(group_list, gp) {
	    if (wildmat(ap->name, gp->name)) {
		TAG	*t = (TAG *)malloc(sizeof(TAG));
		if (!t) {
		    logit(L_BOTH, "WARNING", "insufficient memory to prune!");
		    return;
		}

		/* add the group to the front of this ap's tag list */
		t->group = gp;
		t->next = ap->u.tag;
		ap->u.tag = t;
	    }
	}
    }

    /* iterate the groups list to see if each group any effect on the active */
    TRAVERSE(group_list, gp) {
	int	effect = FALSE;

	TRAVERSE(active_list, ap) {
	    TAG	*tag = ap->u.tag;

	    /* does gp affect ap? */
	    if (tag && (tag->group == gp) && ((!tag->next && !gp->u.not) ||
		    (tag->next && (tag->next->group->u.not != gp->u.not)))) {
		effect = TRUE;
		break;
	    }
	}

	if (!effect) {
	    /* group doesn't do anything - clobber it */

	    /*
	     * remove it from any tags in which it appears - makes the
	     * tag-check faster.  We *could* have done an active tag list
	     * for each group to speed this, but it at the expense of the
	     * initial tagging process.  As implemented here, we assume
	     * pruning is a relatively rare occurrence.
	     */
	    TRAVERSE(active_list, ap) {
		TAG	*t, *prev;

		for (prev = NULL, t = ap->u.tag; t; prev = t, t = t->next) {
		    if (t->group == gp) {
			if (!prev)
			    ap->u.tag = t->next;
			else
			    prev->next = t->next;
			free((char*) t);

			break;
		    }
		}
	    }

	    remove_group(group_list, gp);

	    sprintf(msg, "%s %s subsumed",
		    gp->u.not ? "exclude" : "include", gp->name);
	    logit(L_BOTH, "PRUNED", msg);
	}
    }
#else
    GROUP	*gp1;
    int		active_list_length = LIST_LENGTH(active_list);
    char	*orig_selections;
    char	*cumulative_selections;
    char	*new_selections;
    char	*sel;

#ifdef USE_ALLOCA
    orig_selections = alloca(active_list_length);
    cumulative_selections = alloca(active_list_length);
    new_selections = alloca(active_list_length);
#else
    orig_selections = (char *)malloc(active_list_length);
    cumulative_selections = (char *)malloc(active_list_length);
    new_selections = (char *)malloc(active_list_length);
#endif
    if (!orig_selections || !new_selections)
	gupout(1, "unable to prune due to malloc failure");

    /* to do this checking correctly, the complete list of groups produced by
     * group_list must be compared with the groups expanded when an entry is
     * removed.  If they are the same, the entry can be removed.
     */

    memset(orig_selections, 0, active_list_length);
    memset(cumulative_selections, 0, active_list_length);

    /* evaluate the effect of the full groups list */
    sel = orig_selections;
    TRAVERSE(active_list, ap) {
	TRAVERSE(group_list, gp) {
	    if (wildmat(ap->name, gp->name))
		*sel = !gp->not;
	}
	sel++;
    }

    /* now see if removing any entries is OK */
    TRAVERSE(group_list, gp) {
	memcpy(new_selections, cumulative_selections, active_list_length);

	/* evaluate what happens when we remove gp from the list */
	sel = new_selections;
	TRAVERSE(active_list, ap) {
	    for (gp1 = gp, NEXT(group_list, gp1); gp1; NEXT(group_list, gp1)) {
		if (wildmat(ap->name, gp1->name))
		    *sel = !gp1->not;
	    }
	    sel++;
	}

	/* check what happened */
	if (!memcmp(orig_selections, new_selections, active_list_length)) {
	    sprintf(msg, "%s %s subsumed",
		    gp->not ? "exclude" : "include", gp->name);
	    logit(L_BOTH, "PRUNED", msg);
	    remove_group(group_list, gp);
	}
	else {
	    /* union this set with cumulative_selections */
	    sel = cumulative_selections;
	    TRAVERSE(active_list, ap) {
		if (wildmat(ap->name, gp->name))
		    *sel = !gp->not;
		sel++;
	    }
	}
    }

#ifndef USE_ALLOCA
    free(orig_selections);
    free(cumulative_selections);
    free(new_selections);
#endif
#endif /* OLD_PRUNE */
}
