2 #include "encodinggraph.h"
6 EncodingSubGraph::EncodingSubGraph() :
12 EncodingSubGraph::~EncodingSubGraph() {
13 map.resetAndDeleteKeys();
14 values.resetAndDelete();
17 uint hashNodeValuePair(NodeValuePair *nvp) {
18 return (uint) (nvp->value ^ ((uintptr_t)nvp->node));
21 bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2) {
22 return nvp1->value == nvp2->value && nvp1->node == nvp2->node;
25 int sortEncodingValue(const void *p1, const void *p2) {
26 const EncodingValue *e1 = *(const EncodingValue **) p1;
27 const EncodingValue *e2 = *(const EncodingValue **) p2;
28 uint se1 = e1->notequals.getSize();
29 uint se2 = e2->notequals.getSize();
38 uint EncodingSubGraph::getEncoding(EncodingNode *n, uint64_t val) {
39 NodeValuePair nvp(n, val);
40 EncodingValue *ev = map.get(&nvp);
44 void EncodingSubGraph::solveEquals() {
45 Vector<EncodingValue *> toEncode;
46 Vector<bool> encodingArray;
47 SetIteratorEncodingValue *valIt = values.iterator();
48 while (valIt->hasNext()) {
49 EncodingValue *ev = valIt->next();
50 if (!ev->inComparison)
56 bsdqsort(toEncode.expose(), toEncode.getSize(), sizeof(EncodingValue *), sortEncodingValue);
57 uint toEncodeSize = toEncode.getSize();
58 for (uint i = 0; i < toEncodeSize; i++) {
59 EncodingValue *ev = toEncode.get(i);
60 encodingArray.clear();
61 SetIteratorEncodingValue *conflictIt = ev->notequals.iterator();
62 while (conflictIt->hasNext()) {
63 EncodingValue *conflict = conflictIt->next();
64 if (conflict->assigned) {
65 encodingArray.setExpand(conflict->encoding, true);
70 for (; encoding < encodingArray.getSize(); encoding++) {
71 //See if this is unassigned
72 if (!encodingArray.get(encoding))
75 if (encoding > maxEncodingVal)
76 maxEncodingVal = encoding;
77 ev->encoding = encoding;
82 void EncodingSubGraph::solveComparisons() {
83 HashsetEncodingValue discovered;
84 Vector<EncodingValue *> tovisit;
85 SetIteratorEncodingValue *valIt = values.iterator();
86 while (valIt->hasNext()) {
87 EncodingValue *ev = valIt->next();
88 if (discovered.add(ev)) {
90 while (tovisit.getSize() != 0) {
91 EncodingValue *val = tovisit.last(); tovisit.pop();
92 SetIteratorEncodingValue *nextIt = val->larger.iterator();
93 uint minVal = val->encoding + 1;
94 while (nextIt->hasNext()) {
95 EncodingValue *nextVal = nextIt->next();
96 if (nextVal->encoding < minVal) {
97 if (minVal > maxEncodingVal)
98 maxEncodingVal = minVal;
99 nextVal->encoding = minVal;
100 discovered.add(nextVal);
101 tovisit.push(nextVal);
111 uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
113 SetIteratorEncodingNode *nit = sg->nodes.iterator();
114 while (nit->hasNext()) {
115 EncodingNode *en = nit->next();
116 uint size = estimateNewSize(en);
124 double EncodingSubGraph::measureSimilarity(EncodingNode *node) {
127 SetIteratorEncodingNode *nit = nodes.iterator();
128 while (nit->hasNext()) {
129 EncodingNode *en = nit->next();
130 for(uint i=0; i < en->getSize(); i++){
131 intSet.add(en->getIndex(i));
134 for(uint i=0; i < node->getSize(); i++){
135 if(intSet.contains( node->getIndex(i) )){
139 // model_print("measureSimilarity:139: common=%u\t GraphSize=%u\tnodeSize=%u\tGraphSim=%f\tnodeSim=%f\n", common, intSet.getSize(), node->getSize(), 1.0*common/intSet.getSize(), 1.0*common/node->getSize());
141 return common*1.0/intSet.getSize() + common*1.0/node->getSize();
144 double EncodingSubGraph::measureSimilarity(EncodingSubGraph *sg) {
148 SetIteratorEncodingNode *nit = nodes.iterator();
149 while (nit->hasNext()) {
150 EncodingNode *en = nit->next();
151 for(uint i=0; i < en->getSize(); i++){
152 set1.add(en->getIndex(i));
156 nit = sg->nodes.iterator();
157 while (nit->hasNext()) {
158 EncodingNode *en = nit->next();
159 for(uint i=0; i < en->getSize(); i++){
160 set2.add(en->getIndex(i));
164 SetIterator64Int *setIter1 = set1.iterator();
165 while(setIter1->hasNext()){
166 uint64_t item1 = setIter1->next();
167 if( set2.contains(item1)){
172 // model_print("measureSimilarity:139: common=%u\tGraphSize1=%u\tGraphSize2=%u\tGraphSize1=%f\tGraphSize2=%f\n", common, set1.getSize(), set2.getSize(), 1.0*common/set1.getSize(), 1.0*common/set2.getSize());
173 return common*1.0/set1.getSize() + common*1.0/set2.getSize();
176 uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
177 SetIteratorEncodingEdge *eeit = n->edges.iterator();
178 uint newsize = n->getSize();
179 while (eeit->hasNext()) {
180 EncodingEdge *ee = eeit->next();
181 if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
182 uint intersectSize = n->s->getUnionSize(ee->left->s);
183 if (intersectSize > newsize)
184 newsize = intersectSize;
186 if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
187 uint intersectSize = n->s->getUnionSize(ee->right->s);
188 if (intersectSize > newsize)
189 newsize = intersectSize;
191 if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
192 uint intersectSize = n->s->getUnionSize(ee->dst->s);
193 if (intersectSize > newsize)
194 newsize = intersectSize;
201 void EncodingSubGraph::addNode(EncodingNode *n) {
203 uint newSize = estimateNewSize(n);
204 numElements += n->elements.getSize();
205 if (newSize > encodingSize)
206 encodingSize = newSize;
209 SetIteratorEncodingNode *EncodingSubGraph::nodeIterator() {
210 return nodes.iterator();
213 void EncodingSubGraph::encode() {
214 computeEncodingValue();
215 computeComparisons();
221 void EncodingSubGraph::computeEqualities() {
222 SetIteratorEncodingNode *nodeit = nodes.iterator();
223 while (nodeit->hasNext()) {
224 EncodingNode *node = nodeit->next();
225 generateEquals(node, node);
227 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
228 while (edgeit->hasNext()) {
229 EncodingEdge *edge = edgeit->next();
230 //skip over comparisons as we have already handled them
231 if (edge->numComparisons != 0)
233 if (edge->numEquals == 0)
235 if (edge->left == NULL || !nodes.contains(edge->left))
237 if (edge->right == NULL || !nodes.contains(edge->right))
240 if (edge->left != node)
242 //We have a comparison edge between two nodes in the subgraph
243 //For now we don't support multiple encoding values with the same encoding....
244 //So we enforce != constraints for every Set...
245 if (edge->left != edge->right)
246 generateEquals(edge->left, edge->right);
253 void EncodingSubGraph::computeComparisons() {
254 SetIteratorEncodingNode *nodeit = nodes.iterator();
255 while (nodeit->hasNext()) {
256 EncodingNode *node = nodeit->next();
257 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
258 while (edgeit->hasNext()) {
259 EncodingEdge *edge = edgeit->next();
260 if (edge->numComparisons == 0)
262 if (edge->left == NULL || !nodes.contains(edge->left))
264 if (edge->right == NULL || !nodes.contains(edge->right))
267 if (edge->left != node)
269 //We have a comparison edge between two nodes in the subgraph
270 generateComparison(edge->left, edge->right);
277 void EncodingSubGraph::orderEV(EncodingValue *earlier, EncodingValue *later) {
278 earlier->larger.add(later);
281 void EncodingSubGraph::generateEquals(EncodingNode *left, EncodingNode *right) {
283 Set *rset = right->s;
284 uint lSize = lset->getSize(), rSize = rset->getSize();
285 for (uint lindex = 0; lindex < lSize; lindex++) {
286 for (uint rindex = 0; rindex < rSize; rindex++) {
287 uint64_t lVal = lset->getElement(lindex);
288 NodeValuePair nvp1(left, lVal);
289 EncodingValue *lev = map.get(&nvp1);
290 uint64_t rVal = rset->getElement(rindex);
291 NodeValuePair nvp2(right, rVal);
292 EncodingValue *rev = map.get(&nvp2);
294 if (lev->inComparison && rev->inComparison) {
295 //Need to assign during comparison stage...
296 //Thus promote to comparison
303 lev->notequals.add(rev);
304 rev->notequals.add(lev);
311 void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) {
313 Set *rset = right->s;
314 uint lindex = 0, rindex = 0;
315 uint lSize = lset->getSize(), rSize = rset->getSize();
316 uint64_t lVal = lset->getElement(lindex);
317 NodeValuePair nvp1(left, lVal);
318 EncodingValue *lev = map.get(&nvp1);
319 lev->inComparison = true;
320 uint64_t rVal = rset->getElement(rindex);
321 NodeValuePair nvp2(right, rVal);
322 EncodingValue *rev = map.get(&nvp2);
323 rev->inComparison = true;
324 EncodingValue *last = NULL;
326 while (lindex < lSize || rindex < rSize) {
330 if (rev != NULL && lev != rev)
335 (lev != NULL && lVal < rVal)) {
339 if (++lindex < lSize) {
340 lVal = lset->getElement(lindex);
341 NodeValuePair nvpl(left, lVal);
342 lev = map.get(&nvpl);
343 lev->inComparison = true;
350 if (++rindex < rSize) {
351 rVal = rset->getElement(rindex);
352 NodeValuePair nvpr(right, rVal);
353 rev = map.get(&nvpr);
354 rev->inComparison = true;
360 if (++lindex < lSize) {
361 lVal = lset->getElement(lindex);
362 NodeValuePair nvpl(left, lVal);
363 lev = map.get(&nvpl);
364 lev->inComparison = true;
368 if (++rindex < rSize) {
369 rVal = rset->getElement(rindex);
370 NodeValuePair nvpr(right, rVal);
371 rev = map.get(&nvpr);
372 rev->inComparison = true;
379 void EncodingSubGraph::computeEncodingValue() {
380 SetIteratorEncodingNode *nodeit = nodes.iterator();
381 while (nodeit->hasNext()) {
382 EncodingNode *node = nodeit->next();
384 uint setSize = set->getSize();
385 for (uint i = 0; i < setSize; i++) {
386 uint64_t val = set->getElement(i);
387 NodeValuePair nvp(node, val);
388 if (!map.contains(&nvp)) {
389 traverseValue(node, val);
396 void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
397 EncodingValue *ecv = new EncodingValue(value);
399 HashsetEncodingNode discovered;
400 Vector<EncodingNode *> tovisit;
402 discovered.add(node);
403 while (tovisit.getSize() != 0) {
404 EncodingNode *n = tovisit.last();tovisit.pop();
405 //Add encoding node to structures
407 NodeValuePair *nvp = new NodeValuePair(n, value);
409 SetIteratorEncodingEdge *edgeit = n->edges.iterator();
410 while (edgeit->hasNext()) {
411 EncodingEdge *ee = edgeit->next();
412 if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) {
413 tovisit.push(ee->left);
414 discovered.add(ee->left);
416 if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) {
417 tovisit.push(ee->right);
418 discovered.add(ee->right);