dfa/states.c

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