4.3BSD - /usr/src/usr.bin/lint/lpass2.c

   1: #ifndef lint
   2: static char sccsid[] = "@(#)lpass2.c	1.6	(Berkeley)	2/21/86";
   3: #endif lint
   4: 
   5: # include "macdefs.h"
   6: # include "manifest.h"
   7: # include "lmanifest.h"
   8: 
   9: # define USED 01
  10: # define VUSED 02
  11: # define EUSED 04
  12: # define RVAL 010
  13: # define VARARGS 0100
  14: 
  15: # define NSZ 4096
  16: # define TYSZ 3500
  17: # define FSZ 500
  18: # define NTY 50
  19: 
  20: typedef struct sty STYPE;
  21: struct sty { ATYPE t; STYPE *next; };
  22: 
  23: typedef struct sym {
  24: #ifndef FLEXNAMES
  25:     char name[LCHNM];
  26: #else
  27:     char *name;
  28: #endif
  29:     short nargs;
  30:     int decflag;
  31:     int fline;
  32:     STYPE symty;
  33:     int fno;
  34:     int use;
  35:     } STAB;
  36: 
  37: STAB stab[NSZ];
  38: STAB *find();
  39: 
  40: STYPE tary[TYSZ];
  41: STYPE *tget();
  42: 
  43: #ifndef FLEXNAMES
  44: char fnm[FSZ][LFNM];
  45: #else
  46: char *fnm[FSZ];
  47: #endif
  48: 
  49: #ifdef FLEXNAMES
  50: char *getstr();
  51: #endif
  52: 
  53: int tfree;  /* used to allocate types */
  54: int ffree;  /* used to save filenames */
  55: 
  56: struct ty atyp[NTY];
  57:     /* r is where all the input ends up */
  58: union rec r;
  59: 
  60: int hflag = 0;
  61: int pflag = 0;
  62: int xflag = 0;
  63: int uflag = 1;
  64: int ddddd = 0;
  65: int zflag = 0;
  66: int Pflag = 0;
  67: 
  68: int cfno;  /* current file number */
  69: 
  70: main( argc, argv ) char *argv[]; {
  71:     register char *p;
  72: 
  73:     /* first argument is intermediate file */
  74:     /* second argument is - options */
  75: 
  76:     for( ; argc>2 && argv[argc-1][0] == '-' ; --argc ){
  77:         for( p=argv[argc-1]; *p; ++p ){
  78:             switch( *p ){
  79: 
  80:             case 'h':
  81:                 hflag = 1;
  82:                 break;
  83: 
  84:             case 'p':
  85:                 pflag = 1;
  86:                 break;
  87: 
  88:             case 'x':
  89:                 xflag = 1;
  90:                 break;
  91: 
  92:             case 'X':
  93:                 ddddd = 1;
  94:                 break;
  95: 
  96:             case 'u':
  97:                 uflag = 0;
  98:                 break;
  99: 
 100:             case 'z':
 101:                 zflag = 1;
 102:                 break;
 103: 
 104:             case 'P':
 105:                 Pflag = 1;
 106:                 break;
 107: 
 108:                 }
 109:             }
 110:         }
 111: 
 112:     if( argc < 2 || !freopen( argv[1], "r", stdin ) ){
 113:         error( "cannot open intermediate file" );
 114:         exit( 1 );
 115:         }
 116:     if( Pflag ){
 117:         pfile();
 118:         return( 0 );
 119:         }
 120:     mloop( LDI|LIB|LST );
 121:     rewind( stdin );
 122:     mloop( LDC|LDX );
 123:     rewind( stdin );
 124:     mloop( LRV|LUV|LUE|LUM );
 125:     cleanup();
 126:     return(0);
 127:     }
 128: 
 129: mloop( m ){
 130:     /* do the main loop */
 131:     register STAB *q;
 132: 
 133:     while( lread(m) ){
 134:         q = find();
 135:         if( q->decflag ) chkcompat(q);
 136:         else setuse(q);
 137:         }
 138:     }
 139: 
 140: lread(m){ /* read a line into r.l */
 141: 
 142:     register n;
 143: 
 144:     for(;;) {
 145:         if( fread( (char *)&r, sizeof(r), 1, stdin ) <= 0 ) return(0);
 146:         if( r.l.decflag & LFN ){
 147:             /* new filename */
 148: #ifdef FLEXNAMES
 149:             r.f.fn = getstr();
 150: #endif
 151:             if( Pflag ) return( 1 );
 152:             setfno( r.f.fn );
 153:             continue;
 154:             }
 155: #ifdef FLEXNAMES
 156:         r.l.name = getstr();
 157: #endif
 158:         n = r.l.nargs;
 159:         if( n<0 ) n = -n;
 160:         if( n>=NTY ) error( "more than %d args?", n );
 161:         fread( (char *)atyp, sizeof(ATYPE), n, stdin );
 162:         if( ( r.l.decflag & m ) ) return( 1 );
 163:         }
 164:     }
 165: 
 166: setfno( s ) char *s; {
 167:     /* look up current file names */
 168:     /* first, strip backwards to the beginning or to the first / */
 169:     int i;
 170: 
 171:     /* now look up s */
 172:     for( i=0; i<ffree; ++i ){
 173: #ifndef FLEXNAMES
 174:         if( !strncmp( s, fnm[i], LFNM ) )
 175: #else
 176:         if (fnm[i] == s)
 177: #endif
 178:             {
 179:             cfno = i;
 180:             return;
 181:             }
 182:         }
 183:     /* make a new entry */
 184:     if( ffree >= FSZ ) error( "more than %d files", FSZ );
 185: #ifndef FLEXNAMES
 186:     strncpy( fnm[ffree], s, LFNM );
 187: #else
 188:     fnm[ffree] = s;
 189: #endif
 190:     cfno = ffree++;
 191:     }
 192: 
 193: /* VARARGS */
 194: error( s, a ) char *s; {
 195: 
 196: #ifndef FLEXNAMES
 197:     fprintf( stderr, "pass 2 error:(file %.*s) ", LFNM, fnm[cfno] );
 198: #else
 199:     fprintf( stderr, "pass 2 error:(file %s) ", fnm[cfno] );
 200: #endif
 201:     fprintf( stderr, s, a );
 202:     fprintf( stderr, "\n" );
 203:     exit(1);
 204:     }
 205: 
 206: STAB *
 207: find(){
 208:     register h=0;
 209: #ifndef FLEXNAMES
 210:     h = hashstr(r.l.name, LCHNM) % NSZ;
 211: #else
 212:     h = (int)r.l.name % NSZ;
 213: #endif
 214:     {   register STAB *p, *q;
 215:         for( p=q= &stab[h]; q->decflag; ){
 216: #ifndef FLEXNAMES
 217:             if( !strncmp( r.l.name, q->name, LCHNM))
 218: #else
 219:             if (r.l.name == q->name)
 220: #endif
 221:                 if( ((q->decflag|r.l.decflag)&LST)==0 || q->fno==cfno )
 222:                     return(q);
 223:             if( ++q >= &stab[NSZ] ) q = stab;
 224:             if( q == p ) error( "too many names defined" );
 225:             }
 226: #ifndef FLEXNAMES
 227:         strncpy( q->name, r.l.name, LCHNM );
 228: #else
 229:         q->name = r.l.name;
 230: #endif
 231:         return( q );
 232:         }
 233:     }
 234: 
 235: STYPE *
 236: tget(){
 237:     if( tfree >= TYSZ ){
 238:         error( "too many types needed" );
 239:         }
 240:     return( &tary[tfree++] );
 241:     }
 242: 
 243: chkcompat(q) STAB *q; {
 244:     /* are the types, etc. in r.l and q compatible */
 245:     register int i;
 246:     STYPE *qq;
 247: 
 248:     setuse(q);
 249: 
 250:     /* argument check */
 251: 
 252:     if( q->decflag & (LDI|LIB|LUV|LUE|LST) ){
 253:         if( r.l.decflag & (LUV|LIB|LUE) ){
 254:             if( q->nargs != r.l.nargs ){
 255:                 if( !(q->use&VARARGS) ){
 256: #ifndef FLEXNAMES
 257:                     printf( "%.8s: variable # of args.", q->name );
 258: #else
 259:                     printf( "%s: variable # of args.", q->name );
 260: #endif
 261:                     viceversa(q);
 262:                     }
 263:                 if( r.l.nargs > q->nargs ) r.l.nargs = q->nargs;
 264:                 if( !(q->decflag & (LDI|LIB|LST) ) ) {
 265:                     q->nargs = r.l.nargs;
 266:                     q->use |= VARARGS;
 267:                     }
 268:                 }
 269:             for( i=0,qq=q->symty.next; i<r.l.nargs; ++i,qq=qq->next){
 270:                 if( chktype( &qq->t, &atyp[i] ) ){
 271: #ifndef FLEXNAMES
 272:                     printf( "%.8s, arg. %d used inconsistently",
 273: #else
 274:                     printf( "%s, arg. %d used inconsistently",
 275: #endif
 276:                         q->name, i+1 );
 277:                     viceversa(q);
 278:                     }
 279:                 }
 280:             }
 281:         }
 282: 
 283:     if( (q->decflag&(LDI|LIB|LUV|LST)) && r.l.decflag==LUV ){
 284:         if( chktype( &r.l.type, &q->symty.t ) ){
 285: #ifndef FLEXNAMES
 286:             printf( "%.8s value used inconsistently", q->name );
 287: #else
 288:             printf( "%s value used inconsistently", q->name );
 289: #endif
 290:             viceversa(q);
 291:             }
 292:         }
 293: 
 294:     /* check for multiple declaration */
 295: 
 296:     if( (q->decflag&(LDI|LST)) && (r.l.decflag&(LDI|LIB|LST)) ){
 297: #ifndef FLEXNAMES
 298:         printf( "%.8s multiply declared", q->name );
 299: #else
 300:         printf( "%s multiply declared", q->name );
 301: #endif
 302:         viceversa(q);
 303:         }
 304: 
 305:     /* do a bit of checking of definitions and uses... */
 306: 
 307:     if( (q->decflag & (LDI|LIB|LDX|LDC|LUM|LST)) && (r.l.decflag & (LDX|LDC|LUM)) && q->symty.t.aty != r.l.type.aty ){
 308: #ifndef FLEXNAMES
 309:         printf( "%.8s value declared inconsistently", q->name );
 310: #else
 311:         printf( "%s value declared inconsistently", q->name );
 312: #endif
 313:         viceversa(q);
 314:         }
 315: 
 316:     /* better not call functions which are declared to be structure or union returning */
 317: 
 318:     if( (q->decflag & (LDI|LIB|LDX|LDC|LST)) && (r.l.decflag & LUE) && q->symty.t.aty != r.l.type.aty ){
 319:         /* only matters if the function returns union or structure */
 320:         TWORD ty;
 321:         ty = q->symty.t.aty;
 322:         if( ISFTN(ty) && ((ty = DECREF(ty))==STRTY || ty==UNIONTY ) ){
 323: #ifndef FLEXNAMES
 324:             printf( "%.8s function value type must be declared before use", q->name );
 325: #else
 326:             printf( "%s function value type must be declared before use", q->name );
 327: #endif
 328:             viceversa(q);
 329:             }
 330:         }
 331: 
 332:     if( pflag && q->decflag==LDX && r.l.decflag == LUM && !ISFTN(q->symty.t.aty) ){
 333:         /* make the external declaration go away */
 334:         /* in effect, it was used without being defined */
 335:         }
 336:     }
 337: 
 338: viceversa(q) STAB *q; {
 339:     /* print out file comparison */
 340: #ifndef FLEXNAMES
 341:     printf( "	%.*s(%d)  ::  %.*s(%d)\n",
 342:         LFNM, fnm[q->fno], q->fline,
 343:         LFNM, fnm[cfno], r.l.fline );
 344: #else
 345:     printf( "	%s(%d)  ::  %s(%d)\n",
 346:         fnm[q->fno], q->fline,
 347:         fnm[cfno], r.l.fline );
 348: #endif
 349:     }
 350: 
 351:     /* messages for defintion/use */
 352: char *
 353: mess[2][2] ={
 354:     "",
 355: #ifndef FLEXNAMES
 356:     "%.8s used( %.*s(%d) ), but not defined\n",
 357:     "%.8s defined( %.*s(%d) ), but never used\n",
 358:     "%.8s declared( %.*s(%d) ), but never used or defined\n"
 359: #else
 360:     "%s used( %s(%d) ), but not defined\n",
 361:     "%s defined( %s(%d) ), but never used\n",
 362:     "%s declared( %s(%d) ), but never used or defined\n"
 363: #endif
 364:     };
 365: 
 366: lastone(q) STAB *q; {
 367: 
 368:     register nu, nd, uses;
 369: 
 370:     if( ddddd ) pst(q);
 371: 
 372:     nu = nd = 0;
 373:     uses = q->use;
 374: 
 375:     if( !(uses&USED) && q->decflag != LIB ) {
 376: #ifndef FLEXNAMES
 377:         if( strncmp(q->name,"main",7) )
 378: #else
 379:         if (strcmp(q->name, "main"))
 380: #endif
 381:             nu = 1;
 382:         }
 383: 
 384:     if( !ISFTN(q->symty.t.aty) ){
 385:         switch( q->decflag ){
 386: 
 387:         case LIB:
 388:             nu = nd = 0;  /* don't complain about uses on libraries */
 389:             break;
 390:         case LDX:
 391:             if( !xflag ) break;
 392:         case LUV:
 393:         case LUE:
 394: /* 01/04/80 */  case LUV | LUE:
 395:         case LUM:
 396:             nd = 1;
 397:             }
 398:         }
 399:     if( uflag && ( nu || nd ) )
 400: #ifndef FLEXNAMES
 401:         printf( mess[nu][nd], q->name, LFNM, fnm[q->fno], q->fline );
 402: #else
 403:         printf( mess[nu][nd], q->name, fnm[q->fno], q->fline );
 404: #endif
 405: 
 406:     if( (uses&(RVAL+EUSED)) == (RVAL+EUSED) ){
 407:         /* if functions is static, then print the file name too */
 408:         if( q->decflag & LST )
 409: #ifndef FLEXNAMES
 410:             printf( "%.*s(%d):", LFNM, fnm[q->fno], q->fline );
 411: #else
 412:             printf( "%s(%d):", fnm[q->fno], q->fline );
 413: #endif
 414: #ifndef FLEXNAMES
 415:         printf( "%.*s returns value which is %s ignored\n",
 416:             LCHNM, q->name, uses&VUSED ? "sometimes" : "always" );
 417: #else
 418:         printf( "%s returns value which is %s ignored\n",
 419:             q->name, uses&VUSED ? "sometimes" : "always" );
 420: #endif
 421:         }
 422: 
 423:     if( (uses&(RVAL+VUSED)) == (VUSED) && (q->decflag&(LDI|LIB|LST)) ){
 424:         if( q->decflag & LST )
 425: #ifndef FLEXNAMES
 426:             printf( "%.*s(%d):", LFNM, fnm[q->fno], q->fline );
 427: #else
 428:             printf( "%s(%d):", fnm[q->fno], q->fline );
 429: #endif
 430: #ifndef FLEXNAMES
 431:         printf( "%.*s value is used, but none returned\n",
 432:             LCHNM, q->name);
 433: #else
 434:         printf( "%s value is used, but none returned\n", q->name);
 435: #endif
 436:         }
 437:     }
 438: 
 439: cleanup(){ /* call lastone and die gracefully */
 440:     STAB *q;
 441:     for( q=stab; q< &stab[NSZ]; ++q ){
 442:         if( q->decflag ) lastone(q);
 443:         }
 444:     exit(0);
 445:     }
 446: 
 447: setuse(q) STAB *q; { /* check new type to ensure that it is used */
 448: 
 449:     if( !q->decflag ){ /* new one */
 450:         q->decflag = r.l.decflag;
 451:         q->symty.t = r.l.type;
 452:         if( r.l.nargs < 0 ){
 453:             q->nargs = -r.l.nargs;
 454:             q->use = VARARGS;
 455:             }
 456:         else {
 457:             q->nargs = r.l.nargs;
 458:             q->use = 0;
 459:             }
 460:         q->fline = r.l.fline;
 461:         q->fno = cfno;
 462:         if( q->nargs ){
 463:             int i;
 464:             STYPE *qq;
 465:             for( i=0,qq= &q->symty; i<q->nargs; ++i,qq=qq->next ){
 466:                 qq->next = tget();
 467:                 qq->next->t = atyp[i];
 468:                 }
 469:             }
 470:         }
 471: 
 472:     switch( r.l.decflag ){
 473: 
 474:     case LRV:
 475:         q->use |= RVAL;
 476:         return;
 477:     case LUV:
 478:         q->use |= VUSED+USED;
 479:         return;
 480:     case LUE:
 481:         q->use |= EUSED+USED;
 482:         return;
 483: /* 01/04/80 */  case LUV | LUE:
 484:     case LUM:
 485:         q->use |= USED;
 486:         return;
 487: 
 488:         }
 489:     }
 490: 
 491: chktype( pt1, pt2 ) register ATYPE *pt1, *pt2; {
 492:     TWORD t;
 493: 
 494:     /* check the two type words to see if they are compatible */
 495:     /* for the moment, enums are turned into ints, and should be checked as such */
 496:     if( pt1->aty == ENUMTY ) pt1->aty =  INT;
 497:     if( pt2->aty == ENUMTY ) pt2->aty = INT;
 498: 
 499:     if( (t=BTYPE(pt1->aty)==STRTY) || t==UNIONTY ){
 500:         if( pt1->aty != pt2->aty || pt1->extra1 != pt2->extra1 )
 501:             return 1;
 502:         /* if -z then don't worry about undefined structures,
 503: 		   as long as the names match */
 504:         if( zflag && (pt1->extra == 0 || pt2->extra == 0) ) return 0;
 505:         return pt1->extra != pt2->extra;
 506:         }
 507: 
 508:     if( pt2->extra ){ /* constant passed in */
 509:         if( pt1->aty == UNSIGNED && pt2->aty == INT ) return( 0 );
 510:         else if( pt1->aty == ULONG && pt2->aty == LONG ) return( 0 );
 511:         }
 512:     else if( pt1->extra ){ /* for symmetry */
 513:         if( pt2->aty == UNSIGNED && pt1->aty == INT ) return( 0 );
 514:         else if( pt2->aty == ULONG && pt1->aty == LONG ) return( 0 );
 515:         }
 516: 
 517:     return( pt1->aty != pt2->aty );
 518:     }
 519: 
 520: struct tb { int m; char * nm };
 521: 
 522: struct tb dfs[] = {
 523:     LDI, "LDI",
 524:     LIB, "LIB",
 525:     LDC, "LDC",
 526:     LDX, "LDX",
 527:     LRV, "LRV",
 528:     LUV, "LUV",
 529:     LUE, "LUE",
 530:     LUM, "LUM",
 531:     LST, "LST",
 532:     LFN, "LFN",
 533:     0, "" };
 534: 
 535: struct tb us[] = {
 536:     USED, "USED",
 537:     VUSED, "VUSED",
 538:     EUSED, "EUSED",
 539:     RVAL, "RVAL",
 540:     VARARGS, "VARARGS",
 541:     0, "" };
 542: 
 543: ptb( v, tp ) struct tb *tp; {
 544:     /* print a value from the table */
 545:     int flag;
 546:     flag = 0;
 547:     for( ; tp->m; ++tp ){
 548:         if( v&tp->m ){
 549:             if( flag++ ) putchar( '|' );
 550:             printf( "%s", tp->nm );
 551:             }
 552:         }
 553:     }
 554: 
 555: pst( q ) STAB *q; {
 556:     /* give a debugging output for q */
 557: 
 558: #ifndef FLEXNAMES
 559:     printf( "%.8s (", q->name );
 560: #else
 561:     printf( "%s (", q->name );
 562: #endif
 563:     ptb( q->decflag, dfs );
 564:     printf( "), use= " );
 565:     ptb( q->use, us );
 566:     printf( ", line %d, nargs=%d\n", q->fline, q->nargs );
 567:     }
 568: 
 569: pfile() {
 570:     /* print the input file in readable form */
 571:     while( lread( LDI|LIB|LDC|LDX|LRV|LUV|LUE|LUM|LST|LFN ) )
 572:         prc();
 573:     }
 574: 
 575: prc() {
 576:     /* print out 'r' for debugging */
 577:     register i, j, k;
 578: 
 579:     printf( "decflag\t" );
 580:     ptb( r.l.decflag, dfs );
 581:     putchar( '\n' );
 582:     if( r.l.decflag & LFN ){
 583: #ifdef FLEXNAMES
 584:         printf( "fn\t\t%s\n", r.f.fn );
 585: #else
 586:         printf( "fn\t%\t.*s\n", LFNM, r.f.fn );
 587: #endif
 588:         }
 589:     else {
 590: #ifdef FLEXNAMES
 591:         printf( "name\t%s\n", r.l.name );
 592: #else
 593:         printf( "name\t%.*s\n", LCHNM, r.l.name );
 594: #endif
 595:         printf( "nargs\t%d\n", r.l.nargs );
 596:         printf( "fline\t%d\n", r.l.fline );
 597:         printf( "type.aty\t0%o (", r.l.type.aty );
 598:         pty( r.l.type.aty, r.l.name );
 599:         printf( ")\ntype.extra\t%d\n", r.l.type.extra );
 600:         j = r.l.type.extra1;
 601:         printf( "type.extra1\t0x%x (%d,%d)\n",
 602:             j, j & X_NONAME ? 1 : 0, j & ~X_NONAME );
 603:         k = r.l.nargs;
 604:         if( k < 0 ) k = -k;
 605:         for( i = 0; i < k; i++ ){
 606:             printf( "atyp[%d].aty\t0%o (", i, atyp[i].aty );
 607:             pty( atyp[i].aty, "" );
 608:             printf( ")\natyp[%d].extra\t%d\n", i, atyp[i].extra);
 609:             j = atyp[i].extra1;
 610:             printf( "atyp[%d].extra1\t0x%x (%d,%d)\n",
 611:                 i, j, j & X_NONAME ? 1 : 0, j & ~X_NONAME );
 612:             }
 613:         }
 614:         putchar( '\n' );
 615:     }
 616: 
 617: pty( t, name )  TWORD t; {
 618:     static char * tnames[] = {
 619:         "void", "farg", "char", "short",
 620:         "int", "long", "float", "double",
 621:         "struct xxx", "union %s", "enum", "moety",
 622:         "unsigned char", "unsigned short", "unsigned", "unsigned long",
 623:         "?", "?"
 624:         };
 625: 
 626:     printf( "%s ", tnames[BTYPE(t)] );
 627:     pty1( t, name, (8 * sizeof (int) - BTSHIFT) / TSHIFT );
 628:     }
 629: 
 630: pty1( t, name, level ) TWORD t; {
 631:     register TWORD u;
 632: 
 633:     if( level < 0 ){
 634:         printf( "%s", name );
 635:         return;
 636:         }
 637:     u = t >> level * TSHIFT;
 638:     if( ISPTR(u) ){
 639:         printf( "*" );
 640:         pty1( t, name, level-1 );
 641:         }
 642:     else if( ISFTN(u) ){
 643:         if( level > 0 && ISPTR(u << TSHIFT) ){
 644:             printf( "(" );
 645:             pty1( t, name, level-1 );
 646:             printf( ")()" );
 647:             }
 648:         else {
 649:             pty1( t, name, level-1 );
 650:             printf( "()" );
 651:             }
 652:         }
 653:     else if( ISARY(u) ){
 654:         if( level > 0 && ISPTR(u << TSHIFT) ){
 655:             printf( "(" );
 656:             pty1( t, name, level-1 );
 657:             printf( ")[]" );
 658:             }
 659:         else {
 660:             pty1( t, name, level-1 );
 661:             printf( "[]" );
 662:             }
 663:         }
 664:     else {
 665:         pty1( t, name, level-1 );
 666:         }
 667:     }
 668: 
 669: #ifdef FLEXNAMES
 670: char *
 671: getstr()
 672: {
 673:     char buf[BUFSIZ];
 674:     register char *cp = buf;
 675:     register int c;
 676: 
 677:     if (feof(stdin) || ferror(stdin))
 678:         return("");
 679:     while ((c = getchar()) > 0)
 680:         *cp++ = c;
 681:     if (c < 0) {
 682:         error("intermediate file format error (getstr)");
 683:         exit(1);
 684:     }
 685:     *cp++ = 0;
 686:     return (hash(buf));
 687: }
 688: 
 689: #define NSAVETAB    4096
 690: char    *savetab;
 691: int saveleft;
 692: 
 693: char *
 694: savestr(cp)
 695:     register char *cp;
 696: {
 697:     register int len;
 698: 
 699:     len = strlen(cp) + 1;
 700:     if (len > saveleft) {
 701:         saveleft = NSAVETAB;
 702:         if (len > saveleft)
 703:             saveleft = len;
 704:         savetab = (char *)malloc(saveleft);
 705:         if (savetab == 0) {
 706:             error("ran out of memory (savestr)");
 707:             exit(1);
 708:         }
 709:     }
 710:     strncpy(savetab, cp, len);
 711:     cp = savetab;
 712:     savetab += len;
 713:     saveleft -= len;
 714:     return (cp);
 715: }
 716: 
 717: /*
 718:  * The definition for the segmented hash tables.
 719:  */
 720: #define MAXHASH 20
 721: #define HASHINC 1013
 722: struct ht {
 723:     char    **ht_low;
 724:     char    **ht_high;
 725:     int ht_used;
 726: } htab[MAXHASH];
 727: 
 728: char *
 729: hash(s)
 730:     char *s;
 731: {
 732:     register char **h;
 733:     register i;
 734:     register char *cp;
 735:     struct ht *htp;
 736:     int sh;
 737: 
 738:     sh = hashstr(s) % HASHINC;
 739:     cp = s;
 740:     /*
 741: 	 * There are as many as MAXHASH active
 742: 	 * hash tables at any given point in time.
 743: 	 * The search starts with the first table
 744: 	 * and continues through the active tables
 745: 	 * as necessary.
 746: 	 */
 747:     for (htp = htab; htp < &htab[MAXHASH]; htp++) {
 748:         if (htp->ht_low == 0) {
 749:             register char **hp =
 750:                 (char **) calloc(sizeof (char **), HASHINC);
 751:             if (hp == 0) {
 752:                 error("ran out of memory (hash)");
 753:                 exit(1);
 754:             }
 755:             htp->ht_low = hp;
 756:             htp->ht_high = htp->ht_low + HASHINC;
 757:         }
 758:         h = htp->ht_low + sh;
 759:         /*
 760: 		 * quadratic rehash increment
 761: 		 * starts at 1 and incremented
 762: 		 * by two each rehash.
 763: 		 */
 764:         i = 1;
 765:         do {
 766:             if (*h == 0) {
 767:                 if (htp->ht_used > (HASHINC * 3)/4)
 768:                     break;
 769:                 htp->ht_used++;
 770:                 *h = savestr(cp);
 771:                 return (*h);
 772:             }
 773:             if (**h == *cp && strcmp(*h, cp) == 0)
 774:                 return (*h);
 775:             h += i;
 776:             i += 2;
 777:             if (h >= htp->ht_high)
 778:                 h -= HASHINC;
 779:         } while (i < HASHINC);
 780:     }
 781:     error("ran out of hash tables");
 782:     exit(1);
 783: }
 784: char    *tstrbuf[1];
 785: #endif

Defined functions

Defined variables

Defined struct's

Defined typedef's

Defined macros