4.3BSD/usr/ingres/source/parser/tree.c
# include <stdio.h>
# include <ingres.h>
# include <aux.h>
# include <tree.h>
# include <pv.h>
# include "parser.h"
# include <symbol.h>
# include <sccs.h>
# include <errors.h>
SCCSID(@(#)tree.c 8.3 2/8/85)
/*
** TREE
** FUNCTION TO ADD NODE TO QUERY TREE
** RETURN VALUE IS POINTER TO NODE JUST CREATED
*/
QTREE *
tree(lptr, rptr, typ, len, valu, attnum)
QTREE *lptr;
QTREE *rptr;
char typ;
int len;
register int valu;
register struct atstash *attnum;
{
register QTREE *tptr;
extern char Trfrmt;
extern char Trfrml;
extern char *need();
extern QTREE *norm();
extern int Err_current;
# ifdef xPTR3
tTfp(55, 0, "tree type(%d), len(%d), value(%d).\n", typ, len, valu);
# endif
if (Err_current)
return (NULL);
/* Following is a hack. Sorry about that John. */
if (typ == AND)
len = sizeof (struct rootnode) - sizeof (short);
tptr = (QTREE *) need(Qbuf, QT_HDR_SIZ + len);
tptr->left = lptr;
tptr->right = rptr;
tptr->sym.type = typ;
tptr->sym.len = len;
switch (typ)
{
case VAR:
tptr->sym.value.sym_var.varno = valu & I1MASK;
tptr->sym.value.sym_var.attno = attnum->atbid;
tptr->sym.value.sym_var.varfrmt = attnum->atbfrmt;
tptr->sym.value.sym_var.varfrml = attnum->atbfrml;
tptr->sym.value.sym_var.valptr = NULL;
tptr->sym.value.sym_var.varstr = NULL;
break;
case ROOT:
case AGHEAD:
tptr->sym.value.sym_root.rootuser = valu;
break;
case TREE:
case BYHEAD:
case AND:
case OR:
case QLEND:
break;
case UOP:
case BOP:
tptr->sym.value.sym_op.opno = valu;
format(tptr);
break;
case COP:
if ((tptr->sym.value.sym_op.opno = getcop(valu)) == BADCOP)
{
/* bad const operator */
par_error(BADCONSTOP, WARN, valu, 0);
return(NULL);
}
break;
case AOP:
format(tptr->right);
tptr->sym.value.sym_op.agfrmt = Trfrmt;
tptr->sym.value.sym_op.agfrml = Trfrml;
case RESDOM:
tptr->sym.value.sym_resdom.resno = valu;
format(tptr);
tptr->sym.value.sym_resdom.resfrmt = Trfrmt;
tptr->sym.value.sym_resdom.resfrml = Trfrml;
break;
default:
/* INT, FLOAT, CHAR */
bmove(valu, &tptr->sym.value, len & I1MASK);
break;
}
return (tptr);
}
/*
** WINDUP
** assign resno's to resdoms of an agg fcn
*/
windup(ptr)
QTREE *ptr;
{
register int tot;
register int kk;
register QTREE *t;
/* COUNT THE RESDOM'S OF THIS TARGET LIST */
kk = 1;
for (t = ptr; t; t = t->left)
kk++;
tot = 1;
for (t=ptr; t;t = t->left)
t->sym.value.sym_resdom.resno = kk - tot++;
}
/*
** ADDRESDOM - makes a new entry for the target list
**
** Trname must contain the name of the resdom to
** use for the header, create and Rsdmno for append, replace
**
** the parameters are pointers to the subtrees to be
** suspended from the node
*/
QTREE *
addresdom(lptr, rptr)
QTREE *lptr, *rptr;
{
register QTREE *rtval;
register struct atstash *aptr;
char buf[10]; /* buffer type and length in ascii for dbu */
extern int Opflag;
extern int Rsdmno;
extern int Equel;
extern int Resrng;
extern char Trfrmt;
extern char Trfrml;
extern char *Trname;
extern PARRNG Parrng[];
extern QTREE *tree();
extern struct atstash *attlookup();
int temp;
switch (Opflag)
{
case mdSTOP:
rtval = NULL;
break;
case mdRETR:
case mdRET_UNI:
case mdVIEW:
Rsdmno++;
if (Rsdmno >= MAXDOM)
/* too many resdoms */
par_error(RESXTRA, FATAL, 0);
rtval = tree(lptr, rptr, RESDOM, sizeof (struct resdomnode), Rsdmno);
if (!Equel || Resrng)
{
/* buffer info for header or CREATE */
setp(PV_STR, Trname);
buf[0] = Trfrmt & I1MASK;
smove(iocv(Trfrml & I1MASK), &buf[1]);
setp(PV_STR, buf);
}
break;
default:
/*
** for append and replace, the result domain
** number is determined by the location of
** the attribute in the result relation
*/
if (sequal(Trname, "tid"))
/* attrib not found */
par_error(NOATTRIN, WARN, Trname,
trim_relname(Parrng[Resrng].vardesc.reldum.relid), 0);
# ifdef DISTRIB
if (sequal(Trname, "sid"))
/* attrib not found */
par_error(NOATTRIN, WARN, Trname,
trim_relname(Parrng[Resrng].vardesc.reldum.relid), 0);
# endif
aptr = attlookup(Resrng, Trname);
Rsdmno = aptr->atbid;
rtval = tree(lptr, rptr, RESDOM, sizeof (struct resdomnode), Rsdmno);
if (Opflag != mdPROT) /* INTEGRITY not possible here */
attcheck(aptr);
break;
}
return (rtval);
}
/*
** GETCOP
** routine to lookup 'string' in constant operators table
** constant table is declared in tables.y
** structure is defined in ../parser.h
*/
getcop(string)
char *string;
{
register struct constop *cpt;
register char *sptr;
extern struct constop Coptab[];
sptr = string;
for (cpt = Coptab; cpt->copname; cpt++)
if (sequal(sptr, cpt->copname))
return (cpt->copnum);
return (BADCOP);
}
/*
** SUBSTRING
** creates structure to save delimiters of a substring
** structure is defined in ../h/tree.h
*/
STRKEEPER
*substring(str,isname)
char *str;
int isname;
{
extern char *need();
STRKEEPER *s;
s = (STRKEEPER *) need(Qbuf,sizeof(STRKEEPER));
s->number[0] = 1;
s->string[0] = str;
if (isname)
s->flag[0] = 1;
if (str == NULL)
s->flag[0] |= 2;
return(s);
}
STRKEEPER
*endvals(interval,left,right)
STRKEEPER *interval;
int left,right;
{
if (left == '(')
interval->type[0] = OPEN;
else
interval->type[0] = CLOSED;
if (right == ')')
interval->type[1] = OPEN;
else
interval->type[1] = CLOSED;
return(interval);
}
setnumber(interval,num)
STRKEEPER *interval;
int *num;
{
interval->number[0] = *num;
}
groupstrings(left,right)
STRKEEPER *left,*right;
{
left->string[1] = right->string[0];
left->flag[1] = right->flag[0];
left->number[1] = right->number[0];
}
/*
** CHECK_BNF -- check the legality of a simplified BNF defnition
**
** Parameters:
** str-- the string to be checked
**
** Returns:
** 0 - the string is legal
** <0 - the string is not legal
** -1 : bracket,brace not matched
** -2 : hyphen misused
**
** Called by:
** make_tuples
**
** Comments:
** the string may not contain nested braces or brackets
** these chars have special meaning and must be
** backslashed: { } [ ] - \
**
*/
check_bnf(str)
char *str;
{
char *temp; /* temp ptr to string */
int len; /* length of string */
char ch; /* ptr to one char of string */
char nextch;
int inbrace=0; /* keeps track of braces */
int inbrak=0; /* keeps track of brackets */
len = strlen(str);
temp = str;
while (len > 0)
{
len--;
ch = *temp++;
switch (ch)
{
case LBRACKET:
if (!inbrace)
inbrak++;
else
return(-1);
break;
case RBRACKET:
inbrak--;
if (inbrak != 0)
return(-1);
break;
case LBRACE:
if (!inbrak)
inbrace++;
else
return(-1);
break;
case RBRACE:
inbrace--;
if (inbrace != 0)
return(-1);
break;
case '-':
return(-2);
break;
case '\\':
*temp++;
break;
default:
nextch = *temp;
if (nextch == '-')
{
*temp++;
len--;
if (!len)
return(-2);
ch = *temp;
switch(ch)
{
case LBRACKET:
case RBRACKET:
case LBRACE:
case RBRACE:
case '-':
return(-2);
break;
case '\\':
*temp++;
break;
default:
break;
}
}
}
}
if ((inbrace) || (inbrak))
return(-1);
return(0);
}
/*
** MAKE_TUPLES -- create the tuples for the 'rdelim' relation
** as specified by a user-defined delimitor
**
** Paramaters:
** desc--descriptor for the relation
** group--group name for the delimitor
** delim--name of the delimitor
** str-bnf string specifying the delimitor
**
** Returns:
** 0 if successful
** <0 if not successful
** -1,-2: BNF expression not legal
**
*/
make_tuples(desc,group,delim,str)
DESC *desc;
char *group;
char *delim;
char *str;
{
int err; /* error status of bnf string */
char *map; /* pointer to next string to make into bitmap */
int len; /* len of str */
int mlen; /* len of substring to make into bitmap */
int order; /* order of bitmap */
int type; /* type of interval ONE or ZEROMORE */
char ch; /* pointer to current char */
err = check_bnf(str);
if (err < 0)
return(err);
len = strlen(str);
order = 0;
while (len > 0)
{
order++;
map = str;
mlen = 0;
ch = *str++;
len--;
switch (ch)
{
case LBRACKET:
type = ONE;
map = str;
while ((ch = *str++) != RBRACKET)
{
mlen++;
len--;
if (ch == '\\')
{
ch = *str++;
mlen++;
len--;
}
}
len--;
break;
case LBRACE:
type = ZEROMORE;
map = str;
while ((ch = *str++) != RBRACE)
{
mlen++;
len--;
if (ch == '\\')
{
ch = *str++;
mlen++;
len--;
}
}
len--;
break;
default:
type = ONE;
if (ch == '\\')
{
map = str;
ch = *str++;
len--;
mlen = 1;
}
if (*str == '-')
{
*str++;
len--;
mlen++;
*str++;
len--;
mlen++;
}
else
mlen = 1;
break;
}
create_tup(desc,order,group,delim,type,map,mlen);
}
return(0);
}
/*
** CREATE_TUP-- create a tuple in the 'rdelim' relation
**
** Parameters:
** desc - descriptor for the relation
** order - order field for tuple
** group - group field for tuple
** delim - delim field for tuple
** type - type field for tuple
** str - string to be converted into bitmap
** strlen - length of str
**
** Called by:
** make_tuples
*/
create_tup(desc,order,group,delim,type,str,strlen)
DESC *desc;
int order;
char *group;
char *delim;
int type;
char *str;
int strlen;
{
DELIM_TUP *tuple;
char bitmap[BITMAPLEN];
TID *tid;
char *malloc();
char *make_dmap();
char b[BITMAPLEN];
int i;
tuple = (DELIM_TUP *) malloc (sizeof(DELIM_TUP));
tuple->order = order;
strcpy(tuple->group,group);
strcpy(tuple->delim,delim);
tuple->type = type;
make_dmap(str,strlen,b);
for ( i= 0; i< BITMAPLEN; i++)
tuple->bitmap[i] = b[i];
insert(desc,&tid,tuple,1);
}
/*
** MAKE_DMAP -- given a BNF string, make the corresponding bitmap
**
** Parameters:
** str - BNF string
** len - length of string
**
** Called by:
** create_tup
**
** Returns:
** pointer to the bitmap of 16 chars
**
** Comments:
** The bitmap is formed of 16 chars. The total bits
** (128) represents the characters of the ASCII set.
** If the BNF string indicates a character, the bit
** corresponding to that char is set in the bitmap.
** All other bits are reset.
*/
char *
make_dmap(str,len,b)
char *str;
int len;
char *b;
{
char ch;
char nextch;
int i;
# ifdef xPTR3
tTfp(42,0,"DMAP: str = %s, len = %d\n",str,len);
# endif
for (i = 0; i < ACHARS; i++)
reset(b,i);
while (len > 0)
{
ch = *str++;
len--;
if (ch == '\\')
{
ch = *str++;
len--;
}
if ( (len > 0) && (*str == '-'))
{
*str++;
len--;
nextch = *str++;
len--;
for (i = ch; i <= nextch; i++)
{
set(b,i);
}
}
else
{
set(b,ch);
}
}
return(b);
}
/*
** SET,RESET -- bitmap setting routines
**
** Parameters:
** map: the array of chars which forms the bitmap
** n: the bit to set or reset
**
** Called by:
** make_bitmap
**
*/
set(map,n)
char *map;
int n;
{
map[n/BITS] |= (1<<(n%BITS));
}
reset(map,n)
char *map;
int n;
{
map[n/BITS] &= ((1<<(n%BITS)) ^ MAXFIELD);
}
test(map,n)
char *map;
int n;
{
return ((map[n/BITS] & (1<<(n%BITS))) != 0);
}
/*
** MAKE_LIST -- puts the delimitors to be used in the delim queue
**
** Parameters:
** desc - descriptor for the relation
** group - group of delims to use
**
** Returns:
** 0 if ok
** -1 if no delims could be found in the specified group
**
** Comments:
** given a group name, adds all delimitors in that
** group to the head of the delim queue, which is
** pointed to by Delimhead.
** if the queue is empty, the predefined delimitors
** 'w' and 'c' will be added to the list
*/
make_list(desc,group)
DESC *desc;
char *group;
{
DELIM_TUP tuple;
TID lotid, hitid;
extern DELIMLIST *Delimhead;
DELIMLIST *d;
DMAP *map, *m;
char delim[12];
int start = 1;
extern char *malloc();
int i;
int notfound = 1;
# ifdef xPTR3
tTfp(42,0,"Make_list: group = %s\n", group);
# endif
if (!strcmp (group,"system"))
{
predef_delims();
return(0);
}
if (find(desc,LRANGEKEY, &lotid, &hitid, group) < 0)
return(-1);
find(desc,HRANGEKEY, &lotid, &hitid, group);
while (!get(desc, &lotid, &hitid, &tuple, 1))
{
if (strcmp(tuple.group, group))
{
continue;
}
notfound = FALSE;
/* check if it is a new delimitor */
if (strcmp(tuple.delim, delim))
start = 1;
/* start a new delimitor node */
if (start)
{
d = (DELIMLIST *) malloc( sizeof(DELIMLIST));
strcpy(delim, tuple.delim);
strcpy(d->group,tuple.group);
strcpy(d->delim,delim);
d->back = Delimhead;
Delimhead = d;
map = (DMAP *) malloc(sizeof(DMAP));
map->order = tuple.order;
map->type = tuple.type;
for ( i = 0; i < BITMAPLEN; i++)
map->bits[i] = tuple.bitmap[i];
map->next = NULL;
d->maptr = map;
m = map;
start = 0;
}
else /* add another bitmap to the delimitor node */
{
map = (DMAP *) malloc(sizeof(DMAP));
map->order = tuple.order;
map->type = tuple.type;
for ( i = 0; i < BITMAPLEN; i++)
map->bits[i] = tuple.bitmap[i];
map->next = NULL;
m->next = map;
m = m->next;
}
}
/*prlist(Delimhead); */
if (notfound)
return(-1);
return(0);
}
/*
** PREDEF_DELIMS - add the predefined delims to the queue
**
** Called by:
** make_list
**
** Side Effects:
** the delim queue pointed to by Delimhead
** is initialized with the delims 'w' and 'c'.
**
*/
predef_delims()
{
DELIMLIST *d;
DMAP *m, *m2;
int i;
d = (DELIMLIST * ) malloc(sizeof(DELIMLIST));
strcpy(d->group, "system");
strcpy(d->delim, "c");
d->back = NULL;
m = (DMAP *) malloc(sizeof (DMAP));
m->order = 1;
m->type = 0;
for (i = ' '; i <= '~'; i++)
set(m->bits, i);
m->next = NULL;
d->maptr = m;
Delimhead = d;
d = (DELIMLIST * ) malloc(sizeof(DELIMLIST));
strcpy(d->group, "system");
strcpy(d->delim, "w");
d->back = NULL;
m = (DMAP *) malloc(sizeof (DMAP));
m->order = 1;
m->type = 0;
for (i = 'A'; i <= 'Z'; i++)
set(m->bits, i);
for (i = 'a'; i <= 'z'; i++)
set(m->bits, i);
d->maptr = m;
m2 = (DMAP *) malloc(sizeof(DMAP));
m2->order = 2;
m2->type = 1;
for (i = 'A'; i <= 'Z'; i++)
set(m2->bits, i);
for (i = 'a'; i <= 'z'; i++)
set(m2->bits, i);
m->next = m2;
m2->next = NULL;
d->back = Delimhead;
Delimhead = d;
}
/*
** PRLIST -- print contents of delimiter queue
*/
prlist(d)
struct delimlist *d;
{
struct delimlist *q;
DMAP *m;
int i;
printf("DELIM QUEUE:\n");
q = d;
while (q != NULL)
{
printf("-------------------------------------------------------\n");
printf("NODE: group= %s, delim = %s \n", q->group, q->delim);
m = q->maptr;
while (m != NULL)
{
printf("maps:\n");
printf("order = %d, type = %d \n", m->order, m->type);
for (i = 0; i < ACHARS; i++)
printf("%d ", test(m->bits,i));
printf("\n");
m = m->next;
}
q = q->back;
printf("-------------------------------------------------------\n");
}
return(0);
}
/*
** SHRINK_LIST -- remove the delims in specified group from list
**
** Parameters:
** group - name of the group to remove
**
*/
shrink_list(group)
char *group;
{
struct delimlist *p, *q;
extern struct delimlist *Delimhead;
/* may not delete sytem delims */
if (!strcmp(group, "system"))
return(-1);
p = Delimhead;
while ((p != NULL) && (strcmp(p->group, group)))
{
q = p;
p = p->back;
}
if (p == NULL)
{
return(-1); /* error group not found */
}
while(!strcmp(p->group, group))
{
if (p == Delimhead)
Delimhead = p->back;
else
q->back = p->back;
if (p->back == NULL)
{
return(0);
}
p = p-> back;
}
/* prlist(Delimhead); */
return(0);
}
/*
** DESTROY_DELIM -- remove the group of delims from the relation 'rdelim'
**
** Parameters:
** group - the group of delims to remove
**
** Called By:
** grammar.y
**
** Returns:
** 0 if delims were successfully removed
** -1 if delims were not found in relation
*/
destroy_delim(desc, group)
DESC *desc;
char *group;
{
DELIM_TUP tuple;
TID lotid,hitid;
int notfound = 1;
if (find(desc,LRANGEKEY, &lotid, &hitid, group) < 0)
return(-1);
find(desc,HRANGEKEY, &lotid, &hitid, group);
while (!get(desc, &lotid, &hitid, &tuple, 1))
{
if (!strcmp(tuple.group, group))
{
notfound = 0;
delete(desc,&lotid);
}
}
if (notfound)
return(-1);
return(0);
}