SparseBitSet.cpp revision dff5e5d5a1d0f17a1b5d2fd197b5a6389bc41e28 
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#define LOG_TAG "SparseBitSet"
18
19#include <stddef.h>
20#include <string.h>
21
22#include <log/log.h>
23
24#include <minikin/SparseBitSet.h>
25
26namespace minikin {
27
28const uint32_t SparseBitSet::kNotFound;
29
30void SparseBitSet::clear() {
31    mMaxVal = 0;
32    if (mOwnIndicesAndBitmaps) {
33        delete[] mIndices;
34        delete[] mBitmaps;
35        mIndexSize = 0;
36        mBitmapSize = 0;
37        mOwnIndicesAndBitmaps = false;
38    }
39}
40
41uint32_t SparseBitSet::calcNumPages(const uint32_t* ranges, size_t nRanges) {
42    bool haveZeroPage = false;
43    uint32_t nonzeroPageEnd = 0;
44    uint32_t nPages = 0;
45    for (size_t i = 0; i < nRanges; i++) {
46        uint32_t start = ranges[i * 2];
47        uint32_t end = ranges[i * 2 + 1];
48        uint32_t startPage = start >> kLogValuesPerPage;
49        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
50        if (startPage >= nonzeroPageEnd) {
51            if (startPage > nonzeroPageEnd) {
52                if (!haveZeroPage) {
53                    haveZeroPage = true;
54                    nPages++;
55                }
56            }
57            nPages++;
58        }
59        nPages += endPage - startPage;
60        nonzeroPageEnd = endPage + 1;
61    }
62    return nPages;
63}
64
65void SparseBitSet::initFromRanges(const uint32_t* ranges, size_t nRanges) {
66    if (nRanges == 0) {
67        clear();
68        return;
69    }
70    mMaxVal = ranges[nRanges * 2 - 1];
71    mIndexSize = (mMaxVal + kPageMask) >> kLogValuesPerPage;
72    uint32_t* indices = new uint32_t[mIndexSize];
73    uint32_t nPages = calcNumPages(ranges, nRanges);
74    mBitmapSize = nPages << (kLogValuesPerPage - kLogBitsPerEl);
75    element* bitmaps = new element[mBitmapSize];
76    mOwnIndicesAndBitmaps = true;
77    memset(bitmaps, 0, nPages << (kLogValuesPerPage - 3));
78    mZeroPageIndex = noZeroPage;
79    uint32_t nonzeroPageEnd = 0;
80    uint32_t currentPage = 0;
81    for (size_t i = 0; i < nRanges; i++) {
82        uint32_t start = ranges[i * 2];
83        uint32_t end = ranges[i * 2 + 1];
84        LOG_ALWAYS_FATAL_IF(end < start);  // make sure range size is nonnegative
85        uint32_t startPage = start >> kLogValuesPerPage;
86        uint32_t endPage = (end - 1) >> kLogValuesPerPage;
87        if (startPage >= nonzeroPageEnd) {
88            if (startPage > nonzeroPageEnd) {
89                if (mZeroPageIndex == noZeroPage) {
90                    mZeroPageIndex = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
91                }
92                for (uint32_t j = nonzeroPageEnd; j < startPage; j++) {
93                    indices[j] = mZeroPageIndex;
94                }
95            }
96            indices[startPage] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
97        }
98
99        size_t index = ((currentPage - 1) << (kLogValuesPerPage - kLogBitsPerEl)) +
100            ((start & kPageMask) >> kLogBitsPerEl);
101        size_t nElements = (end - (start & ~kElMask) + kElMask) >> kLogBitsPerEl;
102        if (nElements == 1) {
103            bitmaps[index] |= (kElAllOnes >> (start & kElMask)) &
104                (kElAllOnes << ((~end + 1) & kElMask));
105        } else {
106            bitmaps[index] |= kElAllOnes >> (start & kElMask);
107            for (size_t j = 1; j < nElements - 1; j++) {
108                bitmaps[index + j] = kElAllOnes;
109            }
110            bitmaps[index + nElements - 1] |= kElAllOnes << ((~end + 1) & kElMask);
111        }
112        for (size_t j = startPage + 1; j < endPage + 1; j++) {
113            indices[j] = (currentPage++) << (kLogValuesPerPage - kLogBitsPerEl);
114        }
115        nonzeroPageEnd = endPage + 1;
116    }
117    mBitmaps = bitmaps;
118    mIndices = indices;
119}
120
121int SparseBitSet::CountLeadingZeros(element x) {
122    // Note: GCC / clang builtin
123    return sizeof(element) <= sizeof(int) ? __builtin_clz(x) : __builtin_clzl(x);
124}
125
126uint32_t SparseBitSet::nextSetBit(uint32_t fromIndex) const {
127    if (fromIndex >= mMaxVal) {
128        return kNotFound;
129    }
130    uint32_t fromPage = fromIndex >> kLogValuesPerPage;
131    const element* bitmap = &mBitmaps[mIndices[fromPage]];
132    uint32_t offset = (fromIndex & kPageMask) >> kLogBitsPerEl;
133    element e = bitmap[offset] & (kElAllOnes >> (fromIndex & kElMask));
134    if (e != 0) {
135        return (fromIndex & ~kElMask) + CountLeadingZeros(e);
136    }
137    for (uint32_t j = offset + 1; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
138        e = bitmap[j];
139        if (e != 0) {
140            return (fromIndex & ~kPageMask) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
141        }
142    }
143    uint32_t maxPage = (mMaxVal + kPageMask) >> kLogValuesPerPage;
144    for (uint32_t page = fromPage + 1; page < maxPage; page++) {
145        uint32_t index = mIndices[page];
146        if (index == mZeroPageIndex) {
147            continue;
148        }
149        bitmap = &mBitmaps[index];
150        for (uint32_t j = 0; j < (1 << (kLogValuesPerPage - kLogBitsPerEl)); j++) {
151            e = bitmap[j];
152            if (e != 0) {
153                return (page << kLogValuesPerPage) + (j << kLogBitsPerEl) + CountLeadingZeros(e);
154            }
155        }
156    }
157    return kNotFound;
158}
159
160}  // namespace minikin
161