76cf6cffbf9e6ef97110a6e3d80909c52eb6744c
[idzebra-moved-to-github.git] / 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 }