Coverage Report

Coverage Report - org.apache.giraph.utils.IncreasingBitSet

Classes in this File

Line Coverage

Branch Coverage

Complexity

IncreasingBitSet

0/28

0/10

2.5

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 package org.apache.giraph.utils;
 
 import java.util.BitSet;
 
 /**
  * Bit set optimized for increasing longs to save storage space.
  * The general idea is that even though some keys will be added out-of-order,
  * there is a base key that keeps increasing so that the bit set doesn't get
  * very big.  When there are enough set bits, the bit set gets compacted.
  * Thread-safe.
  */
 public class IncreasingBitSet {
   /** Minimum number of bits to shift */
   public static final int MIN_BITS_TO_SHIFT = 64 * 1024;
   /** Bit set used */
   private BitSet bitSet = new BitSet();
   /** Last base key (all keys < this have been accepted */
   private long lastBaseKey = 0;
 
   /**
    * Add a key if it is possible.
    *
    * @param key Key to add
    * @return True if the key was added, false otherwise
    */
   public synchronized boolean add(long key) {
     long remainder = key - lastBaseKey;
     checkLegalKey(remainder);
 
     if (remainder < 0) {
       return false;
     }
     if (bitSet.get((int) remainder)) {
       return false;
     }
     bitSet.set((int) remainder);
     int nextClearBit = bitSet.nextClearBit(0);
     if (nextClearBit >= MIN_BITS_TO_SHIFT) {
       bitSet = bitSet.get(nextClearBit,
           Math.max(nextClearBit, bitSet.length()));
       lastBaseKey += nextClearBit;
     }
     return true;
   }
 
   /**
    * Get the number of set bits
    *
    * @return Number of set bits
    */
   public synchronized long cardinality() {
     long size = bitSet.cardinality();
     return size + lastBaseKey;
   }
 
   /**
    * Get the size of the bit set
    *
    * @return Size of the bit set
    */
   public synchronized int size() {
     return bitSet.size();
   }
 
   /**
    * Check for existence of a key
    *
    * @param key Key to check for
    * @return True if the key exists, false otherwise
    */
   public synchronized boolean has(long key) {
     long remainder = key - lastBaseKey;
     checkLegalKey(remainder);
 
     if (remainder < 0) {
       return true;
     }
     return bitSet.get((int) remainder);
   }
 
   /**
    * Get the last base key (mainly for debugging).
    *
    * @return Last base key
    */
   public synchronized long getLastBaseKey() {
     return lastBaseKey;
   }
 
   /**
    * Check the remainder for validity
    *
    * @param remainder Remainder to check
    */
   private void checkLegalKey(long remainder) {
     if (remainder > Integer.MAX_VALUE) {
       throw new IllegalArgumentException(
           "checkLegalKey: Impossible that to add key " +
           (remainder + lastBaseKey) + " with base " +
           lastBaseKey + " since the " +
           "spread is too large (> " + Integer.MAX_VALUE);
     }
   }
 }

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	0	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	0	private BitSet bitSet = new BitSet();
35		/** Last base key (all keys < this have been accepted */
36	0	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	0	long remainder = key - lastBaseKey;
46	0	checkLegalKey(remainder);
47
48	0	if (remainder < 0) {
49	0	return false;
50		}
51	0	if (bitSet.get((int) remainder)) {
52	0	return false;
53		}
54	0	bitSet.set((int) remainder);
55	0	int nextClearBit = bitSet.nextClearBit(0);
56	0	if (nextClearBit >= MIN_BITS_TO_SHIFT) {
57	0	bitSet = bitSet.get(nextClearBit,
58	0	Math.max(nextClearBit, bitSet.length()));
59	0	lastBaseKey += nextClearBit;
60		}
61	0	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	0	long size = bitSet.cardinality();
71	0	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	0	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	0	long remainder = key - lastBaseKey;
91	0	checkLegalKey(remainder);
92
93	0	if (remainder < 0) {
94	0	return true;
95		}
96	0	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	0	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	0	if (remainder > Integer.MAX_VALUE) {
115	0	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	0	}
122		}