1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #define LOG_TAG "SparseBitSet" 18 19 #include <stddef.h> 20 #include <string.h> 21 22 #include <log/log.h> 23 24 #include <minikin/SparseBitSet.h> 25 26 namespace minikin { 27 28 const uint32_t SparseBitSet::kNotFound; 29 calcNumPages(const uint32_t * ranges,size_t nRanges)30uint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) { 31 bool haveZeroPage = false; 32 uint32_t nonzeroPageEnd = 0; 33 uint32_t nPages = 0; 34 for (size_t i = 0; i < nRanges; i++) { 35 uint32_t start = ranges[i * 2]; 36 uint32_t end = ranges[i * 2 + 1]; 37 uint32_t startPage = start >> kLogValuesPerPage; 38 uint32_t endPage = (end - 1) >> kLogValuesPerPage; 39 if (startPage >= nonzeroPageEnd) { 40 if (startPage > nonzeroPageEnd) { 41 if (!haveZeroPage) { 42 haveZeroPage = true; 43 nPages++; 44 } 45 } 46 nPages++; 47 } 48 nPages += endPage - startPage; 49 nonzeroPageEnd = endPage + 1; 50 } 51 return nPages; 52 } 53 initFromRanges(const uint32_t * ranges,size_t nRanges)54void SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) { 55 if (nRanges == 0) { 56 return; 57 } 58 const uint32_t maxVal = ranges[nRanges * 2 - 1]; 59 if (maxVal >= kMaximumCapacity) { 60 return; 61 } 62 mMaxVal = maxVal; 63 mIndices.reset(new uint16_t[(mMaxVal + kPageMask) >> kLogValuesPerPage]); 64 uint32_t nPages = calcNumPages(ranges, nRanges); 65 mBitmaps.reset(new element[nPages << (kLogValuesPerPage - kLogBitsPerEl)]()); 66 mZeroPageIndex = noZeroPage; 67 uint32_t nonzeroPageEnd = 0; 68 uint32_t currentPage = 0; 69 for (size_t i = 0; i < nRanges; i++) { 70 uint32_t start = ranges[i * 2]; 71 uint32_t end = ranges[i * 2 + 1]; 72 LOG_ALWAYS_FATAL_IF(end < start); // make sure range size is nonnegative 73 uint32_t startPage = start >> kLogValuesPerPage; 74 uint32_t endPage = (end - 1) >> kLogValuesPerPage; 75 if (startPage >= nonzeroPageEnd) { 76 if (startPage > nonzeroPageEnd) { 77 if (mZeroPageIndex == noZeroPage) { 78 mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 79 } 80 for (uint32_t j = nonzeroPageEnd; j < startPage; j++) { 81 mIndices[j] = mZeroPageIndex; 82 } 83 } 84 mIndices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 85 } 86 87 size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) + 88 ((start & kPageMask) >> kLogBitsPerEl); 89 size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl; 90 if (nElements == 1) { 91 mBitmaps[index] |= (kElAllOnes >> (start & kElMask)) & 92 (kElAllOnes << ((~end + 1) & kElMask)); 93 } else { 94 mBitmaps[index] |= kElAllOnes >> (start & kElMask); 95 for (size_t j = 1; j < nElements - 1; j++) { 96 mBitmaps[index + j] = kElAllOnes; 97 } 98 mBitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask); 99 } 100 for (size_t j = startPage + 1; j < endPage + 1; j++) { 101 mIndices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 102 } 103 nonzeroPageEnd = endPage + 1; 104 } 105 } 106 CountLeadingZeros(element x)107int SparseBitSet::CountLeadingZeros(element x) { 108 // Note: GCC / clang builtin 109 return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x); 110 } 111 nextSetBit(uint32_t fromIndex) const112uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const { 113 if (fromIndex >= mMaxVal) { 114 return kNotFound; 115 } 116 uint32_t fromPage = fromIndex >> kLogValuesPerPage; 117 const element* bitmap = &mBitmaps[mIndices[fromPage]]; 118 uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl; 119 element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask)); 120 if (e != 0) { 121 return (fromIndex & ~kElMask) + CountLeadingZeros(e); 122 } 123 for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) { 124 e = bitmap[j]; 125 if (e != 0) { 126 return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e); 127 } 128 } 129 uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage; 130 for (uint32_t page = fromPage + 1; page < maxPage; page++) { 131 uint16_t index = mIndices[page]; 132 if (index == mZeroPageIndex) { 133 continue; 134 } 135 bitmap = &mBitmaps[index]; 136 for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) { 137 e = bitmap[j]; 138 if (e != 0) { 139 return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e); 140 } 141 } 142 } 143 return kNotFound; 144 } 145 146 } // namespace minikin 147