/tmp/build/foma/foma-0.10.0+g279~a2d32b38/determinize.c

Bug Summary

File:	determinize.c
Warning:	line 626, column 44 The left operand of '==' is a garbage value

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name determinize.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/tmp/build/foma/foma-0.10.0+g279~a2d32b38 -resource-dir /usr/lib/llvm-16/lib/clang/16 -D _GNU_SOURCE -D foma_shared_EXPORTS -I /tmp/build/foma/foma-0.10.0+g279~a2d32b38 -internal-isystem /usr/lib/llvm-16/lib/clang/16/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -Wno-missing-field-initializers -Wno-deprecated -Wno-unused-parameter -std=c18 -fdebug-compilation-dir=/tmp/build/foma/foma-0.10.0+g279~a2d32b38 -ferror-limit 19 -fvisibility=hidden -fgnuc-version=4.2.1 -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/build/foma/scan-build/2024-09-11-155945-2678-1 -x c /tmp/build/foma/foma-0.10.0+g279~a2d32b38/determinize.c

1/*   Foma: a finite-state toolkit and library.                                 */
2/*   Copyright © 2008-2021 Mans Hulden                                         */

4/*   This file is part of foma.                                                */

6/*   Licensed under the Apache License, Version 2.0 (the "License");           */
7/*   you may not use this file except in compliance with the License.          */
8/*   You may obtain a copy of the License at                                   */

10/*      http://www.apache.org/licenses/LICENSE-2.0                             */

12/*   Unless required by applicable law or agreed to in writing, software       */
13/*   distributed under the License is distributed on an "AS IS" BASIS,         */
14/*   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  */
15/*   See the License for the specific language governing permissions and       */
16/*   limitations under the License.                                            */

18#include <stdio.h>
19#include <stdlib.h>
20#include <assert.h>
21#include <limits.h>
22#include <stdint.h>
23#include <string.h>
24#include "foma.h"

26#define SUBSET_EPSILON_REMOVE1 1
27#define SUBSET_DETERMINIZE2 2
28#define SUBSET_TEST_STAR_FREE3 3

30#define NHASH_LOAD_LIMIT2 2 /* load limit for nhash table size */

32static int fsm_linecount, num_states, num_symbols, epsilon_symbol, *single_sigma_array, *double_sigma_array, limit, num_start_states, op;

34static _Bool *finals, deterministic, numss;

36struct e_closure_memo {
  int state;
  int mark;
  struct e_closure_memo *target;
  struct e_closure_memo *next;
41};

43static unsigned int primes[26] = {61,127,251,509,1021,2039,4093,8191,16381,32749,65521,131071,262139,524287,1048573,2097143,4194301,8388593,16777213,33554393,67108859,134217689,268435399,536870909,1073741789,2147483647};

45static struct e_closure_memo *e_closure_memo;

47int T_last_unmarked, T_limit;

49struct nhash_list {
  int setnum;
  unsigned int size;
  unsigned int set_offset;
  struct nhash_list *next;
54};

56struct T_memo {
  unsigned char finalstart;
  unsigned int size;
  unsigned int set_offset;
60};

62struct trans_list {
  int inout;
  int target;
65} *trans_list_determinize;

67struct trans_array {
  struct trans_list *transitions;
  unsigned int size;
  unsigned int tail;
71} *trans_array_determinize;

73static struct T_memo *T_ptr;

75static int nhash_tablesize, nhash_load, current_setnum, *e_table, *marktable, *temp_move, mainloop, maxsigma, *set_table, set_table_size, star_free_mark;
76static unsigned int set_table_offset;
77static struct nhash_list *table;

79extern int add_fsm_arc(struct fsm_state *fsm, int offset, int state_no, int in, int out, int target, int final_state, int start_state);

81static void init(struct fsm *net);
82INLINEinline static int e_closure(int states);
83INLINEinline static int set_lookup(int *lookup_table, int size);
84static int initial_e_closure(struct fsm *network);
85static void memoize_e_closure(struct fsm_state *fsm);
86static int next_unmarked(void);
87static void single_symbol_to_symbol_pair(int symbol, int *symbol_in, int *symbol_out);
88static int symbol_pair_to_single_symbol(int in, int out);
89static void sigma_to_pairs(struct fsm *net);
90static int nhash_find_insert(int *set, int setsize);
91INLINEinline static int hashf(int *set, int setsize);
92static int nhash_insert(int hashval, int *set, int setsize);
93static void nhash_rebuild_table ();
94static void nhash_init (int initial_size);
95static void nhash_free(struct nhash_list *nptr, int size);
96static void e_closure_free();
97static void init_trans_array(struct fsm *net);
98static struct fsm *fsm_subset(struct fsm *net, int operation);

100struct fsm *fsm_epsilon_remove(struct fsm *net) {
  return(fsm_subset(net, SUBSET_EPSILON_REMOVE1));
102}

104struct fsm *fsm_determinize(struct fsm *net) {
  return(fsm_subset(net, SUBSET_DETERMINIZE2));
1
Calling 'fsm_subset'→
106}

108static struct fsm *fsm_subset(struct fsm *net, int operation) {

  int T, U;

  if (net->is_deterministic == YES1 && operation != SUBSET_TEST_STAR_FREE3) {
2
←
Assuming field 'is_deterministic' is not equal to YES→
      return(net);
  }
  /* Export this var */
  op = operation;
  fsm_count(net);
  num_states = net->statecount;
  deterministic = 1;
  init(net);
3
←
Calling 'init'→
  nhash_init((num_states < 12) ? 6 : num_states/2);

  T = initial_e_closure(net);

  int_stack_clear();

  if (deterministic == 1 && epsilon_symbol == -1 && num_start_states == 1 && numss == 0) {
      net->is_deterministic = YES1;
      net->is_epsilon_free = YES1;
      nhash_free(table, nhash_tablesize);
      free(T_ptr);
      free(e_table);
      free(trans_list_determinize);
      free(trans_array_determinize);
      free(double_sigma_array);
      free(single_sigma_array);
      free(finals);
      free(temp_move);
      free(set_table);
      return(net);
  }

  if (operation == SUBSET_EPSILON_REMOVE1 && epsilon_symbol == -1) {
      net->is_epsilon_free = YES1;
      nhash_free(table, nhash_tablesize);
      free(T_ptr);
      free(e_table);
      free(trans_list_determinize);
      free(trans_array_determinize);
      free(double_sigma_array);
      free(single_sigma_array);
      free(finals);
      free(temp_move);
      free(set_table);
      return(net);
  }

  if (operation == SUBSET_TEST_STAR_FREE3) {
      fsm_state_init(sigma_max(net->sigma)+1);
      star_free_mark = 0;
  } else {
      fsm_state_init(sigma_max(net->sigma));
      free(net->states);
  }

  /* init */

  do {
      int i, j, tail, setsize, *theset, stateno, has_trans, minsym, next_minsym, trgt, symbol_in, symbol_out;
      struct trans_list *transitions;
      struct trans_array *tptr;

      fsm_state_set_current_state(T, (T_ptr+T)->finalstart, T == 0 ? 1 : 0);

      /* Prepare set */
      setsize = (T_ptr+T)->size;
      theset = set_table+(T_ptr+T)->set_offset;
      minsym = INT_MAX2147483647;
      has_trans = 0;
      for (i = 0; i < setsize; i++) {
          stateno = *(theset+i);
          tptr = trans_array_determinize+stateno;
          tptr->tail = 0;
          if (tptr->size == 0)
              continue;
          if ((tptr->transitions)->inout < minsym) {
              minsym = (tptr->transitions)->inout;
              has_trans = 1;
          }
      }
      if (!has_trans) {
          /* close state */
          fsm_state_end_state();
          continue;
      }

      /* While set not empty */

      for (next_minsym = INT_MAX2147483647; minsym != INT_MAX2147483647 ; minsym = next_minsym, next_minsym = INT_MAX2147483647) {
          theset = set_table+(T_ptr+T)->set_offset;

          for (i = 0, j = 0 ; i < setsize; i++) {

              stateno = *(theset+i);
              tptr = trans_array_determinize+stateno;
              tail = tptr->tail;
              transitions = (tptr->transitions)+tail;

              while (tail < tptr->size &&  transitions->inout == minsym) {
                  trgt = transitions->target;
                  if (*(e_table+(trgt)) != mainloop) {
                      *(e_table+(trgt)) = mainloop;
                      *(temp_move+j) = trgt;
                      j++;

                      if (operation == SUBSET_EPSILON_REMOVE1) {
                          mainloop++;
                          if ((U = e_closure(j)) != -1) {
                              single_symbol_to_symbol_pair(minsym, &symbol_in, &symbol_out);
                              fsm_state_add_arc(T, symbol_in, symbol_out, U, (T_ptr+T)->finalstart, T == 0 ? 1 : 0);
                              j = 0;
                          }
                      }
                  }
                  tail++;
                  transitions++;
              }

              tptr->tail = tail;

              if (tail == tptr->size)
                  continue;
              /* Check next minsym */
              if (transitions->inout < next_minsym) {
                  next_minsym = transitions->inout;
              }
          }
          if (operation == SUBSET_DETERMINIZE2) {
              mainloop++;
              if ((U = e_closure(j)) != -1) {
                  single_symbol_to_symbol_pair(minsym, &symbol_in, &symbol_out);
                  fsm_state_add_arc(T, symbol_in, symbol_out, U, (T_ptr+T)->finalstart, T == 0 ? 1 : 0);
              }
          }
          if (operation == SUBSET_TEST_STAR_FREE3) {
              mainloop++;
              if ((U = e_closure(j)) != -1) {
                  single_symbol_to_symbol_pair(minsym, &symbol_in, &symbol_out);
                  fsm_state_add_arc(T, symbol_in, symbol_out, U, (T_ptr+T)->finalstart, T == 0 ? 1 : 0);
                  if (star_free_mark == 1) {
                      //fsm_state_add_arc(T, maxsigma, maxsigma, U, (T_ptr+T)->finalstart, T == 0 ? 1 : 0);
                      star_free_mark = 0;
                  }
              }
          }
      }
      /* end state */
      fsm_state_end_state();
  } while ((T = next_unmarked()) != -1);

  /* wrapup() */
  nhash_free(table, nhash_tablesize);
  free(set_table);
  free(T_ptr);
  free(temp_move);
  free(e_table);
  free(trans_list_determinize);
  free(trans_array_determinize);

  if (epsilon_symbol != -1)
      e_closure_free();
  free(double_sigma_array);
  free(single_sigma_array);
  free(finals);
  fsm_state_close(net);
  return(net);
277}

279static void init(struct fsm *net) {
  /* A temporary table for handling epsilon closure */
  /* to avoid doubles */

  e_table = calloc(net->statecount,sizeof(int));

  /* Counter for our access tables */

  mainloop = 1;

  /* Temporary table for storing sets and */
  /* passing to hash function */

  /* Table for listing current results of move & e-closure */
  temp_move = malloc((net->statecount + 1) *sizeof(int));

  /* We malloc this much memory to begin with for the new fsm */
  /* Then grow it by the double as needed */

  limit = next_power_of_two(net->linecount);
  fsm_linecount = 0;
  sigma_to_pairs(net);
4
←
Calling 'sigma_to_pairs'→

  /* Optimistically malloc T_ptr array */
  /* We allocate memory for a number of pointers to a set of states */
  /* To handle fast lookup in array */
  /* Optimistically, we choose the initial size to be the number of */
  /* states in the non-deterministic fsm */

  T_last_unmarked = 0;
  T_limit = next_power_of_two(num_states);

  T_ptr = calloc(T_limit,sizeof(struct T_memo));

  /* Stores all sets consecutively in one table */
  /* T_ptr->set_offset and size                 */
  /* are used to retrieve the set               */

  set_table_size = next_power_of_two(num_states);
  set_table = malloc(set_table_size*sizeof(int));
  set_table_offset = 0;

  init_trans_array(net);
322}

324static int trans_sort_cmp(const void *a, const void *b) {
return (((const struct trans_list *)a)->inout - ((const struct trans_list *)b)->inout);
326}

328static void init_trans_array(struct fsm *net) {
  struct trans_list *arrptr;
  struct fsm_state *fsm;
  int i, j, laststate, lastsym, inout, size, state;

  arrptr = trans_list_determinize = malloc(net->linecount * sizeof(struct trans_list));
  trans_array_determinize = calloc(net->statecount, sizeof(struct trans_array));

  laststate = -1;
  fsm = net->states;

  for (i=0, size = 0; (fsm+i)->state_no != -1; i++) {
      state = (fsm+i)->state_no;
      if (state != laststate) {
          if (laststate != -1) {
              (trans_array_determinize+laststate)->size = size;
          }
          (trans_array_determinize+state)->transitions = arrptr;
          size = 0;
      }
      laststate = state;

      if ((fsm+i)->target == -1)
          continue;
      inout = symbol_pair_to_single_symbol((fsm+i)->in, (fsm+i)->out);
      if (inout == epsilon_symbol)
          continue;

      arrptr->inout = inout;
      arrptr->target = (fsm+i)->target;
      arrptr++;
      size++;
  }

  if (laststate != -1) {
      (trans_array_determinize+laststate)->size = size;
  }

  for (i=0; i < net->statecount; i++) {
      arrptr = (trans_array_determinize+i)->transitions;
      size = (trans_array_determinize+i)->size;
      if (size > 1) {
          qsort(arrptr, size, sizeof(struct trans_list), trans_sort_cmp);
          lastsym = -1;
          /* Figure out if we're already deterministic */
          for (j=0; j < size; j++) {
              if ((arrptr+j)->inout == lastsym)
                  deterministic = 0;
              lastsym = (arrptr+j)->inout;
          }
      }
  }
380}

382INLINEinline static int e_closure(int states) {

  int i, set_size;
  struct e_closure_memo *ptr;

  /* e_closure extends the list of states which are reachable */
  /* and appends these to e_table                             */

  if (epsilon_symbol == -1)
      return(set_lookup(temp_move, states));

  if (states == 0)
      return -1;

  mainloop--;

  set_size = states;

  for (i = 0; i < states; i++) {

      /* State number we want to do e-closure on */
      ptr = e_closure_memo + *(temp_move+i);
      if (ptr->target == NULL((void*)0))
          continue;
      ptr_stack_push(ptr);

      while (!(ptr_stack_isempty())) {
          ptr = ptr_stack_pop();
          /* Don't follow if already seen */
          if (*(marktable+ptr->state) == mainloop)
              continue;

          ptr->mark = mainloop;
          *(marktable+ptr->state) = mainloop;
          /* Add to tail of list */
          if (*(e_table+(ptr->state)) != mainloop) {
              *(temp_move+set_size) = ptr->state;
              *(e_table+(ptr->state)) = mainloop;
              set_size++;
          }

          if (ptr->target == NULL((void*)0))
              continue;
          /* Traverse chain */

          for (; ptr != NULL((void*)0) ; ptr = ptr->next) {
              if (ptr->target->mark != mainloop) {
                  /* Push */
                  ptr->target->mark = mainloop;
                  ptr_stack_push(ptr->target);
              }
          }
      }
  }

  mainloop++;
  return(set_lookup(temp_move, set_size));
439}

441INLINEinline static int set_lookup (int *lookup_table, int size) {

/* Look up a set and its corresponding state number */
/* if it doesn't exist from before, assign a state number */

  return(nhash_find_insert(lookup_table, size));

448}

450void add_T_ptr(int setnum, int setsize, unsigned int theset, int fs) {

int i;
if (setnum >= T_limit) {
  T_limit *= 2;
  T_ptr = realloc(T_ptr, sizeof(struct T_memo)*T_limit);
  for (i=setnum; i < T_limit; i++) {
      (T_ptr+i)->size = 0;
  }
}

(T_ptr + setnum)->size = setsize;
(T_ptr + setnum)->set_offset = theset;
(T_ptr + setnum)->finalstart = fs;
int_stack_push(setnum);

466}

468static int initial_e_closure(struct fsm *net) {

  struct fsm_state *fsm;
  int i,j;

  finals = calloc(num_states, sizeof(_Bool));

  num_start_states = 0;
  fsm = net->states;

  /* Create lookups for each state */
  for (i=0,j=0; (fsm+i)->state_no != -1; i++) {
      if ((fsm+i)->final_state) {
          finals[(fsm+i)->state_no] = 1;
      }
      /* Add the start states as the initial set */
      if ((op == SUBSET_TEST_STAR_FREE3) || ((fsm+i)->start_state)) {
          if (*(e_table+((fsm+i)->state_no)) != mainloop) {
              num_start_states++;
              numss = (fsm+i)->state_no;
              *(e_table+((fsm+i)->state_no)) = mainloop;
              *(temp_move+j) = (fsm+i)->state_no;
              j++;
          }
      }
  }
  mainloop++;
  /* Memoize e-closure(u) */
  if (epsilon_symbol != -1) {
      memoize_e_closure(fsm);
  }
  return(e_closure(j));
500}

502static void memoize_e_closure(struct fsm_state *fsm) {

  int i, state, laststate, *redcheck;
  struct e_closure_memo *ptr;

  e_closure_memo = calloc(num_states,sizeof(struct e_closure_memo));
  marktable = calloc(num_states,sizeof(int));
  /* Table for avoiding redundant epsilon arcs in closure */
  redcheck = malloc(num_states*sizeof(int));

  for (i=0; i < num_states; i++) {
      ptr = e_closure_memo+i;
      ptr->state = i;
      ptr->target = NULL((void*)0);
      *(redcheck+i) = -1;
  }

  laststate = -1;

  for (i=0; ;i++) {

      state = (fsm+i)->state_no;

      if (state != laststate) {
          if (!int_stack_isempty()) {
              deterministic = 0;
              ptr = e_closure_memo+laststate;
              ptr->target = e_closure_memo+int_stack_pop();
              while (!int_stack_isempty()) {
                  ptr->next = malloc(sizeof(struct e_closure_memo));
                  ptr->next->state = laststate;
                  ptr->next->target = e_closure_memo+int_stack_pop();
                  ptr->next->next = NULL((void*)0);
                  ptr = ptr->next;
              }
          }
      }
      if (state == -1) {
          break;
      }
      if ((fsm+i)->target == -1) {
          continue;
      }
      /* Check if we have a redundant epsilon arc */
      if ((fsm+i)->in == EPSILON0 && (fsm+i)->out == EPSILON0) {
          if (*(redcheck+((fsm+i)->target)) != (fsm+i)->state_no) {
              if ((fsm+i)->target != (fsm+i)->state_no) {
                  int_stack_push((fsm+i)->target);
                  *(redcheck+((fsm+i)->target)) = (fsm+i)->state_no;
              }
          }
          laststate = state;
      }
  }
  free(redcheck);
557}

559static int next_unmarked(void) {
  if ((int_stack_isempty()))
      return -1;
  return(int_stack_pop());

  if ((T_limit <= T_last_unmarked + 1) || (T_ptr+T_last_unmarked+1)->size == 0) {
      return -1;
  } else {
      T_last_unmarked++;
      return(T_last_unmarked);
  }
570}

572static void single_symbol_to_symbol_pair(int symbol, int *symbol_in, int *symbol_out) {

*symbol_in = *(single_sigma_array+(symbol*2));
*symbol_out = *(single_sigma_array+(symbol*2+1));

577}

579static int symbol_pair_to_single_symbol(int in, int out) {
return(*(double_sigma_array+maxsigma*in+out));
581}

583static void sigma_to_pairs(struct fsm *net) {

int i, j, x, y, z, next_x = 0;
struct fsm_state *fsm;

fsm = net->states;

epsilon_symbol = -1;
maxsigma = sigma_max(net->sigma);
maxsigma++;

single_sigma_array = malloc(2*maxsigma*maxsigma*sizeof(int));
double_sigma_array = malloc(maxsigma*maxsigma*sizeof(int));
5
←
Storing uninitialized value→

for (i=0; i < maxsigma; i++) {
6
←
Assuming 'i' is < 'maxsigma'→
7
←
Loop condition is true.  Entering loop body→
11
←
Loop condition is false. Execution continues on line 617→
  for (j=0; j7.1
'j' is < 'maxsigma'
< maxsigma; j++) {
8
←
Loop condition is true.  Entering loop body→
9
←
Assuming 'j' is >= 'maxsigma'→
10
←
Loop condition is false. Execution continues on line 597→
    *(double_sigma_array+maxsigma*i+j) = -1;
  }
}

/* f(x) -> y,z sigma pair */
/* f(y,z) -> x simple entry */
/* if exists f(n) <-> EPSILON, EPSILON, save n */
/* symbol(x) x>=1 */

/* Forward mapping: */
/* *(double_sigma_array+maxsigma*in+out) */

/* Backmapping: */
/* *(single_sigma_array+(symbol*2) = in(symbol) */
/* *(single_sigma_array+(symbol*2+1) = out(symbol) */

/* Table for checking whether a state is final */

x = 0;
net->arity = 1;
for (i=0; (fsm+i)->state_no != -1; i++) {
12
←
Assuming the condition is true→
13
←
Loop condition is true.  Entering loop body→
  y = (fsm+i)->in;
  z = (fsm+i)->out;
  if ((y == -1) || (z == -1))
14
←
Assuming the condition is false→
15
←
Assuming the condition is false→
    continue;
  if (y != z || y == UNKNOWN1 || z == UNKNOWN1)
16
←
Assuming 'y' is equal to 'z'→
17
←
Assuming 'y' is equal to UNKNOWN→
      net->arity = 2;
  if (*(double_sigma_array+maxsigma*y+z) == -1) {
18
←
The left operand of '==' is a garbage value
    *(double_sigma_array+maxsigma*y+z) = x;
    *(single_sigma_array+next_x) = y;
    next_x++;
    *(single_sigma_array+next_x) = z;
    next_x++;
    if (y == EPSILON0 && z == EPSILON0) {
epsilon_symbol = x;
    }
    x++;
  }
}
num_symbols = x;
639}


642/* Functions for hashing n integers */
643/* with permutations hashing to the same value */
644/* necessary for subset construction */

646static int nhash_find_insert(int *set, int setsize) {
  int j, found, *currlist;
  struct nhash_list *tableptr;
  unsigned int hashval;

  hashval = hashf(set, setsize);
  if ((table+hashval)->size == 0) {
      return(nhash_insert(hashval, set, setsize));
  } else {
      for (tableptr=(table+hashval); tableptr != NULL((void*)0); tableptr = tableptr->next) {
          if ((tableptr)->size != setsize) {
              continue;
          } else {
              /* Compare the list at hashval position */
              /* to the current set by looking at etable */
              /* entries */
              for (j=0, found = 1, currlist= set_table+tableptr->set_offset; j < setsize; j++) {
                  if (*(e_table+(*(currlist+j))) != (mainloop-1)) {
                      found = 0;
                      break;
                  }
              }
              if (op == SUBSET_TEST_STAR_FREE3 && found == 1) {
                  for (j=0, currlist= set_table+tableptr->set_offset; j < setsize; j++) {
                      if (*(set+j) != *(currlist+j)) {
                          /* Set mark */
                          star_free_mark = 1;
                      }
                  }
              }
              if (found == 1) {
                  return(tableptr->setnum);
              }
          }
      }

      if (nhash_load / NHASH_LOAD_LIMIT2 > nhash_tablesize) {
          nhash_rebuild_table();
          hashval = hashf(set, setsize);
      }
      return(nhash_insert(hashval, set, setsize));
  }
688}

690INLINEinline static int hashf(int *set, int setsize) {
int i;
unsigned int hashval, sum = 0;
hashval = 6703271;
for (i = 0; i < setsize; i++) {
    hashval = (unsigned int) (*(set+i) + 1103 * setsize) * hashval;
    sum += *(set+i) + i;
}
hashval = hashval + sum * 31;
hashval = (hashval % nhash_tablesize);
return hashval;
701}

703static unsigned int move_set(int *set, int setsize) {
  unsigned int old_offset;
  if (set_table_offset + setsize >= set_table_size) {
      while (set_table_offset + setsize >= set_table_size) {
          set_table_size *= 2;
      }
      set_table = realloc(set_table, set_table_size * sizeof(int));
  }
  memcpy(set_table+set_table_offset, set, setsize * sizeof(int));
  old_offset = set_table_offset;
  set_table_offset += setsize;
  return(old_offset);
715}

717static int nhash_insert(int hashval, int *set, int setsize) {
struct nhash_list *tableptr;
int i, fs = 0;

current_setnum++;
tableptr = table+hashval;

nhash_load++;
for (i = 0; i < setsize; i++) {
    if (finals[*(set+i)])
        fs = 1;
}
if (tableptr->size == 0) {

    tableptr->set_offset = move_set(set, setsize);
    tableptr->size = setsize;
    tableptr->setnum = current_setnum;

    add_T_ptr(current_setnum, setsize, tableptr->set_offset, fs);
    return(current_setnum);
}

tableptr = malloc(sizeof(struct nhash_list));
tableptr->next = (table+hashval)->next;
(table+hashval)->next = tableptr;
tableptr->setnum = current_setnum;
tableptr->size = setsize;
tableptr->set_offset = move_set(set, setsize);

add_T_ptr(current_setnum, setsize, tableptr->set_offset, fs);
return(current_setnum);
748}

750static void nhash_rebuild_table () {
  int i, oldsize;
  struct nhash_list *oldtable, *tableptr, *ntableptr, *newptr;
  unsigned int hashval;

  oldtable = table;
  oldsize = nhash_tablesize;

  nhash_load = 0;
  for (i=0; primes[i] < nhash_tablesize; i++) { }
  nhash_tablesize = primes[(i+1)];

  table = calloc(nhash_tablesize,sizeof(struct nhash_list));
  for (i=0; i < oldsize;i++) {
      if ((oldtable+i)->size == 0) {
          continue;
      }
      tableptr = oldtable+i;
      for ( ; tableptr != NULL((void*)0); (tableptr = tableptr->next)) {
          /* rehash */
          hashval = hashf(set_table+tableptr->set_offset,tableptr->size);
          ntableptr = table+hashval;
          if (ntableptr->size == 0) {
              nhash_load++;
              ntableptr->size = tableptr->size;
              ntableptr->set_offset = tableptr->set_offset;
              ntableptr->setnum = tableptr->setnum;
              ntableptr->next = NULL((void*)0);
          } else {
              newptr = malloc(sizeof(struct nhash_list));
              newptr->next = ntableptr->next;
              ntableptr->next = newptr;
              newptr->setnum = tableptr->setnum;
              newptr->size = tableptr->size;
              newptr->set_offset = tableptr->set_offset;
          }
      }
  }
  nhash_free(oldtable, oldsize);
789}

791static void nhash_init (int initial_size) {

int i;

for (i=0; primes[i] < initial_size; i++) { }
nhash_load = 0;
nhash_tablesize = primes[i];
table = calloc(nhash_tablesize , sizeof(struct nhash_list));
current_setnum = -1;
800}
801static void e_closure_free() {
  int i;
  struct e_closure_memo *eptr, *eprev;
  free(marktable);
  for (i=0;i < num_states; i++) {
      eptr = (e_closure_memo+i)->next;
      for (eprev = NULL((void*)0); eptr != NULL((void*)0); ) {
          eprev = eptr;
          eptr = eptr->next;
          free(eprev);
      }

  }
  free(e_closure_memo);
815}

817static void nhash_free(struct nhash_list *nptr, int size) {
  struct nhash_list *nptr2, *nnext;
  int i;
  for (i=0; i < size; i++) {
      for (nptr2 = (nptr+i)->next; nptr2 != NULL((void*)0); nptr2 = nnext) {
          nnext = nptr2->next;
          free(nptr2);
      }
  }
  free(nptr);
827}