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 BitMapProducer interface.</p> 024 * 025 * @since 4.5 026 */ 027public class BitMap { 028 /** A bit shift to apply to an integer to divided by 64 (2^6). */ 029 private static final int DIVIDE_BY_64 = 6; 030 031 /** 032 * Checks if the specified index bit is enabled in the array of bit maps. 033 * 034 * If the bit specified by bitIndex is not in the bit map false is returned. 035 * 036 * @param bitMaps The array of bit maps. 037 * @param bitIndex the index of the bit to locate. 038 * @return {@code true} if the bit is enabled, {@code false} otherwise. 039 * @throws IndexOutOfBoundsException if bitIndex specifies a bit not in the range being tracked. 040 */ 041 public static boolean contains(final long[] bitMaps, final int bitIndex) { 042 return (bitMaps[getLongIndex(bitIndex)] & getLongBit(bitIndex)) != 0; 043 } 044 045 /** 046 * Gets the filter bit mask for the specified bit index assuming the filter is using 64-bit 047 * longs to store bits starting at index 0. The returned value is a {@code long} with only 048 * 1 bit set. 049 * 050 * <p>The index is assumed to be positive. For a positive index the result will match 051 * {@code 1L << (bitIndex % 64)}.</p> 052 * 053 * <p><em>If the input is negative the behavior is not defined.</em></p> 054 * 055 * @param bitIndex the bit index (assumed to be positive) 056 * @return the filter bit 057 */ 058 public static long getLongBit(final int bitIndex) { 059 // Bit shifts only use the first 6 bits. Thus it is not necessary to mask this 060 // using 0x3f (63) or compute bitIndex % 64. 061 // Note: If the index is negative the shift will be (64 - (bitIndex & 0x3f)) and 062 // this will identify an incorrect bit. 063 return 1L << bitIndex; 064 } 065 066 /** 067 * Gets the filter index for the specified bit index assuming the filter is using 64-bit longs 068 * to store bits starting at index 0. 069 * 070 * <p>The index is assumed to be positive. For a positive index the result will match 071 * {@code bitIndex / 64}.</p> 072 * 073 * <p><em>The divide is performed using bit shifts. If the input is negative the behavior 074 * is not defined.</em></p> 075 * 076 * @param bitIndex the bit index (assumed to be positive) 077 * @return the index of the bit map in an array of bit maps. 078 */ 079 public static int getLongIndex(final int bitIndex) { 080 // An integer divide by 64 is equivalent to a shift of 6 bits if the integer is 081 // positive. 082 // We do not explicitly check for a negative here. Instead we use a 083 // signed shift. Any negative index will produce a negative value 084 // by sign-extension and if used as an index into an array it will throw an 085 // exception. 086 return bitIndex >> DIVIDE_BY_64; 087 } 088 089 /** 090 * Performs a modulus calculation on an unsigned long and a positive integer divisor. 091 * 092 * <p>This method computes the same result as {@link Long#remainderUnsigned(long, long)} 093 * but assumes that the divisor is an integer in the range 1 to 2<sup>31</sup> - 1 inclusive, 094 * that is a strictly positive integer size. 095 * 096 * <p><em>If the divisor is negative the behavior is not defined.</em></p> 097 * 098 * @param dividend an unsigned long value to calculate the modulus of. 099 * @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}