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 <stdlib.h> 22 #include <sys/types.h> 23 24 #include <cstdint> 25 #include <memory> 26 27 // --------------------------------------------------------------------------- 28 29 namespace minikin { 30 31 // This is an implementation of a set of integers. It is optimized for 32 // values that are somewhat sparse, in the ballpark of a maximum value 33 // of thousands to millions. It is particularly efficient when there are 34 // large gaps. The motivating example is Unicode coverage of a font, but 35 // the abstraction itself is fully general. 36 class SparseBitSet { 37 public: 38 // Create an empty bit set. SparseBitSet()39 SparseBitSet() : mData(nullptr) {} 40 41 // Initialize the set to a new value, represented by ranges. For 42 // simplicity, these ranges are arranged as pairs of values, 43 // inclusive of start, exclusive of end, laid out in a uint32 array. SparseBitSet(const uint32_t * ranges,size_t nRanges)44 SparseBitSet(const uint32_t* ranges, size_t nRanges) : SparseBitSet() { 45 initFromRanges(ranges, nRanges); 46 } 47 SparseBitSet(BufferReader * reader)48 explicit SparseBitSet(BufferReader* reader) : SparseBitSet() { initFromBuffer(reader); } 49 50 SparseBitSet(SparseBitSet&&) = default; 51 SparseBitSet& operator=(SparseBitSet&&) = default; 52 53 void writeTo(BufferWriter* writer) const; 54 55 // Determine whether the value is included in the set get(uint32_t ch)56 bool get(uint32_t ch) const { 57 if (ch >= length()) return false; 58 const uint32_t* bitmap = mData->bitmaps() + mData->indices()[ch >> kLogValuesPerPage]; 59 uint32_t index = ch & kPageMask; 60 return (bitmap[index >> kLogBitsPerEl] & (kElFirst >> (index & kElMask))) != 0; 61 } 62 63 // One more than the maximum value in the set, or zero if empty length()64 uint32_t length() const { return mData != nullptr ? mData->mMaxVal : 0; } 65 empty()66 bool empty() const { return mData == nullptr || mData->mMaxVal == 0; } 67 68 // The next set bit starting at fromIndex, inclusive, or kNotFound 69 // if none exists. 70 uint32_t nextSetBit(uint32_t fromIndex) const; 71 72 static const uint32_t kNotFound = ~0u; 73 74 private: 75 void initFromRanges(const uint32_t* ranges, size_t nRanges); 76 void initFromBuffer(BufferReader* reader); 77 78 static const uint32_t kMaximumCapacity = 0xFFFFFF; 79 static const int kLogValuesPerPage = 8; 80 static const int kPageMask = (1 << kLogValuesPerPage) - 1; 81 static const int kLogBytesPerEl = 2; 82 static const int kLogBitsPerEl = kLogBytesPerEl + 3; 83 static const int kElMask = (1 << kLogBitsPerEl) - 1; 84 // invariant: sizeof(element) == (1 << kLogBytesPerEl) 85 typedef uint32_t element; 86 static const element kElAllOnes = ~((element)0); 87 static const element kElFirst = ((element)1) << kElMask; 88 static const uint16_t noZeroPage = 0xFFFF; 89 90 static uint32_t calcNumPages(const uint32_t* ranges, size_t nRanges); 91 static int CountLeadingZeros(element x); 92 93 // MappableData represents memory block holding SparseBitSet's fields. 94 // 'packed' is used so that the object layout won't change between 95 // 32-bit and 64-bit processes. 96 // 'aligned(4)' is only for optimization. 97 struct __attribute__((packed, aligned(4))) MappableData { 98 uint32_t mMaxVal; 99 uint32_t mIndicesCount; 100 uint32_t mBitmapsCount; 101 uint16_t mZeroPageIndex; 102 // Whether the memory is mapped (BufferReader::map()) or allocated 103 // (malloc()). 104 uint16_t mIsMapped; 105 // mArray packs two arrays: 106 // element mBitmaps[mBitmapsCount]; 107 // uint16_t mIndices[mIndicesCount]; 108 __attribute__((aligned(4))) uint32_t mArray[]; bitmapsMappableData109 const element* bitmaps() const { return mArray; } bitmapsMappableData110 element* bitmaps() { return mArray; } indicesMappableData111 const uint16_t* indices() const { 112 return reinterpret_cast<const uint16_t*>(mArray + mBitmapsCount); 113 } indicesMappableData114 uint16_t* indices() { return reinterpret_cast<uint16_t*>(mArray + mBitmapsCount); } sizeMappableData115 size_t size() const { return calcSize(mIndicesCount, mBitmapsCount); } calcSizeMappableData116 static size_t calcSize(uint32_t indicesCount, uint32_t bitmapsCount) { 117 static_assert(std::is_same<element, uint32_t>::value); 118 static_assert(sizeof(uint32_t) == 4); 119 static_assert(sizeof(uint16_t) == 2); 120 // Round-up indicesCount / 2 121 size_t arrayCount = bitmapsCount + (indicesCount + 1) / 2; 122 return offsetof(MappableData, mArray) + sizeof(uint32_t) * arrayCount; 123 } 124 static MappableData* allocate(uint32_t indicesCount, uint32_t bitmapsCount); 125 }; 126 127 // MappableDataDeleter does NOT call free() if the data is on a memory map. 128 class MappableDataDeleter { 129 public: operator()130 void operator()(const MappableData* data) const { 131 if (data != nullptr && !data->mIsMapped) free((void*)data); 132 } 133 }; 134 135 std::unique_ptr<const MappableData, MappableDataDeleter> mData; 136 137 // Forbid copy and assign. 138 SparseBitSet(const SparseBitSet&) = delete; 139 SparseBitSet& operator=(const SparseBitSet&) = delete; 140 }; 141 142 } // namespace minikin 143 144 #endif // MINIKIN_SPARSE_BIT_SET_H 145