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
;
227 for (i
= 0; i
< pfsm
->nqueues
; i
++) {
228 phead
= &pfsm
->pqtable
[i
];
229 STAILQ_FOREACH(pnode
, phead
, pq_next
)
236 fsmret_t
fsm_process_event(fsm_t
*pfsm
, unsigned int evtkey
, void *data
)
240 /* Can the current state handle the incoming event ? */
241 if ((pevt
= htable_search(pfsm
->cstate
->evttable
, &evtkey
)) == NULL
)
242 return FSM_ENOTFOUND
;
244 /* Execute appropriate action */
245 if (pevt
->evt_actionf
!= NULL
)
246 pevt
->evt_actionf(data
);
248 /* Is the transition made to an existent state ? */
249 if ((pevt
->evt_newstate
== NULL
)
250 || (htable_search(pfsm
->sttable
, pevt
->evt_newstate
->st_key
) == NULL
))
251 return FSM_ENOTFOUND
;
254 pfsm
->cstate
= pevt
->evt_newstate
;
259 fsmret_t
fsm_validate(const fsm_t
*pfsm
)
261 /* Is FSM empty of states ? */
262 if (htable_get_used(pfsm
->sttable
) == 0)
268 void fsm_export_to_dot(const fsm_t
*pfsm
, FILE *fp
)
270 const state_t
*pstate
;
272 htable_iterator_t sit
; /* state iterator */
273 htable_iterator_t eit
; /* event iterator */
275 fprintf(fp
, "digraph {\n");
277 /* Traverse all states of FSM */
278 htable_iterator_init(&sit
);
279 while ((sit
.pnode
= htable_get_next_elm(pfsm
->sttable
, &sit
)) != NULL
) {
280 /* Traverse all events associated with the current state */
281 pstate
= htable_iterator_get_data(sit
);
282 htable_iterator_init(&eit
);
283 while ((eit
.pnode
= htable_get_next_elm(pstate
->evttable
, &eit
)) != NULL
) {
284 pevt
= htable_iterator_get_data(eit
);
285 printf("S%u -> S%u [label=\"E%u\"]\n",
286 *(unsigned int *) htable_iterator_get_key(sit
),
287 *(unsigned int *) (pevt
->evt_newstate
->st_key
),
288 *(unsigned int *) htable_iterator_get_key(eit
));
295 void fsm_print_states(const fsm_t
*pfsm
, FILE *fp
)
297 const state_t
*pstate
;
298 htable_iterator_t sit
; /* states iterator */
300 /* Traverse all states of FSM */
301 htable_iterator_init(&sit
);
302 while ((sit
.pnode
= htable_get_next_elm(pfsm
->sttable
, &sit
)) != NULL
) {
303 pstate
= htable_iterator_get_data(sit
);
304 fprintf(fp
, "state [key = %u, reachable = %c]\n",
305 *(unsigned int *) (pstate
->st_key
),
306 STATE_IS_REACHABLE(pstate
) ? 'T' : 'F');
307 state_print_evts(pstate
, fp
);
311 void fsm_mark_reachable_states(fsm_t
*pfsm
)
313 const state_t
*pstate
;
315 htable_iterator_t sit
; /* states iterator */
316 htable_iterator_t eit
; /* event iterator */
319 htable_iterator_init(&sit
);
320 while ((sit
.pnode
= htable_get_next_elm(pfsm
->sttable
, &sit
)) != NULL
) {
321 pstate
= htable_iterator_get_data(sit
);
322 htable_iterator_init(&eit
);
325 * We mark a state as reachable, if and only if
326 * there exist transitions to this state, from other
327 * _reachable_ states.
329 while ((eit
.pnode
= htable_get_next_elm(pstate
->evttable
, &eit
)) != NULL
) {
330 pevt
= htable_iterator_get_data(eit
);
331 if (STATE_IS_REACHABLE(pstate
))
332 STATE_MARK_AS_REACHABLE(pevt
->evt_newstate
);
337 void fsm_minimize(fsm_t
*pfsm
)
339 const state_t
*pstate
;
340 htable_iterator_t sit
; /* states iterator */
342 /* Remove unreachable states */
343 htable_iterator_init(&sit
);
344 while ((sit
.pnode
= htable_get_next_elm(pfsm
->sttable
, &sit
)) != NULL
) {
345 pstate
= htable_iterator_get_data(sit
);
349 /* Callback funtions */
350 static unsigned int fsm_hashf(const void *pkey
)
352 return *(const unsigned int *) pkey
;
355 static int fsm_cmpf(const void *parg1
, const void *parg2
)
357 unsigned int a
= *(const unsigned int *) parg1
;
358 unsigned int b
= *(const unsigned int *) parg2
;
368 static void fsm_printf(const void *pkey
, const void *pdata
)
370 printf("key: %u ", *(const unsigned int *) pkey
);
373 static void fsm_pq_lock(const fsm_t
*pfsm
)
375 /* Machine dependent code */
376 pthread_mutex_lock((pthread_mutex_t
*) pfsm
->mobj
);
379 static void fsm_pq_unlock(const fsm_t
*pfsm
)
381 /* Machine dependent code */
382 pthread_mutex_unlock((pthread_mutex_t
*) pfsm
->mobj
);