2 #include "encodinggraph.h"
6 EncodingSubGraph::EncodingSubGraph() :
12 uint hashNodeValuePair(NodeValuePair *nvp) {
13 return (uint) (nvp->value ^ ((uintptr_t)nvp->node));
16 bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2) {
17 return nvp1->value == nvp2->value && nvp1->node == nvp2->node;
20 int sortEncodingValue(const void *p1, const void *p2) {
21 const EncodingValue * e1 = * (const EncodingValue **) p1;
22 const EncodingValue * e2 = * (const EncodingValue **) p2;
23 uint se1=e1->notequals.getSize();
24 uint se2=e2->notequals.getSize();
33 uint EncodingSubGraph::getEncoding(EncodingNode *n, uint64_t val) {
34 NodeValuePair nvp(n, val);
35 EncodingValue *ev = map.get(&nvp);
39 void EncodingSubGraph::solveEquals() {
40 Vector<EncodingValue *> toEncode;
41 Vector<bool> encodingArray;
42 SetIteratorEncodingValue *valIt=values.iterator();
43 while(valIt->hasNext()) {
44 EncodingValue *ev=valIt->next();
45 if (!ev->inComparison)
51 bsdqsort(toEncode.expose(), toEncode.getSize(), sizeof(EncodingValue *), sortEncodingValue);
52 uint toEncodeSize=toEncode.getSize();
53 for(uint i=0; i<toEncodeSize; i++) {
54 EncodingValue * ev=toEncode.get(i);
55 encodingArray.clear();
56 SetIteratorEncodingValue *conflictIt=ev->notequals.iterator();
57 while(conflictIt->hasNext()) {
58 EncodingValue * conflict=conflictIt->next();
59 if (conflict->assigned) {
60 encodingArray.setExpand(conflict->encoding, true);
65 for(;encoding<encodingArray.getSize();encoding++) {
66 //See if this is unassigned
67 if (!encodingArray.get(encoding))
70 if (encoding > maxEncodingVal)
71 maxEncodingVal = encoding;
72 ev->encoding = encoding;
77 void EncodingSubGraph::solveComparisons() {
78 HashsetEncodingValue discovered;
79 Vector<EncodingValue *> tovisit;
80 SetIteratorEncodingValue *valIt=values.iterator();
81 while(valIt->hasNext()) {
82 EncodingValue *ev=valIt->next();
83 if (discovered.add(ev)) {
85 while(tovisit.getSize()!=0) {
86 EncodingValue * val=tovisit.last(); tovisit.pop();
87 SetIteratorEncodingValue *nextIt=val->larger.iterator();
88 uint minVal = val->encoding + 1;
89 while(nextIt->hasNext()) {
90 EncodingValue *nextVal=nextIt->next();
91 if (nextVal->encoding < minVal) {
92 if (minVal > maxEncodingVal)
93 maxEncodingVal = minVal;
94 nextVal->encoding = minVal;
95 discovered.add(nextVal);
96 tovisit.push(nextVal);
106 uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
108 SetIteratorEncodingNode * nit = sg->nodes.iterator();
109 while(nit->hasNext()) {
110 EncodingNode *en = nit->next();
111 uint size=estimateNewSize(en);
119 uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
120 SetIteratorEncodingEdge * eeit = n->edges.iterator();
121 uint newsize=n->getSize();
122 while(eeit->hasNext()) {
123 EncodingEdge * ee = eeit->next();
124 if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
125 uint intersectSize = n->s->getUnionSize(ee->left->s);
126 if (intersectSize > newsize)
127 newsize = intersectSize;
129 if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
130 uint intersectSize = n->s->getUnionSize(ee->right->s);
131 if (intersectSize > newsize)
132 newsize = intersectSize;
134 if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
135 uint intersectSize = n->s->getUnionSize(ee->dst->s);
136 if (intersectSize > newsize)
137 newsize = intersectSize;
144 void EncodingSubGraph::addNode(EncodingNode *n) {
146 uint newSize=estimateNewSize(n);
147 numElements += n->elements.getSize();
148 if (newSize > encodingSize)
149 encodingSize=newSize;
152 SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
153 return nodes.iterator();
156 void EncodingSubGraph::encode() {
157 computeEncodingValue();
158 computeComparisons();
164 void EncodingSubGraph::computeEqualities() {
165 SetIteratorEncodingNode *nodeit=nodes.iterator();
166 while(nodeit->hasNext()) {
167 EncodingNode *node=nodeit->next();
168 generateEquals(node, node);
170 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
171 while(edgeit->hasNext()) {
172 EncodingEdge *edge=edgeit->next();
173 //skip over comparisons as we have already handled them
174 if (edge->numComparisons != 0)
176 if (edge->numEquals == 0)
178 if (edge->left == NULL || !nodes.contains(edge->left))
180 if (edge->right == NULL || !nodes.contains(edge->right))
183 if (edge->left != node)
185 //We have a comparison edge between two nodes in the subgraph
186 //For now we don't support multiple encoding values with the same encoding....
187 //So we enforce != constraints for every Set...
188 if (edge->left != edge->right)
189 generateEquals(edge->left, edge->right);
196 void EncodingSubGraph::computeComparisons() {
197 SetIteratorEncodingNode *nodeit=nodes.iterator();
198 while(nodeit->hasNext()) {
199 EncodingNode *node=nodeit->next();
200 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
201 while(edgeit->hasNext()) {
202 EncodingEdge *edge=edgeit->next();
203 if (edge->numComparisons == 0)
205 if (edge->left == NULL || !nodes.contains(edge->left))
207 if (edge->right == NULL || !nodes.contains(edge->right))
210 if (edge->left != node)
212 //We have a comparison edge between two nodes in the subgraph
213 generateComparison(edge->left, edge->right);
222 void EncodingSubGraph::orderEV(EncodingValue *earlier, EncodingValue *later) {
223 earlier->larger.add(later);
226 void EncodingSubGraph::generateEquals(EncodingNode *left, EncodingNode *right) {
229 uint lSize=lset->getSize(), rSize=rset->getSize();
230 for(uint lindex=0; lindex < lSize; lindex++) {
231 for(uint rindex=0; rindex < rSize; rindex++) {
232 uint64_t lVal=lset->getElement(lindex);
233 NodeValuePair nvp1(left, lVal);
234 EncodingValue *lev = map.get(&nvp1);
235 uint64_t rVal=rset->getElement(rindex);
236 NodeValuePair nvp2(right, rVal);
237 EncodingValue *rev = map.get(&nvp2);
239 if (lev->inComparison && rev->inComparison) {
240 //Need to assign during comparison stage...
241 //Thus promote to comparison
248 lev->notequals.add(rev);
249 rev->notequals.add(lev);
256 void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) {
259 uint lindex=0, rindex=0;
260 uint lSize=lset->getSize(), rSize=rset->getSize();
261 uint64_t lVal=lset->getElement(lindex);
262 NodeValuePair nvp1(left, lVal);
263 EncodingValue *lev = map.get(&nvp1);
264 lev->inComparison = true;
265 uint64_t rVal=rset->getElement(rindex);
266 NodeValuePair nvp2(right, rVal);
267 EncodingValue *rev = map.get(&nvp2);
268 rev->inComparison = true;
269 EncodingValue *last = NULL;
271 while(lindex < lSize || rindex < rSize) {
275 if (rev != NULL && lev != rev)
279 if (rev == NULL || lVal < rVal) {
283 if (++lindex < lSize) {
284 lVal=lset->getElement(lindex);
285 NodeValuePair nvpl(left, lVal);
286 lev = map.get(&nvpl);
287 lev->inComparison = true;
294 if (++rindex < rSize) {
295 rVal=rset->getElement(rindex);
296 NodeValuePair nvpr(right, rVal);
297 rev = map.get(&nvpr);
298 rev->inComparison = true;
304 if (++lindex < lSize) {
305 lVal=lset->getElement(lindex);
306 NodeValuePair nvpl(left, lVal);
307 lev = map.get(&nvpl);
308 lev->inComparison = true;
312 if (++rindex < rSize) {
313 rVal=rset->getElement(rindex);
314 NodeValuePair nvpr(right, rVal);
315 rev = map.get(&nvpr);
316 rev->inComparison = true;
323 void EncodingSubGraph::computeEncodingValue() {
324 SetIteratorEncodingNode *nodeit=nodes.iterator();
325 while(nodeit->hasNext()) {
326 EncodingNode *node=nodeit->next();
328 uint setSize = set->getSize();
329 for(uint i=0; i<setSize; i++) {
330 uint64_t val = set->getElement(i);
331 NodeValuePair nvp(node, val);
332 if (!map.contains(&nvp)) {
333 traverseValue(node, val);
340 void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
341 EncodingValue *ecv=new EncodingValue(value);
343 HashsetEncodingNode discovered;
344 Vector<EncodingNode *> tovisit;
346 discovered.add(node);
347 while(tovisit.getSize()!=0) {
348 EncodingNode *n=tovisit.last();tovisit.pop();
349 //Add encoding node to structures
351 NodeValuePair *nvp=new NodeValuePair(n, value);
353 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
354 while(edgeit->hasNext()) {
355 EncodingEdge *ee=edgeit->next();
356 if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) {
357 tovisit.push(ee->left);
358 discovered.add(ee->left);
360 if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) {
361 tovisit.push(ee->right);
362 discovered.add(ee->right);