1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.bloomfilter;
18
19 /**
20 * Contains functions to convert {@code int} indices into Bloom filter bit positions and visa versa.
21 *
22 * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged
23 * in memory as a little-endian long value. This matches the requirements of the BitMapProducer interface.</p>
24 *
25 * @since 4.5
26 */
27 public class BitMap {
28 /** A bit shift to apply to an integer to divided by 64 (2^6). */
29 private static final int DIVIDE_BY_64 = 6;
30
31 /**
32 * Checks if the specified index bit is enabled in the array of bit maps.
33 *
34 * If the bit specified by bitIndex is not in the bit map false is returned.
35 *
36 * @param bitMaps The array of bit maps.
37 * @param bitIndex the index of the bit to locate.
38 * @return {@code true} if the bit is enabled, {@code false} otherwise.
39 * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
40 */
41 public static boolean contains(final long[] bitMaps, final int bitIndex) {
42 return (bitMaps[getLongIndex(bitIndex)] & getLongBit(bitIndex)) != 0;
43 }
44
45 /**
46 * Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit
47 * longs to store bits starting at index 0. The returned value is a {@code long} with only
48 * 1 bit set.
49 *
50 * <p>The index is assumed to be positive. For a positive index the result will match
51 * {@code 1L << (bitIndex % 64)}.</p>
52 *
53 * <p><em>If the input is negative the behavior is not defined.</em></p>
54 *
55 * @param bitIndex the bit index (assumed to be positive)
56 * @return the filter bit
57 */
58 public static long getLongBit(final int bitIndex) {
59 // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this
60 // using 0x3f (63) or compute bitIndex % 64.
61 // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and
62 // this will identify an incorrect bit.
63 return 1L << bitIndex;
64 }
65
66 /**
67 * Gets the filter index for the specified bit index assuming the filter is using 64-bit longs
68 * to store bits starting at index 0.
69 *
70 * <p>The index is assumed to be positive. For a positive index the result will match
71 * {@code bitIndex / 64}.</p>
72 *
73 * <p><em>The divide is performed using bit shifts. If the input is negative the behavior
74 * is not defined.</em></p>
75 *
76 * @param bitIndex the bit index (assumed to be positive)
77 * @return the index of the bit map in an array of bit maps.
78 */
79 public static int getLongIndex(final int bitIndex) {
80 // An integer divide by 64 is equivalent to a shift of 6 bits if the integer is
81 // positive.
82 // We do not explicitly check for a negative here. Instead we use a
83 // signed shift. Any negative index will produce a negative value
84 // by sign-extension and if used as an index into an array it will throw an
85 // exception.
86 return bitIndex >> DIVIDE_BY_64;
87 }
88
89 /**
90 * Performs a modulus calculation on an unsigned long and a positive integer divisor.
91 *
92 * <p>This method computes the same result as {@link Long#remainderUnsigned(long, long)}
93 * but assumes that the divisor is an integer in the range 1 to 2<sup>31</sup> - 1 inclusive,
94 * that is a strictly positive integer size.
95 *
96 * <p><em>If the divisor is negative the behavior is not defined.</em></p>
97 *
98 * @param dividend an unsigned long value to calculate the modulus of.
99 * @param divisor the divisor for the modulus calculation, must be strictly positive.
100 * @return the remainder or modulus value.
101 * @throws ArithmeticException if the divisor is zero
102 * @see Long#remainderUnsigned(long, long)
103 */
104 public static int mod(final long dividend, final int divisor) {
105 // See Hacker's Delight (2nd ed), section 9.3.
106 // Assume divisor is positive.
107 // Divide half the unsigned number and then double the quotient result.
108 final long quotient = (dividend >>> 1) / divisor << 1;
109 final long remainder = dividend - quotient * divisor;
110 // remainder in [0, 2 * divisor)
111 return (int) (remainder >= divisor ? remainder - divisor : remainder);
112 }
113
114 /**
115 * Calculates the number of bit maps (longs) required for the numberOfBits parameter.
116 *
117 * <p><em>If the input is negative the behavior is not defined.</em></p>
118 *
119 * @param numberOfBits the number of bits to store in the array of bit maps.
120 * @return the number of bit maps necessary.
121 */
122 public static int numberOfBitMaps(final int numberOfBits) {
123 return (numberOfBits - 1 >> DIVIDE_BY_64) + 1;
124 }
125
126 /**
127 * Sets the bit in the bit maps.
128 * <p><em>Does not perform range checking</em></p>
129 *
130 * @param bitMaps The array of bit maps.
131 * @param bitIndex the index of the bit to set.
132 * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked.
133 */
134 public static void set(final long[] bitMaps, final int bitIndex) {
135 bitMaps[getLongIndex(bitIndex)] |= getLongBit(bitIndex);
136 }
137
138 /** Do not instantiate. */
139 private BitMap() {
140 }
141 }