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