This project has retired. For details please refer to its Attic page.
IncreasingBitSet xref
View Javadoc

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 }