From 0fa099713036eac275a38db2d9ec3eeb3c54ed4b Mon Sep 17 00:00:00 2001
From: Justin Seyster <jseyster@cs.sunysb.edu>
Date: Thu, 17 Feb 2011 18:25:10 -0500
Subject: [PATCH] Tracecut advice deletes tuples it doesn't need to store.

---
 src/nfa.c             | 16 +++++++++
 src/nfa.h             |  1 +
 src/tracecut-advice.c | 76 ++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 88 insertions(+), 5 deletions(-)

diff --git a/src/nfa.c b/src/nfa.c
index 5f7b9cf..0664872 100644
--- a/src/nfa.c
+++ b/src/nfa.c
@@ -430,6 +430,22 @@ ismatch(NState *ns)
 	return inlist(&ns->l, &matchstate);
 }
 
+/* True if the given state is exactly equivalent to the state of an
+   NFA that has received no input. */
+int
+isatstart(NState *ns)
+{
+	/* The first state is always the start state.  Also note that
+	 * matchstate never goes anywhere, so its presence in the
+	 * state list doesn't change anything. */
+	if (ns->l.n == 1)
+		return 1;
+	else if (ns->l.n == 2)
+		return (ns->l.s[1] == &matchstate);
+	else
+		return 0;
+}
+
 /* Add s to l, following unlabeled arrows. */
 static void
 addstate(List *l, State *s)
diff --git a/src/nfa.h b/src/nfa.h
index 01f572c..2cf53b3 100644
--- a/src/nfa.h
+++ b/src/nfa.h
@@ -28,6 +28,7 @@ struct NFA;
 struct NState;
 
 extern int ismatch (struct NState *ns);
+extern int isatstart (struct NState *ns);
 extern void step (struct NState *ns, int c);
 extern struct NState *getstartstate(struct NFA *nfa);
 extern void freenstate (struct NState *ns);
diff --git a/src/tracecut-advice.c b/src/tracecut-advice.c
index 66b4fed..7fe554d 100644
--- a/src/tracecut-advice.c
+++ b/src/tracecut-advice.c
@@ -52,8 +52,9 @@ static struct event *current_event = NULL;
    every state machine whose params match the non-vacant params in the
    event. */
 struct tuple {
-  /* For now, tuples are stored in a linked list. */
+  /* For now, tuples are stored in a doubly-linked list. */
   struct tuple *next;
+  struct tuple *prev;
 
   struct param_val *param_vals;
 
@@ -115,15 +116,72 @@ tc_report_match (struct tracecut *tc, struct tuple *tuple, int symbol_index)
     }
 }
 
+static void
+insert_tuple (struct tracecut *tc, struct tuple *tuple)
+{
+  tuple->prev = NULL;
+  tuple->next = tc->tuple_list;
+
+  if (tc->tuple_list != NULL)
+    tc->tuple_list->prev = tuple;
+
+  tc->tuple_list = tuple;
+}
+
+
+static void
+remove_tuple (struct tracecut *tc, struct tuple *tuple)
+{
+  if (tc->tuple_list == tuple)
+    tc->tuple_list = tuple->next;
+
+  if (tuple->next != NULL)
+    tuple->next->prev = tuple->prev;
+
+  if (tuple->prev != NULL)
+    tuple->prev->next = tuple->next;
+
+  tuple->next = tuple->prev = NULL;
+}
+
+static void
+destroy_tuple (struct tuple *tuple, int num_rules)
+{
+  if (tuple != NULL)
+    {
+      int i;
+      for (i = 0; i < num_rules; i++)
+	freenstate (tuple->states[i]);
+
+      free (tuple->states);
+      free (tuple->param_vals);
+      free (tuple);
+    }
+}
+
 static void
 advance_state_machine (struct tracecut *tc, struct tuple *tuple, int symbol_index)
 {
   int i;
+  int num_trivial = 0;
   for (i = 0; i < tc->num_rules; i++)
     {
       step (tuple->states[i], symbol_index);
       if (ismatch (tuple->states[i]))
 	tc_report_match (tc, tuple, symbol_index);
+
+      if (isatstart (tuple->states[i]))
+	num_trivial++;
+    }
+
+  /* If every state machine is in a "trivial" state, then we don't
+     need to keep this tuple around any more.  We say a state is
+     trivial when it looks exactly as it did when it was
+     initialized. */
+  if (num_trivial == tc->num_rules)
+    {
+      remove_tuple (tc, tuple);
+      destroy_tuple (tuple, tc->num_rules);
     }
 }
 
@@ -160,14 +218,21 @@ update_matching_tuples (struct event *event)
   struct tuple *tuple;
   int tuples_updated = 0;
 
-  for (tuple = tc->tuple_list; tuple != NULL; tuple = tuple->next)
+  tuple = tc->tuple_list;
+  while (tuple != NULL)
     {
+      /* This tuple might get destroyed by advance_state_machine, so
+	 save it's next value now. */
+      struct tuple *next = tuple->next;
+
       if (event_matches_tuple (event, tuple))
 	{
 	  advance_state_machine (event->tracecut, tuple, event->symbol_index);
 	  tuples_updated++;
 	  fprintf (stderr, "Advancing existing tuple.\n");
 	}
+
+      tuple = next;
     }
 
   return tuples_updated;
@@ -190,6 +255,7 @@ add_tuple_for_event (struct event *event)
       return NULL;
     }
 
+  tuple->next = tuple->prev = NULL;
   tuple->param_vals = calloc (tc->num_params, sizeof (struct param_val));
   tuple->states = calloc (tc->num_rules, sizeof (struct DState *));
   if (tuple->param_vals == NULL || tuple->states == NULL)
@@ -207,9 +273,7 @@ add_tuple_for_event (struct event *event)
 	goto nomem;
     }
 
-  /* Insert the tuple into the tracecut's tuple list. */
-  tuple->next = tc->tuple_list;
-  tc->tuple_list = tuple;
+  insert_tuple (tc, tuple);
 
   return tuple;
 
@@ -439,6 +503,8 @@ _tc_event_transition (int tc_index, int symbol_index)
       return;
     }
 
+  fprintf (stderr, "Event: %s\n", current_event->tracecut->symbol_names[symbol_index]);
+
   current_event->symbol_index = symbol_index;
   do_transition (current_event);
 }
-- 
2.34.1