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