dfa/states.c

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