platform/util/src/com/intellij/util/containers/ConcurrentBitSet.java - platform/tools/idea - Git at Google

 /*
  * Copyright 2000-2014 JetBrains s.r.o.
  *
  * Licensed 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 com.intellij.util.containers;

 import org.jetbrains.annotations.NotNull;

 import java.io.File;
 import java.io.IOException;
 import java.io.RandomAccessFile;
 import java.util.concurrent.atomic.AtomicLongArray;
 import java.util.concurrent.atomic.AtomicReferenceArray;

 /**
  * This class is a thread-safe version of the
  * {@code java.util.BitSet} except for some methods which don't make sense in concurrent environment or those i was too lazy to implement.
  *
  * Implementation is based on "Lock-free Dynamically Resizable Arrays" by Dechev, Pirkelbauer, Bjarne Stroustrup.
  * http://www.stroustrup.com/lock-free-vector.pdf
  *
  * @see java.util.BitSet
  */
 public class ConcurrentBitSet {
   public ConcurrentBitSet() {
   }

   /**
    * An array of 32 longword vectors.
    * Vector at index "i" has length of (1 << i) long words.
    * Each long word stores next 64 bits part of the set.
    * Therefore the i-th bit of the set is stored in {@code arrays.get(arrayIndex(i)).get(wordIndexInArray(i))} word in the {@code 1L << i} position.
    */
   private final AtomicReferenceArray<AtomicLongArray> arrays = new AtomicReferenceArray<AtomicLongArray>(32);
   private static int arrayIndex(int bitIndex) {
     int i = (bitIndex >> ADDRESS_BITS_PER_WORD) + 1;
     return 31 - Integer.numberOfLeadingZeros(i);
   }
   private static int wordIndexInArray(int bitIndex) {
     int i = (bitIndex >> ADDRESS_BITS_PER_WORD) + 1;
     return clearHighestBit(i);
   }

   private static int clearHighestBit(int index) {
     int i = index>>1;
     i |= i >>  1;
     i |= i >>  2;
     i |= i >>  4;
     i |= i >>  8;
     i |= i >> 16;
     return index & i;
   }

   /* BitSets are packed into arrays of "words."  Currently a word is
      a long, which consists of 64 bits, requiring 6 address bits.
      The choice of word size is determined purely by performance concerns.
   */
   private static final int ADDRESS_BITS_PER_WORD = 6;
   private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

   /* Used to shift left or right for a partial word mask */
   private static final long WORD_MASK = -1L;

   /**
    * Sets the bit at the specified index to the complement of its
    * current value.
    *
    * @param bitIndex the index of the bit to flip
    * @return new bit value
    * @throws IndexOutOfBoundsException if the specified index is negative
    */
   public boolean flip(int bitIndex) {
     if (bitIndex < 0) {
       throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
     }

     AtomicLongArray array = getOrCreateArray(bitIndex);

     int wordIndexInArray = wordIndexInArray(bitIndex);

     long word;
     long newWord;
     do {
       word = array.get(wordIndexInArray);
       newWord = word ^ (1L << bitIndex);
     }
     while (!array.compareAndSet(wordIndexInArray, word, newWord));
     return (newWord & (1L << bitIndex)) != 0;
   }

   /**
    * Sets the bit at the specified index to {@code true}.
    *
    * @param bitIndex a bit index
    * @return previous value
    * @throws IndexOutOfBoundsException if the specified index is negative
    */
   public boolean set(int bitIndex) {
     if (bitIndex < 0) {
       throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
     }

     AtomicLongArray array = getOrCreateArray(bitIndex);

     int wordIndexInArray = wordIndexInArray(bitIndex);
     long word;
     long newWord;
     boolean previousBit;
     do {
       word = array.get(wordIndexInArray);
       previousBit = (word & (1L << bitIndex)) != 0;
       newWord = word | (1L << bitIndex);
     }
     while (!array.compareAndSet(wordIndexInArray, word, newWord));
     return previousBit;
   }

   /**
    * Sets the bit at the specified index to the specified value.
    *
    * @param bitIndex a bit index
    * @param value    a boolean value to set
    * @throws IndexOutOfBoundsException if the specified index is negative
    */
   public void set(int bitIndex, boolean value) {
     if (value) {
       set(bitIndex);
     }
     else {
       clear(bitIndex);
     }
   }

   /**
    * Sets the bit specified by the index to {@code false}.
    *
    * @param bitIndex the index of the bit to be cleared
    * @throws IndexOutOfBoundsException if the specified index is negative
    * @return previous value
    */
   public boolean clear(int bitIndex) {
     if (bitIndex < 0) {
       throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
     }

     AtomicLongArray array = getOrCreateArray(bitIndex);

     int wordIndexInArray = wordIndexInArray(bitIndex);
     long word;
     long newWord;
     boolean previousBit;
     do {
       word = array.get(wordIndexInArray);
       previousBit = (word & (1L << bitIndex)) != 0;
       newWord = word & ~ (1L << bitIndex);
     }
     while (!array.compareAndSet(wordIndexInArray, word, newWord));
     return previousBit;
   }

   @NotNull
   private AtomicLongArray getOrCreateArray(int bitIndex) {
     int arrayIndex = arrayIndex(bitIndex);
     AtomicLongArray array;

     // while loop is here because of clear() method
     while ((array = arrays.get(arrayIndex)) == null) {
       arrays.compareAndSet(arrayIndex, null, new AtomicLongArray(1<<arrayIndex));
     }
     return array;
   }


   /**
    * Clear method in presense of concurrency complicates everything to no end.
    * PLEASE REWRITE EVERY OTHER METHOD IF EVER DECIDE TO IMPLEMENT THIS
    */
   public void clear() {
     for (int i=0; i<arrays.length();i++) {
       arrays.set(i, null);
     }
   }

   /**
    * Returns the value of the bit with the specified index. The value
    * is {@code true} if the bit with the index {@code bitIndex}
    * is currently set; otherwise, the result is {@code false}.
    *
    * @param bitIndex the bit index
    * @return the value of the bit with the specified index
    * @throws IndexOutOfBoundsException if the specified index is negative
    */
   public boolean get(int bitIndex) {
     if (bitIndex < 0) {
       throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
     }

     int arrayIndex = arrayIndex(bitIndex);
     AtomicLongArray array = arrays.get(arrayIndex);
     if (array == null) {
       return false;
     }

     int wordIndexInArray = wordIndexInArray(bitIndex);
     long word = array.get(wordIndexInArray);
     return (word & (1L<<bitIndex)) != 0;
   }

   /**
   * Returns the index of the first bit that is set to {@code true}
   * that occurs on or after the specified starting index. If no such
   * bit exists then {@code -1} is returned.
   * <p/>
   * <p>To iterate over the {@code true} bits,
   * use the following loop:
   * <p/>
   * <pre> {@code
   * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
   *     // operate on index i here
   * }}</pre>
   *
   * @param fromIndex the index to start checking from (inclusive)
   * @return the index of the next set bit, or {@code -1} if there
   * is no such bit
   * @throws IndexOutOfBoundsException if the specified index is negative
   */
   public int nextSetBit(int fromIndex) {
     if (fromIndex < 0) {
       throw new IndexOutOfBoundsException("bitIndex < 0: " + fromIndex);
     }

     int arrayIndex;
     AtomicLongArray array = null;
     for (arrayIndex = arrayIndex(fromIndex); arrayIndex < arrays.length() && (array = arrays.get(arrayIndex)) == null; arrayIndex++);
     if (array == null) {
       return -1;
     }

     int wordIndexInArray = wordIndexInArray(fromIndex);

     long word = array.get(wordIndexInArray) & (WORD_MASK << fromIndex);

     while (true) {
       if (word != 0) {
         return ((1<<arrayIndex)-1 + wordIndexInArray) * BITS_PER_WORD + Long.numberOfTrailingZeros(word);
       }
       if (++wordIndexInArray == array.length()) {
         wordIndexInArray = 0;
         for (++arrayIndex; arrayIndex != arrays.length() && (array = arrays.get(arrayIndex)) == null; arrayIndex++);
         if (array == null) {
           return -1;
         }
       }

       word = array.get(wordIndexInArray);
     }
   }


   /**
   * Returns the index of the first bit that is set to {@code false}
   * that occurs on or after the specified starting index.
   *
   * @param fromIndex the index to start checking from (inclusive)
   * @return the index of the next clear bit
   * @throws IndexOutOfBoundsException if the specified index is negative
   */
   public int nextClearBit(int fromIndex) {
     if (fromIndex < 0) {
       throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
     }

     int arrayIndex = arrayIndex(fromIndex);
     AtomicLongArray array = arrays.get(arrayIndex);
     int wordIndexInArray = wordIndexInArray(fromIndex);
     if (array == null) {
       return ((1<<arrayIndex)-1+wordIndexInArray) * BITS_PER_WORD+(fromIndex%BITS_PER_WORD);
     }

     long word = ~array.get(wordIndexInArray) & (WORD_MASK << fromIndex);

     while (true) {
       if (word != 0) {
         return ((1<<arrayIndex)-1 + wordIndexInArray) * BITS_PER_WORD + Long.numberOfTrailingZeros(word);
       }
       if (++wordIndexInArray == array.length()) {
         wordIndexInArray = 0;
         if (++arrayIndex == arrays.length()) return -1;
         array = arrays.get(arrayIndex);
         if (array == null) {
           return ((1<<arrayIndex)-1+wordIndexInArray) * BITS_PER_WORD;
         }
       }

       word = ~array.get(wordIndexInArray);
     }
   }

   /**
   * Returns the hash code value for this bit set. The hash code depends
   * only on which bits are set.
   * <p/>
   * <p>The hash code is defined to be the result of the following
   * calculation:
   * <pre> {@code
   * public int hashCode() {
   *     long h = 1234;
   *     for (int i = words.length; --i >= 0; )
   *         h ^= words[i] * (i + 1);
   *     return (int)((h >> 32) ^ h);
   * }}</pre>
   * Note that the hash code changes if the set of bits is altered.
   *
   * @return the hash code value for this bit set
   */
   public int hashCode() {
     long h = 1234;
     for (int a = 0; a<arrays.length();a++) {
       AtomicLongArray array = arrays.get(a);
       if (array == null) continue;
       for (int i=0;i<array.length();i++) {
         long word = array.get(i);
         h ^= word * ((1<<a)+ i);
       }
     }

     return (int)(h >> 32 ^ h);
   }


   /**
   * Returns the number of bits of space actually in use
   *
   * @return the number of bits currently in this bit set
   */
   public int size() {
     int a;
     for (a = arrays.length() - 1; a >= 0; a--) {
       AtomicLongArray array = arrays.get(a);
       if (array != null) break;
     }
     return ((1<<a+1)-1)*BITS_PER_WORD;
   }

   /**
   * Compares this object against the specified object.
   * The result is {@code true} if and only if the argument is
   * not {@code null} and is a {@code ConcurrentBitSet} object that has
   * exactly the same set of bits set to {@code true} as this bit
   * set. That is, for every nonnegative {@code int} index {@code k},
   * <pre>((ConcurrentBitSet)obj).get(k) == this.get(k)</pre>
   * must be true. The current sizes of the two bit sets are not compared.
   *
   * @param obj the object to compare with
   * @return {@code true} if the objects are the same;
   * {@code false} otherwise
   * @see #size()
   */
   public boolean equals(Object obj) {
     if (!(obj instanceof ConcurrentBitSet)) {
       return false;
     }
     if (this == obj) {
       return true;
     }

     ConcurrentBitSet set = (ConcurrentBitSet)obj;

     for (int i = 0; i < arrays.length(); i++) {
       AtomicLongArray array1 = arrays.get(i);
       AtomicLongArray array2 = set.arrays.get(i);
       if (array1 == null && array2 == null) continue;
       int size = array1 == null ? array2.length() : array1.length();
       for (int k=0; k<size;k++) {
         long word1 = array1 == null ? 0 : array1.get(k);
         long word2 = array2 == null ? 0 : array2.get(k);
         if (word1 != word2) return false;
       }
     }

     return true;
   }

   /**
   * Returns a string representation of this bit set. For every index
   * which contains a bit in the set
   * state, the decimal representation of that index is included in
   * the result. Such indices are listed in order from lowest to
   * highest, separated by ",&nbsp;" (a comma and a space) and
   * surrounded by braces, resulting in the usual mathematical
   * notation for a set of integers.
   *
   * @return a string representation of this bit set
   */
   public String toString() {
     StringBuilder b = new StringBuilder();
     b.append('{');

     for (int i = nextSetBit(0); i >= 0; i = nextSetBit(i + 1)) {
       int endOfRun = nextClearBit(i);
       if (endOfRun - i > 1) {
         if (b.length() != 1) {
           b.append(", ");
         }
         b.append(i).append("...").append(endOfRun-1);
         i = endOfRun;
       }
       else {
         do {
           if (b.length() != 1) {
             b.append(", ");
           }
           b.append(i);
         }
         while (++i < endOfRun);
       }
     }

     b.append('}');
     return b.toString();
   }

   @NotNull
   public long[] toLongArray() {
     int bits = size();
     long[] result = new long[bits/BITS_PER_WORD];
     int i = 0;
     for (int b=0; b<bits;b += BITS_PER_WORD){
       AtomicLongArray array = arrays.get(arrayIndex(b));
       long word = array == null ? 0 : array.get(wordIndexInArray(b));
       result[i++] = word;
     }
     return result;
   }

   public void writeTo(@NotNull File file) throws IOException {
     RandomAccessFile bitSetStorage = new RandomAccessFile(file,"rw");
     try {
       long[] words = toLongArray();
       for (long word : words) {
         bitSetStorage.writeLong(word);
       }
     }
     finally {
       bitSetStorage.close();
     }
   }

   @NotNull
   public static ConcurrentBitSet readFrom(@NotNull File file) throws IOException {
     if (!file.exists()) {
       return new ConcurrentBitSet();
     }
     RandomAccessFile bitSetStorage = new RandomAccessFile(file,"r");
     try {
       long length = file.length();
       long[] words = new long[(int)(length/8)];
       for (int i=0; i<words.length;i++) {
         words[i] = bitSetStorage.readLong();
       }
       return new ConcurrentBitSet(words);
     }
     finally {
       bitSetStorage.close();
     }
   }

   private ConcurrentBitSet(@NotNull long[] words) {
     for (int i = 0; i < words.length; i++) {
       long word = words[i];
       for (int b=0;b<BITS_PER_WORD;b++) {
         boolean bit = (word & (1L << b)) != 0;
         set(i * BITS_PER_WORD + b, bit);
       }
     }
   }

 }
	/*
	* Copyright 2000-2014 JetBrains s.r.o.
	*
	* Licensed 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 com.intellij.util.containers;

	import org.jetbrains.annotations.NotNull;

	import java.io.File;
	import java.io.IOException;
	import java.io.RandomAccessFile;
	import java.util.concurrent.atomic.AtomicLongArray;
	import java.util.concurrent.atomic.AtomicReferenceArray;

	/**
	* This class is a thread-safe version of the
	* {@code java.util.BitSet} except for some methods which don't make sense in concurrent environment or those i was too lazy to implement.
	*
	* Implementation is based on "Lock-free Dynamically Resizable Arrays" by Dechev, Pirkelbauer, Bjarne Stroustrup.
	* http://www.stroustrup.com/lock-free-vector.pdf
	*
	* @see java.util.BitSet
	*/
	public class ConcurrentBitSet {
	public ConcurrentBitSet() {
	}

	/**
	* An array of 32 longword vectors.
	* Vector at index "i" has length of (1 << i) long words.
	* Each long word stores next 64 bits part of the set.
	* Therefore the i-th bit of the set is stored in {@code arrays.get(arrayIndex(i)).get(wordIndexInArray(i))} word in the {@code 1L << i} position.
	*/
	private final AtomicReferenceArray<AtomicLongArray> arrays = new AtomicReferenceArray<AtomicLongArray>(32);
	private static int arrayIndex(int bitIndex) {
	int i = (bitIndex >> ADDRESS_BITS_PER_WORD) + 1;
	return 31 - Integer.numberOfLeadingZeros(i);
	}
	private static int wordIndexInArray(int bitIndex) {
	int i = (bitIndex >> ADDRESS_BITS_PER_WORD) + 1;
	return clearHighestBit(i);
	}

	private static int clearHighestBit(int index) {
	int i = index>>1;
	i \|= i >> 1;
	i \|= i >> 2;
	i \|= i >> 4;
	i \|= i >> 8;
	i \|= i >> 16;
	return index & i;
	}

	/* BitSets are packed into arrays of "words." Currently a word is
	a long, which consists of 64 bits, requiring 6 address bits.
	The choice of word size is determined purely by performance concerns.
	*/
	private static final int ADDRESS_BITS_PER_WORD = 6;
	private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

	/* Used to shift left or right for a partial word mask */
	private static final long WORD_MASK = -1L;

	/**
	* Sets the bit at the specified index to the complement of its
	* current value.
	*
	* @param bitIndex the index of the bit to flip
	* @return new bit value
	* @throws IndexOutOfBoundsException if the specified index is negative
	*/
	public boolean flip(int bitIndex) {
	if (bitIndex < 0) {
	throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
	}

	AtomicLongArray array = getOrCreateArray(bitIndex);

	int wordIndexInArray = wordIndexInArray(bitIndex);

	long word;
	long newWord;
	do {
	word = array.get(wordIndexInArray);
	newWord = word ^ (1L << bitIndex);
	}
	while (!array.compareAndSet(wordIndexInArray, word, newWord));
	return (newWord & (1L << bitIndex)) != 0;
	}

	/**
	* Sets the bit at the specified index to {@code true}.
	*
	* @param bitIndex a bit index
	* @return previous value
	* @throws IndexOutOfBoundsException if the specified index is negative
	*/
	public boolean set(int bitIndex) {
	if (bitIndex < 0) {
	throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
	}

	AtomicLongArray array = getOrCreateArray(bitIndex);

	int wordIndexInArray = wordIndexInArray(bitIndex);
	long word;
	long newWord;
	boolean previousBit;
	do {
	word = array.get(wordIndexInArray);
	previousBit = (word & (1L << bitIndex)) != 0;
	newWord = word \| (1L << bitIndex);
	}
	while (!array.compareAndSet(wordIndexInArray, word, newWord));
	return previousBit;
	}

	/**
	* Sets the bit at the specified index to the specified value.
	*
	* @param bitIndex a bit index
	* @param value a boolean value to set
	* @throws IndexOutOfBoundsException if the specified index is negative
	*/
	public void set(int bitIndex, boolean value) {
	if (value) {
	set(bitIndex);
	}
	else {
	clear(bitIndex);
	}
	}

	/**
	* Sets the bit specified by the index to {@code false}.
	*
	* @param bitIndex the index of the bit to be cleared
	* @throws IndexOutOfBoundsException if the specified index is negative
	* @return previous value
	*/
	public boolean clear(int bitIndex) {
	if (bitIndex < 0) {
	throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
	}

	AtomicLongArray array = getOrCreateArray(bitIndex);

	int wordIndexInArray = wordIndexInArray(bitIndex);
	long word;
	long newWord;
	boolean previousBit;
	do {
	word = array.get(wordIndexInArray);
	previousBit = (word & (1L << bitIndex)) != 0;
	newWord = word & ~ (1L << bitIndex);
	}
	while (!array.compareAndSet(wordIndexInArray, word, newWord));
	return previousBit;
	}

	@NotNull
	private AtomicLongArray getOrCreateArray(int bitIndex) {
	int arrayIndex = arrayIndex(bitIndex);
	AtomicLongArray array;

	// while loop is here because of clear() method
	while ((array = arrays.get(arrayIndex)) == null) {
	arrays.compareAndSet(arrayIndex, null, new AtomicLongArray(1<<arrayIndex));
	}
	return array;
	}


	/**
	* Clear method in presense of concurrency complicates everything to no end.
	* PLEASE REWRITE EVERY OTHER METHOD IF EVER DECIDE TO IMPLEMENT THIS
	*/
	public void clear() {
	for (int i=0; i<arrays.length();i++) {
	arrays.set(i, null);
	}
	}

	/**
	* Returns the value of the bit with the specified index. The value
	* is {@code true} if the bit with the index {@code bitIndex}
	* is currently set; otherwise, the result is {@code false}.
	*
	* @param bitIndex the bit index
	* @return the value of the bit with the specified index
	* @throws IndexOutOfBoundsException if the specified index is negative
	*/
	public boolean get(int bitIndex) {
	if (bitIndex < 0) {
	throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
	}

	int arrayIndex = arrayIndex(bitIndex);
	AtomicLongArray array = arrays.get(arrayIndex);
	if (array == null) {
	return false;
	}

	int wordIndexInArray = wordIndexInArray(bitIndex);
	long word = array.get(wordIndexInArray);
	return (word & (1L<<bitIndex)) != 0;
	}

	/**
	* Returns the index of the first bit that is set to {@code true}
	* that occurs on or after the specified starting index. If no such
	* bit exists then {@code -1} is returned.
	* <p/>
	* <p>To iterate over the {@code true} bits,
	* use the following loop:
	* <p/>
	* <pre> {@code
	* for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
	* // operate on index i here
	* }}</pre>
	*
	* @param fromIndex the index to start checking from (inclusive)
	* @return the index of the next set bit, or {@code -1} if there
	* is no such bit
	* @throws IndexOutOfBoundsException if the specified index is negative
	*/
	public int nextSetBit(int fromIndex) {
	if (fromIndex < 0) {
	throw new IndexOutOfBoundsException("bitIndex < 0: " + fromIndex);
	}

	int arrayIndex;
	AtomicLongArray array = null;
	for (arrayIndex = arrayIndex(fromIndex); arrayIndex < arrays.length() && (array = arrays.get(arrayIndex)) == null; arrayIndex++);
	if (array == null) {
	return -1;
	}

	int wordIndexInArray = wordIndexInArray(fromIndex);

	long word = array.get(wordIndexInArray) & (WORD_MASK << fromIndex);

	while (true) {
	if (word != 0) {
	return ((1<<arrayIndex)-1 + wordIndexInArray) * BITS_PER_WORD + Long.numberOfTrailingZeros(word);
	}
	if (++wordIndexInArray == array.length()) {
	wordIndexInArray = 0;
	for (++arrayIndex; arrayIndex != arrays.length() && (array = arrays.get(arrayIndex)) == null; arrayIndex++);
	if (array == null) {
	return -1;
	}
	}

	word = array.get(wordIndexInArray);
	}
	}


	/**
	* Returns the index of the first bit that is set to {@code false}
	* that occurs on or after the specified starting index.
	*
	* @param fromIndex the index to start checking from (inclusive)
	* @return the index of the next clear bit
	* @throws IndexOutOfBoundsException if the specified index is negative
	*/
	public int nextClearBit(int fromIndex) {
	if (fromIndex < 0) {
	throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
	}

	int arrayIndex = arrayIndex(fromIndex);
	AtomicLongArray array = arrays.get(arrayIndex);
	int wordIndexInArray = wordIndexInArray(fromIndex);
	if (array == null) {
	return ((1<<arrayIndex)-1+wordIndexInArray) * BITS_PER_WORD+(fromIndex%BITS_PER_WORD);
	}

	long word = ~array.get(wordIndexInArray) & (WORD_MASK << fromIndex);

	while (true) {
	if (word != 0) {
	return ((1<<arrayIndex)-1 + wordIndexInArray) * BITS_PER_WORD + Long.numberOfTrailingZeros(word);
	}
	if (++wordIndexInArray == array.length()) {
	wordIndexInArray = 0;
	if (++arrayIndex == arrays.length()) return -1;
	array = arrays.get(arrayIndex);
	if (array == null) {
	return ((1<<arrayIndex)-1+wordIndexInArray) * BITS_PER_WORD;
	}
	}

	word = ~array.get(wordIndexInArray);
	}
	}

	/**
	* Returns the hash code value for this bit set. The hash code depends
	* only on which bits are set.
	* <p/>
	* <p>The hash code is defined to be the result of the following
	* calculation:
	* <pre> {@code
	* public int hashCode() {
	* long h = 1234;
	* for (int i = words.length; --i >= 0; )
	* h ^= words[i] * (i + 1);
	* return (int)((h >> 32) ^ h);
	* }}</pre>
	* Note that the hash code changes if the set of bits is altered.
	*
	* @return the hash code value for this bit set
	*/
	public int hashCode() {
	long h = 1234;
	for (int a = 0; a<arrays.length();a++) {
	AtomicLongArray array = arrays.get(a);
	if (array == null) continue;
	for (int i=0;i<array.length();i++) {
	long word = array.get(i);
	h ^= word * ((1<<a)+ i);
	}
	}

	return (int)(h >> 32 ^ h);
	}


	/**
	* Returns the number of bits of space actually in use
	*
	* @return the number of bits currently in this bit set
	*/
	public int size() {
	int a;
	for (a = arrays.length() - 1; a >= 0; a--) {
	AtomicLongArray array = arrays.get(a);
	if (array != null) break;
	}
	return ((1<<a+1)-1)*BITS_PER_WORD;
	}

	/**
	* Compares this object against the specified object.
	* The result is {@code true} if and only if the argument is
	* not {@code null} and is a {@code ConcurrentBitSet} object that has
	* exactly the same set of bits set to {@code true} as this bit
	* set. That is, for every nonnegative {@code int} index {@code k},
	* <pre>((ConcurrentBitSet)obj).get(k) == this.get(k)</pre>
	* must be true. The current sizes of the two bit sets are not compared.
	*
	* @param obj the object to compare with
	* @return {@code true} if the objects are the same;
	* {@code false} otherwise
	* @see #size()
	*/
	public boolean equals(Object obj) {
	if (!(obj instanceof ConcurrentBitSet)) {
	return false;
	}
	if (this == obj) {
	return true;
	}

	ConcurrentBitSet set = (ConcurrentBitSet)obj;

	for (int i = 0; i < arrays.length(); i++) {
	AtomicLongArray array1 = arrays.get(i);
	AtomicLongArray array2 = set.arrays.get(i);
	if (array1 == null && array2 == null) continue;
	int size = array1 == null ? array2.length() : array1.length();
	for (int k=0; k<size;k++) {
	long word1 = array1 == null ? 0 : array1.get(k);
	long word2 = array2 == null ? 0 : array2.get(k);
	if (word1 != word2) return false;
	}
	}

	return true;
	}

	/**
	* Returns a string representation of this bit set. For every index
	* which contains a bit in the set
	* state, the decimal representation of that index is included in
	* the result. Such indices are listed in order from lowest to
	* highest, separated by ", " (a comma and a space) and
	* surrounded by braces, resulting in the usual mathematical
	* notation for a set of integers.
	*
	* @return a string representation of this bit set
	*/
	public String toString() {
	StringBuilder b = new StringBuilder();
	b.append('{');

	for (int i = nextSetBit(0); i >= 0; i = nextSetBit(i + 1)) {
	int endOfRun = nextClearBit(i);
	if (endOfRun - i > 1) {
	if (b.length() != 1) {
	b.append(", ");
	}
	b.append(i).append("...").append(endOfRun-1);
	i = endOfRun;
	}
	else {
	do {
	if (b.length() != 1) {
	b.append(", ");
	}
	b.append(i);
	}
	while (++i < endOfRun);
	}
	}

	b.append('}');
	return b.toString();
	}

	@NotNull
	public long[] toLongArray() {
	int bits = size();
	long[] result = new long[bits/BITS_PER_WORD];
	int i = 0;
	for (int b=0; b<bits;b += BITS_PER_WORD){
	AtomicLongArray array = arrays.get(arrayIndex(b));
	long word = array == null ? 0 : array.get(wordIndexInArray(b));
	result[i++] = word;
	}
	return result;
	}

	public void writeTo(@NotNull File file) throws IOException {
	RandomAccessFile bitSetStorage = new RandomAccessFile(file,"rw");
	try {
	long[] words = toLongArray();
	for (long word : words) {
	bitSetStorage.writeLong(word);
	}
	}
	finally {
	bitSetStorage.close();
	}
	}

	@NotNull
	public static ConcurrentBitSet readFrom(@NotNull File file) throws IOException {
	if (!file.exists()) {
	return new ConcurrentBitSet();
	}
	RandomAccessFile bitSetStorage = new RandomAccessFile(file,"r");
	try {
	long length = file.length();
	long[] words = new long[(int)(length/8)];
	for (int i=0; i<words.length;i++) {
	words[i] = bitSetStorage.readLong();
	}
	return new ConcurrentBitSet(words);
	}
	finally {
	bitSetStorage.close();
	}
	}

	private ConcurrentBitSet(@NotNull long[] words) {
	for (int i = 0; i < words.length; i++) {
	long word = words[i];
	for (int b=0;b<BITS_PER_WORD;b++) {
	boolean bit = (word & (1L << b)) != 0;
	set(i * BITS_PER_WORD + b, bit);
	}
	}
	}

	}