File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\util\BitField.java.html

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