2011-01-29 Geoffrey Garen <ggaren@apple.com>
[WebKit.git] / Source / JavaScriptCore / wtf / Bitmap.h
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
26 namespace WTF {
27
28 template<size_t size>
29 class Bitmap {
30 private:
31     typedef uint32_t WordType;
32
33 public:
34     Bitmap();
35
36     bool get(size_t) const;
37     void set(size_t);
38     bool testAndSet(size_t);
39     size_t nextPossiblyUnset(size_t) const;
40     void clear(size_t);
41     void clearAll();
42     size_t count(size_t = 0) const;
43     size_t isEmpty() const;
44     size_t isFull() const;
45
46 private:
47     static const WordType wordSize = sizeof(WordType) * 8;
48     static const WordType words = (size + wordSize - 1) / wordSize;
49
50     // the literal '1' is of type signed int.  We want to use an unsigned
51     // version of the correct size when doing the calculations because if
52     // WordType is larger than int, '1 << 31' will first be sign extended
53     // and then casted to unsigned, meaning that set(31) when WordType is
54     // a 64 bit unsigned int would give 0xffff8000
55     static const WordType one = 1;
56
57     FixedArray<WordType, words> bits;
58 };
59
60 template<size_t size>
61 inline Bitmap<size>::Bitmap()
62 {
63     clearAll();
64 }
65
66 template<size_t size>
67 inline bool Bitmap<size>::get(size_t n) const
68 {
69     return !!(bits[n / wordSize] & (one << (n % wordSize)));
70 }
71
72 template<size_t size>
73 inline void Bitmap<size>::set(size_t n)
74 {
75     bits[n / wordSize] |= (one << (n % wordSize));
76 }
77
78 template<size_t size>
79 inline bool Bitmap<size>::testAndSet(size_t n)
80 {
81     WordType mask = one << (n % wordSize);
82     size_t index = n / wordSize;
83     bool result = bits[index] & mask;
84     bits[index] |= mask;
85     return result;
86 }
87
88 template<size_t size>
89 inline void Bitmap<size>::clear(size_t n)
90 {
91     bits[n / wordSize] &= ~(one << (n % wordSize));
92 }
93
94 template<size_t size>
95 inline void Bitmap<size>::clearAll()
96 {
97     memset(bits.data(), 0, sizeof(bits));
98 }
99
100 template<size_t size>
101 inline size_t Bitmap<size>::nextPossiblyUnset(size_t start) const
102 {
103     if (!~bits[start / wordSize])
104         return ((start / wordSize) + 1) * wordSize;
105     return start + 1;
106 }
107
108 template<size_t size>
109 inline size_t Bitmap<size>::count(size_t start) const
110 {
111     size_t result = 0;
112     for ( ; (start % wordSize); ++start) {
113         if (get(start))
114             ++result;
115     }
116     for (size_t i = start / wordSize; i < words; ++i)
117         result += WTF::bitCount(bits[i]);
118     return result;
119 }
120
121 template<size_t size>
122 inline size_t Bitmap<size>::isEmpty() const
123 {
124     for (size_t i = 0; i < words; ++i)
125         if (bits[i])
126             return false;
127     return true;
128 }
129
130 template<size_t size>
131 inline size_t Bitmap<size>::isFull() const
132 {
133     for (size_t i = 0; i < words; ++i)
134         if (~bits[i])
135             return false;
136     return true;
137 }
138
139 }
140 #endif