![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / ingres / source / parser|
Return to tree.c CVS log | Up to [CSRG BSD Unix] / 43BSD / ingres / source / parser |
1.1 root 1: # include <stdio.h>
2: # include <ingres.h>
3: # include <aux.h>
4: # include <tree.h>
5: # include <pv.h>
6: # include "parser.h"
7: # include <symbol.h>
8: # include <sccs.h>
9: # include <errors.h>
10:
11: SCCSID(@(#)tree.c 8.3 2/8/85)
12:
13:
14: /*
15: ** TREE
16: ** FUNCTION TO ADD NODE TO QUERY TREE
17: ** RETURN VALUE IS POINTER TO NODE JUST CREATED
18: */
19: QTREE *
20: tree(lptr, rptr, typ, len, valu, attnum)
21: QTREE *lptr;
22: QTREE *rptr;
23: char typ;
24: int len;
25: register int valu;
26: register struct atstash *attnum;
27: {
28: register QTREE *tptr;
29: extern char Trfrmt;
30: extern char Trfrml;
31: extern char *need();
32: extern QTREE *norm();
33: extern int Err_current;
34:
35: # ifdef xPTR3
36: tTfp(55, 0, "tree type(%d), len(%d), value(%d).\n", typ, len, valu);
37: # endif
38:
39: if (Err_current)
40: return (NULL);
41:
42: /* Following is a hack. Sorry about that John. */
43: if (typ == AND)
44: len = sizeof (struct rootnode) - sizeof (short);
45:
46: tptr = (QTREE *) need(Qbuf, QT_HDR_SIZ + len);
47: tptr->left = lptr;
48: tptr->right = rptr;
49: tptr->sym.type = typ;
50: tptr->sym.len = len;
51:
52: switch (typ)
53: {
54: case VAR:
55: tptr->sym.value.sym_var.varno = valu & I1MASK;
56: tptr->sym.value.sym_var.attno = attnum->atbid;
57: tptr->sym.value.sym_var.varfrmt = attnum->atbfrmt;
58: tptr->sym.value.sym_var.varfrml = attnum->atbfrml;
59: tptr->sym.value.sym_var.valptr = NULL;
60: tptr->sym.value.sym_var.varstr = NULL;
61: break;
62:
63: case ROOT:
64: case AGHEAD:
65: tptr->sym.value.sym_root.rootuser = valu;
66: break;
67:
68: case TREE:
69: case BYHEAD:
70: case AND:
71: case OR:
72: case QLEND:
73: break;
74:
75: case UOP:
76: case BOP:
77: tptr->sym.value.sym_op.opno = valu;
78: format(tptr);
79: break;
80:
81: case COP:
82: if ((tptr->sym.value.sym_op.opno = getcop(valu)) == BADCOP)
83: {
84: /* bad const operator */
85: par_error(BADCONSTOP, WARN, valu, 0);
86: return(NULL);
87: }
88: break;
89:
90: case AOP:
91: format(tptr->right);
92: tptr->sym.value.sym_op.agfrmt = Trfrmt;
93: tptr->sym.value.sym_op.agfrml = Trfrml;
94:
95: case RESDOM:
96: tptr->sym.value.sym_resdom.resno = valu;
97: format(tptr);
98: tptr->sym.value.sym_resdom.resfrmt = Trfrmt;
99: tptr->sym.value.sym_resdom.resfrml = Trfrml;
100: break;
101:
102: default:
103: /* INT, FLOAT, CHAR */
104: bmove(valu, &tptr->sym.value, len & I1MASK);
105: break;
106: }
107: return (tptr);
108: }
109:
110: /*
111: ** WINDUP
112: ** assign resno's to resdoms of an agg fcn
113: */
114: windup(ptr)
115: QTREE *ptr;
116: {
117: register int tot;
118: register int kk;
119: register QTREE *t;
120:
121: /* COUNT THE RESDOM'S OF THIS TARGET LIST */
122: kk = 1;
123: for (t = ptr; t; t = t->left)
124: kk++;
125: tot = 1;
126: for (t=ptr; t;t = t->left)
127: t->sym.value.sym_resdom.resno = kk - tot++;
128: }
129:
130: /*
131: ** ADDRESDOM - makes a new entry for the target list
132: **
133: ** Trname must contain the name of the resdom to
134: ** use for the header, create and Rsdmno for append, replace
135: **
136: ** the parameters are pointers to the subtrees to be
137: ** suspended from the node
138: */
139: QTREE *
140: addresdom(lptr, rptr)
141: QTREE *lptr, *rptr;
142: {
143: register QTREE *rtval;
144: register struct atstash *aptr;
145: char buf[10]; /* buffer type and length in ascii for dbu */
146:
147: extern int Opflag;
148: extern int Rsdmno;
149: extern int Equel;
150: extern int Resrng;
151: extern char Trfrmt;
152: extern char Trfrml;
153: extern char *Trname;
154: extern PARRNG Parrng[];
155:
156: extern QTREE *tree();
157: extern struct atstash *attlookup();
158:
159: int temp;
160:
161: switch (Opflag)
162: {
163: case mdSTOP:
164: rtval = NULL;
165: break;
166: case mdRETR:
167: case mdRET_UNI:
168: case mdVIEW:
169: Rsdmno++;
170: if (Rsdmno >= MAXDOM)
171: /* too many resdoms */
172: par_error(RESXTRA, FATAL, 0);
173: rtval = tree(lptr, rptr, RESDOM, sizeof (struct resdomnode), Rsdmno);
174: if (!Equel || Resrng)
175: {
176: /* buffer info for header or CREATE */
177: setp(PV_STR, Trname);
178:
179: buf[0] = Trfrmt & I1MASK;
180: smove(iocv(Trfrml & I1MASK), &buf[1]);
181:
182: setp(PV_STR, buf);
183: }
184: break;
185:
186: default:
187: /*
188: ** for append and replace, the result domain
189: ** number is determined by the location of
190: ** the attribute in the result relation
191: */
192: if (sequal(Trname, "tid"))
193: /* attrib not found */
194: par_error(NOATTRIN, WARN, Trname,
195: trim_relname(Parrng[Resrng].vardesc.reldum.relid), 0);
196: # ifdef DISTRIB
197: if (sequal(Trname, "sid"))
198: /* attrib not found */
199: par_error(NOATTRIN, WARN, Trname,
200: trim_relname(Parrng[Resrng].vardesc.reldum.relid), 0);
201: # endif
202: aptr = attlookup(Resrng, Trname);
203: Rsdmno = aptr->atbid;
204: rtval = tree(lptr, rptr, RESDOM, sizeof (struct resdomnode), Rsdmno);
205: if (Opflag != mdPROT) /* INTEGRITY not possible here */
206: attcheck(aptr);
207: break;
208: }
209: return (rtval);
210: }
211: /*
212: ** GETCOP
213: ** routine to lookup 'string' in constant operators table
214: ** constant table is declared in tables.y
215: ** structure is defined in ../parser.h
216: */
217: getcop(string)
218: char *string;
219: {
220: register struct constop *cpt;
221: register char *sptr;
222: extern struct constop Coptab[];
223:
224: sptr = string;
225: for (cpt = Coptab; cpt->copname; cpt++)
226: if (sequal(sptr, cpt->copname))
227: return (cpt->copnum);
228: return (BADCOP);
229: }
230:
231: /*
232: ** SUBSTRING
233: ** creates structure to save delimiters of a substring
234: ** structure is defined in ../h/tree.h
235: */
236: STRKEEPER
237: *substring(str,isname)
238: char *str;
239: int isname;
240: {
241: extern char *need();
242: STRKEEPER *s;
243:
244: s = (STRKEEPER *) need(Qbuf,sizeof(STRKEEPER));
245: s->number[0] = 1;
246: s->string[0] = str;
247: if (isname)
248: s->flag[0] = 1;
249: if (str == NULL)
250: s->flag[0] |= 2;
251: return(s);
252: }
253:
254: STRKEEPER
255: *endvals(interval,left,right)
256: STRKEEPER *interval;
257: int left,right;
258: {
259: if (left == '(')
260: interval->type[0] = OPEN;
261: else
262: interval->type[0] = CLOSED;
263: if (right == ')')
264: interval->type[1] = OPEN;
265: else
266: interval->type[1] = CLOSED;
267: return(interval);
268: }
269:
270: setnumber(interval,num)
271: STRKEEPER *interval;
272: int *num;
273: {
274: interval->number[0] = *num;
275: }
276:
277:
278: groupstrings(left,right)
279: STRKEEPER *left,*right;
280: {
281: left->string[1] = right->string[0];
282: left->flag[1] = right->flag[0];
283: left->number[1] = right->number[0];
284: }
285:
286:
287: /*
288: ** CHECK_BNF -- check the legality of a simplified BNF defnition
289: **
290: ** Parameters:
291: ** str-- the string to be checked
292: **
293: ** Returns:
294: ** 0 - the string is legal
295: ** <0 - the string is not legal
296: ** -1 : bracket,brace not matched
297: ** -2 : hyphen misused
298: **
299: ** Called by:
300: ** make_tuples
301: **
302: ** Comments:
303: ** the string may not contain nested braces or brackets
304: ** these chars have special meaning and must be
305: ** backslashed: { } [ ] - \
306: **
307: */
308:
309: check_bnf(str)
310: char *str;
311: {
312: char *temp; /* temp ptr to string */
313: int len; /* length of string */
314: char ch; /* ptr to one char of string */
315: char nextch;
316: int inbrace=0; /* keeps track of braces */
317: int inbrak=0; /* keeps track of brackets */
318:
319:
320: len = strlen(str);
321: temp = str;
322:
323: while (len > 0)
324: {
325: len--;
326: ch = *temp++;
327:
328: switch (ch)
329: {
330: case LBRACKET:
331: if (!inbrace)
332: inbrak++;
333: else
334: return(-1);
335: break;
336: case RBRACKET:
337: inbrak--;
338: if (inbrak != 0)
339: return(-1);
340: break;
341: case LBRACE:
342: if (!inbrak)
343: inbrace++;
344: else
345: return(-1);
346: break;
347: case RBRACE:
348: inbrace--;
349: if (inbrace != 0)
350: return(-1);
351: break;
352: case '-':
353: return(-2);
354: break;
355: case '\\':
356: *temp++;
357: break;
358: default:
359: nextch = *temp;
360: if (nextch == '-')
361: {
362: *temp++;
363: len--;
364: if (!len)
365: return(-2);
366: ch = *temp;
367: switch(ch)
368: {
369: case LBRACKET:
370: case RBRACKET:
371: case LBRACE:
372: case RBRACE:
373: case '-':
374: return(-2);
375: break;
376: case '\\':
377: *temp++;
378: break;
379: default:
380: break;
381: }
382: }
383: }
384: }
385: if ((inbrace) || (inbrak))
386: return(-1);
387: return(0);
388: }
389:
390:
391: /*
392: ** MAKE_TUPLES -- create the tuples for the 'rdelim' relation
393: ** as specified by a user-defined delimitor
394: **
395: ** Paramaters:
396: ** desc--descriptor for the relation
397: ** group--group name for the delimitor
398: ** delim--name of the delimitor
399: ** str-bnf string specifying the delimitor
400: **
401: ** Returns:
402: ** 0 if successful
403: ** <0 if not successful
404: ** -1,-2: BNF expression not legal
405: **
406: */
407: make_tuples(desc,group,delim,str)
408: DESC *desc;
409: char *group;
410: char *delim;
411: char *str;
412: {
413: int err; /* error status of bnf string */
414: char *map; /* pointer to next string to make into bitmap */
415: int len; /* len of str */
416: int mlen; /* len of substring to make into bitmap */
417: int order; /* order of bitmap */
418: int type; /* type of interval ONE or ZEROMORE */
419: char ch; /* pointer to current char */
420:
421: err = check_bnf(str);
422: if (err < 0)
423: return(err);
424:
425: len = strlen(str);
426: order = 0;
427:
428: while (len > 0)
429: {
430: order++;
431: map = str;
432: mlen = 0;
433:
434: ch = *str++;
435: len--;
436:
437: switch (ch)
438: {
439: case LBRACKET:
440: type = ONE;
441: map = str;
442: while ((ch = *str++) != RBRACKET)
443: {
444: mlen++;
445: len--;
446: if (ch == '\\')
447: {
448: ch = *str++;
449: mlen++;
450: len--;
451: }
452: }
453: len--;
454: break;
455:
456: case LBRACE:
457: type = ZEROMORE;
458: map = str;
459: while ((ch = *str++) != RBRACE)
460: {
461: mlen++;
462: len--;
463: if (ch == '\\')
464: {
465: ch = *str++;
466: mlen++;
467: len--;
468: }
469: }
470: len--;
471: break;
472:
473: default:
474: type = ONE;
475: if (ch == '\\')
476: {
477: map = str;
478: ch = *str++;
479: len--;
480: mlen = 1;
481: }
482: if (*str == '-')
483: {
484: *str++;
485: len--;
486: mlen++;
487: *str++;
488: len--;
489: mlen++;
490: }
491: else
492: mlen = 1;
493: break;
494: }
495:
496: create_tup(desc,order,group,delim,type,map,mlen);
497: }
498: return(0);
499: }
500:
501:
502:
503: /*
504: ** CREATE_TUP-- create a tuple in the 'rdelim' relation
505: **
506: ** Parameters:
507: ** desc - descriptor for the relation
508: ** order - order field for tuple
509: ** group - group field for tuple
510: ** delim - delim field for tuple
511: ** type - type field for tuple
512: ** str - string to be converted into bitmap
513: ** strlen - length of str
514: **
515: ** Called by:
516: ** make_tuples
517: */
518: create_tup(desc,order,group,delim,type,str,strlen)
519: DESC *desc;
520: int order;
521: char *group;
522: char *delim;
523: int type;
524: char *str;
525: int strlen;
526: {
527: DELIM_TUP *tuple;
528: char bitmap[BITMAPLEN];
529: TID *tid;
530: char *malloc();
531: char *make_dmap();
532: char b[BITMAPLEN];
533: int i;
534:
535:
536: tuple = (DELIM_TUP *) malloc (sizeof(DELIM_TUP));
537: tuple->order = order;
538: strcpy(tuple->group,group);
539: strcpy(tuple->delim,delim);
540: tuple->type = type;
541:
542: make_dmap(str,strlen,b);
543: for ( i= 0; i< BITMAPLEN; i++)
544: tuple->bitmap[i] = b[i];
545:
546: insert(desc,&tid,tuple,1);
547: }
548:
549:
550: /*
551: ** MAKE_DMAP -- given a BNF string, make the corresponding bitmap
552: **
553: ** Parameters:
554: ** str - BNF string
555: ** len - length of string
556: **
557: ** Called by:
558: ** create_tup
559: **
560: ** Returns:
561: ** pointer to the bitmap of 16 chars
562: **
563: ** Comments:
564: ** The bitmap is formed of 16 chars. The total bits
565: ** (128) represents the characters of the ASCII set.
566: ** If the BNF string indicates a character, the bit
567: ** corresponding to that char is set in the bitmap.
568: ** All other bits are reset.
569: */
570: char *
571: make_dmap(str,len,b)
572: char *str;
573: int len;
574: char *b;
575: {
576: char ch;
577: char nextch;
578: int i;
579:
580: # ifdef xPTR3
581: tTfp(42,0,"DMAP: str = %s, len = %d\n",str,len);
582: # endif
583: for (i = 0; i < ACHARS; i++)
584: reset(b,i);
585:
586: while (len > 0)
587: {
588: ch = *str++;
589: len--;
590: if (ch == '\\')
591: {
592: ch = *str++;
593: len--;
594: }
595: if ( (len > 0) && (*str == '-'))
596: {
597: *str++;
598: len--;
599: nextch = *str++;
600: len--;
601: for (i = ch; i <= nextch; i++)
602: {
603: set(b,i);
604: }
605: }
606: else
607: {
608: set(b,ch);
609: }
610: }
611: return(b);
612: }
613:
614: /*
615: ** SET,RESET -- bitmap setting routines
616: **
617: ** Parameters:
618: ** map: the array of chars which forms the bitmap
619: ** n: the bit to set or reset
620: **
621: ** Called by:
622: ** make_bitmap
623: **
624: */
625: set(map,n)
626: char *map;
627: int n;
628: {
629: map[n/BITS] |= (1<<(n%BITS));
630: }
631:
632: reset(map,n)
633: char *map;
634: int n;
635: {
636: map[n/BITS] &= ((1<<(n%BITS)) ^ MAXFIELD);
637: }
638:
639: test(map,n)
640: char *map;
641: int n;
642: {
643: return ((map[n/BITS] & (1<<(n%BITS))) != 0);
644: }
645:
646: /*
647: ** MAKE_LIST -- puts the delimitors to be used in the delim queue
648: **
649: ** Parameters:
650: ** desc - descriptor for the relation
651: ** group - group of delims to use
652: **
653: ** Returns:
654: ** 0 if ok
655: ** -1 if no delims could be found in the specified group
656: **
657: ** Comments:
658: ** given a group name, adds all delimitors in that
659: ** group to the head of the delim queue, which is
660: ** pointed to by Delimhead.
661: ** if the queue is empty, the predefined delimitors
662: ** 'w' and 'c' will be added to the list
663: */
664: make_list(desc,group)
665: DESC *desc;
666: char *group;
667: {
668: DELIM_TUP tuple;
669: TID lotid, hitid;
670: extern DELIMLIST *Delimhead;
671: DELIMLIST *d;
672: DMAP *map, *m;
673: char delim[12];
674: int start = 1;
675: extern char *malloc();
676: int i;
677: int notfound = 1;
678:
679: # ifdef xPTR3
680: tTfp(42,0,"Make_list: group = %s\n", group);
681: # endif
682: if (!strcmp (group,"system"))
683: {
684: predef_delims();
685: return(0);
686: }
687: if (find(desc,LRANGEKEY, &lotid, &hitid, group) < 0)
688: return(-1);
689: find(desc,HRANGEKEY, &lotid, &hitid, group);
690: while (!get(desc, &lotid, &hitid, &tuple, 1))
691: {
692: if (strcmp(tuple.group, group))
693: {
694: continue;
695: }
696: notfound = FALSE;
697: /* check if it is a new delimitor */
698: if (strcmp(tuple.delim, delim))
699: start = 1;
700:
701: /* start a new delimitor node */
702: if (start)
703: {
704: d = (DELIMLIST *) malloc( sizeof(DELIMLIST));
705: strcpy(delim, tuple.delim);
706: strcpy(d->group,tuple.group);
707: strcpy(d->delim,delim);
708: d->back = Delimhead;
709: Delimhead = d;
710:
711: map = (DMAP *) malloc(sizeof(DMAP));
712: map->order = tuple.order;
713: map->type = tuple.type;
714: for ( i = 0; i < BITMAPLEN; i++)
715: map->bits[i] = tuple.bitmap[i];
716: map->next = NULL;
717: d->maptr = map;
718: m = map;
719: start = 0;
720:
721: }
722: else /* add another bitmap to the delimitor node */
723: {
724: map = (DMAP *) malloc(sizeof(DMAP));
725: map->order = tuple.order;
726: map->type = tuple.type;
727: for ( i = 0; i < BITMAPLEN; i++)
728: map->bits[i] = tuple.bitmap[i];
729: map->next = NULL;
730: m->next = map;
731: m = m->next;
732:
733: }
734:
735: }
736: /*prlist(Delimhead); */
737: if (notfound)
738: return(-1);
739: return(0);
740: }
741:
742: /*
743: ** PREDEF_DELIMS - add the predefined delims to the queue
744: **
745: ** Called by:
746: ** make_list
747: **
748: ** Side Effects:
749: ** the delim queue pointed to by Delimhead
750: ** is initialized with the delims 'w' and 'c'.
751: **
752: */
753: predef_delims()
754: {
755: DELIMLIST *d;
756: DMAP *m, *m2;
757: int i;
758:
759: d = (DELIMLIST * ) malloc(sizeof(DELIMLIST));
760: strcpy(d->group, "system");
761: strcpy(d->delim, "c");
762: d->back = NULL;
763:
764: m = (DMAP *) malloc(sizeof (DMAP));
765: m->order = 1;
766: m->type = 0;
767: for (i = ' '; i <= '~'; i++)
768: set(m->bits, i);
769: m->next = NULL;
770: d->maptr = m;
771: Delimhead = d;
772:
773:
774: d = (DELIMLIST * ) malloc(sizeof(DELIMLIST));
775: strcpy(d->group, "system");
776: strcpy(d->delim, "w");
777: d->back = NULL;
778: m = (DMAP *) malloc(sizeof (DMAP));
779: m->order = 1;
780: m->type = 0;
781: for (i = 'A'; i <= 'Z'; i++)
782: set(m->bits, i);
783: for (i = 'a'; i <= 'z'; i++)
784: set(m->bits, i);
785: d->maptr = m;
786:
787: m2 = (DMAP *) malloc(sizeof(DMAP));
788: m2->order = 2;
789: m2->type = 1;
790: for (i = 'A'; i <= 'Z'; i++)
791: set(m2->bits, i);
792: for (i = 'a'; i <= 'z'; i++)
793: set(m2->bits, i);
794: m->next = m2;
795: m2->next = NULL;
796:
797: d->back = Delimhead;
798: Delimhead = d;
799: }
800:
801:
802:
803:
804:
805: /*
806: ** PRLIST -- print contents of delimiter queue
807: */
808: prlist(d)
809: struct delimlist *d;
810: {
811: struct delimlist *q;
812: DMAP *m;
813: int i;
814:
815: printf("DELIM QUEUE:\n");
816: q = d;
817: while (q != NULL)
818: {
819: printf("-------------------------------------------------------\n");
820: printf("NODE: group= %s, delim = %s \n", q->group, q->delim);
821: m = q->maptr;
822: while (m != NULL)
823: {
824: printf("maps:\n");
825: printf("order = %d, type = %d \n", m->order, m->type);
826: for (i = 0; i < ACHARS; i++)
827: printf("%d ", test(m->bits,i));
828: printf("\n");
829: m = m->next;
830: }
831: q = q->back;
832: printf("-------------------------------------------------------\n");
833: }
834:
835: return(0);
836:
837: }
838:
839: /*
840: ** SHRINK_LIST -- remove the delims in specified group from list
841: **
842: ** Parameters:
843: ** group - name of the group to remove
844: **
845: */
846: shrink_list(group)
847: char *group;
848: {
849: struct delimlist *p, *q;
850: extern struct delimlist *Delimhead;
851:
852: /* may not delete sytem delims */
853: if (!strcmp(group, "system"))
854: return(-1);
855:
856: p = Delimhead;
857:
858: while ((p != NULL) && (strcmp(p->group, group)))
859: {
860: q = p;
861: p = p->back;
862: }
863: if (p == NULL)
864: {
865: return(-1); /* error group not found */
866: }
867:
868: while(!strcmp(p->group, group))
869: {
870: if (p == Delimhead)
871: Delimhead = p->back;
872: else
873: q->back = p->back;
874:
875: if (p->back == NULL)
876: {
877: return(0);
878: }
879:
880: p = p-> back;
881: }
882:
883: /* prlist(Delimhead); */
884: return(0);
885: }
886:
887: /*
888: ** DESTROY_DELIM -- remove the group of delims from the relation 'rdelim'
889: **
890: ** Parameters:
891: ** group - the group of delims to remove
892: **
893: ** Called By:
894: ** grammar.y
895: **
896: ** Returns:
897: ** 0 if delims were successfully removed
898: ** -1 if delims were not found in relation
899: */
900: destroy_delim(desc, group)
901: DESC *desc;
902: char *group;
903: {
904: DELIM_TUP tuple;
905: TID lotid,hitid;
906: int notfound = 1;
907:
908: if (find(desc,LRANGEKEY, &lotid, &hitid, group) < 0)
909: return(-1);
910: find(desc,HRANGEKEY, &lotid, &hitid, group);
911:
912: while (!get(desc, &lotid, &hitid, &tuple, 1))
913: {
914: if (!strcmp(tuple.group, group))
915: {
916: notfound = 0;
917: delete(desc,&lotid);
918: }
919: }
920: if (notfound)
921: return(-1);
922: return(0);
923: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.