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