1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the 7 * "License"); you may not use this file except in compliance 8 * with the License. You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 19 package org.apache.giraph.utils; 20 21 import java.util.BitSet; 22 23 /** 24 * Bit set optimized for increasing longs to save storage space. 25 * The general idea is that even though some keys will be added out-of-order, 26 * there is a base key that keeps increasing so that the bit set doesn't get 27 * very big. When there are enough set bits, the bit set gets compacted. 28 * Thread-safe. 29 */ 30 public class IncreasingBitSet { 31 /** Minimum number of bits to shift */ 32 public static final int MIN_BITS_TO_SHIFT = 64 * 1024; 33 /** Bit set used */ 34 private BitSet bitSet = new BitSet(); 35 /** Last base key (all keys < this have been accepted */ 36 private long lastBaseKey = 0; 37 38 /** 39 * Add a key if it is possible. 40 * 41 * @param key Key to add 42 * @return True if the key was added, false otherwise 43 */ 44 public synchronized boolean add(long key) { 45 long remainder = key - lastBaseKey; 46 checkLegalKey(remainder); 47 48 if (remainder < 0) { 49 return false; 50 } 51 if (bitSet.get((int) remainder)) { 52 return false; 53 } 54 bitSet.set((int) remainder); 55 int nextClearBit = bitSet.nextClearBit(0); 56 if (nextClearBit >= MIN_BITS_TO_SHIFT) { 57 bitSet = bitSet.get(nextClearBit, 58 Math.max(nextClearBit, bitSet.length())); 59 lastBaseKey += nextClearBit; 60 } 61 return true; 62 } 63 64 /** 65 * Get the number of set bits 66 * 67 * @return Number of set bits 68 */ 69 public synchronized long cardinality() { 70 long size = bitSet.cardinality(); 71 return size + lastBaseKey; 72 } 73 74 /** 75 * Get the size of the bit set 76 * 77 * @return Size of the bit set 78 */ 79 public synchronized int size() { 80 return bitSet.size(); 81 } 82 83 /** 84 * Check for existence of a key 85 * 86 * @param key Key to check for 87 * @return True if the key exists, false otherwise 88 */ 89 public synchronized boolean has(long key) { 90 long remainder = key - lastBaseKey; 91 checkLegalKey(remainder); 92 93 if (remainder < 0) { 94 return true; 95 } 96 return bitSet.get((int) remainder); 97 } 98 99 /** 100 * Get the last base key (mainly for debugging). 101 * 102 * @return Last base key 103 */ 104 public synchronized long getLastBaseKey() { 105 return lastBaseKey; 106 } 107 108 /** 109 * Check the remainder for validity 110 * 111 * @param remainder Remainder to check 112 */ 113 private void checkLegalKey(long remainder) { 114 if (remainder > Integer.MAX_VALUE) { 115 throw new IllegalArgumentException( 116 "checkLegalKey: Impossible that to add key " + 117 (remainder + lastBaseKey) + " with base " + 118 lastBaseKey + " since the " + 119 "spread is too large (> " + Integer.MAX_VALUE); 120 } 121 } 122 }