utilities.c

agrep

/* this file contains various utility functions for accessing
   and manipulating regular expression syntax trees.	*/

#include <stdio.h>
#include "re.h"

/************************************************************************/
/*                                                                      */
/*  the following routines implement an abstract data type "stack".	*/
/*                                                                      */
/************************************************************************/

Stack Push(s, v)
Stack *s;
Re_node v;
{
    Stack node;

    node = (Stack) new_node(node);
    if (s == NULL || node == NULL) return NULL;	    /* can't allocate */
    node->next = *s;
    node->val = v;
    if (*s == NULL) node->size = 1;
    else node->size = (*s)->size + 1;
    *s = node;
    return *s;
}

Re_node Pop(s)
Stack *s;
{
    Re_node node;
    Stack temp;

    if (s == NULL || *s == NULL) return NULL;
    else {
	temp = *s;
	node = (*s)->val;
	*s = (*s)->next;
	free(temp);
	return node;
    }
}

Re_node Top(s)
Stack s;
{
    if (s == NULL) return NULL;
    else return s->val;
}

int Size(s)
Stack s;
{
    if (s == NULL) return 0;
    else return s->size;
}

/************************************************************************/
/*                                                                      */
/*	the following routines manipulate sets of positions.		*/
/*                                                                      */
/************************************************************************/

int occurs_in(n, p)
int n;
Pset p;
{
    while (p != NULL)
	if (n == p->posnum) return 1;
	else p = p->nextpos;
    return 0;
}

/* pset_union() takes two position-sets and returns their union.    */

Pset pset_union(s1, s2)
Pset s1, s2;
{
    Pset hd, curr, new;
    int occ;

    hd = NULL; curr = NULL;
    while (s1 != NULL) {
	if (!occurs_in(s1->posnum, s2)) {
	    new = (Pset) new_node(new);
	    if (new == NULL) return NULL;
	    new->posnum = s1->posnum;
	    if (hd == NULL) hd = new;
	    else curr->nextpos = new;
	}
	curr = new;
	s1 = s1->nextpos;
    }
    if (hd == NULL) hd = s2;
    else curr->nextpos = s2;
    return hd;
}

/* create_pos() creates a position node with the position value given,
   then returns a pointer to this node.					*/

Pset create_pos(n)
int n;
{
    Pset x;

    x = (Pset) new_node(x);
    if (x == NULL) return NULL;
    x->posnum = n;
    x->nextpos = NULL;
    return x;
}

/* eq_pset() takes two position sets and checks to see if they are
   equal.  It returns 1 if the sets are equal, 0 if they are not.	*/

subset_pset(s1, s2)
Pset s1, s2;
{
    int subs = 1;

    while (s1 != NULL && subs != 0) {
	subs = 0;
	while (s2 != NULL && subs != 1)
	    if (s1->posnum == s2->posnum) subs = 1;
	    else s2 = s2->nextpos;
	s1 = s1->nextpos;
    }
    return subs;
}	

int eq_pset(s1, s2)
Pset s1, s2;
{
    return subset_pset(s1, s2) && subset_pset(s2, s1);
}