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 #include <cutils/log.h> 18 #include <stddef.h> 19 #include <string.h> 20 #include <minikin/SparseBitSet.h> 21 22 namespace android { 23 24 const uint32_t SparseBitSet::kNotFound; 25 26 void SparseBitSet::clear() { 27 mMaxVal = 0; 28 mIndices.reset(); 29 mBitmaps.reset(); 30 } 31 32 uint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) { 33 bool haveZeroPage = false; 34 uint32_t nonzeroPageEnd = 0; 35 uint32_t nPages = 0; 36 for (size_t i = 0; i < nRanges; i++) { 37 uint32_t start = ranges[i * 2]; 38 uint32_t end = ranges[i * 2 + 1]; 39 uint32_t startPage = start >> kLogValuesPerPage; 40 uint32_t endPage = (end - 1) >> kLogValuesPerPage; 41 if (startPage >= nonzeroPageEnd) { 42 if (startPage > nonzeroPageEnd) { 43 if (!haveZeroPage) { 44 haveZeroPage = true; 45 nPages++; 46 } 47 } 48 nPages++; 49 } 50 nPages += endPage - startPage; 51 nonzeroPageEnd = endPage + 1; 52 } 53 return nPages; 54 } 55 56 void SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) { 57 if (nRanges == 0) { 58 mMaxVal = 0; 59 mIndices.reset(); 60 mBitmaps.reset(); 61 return; 62 } 63 mMaxVal = ranges[nRanges * 2 - 1]; 64 size_t indexSize = (mMaxVal + kPageMask) >> kLogValuesPerPage; 65 mIndices.reset(new uint32_t[indexSize]); 66 uint32_t nPages = calcNumPages(ranges, nRanges); 67 mBitmaps.reset(new element[nPages << (kLogValuesPerPage - kLogBitsPerEl)]); 68 memset(mBitmaps.get(), 0, nPages << (kLogValuesPerPage - 3)); 69 mZeroPageIndex = noZeroPage; 70 uint32_t nonzeroPageEnd = 0; 71 uint32_t currentPage = 0; 72 for (size_t i = 0; i < nRanges; i++) { 73 uint32_t start = ranges[i * 2]; 74 uint32_t end = ranges[i * 2 + 1]; 75 LOG_ALWAYS_FATAL_IF(end < start); // make sure range size is nonnegative 76 uint32_t startPage = start >> kLogValuesPerPage; 77 uint32_t endPage = (end - 1) >> kLogValuesPerPage; 78 if (startPage >= nonzeroPageEnd) { 79 if (startPage > nonzeroPageEnd) { 80 if (mZeroPageIndex == noZeroPage) { 81 mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 82 } 83 for (uint32_t j = nonzeroPageEnd; j < startPage; j++) { 84 mIndices[j] = mZeroPageIndex; 85 } 86 } 87 mIndices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 88 } 89 90 size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) + 91 ((start & kPageMask) >> kLogBitsPerEl); 92 size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl; 93 if (nElements == 1) { 94 mBitmaps[index] |= (kElAllOnes >> (start & kElMask)) & 95 (kElAllOnes << ((~end + 1) & kElMask)); 96 } else { 97 mBitmaps[index] |= kElAllOnes >> (start & kElMask); 98 for (size_t j = 1; j < nElements - 1; j++) { 99 mBitmaps[index + j] = kElAllOnes; 100 } 101 mBitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask); 102 } 103 for (size_t j = startPage + 1; j < endPage + 1; j++) { 104 mIndices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 105 } 106 nonzeroPageEnd = endPage + 1; 107 } 108 } 109 110 int SparseBitSet::CountLeadingZeros(element x) { 111 // Note: GCC / clang builtin 112 return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x); 113 } 114 115 uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const { 116 if (fromIndex >= mMaxVal) { 117 return kNotFound; 118 } 119 uint32_t fromPage = fromIndex >> kLogValuesPerPage; 120 const element* bitmap = &mBitmaps[mIndices[fromPage]]; 121 uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl; 122 element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask)); 123 if (e != 0) { 124 return (fromIndex & ~kElMask) + CountLeadingZeros(e); 125 } 126 for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) { 127 e = bitmap[j]; 128 if (e != 0) { 129 return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e); 130 } 131 } 132 uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage; 133 for (uint32_t page = fromPage + 1; page < maxPage; page++) { 134 uint32_t index = mIndices[page]; 135 if (index == mZeroPageIndex) { 136 continue; 137 } 138 bitmap = &mBitmaps[index]; 139 for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) { 140 e = bitmap[j]; 141 if (e != 0) { 142 return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e); 143 } 144 } 145 } 146 return kNotFound; 147 } 148 149 } // namespace android 150
