1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.util; |
7 | |
8 | /** |
9 | * A list of bits. |
10 | */ |
11 | public final class BitField { |
12 | |
13 | private static final int ADDRESS_BITS = 6; |
14 | private static final int BITS = 64; |
15 | private static final int ADDRESS_MASK = BITS - 1; |
16 | private long[] data; |
17 | private int maxLength; |
18 | |
19 | public BitField() { |
20 | this(64); |
21 | } |
22 | |
23 | public BitField(int capacity) { |
24 | data = new long[capacity >>> 3]; |
25 | } |
26 | |
27 | /** |
28 | * Get the index of the next bit that is not set. |
29 | * |
30 | * @param fromIndex where to start searching |
31 | * @return the index of the next disabled bit |
32 | */ |
33 | public int nextClearBit(int fromIndex) { |
34 | int i = fromIndex >> ADDRESS_BITS; |
35 | int max = data.length; |
36 | for (; i < max; i++) { |
37 | if (data[i] == -1) { |
38 | continue; |
39 | } |
40 | int j = Math.max(fromIndex, i << ADDRESS_BITS); |
41 | for (int end = j + 64; j < end; j++) { |
42 | if (!get(j)) { |
43 | return j; |
44 | } |
45 | } |
46 | } |
47 | return max << ADDRESS_BITS; |
48 | } |
49 | |
50 | /** |
51 | * Get the bit at the given index. |
52 | * |
53 | * @param i the index |
54 | * @return true if the bit is enabled |
55 | */ |
56 | public boolean get(int i) { |
57 | int addr = i >> ADDRESS_BITS; |
58 | if (addr >= data.length) { |
59 | return false; |
60 | } |
61 | return (data[addr] & getBitMask(i)) != 0; |
62 | } |
63 | |
64 | /** |
65 | * Get the next 8 bits at the given index. |
66 | * The index must be a multiple of 8. |
67 | * |
68 | * @param i the index |
69 | * @return the next 8 bits |
70 | */ |
71 | public int getByte(int i) { |
72 | int addr = i >> ADDRESS_BITS; |
73 | if (addr >= data.length) { |
74 | return 0; |
75 | } |
76 | return (int) (data[addr] >>> (i & (7 << 3)) & 255); |
77 | } |
78 | |
79 | /** |
80 | * Combine the next 8 bits at the given index with OR. |
81 | * The index must be a multiple of 8. |
82 | * |
83 | * @param i the index |
84 | * @param x the next 8 bits (0 - 255) |
85 | */ |
86 | public void setByte(int i, int x) { |
87 | int addr = i >> ADDRESS_BITS; |
88 | checkCapacity(addr); |
89 | data[addr] |= ((long) x) << (i & (7 << 3)); |
90 | if (maxLength < i && x != 0) { |
91 | maxLength = i + 7; |
92 | } |
93 | } |
94 | |
95 | /** |
96 | * Set bit at the given index to 'true'. |
97 | * |
98 | * @param i the index |
99 | */ |
100 | public void set(int i) { |
101 | int addr = i >> ADDRESS_BITS; |
102 | checkCapacity(addr); |
103 | data[addr] |= getBitMask(i); |
104 | if (maxLength < i) { |
105 | maxLength = i; |
106 | } |
107 | } |
108 | |
109 | /** |
110 | * Set bit at the given index to 'false'. |
111 | * |
112 | * @param i the index |
113 | */ |
114 | public void clear(int i) { |
115 | int addr = i >> ADDRESS_BITS; |
116 | if (addr >= data.length) { |
117 | return; |
118 | } |
119 | data[addr] &= ~getBitMask(i); |
120 | } |
121 | |
122 | private static long getBitMask(int i) { |
123 | return 1L << (i & ADDRESS_MASK); |
124 | } |
125 | |
126 | private void checkCapacity(int size) { |
127 | if (size >= data.length) { |
128 | expandCapacity(size); |
129 | } |
130 | } |
131 | |
132 | private void expandCapacity(int size) { |
133 | while (size >= data.length) { |
134 | int newSize = data.length == 0 ? 1 : data.length * 2; |
135 | long[] d = new long[newSize]; |
136 | System.arraycopy(data, 0, d, 0, data.length); |
137 | data = d; |
138 | } |
139 | } |
140 | |
141 | /** |
142 | * Enable or disable a number of bits. |
143 | * |
144 | * @param fromIndex the index of the first bit to enable or disable |
145 | * @param toIndex one plus the index of the last bit to enable or disable |
146 | * @param value the new value |
147 | */ |
148 | public void set(int fromIndex, int toIndex, boolean value) { |
149 | // go backwards so that OutOfMemory happens |
150 | // before some bytes are modified |
151 | for (int i = toIndex - 1; i >= fromIndex; i--) { |
152 | set(i, value); |
153 | } |
154 | if (value) { |
155 | if (toIndex > maxLength) { |
156 | maxLength = toIndex; |
157 | } |
158 | } else { |
159 | if (toIndex >= maxLength) { |
160 | maxLength = fromIndex; |
161 | } |
162 | } |
163 | } |
164 | |
165 | private void set(int i, boolean value) { |
166 | if (value) { |
167 | set(i); |
168 | } else { |
169 | clear(i); |
170 | } |
171 | } |
172 | |
173 | /** |
174 | * Get the index of the highest set bit plus one, or 0 if no bits are set. |
175 | * |
176 | * @return the length of the bit field |
177 | */ |
178 | public int length() { |
179 | int m = maxLength >> ADDRESS_BITS; |
180 | while (m > 0 && data[m] == 0) { |
181 | m--; |
182 | } |
183 | maxLength = (m << ADDRESS_BITS) + |
184 | (64 - Long.numberOfLeadingZeros(data[m])); |
185 | return maxLength; |
186 | } |
187 | |
188 | } |