    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}