IDZEBRA  2.2.7
states.c
Go to the documentation of this file.
1 /* This file is part of the Zebra server.
2  Copyright (C) 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 #if HAVE_CONFIG_H
22 #include <config.h>
23 #endif
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 }
199 /*
200  * Local variables:
201  * c-basic-offset: 4
202  * c-file-style: "Stroustrup"
203  * indent-tabs-mode: nil
204  * End:
205  * vim: shiftwidth=4 tabstop=8 expandtab
206  */
207 
int eq_DFASet(DFASetType s, DFASet s1, DFASet s2)
Definition: set.c:249
DFASet rm_DFASet(DFASetType st, DFASet s)
Definition: set.c:115
unsigned hash_DFASet(DFASetType st, DFASet s)
Definition: set.c:238
void ifree(void *p)
Definition: imalloc.c:93
void * imalloc(size_t size)
Definition: imalloc.c:43
void sort_DFA_states(struct DFA_states *dfas)
Definition: states.c:188
int rm_DFA_states(struct DFA_states **dfasp)
Definition: states.c:70
struct DFA_state * get_DFA_state(struct DFA_states *dfas)
Definition: states.c:174
#define DFA_CHUNK
Definition: states.c:33
void add_DFA_tran(struct DFA_states *dfas, struct DFA_state *s, int ch0, int ch1, int to)
Definition: states.c:144
int add_DFA_state(struct DFA_states *dfas, DFASet *s, struct DFA_state **sp)
Definition: states.c:98
#define TRAN_CHUNK
Definition: states.c:34
int init_DFA_states(struct DFA_states **dfasp, DFASetType st, int hash)
Definition: states.c:36
static struct strmap_entry ** hash(zebra_strmap_t st, const char *name)
Definition: strmap.c:70
Definition: dfa.h:42
struct DFA_state * link
Definition: dfa.h:44
short tran_no
Definition: dfa.h:48
DFASet set
Definition: dfa.h:46
struct DFA_tran * trans
Definition: dfa.h:45
struct DFA_state * next
Definition: dfa.h:43
short no
Definition: dfa.h:47
struct DFA_state * state_block
Definition: dfap.h:62
struct DFA_stateb_ * next
Definition: dfap.h:61
struct DFA_state * unmarked
Definition: dfap.h:67
int no
Definition: dfap.h:70
struct DFA_trans * transmem
Definition: dfap.h:75
struct DFA_state * freelist
Definition: dfap.h:66
struct DFA_state ** hasharray
Definition: dfap.h:73
DFA_stateb * statemem
Definition: dfap.h:69
struct DFA_state ** sortarray
Definition: dfap.h:74
struct DFA_state * marked
Definition: dfap.h:68
int hash
Definition: dfap.h:72
DFASetType st
Definition: dfap.h:71
Definition: dfa.h:30
unsigned short to
Definition: dfa.h:32
unsigned char ch[2]
Definition: dfa.h:31
Definition: dfa.h:35
struct DFA_trans * next
Definition: dfa.h:36
struct DFA_tran * tran_block
Definition: dfa.h:37
int ptr
Definition: dfa.h:38
int size
Definition: dfa.h:39