edits

diff --git a/src/ASTAnalyses/Encoding/encodinggraph.cc b/src/ASTAnalyses/Encoding/encodinggraph.cc
index 3e8eec5ba5c20c49aed3f873e6fcde4378d2c414..e0cc869bd19cc5ffc781b88698c063f9c2d1c5c2 100644 (file)
--- a/src/ASTAnalyses/Encoding/encodinggraph.cc
+++ b/src/ASTAnalyses/Encoding/encodinggraph.cc
@@ -7,6 +7,7 @@
 #include "csolver.h"
 #include "tunable.h"
 #include "qsort.h"
+#include "subgraph.h"
 
 EncodingGraph::EncodingGraph(CSolver * _solver) :
        solver(_solver) {
@@ -303,57 +304,4 @@ uint64_t EncodingEdge::getValue() const {
        return numEquals * min + numComparisons * lSize * rSize;
 }
 
-EncodingSubGraph::EncodingSubGraph() :
-       encodingSize(0),
-       numElements(0) {
-}
-
-uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
-       uint newSize=0;
-       SetIteratorEncodingNode * nit = sg->nodes.iterator();
-       while(nit->hasNext()) {
-               EncodingNode *en = nit->next();
-               uint size=estimateNewSize(en);
-               if (size > newSize)
-                       newSize = size;
-       }
-       delete nit;
-       return newSize;
-}
 
-uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
-       SetIteratorEncodingEdge * eeit = n->edges.iterator();
-       uint newsize=n->getSize();
-       while(eeit->hasNext()) {
-               EncodingEdge * ee = eeit->next();
-               if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
-                       uint intersectSize = n->s->getUnionSize(ee->left->s);
-                       if (intersectSize > newsize)
-                               newsize = intersectSize;
-               }
-               if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
-                       uint intersectSize = n->s->getUnionSize(ee->right->s);
-                       if (intersectSize > newsize)
-                               newsize = intersectSize;
-               }
-               if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
-                       uint intersectSize = n->s->getUnionSize(ee->dst->s);
-                       if (intersectSize > newsize)
-                               newsize = intersectSize;
-               }
-       }
-       delete eeit;
-       return newsize;
-}
-
-void EncodingSubGraph::addNode(EncodingNode *n) {
-       nodes.add(n);
-       uint newSize=estimateNewSize(n);
-       numElements += n->elements.getSize();
-       if (newSize > encodingSize)
-               encodingSize=newSize;
-}
-
-SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
-       return nodes.iterator();
-}

diff --git a/src/ASTAnalyses/Encoding/encodinggraph.h b/src/ASTAnalyses/Encoding/encodinggraph.h
index f452dac2fc7660940bed0fa351695ec0abdd3bbd..2fd4b3748896f11ca44bfb1e92ee0aeb2ba50326 100644 (file)
--- a/src/ASTAnalyses/Encoding/encodinggraph.h
+++ b/src/ASTAnalyses/Encoding/encodinggraph.h
@@ -2,19 +2,7 @@
 #define ENCODINGGRAPH_H
 #include "classlist.h"
 #include "structs.h"
-
-uint hashEncodingEdge(EncodingEdge *edge);
-bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2);
-class EncodingSubGraph;
-
-
-typedef Hashtable<EncodingEdge *, EncodingEdge *, uintptr_t, PTRSHIFT, hashEncodingEdge, equalsEncodingEdge> HashtableEdge;
-typedef Hashset<EncodingNode *, uintptr_t, PTRSHIFT> HashsetEncodingNode;
-typedef SetIterator<EncodingNode *, uintptr_t, PTRSHIFT> SetIteratorEncodingNode;
-typedef Hashset<EncodingEdge *, uintptr_t, PTRSHIFT> HashsetEncodingEdge;
-typedef SetIterator<EncodingEdge *, uintptr_t, PTRSHIFT> SetIteratorEncodingEdge;
-
-typedef Hashtable<EncodingNode *, EncodingSubGraph *, uintptr_t, PTRSHIFT> HashtableNodeToSubGraph;
+#include "graphstructs.h"
 
 class EncodingGraph {
  public:
@@ -57,24 +45,6 @@ class EncodingNode {
        friend class EncodingSubGraph;
 };
 
-class EncodingSubGraph {
- public:
-       EncodingSubGraph();
-       void addNode(EncodingNode *n);
-       SetIteratorEncodingNode * nodeIterator();
-       
-       CMEMALLOC;
- private:
-       uint estimateNewSize(EncodingNode *n);
-       uint estimateNewSize(EncodingSubGraph *sg);
-
-       HashsetEncodingNode nodes;
-       uint encodingSize;
-       uint numElements;
-
-       friend class EncodingGraph;
-};
-
 enum EdgeEncodingType { EDGE_UNASSIGNED, EDGE_BREAK, EDGE_MATCH};
 typedef enum EdgeEncodingType EdgeEncodingType;
 

diff --git a/src/ASTAnalyses/Encoding/graphstructs.h b/src/ASTAnalyses/Encoding/graphstructs.h
new file mode 100644 (file)
index 0000000..3a54a81
--- /dev/null
+++ b/src/ASTAnalyses/Encoding/graphstructs.h
@@ -0,0 +1,18 @@
+#ifndef GRAPHSTRUCTS_H
+#define GRAPHSTRUCTS_H
+#include "classlist.h"
+#include "structs.h"
+
+uint hashEncodingEdge(EncodingEdge *edge);
+bool equalsEncodingEdge(EncodingEdge *e1, EncodingEdge *e2);
+class EncodingSubGraph;
+
+
+typedef Hashtable<EncodingEdge *, EncodingEdge *, uintptr_t, PTRSHIFT, hashEncodingEdge, equalsEncodingEdge> HashtableEdge;
+typedef Hashset<EncodingNode *, uintptr_t, PTRSHIFT> HashsetEncodingNode;
+typedef SetIterator<EncodingNode *, uintptr_t, PTRSHIFT> SetIteratorEncodingNode;
+typedef Hashset<EncodingEdge *, uintptr_t, PTRSHIFT> HashsetEncodingEdge;
+typedef SetIterator<EncodingEdge *, uintptr_t, PTRSHIFT> SetIteratorEncodingEdge;
+
+typedef Hashtable<EncodingNode *, EncodingSubGraph *, uintptr_t, PTRSHIFT> HashtableNodeToSubGraph;
+#endif

diff --git a/src/ASTAnalyses/Encoding/subgraph.cc b/src/ASTAnalyses/Encoding/subgraph.cc
new file mode 100644 (file)
index 0000000..ceca9b0
--- /dev/null
+++ b/src/ASTAnalyses/Encoding/subgraph.cc
@@ -0,0 +1,87 @@
+#include "subgraph.h"
+#include "encodinggraph.h"
+#include "set.h"
+
+EncodingSubGraph::EncodingSubGraph() :
+       encodingSize(0),
+       numElements(0) {
+}
+
+uint hashNodeValuePair(NodeValuePair *nvp) {
+       return (uint) (nvp->value ^ ((uintptr_t)nvp->node));
+}
+
+bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2) {
+       return nvp1->value == nvp2->value && nvp1->node == nvp2->node;
+}
+
+uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
+       uint newSize=0;
+       SetIteratorEncodingNode * nit = sg->nodes.iterator();
+       while(nit->hasNext()) {
+               EncodingNode *en = nit->next();
+               uint size=estimateNewSize(en);
+               if (size > newSize)
+                       newSize = size;
+       }
+       delete nit;
+       return newSize;
+}
+
+uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
+       SetIteratorEncodingEdge * eeit = n->edges.iterator();
+       uint newsize=n->getSize();
+       while(eeit->hasNext()) {
+               EncodingEdge * ee = eeit->next();
+               if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
+                       uint intersectSize = n->s->getUnionSize(ee->left->s);
+                       if (intersectSize > newsize)
+                               newsize = intersectSize;
+               }
+               if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
+                       uint intersectSize = n->s->getUnionSize(ee->right->s);
+                       if (intersectSize > newsize)
+                               newsize = intersectSize;
+               }
+               if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
+                       uint intersectSize = n->s->getUnionSize(ee->dst->s);
+                       if (intersectSize > newsize)
+                               newsize = intersectSize;
+               }
+       }
+       delete eeit;
+       return newsize;
+}
+
+void EncodingSubGraph::addNode(EncodingNode *n) {
+       nodes.add(n);
+       uint newSize=estimateNewSize(n);
+       numElements += n->elements.getSize();
+       if (newSize > encodingSize)
+               encodingSize=newSize;
+}
+
+SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
+       return nodes.iterator();
+}
+
+void EncodingSubGraph::encode() {
+       SetIteratorEncodingNode *nodeit=nodes.iterator();
+       while(nodeit->hasNext()) {
+               EncodingNode *node=nodeit->next();
+               Set * set = node->s;
+               uint setSize = set->getSize();
+               for(uint i=0; i<setSize; i++) {
+                       uint64_t val = set->getElement(i);
+                       NodeValuePair nvp(node, val);
+                       if (!map.contains(&nvp)) {
+                               traverseValue(node, val);
+                       }
+               }
+       }
+       delete nodeit;
+}
+
+void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
+       
+}

diff --git a/src/ASTAnalyses/Encoding/subgraph.h b/src/ASTAnalyses/Encoding/subgraph.h
new file mode 100644 (file)
index 0000000..5520709
--- /dev/null
+++ b/src/ASTAnalyses/Encoding/subgraph.h
@@ -0,0 +1,48 @@
+#ifndef SUBGRAPH_H
+#define SUBGRAPH_H
+#include "classlist.h"
+#include "structs.h"
+#include "graphstructs.h"
+
+class NodeValuePair {
+ public:
+ NodeValuePair(EncodingNode *n, uint64_t val) : node(n), value(val) {}
+       EncodingNode *node;
+       uint64_t value;
+};
+
+class EncodingValue {
+ public:
+       void merge(EncodingValue *value);
+       uint64_t value;
+       HashsetEncodingNode nodes;
+};
+
+uint hashNodeValuePair(NodeValuePair *nvp);
+bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2);
+
+typedef Hashtable<NodeValuePair *, EncodingValue *, uintptr_t, 4, hashNodeValuePair, equalsNodeValuePair> NVPMap;
+
+class EncodingSubGraph {
+ public:
+       EncodingSubGraph();
+       void addNode(EncodingNode *n);
+       SetIteratorEncodingNode * nodeIterator();
+       void encode();
+       
+       CMEMALLOC;
+ private:
+       uint estimateNewSize(EncodingNode *n);
+       uint estimateNewSize(EncodingSubGraph *sg);
+       void traverseValue(EncodingNode *node, uint64_t value);
+
+       
+       HashsetEncodingNode nodes;
+       NVPMap map;
+       uint encodingSize;
+       uint numElements;
+
+       friend class EncodingGraph;
+};
+
+#endif