12 /* Callback funtions prototypes */
13 static unsigned int fsm_hashf(const void *key
);
14 static int fsm_cmpf(const void *arg1
, const void *arg2
);
15 static void fsm_printf(const void *key
, const void *data
);
16 static void fsm_pq_lock(const fsm_t
*fsm
);
17 static void fsm_pq_unlock(const fsm_t
*fsm
);
19 fsmret_t
fsm_init(fsm_t
**ppfsm
, size_t size
, unsigned int factor
,
24 /* FIXME: Validate input */
26 /* Allocate memory for fsm data structure */
27 if ((*ppfsm
= malloc(sizeof **ppfsm
)) == NULL
)
30 /* Allocate memory for fsm's states' hash table */
31 if (((*ppfsm
)->sttable
= malloc(sizeof *(*ppfsm
)->sttable
)) == NULL
) {
36 /* Allocate memory for priority queues */
37 if (((*ppfsm
)->pqtable
= malloc(nqueues
* sizeof *(*ppfsm
)->pqtable
)) == NULL
) {
38 free((*ppfsm
)->sttable
);
43 /* Allocate memory for "mutex object" -- machine dependent code */
44 if (((*ppfsm
)->mobj
= malloc(sizeof(pthread_mutex_t
))) == NULL
) {
46 free((*ppfsm
)->sttable
);
50 /* Machine dependent code */
51 pthread_mutex_init((pthread_mutex_t
*)(*ppfsm
)->mobj
, NULL
);
53 /* Initialize queues */
54 (*ppfsm
)->nqueues
= nqueues
;
55 for (i
= 0; i
< nqueues
; i
++)
56 STAILQ_INIT(&(*ppfsm
)->pqtable
[i
]);
58 /* Initialize states' hash table */
59 if (htable_init((*ppfsm
)->sttable
, size
, factor
,
60 fsm_hashf
, fsm_cmpf
, fsm_printf
) == HT_NOMEM
) {
61 free((*ppfsm
)->pqtable
);
62 free((*ppfsm
)->sttable
);
70 fsmret_t
fsm_add_state(fsm_t
*pfsm
, unsigned int key
, state_t
*pstate
)
73 * There is no need to allocate memory for state's key,
74 * since this is done in state_init().
76 *pstate
->st_key
= key
;
78 /* Insert state to hash table */
79 if (htable_insert(pfsm
->sttable
, pstate
->st_key
, pstate
) == HT_EXISTS
)
85 fsmret_t
fsm_free(fsm_t
*pfsm
)
89 htable_iterator_t sit
; /* states iterator */
92 /* Free states' table */
93 htable_iterator_init(&sit
);
94 while ((sit
.pnode
= htable_get_next_elm(pfsm
->sttable
, &sit
)) != NULL
)
95 state_free(htable_iterator_get_data(sit
));
98 htable_free_all_obj(pfsm
->sttable
, HT_FREEKEY
);
99 htable_free(pfsm
->sttable
);
102 /* Free queues' elements */
103 for (i
= 0; i
< pfsm
->nqueues
; i
++) {
104 phead
= &pfsm
->pqtable
[i
];
105 while (STAILQ_FIRST(phead
) != NULL
) {
106 pnode
= STAILQ_FIRST(phead
);
107 STAILQ_REMOVE_HEAD(phead
, pq_next
);
120 fsmret_t
fsm_set_state(fsm_t
*pfsm
, unsigned int stkey
)
124 /* Does this state exist in states' hash table ? */
125 if ((pstate
= htable_search(pfsm
->sttable
, &stkey
)) == NULL
)
126 return FSM_ENOTFOUND
;
129 * Mark state as reachable
131 * By calling fsm_mark_reachable_states() we guarantee that
132 * states' flags are always in accordance with reality.
133 * Also, we use fsm_set_state() to set the _initial_ state,
134 * thus rendering it "explicitly reachable".
136 STATE_MARK_AS_REACHABLE(pstate
);
137 fsm_mark_reachable_states(pfsm
);
139 /* Set fsm to new state */
140 pfsm
->cstate
= pstate
;
145 unsigned int fsm_get_current_state(const fsm_t
*pfsm
)
147 return *pfsm
->cstate
->st_key
;
150 fsmret_t
fsm_queue_event(fsm_t
*pfsm
, unsigned int evtkey
,
151 void *pdata
, size_t size
, unsigned int prio
)
157 if (prio
>= pfsm
->nqueues
)
160 /* Allocate memory for new pending event */
161 if ((pnode
= malloc(sizeof *pnode
)) == NULL
)
164 pnode
->evtkey
= evtkey
;
168 * Allocate memory for data and copy them over.
169 * Note that this strategy leads to memory fragmentation,
170 * and should be addressed with a custom memory allocator,
173 if ((pnode
->data
= malloc(size
)) == NULL
) {
177 memcpy(pnode
->data
, pdata
, size
);
179 /* Get the head of the queue with the appropriate priority */
180 phead
= &pfsm
->pqtable
[prio
];
182 /* Insert new event in tail (we serve from head) */
184 STAILQ_INSERT_TAIL(phead
, pnode
, pq_next
);
189 fsmret_t
fsm_dequeue_event(fsm_t
*pfsm
)
195 /* Scan queues starting from the one with the biggest priority */
196 i
= pfsm
->nqueues
- 1;
198 phead
= &pfsm
->pqtable
[i
];
199 if ((pnode
= STAILQ_FIRST(phead
)) != NULL
) {
200 if (fsm_process_event(pfsm
, pnode
->evtkey
, pnode
->data
) == FSM_ENOTFOUND
) {
202 * XXX: Should the event should stay in queue, waiting for fsm
203 * to go into a state that can handle it ? We haven't though
204 * implemented such a sticky bit in event's structure yet.
209 pnode
= STAILQ_FIRST(phead
);
210 STAILQ_REMOVE_HEAD(phead
, pq_next
);
211 free(pnode
->data
); /* Argh, memory fragmentation */
220 size_t fsm_get_queued_events(const fsm_t
*pfsm
)
222 const pqhead_t
*phead
;
223 const pqnode_t
*pnode
;
228 for (i
= 0; i
< pfsm
->nqueues
; i
++) {
229 phead
= &pfsm
->pqtable
[i
];
230 STAILQ_FOREACH(pnode
, phead
, pq_next
)
238 fsmret_t
fsm_process_event(fsm_t
*pfsm
, unsigned int evtkey
, void *data
)
242 /* Can the current state handle the incoming event ? */
243 if ((pevt
= htable_search(pfsm
->cstate
->evttable
, &evtkey
)) == NULL
)
244 return FSM_ENOTFOUND
;
246 /* Execute appropriate action */
247 if (pevt
->evt_actionf
!= NULL
)
248 pevt
->evt_actionf(data
);
250 /* Is the transition made to an existent state ? */
251 if ((pevt
->evt_newstate
== NULL
)
252 || (htable_search(pfsm
->sttable
, pevt
->evt_newstate
->st_key
) == NULL
))
253 return FSM_ENOTFOUND
;
256 pfsm
->cstate
= pevt
->evt_newstate
;
261 fsmret_t
fsm_validate(const fsm_t
*pfsm
)
263 /* Is FSM empty of states ? */
264 if (htable_get_used(pfsm
->sttable
) == 0)
270 void fsm_export_to_dot(const fsm_t
*pfsm
, FILE *fp
)
272 const state_t
*pstate
;
274 htable_iterator_t sit
; /* state iterator */
275 htable_iterator_t eit
; /* events iterator */
277 fprintf(fp
, "digraph {\n");
279 /* Traverse all states of FSM */
280 htable_iterator_init(&sit
);
281 while ((sit
.pnode
= htable_get_next_elm(pfsm
->sttable
, &sit
)) != NULL
) {
282 /* Traverse all events associated with the current state */
283 pstate
= htable_iterator_get_data(sit
);
284 htable_iterator_init(&eit
);
285 while ((eit
.pnode
= htable_get_next_elm(pstate
->evttable
, &eit
)) != NULL
) {
286 pevt
= htable_iterator_get_data(eit
);
287 printf("S%u -> S%u [label=\"E%u\"]\n",
288 *(unsigned int *) htable_iterator_get_key(sit
),
289 *(unsigned int *) (pevt
->evt_newstate
->st_key
),
290 *(unsigned int *) htable_iterator_get_key(eit
));
297 void fsm_print_states(const fsm_t
*pfsm
, FILE *fp
)
299 const state_t
*pstate
;
300 htable_iterator_t sit
; /* states iterator */
302 /* Traverse all states of FSM */
303 htable_iterator_init(&sit
);
304 while ((sit
.pnode
= htable_get_next_elm(pfsm
->sttable
, &sit
)) != NULL
) {
305 pstate
= htable_iterator_get_data(sit
);
306 fprintf(fp
, "state [key = %u, reachable = %c]\n",
307 *(unsigned int *) (pstate
->st_key
),
308 STATE_IS_REACHABLE(pstate
) ? 'T' : 'F');
309 state_print_evts(pstate
, fp
);
313 void fsm_mark_reachable_states(fsm_t
*pfsm
)
315 const state_t
*pstate
;
317 htable_iterator_t sit
; /* states iterator */
318 htable_iterator_t eit
; /* events iterator */
321 htable_iterator_init(&sit
);
322 while ((sit
.pnode
= htable_get_next_elm(pfsm
->sttable
, &sit
)) != NULL
) {
323 pstate
= htable_iterator_get_data(sit
);
324 htable_iterator_init(&eit
);
327 * We mark a state as reachable, if and only if there exist transitions
328 * to this state from other _reachable_ states.
330 while ((eit
.pnode
= htable_get_next_elm(pstate
->evttable
, &eit
)) != NULL
) {
331 pevt
= htable_iterator_get_data(eit
);
332 if (STATE_IS_REACHABLE(pstate
))
333 STATE_MARK_AS_REACHABLE(pevt
->evt_newstate
);
338 void fsm_remove_unreachable_state(fsm_t
*pfsm
, const state_t
*pstate
)
342 void fsm_minimize(fsm_t
*pfsm
)
344 const state_t
*pstate
;
345 htable_iterator_t sit
; /* states iterator */
347 /* Remove unreachable states */
348 htable_iterator_init(&sit
);
349 while ((sit
.pnode
= htable_get_next_elm(pfsm
->sttable
, &sit
)) != NULL
) {
350 pstate
= htable_iterator_get_data(sit
);
352 if (!STATE_IS_REACHABLE(pstate
))
353 fsm_remove_unreachable_state(pfsm
, pstate
);
357 /* Callback funtions */
358 static unsigned int fsm_hashf(const void *pkey
)
360 return *(const unsigned int *) pkey
;
363 static int fsm_cmpf(const void *parg1
, const void *parg2
)
365 unsigned int a
= *(const unsigned int *) parg1
;
366 unsigned int b
= *(const unsigned int *) parg2
;
376 static void fsm_printf(const void *pkey
, const void *pdata
)
378 printf("key: %u ", *(const unsigned int *) pkey
);
381 static void fsm_pq_lock(const fsm_t
*pfsm
)
383 /* Machine dependent code */
384 pthread_mutex_lock((pthread_mutex_t
*) pfsm
->mobj
);
387 static void fsm_pq_unlock(const fsm_t
*pfsm
)
389 /* Machine dependent code */
390 pthread_mutex_unlock((pthread_mutex_t
*) pfsm
->mobj
);