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: }