From 36186bb2c75326350898d1253c00af5e6d547ec8 Mon Sep 17 00:00:00 2001
From: Stathis Kamperis <ekamperi@auth.gr>
Date: Mon, 21 Apr 2008 16:47:00 +0300
Subject: [PATCH] Add fsm_mark_reachable_states()

---
 fsm/fsm.c   | 40 ++++++++++++++++++++++++++++++++++++++--
 fsm/fsm.h   |  1 +
 fsm/types.h |  5 +++++
 3 files changed, 44 insertions(+), 2 deletions(-)

diff --git a/fsm/fsm.c b/fsm/fsm.c
index bfb77ac..5234d45 100644
--- a/fsm/fsm.c
+++ b/fsm/fsm.c
@@ -125,6 +125,14 @@ fsmret_t fsm_set_state(fsm_t *fsm, unsigned int stkey)
     if ((state = htable_search(fsm->sttable, &stkey)) == NULL)
         return FSM_ENOTFOUND;
 
+    /* Mark state as reachable
+     * XXX: Do we need to call fsm_mark_reachable_states() ?
+     * By doing so, we guarantee that fsm's states's flags
+     * are always uptodate.
+     */
+    STATE_MARK_AS_REACHABLE(state);
+    fsm_mark_reachable_states(fsm);
+
     /* Set fsm to new state */
     fsm->cstate = state;
 
@@ -289,12 +297,39 @@ void fsm_print_states(const fsm_t *fsm, FILE *fp)
     htable_iterator_init(&sit);
     while ((sit.pnode = htable_get_next_elm(fsm->sttable, &sit)) != NULL) {
         pstate = sit.pnode->hn_data;
-        fprintf(fp, "state [key = %u]\n",
-                *(unsigned int *)(pstate->st_key));
+        fprintf(fp, "state [key = %u, reachable = %c]\n",
+                *(unsigned int *)(pstate->st_key),
+                STATE_IS_REACHABLE(pstate) ? 'T' : 'F');
         state_print_evts(pstate, fp);
     }
 }
 
+void fsm_mark_reachable_states(fsm_t *fsm)
+{
+    const state_t *pstate;
+    const event_t *pevt;
+    htable_iterator_t sit;    /* states iterator */
+    htable_iterator_t eit;    /* event iterator */
+
+    /* For all states */
+    htable_iterator_init(&sit);
+    while ((sit.pnode = htable_get_next_elm(fsm->sttable, &sit)) != NULL) {
+        htable_iterator_init(&eit);
+        pstate = sit.pnode->hn_data;
+
+        /*
+         * We mark a state as reachable, if and only if
+         * there exist transitions to this state, from other
+         * _reachable_ states.
+         */
+        while ((eit.pnode = htable_get_next_elm(pstate->evttable, &eit)) != NULL) {
+            pevt = eit.pnode->hn_data;
+            if (STATE_IS_REACHABLE(pstate))
+                STATE_MARK_AS_REACHABLE(pevt->evt_newstate);
+        }
+    }
+}
+
 void fsm_minimize(fsm_t *fsm)
 {
     const state_t *pstate;
@@ -342,3 +377,4 @@ static void fsm_pq_unlock(const fsm_t *fsm)
     /* Machine dependent code */
     pthread_mutex_unlock((pthread_mutex_t *) fsm->mobj);
 }
+
diff --git a/fsm/fsm.h b/fsm/fsm.h
index caf7e77..cac89cd 100644
--- a/fsm/fsm.h
+++ b/fsm/fsm.h
@@ -19,5 +19,6 @@ fsmret_t fsm_process_event(fsm_t *fsm, unsigned int evtkey, void *data);
 fsmret_t fsm_validate(const fsm_t *fsm);
 void fsm_export_to_dot(const fsm_t *fsm, FILE *fp);
 void fsm_print_states(const fsm_t *fsm, FILE *fp);
+void fsm_mark_reachable_states(fsm_t *fsm);
 void fsm_minimize(fsm_t *fsm);
 #endif    /* FSM_H */
diff --git a/fsm/types.h b/fsm/types.h
index aae67df..6836ae6 100644
--- a/fsm/types.h
+++ b/fsm/types.h
@@ -14,8 +14,13 @@ typedef struct event {
 typedef struct state {
     htable_t *evttable;
     unsigned int *st_key;
+    unsigned char flag;
 } state_t;
 
+#define STATE_REACHABLE (1 << 0)
+#define STATE_IS_REACHABLE(pstate) (pstate->flag & STATE_REACHABLE)
+#define STATE_MARK_AS_REACHABLE(pstate) pstate->flag |= STATE_REACHABLE;
+
 typedef enum {
     ST_OK,
     ST_EXISTS,
-- 
2.11.4.GIT