dfa/states.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: states.c,v $
   7  * Revision 1.5  1996-10-29 13:57:31  adam
   8  * Include of zebrautl.h instead of alexutil.h.
   9  *
  10  * Revision 1.4  1995/09/04 12:33:28  adam
  11  * Various cleanup. YAZ util used instead.
  12  *
  13  * Revision 1.3  1995/01/25  11:30:51  adam
  14  * Simple error reporting when parsing regular expressions.
  15  * Memory usage reduced.
  16  *
  17  * Revision 1.2  1995/01/24  16:00:23  adam
  18  * Added -ansi to CFLAGS.
  19  * Some changes to the dfa module.
  20  *
  21  * Revision 1.1  1994/09/26  10:16:58  adam
  22  * First version of dfa module in alex. This version uses yacc to parse
  23  * regular expressions. This should be hand-made instead.
  24  *
  25  */
  26 #include <stdio.h>
  27 #include <assert.h>
  28
  29 #include <stdlib.h>
  30 #include <string.h>
  31
  32 #include "dfap.h"
  33 #include "imalloc.h"
  34
  35 #define DFA_CHUNK 40
  36 #define TRAN_CHUNK 100
  37
  38 int init_DFA_states (struct DFA_states **dfasp, SetType st, int hash)
  39 {
  40     struct DFA_states *dfas;
  41     struct DFA_trans *tm;
  42     int i;
  43
  44     dfas = (struct DFA_states *) imalloc (sizeof(struct DFA_states));
  45     assert (dfas);
  46     dfas->hasharray = (struct DFA_state **)
  47         imalloc (sizeof(struct DFA_state*) * hash);
  48     assert (dfas->hasharray);
  49     *dfasp = dfas;
  50     dfas->freelist = dfas->unmarked = dfas->marked = NULL;
  51     dfas->statemem = NULL;
  52     dfas->hash = hash;
  53     dfas->st = st;
  54     dfas->no = 0;
  55
  56     dfas->transmem = tm = (struct DFA_trans *)
  57         imalloc (sizeof(struct DFA_trans));
  58     assert (tm);
  59     tm->next = NULL;
  60     tm->size = TRAN_CHUNK;
  61     tm->ptr = 0;
  62     tm->tran_block = (struct DFA_tran *)
  63         imalloc (sizeof(struct DFA_tran) * tm->size);
  64     assert (tm->tran_block);
  65
  66     dfas->sortarray = NULL;
  67     for (i=0; i<dfas->hash; i++)
  68         dfas->hasharray[i] = NULL;
  69     return 0;
  70 }
  71
  72 int rm_DFA_states (struct DFA_states **dfasp)
  73 {
  74     struct DFA_states *dfas = *dfasp;
  75     DFA_stateb *sm, *sm1;
  76     struct DFA_trans  *tm, *tm1;
  77
  78     assert (dfas);
  79     if (dfas->hasharray)
  80         ifree (dfas->hasharray);
  81     ifree (dfas->sortarray);
  82
  83     for (tm=dfas->transmem; tm; tm=tm1)
  84     {
  85         ifree (tm->tran_block);
  86         tm1 = tm->next;
  87         ifree (tm);
  88     }
  89     for (sm=dfas->statemem; sm; sm=sm1)
  90     {
  91         ifree (sm->state_block);
  92         sm1 = sm->next;
  93         ifree (sm);
  94     }
  95     ifree (dfas);
  96     *dfasp = NULL;
  97     return 0;
  98 }
  99
 100 int add_DFA_state (struct DFA_states *dfas, Set *s, struct DFA_state **sp)
 101 {
 102     int i;
 103     struct DFA_state *si, **sip;
 104     DFA_stateb *sb;
 105
 106     assert (dfas);
 107     assert (*s);
 108     assert (dfas->hasharray);
 109     sip = dfas->hasharray + (hash_Set (dfas->st, *s) % dfas->hash);
 110     for (si = *sip; si; si=si->link)
 111         if (eq_Set (dfas->st, si->set, *s))
 112         {
 113             *sp = si;
 114             *s = rm_Set (dfas->st, *s);
 115             return 0;
 116         }
 117     if (!dfas->freelist)
 118     {
 119         sb = (DFA_stateb *) imalloc (sizeof(*sb));
 120         sb->next = dfas->statemem;
 121         dfas->statemem = sb;
 122         sb->state_block = si = dfas->freelist =
 123             (struct DFA_state *) imalloc (sizeof(struct DFA_state)*DFA_CHUNK);
 124         for (i = 0; i<DFA_CHUNK-1; i++, si++)
 125             si->next = si+1;
 126         si->next = NULL;
 127     }
 128
 129     si = dfas->freelist;
 130     dfas->freelist = si->next;
 131
 132     si->next = dfas->unmarked;
 133     dfas->unmarked = si;
 134
 135     si->link = *sip;
 136     *sip = si;
 137
 138     si->no = (dfas->no)++;
 139     si->tran_no = 0;
 140     si->set = *s;
 141     *s = NULL;
 142     *sp = si;
 143     return 1;
 144 }
 145
 146 void add_DFA_tran (struct DFA_states *dfas, struct DFA_state *s,
 147                    int ch0, int ch1, int to)
 148 {
 149     struct DFA_trans *tm;
 150     struct DFA_tran *t;
 151
 152     tm = dfas->transmem;
 153     if (tm->ptr == tm->size)
 154     {
 155         tm = (struct DFA_trans *) imalloc (sizeof(struct DFA_trans));
 156         assert (tm);
 157         tm->next = dfas->transmem;
 158         dfas->transmem = tm;
 159         tm->size = s->tran_no >= TRAN_CHUNK ? s->tran_no+8 : TRAN_CHUNK;
 160         tm->tran_block = (struct DFA_tran *)
 161             imalloc (sizeof(struct DFA_tran) * tm->size);
 162         assert (tm->tran_block);
 163         if (s->tran_no)
 164             memcpy (tm->tran_block, s->trans,
 165                     s->tran_no*sizeof (struct DFA_tran));
 166         tm->ptr = s->tran_no;
 167         s->trans = tm->tran_block;
 168     }
 169     s->tran_no++;
 170     t = tm->tran_block + tm->ptr++;
 171     t->ch[0] = ch0;
 172     t->ch[1] = ch1;
 173     t->to = to;
 174 }
 175
 176 struct DFA_state *get_DFA_state (struct DFA_states *dfas)
 177 {
 178     struct DFA_state *si;
 179     assert (dfas);
 180     if (!(si = dfas->unmarked))
 181         return NULL;
 182     dfas->unmarked = si->next;
 183     si->next = dfas->marked;
 184     dfas->marked = si;
 185     si->trans = dfas->transmem->tran_block + dfas->transmem->ptr;
 186
 187     return si;
 188 }
 189
 190 void sort_DFA_states (struct DFA_states *dfas)
 191 {
 192     struct DFA_state *s;
 193     assert (dfas);
 194     dfas->sortarray = (struct DFA_state **)
 195         imalloc (sizeof(struct DFA_state *)*dfas->no);
 196     for (s = dfas->marked; s; s=s->next)
 197         dfas->sortarray[s->no] = s;
 198     ifree (dfas->hasharray);
 199     dfas->hasharray = NULL;
 200 }