Happy new year.
[idzebra-moved-to-github.git] / 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