1/*
2 *  Copyright (C) 2010 Apple Inc. All rights reserved.
3 *
4 *  This library is free software; you can redistribute it and/or
5 *  modify it under the terms of the GNU Lesser General Public
6 *  License as published by the Free Software Foundation; either
7 *  version 2 of the License, or (at your option) any later version.
8 *
9 *  This library is distributed in the hope that it will be useful,
10 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 *  Lesser General Public License for more details.
13 *
14 *  You should have received a copy of the GNU Lesser General Public
15 *  License along with this library; if not, write to the Free Software
16 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
17 *
18 */
19#ifndef Bitmap_h
20#define Bitmap_h
21
22#include "FixedArray.h"
23#include "StdLibExtras.h"
24#include <stdint.h>
25#include <string.h>
26
27namespace WTF {
28
29template<size_t size>
30class Bitmap {
31private:
32    typedef uint32_t WordType;
33
34public:
35    Bitmap();
36
37    bool get(size_t) const;
38    void set(size_t);
39    bool testAndSet(size_t);
40    size_t nextPossiblyUnset(size_t) const;
41    void clear(size_t);
42    void clearAll();
43    int64_t findRunOfZeros(size_t) const;
44    size_t count(size_t = 0) const;
45    size_t isEmpty() const;
46    size_t isFull() const;
47
48private:
49    static const WordType wordSize = sizeof(WordType) * 8;
50    static const WordType words = (size + wordSize - 1) / wordSize;
51
52    // the literal '1' is of type signed int.  We want to use an unsigned
53    // version of the correct size when doing the calculations because if
54    // WordType is larger than int, '1 << 31' will first be sign extended
55    // and then casted to unsigned, meaning that set(31) when WordType is
56    // a 64 bit unsigned int would give 0xffff8000
57    static const WordType one = 1;
58
59    FixedArray<WordType, words> bits;
60};
61
62template<size_t size>
63inline Bitmap<size>::Bitmap()
64{
65    clearAll();
66}
67
68template<size_t size>
69inline bool Bitmap<size>::get(size_t n) const
70{
71    return !!(bits[n / wordSize] & (one << (n % wordSize)));
72}
73
74template<size_t size>
75inline void Bitmap<size>::set(size_t n)
76{
77    bits[n / wordSize] |= (one << (n % wordSize));
78}
79
80template<size_t size>
81inline bool Bitmap<size>::testAndSet(size_t n)
82{
83    WordType mask = one << (n % wordSize);
84    size_t index = n / wordSize;
85    bool result = bits[index] & mask;
86    bits[index] |= mask;
87    return result;
88}
89
90template<size_t size>
91inline void Bitmap<size>::clear(size_t n)
92{
93    bits[n / wordSize] &= ~(one << (n % wordSize));
94}
95
96template<size_t size>
97inline void Bitmap<size>::clearAll()
98{
99    memset(bits.data(), 0, sizeof(bits));
100}
101
102template<size_t size>
103inline size_t Bitmap<size>::nextPossiblyUnset(size_t start) const
104{
105    if (!~bits[start / wordSize])
106        return ((start / wordSize) + 1) * wordSize;
107    return start + 1;
108}
109
110template<size_t size>
111inline int64_t Bitmap<size>::findRunOfZeros(size_t runLength) const
112{
113    if (!runLength)
114        runLength = 1;
115
116    for (size_t i = 0; i <= (size - runLength) ; i++) {
117        bool found = true;
118        for (size_t j = i; j <= (i + runLength - 1) ; j++) {
119            if (get(j)) {
120                found = false;
121                break;
122            }
123        }
124        if (found)
125            return i;
126    }
127    return -1;
128}
129
130template<size_t size>
131inline size_t Bitmap<size>::count(size_t start) const
132{
133    size_t result = 0;
134    for ( ; (start % wordSize); ++start) {
135        if (get(start))
136            ++result;
137    }
138    for (size_t i = start / wordSize; i < words; ++i)
139        result += WTF::bitCount(bits[i]);
140    return result;
141}
142
143template<size_t size>
144inline size_t Bitmap<size>::isEmpty() const
145{
146    for (size_t i = 0; i < words; ++i)
147        if (bits[i])
148            return false;
149    return true;
150}
151
152template<size_t size>
153inline size_t Bitmap<size>::isFull() const
154{
155    for (size_t i = 0; i < words; ++i)
156        if (~bits[i])
157            return false;
158    return true;
159}
160
161}
162#endif
163