1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 package org.apache.hadoop.hbase.util;
22
23 import org.apache.hadoop.io.Writable;
24
25 import java.io.DataInput;
26 import java.io.DataOutput;
27 import java.io.IOException;
28 import java.nio.ByteBuffer;
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 public class DynamicByteBloomFilter implements BloomFilter {
62
63 public static final int VERSION = 2;
64
65 protected final int keyInterval;
66
67 protected final float errorRate;
68
69 protected final int hashType;
70
71 protected int curKeys;
72
73 protected int readMatrixSize;
74
75 protected ByteBloomFilter[] matrix;
76
77
78
79
80
81
82 public DynamicByteBloomFilter(ByteBuffer meta) throws IllegalArgumentException {
83 int version = meta.getInt();
84 if (version != VERSION) throw new IllegalArgumentException("Bad version");
85
86 this.keyInterval = meta.getInt();
87 this.errorRate = meta.getFloat();
88 this.hashType = meta.getInt();
89 this.readMatrixSize = meta.getInt();
90 this.curKeys = meta.getInt();
91
92 readSanityCheck();
93
94 this.matrix = new ByteBloomFilter[1];
95 this.matrix[0] = new ByteBloomFilter(keyInterval, errorRate, hashType, 0);
96 }
97
98
99
100
101
102
103
104
105
106 public DynamicByteBloomFilter(int keyInterval, float errorRate, int hashType)
107 throws IllegalArgumentException {
108 this.keyInterval = keyInterval;
109 this.errorRate = errorRate;
110 this.hashType = hashType;
111 this.curKeys = 0;
112
113 if(keyInterval <= 0) {
114 throw new IllegalArgumentException("keyCount must be > 0");
115 }
116
117 this.matrix = new ByteBloomFilter[1];
118 this.matrix[0] = new ByteBloomFilter(keyInterval, errorRate, hashType, 0);
119 }
120
121 @Override
122 public void allocBloom() {
123 this.matrix[0].allocBloom();
124 }
125
126 void readSanityCheck() throws IllegalArgumentException {
127 if (this.curKeys <= 0) {
128 throw new IllegalArgumentException("last bloom's key count invalid");
129 }
130
131 if (this.readMatrixSize <= 0) {
132 throw new IllegalArgumentException("matrix size must be known");
133 }
134 }
135
136 @Override
137 public void add(byte []buf, int offset, int len) {
138 BloomFilter bf = getCurBloom();
139
140 if (bf == null) {
141 addRow();
142 bf = matrix[matrix.length - 1];
143 curKeys = 0;
144 }
145
146 bf.add(buf, offset, len);
147 curKeys++;
148 }
149
150 @Override
151 public void add(byte []buf) {
152 add(buf, 0, buf.length);
153 }
154
155
156
157
158 boolean contains(byte [] buf) {
159 return contains(buf, 0, buf.length);
160 }
161
162
163
164
165 boolean contains(byte [] buf, int offset, int length) {
166 for (int i = 0; i < matrix.length; i++) {
167 if (matrix[i].contains(buf, offset, length)) {
168 return true;
169 }
170 }
171 return false;
172 }
173
174 @Override
175 public boolean contains(byte [] buf, ByteBuffer theBloom) {
176 return contains(buf, 0, buf.length, theBloom);
177 }
178
179 @Override
180 public boolean contains(byte[] buf, int offset, int length,
181 ByteBuffer theBloom) {
182 if(offset + length > buf.length) {
183 return false;
184 }
185
186
187 int bytesPerBloom = this.matrix[0].getByteSize();
188
189 if(theBloom.limit() != bytesPerBloom * readMatrixSize) {
190 throw new IllegalArgumentException("Bloom does not match expected size");
191 }
192
193 ByteBuffer tmp = theBloom.duplicate();
194
195
196 for (int m = 0; m < readMatrixSize; ++m) {
197 tmp.position(m* bytesPerBloom);
198 tmp.limit(tmp.position() + bytesPerBloom);
199 boolean match = this.matrix[0].contains(buf, offset, length, tmp.slice());
200 if (match) {
201 return true;
202 }
203 }
204
205
206 return false;
207 }
208
209 int bloomCount() {
210 return Math.max(this.matrix.length, this.readMatrixSize);
211 }
212
213 @Override
214 public int getKeyCount() {
215 return (bloomCount()-1) * this.keyInterval + this.curKeys;
216 }
217
218 @Override
219 public int getMaxKeys() {
220 return bloomCount() * this.keyInterval;
221 }
222
223 @Override
224 public int getByteSize() {
225 return bloomCount() * this.matrix[0].getByteSize();
226 }
227
228 @Override
229 public void compactBloom() {
230 }
231
232
233
234
235 private void addRow() {
236 ByteBloomFilter[] tmp = new ByteBloomFilter[matrix.length + 1];
237
238 for (int i = 0; i < matrix.length; i++) {
239 tmp[i] = matrix[i];
240 }
241
242 tmp[tmp.length-1] = new ByteBloomFilter(keyInterval, errorRate, hashType, 0);
243 tmp[tmp.length-1].allocBloom();
244 matrix = tmp;
245 }
246
247
248
249
250
251
252 private BloomFilter getCurBloom() {
253 if (curKeys >= keyInterval) {
254 return null;
255 }
256
257 return matrix[matrix.length - 1];
258 }
259
260 @Override
261 public Writable getMetaWriter() {
262 return new MetaWriter();
263 }
264
265 @Override
266 public Writable getDataWriter() {
267 return new DataWriter();
268 }
269
270 private class MetaWriter implements Writable {
271 protected MetaWriter() {}
272 @Override
273 public void readFields(DataInput arg0) throws IOException {
274 throw new IOException("Cant read with this class.");
275 }
276
277 @Override
278 public void write(DataOutput out) throws IOException {
279 out.writeInt(VERSION);
280 out.writeInt(keyInterval);
281 out.writeFloat(errorRate);
282 out.writeInt(hashType);
283 out.writeInt(matrix.length);
284 out.writeInt(curKeys);
285 }
286 }
287
288 private class DataWriter implements Writable {
289 protected DataWriter() {}
290 @Override
291 public void readFields(DataInput arg0) throws IOException {
292 throw new IOException("Cant read with this class.");
293 }
294
295 @Override
296 public void write(DataOutput out) throws IOException {
297 for (int i = 0; i < matrix.length; ++i) {
298 matrix[i].writeBloom(out);
299 }
300 }
301 }
302 }