View Javadoc
1   /*
2    * Copyright (C) 2012, Google Inc. and others
3    *
4    * This program and the accompanying materials are made available under the
5    * terms of the Eclipse Distribution License v. 1.0 which is available at
6    * https://www.eclipse.org/org/documents/edl-v10.php.
7    *
8    * SPDX-License-Identifier: BSD-3-Clause
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   * A random access BitSet to supports efficient conversions to
19   * EWAHCompressedBitmap.
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  }