[apparmor] [PATCH 2/9] Embedded the temporary computed nodes as part of the state

[John Johansen]

Embedding the nodes are part of the state gives fast back reference from
the state to the nodes that created it.  This is useful for the state to
nodes mapping dump as it lets us output the states in order.  It will also
let us avoid certain nodemap lookup in the future.

Overlay the nodes field (used only in dfa construction) with the partition
field which is only used during dfa minimization to avoid making the state
any larger.

Signed-off-by: John Johansen <john.johansen at canonical.com>
---
 parser/libapparmor_re/regexp.y |   21 +++++++++++++++------
 1 files changed, 15 insertions(+), 6 deletions(-)

diff --git a/parser/libapparmor_re/regexp.y b/parser/libapparmor_re/regexp.y
index 82e9bb5..f866b78 100644
--- a/parser/libapparmor_re/regexp.y
+++ b/parser/libapparmor_re/regexp.y
@@ -1403,7 +1403,10 @@ class State {
 public:
 State() : label (0), audit(0), accept(0), cases() { }
 	int label;
-	Partition *partition;
+	union {
+		Partition *partition;
+		NodeSet *nodes;
+	};
 	uint32_t audit, accept;
 	Cases cases;
 };
@@ -1421,6 +1424,7 @@ typedef map<pair<unsigned long, NodeSet *>, State *, deref_less_than > NodeMap;
 /* Transitions in the DFA. */
 
 class DFA {
+    void dump_node_to_dfa(void);
 public:
     DFA(Node *root, dfaflags_t flags);
     virtual ~DFA();
@@ -1454,6 +1458,7 @@ do { \
 		 */ \
 		TARGET = new State(); \
 		(TARGET)->label = nodemap.size();	\
+		(TARGET)->nodes = (NODES); \
 		states.push_back(TARGET); \
 		nodemap.insert(make_pair(index, TARGET)); \
 		work_queue.push_back(NODES);	  \
@@ -1468,14 +1473,16 @@ do { \
 	} \
 } while (0)
 
-static void dump_node_to_dfa(NodeMap &nodemap)
+/* WARNING: This routine can only be called from within DFA creation as
+ * the nodes value is only valid during dfa construction.
+ */
+void DFA::dump_node_to_dfa(void)
 {
 	cerr << "Mapping of States to expr nodes\n"
 		"  State  <=   Nodes\n"
 		"-------------------\n";
-	for (NodeMap::iterator i = nodemap.begin(); i != nodemap.end(); i++)
-		cerr << "  " << i->second->label << " <= " << *i->first.second << "\n";
-
+	for (Partition::iterator i = states.begin(); i != states.end(); i++)
+		cerr << "  " << (*i)->label << " <= " << *(*i)->nodes << "\n";
 }
 
 /**
@@ -1505,6 +1512,7 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
 	nonmatching = new State;
 	states.push_back(nonmatching);
 	NodeSet *emptynode = new NodeSet;
+	nonmatching->nodes = emptynode;
 	nodemap.insert(make_pair(make_pair(hash_NodeSet(emptynode), emptynode), nonmatching));
 	/* there is no nodemapping for the nonmatching state */
 
@@ -1515,6 +1523,7 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
 	start->label = 1;
 	states.push_back(start);
 	NodeSet *first = new NodeSet(root->firstpos);
+	start->nodes = first;
 	nodemap.insert(make_pair(make_pair(hash_NodeSet(first), first), start));
 
 	/* the work_queue contains the proto-states (set of nodes that is
@@ -1594,7 +1603,7 @@ DFA::DFA(Node *root, dfaflags_t flags) : root(root)
 	}
 
 	if (flags & DFA_DUMP_NODE_TO_DFA)
-		dump_node_to_dfa(nodemap);
+		dump_node_to_dfa();
 
 	for (NodeMap::iterator i = nodemap.begin(); i != nodemap.end(); i++)
 		delete i->first.second;
-- 
1.7.1