BitArray.cpp 4.2 KB

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