TaPAS  0.2
sataf-inline.h
Go to the documentation of this file.
1 /*
2  * sataf-inline.h -- add a comment about this file
3  *
4  * This file is a part of the SATAF library.
5  *
6  * Copyright (C) 2010 CNRS UMR 5800 & Universit√© Bordeaux I (see AUTHORS file).
7  *
8  * This program is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation; either version 2 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software
20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21  * 02110-1301 USA
22  */
23 
29 #ifndef __SATAF_INLINE_H__
30 # define __SATAF_INLINE_H__
31 
32 # include <ccl/ccl-assert.h>
33 # include <sataf/sataf.h>
34 
35 BEGIN_C_DECLS
36 
37 struct sataf_mao_st
38 {
39  const sataf_mao_methods *methods;
40  uint32_t refcount;
41 };
42 
43 struct sataf_msa_st
44 {
45  uint32_t refcount;
46  sataf_sa *A;
47  uint32_t initial;
48  sataf_msa *next;
49 };
50 
51 struct sataf_ea_st
52 {
53  sataf_ea *next;
54  uint32_t refcount;
55  uint32_t alphabet_size;
56  uint32_t nb_local_states;
57  uint32_t nb_exit_states;
58  uint8_t *is_final;
59  uint32_t successor[1];
60 };
61 
62 struct sataf_sa_st
63 {
64  sataf_sa *next;
65  uint32_t refcount;
66  sataf_ea *automaton;
67  uint32_t depth;
68  sataf_msa *bind[1];
69 };
70 
71 
72  /* --------------- */
73 
74 static inline sataf_mao *
76 {
77  ccl_pre (a != NULL);
78  a->refcount++;
79  return a;
80 }
81 
82  /* --------------- */
83 
84 extern void
85 sataf_mao_destroy (sataf_mao *a);
86 
87 static inline void
89 {
90  ccl_pre (a != NULL);
91  --a->refcount;
92  if (a->refcount == 0)
93  sataf_mao_destroy (a);
94 }
95 
96  /* --------------- */
97 
98 static inline const char *
100 {
101  ccl_pre (self != NULL);
102  return self->methods->type;
103 }
104 
105  /* --------------- */
106 
107 static inline uint32_t
109 {
110  return index << 1;
111 }
112 
113  /* --------------- */
114 
115 static inline uint32_t
116 sataf_ea_encode_succ_as_exit_state (uint32_t index)
117 {
118  return 1 + (index << 1);
119 }
120 
121  /* --------------- */
122 
123 static inline uint32_t
124 sataf_ea_decode_succ_state (uint32_t index)
125 {
126  return index >> 1;
127 }
128 
129  /* --------------- */
130 
131 static inline int
132 sataf_ea_is_exit_state (uint32_t successor)
133 {
134  return (successor & 0x1) != 0;
135 }
136 
137  /* --------------- */
138 
139 static inline int
140 sataf_ea_is_local_state (uint32_t successor)
141 {
142  return ! sataf_ea_is_exit_state (successor);
143 }
144 
145  /* --------------- */
146 
147 static inline uint32_t
149 {
150  ccl_pre (ea != NULL);
151  return ea->alphabet_size;
152 }
153 
154  /* --------------- */
155 
156 static inline uint32_t
158 {
159  ccl_pre (ea != NULL);
160  return ea->nb_local_states;
161 }
162 
163  /* --------------- */
164 
165 static inline uint32_t
167 {
168  ccl_pre (ea != NULL);
169  return ea->nb_exit_states;
170 }
171 
172  /* --------------- */
173 
174 static inline int
175 sataf_ea_is_final (sataf_ea *ea, uint32_t s)
176 {
178  return ea->is_final[s];
179 }
180 
181  /* --------------- */
182 
183 static inline uint32_t
184 sataf_ea_get_successor (sataf_ea *ea, uint32_t state, uint32_t a)
185 {
186  ccl_pre (ea != NULL);
187  ccl_pre (state < ea->nb_local_states);
188  ccl_pre (a < ea->alphabet_size);
189 
190  return ea->successor[ea->alphabet_size * state + a];
191 }
192 
193  /* --------------- */
194 
195 static inline int
197 {
198  return sataf_ea_is_zero_or_one (ea) && !ea->is_final[0];
199 }
200 
201  /* --------------- */
202 
203 static inline int
205 {
206  return sataf_ea_is_zero_or_one (ea) && (ea)->is_final[0];
207 }
208 
209  /* --------------- */
210 
211 static inline int
213 {
214  ccl_pre (ea != NULL);
215  return ea->nb_local_states == 1 && ea->nb_exit_states == 0;
216 }
217 
218  /* --------------- */
219 
220 static inline void
221 sataf_ea_set_final (sataf_ea *ea, unsigned int s, int is_final)
222 {
223  ccl_pre (ea != NULL);
224  ccl_pre (s < ea->nb_local_states);
225 
226  ea->is_final[s] = is_final?1:0;
227 }
228 
229  /* --------------- */
230 
231 static inline sataf_sa *
233 {
234  ccl_pre (sa != NULL);
235  sa->refcount++;
236  return sa;
237 }
238 
239  /* --------------- */
240 
241 
242 extern void
243 sataf_sa_destroy (sataf_sa *sa);
244 
245 static inline void
247 {
248  ccl_pre (sa != NULL);
249  ccl_pre (sa->refcount > 0);
250  sa->refcount--;
251  if (sa->refcount == 0)
252  sataf_sa_destroy (sa);
253 }
254 
255  /* --------------- */
256 
257 static inline uint32_t
259 {
260  ccl_pre (sa != NULL);
261  return sataf_ea_get_alphabet_size (sa->automaton);
262 }
263 
264  /* --------------- */
265 
266 static inline int
268 {
269  ccl_pre (sa != NULL);
270  return sataf_ea_is_zero (sa->automaton);
271 }
272 
273  /* --------------- */
274 
275 static inline int
277 {
278  ccl_pre (sa != NULL);
279  return sataf_ea_is_one (sa->automaton);
280 }
281 
282  /* --------------- */
283 
284 static inline int
286 {
287  ccl_pre (sa != NULL);
288  return sataf_ea_is_zero_or_one (sa->automaton);
289 }
290 
291  /* --------------- */
292 
293 static inline uint32_t
295 {
296  ccl_pre (msa != NULL);
297  return sataf_sa_get_alphabet_size (msa->A);
298 }
299 
300  /* --------------- */
301 
302 static inline sataf_msa *
304 {
305  ccl_pre (msa != NULL);
306  msa->refcount++;
307  return msa;
308 }
309 
310  /* --------------- */
311 
312 extern void
313 sataf_msa_destroy (sataf_msa *msa);
314 
315 
316 static inline void
318 {
319  ccl_pre (msa != NULL);
320  ccl_pre (msa->refcount > 0);
321  msa->refcount--;
322  if (msa->refcount == 0)
323  sataf_msa_destroy (msa);
324 }
325 
326  /* --------------- */
327 
328 static inline int
330 {
331  ccl_pre (msa != NULL);
332 
333  return sataf_ea_is_final (msa->A->automaton, msa->initial);
334 }
335 
336 
337  /* --------------- */
338 
339 static inline uint32_t
341 {
342  ccl_pre (msa != NULL);
343  return msa->initial;
344 }
345 
346  /* --------------- */
347 
348 static inline sataf_sa *
350 {
352 }
353 
354  /* --------------- */
355 
356 static inline sataf_sa *
358 {
359  ccl_pre (msa != NULL);
360  return msa->A;
361 }
362 
363  /* --------------- */
364 
365 static inline sataf_msa *
367 {
368  return sataf_msa_compute_with_transformer (A, NULL);
369 }
370 
371  /* --------------- */
372 
373 static inline int
375 {
376  ccl_pre (msa != NULL);
377 
378  return sataf_sa_is_zero (msa->A);
379 }
380 
381  /* --------------- */
382 
383 static inline int
385 {
386  ccl_pre (msa != NULL);
387 
388  return sataf_sa_is_one (msa->A);
389 }
390 
391  /* --------------- */
392 
393 static inline int
395 {
396  ccl_pre (msa != NULL);
397 
398  return sataf_sa_is_zero_or_one (msa->A);
399 }
400 
401  /* --------------- */
402 
403 
404 END_C_DECLS
405 
406 #endif /* ! __SATAF_INLINE_H__ */
static int sataf_sa_is_one(sataf_sa *sa)
Return if sa is the shared automaton accepting any word.
static uint32_t sataf_ea_get_nb_states(sataf_ea *ea)
Return the number of local states of ea.
static int sataf_sa_is_zero(sataf_sa *sa)
Return if sa is the shared automaton accepting no word.
Structure gathering the methods applied to a Marked Automaton Object.
Definition: sataf.h:109
static uint32_t sataf_sa_get_alphabet_size(sataf_sa *sa)
Return the size of the alphabet.
struct sataf_ea_st sataf_ea
Type for the data structure encoding Exit Automata.
Definition: sataf.h:99
static uint32_t sataf_msa_get_alphabet_size(sataf_msa *msa)
Return the size of the alphabet.
static uint32_t sataf_msa_get_state(sataf_msa *msa)
Return the marked state defining msa.
static int sataf_msa_is_final(sataf_msa *msa)
Return if msa accepts the empty word.
static int sataf_ea_is_one(sataf_ea *ea)
Check if ea accepts any word.
static const char * sataf_mao_get_type(sataf_mao *self)
Return the type of the MAO self.
static int sataf_ea_is_zero(sataf_ea *ea)
Check if ea accepts nothing.
static int sataf_msa_is_one(sataf_msa *msa)
Check if msa is the one recognizing everything.
static sataf_mao * sataf_mao_add_reference(sataf_mao *a)
Increments the number of references to this MAP.
#define ccl_pre(_cond_)
Checks if the pre-condition cond is satisfied.
Definition: ccl-assert.h:57
static uint32_t sataf_ea_encode_succ_as_exit_state(uint32_t index)
Encode the successor state index as an exit state.
static int sataf_ea_is_exit_state(uint32_t successor)
Check if the given successor corresponds to an exit state or not.
static sataf_msa * sataf_msa_add_reference(sataf_msa *msa)
Increment the counter of references of msa.
static sataf_msa * sataf_msa_compute(sataf_mao *A)
Minimize, canonicalize and share the given MAO A.
struct sataf_mao_st sataf_mao
Type of a Marked Automaton Object (MAO).
Definition: sataf.h:65
static sataf_sa * sataf_msa_get_sa(sataf_msa *msa)
Return the shared automaton defining msa.
static int sataf_ea_is_final(sataf_ea *ea, uint32_t s)
Return a non null value is the local state s of ea is accepting or not.
static void sataf_ea_set_final(sataf_ea *ea, uint32_t s, int is_final)
Change the acceptance condition for the state s.
static int sataf_ea_is_local_state(uint32_t successor)
Check if the given successor corresponds to a local state or not.
static int sataf_msa_is_zero_or_one(sataf_msa *msa)
Check if msa is one of the two elementary MSAs i.e. either the one recognizing everything or the one ...
sataf_msa * sataf_msa_compute_with_transformer(sataf_mao *A, sataf_sa_transformer *T)
Minimize, canonicalize and share the given MAO A.
static int sataf_msa_is_zero(sataf_msa *msa)
Check if msa is the one recognizing nothing.
static uint32_t sataf_ea_get_alphabet_size(sataf_ea *ea)
Return the size of this alphabet used by the exit automaton ea.
static int sataf_ea_is_zero_or_one(sataf_ea *ea)
Check if ea recognizes anything or nothing.
static void sataf_sa_del_reference(sataf_sa *sa)
Decrement the number of references to sa.
static sataf_sa * sataf_sa_add_reference(sataf_sa *sa)
Add one the counter of references to sa.
static int sataf_sa_is_zero_or_one(sataf_sa *sa)
Check if sa accepts nothing or accepts nothing.
static uint32_t sataf_ea_encode_succ_as_local_state(uint32_t index)
Encode the successor state index as a local state.
static void sataf_mao_del_reference(sataf_mao *a)
Decrements the number of references to the given MAO.
static sataf_sa * sataf_msa_get_sa_no_ref(sataf_msa *msa)
Return the shared automaton defining msa but without incrementing its counter of references.
static uint32_t sataf_ea_get_successor(sataf_ea *ea, uint32_t state, uint32_t a)
Get the successor of state by the letter a.
static uint32_t sataf_ea_decode_succ_state(uint32_t index)
Decode the successor state index.
Macros allowing to set assertions into the code.
static void sataf_msa_del_reference(sataf_msa *msa)
Decrement the counter of references of msa.
struct sataf_sa_st sataf_sa
Type for the data structure encoding Shared Automata.
Definition: sataf.h:90
struct sataf_msa_st sataf_msa
Type for the data structure encoding Marked Shared Automata.
Definition: sataf.h:81
static uint32_t sataf_ea_get_nb_exits(sataf_ea *ea)
Return the number of exit states of ea.