2 #include "encodinggraph.h"
6 EncodingSubGraph::EncodingSubGraph() :
10 EncodingSubGraph::~EncodingSubGraph() {
11 map.resetAndDeleteKeys();
12 values.resetAndDelete();
15 uint hashNodeValuePair(NodeValuePair *nvp) {
16 return (uint) (nvp->value ^ ((uintptr_t)nvp->node));
19 bool equalsNodeValuePair(NodeValuePair *nvp1, NodeValuePair *nvp2) {
20 return nvp1->value == nvp2->value && nvp1->node == nvp2->node;
23 int sortEncodingValue(const void *p1, const void *p2) {
24 const EncodingValue *e1 = *(const EncodingValue **) p1;
25 const EncodingValue *e2 = *(const EncodingValue **) p2;
26 uint se1 = e1->notequals.getSize();
27 uint se2 = e2->notequals.getSize();
36 uint EncodingSubGraph::getEncoding(EncodingNode *n, uint64_t val) {
37 NodeValuePair nvp(n, val);
38 EncodingValue *ev = map.get(&nvp);
42 void EncodingSubGraph::solveEquals() {
43 Vector<EncodingValue *> toEncode;
44 Vector<bool> encodingArray;
45 SetIteratorEncodingValue *valIt = values.iterator();
46 while (valIt->hasNext()) {
47 EncodingValue *ev = valIt->next();
48 if (!ev->inComparison)
54 bsdqsort(toEncode.expose(), toEncode.getSize(), sizeof(EncodingValue *), sortEncodingValue);
55 uint toEncodeSize = toEncode.getSize();
56 for (uint i = 0; i < toEncodeSize; i++) {
57 EncodingValue *ev = toEncode.get(i);
58 encodingArray.clear();
59 SetIteratorEncodingValue *conflictIt = ev->notequals.iterator();
60 while (conflictIt->hasNext()) {
61 EncodingValue *conflict = conflictIt->next();
62 if (conflict->assigned) {
63 encodingArray.setExpand(conflict->encoding, true);
68 for (; encoding < encodingArray.getSize(); encoding++) {
69 //See if this is unassigned
70 if (!encodingArray.get(encoding))
73 if (encoding > maxEncodingVal)
74 maxEncodingVal = encoding;
75 ev->encoding = encoding;
80 void EncodingSubGraph::solveComparisons() {
81 HashsetEncodingValue discovered;
82 Vector<EncodingValue *> tovisit;
83 SetIteratorEncodingValue *valIt = values.iterator();
84 while (valIt->hasNext()) {
85 EncodingValue *ev = valIt->next();
86 if (discovered.add(ev)) {
88 while (tovisit.getSize() != 0) {
89 EncodingValue *val = tovisit.last(); tovisit.pop();
90 SetIteratorEncodingValue *nextIt = val->larger.iterator();
91 uint minVal = val->encoding + 1;
92 while (nextIt->hasNext()) {
93 EncodingValue *nextVal = nextIt->next();
94 if (nextVal->encoding < minVal) {
95 if (minVal > maxEncodingVal)
96 maxEncodingVal = minVal;
97 nextVal->encoding = minVal;
98 discovered.add(nextVal);
99 tovisit.push(nextVal);
109 uint EncodingSubGraph::estimateNewSize(EncodingSubGraph *sg) {
110 uint newSize = sg->allValues.getSize() + allValues.getSize();
111 SetIterator64Int *it = sg->allValues.iterator();
113 while (it->hasNext()) {
114 uint64_t val = it->next();
115 if (allValues.contains(val))
122 double EncodingSubGraph::measureSimilarity(EncodingNode *node) {
124 uint size = node->getSize();
125 for (uint i = 0; i < size; i++) {
126 uint64_t val = node->getIndex(i);
127 if (allValues.contains(val))
130 return common * 1.0 / allValues.getSize() + common * 1.0 / node->getSize();
133 double EncodingSubGraph::measureSimilarity(EncodingSubGraph *sg) {
135 SetIterator64Int *setIter1 = allValues.iterator();
136 while (setIter1->hasNext()) {
137 uint64_t item1 = setIter1->next();
138 if ( sg->allValues.contains(item1)) {
143 return common * 1.0 / allValues.getSize() + common * 1.0 / sg->allValues.getSize();
146 uint EncodingSubGraph::estimateNewSize(EncodingNode *n) {
147 uint nSize = n->getSize();
148 uint newSize = allValues.getSize() + nSize;
149 for (uint i = 0; i < nSize; i++) {
150 if (allValues.contains(n->getIndex(i)))
156 uint EncodingSubGraph::numValues() {
157 return allValues.getSize();
160 void EncodingSubGraph::addNode(EncodingNode *n) {
162 uint size = n->getSize();
163 for (uint i = 0; i < size; i++)
164 allValues.add(n->getIndex(i));
167 SetIteratorEncodingNode *EncodingSubGraph::nodeIterator() {
168 return nodes.iterator();
171 void EncodingSubGraph::encode() {
172 computeEncodingValue();
173 computeComparisons();
179 void EncodingSubGraph::computeEqualities() {
180 SetIteratorEncodingNode *nodeit = nodes.iterator();
181 while (nodeit->hasNext()) {
182 EncodingNode *node = nodeit->next();
183 generateEquals(node, node);
185 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
186 while (edgeit->hasNext()) {
187 EncodingEdge *edge = edgeit->next();
188 //skip over comparisons as we have already handled them
189 if (edge->numComparisons != 0)
191 if (edge->numEquals == 0)
193 if (edge->left == NULL || !nodes.contains(edge->left))
195 if (edge->right == NULL || !nodes.contains(edge->right))
198 if (edge->left != node)
200 //We have a comparison edge between two nodes in the subgraph
201 //For now we don't support multiple encoding values with the same encoding....
202 //So we enforce != constraints for every Set...
203 if (edge->left != edge->right)
204 generateEquals(edge->left, edge->right);
211 void EncodingSubGraph::computeComparisons() {
212 SetIteratorEncodingNode *nodeit = nodes.iterator();
213 while (nodeit->hasNext()) {
214 EncodingNode *node = nodeit->next();
215 SetIteratorEncodingEdge *edgeit = node->edges.iterator();
216 while (edgeit->hasNext()) {
217 EncodingEdge *edge = edgeit->next();
218 if (edge->numComparisons == 0)
220 if (edge->left == NULL || !nodes.contains(edge->left))
222 if (edge->right == NULL || !nodes.contains(edge->right))
225 if (edge->left != node)
227 //We have a comparison edge between two nodes in the subgraph
228 generateComparison(edge->left, edge->right);
235 void EncodingSubGraph::orderEV(EncodingValue *earlier, EncodingValue *later) {
236 earlier->larger.add(later);
239 void EncodingSubGraph::generateEquals(EncodingNode *left, EncodingNode *right) {
241 Set *rset = right->s;
242 uint lSize = lset->getSize(), rSize = rset->getSize();
243 for (uint lindex = 0; lindex < lSize; lindex++) {
244 for (uint rindex = 0; rindex < rSize; rindex++) {
245 uint64_t lVal = lset->getElement(lindex);
246 NodeValuePair nvp1(left, lVal);
247 EncodingValue *lev = map.get(&nvp1);
248 uint64_t rVal = rset->getElement(rindex);
249 NodeValuePair nvp2(right, rVal);
250 EncodingValue *rev = map.get(&nvp2);
252 if (lev->inComparison && rev->inComparison) {
253 //Need to assign during comparison stage...
254 //Thus promote to comparison
261 lev->notequals.add(rev);
262 rev->notequals.add(lev);
269 void EncodingSubGraph::generateComparison(EncodingNode *left, EncodingNode *right) {
271 Set *rset = right->s;
272 uint lindex = 0, rindex = 0;
273 uint lSize = lset->getSize(), rSize = rset->getSize();
274 uint64_t lVal = lset->getElement(lindex);
275 NodeValuePair nvp1(left, lVal);
276 EncodingValue *lev = map.get(&nvp1);
277 lev->inComparison = true;
278 uint64_t rVal = rset->getElement(rindex);
279 NodeValuePair nvp2(right, rVal);
280 EncodingValue *rev = map.get(&nvp2);
281 rev->inComparison = true;
282 EncodingValue *last = NULL;
284 while (lindex < lSize || rindex < rSize) {
288 if (rev != NULL && lev != rev)
293 (lev != NULL && lVal < rVal)) {
297 if (++lindex < lSize) {
298 lVal = lset->getElement(lindex);
299 NodeValuePair nvpl(left, lVal);
300 lev = map.get(&nvpl);
301 lev->inComparison = true;
308 if (++rindex < rSize) {
309 rVal = rset->getElement(rindex);
310 NodeValuePair nvpr(right, rVal);
311 rev = map.get(&nvpr);
312 rev->inComparison = true;
318 if (++lindex < lSize) {
319 lVal = lset->getElement(lindex);
320 NodeValuePair nvpl(left, lVal);
321 lev = map.get(&nvpl);
322 lev->inComparison = true;
326 if (++rindex < rSize) {
327 rVal = rset->getElement(rindex);
328 NodeValuePair nvpr(right, rVal);
329 rev = map.get(&nvpr);
330 rev->inComparison = true;
337 void EncodingSubGraph::computeEncodingValue() {
338 SetIteratorEncodingNode *nodeit = nodes.iterator();
339 while (nodeit->hasNext()) {
340 EncodingNode *node = nodeit->next();
342 uint setSize = set->getSize();
343 for (uint i = 0; i < setSize; i++) {
344 uint64_t val = set->getElement(i);
345 NodeValuePair nvp(node, val);
346 if (!map.contains(&nvp)) {
347 traverseValue(node, val);
354 void EncodingSubGraph::traverseValue(EncodingNode *node, uint64_t value) {
355 EncodingValue *ecv = new EncodingValue(value);
357 HashsetEncodingNode discovered;
358 Vector<EncodingNode *> tovisit;
360 discovered.add(node);
361 while (tovisit.getSize() != 0) {
362 EncodingNode *n = tovisit.last();tovisit.pop();
363 //Add encoding node to structures
365 NodeValuePair *nvp = new NodeValuePair(n, value);
367 SetIteratorEncodingEdge *edgeit = n->edges.iterator();
368 while (edgeit->hasNext()) {
369 EncodingEdge *ee = edgeit->next();
370 if (!discovered.contains(ee->left) && nodes.contains(ee->left) && ee->left->s->exists(value)) {
371 tovisit.push(ee->left);
372 discovered.add(ee->left);
374 if (!discovered.contains(ee->right) && nodes.contains(ee->right) && ee->right->s->exists(value)) {
375 tovisit.push(ee->right);
376 discovered.add(ee->right);