1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5#include "jitpch.h"
6#ifdef _MSC_VER
7#pragma hdrstop
8#endif
9
10// --------------------------------------------------------------------
11// --------------------------------------------------------------------
12
13#ifdef DEBUG
14void hashBvNode::dump()
15{
16 printf("base: %d { ", baseIndex);
17 this->foreachBit(pBit);
18 printf("}\n");
19}
20#endif // DEBUG
21
22void hashBvNode::Reconstruct(indexType base)
23{
24 baseIndex = base;
25
26 assert(!(baseIndex % BITS_PER_NODE));
27
28 for (int i = 0; i < this->numElements(); i++)
29 {
30 elements[i] = 0;
31 }
32 next = nullptr;
33}
34
35hashBvNode::hashBvNode(indexType base)
36{
37 this->Reconstruct(base);
38}
39
40hashBvNode* hashBvNode::Create(indexType base, Compiler* compiler)
41{
42 hashBvNode* result = nullptr;
43
44 if (compiler->hbvGlobalData.hbvNodeFreeList)
45 {
46 result = compiler->hbvGlobalData.hbvNodeFreeList;
47 compiler->hbvGlobalData.hbvNodeFreeList = result->next;
48 }
49 else
50 {
51 result = new (compiler, CMK_hashBv) hashBvNode;
52 }
53 result->Reconstruct(base);
54 return result;
55}
56
57void hashBvNode::freeNode(hashBvGlobalData* glob)
58{
59 this->next = glob->hbvNodeFreeList;
60 glob->hbvNodeFreeList = this;
61}
62
63void hashBvNode::setBit(indexType base)
64{
65 assert(base >= baseIndex);
66 assert(base - baseIndex < BITS_PER_NODE);
67
68 base -= baseIndex;
69 indexType elem = base / BITS_PER_ELEMENT;
70 indexType posi = base % BITS_PER_ELEMENT;
71
72 elements[elem] |= indexType(1) << posi;
73}
74
75void hashBvNode::setLowest(indexType numToSet)
76{
77 assert(numToSet <= BITS_PER_NODE);
78
79 int elemIndex = 0;
80 while (numToSet > BITS_PER_ELEMENT)
81 {
82 elements[elemIndex] = ~(elemType(0));
83 numToSet -= BITS_PER_ELEMENT;
84 elemIndex++;
85 }
86 if (numToSet)
87 {
88 elemType allOnes = ~(elemType(0));
89 int numToShift = (int)(BITS_PER_ELEMENT - numToSet);
90 elements[elemIndex] = allOnes >> numToShift;
91 }
92}
93
94void hashBvNode::clrBit(indexType base)
95{
96 assert(base >= baseIndex);
97 assert(base - baseIndex < BITS_PER_NODE);
98
99 base -= baseIndex;
100 indexType elem = base / BITS_PER_ELEMENT;
101 indexType posi = base % BITS_PER_ELEMENT;
102
103 elements[elem] &= ~(indexType(1) << posi);
104}
105
106bool hashBvNode::belongsIn(indexType index)
107{
108 if (index < baseIndex)
109 {
110 return false;
111 }
112 if (index >= baseIndex + BITS_PER_NODE)
113 {
114 return false;
115 }
116 return true;
117}
118
119int countBitsInWord(unsigned int bits)
120{
121 // In-place adder tree: perform 16 1-bit adds, 8 2-bit adds,
122 // 4 4-bit adds, 2 8=bit adds, and 1 16-bit add.
123 bits = ((bits >> 1) & 0x55555555) + (bits & 0x55555555);
124 bits = ((bits >> 2) & 0x33333333) + (bits & 0x33333333);
125 bits = ((bits >> 4) & 0x0F0F0F0F) + (bits & 0x0F0F0F0F);
126 bits = ((bits >> 8) & 0x00FF00FF) + (bits & 0x00FF00FF);
127 bits = ((bits >> 16) & 0x0000FFFF) + (bits & 0x0000FFFF);
128 return (int)bits;
129}
130
131int countBitsInWord(unsigned __int64 bits)
132{
133 bits = ((bits >> 1) & 0x5555555555555555) + (bits & 0x5555555555555555);
134 bits = ((bits >> 2) & 0x3333333333333333) + (bits & 0x3333333333333333);
135 bits = ((bits >> 4) & 0x0F0F0F0F0F0F0F0F) + (bits & 0x0F0F0F0F0F0F0F0F);
136 bits = ((bits >> 8) & 0x00FF00FF00FF00FF) + (bits & 0x00FF00FF00FF00FF);
137 bits = ((bits >> 16) & 0x0000FFFF0000FFFF) + (bits & 0x0000FFFF0000FFFF);
138 bits = ((bits >> 32) & 0x00000000FFFFFFFF) + (bits & 0x00000000FFFFFFFF);
139 return (int)bits;
140}
141
142int hashBvNode::countBits()
143{
144 int result = 0;
145
146 for (int i = 0; i < this->numElements(); i++)
147 {
148 elemType bits = elements[i];
149
150 result += countBitsInWord(bits);
151
152 result += (int)bits;
153 }
154 return result;
155}
156
157bool hashBvNode::anyBits()
158{
159 for (int i = 0; i < this->numElements(); i++)
160 {
161 if (elements[i])
162 {
163 return true;
164 }
165 }
166 return false;
167}
168
169bool hashBvNode::getBit(indexType base)
170{
171 assert(base >= baseIndex);
172 assert(base - baseIndex < BITS_PER_NODE);
173 base -= baseIndex;
174
175 indexType elem = base / BITS_PER_ELEMENT;
176 indexType posi = base % BITS_PER_ELEMENT;
177
178 if (elements[elem] & (indexType(1) << posi))
179 {
180 return true;
181 }
182 else
183 {
184 return false;
185 }
186}
187
188bool hashBvNode::anySet()
189{
190 for (int i = 0; i < this->numElements(); i++)
191 {
192 if (elements[i])
193 {
194 return true;
195 }
196 }
197 return false;
198}
199
200void hashBvNode::copyFrom(hashBvNode* other)
201{
202 this->baseIndex = other->baseIndex;
203 for (int i = 0; i < this->numElements(); i++)
204 {
205 this->elements[i] = other->elements[i];
206 }
207}
208
209void hashBvNode::foreachBit(bitAction a)
210{
211 indexType base;
212 for (int i = 0; i < this->numElements(); i++)
213 {
214 base = baseIndex + i * BITS_PER_ELEMENT;
215 elemType e = elements[i];
216 while (e)
217 {
218 if (e & 1)
219 {
220 a(base);
221 }
222 e >>= 1;
223 base++;
224 }
225 }
226}
227
228elemType hashBvNode::AndWithChange(hashBvNode* other)
229{
230 elemType result = 0;
231
232 for (int i = 0; i < this->numElements(); i++)
233 {
234 elemType src = this->elements[i];
235 elemType dst;
236
237 dst = src & other->elements[i];
238 result |= src ^ dst;
239 this->elements[i] = dst;
240 }
241 return result;
242}
243
244elemType hashBvNode::OrWithChange(hashBvNode* other)
245{
246 elemType result = 0;
247
248 for (int i = 0; i < this->numElements(); i++)
249 {
250 elemType src = this->elements[i];
251 elemType dst;
252
253 dst = src | other->elements[i];
254 result |= src ^ dst;
255 this->elements[i] = dst;
256 }
257 return result;
258}
259
260elemType hashBvNode::XorWithChange(hashBvNode* other)
261{
262 elemType result = 0;
263
264 for (int i = 0; i < this->numElements(); i++)
265 {
266 elemType src = this->elements[i];
267 elemType dst;
268
269 dst = src ^ other->elements[i];
270 result |= src ^ dst;
271 this->elements[i] = dst;
272 }
273 return result;
274}
275
276elemType hashBvNode::SubtractWithChange(hashBvNode* other)
277{
278 elemType result = 0;
279
280 for (int i = 0; i < this->numElements(); i++)
281 {
282 elemType src = this->elements[i];
283 elemType dst;
284
285 dst = src & ~other->elements[i];
286 result |= src ^ dst;
287 this->elements[i] = dst;
288 }
289 return result;
290}
291
292bool hashBvNode::Intersects(hashBvNode* other)
293{
294 for (int i = 0; i < this->numElements(); i++)
295 {
296 if ((this->elements[i] & other->elements[i]) != 0)
297 {
298 return true;
299 }
300 }
301
302 return false;
303}
304
305void hashBvNode::AndWith(hashBvNode* other)
306{
307 for (int i = 0; i < this->numElements(); i++)
308 {
309 this->elements[i] &= other->elements[i];
310 }
311}
312
313void hashBvNode::OrWith(hashBvNode* other)
314{
315 for (int i = 0; i < this->numElements(); i++)
316 {
317 this->elements[i] |= other->elements[i];
318 }
319}
320
321void hashBvNode::XorWith(hashBvNode* other)
322{
323 for (int i = 0; i < this->numElements(); i++)
324 {
325 this->elements[i] ^= other->elements[i];
326 }
327}
328
329void hashBvNode::Subtract(hashBvNode* other)
330{
331 for (int i = 0; i < this->numElements(); i++)
332 {
333 this->elements[i] &= ~other->elements[i];
334 }
335}
336
337bool hashBvNode::sameAs(hashBvNode* other)
338{
339 if (this->baseIndex != other->baseIndex)
340 {
341 return false;
342 }
343
344 for (int i = 0; i < this->numElements(); i++)
345 {
346 if (this->elements[i] != other->elements[i])
347 {
348 return false;
349 }
350 }
351
352 return true;
353}
354
355// --------------------------------------------------------------------
356// --------------------------------------------------------------------
357
358hashBv::hashBv(Compiler* comp)
359{
360 this->compiler = comp;
361 this->log2_hashSize = 0;
362
363 int hts = hashtable_size();
364 nodeArr = getNewVector(hts);
365
366 for (int i = 0; i < hts; i++)
367 {
368 nodeArr[i] = nullptr;
369 }
370 this->numNodes = 0;
371}
372
373hashBv* hashBv::Create(Compiler* compiler)
374{
375 hashBv* result;
376 hashBvGlobalData* gd = &compiler->hbvGlobalData;
377
378 if (hbvFreeList(gd))
379 {
380 result = hbvFreeList(gd);
381 hbvFreeList(gd) = result->next;
382 assert(result->nodeArr);
383 }
384 else
385 {
386 result = new (compiler, CMK_hashBv) hashBv(compiler);
387 memset(result, 0, sizeof(hashBv));
388 result->nodeArr = result->initialVector;
389 }
390
391 result->compiler = compiler;
392 result->log2_hashSize = 0;
393 result->numNodes = 0;
394
395 return result;
396}
397
398void hashBv::Init(Compiler* compiler)
399{
400 memset(&compiler->hbvGlobalData, 0, sizeof(hashBvGlobalData));
401}
402
403hashBvGlobalData* hashBv::globalData()
404{
405 return &compiler->hbvGlobalData;
406}
407
408hashBvNode** hashBv::getNewVector(int vectorLength)
409{
410 assert(vectorLength > 0);
411 assert(isPow2(vectorLength));
412
413 hashBvNode** newVector = new (compiler, CMK_hashBv) hashBvNode*[vectorLength]();
414 return newVector;
415}
416
417hashBvNode*& hashBv::nodeFreeList(hashBvGlobalData* data)
418{
419 return data->hbvNodeFreeList;
420}
421
422hashBv*& hashBv::hbvFreeList(hashBvGlobalData* data)
423{
424 return data->hbvFreeList;
425}
426
427void hashBv::hbvFree()
428{
429 Compiler* comp = this->compiler;
430
431 int hts = hashtable_size();
432 for (int i = 0; i < hts; i++)
433 {
434 while (nodeArr[i])
435 {
436 hashBvNode* curr = nodeArr[i];
437 nodeArr[i] = curr->next;
438 curr->freeNode(globalData());
439 }
440 }
441 // keep the vector attached because the whole thing is freelisted
442 // plus you don't even know if it's freeable
443
444 this->next = hbvFreeList(globalData());
445 hbvFreeList(globalData()) = this;
446}
447
448hashBv* hashBv::CreateFrom(hashBv* other, Compiler* comp)
449{
450 hashBv* result = hashBv::Create(comp);
451 result->copyFrom(other, comp);
452 return result;
453}
454
455void hashBv::MergeLists(hashBvNode** root1, hashBvNode** root2)
456{
457}
458
459bool hashBv::TooSmall()
460{
461 return this->numNodes > this->hashtable_size() * 4;
462}
463
464bool hashBv::TooBig()
465{
466 return this->hashtable_size() > this->numNodes * 4;
467}
468
469int hashBv::getNodeCount()
470{
471 int size = hashtable_size();
472 int result = 0;
473
474 for (int i = 0; i < size; i++)
475 {
476 hashBvNode* last = nodeArr[i];
477
478 while (last)
479 {
480 last = last->next;
481 result++;
482 }
483 }
484 return result;
485}
486
487bool hashBv::IsValid()
488{
489 int size = hashtable_size();
490 // is power of 2
491 assert(((size - 1) & size) == 0);
492
493 for (int i = 0; i < size; i++)
494 {
495 hashBvNode* last = nodeArr[i];
496 hashBvNode* curr;
497 int lastIndex = -1;
498
499 while (last)
500 {
501 // the node has been hashed correctly
502 assert((int)last->baseIndex > lastIndex);
503 lastIndex = (int)last->baseIndex;
504 assert(i == getHashForIndex(last->baseIndex, size));
505 curr = last->next;
506 // the order is monotonically increasing bases
507 if (curr)
508 {
509 assert(curr->baseIndex > last->baseIndex);
510 }
511 last = curr;
512 }
513 }
514 return true;
515}
516
517void hashBv::Resize()
518{
519 // resize to 'optimal' size
520
521 this->Resize(this->numNodes);
522}
523
524void hashBv::Resize(int newSize)
525{
526 assert(newSize > 0);
527 newSize = nearest_pow2(newSize);
528
529 int oldSize = hashtable_size();
530
531 if (newSize == oldSize)
532 {
533 return;
534 }
535
536 int log2_newSize = genLog2((unsigned)newSize);
537
538 hashBvNode** newNodes = this->getNewVector(newSize);
539
540 hashBvNode*** insertionPoints = (hashBvNode***)alloca(sizeof(hashBvNode*) * newSize);
541 memset(insertionPoints, 0, sizeof(hashBvNode*) * newSize);
542
543 for (int i = 0; i < newSize; i++)
544 {
545 insertionPoints[i] = &(newNodes[i]);
546 }
547
548 if (newSize > oldSize)
549 {
550 // for each src list, expand it into multiple dst lists
551 for (int i = 0; i < oldSize; i++)
552 {
553 hashBvNode* next = nodeArr[i];
554
555 while (next)
556 {
557 hashBvNode* curr = next;
558 next = curr->next;
559 int destination = getHashForIndex(curr->baseIndex, newSize);
560
561 // ...
562
563 // stick the current node on the end of the selected list
564 *(insertionPoints[destination]) = curr;
565 insertionPoints[destination] = &(curr->next);
566 curr->next = nullptr;
567 }
568 }
569 nodeArr = newNodes;
570 log2_hashSize = (unsigned short)log2_newSize;
571 }
572 else if (oldSize > newSize)
573 {
574 int shrinkFactor = oldSize / newSize;
575
576 // shrink multiple lists into one list
577 // more efficient ways to do this but...
578 // if the lists are long, you shouldn't be shrinking.
579 for (int i = 0; i < oldSize; i++)
580 {
581 hashBvNode* next = nodeArr[i];
582
583 if (next)
584 {
585 // all nodes in this list should have the same destination list
586 int destination = getHashForIndex(next->baseIndex, newSize);
587 hashBvNode** insertionPoint = &newNodes[destination];
588 do
589 {
590 hashBvNode* curr = next;
591 // figure out where to insert it
592 while (*insertionPoint && (*insertionPoint)->baseIndex < curr->baseIndex)
593 {
594 insertionPoint = &((*insertionPoint)->next);
595 }
596 next = curr->next;
597
598 hashBvNode* temp = *insertionPoint;
599 *insertionPoint = curr;
600 curr->next = temp;
601
602 } while (next);
603 }
604 }
605 nodeArr = newNodes;
606 log2_hashSize = (unsigned short)log2_newSize;
607 }
608 else
609 {
610 // same size
611 assert(oldSize == newSize);
612 }
613 assert(this->IsValid());
614}
615
616#ifdef DEBUG
617void hashBv::dump()
618{
619 bool first = true;
620 indexType index;
621
622 // uncomment to print internal implementation details
623 // DBEXEC(TRUE, printf("[%d(%d)(nodes:%d)]{ ", hashtable_size(), countBits(), this->numNodes));
624
625 printf("{");
626 FOREACH_HBV_BIT_SET(index, this)
627 {
628 if (!first)
629 {
630 printf(" ");
631 }
632 printf("%d", index);
633 first = false;
634 }
635 NEXT_HBV_BIT_SET;
636 printf("}\n");
637}
638
639void hashBv::dumpFancy()
640{
641 indexType index;
642 indexType last_1 = -1;
643 indexType last_0 = -1;
644
645 printf("{");
646 printf("count:%d", this->countBits());
647 FOREACH_HBV_BIT_SET(index, this)
648 {
649 if (last_1 != index - 1)
650 {
651 if (last_0 + 1 != last_1)
652 {
653 printf(" %d-%d", last_0 + 1, last_1);
654 }
655 else
656 {
657 printf(" %d", last_1);
658 }
659 last_0 = index - 1;
660 }
661 last_1 = index;
662 }
663 NEXT_HBV_BIT_SET;
664
665 // Print the last one
666 if (last_0 + 1 != last_1)
667 {
668 printf(" %d-%d", last_0 + 1, last_1);
669 }
670 else
671 {
672 printf(" %d", last_1);
673 }
674
675 printf("}\n");
676}
677#endif // DEBUG
678
679void hashBv::removeNodeAtBase(indexType index)
680{
681 hashBvNode** insertionPoint = this->getInsertionPointForIndex(index);
682
683 hashBvNode* node = *insertionPoint;
684
685 // make sure that we were called to remove something
686 // that really was there
687 assert(node);
688
689 // splice it out
690 *insertionPoint = node->next;
691 this->numNodes--;
692}
693
694int hashBv::getHashForIndex(indexType index, int table_size)
695{
696 indexType hashIndex;
697
698 hashIndex = index >> LOG2_BITS_PER_NODE;
699 hashIndex &= (table_size - 1);
700
701 return (int)hashIndex;
702}
703
704int hashBv::getRehashForIndex(indexType thisIndex, int thisTableSize, int newTableSize)
705{
706 assert(0);
707 return 0;
708}
709
710hashBvNode** hashBv::getInsertionPointForIndex(indexType index)
711{
712 indexType indexInNode;
713 indexType hashIndex;
714 indexType baseIndex;
715
716 hashBvNode* result;
717
718 hashIndex = getHashForIndex(index, hashtable_size());
719
720 baseIndex = index & ~(BITS_PER_NODE - 1);
721 indexInNode = index & (BITS_PER_NODE - 1);
722
723 // printf("(%x) : hsh=%x, base=%x, index=%x\n", index,
724 // hashIndex, baseIndex, indexInNode);
725
726 // find the node
727 hashBvNode** prev = &nodeArr[hashIndex];
728 result = nodeArr[hashIndex];
729
730 while (result)
731 {
732 if (result->baseIndex == baseIndex)
733 {
734 return prev;
735 }
736 else if (result->baseIndex > baseIndex)
737 {
738 return prev;
739 }
740 else
741 {
742 prev = &(result->next);
743 result = result->next;
744 }
745 }
746 return prev;
747}
748
749hashBvNode* hashBv::getNodeForIndexHelper(indexType index, bool canAdd)
750{
751 // determine the base index of the node containing this index
752 index = index & ~(BITS_PER_NODE - 1);
753
754 hashBvNode** prev = getInsertionPointForIndex(index);
755
756 hashBvNode* node = *prev;
757
758 if (node && node->belongsIn(index))
759 {
760 return node;
761 }
762 else if (canAdd)
763 {
764 // missing node, insert it before the current one
765 hashBvNode* temp = hashBvNode::Create(index, this->compiler);
766 temp->next = node;
767 *prev = temp;
768 this->numNodes++;
769 return temp;
770 }
771 else
772 {
773 return nullptr;
774 }
775}
776
777hashBvNode* hashBv::getNodeForIndex(indexType index)
778{
779 // determine the base index of the node containing this index
780 index = index & ~(BITS_PER_NODE - 1);
781
782 hashBvNode** prev = getInsertionPointForIndex(index);
783
784 hashBvNode* node = *prev;
785
786 if (node && node->belongsIn(index))
787 {
788 return node;
789 }
790 else
791 {
792 return nullptr;
793 }
794}
795
796void hashBv::setBit(indexType index)
797{
798 assert(index >= 0);
799 assert(this->numNodes == this->getNodeCount());
800 hashBvNode* result = nullptr;
801
802 indexType baseIndex = index & ~(BITS_PER_NODE - 1);
803 indexType base = index - baseIndex;
804 indexType elem = base / BITS_PER_ELEMENT;
805 indexType posi = base % BITS_PER_ELEMENT;
806
807 // this should be the 99% case : when there is only one node in the structure
808 if ((result = nodeArr[0]) && result->baseIndex == baseIndex)
809 {
810 result->elements[elem] |= indexType(1) << posi;
811 return;
812 }
813
814 result = getOrAddNodeForIndex(index);
815 result->setBit(index);
816
817 assert(this->numNodes == this->getNodeCount());
818
819 // if it's getting out of control resize it
820 if (this->numNodes > this->hashtable_size() * 4)
821 {
822 this->Resize();
823 }
824
825 return;
826}
827
828void hashBv::setAll(indexType numToSet)
829{
830 // TODO-Throughput: this could be more efficient
831 for (unsigned int i = 0; i < numToSet; i += BITS_PER_NODE)
832 {
833 hashBvNode* node = getOrAddNodeForIndex(i);
834 indexType bits_to_set = min(BITS_PER_NODE, numToSet - i);
835 node->setLowest(bits_to_set);
836 }
837}
838
839void hashBv::clearBit(indexType index)
840{
841 assert(index >= 0);
842 assert(this->numNodes == this->getNodeCount());
843 hashBvNode* result = nullptr;
844
845 indexType baseIndex = index & ~(BITS_PER_NODE - 1);
846 indexType hashIndex = getHashForIndex(index, hashtable_size());
847
848 hashBvNode** prev = &nodeArr[hashIndex];
849 result = nodeArr[hashIndex];
850
851 while (result)
852 {
853 if (result->baseIndex == baseIndex)
854 {
855 result->clrBit(index);
856 // if nothing left set free it
857 if (!result->anySet())
858 {
859 *prev = result->next;
860 result->freeNode(globalData());
861 this->numNodes--;
862 }
863 return;
864 }
865 else if (result->baseIndex > baseIndex)
866 {
867 return;
868 }
869 else
870 {
871 prev = &(result->next);
872 result = result->next;
873 }
874 }
875 assert(this->numNodes == this->getNodeCount());
876 return;
877}
878
879bool hashBv::testBit(indexType index)
880{
881 // determine the base index of the node containing this index
882 indexType baseIndex = index & ~(BITS_PER_NODE - 1);
883 // 99% case
884 if (nodeArr[0] && nodeArr[0]->baseIndex == baseIndex)
885 {
886 return nodeArr[0]->getBit(index);
887 }
888
889 indexType hashIndex = getHashForIndex(baseIndex, hashtable_size());
890
891 hashBvNode* iter = nodeArr[hashIndex];
892
893 while (iter)
894 {
895 if (iter->baseIndex == baseIndex)
896 {
897 return iter->getBit(index);
898 }
899 else
900 {
901 iter = iter->next;
902 }
903 }
904 return false;
905}
906
907int hashBv::countBits()
908{
909 int result = 0;
910 int hts = this->hashtable_size();
911 for (int hashNum = 0; hashNum < hts; hashNum++)
912 {
913 hashBvNode* node = nodeArr[hashNum];
914 while (node)
915 {
916 result += node->countBits();
917 node = node->next;
918 }
919 }
920 return result;
921}
922
923bool hashBv::anySet()
924{
925 int result = 0;
926
927 int hts = this->hashtable_size();
928 for (int hashNum = 0; hashNum < hts; hashNum++)
929 {
930 hashBvNode* node = nodeArr[hashNum];
931 while (node)
932 {
933 if (node->anySet())
934 {
935 return true;
936 }
937 node = node->next;
938 }
939 }
940 return false;
941}
942
943class AndAction
944{
945public:
946 static inline void PreAction(hashBv* lhs, hashBv* rhs)
947 {
948 }
949 static inline void PostAction(hashBv* lhs, hashBv* rhs)
950 {
951 }
952 static inline bool DefaultResult()
953 {
954 return false;
955 }
956
957 static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
958 {
959 // it's in other, not this
960 // so skip it
961 r = r->next;
962 }
963 static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
964 {
965 // it's in LHS, not RHS
966 // so have to remove it
967 hashBvNode* old = *l;
968 *l = (*l)->next;
969 // splice it out
970 old->freeNode(lhs->globalData());
971 lhs->numNodes--;
972 result = true;
973 }
974 static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
975 {
976 if ((*l)->AndWithChange(r))
977 {
978 r = r->next;
979 result = true;
980
981 if ((*l)->anySet())
982 {
983 l = &((*l)->next);
984 }
985 else
986 {
987 hashBvNode* old = *l;
988 *l = (*l)->next;
989 old->freeNode(lhs->globalData());
990 lhs->numNodes--;
991 }
992 }
993 else
994 {
995 r = r->next;
996 l = &((*l)->next);
997 }
998 }
999 static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1000 {
1001 r = r->next;
1002 }
1003};
1004
1005class SubtractAction
1006{
1007public:
1008 static inline void PreAction(hashBv* lhs, hashBv* rhs)
1009 {
1010 }
1011 static inline void PostAction(hashBv* lhs, hashBv* rhs)
1012 {
1013 }
1014 static inline bool DefaultResult()
1015 {
1016 return false;
1017 }
1018 static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1019 {
1020 // it's in other, not this
1021 // so skip it
1022 r = r->next;
1023 }
1024 static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1025 {
1026 // in lhs, not rhs
1027 // so skip lhs
1028 l = &((*l)->next);
1029 }
1030 static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1031 {
1032 if ((*l)->SubtractWithChange(r))
1033 {
1034 r = r->next;
1035 result = true;
1036
1037 if ((*l)->anySet())
1038 {
1039 l = &((*l)->next);
1040 }
1041 else
1042 {
1043 hashBvNode* old = *l;
1044 *l = (*l)->next;
1045 old->freeNode(lhs->globalData());
1046 lhs->numNodes--;
1047 }
1048 }
1049 else
1050 {
1051 r = r->next;
1052 l = &((*l)->next);
1053 }
1054 }
1055 static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1056 {
1057 r = r->next;
1058 }
1059};
1060
1061class XorAction
1062{
1063public:
1064 static inline void PreAction(hashBv* lhs, hashBv* rhs)
1065 {
1066 }
1067 static inline void PostAction(hashBv* lhs, hashBv* rhs)
1068 {
1069 }
1070 static inline bool DefaultResult()
1071 {
1072 return false;
1073 }
1074
1075 static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1076 {
1077 // it's in other, not this
1078 // so put one in
1079 result = true;
1080 hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler);
1081 lhs->numNodes++;
1082 temp->XorWith(r);
1083 temp->next = (*l)->next;
1084 *l = temp;
1085 l = &(temp->next);
1086
1087 r = r->next;
1088 }
1089
1090 static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1091 {
1092 // it's in LHS, not RHS
1093 // so LHS remains the same
1094 l = &((*l)->next);
1095 }
1096
1097 static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1098 {
1099 if ((*l)->XorWithChange(r))
1100 {
1101 result = true;
1102 }
1103 l = &((*l)->next);
1104 r = r->next;
1105 }
1106
1107 static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1108 {
1109 // it's in other, not this
1110 // so put one in
1111 result = true;
1112 hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler);
1113 lhs->numNodes++;
1114 temp->XorWith(r);
1115 temp->next = nullptr;
1116 *l = temp;
1117 l = &(temp->next);
1118
1119 r = r->next;
1120 }
1121};
1122
1123class OrAction
1124{
1125public:
1126 static inline void PreAction(hashBv* lhs, hashBv* rhs)
1127 {
1128 if (lhs->log2_hashSize + 2 < rhs->log2_hashSize)
1129 {
1130 lhs->Resize(rhs->numNodes);
1131 }
1132 if (rhs->numNodes > rhs->hashtable_size() * 4)
1133 {
1134 rhs->Resize(rhs->numNodes);
1135 }
1136 }
1137 static inline void PostAction(hashBv* lhs, hashBv* rhs)
1138 {
1139 }
1140 static inline bool DefaultResult()
1141 {
1142 return false;
1143 }
1144
1145 static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1146 {
1147 // it's in other, not this
1148 // so put one in
1149 result = true;
1150 hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler);
1151 lhs->numNodes++;
1152 temp->OrWith(r);
1153 temp->next = *l;
1154 *l = temp;
1155 l = &(temp->next);
1156
1157 r = r->next;
1158 }
1159 static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1160 {
1161 // in lhs, not rhs
1162 // so skip lhs
1163 l = &((*l)->next);
1164 }
1165 static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1166 {
1167 if ((*l)->OrWithChange(r))
1168 {
1169 result = true;
1170 }
1171 l = &((*l)->next);
1172 r = r->next;
1173 }
1174 static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1175 {
1176 // other contains something this does not
1177 // copy it
1178 // LeftGap(lhs, l, r, result, terminate);
1179 result = true;
1180 hashBvNode* temp = hashBvNode::Create(r->baseIndex, lhs->compiler);
1181 lhs->numNodes++;
1182 temp->OrWith(r);
1183 temp->next = nullptr;
1184 *l = temp;
1185 l = &(temp->next);
1186
1187 r = r->next;
1188 }
1189};
1190
1191class CompareAction
1192{
1193public:
1194 static inline void PreAction(hashBv* lhs, hashBv* rhs)
1195 {
1196 }
1197 static inline void PostAction(hashBv* lhs, hashBv* rhs)
1198 {
1199 }
1200 static inline bool DefaultResult()
1201 {
1202 return true;
1203 }
1204
1205 static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1206 {
1207 terminate = true;
1208 result = false;
1209 }
1210 static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1211 {
1212 // in lhs, not rhs
1213 // so skip lhs
1214 terminate = true;
1215 result = false;
1216 }
1217 static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1218 {
1219 if (!(*l)->sameAs(r))
1220 {
1221 terminate = true;
1222 result = false;
1223 }
1224 l = &((*l)->next);
1225 r = r->next;
1226 }
1227 static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1228 {
1229 terminate = true;
1230 result = false;
1231 }
1232};
1233
1234class IntersectsAction
1235{
1236public:
1237 static inline void PreAction(hashBv* lhs, hashBv* rhs)
1238 {
1239 }
1240 static inline void PostAction(hashBv* lhs, hashBv* rhs)
1241 {
1242 }
1243 static inline bool DefaultResult()
1244 {
1245 return false;
1246 }
1247
1248 static inline void LeftGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1249 {
1250 // in rhs, not lhs
1251 // so skip rhs
1252 r = r->next;
1253 }
1254 static inline void RightGap(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1255 {
1256 // in lhs, not rhs
1257 // so skip lhs
1258 l = &((*l)->next);
1259 }
1260 static inline void BothPresent(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1261 {
1262 if ((*l)->Intersects(r))
1263 {
1264 terminate = true;
1265 result = true;
1266 }
1267 }
1268 static inline void LeftEmpty(hashBv* lhs, hashBvNode**& l, hashBvNode*& r, bool& result, bool& terminate)
1269 {
1270 r = r->next;
1271 }
1272};
1273
1274template <typename Action>
1275bool hashBv::MultiTraverseLHSBigger(hashBv* other)
1276{
1277 int hts = this->hashtable_size();
1278 int ots = other->hashtable_size();
1279
1280 bool result = Action::DefaultResult();
1281 bool terminate = false;
1282
1283 // this is larger
1284 hashBvNode*** cursors;
1285 int expansionFactor = hts / ots;
1286 cursors = (hashBvNode***)alloca(expansionFactor * sizeof(void*));
1287
1288 for (int h = 0; h < other->hashtable_size(); h++)
1289 {
1290 // set up cursors for the expansion of nodes
1291 for (int i = 0; i < expansionFactor; i++)
1292 {
1293 // ex: for [1024] &= [8]
1294 // for rhs in bin 0
1295 // cursors point to lhs: 0, 8, 16, 24, ...
1296 cursors[i] = &nodeArr[ots * i + h];
1297 }
1298
1299 hashBvNode* o = other->nodeArr[h];
1300 while (o)
1301 {
1302 hashBvNode* next = o->next;
1303 // figure out what dst list this goes to
1304 int hash = getHashForIndex(o->baseIndex, hts);
1305 int dstIndex = (hash - h) >> other->log2_hashSize;
1306 hashBvNode** cursor = cursors[dstIndex];
1307 hashBvNode* c = *cursor;
1308
1309 // figure out where o fits in the cursor
1310
1311 if (!c)
1312 {
1313 Action::LeftEmpty(this, cursors[dstIndex], o, result, terminate);
1314 if (terminate)
1315 {
1316 return result;
1317 }
1318 }
1319 else if (c->baseIndex == o->baseIndex)
1320 {
1321 Action::BothPresent(this, cursors[dstIndex], o, result, terminate);
1322 if (terminate)
1323 {
1324 return result;
1325 }
1326 }
1327 else if (c->baseIndex > o->baseIndex)
1328 {
1329 Action::LeftGap(this, cursors[dstIndex], o, result, terminate);
1330 if (terminate)
1331 {
1332 return result;
1333 }
1334 }
1335 else if (c->baseIndex < o->baseIndex)
1336 {
1337 Action::RightGap(this, cursors[dstIndex], o, result, terminate);
1338 if (terminate)
1339 {
1340 return result;
1341 }
1342 }
1343 }
1344 for (int i = 0; i < expansionFactor; i++)
1345 {
1346 while (*(cursors[i]))
1347 {
1348 Action::RightGap(this, cursors[i], o, result, terminate);
1349 if (terminate)
1350 {
1351 return result;
1352 }
1353 }
1354 }
1355 }
1356 return result;
1357}
1358
1359template <typename Action>
1360bool hashBv::MultiTraverseRHSBigger(hashBv* other)
1361{
1362 int hts = this->hashtable_size();
1363 int ots = other->hashtable_size();
1364
1365 bool result = Action::DefaultResult();
1366 bool terminate = false;
1367
1368 for (int hashNum = 0; hashNum < ots; hashNum++)
1369 {
1370 int destination = getHashForIndex(BITS_PER_NODE * hashNum, this->hashtable_size());
1371 assert(hashNum == getHashForIndex(BITS_PER_NODE * hashNum, other->hashtable_size()));
1372
1373 hashBvNode** pa = &this->nodeArr[destination];
1374 hashBvNode** pb = &other->nodeArr[hashNum];
1375 hashBvNode* b = *pb;
1376
1377 while (*pa && b)
1378 {
1379 hashBvNode* a = *pa;
1380 if (a->baseIndex < b->baseIndex)
1381 {
1382 // in a but not in b
1383 // but maybe it's someplace else in b
1384 if (getHashForIndex(a->baseIndex, ots) == hashNum)
1385 {
1386 // this contains something other does not
1387 // need to erase it
1388 Action::RightGap(this, pa, b, result, terminate);
1389 if (terminate)
1390 {
1391 return result;
1392 }
1393 }
1394 else
1395 {
1396 // other might contain this, we don't know yet
1397 pa = &a->next;
1398 }
1399 }
1400 else if (a->baseIndex == b->baseIndex)
1401 {
1402 Action::BothPresent(this, pa, b, result, terminate);
1403 if (terminate)
1404 {
1405 return result;
1406 }
1407 }
1408 else if (a->baseIndex > b->baseIndex)
1409 {
1410 // other contains something this does not
1411 Action::LeftGap(this, pa, b, result, terminate);
1412 if (terminate)
1413 {
1414 return result;
1415 }
1416 }
1417 }
1418 while (*pa)
1419 {
1420 // if it's in the dest but not in src
1421 // then make sure it's expected to be in this list
1422 if (getHashForIndex((*pa)->baseIndex, ots) == hashNum)
1423 {
1424 Action::RightGap(this, pa, b, result, terminate);
1425 if (terminate)
1426 {
1427 return result;
1428 }
1429 }
1430 else
1431 {
1432 pa = &((*pa)->next);
1433 }
1434 }
1435 while (b)
1436 {
1437 Action::LeftEmpty(this, pa, b, result, terminate);
1438 if (terminate)
1439 {
1440 return result;
1441 }
1442 }
1443 }
1444 assert(this->numNodes == this->getNodeCount());
1445 return result;
1446}
1447
1448// LHSBigger and RHSBigger algorithms both work for equal
1449// this is a specialized version of RHSBigger which is simpler (and faster)
1450// because equal sizes are the 99% case
1451template <typename Action>
1452bool hashBv::MultiTraverseEqual(hashBv* other)
1453{
1454 int hts = this->hashtable_size();
1455 assert(other->hashtable_size() == hts);
1456
1457 bool result = Action::DefaultResult();
1458 bool terminate = false;
1459
1460 for (int hashNum = 0; hashNum < hts; hashNum++)
1461 {
1462 int destination = getHashForIndex(BITS_PER_NODE * hashNum, this->hashtable_size());
1463
1464 hashBvNode** pa = &this->nodeArr[hashNum];
1465 hashBvNode** pb = &other->nodeArr[hashNum];
1466 hashBvNode* b = *pb;
1467
1468 while (*pa && b)
1469 {
1470 hashBvNode* a = *pa;
1471 if (a->baseIndex < b->baseIndex)
1472 {
1473 // in a but not in b
1474 Action::RightGap(this, pa, b, result, terminate);
1475 if (terminate)
1476 {
1477 return result;
1478 }
1479 }
1480 else if (a->baseIndex == b->baseIndex)
1481 {
1482 Action::BothPresent(this, pa, b, result, terminate);
1483 if (terminate)
1484 {
1485 return result;
1486 }
1487 }
1488 else if (a->baseIndex > b->baseIndex)
1489 {
1490 // other contains something this does not
1491 Action::LeftGap(this, pa, b, result, terminate);
1492 if (terminate)
1493 {
1494 return result;
1495 }
1496 }
1497 }
1498 while (*pa)
1499 {
1500 // if it's in the dest but not in src
1501 Action::RightGap(this, pa, b, result, terminate);
1502 if (terminate)
1503 {
1504 return result;
1505 }
1506 }
1507 while (b)
1508 {
1509 Action::LeftEmpty(this, pa, b, result, terminate);
1510 if (terminate)
1511 {
1512 return result;
1513 }
1514 }
1515 }
1516 assert(this->numNodes == this->getNodeCount());
1517 return result;
1518}
1519
1520template <class Action>
1521bool hashBv::MultiTraverse(hashBv* other)
1522{
1523 bool result = false;
1524
1525 assert(this->numNodes == this->getNodeCount());
1526
1527 Action::PreAction(this, other);
1528
1529 int hts = this->log2_hashSize;
1530 int ots = other->log2_hashSize;
1531
1532 if (hts == ots)
1533 {
1534 return MultiTraverseEqual<Action>(other);
1535 }
1536 else if (hts > ots)
1537 {
1538 return MultiTraverseLHSBigger<Action>(other);
1539 }
1540 else
1541 {
1542 return MultiTraverseRHSBigger<Action>(other);
1543 }
1544}
1545
1546bool hashBv::Intersects(hashBv* other)
1547{
1548 return MultiTraverse<IntersectsAction>(other);
1549}
1550
1551bool hashBv::AndWithChange(hashBv* other)
1552{
1553 return MultiTraverse<AndAction>(other);
1554}
1555
1556// same as AND ~x
1557bool hashBv::SubtractWithChange(hashBv* other)
1558{
1559 return MultiTraverse<SubtractAction>(other);
1560}
1561
1562void hashBv::Subtract(hashBv* other)
1563{
1564 this->SubtractWithChange(other);
1565}
1566
1567void hashBv::Subtract3(hashBv* o1, hashBv* o2)
1568{
1569 this->copyFrom(o1, compiler);
1570 this->Subtract(o2);
1571}
1572
1573void hashBv::UnionMinus(hashBv* src1, hashBv* src2, hashBv* src3)
1574{
1575 this->Subtract3(src1, src2);
1576 this->OrWithChange(src3);
1577}
1578
1579void hashBv::ZeroAll()
1580{
1581 int hts = this->hashtable_size();
1582
1583 for (int hashNum = 0; hashNum < hts; hashNum++)
1584 {
1585 while (nodeArr[hashNum])
1586 {
1587 hashBvNode* n = nodeArr[hashNum];
1588 nodeArr[hashNum] = n->next;
1589 n->freeNode(globalData());
1590 }
1591 }
1592 this->numNodes = 0;
1593}
1594
1595bool hashBv::OrWithChange(hashBv* other)
1596{
1597 return MultiTraverse<OrAction>(other);
1598}
1599
1600bool hashBv::XorWithChange(hashBv* other)
1601{
1602 return MultiTraverse<XorAction>(other);
1603}
1604void hashBv::OrWith(hashBv* other)
1605{
1606 this->OrWithChange(other);
1607}
1608
1609void hashBv::AndWith(hashBv* other)
1610{
1611 this->AndWithChange(other);
1612}
1613
1614bool hashBv::CompareWith(hashBv* other)
1615{
1616 return MultiTraverse<CompareAction>(other);
1617}
1618
1619void hashBv::copyFrom(hashBv* other, Compiler* comp)
1620{
1621 assert(this != other);
1622
1623 hashBvNode* freeList = nullptr;
1624
1625 this->ZeroAll();
1626
1627 if (this->log2_hashSize != other->log2_hashSize)
1628 {
1629 this->nodeArr = this->getNewVector(other->hashtable_size());
1630 this->log2_hashSize = other->log2_hashSize;
1631 assert(this->hashtable_size() == other->hashtable_size());
1632 }
1633
1634 int hts = this->hashtable_size();
1635 // printf("in copyfrom\n");
1636 for (int h = 0; h < hts; h++)
1637 {
1638 // put the current list on the free list
1639 freeList = this->nodeArr[h];
1640 this->nodeArr[h] = nullptr;
1641
1642 hashBvNode** splicePoint = &(this->nodeArr[h]);
1643 hashBvNode* otherNode = other->nodeArr[h];
1644 hashBvNode* newNode = nullptr;
1645
1646 while (otherNode)
1647 {
1648 // printf("otherNode is True...\n");
1649 hashBvNode* next = *splicePoint;
1650
1651 this->numNodes++;
1652
1653 if (freeList)
1654 {
1655 newNode = freeList;
1656 freeList = freeList->next;
1657 newNode->Reconstruct(otherNode->baseIndex);
1658 }
1659 else
1660 {
1661 newNode = hashBvNode::Create(otherNode->baseIndex, this->compiler);
1662 }
1663 newNode->copyFrom(otherNode);
1664
1665 newNode->next = *splicePoint;
1666 *splicePoint = newNode;
1667 splicePoint = &(newNode->next);
1668
1669 otherNode = otherNode->next;
1670 }
1671 }
1672 while (freeList)
1673 {
1674 hashBvNode* next = freeList->next;
1675 freeList->freeNode(globalData());
1676 freeList = next;
1677 }
1678#if 0
1679 for (int h=0; h<hashtable_size(); h++)
1680 {
1681 printf("%p %p\n", this->nodeArr[h], other->nodeArr[h]);
1682 }
1683#endif
1684}
1685
1686int nodeSort(const void* x, const void* y)
1687{
1688 hashBvNode* a = (hashBvNode*)x;
1689 hashBvNode* b = (hashBvNode*)y;
1690 return (int)(b->baseIndex - a->baseIndex);
1691}
1692
1693void hashBv::InorderTraverse(nodeAction n)
1694{
1695 int hts = hashtable_size();
1696
1697 hashBvNode** x = new (compiler, CMK_hashBv) hashBvNode*[hts];
1698
1699 {
1700 // keep an array of the current pointers
1701 // into each of the the bitvector lists
1702 // in the hashtable
1703 for (int i = 0; i < hts; i++)
1704 {
1705 x[i] = nodeArr[i];
1706 }
1707
1708 while (1)
1709 {
1710 // pick the lowest node in the hashtable
1711
1712 indexType lowest = INT_MAX;
1713 int lowest_index = -1;
1714 for (int i = 0; i < hts; i++)
1715 {
1716 if (x[i] && x[i]->baseIndex < lowest)
1717 {
1718 lowest = x[i]->baseIndex;
1719 lowest_index = i;
1720 }
1721 }
1722 // if there was anything left, use it and update
1723 // the list pointers otherwise we are done
1724 if (lowest_index != -1)
1725 {
1726 n(x[lowest_index]);
1727 x[lowest_index] = x[lowest_index]->next;
1728 }
1729 else
1730 {
1731 break;
1732 }
1733 }
1734 }
1735
1736 delete[] x;
1737}
1738
1739void hashBv::InorderTraverseTwo(hashBv* other, dualNodeAction a)
1740{
1741 int sizeThis, sizeOther;
1742 hashBvNode **nodesThis, **nodesOther;
1743
1744 sizeThis = this->hashtable_size();
1745 sizeOther = other->hashtable_size();
1746
1747 nodesThis = new (compiler, CMK_hashBv) hashBvNode*[sizeThis];
1748 nodesOther = new (compiler, CMK_hashBv) hashBvNode*[sizeOther];
1749
1750 // populate the arrays
1751 for (int i = 0; i < sizeThis; i++)
1752 {
1753 nodesThis[i] = this->nodeArr[i];
1754 }
1755
1756 for (int i = 0; i < sizeOther; i++)
1757 {
1758 nodesOther[i] = other->nodeArr[i];
1759 }
1760
1761 while (1)
1762 {
1763 indexType lowestThis = INT_MAX;
1764 indexType lowestOther = INT_MAX;
1765 int lowestHashIndexThis = -1;
1766 int lowestHashIndexOther = -1;
1767
1768 // find the lowest remaining node in each BV
1769 for (int i = 0; i < sizeThis; i++)
1770 {
1771 if (nodesThis[i] && nodesThis[i]->baseIndex < lowestThis)
1772 {
1773 lowestHashIndexThis = i;
1774 lowestThis = nodesThis[i]->baseIndex;
1775 }
1776 }
1777 for (int i = 0; i < sizeOther; i++)
1778 {
1779 if (nodesOther[i] && nodesOther[i]->baseIndex < lowestOther)
1780 {
1781 lowestHashIndexOther = i;
1782 lowestOther = nodesOther[i]->baseIndex;
1783 }
1784 }
1785 hashBvNode *nodeThis, *nodeOther;
1786 nodeThis = lowestHashIndexThis == -1 ? nullptr : nodesThis[lowestHashIndexThis];
1787 nodeOther = lowestHashIndexOther == -1 ? nullptr : nodesOther[lowestHashIndexOther];
1788 // no nodes left in either, so return
1789 if ((!nodeThis) && (!nodeOther))
1790 {
1791 break;
1792
1793 // there are only nodes left in one bitvector
1794 }
1795 else if ((!nodeThis) || (!nodeOther))
1796 {
1797 a(this, other, nodeThis, nodeOther);
1798 if (nodeThis)
1799 {
1800 nodesThis[lowestHashIndexThis] = nodesThis[lowestHashIndexThis]->next;
1801 }
1802 if (nodeOther)
1803 {
1804 nodesOther[lowestHashIndexOther] = nodesOther[lowestHashIndexOther]->next;
1805 }
1806 }
1807 // nodes are left in both so determine if the lowest ones
1808 // match. if so process them in a pair. if not then
1809 // process the lower of the two alone
1810 else if (nodeThis && nodeOther)
1811 {
1812 if (nodeThis->baseIndex == nodeOther->baseIndex)
1813 {
1814 a(this, other, nodeThis, nodeOther);
1815 nodesThis[lowestHashIndexThis] = nodesThis[lowestHashIndexThis]->next;
1816 nodesOther[lowestHashIndexOther] = nodesOther[lowestHashIndexOther]->next;
1817 }
1818 else if (nodeThis->baseIndex < nodeOther->baseIndex)
1819 {
1820 a(this, other, nodeThis, nullptr);
1821 nodesThis[lowestHashIndexThis] = nodesThis[lowestHashIndexThis]->next;
1822 }
1823 else if (nodeOther->baseIndex < nodeThis->baseIndex)
1824 {
1825 a(this, other, nullptr, nodeOther);
1826 nodesOther[lowestHashIndexOther] = nodesOther[lowestHashIndexOther]->next;
1827 }
1828 }
1829 }
1830 delete[] nodesThis;
1831 delete[] nodesOther;
1832}
1833
1834// --------------------------------------------------------------------
1835// --------------------------------------------------------------------
1836
1837#ifdef DEBUG
1838void SimpleDumpNode(hashBvNode* n)
1839{
1840 printf("base: %d\n", n->baseIndex);
1841}
1842
1843void DumpNode(hashBvNode* n)
1844{
1845 n->dump();
1846}
1847
1848void SimpleDumpDualNode(hashBv* a, hashBv* b, hashBvNode* n, hashBvNode* m)
1849{
1850 printf("nodes: ");
1851 if (n)
1852 {
1853 printf("%d,", n->baseIndex);
1854 }
1855 else
1856 {
1857 printf("----,");
1858 }
1859 if (m)
1860 {
1861 printf("%d\n", m->baseIndex);
1862 }
1863 else
1864 {
1865 printf("----\n");
1866 }
1867}
1868#endif // DEBUG
1869
1870hashBvIterator::hashBvIterator()
1871{
1872 this->bv = nullptr;
1873}
1874
1875hashBvIterator::hashBvIterator(hashBv* bv)
1876{
1877 this->bv = bv;
1878 this->hashtable_index = 0;
1879 this->current_element = 0;
1880 this->current_base = 0;
1881 this->current_data = 0;
1882
1883 if (bv)
1884 {
1885 this->hashtable_size = bv->hashtable_size();
1886 this->currNode = bv->nodeArr[0];
1887
1888 if (!this->currNode)
1889 {
1890 this->nextNode();
1891 }
1892 }
1893}
1894
1895void hashBvIterator::initFrom(hashBv* bv)
1896{
1897 this->bv = bv;
1898 this->hashtable_size = bv->hashtable_size();
1899 this->hashtable_index = 0;
1900 this->currNode = bv->nodeArr[0];
1901 this->current_element = 0;
1902 this->current_base = 0;
1903 this->current_data = 0;
1904
1905 if (!this->currNode)
1906 {
1907 this->nextNode();
1908 }
1909 if (this->currNode)
1910 {
1911 this->current_data = this->currNode->elements[0];
1912 }
1913}
1914
1915void hashBvIterator::nextNode()
1916{
1917 // if we have a valid node then just get the next one in the chain
1918 if (this->currNode)
1919 {
1920 this->currNode = this->currNode->next;
1921 }
1922
1923 // else step to the next one in the hash table
1924 while (!this->currNode)
1925 {
1926 hashtable_index++;
1927 // no more
1928 if (hashtable_index >= hashtable_size)
1929 {
1930 // printf("nextnode bailed\n");
1931 return;
1932 }
1933
1934 this->currNode = bv->nodeArr[hashtable_index];
1935 }
1936 // first element in the new node
1937 this->current_element = 0;
1938 this->current_base = this->currNode->baseIndex;
1939 this->current_data = this->currNode->elements[0];
1940 // printf("nextnode returned base %d\n", this->current_base);
1941 // printf("hti = %d ", hashtable_index);
1942}
1943
1944indexType hashBvIterator::nextBit()
1945{
1946
1947 // printf("in nextbit for bv:\n");
1948 // this->bv->dump();
1949
1950 if (!this->currNode)
1951 {
1952 this->nextNode();
1953 }
1954
1955top:
1956
1957 if (!this->currNode)
1958 {
1959 return NOMOREBITS;
1960 }
1961
1962more_data:
1963 if (!this->current_data)
1964 {
1965 current_element++;
1966 // printf("current element is %d\n", current_element);
1967 // reached the end of this node
1968 if (current_element == (indexType) this->currNode->numElements())
1969 {
1970 // printf("going to next node\n");
1971 this->nextNode();
1972 goto top;
1973 }
1974 else
1975 {
1976 assert(current_element < (indexType) this->currNode->numElements());
1977 // printf("getting more data\n");
1978 current_data = this->currNode->elements[current_element];
1979 current_base = this->currNode->baseIndex + current_element * BITS_PER_ELEMENT;
1980 goto more_data;
1981 }
1982 }
1983 else
1984 {
1985 while (current_data)
1986 {
1987 if (current_data & 1)
1988 {
1989 current_data >>= 1;
1990 current_base++;
1991
1992 return current_base - 1;
1993 }
1994 else
1995 {
1996 current_data >>= 1;
1997 current_base++;
1998 }
1999 }
2000 goto more_data;
2001 }
2002}
2003