unsafe/bitset/BitSetMethods.java

0001 /*
0002  * Licensed to the Apache Software Foundation (ASF) under one or more
0003  * contributor license agreements.  See the NOTICE file distributed with
0004  * this work for additional information regarding copyright ownership.
0005  * The ASF licenses this file to You under the Apache License, Version 2.0
0006  * (the "License"); you may not use this file except in compliance with
0007  * the License.  You may obtain a copy of the License at
0008  *
0009  *    http://www.apache.org/licenses/LICENSE-2.0
0010  *
0011  * Unless required by applicable law or agreed to in writing, software
0012  * distributed under the License is distributed on an "AS IS" BASIS,
0013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014  * See the License for the specific language governing permissions and
0015  * limitations under the License.
0016  */
0017
0018 package org.apache.spark.unsafe.bitset;
0019
0020 import org.apache.spark.unsafe.Platform;
0021
0022 /**
0023  * Methods for working with fixed-size uncompressed bitsets.
0024  *
0025  * We assume that the bitset data is word-aligned (that is, a multiple of 8 bytes in length).
0026  *
0027  * Each bit occupies exactly one bit of storage.
0028  */
0029 public final class BitSetMethods {
0030
0031   private static final long WORD_SIZE = 8;
0032
0033   private BitSetMethods() {
0034     // Make the default constructor private, since this only holds static methods.
0035   }
0036
0037   /**
0038    * Sets the bit at the specified index to {@code true}.
0039    */
0040   public static void set(Object baseObject, long baseOffset, int index) {
0041     assert index >= 0 : "index (" + index + ") should >= 0";
0042     final long mask = 1L << (index & 0x3f);  // mod 64 and shift
0043     final long wordOffset = baseOffset + (index >> 6) * WORD_SIZE;
0044     final long word = Platform.getLong(baseObject, wordOffset);
0045     Platform.putLong(baseObject, wordOffset, word | mask);
0046   }
0047
0048   /**
0049    * Sets the bit at the specified index to {@code false}.
0050    */
0051   public static void unset(Object baseObject, long baseOffset, int index) {
0052     assert index >= 0 : "index (" + index + ") should >= 0";
0053     final long mask = 1L << (index & 0x3f);  // mod 64 and shift
0054     final long wordOffset = baseOffset + (index >> 6) * WORD_SIZE;
0055     final long word = Platform.getLong(baseObject, wordOffset);
0056     Platform.putLong(baseObject, wordOffset, word & ~mask);
0057   }
0058
0059   /**
0060    * Returns {@code true} if the bit is set at the specified index.
0061    */
0062   public static boolean isSet(Object baseObject, long baseOffset, int index) {
0063     assert index >= 0 : "index (" + index + ") should >= 0";
0064     final long mask = 1L << (index & 0x3f);  // mod 64 and shift
0065     final long wordOffset = baseOffset + (index >> 6) * WORD_SIZE;
0066     final long word = Platform.getLong(baseObject, wordOffset);
0067     return (word & mask) != 0;
0068   }
0069
0070   /**
0071    * Returns {@code true} if any bit is set.
0072    */
0073   public static boolean anySet(Object baseObject, long baseOffset, long bitSetWidthInWords) {
0074     long addr = baseOffset;
0075     for (int i = 0; i < bitSetWidthInWords; i++, addr += WORD_SIZE) {
0076       if (Platform.getLong(baseObject, addr) != 0) {
0077         return true;
0078       }
0079     }
0080     return false;
0081   }
0082
0083   /**
0084    * Returns the index of the first bit that is set to true that occurs on or after the
0085    * specified starting index. If no such bit exists then {@code -1} is returned.
0086    * <p>
0087    * To iterate over the true bits in a BitSet, use the following loop:
0088    * <pre>
0089    * <code>
0090    *  for (long i = bs.nextSetBit(0, sizeInWords); i &gt;= 0;
0091    *    i = bs.nextSetBit(i + 1, sizeInWords)) {
0092    *    // operate on index i here
0093    *  }
0094    * </code>
0095    * </pre>
0096    *
0097    * @param fromIndex the index to start checking from (inclusive)
0098    * @param bitsetSizeInWords the size of the bitset, measured in 8-byte words
0099    * @return the index of the next set bit, or -1 if there is no such bit
0100    */
0101   public static int nextSetBit(
0102       Object baseObject,
0103       long baseOffset,
0104       int fromIndex,
0105       int bitsetSizeInWords) {
0106     int wi = fromIndex >> 6;
0107     if (wi >= bitsetSizeInWords) {
0108       return -1;
0109     }
0110
0111     // Try to find the next set bit in the current word
0112     final int subIndex = fromIndex & 0x3f;
0113     long word = Platform.getLong(baseObject, baseOffset + wi * WORD_SIZE) >> subIndex;
0114     if (word != 0) {
0115       return (wi << 6) + subIndex + java.lang.Long.numberOfTrailingZeros(word);
0116     }
0117
0118     // Find the next set bit in the rest of the words
0119     wi += 1;
0120     while (wi < bitsetSizeInWords) {
0121       word = Platform.getLong(baseObject, baseOffset + wi * WORD_SIZE);
0122       if (word != 0) {
0123         return (wi << 6) + java.lang.Long.numberOfTrailingZeros(word);
0124       }
0125       wi += 1;
0126     }
0127
0128     return -1;
0129   }
0130 }