home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / mkstates.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-11-04  |  27.6 KB  |  677 lines
  1. /* $Id: mkstates.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
  2. /*
  3.  This software is subject to the terms of the IBM Jikes Compiler
  4.  License Agreement available at the following URL:
  5.  http://www.ibm.com/research/jikes.
  6.  Copyright (C) 1983, 1999, International Business Machines Corporation
  7.  and others.  All Rights Reserved.
  8.  You must accept the terms of that agreement to use this software.
  9. */
  10. static char hostfile[] = __FILE__;
  11.  
  12. #include "common.h"
  13. #include "header.h"
  14.  
  15. static void mklr0(void);
  16. static struct state_element *lr0_state_map(struct node *kernel);
  17.  
  18. /****************************************************************************/
  19. /* STATE_ELEMENT is used to represent states. Each state is mapped into a   */
  20. /* unique number. The components QUEUE and LINK are auxiliary:              */
  21. /*   QUEUE is used to form a sequential linked-list of the states ordered   */
  22. /* STATE_NUMBER and identified by the variable STATE_ROOT.                  */
  23. /*   LINK is used to resolve collisions in hashing the states.              */
  24. /* NEXT_SHIFT is used to resolve collisions in hashing SHIFT maps.          */
  25. /****************************************************************************/
  26. struct state_element
  27. {
  28.     struct state_element     *link,
  29.                              *queue,
  30.                              *next_shift;
  31.     struct node              *kernel_items,
  32.                              *complete_items;
  33.     struct shift_header_type lr0_shift;
  34.     struct goto_header_type  lr0_goto;
  35.     short                    shift_number,
  36.                              state_number;
  37. };
  38.  
  39. static struct state_element **state_table,
  40.                             **shift_table,
  41.                              *state_root,
  42.                              *state_tail;
  43.  
  44. static short *shift_action;
  45.  
  46. static struct goto_header_type  no_gotos_ptr;
  47. static struct shift_header_type no_shifts_ptr;
  48.  
  49. /*****************************************************************************/
  50. /*                              MKSTATS:                                     */
  51. /*****************************************************************************/
  52. /* In this procedure, we first construct the LR(0) automaton.                */
  53. /*****************************************************************************/
  54. void mkstats(void)
  55. {
  56.     int j;
  57.  
  58.     no_gotos_ptr.size = 0;     /* For states with no GOTOs */
  59.     no_gotos_ptr.map  = NULL;
  60.  
  61.     no_shifts_ptr.size = 0;    /* For states with no SHIFTs */
  62.     no_shifts_ptr.map  = NULL;
  63.  
  64.     mklr0();
  65.  
  66.     if (error_maps_bit &&
  67.         (table_opt == OPTIMIZE_TIME || table_opt == OPTIMIZE_SPACE))
  68.         produce();
  69.  
  70.     /**********************************************************************/
  71.     /* Free space trapped by the CLOSURE and CLITEMS maps.                */
  72.     /**********************************************************************/
  73.     for ALL_NON_TERMINALS(j)
  74.     {
  75.         struct node *p, *q;
  76.  
  77.         q = clitems[j];
  78.         if (q != NULL)
  79.         {
  80.             p = q -> next;
  81.             free_nodes(p, q);
  82.         }
  83.  
  84.         q = closure[j];
  85.         if (q != NULL)
  86.         {
  87.             p = q -> next;
  88.             free_nodes(p, q);
  89.         }
  90.     }
  91.  
  92.     closure += (num_terminals + 1);
  93.     ffree(closure);
  94.     clitems += (num_terminals + 1);
  95.     ffree(clitems);
  96.  
  97.     return;
  98. }
  99.  
  100.  
  101. /*****************************************************************************/
  102. /*                               MKLR0:                                      */
  103. /*****************************************************************************/
  104. /* This procedure constructs an LR(0) automaton.                             */
  105. /*****************************************************************************/
  106. static void mklr0(void)
  107. {
  108.     /*****************************************************************/
  109.     /* STATE_TABLE is the array used to hash the states. States are  */
  110.     /* identified by their Kernel set of items. Hash locations are   */
  111.     /* computed for the states. As states are inserted in the table, */
  112.     /* they are threaded together via the QUEUE component of         */
  113.     /* STATE_ELEMENT. The variable STATE_ROOT points to the root of  */
  114.     /* the thread, and the variable STATE_TAIL points to the tail.   */
  115.     /*                                                               */
  116.     /*   After constructing a state, Shift and Goto actions are      */
  117.     /* defined on that state based on a partition of the set of items*/
  118.     /* in that state. The partitioning is based on the symbols       */
  119.     /* following the dot in the items. The array PARTITION is used   */
  120.     /* for that partitioning. LIST and ROOT are used to construct    */
  121.     /* temporary lists of symbols in a state on which Shift or Goto  */
  122.     /* actions are defined.                                          */
  123.     /*   NT_LIST and NT_ROOT are used to build temporary lists of    */
  124.     /* non-terminals.                                                */
  125.     /*****************************************************************/
  126.  
  127.     struct node *p,
  128.                 *q,
  129.                 *r,
  130.                 *new_item,
  131.                 *tail,
  132.                 *item_ptr,
  133.                 **partition,
  134.                 *closure_root,
  135.                 *closure_tail;
  136.  
  137.     struct state_element *state,
  138.                          *new_state;
  139.  
  140.     BOOLEAN end_node;
  141.  
  142.     int goto_size,
  143.         shift_size,
  144.         i,
  145.         state_no,
  146.         next_item_no,
  147.         item_no,
  148.         symbol,
  149.         rule_no,
  150.         shift_root,
  151.         nt_root,
  152.         root;
  153.  
  154.     struct goto_header_type go_to;
  155.  
  156.     short *shift_list,
  157.           *nt_list,
  158.           *list;
  159.  
  160.     /******************************************************************/
  161.     /* Set up a a pool of temporary space.                            */
  162.     /******************************************************************/
  163.     reset_temporary_space();
  164.  
  165.     list = Allocate_short_array(num_symbols + 1);
  166.     shift_action = Allocate_short_array(num_terminals + 1);
  167.     shift_list = Allocate_short_array(num_terminals + 1);
  168.     nt_list = Allocate_short_array(num_non_terminals);
  169.     nt_list -= (num_terminals + 1);
  170.     partition = (struct node **)
  171.                 calloc(num_symbols + 1, sizeof(struct node *));
  172.     if (partition == NULL)
  173.         nospace(__FILE__, __LINE__);
  174.     state_table = (struct state_element **)
  175.                   calloc(STATE_TABLE_SIZE, sizeof(struct state_element *));
  176.     if (state_table == NULL)
  177.         nospace(__FILE__, __LINE__);
  178.     shift_table = (struct state_element **)
  179.                   calloc(SHIFT_TABLE_SIZE, sizeof(struct state_element *));
  180.     if (shift_table == NULL)
  181.         nospace(__FILE__, __LINE__);
  182.  
  183. /* INITIALIZATION -----------------------------------------------------------*/
  184.     goto_size = 0;
  185.     shift_size = 0;
  186.  
  187.     state_root = NULL;
  188.  
  189.     for (i = 0; i <= num_terminals; i++)
  190.         shift_action[i] = OMEGA;
  191.  
  192.     nt_root = NIL;
  193.     for ALL_NON_TERMINALS(i)
  194.         nt_list[i] = OMEGA;
  195.  
  196.    /* PARTITION, STATE_TABLE and SHIFT_TABLE are initialized by calloc */
  197.  
  198. /* END OF INITIALIZATION ----------------------------------------------------*/
  199.  
  200.     /*****************************************************************/
  201.     /* Kernel of the first state consists of the first items in each */
  202.     /* rule produced by Accept non-terminal.                         */
  203.     /*****************************************************************/
  204.     q = NULL;
  205.     for (end_node = ((p = clitems[accept_image]) == NULL);
  206.          ! end_node; /* Loop over circular list */
  207.          end_node = (p == clitems[accept_image]))
  208.     {
  209.         p = p -> next;
  210.  
  211.         new_item = Allocate_node();
  212.         new_item -> value = p -> value;
  213.         new_item -> next = q;
  214.         q = new_item;
  215.     }
  216.  
  217.     /*****************************************************************/
  218.     /* Insert first state in STATE_TABLE and keep constructing states*/
  219.     /* until we no longer can.                                       */
  220.     /*****************************************************************/
  221.  
  222.     for (state = lr0_state_map(q); /* insert initial state */
  223.          state != NULL; /* and process next state until no more */
  224.          state = state -> queue)
  225.     {
  226.         /******************************************************************/
  227.         /* Now we construct a list of all non-terminals that can be       */
  228.         /* introduced in this state through closure.  The CLOSURE of each */
  229.         /* non-terminal has been previously computed in MKFIRST.          */
  230.         /******************************************************************/
  231.         for (q = state -> kernel_items;
  232.              q != NULL; /* iterate over kernel set of items */
  233.              q = q -> next)
  234.         {
  235.             item_no = q -> value;
  236.             symbol = item_table[item_no].symbol;  /* symbol after dot */
  237.             if (symbol IS_A_NON_TERMINAL)     /* Dot symbol */
  238.             {
  239.                 if (nt_list[symbol] == OMEGA) /* not yet seen */
  240.                 {
  241.                     nt_list[symbol] = nt_root;
  242.                     nt_root = symbol;
  243.  
  244.                     for (end_node = ((p = closure[symbol]) == NULL);
  245.                          ! end_node; /* Loop over circular list */
  246.                          end_node = (p == closure[symbol]))
  247.                     {   /* add its closure to list */
  248.                         p = p -> next;
  249.  
  250.                         if (nt_list[p -> value] == OMEGA)
  251.                         {
  252.                             nt_list[p -> value] = nt_root;
  253.                             nt_root = p -> value;
  254.                         }
  255.                     }
  256.                 }
  257.             }
  258.         }
  259.  
  260.         /*******************************************************************/
  261.         /*   We now construct lists of all start items that the closure    */
  262.         /* non-terminals produce.  A map from each non-terminal to its set */
  263.         /* start items has previously been computed in MKFIRST. (CLITEMS)  */
  264.         /* Empty items are placed directly in the state, whereas non_empty */
  265.         /* items are placed in a temporary list rooted at CLOSURE_ROOT.    */
  266.         /*******************************************************************/
  267.         closure_root = NULL; /* used to construct list of closure items */
  268.         for (symbol = nt_root; symbol != NIL;
  269.              nt_list[symbol] = OMEGA, symbol = nt_root)
  270.         {
  271.             nt_root = nt_list[symbol];
  272.  
  273.             for (end_node = ((p = clitems[symbol]) == NULL);
  274.                  ! end_node;  /* Loop over circular list */
  275.                  end_node = (p == clitems[symbol]))
  276.             {
  277.                 p = p -> next;
  278.  
  279.                 item_no = p -> value;
  280.                 new_item = Allocate_node();
  281.                 new_item -> value = item_no;
  282.  
  283.                 if (item_table[item_no].symbol == empty) /* complete item */
  284.                 {
  285.                     /* Add to COMPLETE_ITEMS set in state */
  286.                     new_item -> next = state -> complete_items;
  287.                     state -> complete_items = new_item;
  288.                 }
  289.                 else
  290.                 {   /* closure item, add to closure list */
  291.                     if (closure_root == NULL)
  292.                         closure_root = new_item;
  293.                     else
  294.                         closure_tail -> next = new_item;
  295.                     closure_tail = new_item;
  296.                 }
  297.             }
  298.         }
  299.  
  300.         if  (closure_root != NULL) /* any non-complete closure items? */
  301.         {
  302.             /* construct list of them and kernel items */
  303.             closure_tail -> next = state -> kernel_items;
  304.             item_ptr = closure_root;
  305.         }
  306.         else  /* else just consider kernel items */
  307.             item_ptr = state -> kernel_items;
  308.  
  309.         /*******************************************************************/
  310.         /*   In this loop, the PARTITION map is constructed. At this point,*/
  311.         /* ITEM_PTR points to all the non_complete items in the closure of */
  312.         /* the state, plus all the kernel items.  We note that the kernel  */
  313.         /* items may still contain complete-items, and if any is found, the*/
  314.         /* COMPLETE_ITEMS list is updated.                                 */
  315.         /*******************************************************************/
  316.         root = NIL;
  317.         for (; item_ptr != NULL; item_ptr = item_ptr -> next)
  318.         {
  319.             item_no = item_ptr -> value;
  320.             symbol = item_table[item_no].symbol;
  321.             if (symbol != empty)  /* incomplete item */
  322.             {
  323.                 next_item_no = item_no + 1;
  324.                 
  325.                 if (partition[symbol] == NULL)
  326.                 {   /* PARTITION not defined on symbol */
  327.                     list[symbol] = root;  /* add to list */
  328.                     root = symbol;
  329.                     if (symbol IS_A_TERMINAL) /* Update transition count */
  330.                         shift_size++;
  331.                     else
  332.                         goto_size++;
  333.                 }
  334.                 for (p = partition[symbol];
  335.                      p != NULL;
  336.                      tail = p, p = p -> next)
  337.                 {
  338.                     if (p -> value > next_item_no)
  339.                         break;
  340.                 }
  341.  
  342.                 r = Allocate_node();
  343.                 r -> value = next_item_no;
  344.                 r -> next = p;
  345.  
  346.                 if (p == partition[symbol]) /* Insert at beginning */
  347.                     partition[symbol] = r;
  348.                 else
  349.                     tail -> next = r;
  350.             }
  351.             else /* Update complete item set with item from kernel */
  352.             {
  353.                  p = Allocate_node();
  354.                  p -> value = item_no;
  355.                  p -> next = state -> complete_items;
  356.                  state -> complete_items = p;
  357.             }
  358.         }
  359.         if (closure_root != NULL)
  360.             free_nodes(closure_root, closure_tail);
  361.  
  362.         /*******************************************************************/
  363.         /* We now iterate over the set of partitions and update the state  */
  364.         /* automaton and the transition maps: SHIFT and GOTO. Each         */
  365.         /* partition represents the kernel of a state.                     */
  366.         /*******************************************************************/
  367.         if (goto_size > 0)
  368.         {
  369.             go_to = Allocate_goto_map(goto_size);
  370.             state -> lr0_goto = go_to;
  371.         }
  372.         else
  373.             state -> lr0_goto = no_gotos_ptr;
  374.  
  375.         shift_root = NIL;
  376.         for (symbol = root;
  377.              symbol != NIL; /* symbols on which transition is defined */
  378.              symbol = list[symbol])
  379.         {
  380.             short action = OMEGA;
  381.  
  382.             /*****************************************************************/
  383.             /* If the partition contains only one item, and it is adequate   */
  384.             /* (i.e. the dot immediately follows the last symbol), and       */
  385.             /* READ-REDUCE is requested, a new state is not created, and the */
  386.             /* action is marked as a Shift-reduce or a Goto-reduce. Otherwise*/
  387.             /* if a state with that kernel set does not yet exist, we create */
  388.             /* it.                                                           */
  389.             /*****************************************************************/
  390.             q = partition[symbol]; /* kernel of a new state */
  391.             if (read_reduce_bit && q -> next == NULL)
  392.             {
  393.                 item_no = q -> value;
  394.                 if (item_table[item_no].symbol == empty)
  395.                 {
  396.                     rule_no = item_table[item_no].rule_number;
  397.                     if (rules[rule_no].lhs != accept_image)
  398.                     {
  399.                         action = -rule_no;
  400.                         free_nodes(q, q);
  401.                     }
  402.                 }
  403.             }
  404.  
  405.             if (action == OMEGA) /* Not a Read-Reduce action */
  406.             {
  407.                 new_state = lr0_state_map(q);
  408.                 action = new_state -> state_number;
  409.             }
  410.  
  411.             /****************************************************************/
  412.             /* At this stage, the partition list has been freed (for an old */
  413.             /* state or an ADEQUATE item), or used (for a new state).  The  */
  414.             /* PARTITION field involved should be reset.                    */
  415.             /****************************************************************/
  416.             partition[symbol] = NULL;           /* To be reused */
  417.  
  418.             /*****************************************************************/
  419.             /* At this point, ACTION contains the value of the state to Shift*/
  420.             /* to, or rule to Read-Reduce on. If the symbol involved is a    */
  421.             /* terminal, we update the Shift map; else, it is a non-terminal */
  422.             /* and we update the Goto map.                                   */
  423.             /* Shift maps are constructed temporarily in SHIFT_ACTION.       */
  424.             /* Later, they are inserted into a map of unique Shift maps, and */
  425.             /* shared by states that contain identical shifts.               */
  426.             /* Since the lookahead set computation is based on the GOTO maps,*/
  427.             /* all these maps and their element maps should be kept as       */
  428.             /* separate entities.                                            */
  429.             /*****************************************************************/
  430.             if (symbol IS_A_TERMINAL) /* terminal? add to SHIFT map */
  431.             {
  432.                 shift_action[symbol] = action;
  433.                 shift_list[symbol] = shift_root;
  434.                 shift_root = symbol;
  435.                 if (action > 0)
  436.                     num_shifts++;
  437.                 else
  438.                     num_shift_reduces++;
  439.             }
  440.  
  441.             /*****************************************************************/
  442.             /* NOTE that for Goto's we update the field LA_PTR of GOTO. This */
  443.             /* field will be used later in the routine MKRDCTS to point to a */
  444.             /* look-ahead set.                                               */
  445.             /*****************************************************************/
  446.             else
  447.             {
  448.                 GOTO_SYMBOL(go_to, goto_size) = symbol; /* symbol field */
  449.                 GOTO_ACTION(go_to, goto_size) = action; /* state field  */
  450.                 GOTO_LAPTR(go_to,  goto_size) = OMEGA;  /* la_ptr field */
  451.                 goto_size--;
  452.                 if (action > 0)
  453.                     num_gotos++;
  454.                 else
  455.                     num_goto_reduces++;
  456.             }
  457.         }
  458.  
  459.         /*******************************************************************/
  460.         /* We are now going to update the set of Shift-maps. Ths idea is   */
  461.         /* to do a look-up in a hash table based on SHIFT_TABLE to see if  */
  462.         /* the Shift map associated with the current state has already been*/
  463.         /* computed. If it has, we simply update the SHIFT_NUMBER and the  */
  464.         /* SHIFT field of the current state. Otherwise, we allocate and    */
  465.         /* construct a SHIFT_ELEMENT map, update the current state, and    */
  466.         /* add it to the set of Shift maps in the hash table.              */
  467.         /*   Note that the SHIFT_NUMBER field in the STATE_ELEMENTs could  */
  468.         /* have been factored out and associated instead with the          */
  469.         /* SHIFT_ELEMENTs. That would have saved some space, but only in   */
  470.         /* the short run. This field was purposely stored in the           */
  471.         /* STATE_ELEMENTs, because once the states have been constructed,  */
  472.         /* they are not kept, whereas the SHIFT_ELEMENTs are kept.         */
  473.         /*    One could have also threaded through the states that contain */
  474.         /* original shift maps so as to avoid duplicate assignments in     */
  475.         /* creating the SHIFT map later. However, this would have          */
  476.         /* increased the storage requirement, and would probably have saved*/
  477.         /* (at most) a totally insignificant amount of time.               */
  478.         /*******************************************************************/
  479. update_shift_maps:
  480.         {
  481.             unsigned long hash_address;
  482.  
  483.             struct shift_header_type sh;
  484.  
  485.             struct state_element *p;
  486.  
  487.             hash_address = shift_size;
  488.             for (symbol = shift_root;
  489.                  symbol != NIL; symbol = shift_list[symbol])
  490.             {
  491.                 hash_address += ABS(shift_action[symbol]);
  492.             }
  493.             hash_address %= SHIFT_TABLE_SIZE;
  494.  
  495.             for (p = shift_table[hash_address];
  496.                  p != NULL; /* Search has table for shift map */
  497.                  p = p -> next_shift)
  498.             {
  499.                 sh = p -> lr0_shift;
  500.                 if (sh.size == shift_size)
  501.                 {
  502.                     for (i = 1; i <= shift_size; i++) /* Compare shift maps */
  503.                     {
  504.                         if (SHIFT_ACTION(sh, i) !=
  505.                             shift_action[SHIFT_SYMBOL(sh, i)])
  506.                             break;
  507.                     }
  508.  
  509.                     if (i > shift_size)  /* Are they equal ? */
  510.                     {
  511.                         state -> lr0_shift    = sh;
  512.                         state -> shift_number = p -> shift_number;
  513.                         for (symbol = shift_root;
  514.                              symbol != NIL; symbol = shift_list[symbol])
  515.                         { /* Clear SHIFT_ACTION */
  516.                             shift_action[symbol] = OMEGA;
  517.                         }
  518.                         shift_size = 0;   /* Reset for next round */
  519.                         goto leave_update_shift_maps;
  520.                     }
  521.                 }
  522.             }
  523.  
  524.             if (shift_size > 0)
  525.             {
  526.                 sh = Allocate_shift_map(shift_size);
  527.                 num_shift_maps++;
  528.                 state -> shift_number = num_shift_maps;
  529.             }
  530.             else
  531.             {
  532.                 state -> shift_number = 0;
  533.                 sh = no_shifts_ptr;
  534.             }
  535.  
  536.             state -> lr0_shift = sh;
  537.             state -> next_shift = shift_table[hash_address];
  538.             shift_table[hash_address] = state;
  539.  
  540.             for (symbol = shift_root;
  541.                  symbol != NIL; symbol = shift_list[symbol])
  542.             {
  543.                 SHIFT_SYMBOL(sh, shift_size) = symbol;
  544.                 SHIFT_ACTION(sh, shift_size) = shift_action[symbol];
  545.                 shift_action[symbol] = OMEGA;
  546.                 shift_size--;
  547.             }
  548.         } /*end update_shift_maps */
  549.  
  550. leave_update_shift_maps:;
  551.     }
  552.  
  553.     /*********************************************************************/
  554.     /* Construct STATSET, a "compact" and final representation of        */
  555.     /* State table, and SHIFT which is a set of all shift maps needed.   */
  556.     /* NOTE that assignments to elements of SHIFT may occur more than    */
  557.     /* once, but that's ok. It is probably faster to  do that than to    */
  558.     /* set up an elaborate scheme to avoid the multiple assignment which */
  559.     /* may in fact cost more.  Look at it this way: it is only a pointer */
  560.     /* assignment, namely a Load and a Store.                            */
  561.     /* Release all NODEs used by  the maps CLITEMS and CLOSURE.          */
  562.     /*********************************************************************/
  563.     {
  564.         struct state_element *p;
  565.  
  566.     /*********************************************************************/
  567.     /* If the grammar is LALR(k), k > 1, more states may be added and    */
  568.     /* the size of the shift map increased.                              */
  569.     /*********************************************************************/
  570.         shift = (struct shift_header_type *)
  571.                 calloc(num_states + 1, sizeof(struct shift_header_type));
  572.         if (shift == NULL)
  573.             nospace(__FILE__, __LINE__);
  574.         shift[0] = no_shifts_ptr;        /* MUST be initialized for LALR(k) */
  575.         statset = (struct statset_type *)
  576.                   calloc(num_states + 1, sizeof(struct statset_type));
  577.         if (statset == NULL)
  578.             nospace(__FILE__, __LINE__);
  579.  
  580.         for (p = state_root; p != NULL; p = p -> queue)
  581.         {
  582.             state_no = p -> state_number;
  583.             statset[state_no].kernel_items = p -> kernel_items;
  584.             statset[state_no].complete_items = p -> complete_items;
  585.             shift[p -> shift_number] = p -> lr0_shift;
  586.             statset[state_no].shift_number = p -> shift_number;
  587.             statset[state_no].go_to = p -> lr0_goto;
  588.         }
  589.     }
  590.  
  591.     ffree(list);
  592.     ffree(shift_action);
  593.     ffree(shift_list);
  594.     nt_list += (num_terminals + 1);
  595.     ffree(nt_list);
  596.     ffree(partition);
  597.     ffree(state_table);
  598.     ffree(shift_table);
  599.  
  600.     return;
  601. }
  602.  
  603.  
  604. /*****************************************************************************/
  605. /*                            LR0_STATE_MAP:                                 */
  606. /*****************************************************************************/
  607. /* LR0_STATE_MAP takes as an argument a pointer to a kernel set of items. If */
  608. /* no state based on that kernel set already exists, then a new one is       */
  609. /* created and added to STATE_TABLE. In any case, a pointer to the STATE of  */
  610. /* the KERNEL is returned.                                                   */
  611. /*****************************************************************************/
  612. static struct state_element *lr0_state_map(struct node *kernel)
  613. {
  614.     unsigned long hash_address = 0;
  615.     struct node *p;
  616.     struct state_element *state_ptr,
  617.                          *ptr;
  618.  
  619.     /*********************************************/
  620.     /*       Compute the hash address.           */
  621.     /*********************************************/
  622.     for (p = kernel; p != NULL; p = p -> next)
  623.     {
  624.         hash_address += p -> value;
  625.     }
  626.     hash_address %= STATE_TABLE_SIZE;
  627.  
  628.     /*************************************************************************/
  629.     /* Check whether a state is already defined by the KERNEL set.           */
  630.     /*************************************************************************/
  631.     for (state_ptr = state_table[hash_address];
  632.          state_ptr != NULL; state_ptr = state_ptr -> link)
  633.     {
  634.         struct node *q,
  635.                     *r;
  636.  
  637.         for (p = state_ptr -> kernel_items, q = kernel;
  638.              p != NULL && q != NULL;
  639.              p = p -> next, r = q, q = q -> next)
  640.         {
  641.             if (p -> value != q -> value)
  642.                 break;
  643.         }
  644.  
  645.         if (p == q)  /* Both P and Q are NULL? */
  646.         {
  647.             free_nodes(kernel, r);
  648.             return(state_ptr);
  649.         }
  650.     }
  651.  
  652.  
  653.     /*******************************************************************/
  654.     /* Add a new state based on the KERNEL set.                        */
  655.     /*******************************************************************/
  656.     ptr = (struct state_element *) talloc(sizeof(struct state_element));
  657.     if (ptr == (struct state_element *) NULL)
  658.         nospace(__FILE__, __LINE__);
  659.  
  660.     num_states++;
  661.     SHORT_CHECK(num_states);
  662.     ptr -> queue = NULL;
  663.     ptr -> kernel_items = kernel;
  664.     ptr -> complete_items = NULL;
  665.     ptr -> state_number = num_states;
  666.     ptr -> link = state_table[hash_address];
  667.     state_table[hash_address] = ptr;
  668.     if (state_root == NULL)
  669.         state_root = ptr;
  670.     else
  671.         state_tail -> queue = ptr;
  672.  
  673.     state_tail = ptr;
  674.  
  675.     return(ptr);
  676. }
  677.