From 44422505466be25fc1566b66fefc22c12eb53cc8 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Mon, 18 Sep 2017 00:10:16 -0700 Subject: [PATCH] edits --- src/AST/set.cc | 20 ++++- src/AST/set.h | 1 - src/ASTAnalyses/Encoding/subgraph.cc | 123 ++++++++++++++++++++++++++- src/ASTAnalyses/Encoding/subgraph.h | 7 +- 4 files changed, 144 insertions(+), 7 deletions(-) diff --git a/src/AST/set.cc b/src/AST/set.cc index 6e150ff..c3050ec 100644 --- a/src/AST/set.cc +++ b/src/AST/set.cc @@ -32,12 +32,24 @@ bool Set::exists(uint64_t element) { if (isRange) { return element >= low && element <= high; } else { - uint size = members->getSize(); - for (uint i = 0; i < size; i++) { - if (element == members->get(i)) + //Use Binary Search + uint low=0; + uint high=members->getSize()-1; + while(true) { + uint middle=(low+high)/2; + uint64_t val=members->get(middle); + if (element < val) { + high=middle; + if (middle==low) + return false; + } else if (element > val) { + low=middle; + if (middle==high) + return false; + } else { return true; + } } - return false; } } diff --git a/src/AST/set.h b/src/AST/set.h index 2eb4828..088eca5 100644 --- a/src/AST/set.h +++ b/src/AST/set.h @@ -34,7 +34,6 @@ protected: uint64_t low;//also used to count unique items uint64_t high; Vector *members; - }; #endif/* SET_H */ diff --git a/src/ASTAnalyses/Encoding/subgraph.cc b/src/ASTAnalyses/Encoding/subgraph.cc index ceca9b0..69fb367 100644 --- a/src/ASTAnalyses/Encoding/subgraph.cc +++ b/src/ASTAnalyses/Encoding/subgraph.cc @@ -66,6 +66,102 @@ SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() { } void EncodingSubGraph::encode() { + computeEncodingValue(); + computeInequalities(); +} + +void EncodingSubGraph::computeInequalities() { + SetIteratorEncodingNode *nodeit=nodes.iterator(); + while(nodeit->hasNext()) { + EncodingNode *node=nodeit->next(); + SetIteratorEncodingEdge *edgeit=node->edges.iterator(); + while(edgeit->hasNext()) { + EncodingEdge *edge=edgeit->next(); + if (edge->numComparisons == 0) + continue; + if (edge->left == NULL || !nodes.contains(edge->left)) + continue; + if (edge->right == NULL || !nodes.contains(edge->right)) + continue; + //examine only once + if (edge->left != node) + continue; + //We have a comparison edge between two nodes in the subgraph + generateComparison(edge->left, edge->right); + } + delete edgeit; + } + delete nodeit; +} + +void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) { + Set *lset=left->s; + Set *rset=right->s; + uint lindex=0, rindex=0; + uint lSize=lset->getSize(), rSize=rset->getSize(); + uint64_t lVal=lset->getElement(lindex); + NodeValuePair nvp1(left, lVal); + EncodingValue *lev = map.get(&nvp1); + lev->inComparison = true; + uint64_t rVal=rset->getElement(rindex); + NodeValuePair nvp2(right, rVal); + EncodingValue *rev = map.get(&nvp2); + rev->inComparison = true; + EncodingValue *last = NULL; + + while(lindex < lSize || rindex < rSize) { + if (last != NULL) { + if (lev != NULL) + last->larger.push(lev); + if (rev != NULL && lev != rev) + last->larger.push(rev); + } + if (lev != rev) { + if (rev == NULL || lVal < rVal) { + if (rev != NULL) + lev->larger.push(rev); + last = lev; + if (++lindex < lSize) { + lVal=lset->getElement(lindex); + NodeValuePair nvpl(left, lVal); + lev = map.get(&nvpl); + lev->inComparison = true; + } else + lev = NULL; + } else { + if (lev != NULL) + rev->larger.push(lev); + last = rev; + if (++rindex < rSize) { + rVal=rset->getElement(rindex); + NodeValuePair nvpr(right, rVal); + rev = map.get(&nvpr); + rev->inComparison = true; + } else + rev = NULL; + } + } else { + last = lev; + if (++lindex < lSize) { + lVal=lset->getElement(lindex); + NodeValuePair nvpl(left, lVal); + lev = map.get(&nvpl); + lev->inComparison = true; + } else + lev = NULL; + + if (++rindex < rSize) { + rVal=rset->getElement(rindex); + NodeValuePair nvpr(right, rVal); + rev = map.get(&nvpr); + rev->inComparison = true; + } else + rev = NULL; + } + } +} + +void EncodingSubGraph::computeEncodingValue() { SetIteratorEncodingNode *nodeit=nodes.iterator(); while(nodeit->hasNext()) { EncodingNode *node=nodeit->next(); @@ -83,5 +179,30 @@ void EncodingSubGraph::encode() { } void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) { - + EncodingValue *ecv=new EncodingValue(value); + HashsetEncodingNode discovered; + Vector tovisit; + tovisit.push(node); + discovered.add(node); + while(tovisit.getSize()!=0) { + EncodingNode *n=tovisit.last();tovisit.pop(); + //Add encoding node to structures + ecv->nodes.add(n); + NodeValuePair *nvp=new NodeValuePair(n, value); + map.put(nvp, ecv); + SetIteratorEncodingEdge *edgeit=node->edges.iterator(); + while(edgeit->hasNext()) { + EncodingEdge *ee=edgeit->next(); + if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) { + tovisit.push(ee->left); + discovered.add(ee->left); + } + if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) { + tovisit.push(ee->right); + discovered.add(ee->right); + } + } + delete edgeit; + } } + diff --git a/src/ASTAnalyses/Encoding/subgraph.h b/src/ASTAnalyses/Encoding/subgraph.h index 5520709..bc7fdbf 100644 --- a/src/ASTAnalyses/Encoding/subgraph.h +++ b/src/ASTAnalyses/Encoding/subgraph.h @@ -13,9 +13,12 @@ class NodeValuePair { class EncodingValue { public: + EncodingValue(uint64_t _val) : value(_val), inComparison(false) {} void merge(EncodingValue *value); uint64_t value; + bool inComparison; HashsetEncodingNode nodes; + Vector larger; }; uint hashNodeValuePair(NodeValuePair *nvp); @@ -35,8 +38,10 @@ class EncodingSubGraph { uint estimateNewSize(EncodingNode *n); uint estimateNewSize(EncodingSubGraph *sg); void traverseValue(EncodingNode *node, uint64_t value); + void computeEncodingValue(); + void computeInequalities(); + void generateComparison(EncodingNode *left, EncodingNode *right); - HashsetEncodingNode nodes; NVPMap map; uint encodingSize; -- 2.34.1