dfa/states.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) 1994-2011 Index Data
   3
   4 Zebra is free software; you can redistribute it and/or modify it under
   5 the terms of the GNU General Public License as published by the Free
   6 Software Foundation; either version 2, or (at your option) any later
   7 version.
   8
   9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12 for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 */
  19
  20
  21 #include <stdio.h>
  22 #include <assert.h>
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #include "dfap.h"
  28 #include "imalloc.h"
  29
  30 #define DFA_CHUNK 40
  31 #define TRAN_CHUNK 100
  32
  33 int init_DFA_states (struct DFA_states **dfasp, DFASetType st, int hash)
  34 {
  35     struct DFA_states *dfas;
  36     struct DFA_trans *tm;
  37     int i;
  38
  39     dfas = (struct DFA_states *) imalloc (sizeof(struct DFA_states));
  40     assert (dfas);
  41     dfas->hasharray = (struct DFA_state **)
  42         imalloc (sizeof(struct DFA_state*) * hash);
  43     assert (dfas->hasharray);
  44     *dfasp = dfas;
  45     dfas->freelist = dfas->unmarked = dfas->marked = NULL;
  46     dfas->statemem = NULL;
  47     dfas->hash = hash;
  48     dfas->st = st;
  49     dfas->no = 0;
  50
  51     dfas->transmem = tm = (struct DFA_trans *)
  52         imalloc (sizeof(struct DFA_trans));
  53     assert (tm);
  54     tm->next = NULL;
  55     tm->size = TRAN_CHUNK;
  56     tm->ptr = 0;
  57     tm->tran_block = (struct DFA_tran *)
  58         imalloc (sizeof(struct DFA_tran) * tm->size);
  59     assert (tm->tran_block);
  60
  61     dfas->sortarray = NULL;
  62     for (i=0; i<dfas->hash; i++)
  63         dfas->hasharray[i] = NULL;
  64     return 0;
  65 }
  66
  67 int rm_DFA_states (struct DFA_states **dfasp)
  68 {
  69     struct DFA_states *dfas = *dfasp;
  70     DFA_stateb *sm, *sm1;
  71     struct DFA_trans  *tm, *tm1;
  72
  73     assert (dfas);
  74     if (dfas->hasharray)
  75         ifree (dfas->hasharray);
  76     ifree (dfas->sortarray);
  77
  78     for (tm=dfas->transmem; tm; tm=tm1)
  79     {
  80         ifree (tm->tran_block);
  81         tm1 = tm->next;
  82         ifree (tm);
  83     }
  84     for (sm=dfas->statemem; sm; sm=sm1)
  85     {
  86         ifree (sm->state_block);
  87         sm1 = sm->next;
  88         ifree (sm);
  89     }
  90     ifree (dfas);
  91     *dfasp = NULL;
  92     return 0;
  93 }
  94
  95 int add_DFA_state (struct DFA_states *dfas, DFASet *s, struct DFA_state **sp)
  96 {
  97     int i;
  98     struct DFA_state *si, **sip;
  99     DFA_stateb *sb;
 100
 101     assert (dfas);
 102     assert (*s);
 103     assert (dfas->hasharray);
 104     sip = dfas->hasharray + (hash_DFASet (dfas->st, *s) % dfas->hash);
 105     for (si = *sip; si; si=si->link)
 106         if (eq_DFASet (dfas->st, si->set, *s))
 107         {
 108             *sp = si;
 109             *s = rm_DFASet (dfas->st, *s);
 110             return 0;
 111         }
 112     if (!dfas->freelist)
 113     {
 114         sb = (DFA_stateb *) imalloc (sizeof(*sb));
 115         sb->next = dfas->statemem;
 116         dfas->statemem = sb;
 117         sb->state_block = si = dfas->freelist =
 118             (struct DFA_state *) imalloc (sizeof(struct DFA_state)*DFA_CHUNK);
 119         for (i = 0; i<DFA_CHUNK-1; i++, si++)
 120             si->next = si+1;
 121         si->next = NULL;
 122     }
 123
 124     si = dfas->freelist;
 125     dfas->freelist = si->next;
 126
 127     si->next = dfas->unmarked;
 128     dfas->unmarked = si;
 129
 130     si->link = *sip;
 131     *sip = si;
 132
 133     si->no = (dfas->no)++;
 134     si->tran_no = 0;
 135     si->set = *s;
 136     *s = NULL;
 137     *sp = si;
 138     return 1;
 139 }
 140
 141 void add_DFA_tran (struct DFA_states *dfas, struct DFA_state *s,
 142                    int ch0, int ch1, int to)
 143 {
 144     struct DFA_trans *tm;
 145     struct DFA_tran *t;
 146
 147     tm = dfas->transmem;
 148     if (tm->ptr == tm->size)
 149     {
 150         tm = (struct DFA_trans *) imalloc (sizeof(struct DFA_trans));
 151         assert (tm);
 152         tm->next = dfas->transmem;
 153         dfas->transmem = tm;
 154         tm->size = s->tran_no >= TRAN_CHUNK ? s->tran_no+8 : TRAN_CHUNK;
 155         tm->tran_block = (struct DFA_tran *)
 156             imalloc (sizeof(struct DFA_tran) * tm->size);
 157         assert (tm->tran_block);
 158         if (s->tran_no)
 159             memcpy (tm->tran_block, s->trans,
 160                     s->tran_no*sizeof (struct DFA_tran));
 161         tm->ptr = s->tran_no;
 162         s->trans = tm->tran_block;
 163     }
 164     s->tran_no++;
 165     t = tm->tran_block + tm->ptr++;
 166     t->ch[0] = ch0;
 167     t->ch[1] = ch1;
 168     t->to = to;
 169 }
 170
 171 struct DFA_state *get_DFA_state (struct DFA_states *dfas)
 172 {
 173     struct DFA_state *si;
 174     assert (dfas);
 175     if (!(si = dfas->unmarked))
 176         return NULL;
 177     dfas->unmarked = si->next;
 178     si->next = dfas->marked;
 179     dfas->marked = si;
 180     si->trans = dfas->transmem->tran_block + dfas->transmem->ptr;
 181
 182     return si;
 183 }
 184
 185 void sort_DFA_states (struct DFA_states *dfas)
 186 {
 187     struct DFA_state *s;
 188     assert (dfas);
 189     dfas->sortarray = (struct DFA_state **)
 190         imalloc (sizeof(struct DFA_state *)*dfas->no);
 191     for (s = dfas->marked; s; s=s->next)
 192         dfas->sortarray[s->no] = s;
 193     ifree (dfas->hasharray);
 194     dfas->hasharray = NULL;
 195 }
 196 /*
 197  * Local variables:
 198  * c-basic-offset: 4
 199  * c-file-style: "Stroustrup"
 200  * indent-tabs-mode: nil
 201  * End:
 202  * vim: shiftwidth=4 tabstop=8 expandtab
 203  */
 204