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 #ifndef MINIKIN_SPARSE_BIT_SET_H 18 #define MINIKIN_SPARSE_BIT_SET_H 19 20 #include <stdint.h> 21 #include <sys/types.h> 22 23 #include <memory> 24 25 // --------------------------------------------------------------------------- 26 27 namespace minikin { 28 29 // This is an implementation of a set of integers. It is optimized for 30 // values that are somewhat sparse, in the ballpark of a maximum value 31 // of thousands to millions. It is particularly efficient when there are 32 // large gaps. The motivating example is Unicode coverage of a font, but 33 // the abstraction itself is fully general. 34 class SparseBitSet { 35 public: 36 // Create an empty bit set. SparseBitSet()37 SparseBitSet() : mMaxVal(0) {} 38 39 // Initialize the set to a new value, represented by ranges. For 40 // simplicity, these ranges are arranged as pairs of values, 41 // inclusive of start, exclusive of end, laid out in a uint32 array. SparseBitSet(const uint32_t * ranges,size_t nRanges)42 SparseBitSet(const uint32_t* ranges, size_t nRanges) : SparseBitSet() { 43 initFromRanges(ranges, nRanges); 44 } 45 46 SparseBitSet(SparseBitSet&&) = default; 47 SparseBitSet& operator=(SparseBitSet&&) = default; 48 49 // Determine whether the value is included in the set get(uint32_t ch)50 bool get(uint32_t ch) const { 51 if (ch >= mMaxVal) 52 return false; 53 const uint32_t* bitmap = &mBitmaps[mIndices[ch >> kLogValuesPerPage]]; 54 uint32_t index = ch & kPageMask; 55 return (bitmap[index >> kLogBitsPerEl] & (kElFirst >> (index & kElMask))) != 56 0; 57 } 58 59 // One more than the maximum value in the set, or zero if empty length()60 uint32_t length() const { return mMaxVal; } 61 62 // The next set bit starting at fromIndex, inclusive, or kNotFound 63 // if none exists. 64 uint32_t nextSetBit(uint32_t fromIndex) const; 65 66 static const uint32_t kNotFound = ~0u; 67 68 private: 69 void initFromRanges(const uint32_t* ranges, size_t nRanges); 70 71 static const uint32_t kMaximumCapacity = 0xFFFFFF; 72 static const int kLogValuesPerPage = 8; 73 static const int kPageMask = (1 << kLogValuesPerPage) - 1; 74 static const int kLogBytesPerEl = 2; 75 static const int kLogBitsPerEl = kLogBytesPerEl + 3; 76 static const int kElMask = (1 << kLogBitsPerEl) - 1; 77 // invariant: sizeof(element) == (1 << kLogBytesPerEl) 78 typedef uint32_t element; 79 static const element kElAllOnes = ~((element)0); 80 static const element kElFirst = ((element)1) << kElMask; 81 static const uint16_t noZeroPage = 0xFFFF; 82 83 static uint32_t calcNumPages(const uint32_t* ranges, size_t nRanges); 84 static int CountLeadingZeros(element x); 85 86 uint32_t mMaxVal; 87 88 std::unique_ptr<uint16_t[]> mIndices; 89 std::unique_ptr<element[]> mBitmaps; 90 uint16_t mZeroPageIndex; 91 92 // Forbid copy and assign. 93 SparseBitSet(const SparseBitSet&) = delete; 94 void operator=(const SparseBitSet&) = delete; 95 }; 96 97 } // namespace minikin 98 99 #endif // MINIKIN_SPARSE_BIT_SET_H 100