2 #include "encodinggraph.h"
6 EncodingSubGraph::EncodingSubGraph() :
11 uint hashNodeValuePair(NodeValuePair *nvp) {
12 return (uint) (nvp->value ^ ((uintptr_t)nvp->node));
15 bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2) {
16 return nvp1->value == nvp2->value && nvp1->node == nvp2->node;
19 int sortEncodingValue(const void *p1, const void *p2) {
20 const EncodingValue * e1 = * (const EncodingValue **) p1;
21 const EncodingValue * e2 = * (const EncodingValue **) p2;
22 uint se1=e1->notequals.getSize();
23 uint se2=e2->notequals.getSize();
32 void EncodingSubGraph::solveEquals() {
33 Vector<EncodingValue *> toEncode;
34 Vector<bool> encodingArray;
35 SetIteratorEncodingValue *valIt=values.iterator();
36 while(valIt->hasNext()) {
37 EncodingValue *ev=valIt->next();
38 if (!ev->inComparison)
44 bsdqsort(toEncode.expose(), toEncode.getSize(), sizeof(EncodingValue *), sortEncodingValue);
45 uint toEncodeSize=toEncode.getSize();
46 for(uint i=0; i<toEncodeSize; i++) {
47 EncodingValue * ev=toEncode.get(i);
48 encodingArray.clear();
49 SetIteratorEncodingValue *conflictIt=ev->notequals.iterator();
50 while(conflictIt->hasNext()) {
51 EncodingValue * conflict=conflictIt->next();
52 if (conflict->assigned) {
53 encodingArray.setExpand(conflict->encoding, true);
58 for(;encoding<encodingArray.getSize();encoding++) {
59 //See if this is unassigned
60 if (!encodingArray.get(encoding))
63 ev->encoding = encoding;
68 void EncodingSubGraph::solveComparisons() {
69 HashsetEncodingValue discovered;
70 Vector<EncodingValue *> tovisit;
71 SetIteratorEncodingValue *valIt=values.iterator();
72 while(valIt->hasNext()) {
73 EncodingValue *ev=valIt->next();
74 if (discovered.add(ev)) {
76 while(tovisit.getSize()!=0) {
77 EncodingValue * val=tovisit.last(); tovisit.pop();
78 SetIteratorEncodingValue *nextIt=val->larger.iterator();
79 uint minVal = val->encoding + 1;
80 while(nextIt->hasNext()) {
81 EncodingValue *nextVal=nextIt->next();
82 if (nextVal->encoding < minVal) {
83 nextVal->encoding = minVal;
84 discovered.add(nextVal);
85 tovisit.push(nextVal);
95 uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
97 SetIteratorEncodingNode * nit = sg->nodes.iterator();
98 while(nit->hasNext()) {
99 EncodingNode *en = nit->next();
100 uint size=estimateNewSize(en);
108 uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
109 SetIteratorEncodingEdge * eeit = n->edges.iterator();
110 uint newsize=n->getSize();
111 while(eeit->hasNext()) {
112 EncodingEdge * ee = eeit->next();
113 if (ee->left != NULL && ee->left != n && nodes.contains(ee->left)) {
114 uint intersectSize = n->s->getUnionSize(ee->left->s);
115 if (intersectSize > newsize)
116 newsize = intersectSize;
118 if (ee->right != NULL && ee->right != n && nodes.contains(ee->right)) {
119 uint intersectSize = n->s->getUnionSize(ee->right->s);
120 if (intersectSize > newsize)
121 newsize = intersectSize;
123 if (ee->dst != NULL && ee->dst != n && nodes.contains(ee->dst)) {
124 uint intersectSize = n->s->getUnionSize(ee->dst->s);
125 if (intersectSize > newsize)
126 newsize = intersectSize;
133 void EncodingSubGraph::addNode(EncodingNode *n) {
135 uint newSize=estimateNewSize(n);
136 numElements += n->elements.getSize();
137 if (newSize > encodingSize)
138 encodingSize=newSize;
141 SetIteratorEncodingNode * EncodingSubGraph::nodeIterator() {
142 return nodes.iterator();
145 void EncodingSubGraph::encode() {
146 computeEncodingValue();
147 computeComparisons();
153 void EncodingSubGraph::computeEqualities() {
154 SetIteratorEncodingNode *nodeit=nodes.iterator();
155 while(nodeit->hasNext()) {
156 EncodingNode *node=nodeit->next();
157 generateEquals(node, node);
159 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
160 while(edgeit->hasNext()) {
161 EncodingEdge *edge=edgeit->next();
162 //skip over comparisons as we have already handled them
163 if (edge->numComparisons != 0)
165 if (edge->numEquals == 0)
167 if (edge->left == NULL || !nodes.contains(edge->left))
169 if (edge->right == NULL || !nodes.contains(edge->right))
172 if (edge->left != node)
174 //We have a comparison edge between two nodes in the subgraph
175 //For now we don't support multiple encoding values with the same encoding....
176 //So we enforce != constraints for every Set...
177 if (edge->left != edge->right)
178 generateEquals(edge->left, edge->right);
185 void EncodingSubGraph::computeComparisons() {
186 SetIteratorEncodingNode *nodeit=nodes.iterator();
187 while(nodeit->hasNext()) {
188 EncodingNode *node=nodeit->next();
189 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
190 while(edgeit->hasNext()) {
191 EncodingEdge *edge=edgeit->next();
192 if (edge->numComparisons == 0)
194 if (edge->left == NULL || !nodes.contains(edge->left))
196 if (edge->right == NULL || !nodes.contains(edge->right))
199 if (edge->left != node)
201 //We have a comparison edge between two nodes in the subgraph
202 generateComparison(edge->left, edge->right);
211 void EncodingSubGraph::orderEV(EncodingValue *earlier, EncodingValue *later) {
212 earlier->larger.add(later);
215 void EncodingSubGraph::generateEquals(EncodingNode *left, EncodingNode *right) {
218 uint lSize=lset->getSize(), rSize=rset->getSize();
219 for(uint lindex=0; lindex < lSize; lindex++) {
220 for(uint rindex=0; rindex < rSize; rindex++) {
221 uint64_t lVal=lset->getElement(lindex);
222 NodeValuePair nvp1(left, lVal);
223 EncodingValue *lev = map.get(&nvp1);
224 uint64_t rVal=rset->getElement(rindex);
225 NodeValuePair nvp2(right, rVal);
226 EncodingValue *rev = map.get(&nvp2);
228 if (lev->inComparison && rev->inComparison) {
229 //Need to assign during comparison stage...
230 //Thus promote to comparison
237 lev->notequals.add(rev);
238 rev->notequals.add(lev);
245 void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) {
248 uint lindex=0, rindex=0;
249 uint lSize=lset->getSize(), rSize=rset->getSize();
250 uint64_t lVal=lset->getElement(lindex);
251 NodeValuePair nvp1(left, lVal);
252 EncodingValue *lev = map.get(&nvp1);
253 lev->inComparison = true;
254 uint64_t rVal=rset->getElement(rindex);
255 NodeValuePair nvp2(right, rVal);
256 EncodingValue *rev = map.get(&nvp2);
257 rev->inComparison = true;
258 EncodingValue *last = NULL;
260 while(lindex < lSize || rindex < rSize) {
264 if (rev != NULL && lev != rev)
268 if (rev == NULL || lVal < rVal) {
272 if (++lindex < lSize) {
273 lVal=lset->getElement(lindex);
274 NodeValuePair nvpl(left, lVal);
275 lev = map.get(&nvpl);
276 lev->inComparison = true;
283 if (++rindex < rSize) {
284 rVal=rset->getElement(rindex);
285 NodeValuePair nvpr(right, rVal);
286 rev = map.get(&nvpr);
287 rev->inComparison = true;
293 if (++lindex < lSize) {
294 lVal=lset->getElement(lindex);
295 NodeValuePair nvpl(left, lVal);
296 lev = map.get(&nvpl);
297 lev->inComparison = true;
301 if (++rindex < rSize) {
302 rVal=rset->getElement(rindex);
303 NodeValuePair nvpr(right, rVal);
304 rev = map.get(&nvpr);
305 rev->inComparison = true;
312 void EncodingSubGraph::computeEncodingValue() {
313 SetIteratorEncodingNode *nodeit=nodes.iterator();
314 while(nodeit->hasNext()) {
315 EncodingNode *node=nodeit->next();
317 uint setSize = set->getSize();
318 for(uint i=0; i<setSize; i++) {
319 uint64_t val = set->getElement(i);
320 NodeValuePair nvp(node, val);
321 if (!map.contains(&nvp)) {
322 traverseValue(node, val);
329 void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
330 EncodingValue *ecv=new EncodingValue(value);
332 HashsetEncodingNode discovered;
333 Vector<EncodingNode *> tovisit;
335 discovered.add(node);
336 while(tovisit.getSize()!=0) {
337 EncodingNode *n=tovisit.last();tovisit.pop();
338 //Add encoding node to structures
340 NodeValuePair *nvp=new NodeValuePair(n, value);
342 SetIteratorEncodingEdge *edgeit=node->edges.iterator();
343 while(edgeit->hasNext()) {
344 EncodingEdge *ee=edgeit->next();
345 if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) {
346 tovisit.push(ee->left);
347 discovered.add(ee->left);
349 if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) {
350 tovisit.push(ee->right);
351 discovered.add(ee->right);