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