SparseBitSet.cpp revision 73abbd59344770601991248cc56846cd199812b8
19cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien/* 29cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * Copyright (C) 2012 The Android Open Source Project 39cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * 49cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * Licensed under the Apache License, Version 2.0 (the "License"); 59cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * you may not use this file except in compliance with the License. 69cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * You may obtain a copy of the License at 79cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * 89cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * http://www.apache.org/licenses/LICENSE-2.0 99cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * 109cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * Unless required by applicable law or agreed to in writing, software 119cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * distributed under the License is distributed on an "AS IS" BASIS, 129cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * See the License for the specific language governing permissions and 149cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien * limitations under the License. 159cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien */ 169cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 1773abbd59344770601991248cc56846cd199812b8Raph Levien#include <cutils/log.h> 189cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#include <stddef.h> 199cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#include <string.h> 209cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#include <minikin/SparseBitSet.h> 219cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 229cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Leviennamespace android { 239cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 249cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienconst uint32_t SparseBitSet::kNotFound; 259cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 269cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienvoid SparseBitSet::clear() { 279cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mMaxVal = 0; 289cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mIndices.reset(); 299cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mBitmaps.reset(); 309cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien} 319cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 329cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienuint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) { 339cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien bool haveZeroPage = false; 349cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t nonzeroPageEnd = 0; 359cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t nPages = 0; 369cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien for (size_t i = 0; i < nRanges; i++) { 379cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t start = ranges[i * 2]; 389cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t end = ranges[i * 2 + 1]; 399cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t startPage = start >> kLogValuesPerPage; 409cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t endPage = (end - 1) >> kLogValuesPerPage; 419cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (startPage >= nonzeroPageEnd) { 429cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (startPage > nonzeroPageEnd) { 439cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (!haveZeroPage) { 449cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien haveZeroPage = true; 459cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien nPages++; 469cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 479cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 489cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien nPages++; 499cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 509cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien nPages += endPage - startPage; 519cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien nonzeroPageEnd = endPage + 1; 529cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 539cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien return nPages; 549cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien} 559cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 569cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienvoid SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) { 579cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (nRanges == 0) { 589cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mMaxVal = 0; 599cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mIndices.reset(); 609cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mBitmaps.reset(); 619cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien return; 629cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 639cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mMaxVal = ranges[nRanges * 2 - 1]; 649cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien size_t indexSize = (mMaxVal + kPageMask) >> kLogValuesPerPage; 659cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mIndices.reset(new uint32_t[indexSize]); 669cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t nPages = calcNumPages(ranges, nRanges); 679cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mBitmaps.reset(new element[nPages << (kLogValuesPerPage - kLogBitsPerEl)]); 689cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien memset(mBitmaps.get(), 0, nPages << (kLogValuesPerPage - 3)); 699cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mZeroPageIndex = noZeroPage; 709cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t nonzeroPageEnd = 0; 719cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t currentPage = 0; 729cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien for (size_t i = 0; i < nRanges; i++) { 739cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t start = ranges[i * 2]; 749cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t end = ranges[i * 2 + 1]; 7573abbd59344770601991248cc56846cd199812b8Raph Levien LOG_ALWAYS_FATAL_IF(end < start); // make sure range size is nonnegative 769cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t startPage = start >> kLogValuesPerPage; 779cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t endPage = (end - 1) >> kLogValuesPerPage; 789cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (startPage >= nonzeroPageEnd) { 799cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (startPage > nonzeroPageEnd) { 809cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (mZeroPageIndex == noZeroPage) { 819cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 829cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 839cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien for (uint32_t j = nonzeroPageEnd; j < startPage; j++) { 849cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mIndices[j] = mZeroPageIndex; 859cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 869cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 879cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mIndices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 889cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 899cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 909cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) + 919cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien ((start & kPageMask) >> kLogBitsPerEl); 929cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl; 939cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (nElements == 1) { 949cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mBitmaps[index] |= (kElAllOnes >> (start & kElMask)) & 951bbe03d215c9452bc9917111e63f19160cc5f56aDan Austin (kElAllOnes << ((~end + 1) & kElMask)); 969cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } else { 979cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mBitmaps[index] |= kElAllOnes >> (start & kElMask); 989cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien for (size_t j = 1; j < nElements - 1; j++) { 999cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mBitmaps[index + j] = kElAllOnes; 1009cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1011bbe03d215c9452bc9917111e63f19160cc5f56aDan Austin mBitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask); 1029cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1039cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien for (size_t j = startPage + 1; j < endPage + 1; j++) { 1049cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien mIndices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl); 1059cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1069cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien nonzeroPageEnd = endPage + 1; 1079cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1089cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien} 1099cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 1109cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienint SparseBitSet::CountLeadingZeros(element x) { 111329ae0639e332fa0ca85049f738776083b6dbafcBehdad Esfahbod // Note: GCC / clang builtin 112329ae0639e332fa0ca85049f738776083b6dbafcBehdad Esfahbod return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x); 1139cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien} 1149cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 1159cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienuint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const { 1169cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (fromIndex >= mMaxVal) { 1179cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien return kNotFound; 1189cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1199cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t fromPage = fromIndex >> kLogValuesPerPage; 1209cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien const element* bitmap = &mBitmaps[mIndices[fromPage]]; 1219cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl; 1229cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask)); 1239cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (e != 0) { 1249cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien return (fromIndex & ~kElMask) + CountLeadingZeros(e); 1259cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1269cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) { 1279cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien e = bitmap[j]; 1289cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (e != 0) { 1299cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e); 1309cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1319cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1329cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage; 1339cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien for (uint32_t page = fromPage + 1; page < maxPage; page++) { 1349cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t index = mIndices[page]; 1359cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (index == mZeroPageIndex) { 1369cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien continue; 1379cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1389cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien bitmap = &mBitmaps[index]; 1399cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) { 1409cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien e = bitmap[j]; 1419cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (e != 0) { 1429cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e); 1439cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1449cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1459cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 1469cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien return kNotFound; 1479cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien} 1489cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 1499cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien} // namespace android 150