[apparmor] [PATCH 07/10] Add a new class hashedNodeSet. It is the functional equivalent of ProtoState. We do this to provide a new level of abstraction that ProtoState can leverage, when the node types are split.

[John Johansen]

Signed-off-by: John Johansen <john.johansen at canonical.com>
---
 parser/libapparmor_re/hfa.cc |   12 +++++++++---
 parser/libapparmor_re/hfa.h  |   27 +++++++++++++++++++++++----
 2 files changed, 32 insertions(+), 7 deletions(-)

diff --git a/parser/libapparmor_re/hfa.cc b/parser/libapparmor_re/hfa.cc
index bcfd2de..c805467 100644
--- a/parser/libapparmor_re/hfa.cc
+++ b/parser/libapparmor_re/hfa.cc
@@ -61,6 +61,12 @@ State *DFA::find_target_state(NodeMap &nodemap, list<State *> &work_queue,
 {
 	State *target;
 
+	pair<set<hashedNodeSet>::iterator,bool> uniq = uniq_nodes.insert(hashedNodeSet(nodes));
+	if (uniq.second == false) {
+		delete(nodes);
+		nodes = uniq.first->nodes;
+	}
+
 	ProtoState index(nodes);
 
 	map<ProtoState, State *>::iterator x = nodemap.find(index);
@@ -74,7 +80,6 @@ State *DFA::find_target_state(NodeMap &nodemap, list<State *> &work_queue,
 	} else {
 		/* set of nodes already has a mapping so free this one */
 		stats.duplicates++;
-		delete(nodes);
 		target = x->second;
 	}
 
@@ -206,8 +211,9 @@ DFA::DFA(Node *root, dfaflags_t flags): root(root)
 	if (flags & DFA_DUMP_NODE_TO_DFA)
 		dump_node_to_dfa();
 
-	for (NodeMap::iterator i = nodemap.begin(); i != nodemap.end(); i++)
-		delete i->first.nodes;
+	for (set<hashedNodeSet>::iterator i = uniq_nodes.begin(); i != uniq_nodes.end(); i++)
+		delete i->nodes;
+	uniq_nodes.clear();
 	nodemap.clear();
 
 	if (flags & (DFA_DUMP_STATS))
diff --git a/parser/libapparmor_re/hfa.h b/parser/libapparmor_re/hfa.h
index 29c552f..8719eb4 100644
--- a/parser/libapparmor_re/hfa.h
+++ b/parser/libapparmor_re/hfa.h
@@ -40,19 +40,19 @@ typedef list<State *> Partition;
 uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
 
 /*
- * ProtoState - NodeSet and ancillery information used to create a state
+ * hashedNodes - for efficient set comparison
  */
-class ProtoState {
+class hashedNodeSet {
 public:
 	unsigned long hash;
 	NodeSet *nodes;
 
-	ProtoState(NodeSet *n): nodes(n)
+	hashedNodeSet(NodeSet *n): nodes(n)
 	{
 		hash = hash_NodeSet(n);
 	}
 
-	bool operator<(ProtoState const &rhs)const
+	bool operator<(hashedNodeSet const &rhs)const
 	{
 		if (hash == rhs.hash) {
 			if (nodes->size() == rhs.nodes->size())
@@ -66,6 +66,21 @@ public:
 };
 
 /*
+ * ProtoState - NodeSet and ancillery information used to create a state
+ */
+class ProtoState {
+public:
+	NodeSet *nodes;
+
+	ProtoState(NodeSet *n): nodes(n) { };
+	bool operator<(ProtoState const &rhs)const
+	{
+		return nodes < rhs.nodes;
+	}
+
+};
+
+/*
  * State - DFA individual state information
  * label: a unique label to identify the state used for pretty printing
  *        the non-matching state is setup to have label == 0 and
@@ -135,6 +150,10 @@ class DFA {
 				      State *state, dfa_stats_t &stats);
 	State *find_target_state(NodeMap &nodemap, list<State *> &work_queue,
 				 NodeSet *nodes, dfa_stats_t &stats);
+
+	/* temporary values used during computations */
+	set<hashedNodeSet> uniq_nodes;
+
 public:
 	DFA(Node *root, dfaflags_t flags);
 	virtual ~DFA();
-- 
1.7.5.4