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 179cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#ifndef MINIKIN_SPARSE_BIT_SET_H 189cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#define MINIKIN_SPARSE_BIT_SET_H 199cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 209cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#include <stdint.h> 219cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#include <sys/types.h> 226261d824595d3590b5355d8dea80949769d8e38eElliott Hughes 236261d824595d3590b5355d8dea80949769d8e38eElliott Hughes#include <memory> 249cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 259cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien// --------------------------------------------------------------------------- 269cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 2714e2d136aaef271ba131f917cf5f27baa31ae5adSeigo Nonakanamespace minikin { 289cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 299cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien// This is an implementation of a set of integers. It is optimized for 309cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien// values that are somewhat sparse, in the ballpark of a maximum value 319cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien// of thousands to millions. It is particularly efficient when there are 329cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien// large gaps. The motivating example is Unicode coverage of a font, but 339cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien// the abstraction itself is fully general. 349cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienclass SparseBitSet { 359cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienpublic: 36db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka // Create an empty bit set. 37db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka SparseBitSet() : mMaxVal(0) {} 389cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 399cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien // Initialize the set to a new value, represented by ranges. For 409cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien // simplicity, these ranges are arranged as pairs of values, 419cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien // inclusive of start, exclusive of end, laid out in a uint32 array. 42db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka SparseBitSet(const uint32_t* ranges, size_t nRanges) : SparseBitSet() { 43db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka initFromRanges(ranges, nRanges); 44db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka } 45db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka 46db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka SparseBitSet(SparseBitSet&&) = default; 47db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka SparseBitSet& operator=(SparseBitSet&&) = default; 489cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 499cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien // Determine whether the value is included in the set 509cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien bool get(uint32_t ch) const { 519cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien if (ch >= mMaxVal) return false; 52fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka const uint32_t *bitmap = &mBitmaps[mIndices[ch >> kLogValuesPerPage]]; 539cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t index = ch & kPageMask; 549cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien return (bitmap[index >> kLogBitsPerEl] & (kElFirst >> (index & kElMask))) != 0; 559cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 569cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 579cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien // One more than the maximum value in the set, or zero if empty 589cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t length() const { 599cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien return mMaxVal; 609cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien } 619cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 629cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien // The next set bit starting at fromIndex, inclusive, or kNotFound 639cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien // if none exists. 649cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t nextSetBit(uint32_t fromIndex) const; 659cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 669cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static const uint32_t kNotFound = ~0u; 679cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 689cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levienprivate: 69db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka void initFromRanges(const uint32_t* ranges, size_t nRanges); 70db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka 71818fbee83a72ca86f64527eb90b2f15ec9b28504Seigo Nonaka static const uint32_t kMaximumCapacity = 0xFFFFFF; 729cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static const int kLogValuesPerPage = 8; 739cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static const int kPageMask = (1 << kLogValuesPerPage) - 1; 749cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static const int kLogBytesPerEl = 2; 759cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static const int kLogBitsPerEl = kLogBytesPerEl + 3; 769cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static const int kElMask = (1 << kLogBitsPerEl) - 1; 779cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien // invariant: sizeof(element) == (1 << kLogBytesPerEl) 789cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien typedef uint32_t element; 799cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static const element kElAllOnes = ~((element)0); 809cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static const element kElFirst = ((element)1) << kElMask; 81818fbee83a72ca86f64527eb90b2f15ec9b28504Seigo Nonaka static const uint16_t noZeroPage = 0xFFFF; 829cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 839cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static uint32_t calcNumPages(const uint32_t* ranges, size_t nRanges); 849cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien static int CountLeadingZeros(element x); 859cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 869cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien uint32_t mMaxVal; 87fbbc5a6b361c623e47a433f83e7200b4e2ba3501Seigo Nonaka 88818fbee83a72ca86f64527eb90b2f15ec9b28504Seigo Nonaka std::unique_ptr<uint16_t[]> mIndices; 89db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka std::unique_ptr<element[]> mBitmaps; 90818fbee83a72ca86f64527eb90b2f15ec9b28504Seigo Nonaka uint16_t mZeroPageIndex; 919cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 92db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka // Forbid copy and assign. 93db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka SparseBitSet(const SparseBitSet&) = delete; 94db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka void operator=(const SparseBitSet&) = delete; 95db1b6cb7765091453d9b4dc7f6c2fb4d7123ab11Seigo Nonaka}; 969cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 9714e2d136aaef271ba131f917cf5f27baa31ae5adSeigo Nonaka} // namespace minikin 989cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien 999cc9bbe1461f359f0b27c5e7645c17dda001ab1dRaph Levien#endif // MINIKIN_SPARSE_BIT_SET_H 100