001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.collections4.bloomfilter; 018 019/** 020 * Contains functions to convert {@code int} indices into Bloom filter bit positions and visa versa. 021 * 022 * <p>The functions view an array of longs as a collection of bit maps each containing 64 bits. The bits are arranged 023 * in memory as a little-endian long value. This matches the requirements of the BitMapExtractor interface.</p> 024 * 025 * @since 4.5.0-M2 026 */ 027public class BitMaps { 028 029 /** A bit shift to apply to an integer to divided by 64 (2^6). */ 030 private static final int DIVIDE_BY_64 = 6; 031 032 /** 033 * Checks if the specified index bit is enabled in the array of bit maps. 034 * <p> 035 * If the bit specified by bitIndex is not in the bit map false is returned. 036 * </p> 037 * 038 * @param bitMaps The array of bit maps. 039 * @param bitIndex the index of the bit to locate. 040 * @return {@code true} if the bit is enabled, {@code false} otherwise. 041 * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked. 042 */ 043 public static boolean contains(final long[] bitMaps, final int bitIndex) { 044 return (bitMaps[getLongIndex(bitIndex)] & getLongBit(bitIndex)) != 0; 045 } 046 047 /** 048 * Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit 049 * longs to store bits starting at index 0. The returned value is a {@code long} with only 050 * 1 bit set. 051 * 052 * <p>The index is assumed to be positive. For a positive index the result will match 053 * {@code 1L << (bitIndex % 64)}.</p> 054 * 055 * <p><em>If the input is negative the behavior is not defined.</em></p> 056 * 057 * @param bitIndex the bit index (assumed to be positive) 058 * @return the filter bit 059 */ 060 public static long getLongBit(final int bitIndex) { 061 // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this 062 // using 0x3f (63) or compute bitIndex % 64. 063 // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and 064 // this will identify an incorrect bit. 065 return 1L << bitIndex; 066 } 067 068 /** 069 * Gets the filter index for the specified bit index assuming the filter is using 64-bit longs 070 * to store bits starting at index 0. 071 * 072 * <p>The index is assumed to be positive. For a positive index the result will match 073 * {@code bitIndex / 64}.</p> 074 * 075 * <p><em>The divide is performed using bit shifts. If the input is negative the behavior 076 * is not defined.</em></p> 077 * 078 * @param bitIndex the bit index (assumed to be positive) 079 * @return the index of the bit map in an array of bit maps. 080 */ 081 public static int getLongIndex(final int bitIndex) { 082 // An integer divide by 64 is equivalent to a shift of 6 bits if the integer is 083 // positive. 084 // We do not explicitly check for a negative here. Instead we use a 085 // signed shift. Any negative index will produce a negative value 086 // by sign-extension and if used as an index into an array it will throw an 087 // exception. 088 return bitIndex >> DIVIDE_BY_64; 089 } 090 091 /** 092 * Performs a modulus calculation on an unsigned long and a positive integer divisor. 093 * 094 * <p>This method computes the same result as {@link Long#remainderUnsigned(long, long)} 095 * but assumes that the divisor is an integer in the range 1 to 2<sup>31</sup> - 1 inclusive, 096 * that is a strictly positive integer size. 097 * 098 * <p><em>If the divisor is negative the behavior is not defined.</em></p> 099 * 100 * @param dividend an unsigned long value to calculate the modulus of. 101 * @param divisor the divisor for the modulus calculation, must be strictly positive. 102 * @return the remainder or modulus value. 103 * @throws ArithmeticException if the divisor is zero 104 * @see Long#remainderUnsigned(long, long) 105 */ 106 public static int mod(final long dividend, final int divisor) { 107 // See Hacker's Delight (2nd ed), section 9.3. 108 // Assume divisor is positive. 109 // Divide half the unsigned number and then double the quotient result. 110 final long quotient = (dividend >>> 1) / divisor << 1; 111 final long remainder = dividend - quotient * divisor; 112 // remainder in [0, 2 * divisor) 113 return (int) (remainder >= divisor ? remainder - divisor : remainder); 114 } 115 116 /** 117 * Creates a new bitmap for the number of bit maps (longs) required for the numberOfBits parameter. 118 * 119 * <p><em>If the input is negative the behavior is not defined.</em></p> 120 * 121 * @param numberOfBits the number of bits to store in the array of bit maps. 122 * @return a new bitmap. 123 */ 124 static long[] newBitMap(final int numberOfBits) { 125 return new long[numberOfBitMaps(numberOfBits)]; 126 } 127 128 /** 129 * Creates a new bitmap for given shape parameter. 130 * 131 * @param shape the shape. 132 * @return a new bitmap. 133 */ 134 static long[] newBitMap(final Shape shape) { 135 return newBitMap(shape.getNumberOfBits()); 136 } 137 138 /** 139 * Calculates the number of bit maps (longs) required for the numberOfBits parameter. 140 * 141 * <p><em>If the input is negative the behavior is not defined.</em></p> 142 * 143 * @param numberOfBits the number of bits to store in the array of bit maps. 144 * @return the number of bit maps necessary. 145 */ 146 public static int numberOfBitMaps(final int numberOfBits) { 147 return (numberOfBits - 1 >> DIVIDE_BY_64) + 1; 148 } 149 150 /** 151 * Calculates the number of bit maps (longs) required for the shape parameter. 152 * 153 * @param shape the shape. 154 * @return the number of bit maps necessary. 155 */ 156 static int numberOfBitMaps(final Shape shape) { 157 return numberOfBitMaps(shape.getNumberOfBits()); 158 } 159 160 /** 161 * Sets the bit in the bit maps. 162 * <p><em>Does not perform range checking</em></p> 163 * 164 * @param bitMaps The array of bit maps. 165 * @param bitIndex the index of the bit to set. 166 * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked. 167 */ 168 public static void set(final long[] bitMaps, final int bitIndex) { 169 bitMaps[getLongIndex(bitIndex)] |= getLongBit(bitIndex); 170 } 171 172 /** Do not instantiate. */ 173 private BitMaps() { 174 } 175}