BitArray.cpp 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156
  1. #include "data/BitArray.h"
  2. #include "math/Math.h"
  3. static int roundUpDivide(int a, int b) {
  4. if(a % b == 0) {
  5. return a / b;
  6. }
  7. return a / b + 1;
  8. }
  9. static constexpr int INT_BITS = sizeof(int) * 8;
  10. static constexpr int DIVIDE_BITS = Math::roundUpLog2(INT_BITS);
  11. static int readBits(const int* data, int index, int bits) {
  12. int dataIndexA = (index * bits) >> DIVIDE_BITS;
  13. int dataIndexB = ((index + 1) * bits) >> DIVIDE_BITS;
  14. int shifts = (index * bits) & (INT_BITS - 1);
  15. if(dataIndexA == dataIndexB) {
  16. return (data[dataIndexA] >> shifts) & ((1 << bits) - 1);
  17. }
  18. int bitsInA = INT_BITS - shifts;
  19. int r = (data[dataIndexA] >> shifts) & ((1 << bitsInA) - 1);
  20. r |= (data[dataIndexB] & ((1 << (bits - bitsInA)) - 1)) << bitsInA;
  21. return r;
  22. }
  23. static void setBits(int* data, int index, int bits, int value) {
  24. int mask = (1 << bits) - 1;
  25. value &= mask;
  26. int dataIndexA = (index * bits) >> DIVIDE_BITS;
  27. int dataIndexB = ((index + 1) * bits) >> DIVIDE_BITS;
  28. int shifts = (index * bits) & (INT_BITS - 1);
  29. data[dataIndexA] &= ~(mask << shifts);
  30. data[dataIndexA] |= (value << shifts);
  31. if(dataIndexA != dataIndexB) {
  32. int leftBits = bits - (INT_BITS - shifts);
  33. int mask = (1 << leftBits) - 1;
  34. data[dataIndexB] &= ~mask;
  35. data[dataIndexB] |= (value >> (INT_BITS - shifts));
  36. }
  37. }
  38. static int getArrayLength(int length, int bits) {
  39. return roundUpDivide(length * bits, sizeof(int) * 8);
  40. }
  41. BitArray::BitArray() : length(0), bits(0), data(nullptr) {
  42. }
  43. static int* allocate(int length, int bits) {
  44. int l = getArrayLength(length, bits);
  45. int* a = new int[l];
  46. memset(a, 0, l * sizeof(int));
  47. return a;
  48. }
  49. BitArray::BitArray(int length, int bits)
  50. : length(length), bits(bits), data(nullptr) {
  51. if(length > 0 && bits > 0) {
  52. data = allocate(length, bits);
  53. }
  54. }
  55. BitArray::BitArray(const BitArray& other) : BitArray(other.length, other.bits) {
  56. for(int i = 0; i < length; i++) {
  57. set(i, other.get(i));
  58. }
  59. }
  60. BitArray::BitArray(BitArray&& other) : BitArray() {
  61. swap(other);
  62. }
  63. BitArray::~BitArray() {
  64. delete[] data;
  65. }
  66. BitArray& BitArray::operator=(BitArray other) {
  67. swap(other);
  68. return *this;
  69. }
  70. BitArray& BitArray::set(int index, int value) {
  71. setBits(data, index, bits, value);
  72. return *this;
  73. }
  74. int BitArray::get(int index) const {
  75. return readBits(data, index, bits);
  76. }
  77. int BitArray::getLength() const {
  78. return length;
  79. }
  80. int BitArray::getBits() const {
  81. return bits;
  82. }
  83. int BitArray::getInternalByteSize() const {
  84. if(bits <= 0 || length <= 0) {
  85. return 0;
  86. }
  87. return getArrayLength(length, bits) * sizeof(int);
  88. }
  89. int BitArray::select(int index) const {
  90. if(index <= 0) {
  91. return -1;
  92. }
  93. int found = 0;
  94. int end = getArrayLength(length, bits);
  95. for(int i = 0; i < end; i++) {
  96. int ones = __builtin_popcount(data[i]);
  97. found += ones;
  98. if(found >= index) {
  99. found -= ones;
  100. int a = i * 32 - 1;
  101. int d = data[i];
  102. while(found < index) {
  103. found += d & 1;
  104. d >>= 1;
  105. a++;
  106. }
  107. return a;
  108. }
  109. }
  110. return -1;
  111. }
  112. void BitArray::fill(int value) {
  113. for(int i = 0; i < length; i++) {
  114. set(i, value);
  115. }
  116. }
  117. void BitArray::resize(int newLength, int newBits) {
  118. int* newData = allocate(newLength, newBits);
  119. int end = Math::min(length, newLength);
  120. for(int i = 0; i < end; i++) {
  121. setBits(newData, i, newBits, get(i));
  122. }
  123. for(int i = end; i < newLength; i++) {
  124. setBits(newData, i, newBits, 0);
  125. }
  126. delete[] data;
  127. data = newData;
  128. bits = newBits;
  129. length = newLength;
  130. }
  131. void BitArray::swap(BitArray& other) {
  132. std::swap(length, other.length);
  133. std::swap(bits, other.bits);
  134. std::swap(data, other.data);
  135. }