home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Professional / OS2PRO194.ISO / os2 / prgramer / awk / awk1.c < prev    next >
C/C++ Source or Header  |  1988-07-17  |  18KB  |  786 lines
  1. /*
  2.  * awk1 -- Expression tree constructors and main program for gawk.
  3.  *
  4.  * Copyright (C) 1986 Free Software Foundation
  5.  *   Written by Paul Rubin, August 1986
  6.  *
  7.  *     Modifications by Andrew D. Estes, July 1988
  8.  */
  9.  
  10. /*
  11. GAWK is distributed in the hope that it will be useful, but WITHOUT ANY
  12. WARRANTY.  No author or distributor accepts responsibility to anyone
  13. for the consequences of using it or for whether it serves any
  14. particular purpose or works at all, unless he says so in writing.
  15. Refer to the GAWK General Public License for full details.
  16.  
  17. Everyone is granted permission to copy, modify and redistribute GAWK,
  18. but only under the conditions described in the GAWK General Public
  19. License.  A copy of this license is supposed to have been given to you
  20. along with GAWK so you can know your rights and responsibilities.  It
  21. should be in a file named COPYING.  Among other things, the copyright
  22. notice and this notice must be preserved on all copies.
  23.  
  24. In other words, go ahead and share GAWK, but don't try to stop
  25. anyone else from sharing it farther.  Help stamp out software hoarding!
  26. */
  27.  
  28. #include <stdio.h>
  29. #include <string.h>
  30. #include "regex.h"
  31. #include "awk.h"
  32.  
  33. extern char *index();    /* Let's be honest here */
  34.  
  35. /* Temporary nodes are stored here.  ob_dummy is a dummy object used to
  36.    keep the obstack library from free()ing up the entire stack.  */
  37. struct obstack temp_strings;
  38. char *ob_dummy;
  39.  
  40. /* The parse tree and field nodes are stored here.  Parse_end is a dummy
  41.    item used to free up unneeded fields without freeing the program being run
  42.  */
  43. struct obstack other_stack;
  44. char *parse_end;
  45.  
  46. /* The global null string */
  47. NODE *Nnull_string;
  48.  
  49. /* The special variable that contains the name of the current input file */
  50. extern NODE *FILENAME_node;
  51.  
  52. /* The name the program was invoked under, for error messages */
  53. char *myname;
  54.  
  55. /* A block of gAWK code to be run before running the program */
  56. NODE    *begin_block = 0;
  57.  
  58. /* A block of gAWK code to be run after the last input file */
  59. NODE    *end_block = 0;
  60.  
  61. FILE *input_file;    /* Where to read from */
  62.  
  63. #ifndef FAST
  64. /* non-zero means in debugging is enabled.  Probably not very useful */
  65. int debugging;
  66. #endif
  67.  
  68. main(argc, argv)
  69.      int argc;
  70.      char **argv;
  71. {
  72.   register int i;
  73.   register NODE *tmp;
  74.   int max_argc;
  75.   char    **do_vars;
  76. #ifndef FAST
  77.     /* Print out the parse tree.   For debugging */
  78.   register int dotree = 0;
  79.   extern int yydebug;
  80. #endif
  81.   extern char *lexptr;
  82.   extern char *lexptr_begin;
  83.   extern int patterns, actions;    /* ADE */
  84.   extern char *get_argv();           /* ADE */
  85.   FILE *fp,*fopen();
  86.  
  87.   do_vars = argv;            /* ADE */
  88.   max_argc = argc;            /* ADE */
  89.   --argc;
  90.   myname= *argv++;
  91.   if(!argc)
  92.     usage();
  93.  
  94.     /* Tell the regex routines how they should work. . . */
  95.   re_set_syntax(RE_NO_BK_PARENS|RE_NO_BK_VBAR);
  96.  
  97.     /* Set up the stack for temporary strings */
  98.   obstack_init (&temp_strings);
  99.   ob_dummy=obstack_alloc(&temp_strings,0);
  100.  
  101.     /* Set up the other stack for other things */
  102.   obstack_init(&other_stack);
  103.     /* initialize the null string */
  104.   Nnull_string = make_string("",0);
  105.   /* This was to keep Nnull_string from ever being free()d  It didn't work */
  106.   /* Nnull_string->stref=32000; */
  107.       /* Set up the special variables */
  108.     /* Note that this must be done BEFORE arg parsing else -R and -F
  109.        break horribly */
  110.   init_vars();
  111.  
  112.  
  113.   for(;*argv && **argv=='-';argc--,argv++) {
  114.     switch(argv[0][1]) {
  115. #ifndef FAST
  116.     case 'd':
  117.       debugging++;
  118.       dotree++;
  119.       break;
  120.  
  121.     case 'D':
  122.       debugging++;
  123.       yydebug=2;
  124.       break;
  125. #endif
  126.       /* This feature isn't in un*x awk, but might be useful */
  127.     case 'R':
  128.       set_rs(&argv[0][2]);
  129.       break;
  130.  
  131.     case 'F':
  132.       set_fs(&argv[0][2]);
  133.       break;
  134.  
  135.  
  136.             /* It would be better to read the input file in as we parse
  137.            it.  Its done this way for hysterical reasons.  Feel
  138.            free to fix it. */
  139.  
  140.         /* I don't know if this is useful or not but a -f followed by a
  141.         ** '-' will allow the awk program to be read from stdin.  This
  142.         ** gets around the DOS/OS|2 line length limitation -ADE-
  143.         */
  144.  
  145.     case 'f':
  146.       if(lexptr)
  147.         panic("Can only use one -f option");
  148.       if (!strcmp(argv[1], "-"))
  149.         fp = stdin;
  150.       else fp=fopen(argv[1],"r");
  151.       if (fp == NULL)
  152.         er_panic(argv[1]);
  153.       else {
  154.         char *curptr;
  155.         int siz,nread;
  156.  
  157.         curptr=lexptr=malloc(2000);
  158.         if(curptr==NULL)
  159.             panic("Memory exhausted");    /* jfw: instead of abort() */
  160.         siz=2000;
  161.         i=siz-1;
  162.         while((nread=fread(curptr,sizeof(char),i,fp)) > 0) {
  163.           curptr+=nread;
  164.           i-=nread;
  165.           if(i==0) {
  166.             lexptr=realloc(lexptr,siz*2);
  167.             if(lexptr==NULL)
  168.                 panic("Memory exhausted");    /* jfw: instead of abort() */
  169.             curptr=lexptr+siz-1;
  170.             i=siz;
  171.             siz*=2;
  172.           }
  173.         }
  174.       *curptr='\0';
  175.       if (fp != stdin)
  176.         fclose(fp);
  177.       }
  178.       argc--;
  179.       argv++;
  180.       break;
  181.  
  182.     case '\0':        /* A file */
  183.       break;
  184.  
  185.     default:
  186.       panic("Unknown option %s",argv[0]);
  187.     }
  188.   }
  189. #ifndef FAST
  190.   if (debugging) setbuf(stdout, 0);    /* jfw: make debugging easier */
  191. #endif /* FAST */
  192.   /* No -f option, use next arg */
  193.   if(!lexptr) {
  194.     if(!argc) usage();
  195.     lexptr= *argv++;
  196.     --argc;
  197.   }
  198. /* This must be done after finding program ADE */
  199. init_args(max_argc-argc, max_argc, do_vars);
  200.  
  201.   /* Read in the program */
  202.   lexptr_begin=lexptr;
  203.   (void)yyparse ();
  204.  
  205. /* Free up the space used for reading in the program -ADE- */
  206.  
  207.   free(lexptr_begin);
  208.  
  209.   /* Anything allocated on the other_stack after here will be freed
  210.      when the next input line is read.
  211.      */
  212.   parse_end=obstack_alloc(&other_stack,0);
  213.  
  214. #ifndef FAST
  215.   if(dotree)
  216.     print_parse_tree(expression_value);
  217. #endif
  218.   /* Set up the field variables */
  219.   init_fields();
  220.  
  221.   /* Look for BEGIN and END blocks.  Only one of each allowed */
  222.   for(tmp=expression_value;tmp;tmp=tmp->rnode) {
  223.     if(!tmp->lnode || !tmp->lnode->lnode)
  224.       continue;
  225.     if(tmp->lnode->lnode->type==Node_K_BEGIN)
  226.       begin_block=tmp->lnode->rnode;
  227.     else if(tmp->lnode->lnode->type==Node_K_END)
  228.       end_block=tmp->lnode->rnode;
  229.   }
  230.   if(begin_block && interpret(begin_block) == 0) exit(0);    /* jfw */
  231.  
  232.   do_vars=argv;
  233.   /* We want to get the command line args from the builtin variables
  234.   ** ARGC and ARGV[].  -ade-
  235.   */
  236.   while(get_argc()>0 && index(get_argv(),'=')) {
  237.     inc_argv();
  238.     ++argv;
  239.     get_argc_dec();
  240.   }
  241.   if(do_vars==argv) do_vars=0;
  242.   if(argc==0) {
  243.     static char *dumb[2]= { "-", 0};
  244.  
  245.     set_argc(1);        /* ade */
  246.     set_argv("-");        /* ade */
  247.   }
  248.     /* no need to open files if there is nothing to do -ADE- */
  249.   while(get_argc_dec() && (patterns>0 || actions>0)) {
  250.     if(!strcmp(get_argv(),"-"))
  251.       {
  252.       input_file=stdin;
  253.       FILENAME_node->var_value=Nnull_string;
  254.       ADD_ONE_REFERENCE(Nnull_string);
  255.       }
  256.     else
  257.       {
  258.       extern NODE *deref;
  259.  
  260.       input_file=fopen(get_argv(),"r");     /* ade */
  261.       /* This should print the error message from errno */
  262.       if(!input_file)
  263.         er_panic(get_argv());            /* ade */
  264.       /* This is a kludge.  */
  265.       deref=FILENAME_node->var_value;
  266.       do_deref();
  267.       FILENAME_node->var_value=make_string(get_argv(),strlen(get_argv()));
  268.       set_fnr(0);
  269.       }
  270.     /* This is where it spends all its time.  The infamous MAIN LOOP */
  271.     if(inrec(0, input_file)==0)
  272.         {
  273.         if(do_vars)
  274.             {
  275.             while(do_vars!=argv && *do_vars)
  276.                 {
  277.                 char *cp;
  278.  
  279.                 cp=index(*do_vars,'=');
  280.                 *cp++='\0';
  281.                 variable(*do_vars)->var_value=make_string(cp,strlen(cp));
  282.                 do_vars++;
  283.                 }
  284.             do_vars=0;
  285.             }
  286.         do
  287.               obstack_free(&temp_strings, ob_dummy);
  288.         while (interpret(expression_value) && inrec(0, input_file) == 0);
  289.         }
  290.     if(input_file!=stdin) fclose(input_file);
  291.     inc_argv();     /* ade */
  292.   }
  293.   if(end_block) (void)interpret(end_block);
  294.   exit(0);
  295. }
  296.  
  297. /* These exit values are arbitrary */
  298. /*VARARGS1*/
  299. panic(str,arg)
  300. char *str;
  301. {
  302.     fprintf(stderr,"%s: ",myname);
  303.     fprintf(stderr,str,arg);
  304.     fprintf(stderr,"\n");
  305.     exit(12);
  306. }
  307.  
  308. er_panic(str)
  309. char *str;
  310. {
  311.     fprintf(stderr,"%s: ",myname);
  312.     perror(str);
  313.     exit(15);
  314. }
  315.  
  316. usage()
  317. {
  318.     fprintf(stderr,"%s: usage: %s {-f progfile | program } [-F{c} -R{c}] file . . .\n",myname,myname);
  319.     exit(11);
  320. }
  321.  
  322.  
  323. /* This allocates a new node of type ty.  Note that this node will not go
  324.    away unless freed, so don't use it for tmp storage */
  325. NODE *
  326. newnode(ty)
  327. NODETYPE ty;
  328. {
  329.     register NODE *r;
  330.  
  331.     r=(NODE *)malloc(sizeof(NODE));
  332.     if(r==NULL)
  333.         panic("Memory exhausted");    /* -ade-: instead of abort() */
  334.     r->type=ty;
  335.     return r;
  336. }
  337.  
  338.  
  339. /* Duplicate a node.  (For global strings, "duplicate" means crank up
  340.    the reference count.)  This creates global nodes. . .*/
  341. NODE *
  342. dupnode(n)
  343. NODE *n;
  344. {
  345.     register NODE *r;
  346.  
  347.     if(n->type==Node_string) {
  348.         n->stref++;
  349.         return n;
  350.     } else if(n->type==Node_temp_string) {
  351.         r=newnode(Node_string);
  352.         r->stlen=n->stlen;
  353.         r->stref=1;
  354.         r->stptr=malloc(n->stlen+1);
  355.         if(r->stptr==NULL)
  356.             panic("Memory exhausted");    /* -ade-: instead of abort() */
  357.         bcopy (n->stptr, r->stptr, n->stlen);
  358.         r->stptr[r->stlen]='\0';            /* JF for hackval */
  359.         return r;
  360.     } else {
  361.         r=newnode(Node_illegal);
  362.         *r= *n;
  363.         return r;
  364.     }
  365. }
  366.  
  367. /* This allocates a node with defined lnode and rnode. */
  368. /* This should only be used by yyparse+co while
  369.    reading in the program */
  370. NODE *
  371. node (left, op, right)
  372.      NODE *left, *right;
  373.      NODETYPE op;
  374. {
  375.   register NODE *r;
  376.  
  377.   r = (NODE *)obstack_alloc(&other_stack,sizeof(NODE));
  378.   r->type=op;
  379.   r->lnode = left;
  380.   r->rnode = right;
  381.   return r;
  382. }
  383.  
  384. /* This allocates a node with defined subnode and proc */
  385. /* Otherwise like node() */
  386. NODE *
  387. snode(subn, op, procp)
  388. NODETYPE op;
  389. NODE *(*procp)();
  390. NODE *subn;
  391. {
  392.     register NODE *r;
  393.  
  394.     r=(NODE *)obstack_alloc(&other_stack,sizeof(NODE));
  395.     r->type=op;
  396.     r->subnode=subn;
  397.     r->proc=procp;
  398.     return r;
  399. }
  400.  
  401. /* (jfw) This allocates a Node_line_range node
  402.  * with defined condpair and zeroes the trigger word
  403.  * to avoid the temptation of assuming that calling
  404.  * 'node( foo, Node_line_range, 0)' will properly initialize 'triggered'.
  405.  */
  406. /* Otherwise like node() */
  407. NODE *
  408. mkrangenode(cpair)
  409. NODE *cpair;
  410. {
  411.     register NODE *r;
  412.  
  413.     r=(NODE *)obstack_alloc(&other_stack,sizeof(NODE));
  414.     r->type=Node_line_range;
  415.     r->condpair=cpair;
  416.     r->triggered = 0;
  417.     return r;
  418. }
  419.  
  420. /* this allocates a node with defined numbr */
  421. /* This creates global nodes! */
  422. NODE *
  423. make_number (x)
  424.      AWKNUM x;
  425. {
  426.   register NODE *r;
  427.  
  428.   r=newnode(Node_number);
  429.   r->numbr = x;
  430.   return r;
  431. }
  432.  
  433. /* This creates temporary nodes.  They go away quite quicly, so
  434.    don't use them for anything important */
  435. #ifndef FAST
  436. NODE *
  437. tmp_number(x)
  438. AWKNUM    x;
  439. {
  440. #ifdef DONTDEF
  441.     return make_number(x);
  442. #endif
  443.     NODE *r;
  444.  
  445.     r=(NODE *)obstack_alloc(&temp_strings,sizeof(NODE));
  446.     r->type=Node_number;
  447.     r->numbr=x;
  448.     return r;
  449. }
  450. #endif
  451.  
  452. /* Make a string node.  If len==0, the string passed in S is supposed to end
  453.    with a double quote, but have had the beginning double quote
  454.    already stripped off by yylex.
  455.    If LEN!=0, we don't care what s ends with.  This creates a global node */
  456.  
  457. NODE *
  458. make_string (s,len)
  459.      char *s;
  460. {
  461.   register NODE *r;
  462.   register char *pf,*pt;
  463.   register int    c;
  464.  
  465.   /* the aborts are impossible because yylex is supposed to have
  466.      already checked for unterminated strings */
  467.   if(len==-1) {        /* Called from yyparse, find our own len */
  468. #ifndef FAST
  469.     if (s[-1] != '\"')    /* Didn't start with " */
  470.       abort ();
  471. #endif
  472.  
  473.     for(pf = pt = s; *pf != '\0' && *pf!='\"';) {
  474.       c= *pf++;
  475.       switch(c) {
  476. #ifndef FAST
  477.       case '\0':
  478.     abort();
  479. #endif
  480.  
  481.       case '\\':
  482. #ifndef FAST
  483.           if(*pf=='\0')
  484.       abort();
  485. #endif
  486.  
  487.     c= *pf++;
  488.     switch(c) {
  489.     case '\\':    /* no massagary needed */
  490.     case '\'':
  491.     case '\"':
  492.       break;
  493.     case '0':
  494.     case '1':
  495.     case '2':
  496.     case '3':
  497.     case '4':
  498.     case '5':
  499.     case '6':
  500.     case '7':
  501.     case '8':
  502.     case '9':
  503.       c-='0';
  504.       while(*pf && *pf>='0' && *pf<='7') {
  505.         c=c*8+ *pf++ - '0';
  506.       }
  507.       break;
  508.     case 'b':
  509.       c='\b';
  510.       break;
  511.     case 'f':
  512.       c='\f';
  513.       break;
  514.     case 'n':
  515.       c='\n';
  516.       break;
  517.     case 'r':
  518.       c='\r';
  519.       break;
  520.     case 't':
  521.       c='\t';
  522.       break;
  523.     case 'v':
  524.       c='\v';
  525.       break;
  526.     default:
  527.       *pt++='\\';
  528.       break;
  529.     }
  530.     /* FALL THROUGH */
  531.       default:
  532.     *pt++=c;
  533.     break;
  534.       }
  535.     }
  536. #ifndef FAST
  537.     if(*pf=='\0')
  538.       abort();    /* JF hit the end of the buf */
  539. #endif
  540.     len = pt - s;        /* JF was p - s - 1 */
  541.   }
  542.  
  543.   r=newnode(Node_string);
  544.   r->stptr=(char *)malloc(len+1);
  545.   if(r->stptr==0)
  546.     panic("Memory exhausted");        /* -ade- was abort() */
  547.   r->type=Node_string;
  548.   r->stlen=len;
  549.   r->stref=1;
  550.   bcopy (s, r->stptr, len);
  551.   r->stptr[len]='\0';        /* JF a hack */
  552.  
  553.   return r;
  554. }
  555.  
  556. /* #ifndef FAST */
  557. /* This should be a macro for speed, but the C compiler chokes. */
  558. /* Read the warning under tmp_number */
  559. NODE *
  560. tmp_string(s,len)
  561. char *s;
  562. {
  563.   register NODE *r;
  564.  
  565. #ifdef DONTDEF
  566.   return make_string(s,len);
  567. #endif
  568.   r=(NODE *)obstack_alloc(&temp_strings,sizeof(NODE));
  569.   r->stptr=(char *)obstack_alloc(&temp_strings,len+1);
  570.   r->type=Node_temp_string;
  571.   r->stlen=len;
  572.   r->stref=1;
  573.   bcopy (s, r->stptr, len);
  574.   r->stptr[len]='\0';        /* JF a hack */
  575.  
  576.   return r;
  577. }
  578. /* #endif */
  579.  
  580. /* Generate compiled regular expressions */
  581.  
  582. /* like make_regexp but returns a NODE*  ADE */
  583.  
  584. NODE *
  585. make_regex(s)
  586. char *s;
  587. {
  588.     register NODE *r;
  589.  
  590.     r = newnode(Node_regex);
  591.     r->rereg = make_regexp(s);
  592.     return r;
  593. }
  594.  
  595. /* make a re_pattern_buffer on the fly from a node    ADE */
  596.  
  597. struct re_pattern_buffer *
  598. make_regexp_n(tree)
  599. NODE *tree;
  600. {
  601.     return (make_regexp(tree->stptr));
  602. }
  603.  
  604. struct re_pattern_buffer *
  605. make_regexp (s)
  606.      char *s;
  607. {
  608.   typedef struct re_pattern_buffer RPAT;
  609.   RPAT *rp;
  610.   char *p, *err;
  611.  
  612.   rp = (RPAT *) obstack_alloc(&other_stack, sizeof (RPAT));
  613.   bzero((char *)rp,sizeof(RPAT));
  614.   rp->buffer = (char *)malloc(8);    /* JF I'd obstack allocate it,
  615.                        except the regex routines
  616.                        try to realloc() it, which fails. */
  617.   /* Note that this means it may never be freed.  Someone fix, please? */
  618.  
  619.   rp->allocated = 8;
  620.   rp->fastmap = (char *)obstack_alloc(&other_stack, 256);
  621.  
  622.   for (p = s; *p != '\0'; p++) {
  623.     if (*p == '\\')
  624.       p++;
  625.     else if (*p == '/')
  626.       break;
  627.   }
  628. #ifndef FAST
  629.  /* commented out so it will not abort when
  630.  ** passed an expression  -ADE-
  631.   if (*p != '/')
  632.     abort (); */          /* impossible */
  633. #endif
  634.  
  635.     /* JF was re_compile_pattern, but that mishandles ( ) and |,
  636.        so I had to write my own front end.  Sigh. */
  637.  
  638.   if ((err = re_compile_pattern (s, p - s, rp)) != NULL) {
  639.     fprintf (stderr, "illegal regexp: ");
  640.     yyerror (err);        /* fatal */
  641.   }
  642.  
  643.   return rp;
  644. }
  645.  
  646. /* Build a for loop */
  647. FOR_LOOP_HEADER *
  648. make_for_loop (init, cond, incr)
  649.      NODE *init, *cond, *incr;
  650. {
  651.   register FOR_LOOP_HEADER *r;
  652.  
  653.   r = (FOR_LOOP_HEADER *)obstack_alloc(&other_stack,sizeof (FOR_LOOP_HEADER));
  654.   r->init = init;
  655.   r->cond = cond;
  656.   r->incr = incr;
  657.   return r;
  658. }
  659.  
  660. /* Name points to a variable name.  Make sure its in the symbol table */
  661. NODE *
  662. variable (name)
  663.      char *name;
  664. {
  665.   register NODE *r;
  666.   NODE    *lookup(), *install();
  667.  
  668.   if ((r = lookup (variables, name)) == NULL) {
  669.     r = install (variables, name, node(Nnull_string, Node_var, (NODE *)NULL));
  670.                         /* JF  make_number (0.0) is WRONG */
  671.   }
  672.   return r;
  673. }
  674.  
  675. /* Create a special variable */
  676. NODE *
  677. spc_var (name,value)
  678. char *name;
  679. NODE *value;
  680. {
  681.   register NODE *r;
  682.   NODE *lookup(), *install();
  683.  
  684.   if ((r = lookup(variables, name)) == NULL)
  685.     r = install (variables, name, node(value, Node_var, (NODE *)NULL));
  686.   return r;
  687. }
  688.  
  689.  
  690. /*
  691.  * Install a name in the hash table specified, even if it is already there.
  692.  * Name stops with first non alphanumeric.
  693.  * Caller must check against redefinition if that is desired.
  694.  */
  695. NODE *
  696. install (table, name, value)
  697.      HASHNODE **table;
  698.      char *name;
  699.      NODE *value;
  700. {
  701.   register HASHNODE *hp;
  702.   register int i, len, bucket;
  703.   register char *p;
  704.  
  705.   len = 0;
  706.   p = name;
  707.   while (is_identchar(*p))
  708.     p++;
  709.   len = p - name;
  710.  
  711.   i = sizeof (HASHNODE) + len + 1;
  712.   hp = (HASHNODE *)obstack_alloc(&other_stack,i);
  713.   bucket = hashf(name, len, HASHSIZE);
  714.   hp->next = table[bucket];
  715.   table[bucket] = hp;
  716.   hp->length = len;
  717.   hp->value = value;
  718.   hp->name = ((char *) hp) + sizeof (HASHNODE);
  719.   hp->length = len;
  720.   bcopy (name, hp->name, len);
  721.   return hp->value;
  722. }
  723.  
  724. /*
  725.  * find the most recent hash node for name name (ending with first
  726.  * non-identifier char) installed by install
  727.  */
  728. NODE *
  729. lookup (table, name)
  730.      HASHNODE **table;
  731.      char *name;
  732. {
  733.   register char *bp;
  734.   register HASHNODE *bucket;
  735.   register int len;
  736.  
  737.   for (bp = name; is_identchar(*bp); bp++)
  738.     ;
  739.   len = bp - name;
  740.   bucket = table[hashf(name, len, HASHSIZE)];
  741.   while (bucket) {
  742.     if (bucket->length == len && strncmp(bucket->name, name, len) == 0)
  743.       return bucket->value;
  744.     bucket = bucket->next;
  745.   }
  746.   return NULL;
  747. }
  748.  
  749. #define HASHSTEP(old, c) ((old << 1) + c)
  750. #define MAKE_POS(v) (v & ~0x80000000) /* make number positive */
  751.  
  752. /*
  753.  * return hash function on name.  must be compatible with the one
  754.  * computed a step at a time, elsewhere  (JF: Where?  I can't find it!)
  755.  */
  756. int
  757. hashf(name, len, hashsize)
  758.      register char *name;
  759.      register int len;
  760.      int hashsize;
  761. {
  762.   register int r = 0;
  763.  
  764.   while (len--)
  765.     r = HASHSTEP(r, *name++);
  766.  
  767.   return MAKE_POS(r) % hashsize;
  768. }
  769.  
  770. /* Add new to the rightmost branch of LIST.  This uses n^2 time, but
  771.    doesn't get used enough to make optimizing worth it. . . */
  772. /* You don't believe me?  Profile it yourself! */
  773.  
  774. NODE *
  775. append_right(list,new)
  776. NODE *list,*new;
  777. {
  778.     register NODE *oldlist;
  779.  
  780.     oldlist = list;
  781.     while(list->rnode!=NULL)
  782.         list=list->rnode;
  783.     list->rnode = new;
  784.     return oldlist;
  785. }
  786.