1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.file;
12
13 import java.util.Arrays;
14
15 import com.googlecode.javaewah.EWAHCompressedBitmap;
16
17
18
19
20
21 final class BitSet {
22
23 private long[] words;
24
25 BitSet(int initialCapacity) {
26 words = new long[block(initialCapacity) + 1];
27 }
28
29 final void clear() {
30 Arrays.fill(words, 0);
31 }
32
33 final void set(int position) {
34 int block = block(position);
35 if (block >= words.length) {
36 long[] buf = new long[2 * block(position)];
37 System.arraycopy(words, 0, buf, 0, words.length);
38 words = buf;
39 }
40 words[block] |= mask(position);
41 }
42
43 final void clear(int position) {
44 int block = block(position);
45 if (block < words.length)
46 words[block] &= ~mask(position);
47 }
48
49 final boolean get(int position) {
50 int block = block(position);
51 return block < words.length && (words[block] & mask(position)) != 0;
52 }
53
54 final EWAHCompressedBitmap toEWAHCompressedBitmap() {
55 EWAHCompressedBitmap compressed = new EWAHCompressedBitmap(
56 words.length);
57 int runningEmptyWords = 0;
58 long lastNonEmptyWord = 0;
59 for (long word : words) {
60 if (word == 0) {
61 runningEmptyWords++;
62 continue;
63 }
64
65 if (lastNonEmptyWord != 0)
66 compressed.addWord(lastNonEmptyWord);
67
68 if (runningEmptyWords > 0) {
69 compressed.addStreamOfEmptyWords(false, runningEmptyWords);
70 runningEmptyWords = 0;
71 }
72
73 lastNonEmptyWord = word;
74 }
75 int bitsThatMatter = 64 - Long.numberOfLeadingZeros(lastNonEmptyWord);
76 if (bitsThatMatter > 0)
77 compressed.addWord(lastNonEmptyWord, bitsThatMatter);
78 return compressed;
79 }
80
81 private static final int block(int position) {
82 return position >> 6;
83 }
84
85 private static final long mask(int position) {
86 return 1L << position;
87 }
88 }