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 <minikin/Buffer.h> 21 #include <sys/types.h> 22 #include <cstdint> 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 SparseBitSet(BufferReader * reader)46 explicit SparseBitSet(BufferReader* reader) : SparseBitSet() { initFromBuffer(reader); } 47 48 SparseBitSet(SparseBitSet&&) = default; 49 SparseBitSet& operator=(SparseBitSet&&) = default; 50 51 void writeTo(BufferWriter* writer) const; 52 53 // Determine whether the value is included in the set get(uint32_t ch)54 bool get(uint32_t ch) const { 55 if (ch >= mMaxVal) return false; 56 const uint32_t* bitmap = &mBitmaps[mIndices[ch >> kLogValuesPerPage]]; 57 uint32_t index = ch & kPageMask; 58 return (bitmap[index >> kLogBitsPerEl] & (kElFirst >> (index & kElMask))) != 0; 59 } 60 61 // One more than the maximum value in the set, or zero if empty length()62 uint32_t length() const { return mMaxVal; } 63 64 // The next set bit starting at fromIndex, inclusive, or kNotFound 65 // if none exists. 66 uint32_t nextSetBit(uint32_t fromIndex) const; 67 68 static const uint32_t kNotFound = ~0u; 69 70 private: 71 void initFromRanges(const uint32_t* ranges, size_t nRanges); 72 void initFromBuffer(BufferReader* reader); 73 74 static const uint32_t kMaximumCapacity = 0xFFFFFF; 75 static const int kLogValuesPerPage = 8; 76 static const int kPageMask = (1 << kLogValuesPerPage) - 1; 77 static const int kLogBytesPerEl = 2; 78 static const int kLogBitsPerEl = kLogBytesPerEl + 3; 79 static const int kElMask = (1 << kLogBitsPerEl) - 1; 80 // invariant: sizeof(element) == (1 << kLogBytesPerEl) 81 typedef uint32_t element; 82 static const element kElAllOnes = ~((element)0); 83 static const element kElFirst = ((element)1) << kElMask; 84 static const uint16_t noZeroPage = 0xFFFF; 85 86 static uint32_t calcNumPages(const uint32_t* ranges, size_t nRanges); 87 static int CountLeadingZeros(element x); 88 89 uint32_t mMaxVal; 90 uint32_t mIndicesCount; 91 const uint16_t* mIndices; 92 uint32_t mBitmapsCount; 93 const element* mBitmaps; 94 uint16_t mZeroPageIndex; 95 96 // Owns allocated memory if this class is created from ranges, otherwise these are nullptr. 97 std::unique_ptr<uint16_t[]> mOwnedIndices; 98 std::unique_ptr<element[]> mOwnedBitmaps; 99 100 // Forbid copy and assign. 101 SparseBitSet(const SparseBitSet&) = delete; 102 void operator=(const SparseBitSet&) = delete; 103 }; 104 105 } // namespace minikin 106 107 #endif // MINIKIN_SPARSE_BIT_SET_H 108