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