harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From telli...@apache.org
Subject svn commit: r545213 - in /harmony/enhanced/classlib/trunk/modules/luni/src: main/java/java/util/BitSet.java test/java/tests/api/java/util/BitSetTest.java test/resources/serialization/tests/api/java/util/BitSetTest.golden.ser
Date Thu, 07 Jun 2007 15:19:22 GMT
Author: tellison
Date: Thu Jun  7 08:19:21 2007
New Revision: 545213

URL: http://svn.apache.org/viewvc?view=rev&rev=545213
Log:
Apply modified patch for HARMONY-4051 ([classlib][luni] Performance improvement of java.util.BitSet)

Added:
    harmony/enhanced/classlib/trunk/modules/luni/src/test/resources/serialization/tests/api/java/util/BitSetTest.golden.ser
  (with props)
Modified:
    harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/BitSet.java
    harmony/enhanced/classlib/trunk/modules/luni/src/test/java/tests/api/java/util/BitSetTest.java

Modified: harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/BitSet.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/BitSet.java?view=diff&rev=545213&r1=545212&r2=545213
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/BitSet.java (original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/main/java/java/util/BitSet.java Thu Jun
 7 08:19:21 2007
@@ -17,6 +17,8 @@
 
 package java.util;
 
+import java.io.IOException;
+import java.io.ObjectInputStream;
 import java.io.Serializable;
 
 import org.apache.harmony.luni.util.Msg;
@@ -29,11 +31,36 @@
 public class BitSet implements Serializable, Cloneable {
     private static final long serialVersionUID = 7997698588986878753L;
 
-    // Size in bits of the data type being used in the bits array
-    private static final int ELM_SIZE = 64;
+    private static final int OFFSET = 6;
+
+    private static final int ELM_SIZE = 1 << OFFSET;
+
+    private static final int RIGHT_BITS = ELM_SIZE - 1;
+
+    private static final long[] TWO_N_ARRAY = new long[] { 0x1L, 0x2L, 0x4L,
+            0x8L, 0x10L, 0x20L, 0x40L, 0x80L, 0x100L, 0x200L, 0x400L, 0x800L,
+            0x1000L, 0x2000L, 0x4000L, 0x8000L, 0x10000L, 0x20000L, 0x40000L,
+            0x80000L, 0x100000L, 0x200000L, 0x400000L, 0x800000L, 0x1000000L,
+            0x2000000L, 0x4000000L, 0x8000000L, 0x10000000L, 0x20000000L,
+            0x40000000L, 0x80000000L, 0x100000000L, 0x200000000L, 0x400000000L,
+            0x800000000L, 0x1000000000L, 0x2000000000L, 0x4000000000L,
+            0x8000000000L, 0x10000000000L, 0x20000000000L, 0x40000000000L,
+            0x80000000000L, 0x100000000000L, 0x200000000000L, 0x400000000000L,
+            0x800000000000L, 0x1000000000000L, 0x2000000000000L,
+            0x4000000000000L, 0x8000000000000L, 0x10000000000000L,
+            0x20000000000000L, 0x40000000000000L, 0x80000000000000L,
+            0x100000000000000L, 0x200000000000000L, 0x400000000000000L,
+            0x800000000000000L, 0x1000000000000000L, 0x2000000000000000L,
+            0x4000000000000000L, 0x8000000000000000L };
 
     private long[] bits;
 
+    private transient boolean needClear;
+
+    private transient int actualArrayLength;
+
+    private transient boolean isLengthActual;
+
     /**
      * Create a new BitSet with size equal to 64 bits
      * 
@@ -46,7 +73,9 @@
      * @see #set(int, int, boolean)
      */
     public BitSet() {
-        this(64);
+        bits = new long[1];
+        actualArrayLength = 0;
+        isLengthActual = true;
     }
 
     /**
@@ -68,11 +97,12 @@
      * @see #set(int, int, boolean)
      */
     public BitSet(int nbits) {
-        if (nbits >= 0) {
-            bits = new long[(nbits / ELM_SIZE) + (nbits % ELM_SIZE > 0 ? 1 : 0)];
-        } else {
+        if (nbits < 0) {
             throw new NegativeArraySizeException();
         }
+        bits = new long[(nbits + ELM_SIZE - 1) >> OFFSET];
+        actualArrayLength = 0;
+        isLengthActual = true;
     }
 
     /**
@@ -80,9 +110,14 @@
      * 
      * @param bits
      *            the size of the bit set
+     * @param needClear
      */
-    private BitSet(long[] bits) {
+    private BitSet(long[] bits, boolean needClear, int actualArrayLength,
+            boolean isLengthActual) {
         this.bits = bits;
+        this.needClear = needClear;
+        this.actualArrayLength = actualArrayLength;
+        this.isLengthActual = isLengthActual;
     }
 
     /**
@@ -118,10 +153,13 @@
         }
         if (obj instanceof BitSet) {
             long[] bsBits = ((BitSet) obj).bits;
-            int length1 = bits.length, length2 = bsBits.length;
+            int length1 = this.actualArrayLength, length2 = ((BitSet) obj).actualArrayLength;
+            if (this.isLengthActual && ((BitSet) obj).isLengthActual
+                    && length1 != length2) {
+                return false;
+            }
             // If one of the BitSets is larger than the other, check to see if
-            // any of
-            // its extra bits are set. If so return false.
+            // any of its extra bits are set. If so return false.
             if (length1 <= length2) {
                 for (int i = 0; i < length1; i++) {
                     if (bits[i] != bsBits[i]) {
@@ -157,11 +195,9 @@
      * @param pos
      *            the index the new array needs to be able to access
      */
-    private void growBits(int pos) {
-        pos++; // Inc to get correct bit count
-        long[] tempBits = new long[(pos / ELM_SIZE)
-                + (pos % ELM_SIZE > 0 ? 1 : 0)];
-        System.arraycopy(bits, 0, tempBits, 0, bits.length);
+    private final void growLength(int len) {
+        long[] tempBits = new long[Math.max(len, bits.length * 2)];
+        System.arraycopy(bits, 0, tempBits, 0, this.actualArrayLength);
         bits = tempBits;
     }
 
@@ -177,9 +213,7 @@
     @Override
     public int hashCode() {
         long x = 1234;
-        // for (int i = 0, length = bits.length; i < length; i+=2)
-        // x ^= (bits[i] + ((long)bits[i+1] << 32)) * (i/2 + 1);
-        for (int i = 0, length = bits.length; i < length; i++) {
+        for (int i = 0, length = actualArrayLength; i < length; i++) {
             x ^= bits[i] * (i + 1);
         }
         return (int) ((x >> 32) ^ x);
@@ -204,14 +238,16 @@
      * @see #set(int, int, boolean)
      */
     public boolean get(int pos) {
-        if (pos >= 0) {
-            if (pos < bits.length * ELM_SIZE) {
-                return (bits[pos / ELM_SIZE] & (1L << (pos % ELM_SIZE))) != 0;
-            }
-            return false;
+        if (pos < 0) {
+            // Negative index specified
+            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
         }
-        // Negative index specified
-        throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+
+        int arrayPos = pos >> OFFSET;
+        if (arrayPos < actualArrayLength) {
+            return (bits[arrayPos] & TWO_N_ARRAY[pos & RIGHT_BITS]) != 0;
+        }
+        return false;
     }
 
     /**
@@ -230,53 +266,62 @@
      * @see #get(int)
      */
     public BitSet get(int pos1, int pos2) {
-        if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) {
-            int last = (bits.length * ELM_SIZE);
-            if (pos1 >= last || pos1 == pos2) {
+        if (pos1 < 0 || pos2 < 0 || pos2 < pos1) {
+            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+        }
+
+        int last = actualArrayLength << OFFSET;
+        if (pos1 >= last || pos1 == pos2) {
+            return new BitSet(0);
+        }
+        if (pos2 > last) {
+            pos2 = last;
+        }
+
+        int idx1 = pos1 >> OFFSET;
+        int idx2 = (pos2 - 1) >> OFFSET;
+        long factor1 = (~0L) << (pos1 & RIGHT_BITS);
+        long factor2 = (~0L) >>> (ELM_SIZE - (pos2 & RIGHT_BITS));
+
+        if (idx1 == idx2) {
+            long result = (bits[idx1] & (factor1 & factor2)) >>> (pos1 %
ELM_SIZE);
+            if (result == 0) {
                 return new BitSet(0);
             }
-            if (pos2 > last) {
-                pos2 = last;
-            }
+            return new BitSet(new long[] { result }, needClear, 1, true);
+        }
+        long[] newbits = new long[idx2 - idx1 + 1];
+        // first fill in the first and last indexes in the new bitset
+        newbits[0] = bits[idx1] & factor1;
+        newbits[newbits.length - 1] = bits[idx2] & factor2;
 
-            int idx1 = pos1 / ELM_SIZE;
-            int idx2 = (pos2 - 1) / ELM_SIZE;
-            long factor1 = (~0L) << (pos1 % ELM_SIZE);
-            long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
-
-            if (idx1 == idx2) {
-                long result = (bits[idx1] & (factor1 & factor2)) >>> (pos1
% ELM_SIZE);
-                return new BitSet(new long[] { result });
-            }
-            long[] newbits = new long[idx2 - idx1 + 1];
-            // first fill in the first and last indexes in the new bitset
-            newbits[0] = bits[idx1] & factor1;
-            newbits[newbits.length - 1] = bits[idx2] & factor2;
-
-            // fill in the in between elements of the new bitset
-            for (int i = 1; i < idx2 - idx1; i++) {
-                newbits[i] = bits[idx1 + i];
-            }
-
-            // shift all the elements in the new bitset to the right by pos1
-            // % ELM_SIZE
-            int numBitsToShift = pos1 % ELM_SIZE;
-            if (numBitsToShift != 0) {
-                for (int i = 0; i < newbits.length; i++) {
-                    // shift the current element to the right regardless of
-                    // sign
-                    newbits[i] = newbits[i] >>> (numBitsToShift);
-
-                    // apply the last x bits of newbits[i+1] to the current
-                    // element
-                    if (i != newbits.length - 1) {
-                        newbits[i] |= newbits[i + 1] << (ELM_SIZE - (numBitsToShift));
-                    }
+        // fill in the in between elements of the new bitset
+        for (int i = 1; i < idx2 - idx1; i++) {
+            newbits[i] = bits[idx1 + i];
+        }
+
+        // shift all the elements in the new bitset to the right by pos1
+        // % ELM_SIZE
+        int numBitsToShift = pos1 & RIGHT_BITS;
+        int actualLen = newbits.length;
+        if (numBitsToShift != 0) {
+            for (int i = 0; i < newbits.length; i++) {
+                // shift the current element to the right regardless of
+                // sign
+                newbits[i] = newbits[i] >>> (numBitsToShift);
+
+                // apply the last x bits of newbits[i+1] to the current
+                // element
+                if (i != newbits.length - 1) {
+                    newbits[i] |= newbits[i + 1] << (ELM_SIZE - (numBitsToShift));
+                }
+                if (newbits[i] != 0) {
+                    actualLen = i + 1;
                 }
             }
-            return new BitSet(newbits);
         }
-        throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+        return new BitSet(newbits, needClear, actualLen,
+                newbits[actualLen - 1] != 0);
     }
 
     /**
@@ -292,14 +337,20 @@
      * @see #clear(int, int)
      */
     public void set(int pos) {
-        if (pos >= 0) {
-            if (pos >= bits.length * ELM_SIZE) {
-                growBits(pos);
-            }
-            bits[pos / ELM_SIZE] |= 1L << (pos % ELM_SIZE);
-        } else {
+        if (pos < 0) {
             throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
         }
+
+        int len = (pos >> OFFSET) + 1;
+        if (len > bits.length) {
+            growLength(len);
+        }
+        bits[len - 1] |= TWO_N_ARRAY[pos & RIGHT_BITS];
+        if (len > actualArrayLength) {
+            actualArrayLength = len;
+            isLengthActual = true;
+        }
+        needClear();
     }
 
     /**
@@ -337,31 +388,41 @@
      * @see #set(int)
      */
     public void set(int pos1, int pos2) {
-        if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) {
-            if (pos1 == pos2) {
-                return;
-            }
-            if (pos2 >= bits.length * ELM_SIZE) {
-                growBits(pos2);
-            }
+        if (pos1 < 0 || pos2 < 0 || pos2 < pos1) {
+            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+        }
 
-            int idx1 = pos1 / ELM_SIZE;
-            int idx2 = (pos2 - 1) / ELM_SIZE;
-            long factor1 = (~0L) << (pos1 % ELM_SIZE);
-            long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
+        if (pos1 == pos2) {
+            return;
+        }
+        int len2 = ((pos2 - 1) >> OFFSET) + 1;
+        if (len2 > bits.length) {
+            growLength(len2);
+        }
 
-            if (idx1 == idx2) {
-                bits[idx1] |= (factor1 & factor2);
-            } else {
-                bits[idx1] |= factor1;
-                bits[idx2] |= factor2;
-                for (int i = idx1 + 1; i < idx2; i++) {
-                    bits[i] |= (~0L);
-                }
-            }
+        int idx1 = pos1 >> OFFSET;
+        int idx2 = (pos2 - 1) >> OFFSET;
+        long factor1 = (~0L) << (pos1 & RIGHT_BITS);
+        long factor2 = (~0L) >>> (ELM_SIZE - (pos2 & RIGHT_BITS));
+
+        if (idx1 == idx2) {
+            bits[idx1] |= (factor1 & factor2);
         } else {
-            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+            bits[idx1] |= factor1;
+            bits[idx2] |= factor2;
+            for (int i = idx1 + 1; i < idx2; i++) {
+                bits[i] |= (~0L);
+            }
         }
+        if (idx2 + 1 > actualArrayLength) {
+            actualArrayLength = idx2 + 1;
+            isLengthActual = true;
+        }
+        needClear();
+    }
+
+    private void needClear() {
+        this.needClear = true;
     }
 
     /**
@@ -395,8 +456,13 @@
      * @see #clear(int, int)
      */
     public void clear() {
-        for (int i = 0; i < bits.length; i++) {
-            bits[i] = 0L;
+        if (needClear) {
+            for (int i = 0; i < bits.length; i++) {
+                bits[i] = 0L;
+            }
+            actualArrayLength = 0;
+            isLengthActual = true;
+            needClear = false;
         }
     }
 
@@ -411,14 +477,21 @@
      * @see #clear(int, int)
      */
     public void clear(int pos) {
-        if (pos >= 0) {
-            if (pos < bits.length * ELM_SIZE) {
-                bits[pos / ELM_SIZE] &= ~(1L << (pos % ELM_SIZE));
-            }
-        } else {
+        if (pos < 0) {
             // Negative index specified
             throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
         }
+
+        if (!needClear) {
+            return;
+        }
+        int arrayPos = pos >> OFFSET;
+        if (arrayPos < actualArrayLength) {
+            bits[arrayPos] &= ~(TWO_N_ARRAY[pos & RIGHT_BITS]);
+            if (bits[actualArrayLength - 1] == 0) {
+                isLengthActual = false;
+            }
+        }
     }
 
     /**
@@ -432,35 +505,40 @@
      * @throws IndexOutOfBoundsException
      *             when pos1 or pos2 is negative, or when pos2 is not smaller
      *             than pos1
-     * 
      * @see #clear(int)
      */
     public void clear(int pos1, int pos2) {
-        if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) {
-            int last = (bits.length * ELM_SIZE);
-            if (pos1 >= last || pos1 == pos2) {
-                return;
-            }
-            if (pos2 > last) {
-                pos2 = last;
-            }
-
-            int idx1 = pos1 / ELM_SIZE;
-            int idx2 = (pos2 - 1) / ELM_SIZE;
-            long factor1 = (~0L) << (pos1 % ELM_SIZE);
-            long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
+        if (pos1 < 0 || pos2 < 0 || pos2 < pos1) {
+            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+        }
 
-            if (idx1 == idx2) {
-                bits[idx1] &= ~(factor1 & factor2);
-            } else {
-                bits[idx1] &= ~factor1;
-                bits[idx2] &= ~factor2;
-                for (int i = idx1 + 1; i < idx2; i++) {
-                    bits[i] = 0L;
-                }
-            }
+        if (!needClear) {
+            return;
+        }
+        int last = (actualArrayLength << OFFSET);
+        if (pos1 >= last || pos1 == pos2) {
+            return;
+        }
+        if (pos2 > last) {
+            pos2 = last;
+        }
+
+        int idx1 = pos1 >> OFFSET;
+        int idx2 = (pos2 - 1) >> OFFSET;
+        long factor1 = (~0L) << (pos1 & RIGHT_BITS);
+        long factor2 = (~0L) >>> (ELM_SIZE - (pos2 & RIGHT_BITS));
+
+        if (idx1 == idx2) {
+            bits[idx1] &= ~(factor1 & factor2);
         } else {
-            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+            bits[idx1] &= ~factor1;
+            bits[idx2] &= ~factor2;
+            for (int i = idx1 + 1; i < idx2; i++) {
+                bits[i] = 0L;
+            }
+        }
+        if ((actualArrayLength > 0) && (bits[actualArrayLength - 1] == 0)) {
+            isLengthActual = false;
         }
     }
 
@@ -475,14 +553,20 @@
      * @see #flip(int, int)
      */
     public void flip(int pos) {
-        if (pos >= 0) {
-            if (pos >= bits.length * ELM_SIZE) {
-                growBits(pos);
-            }
-            bits[pos / ELM_SIZE] ^= 1L << (pos % ELM_SIZE);
-        } else {
+        if (pos < 0) {
             throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
         }
+
+        int len = (pos >> OFFSET) + 1;
+        if (len > bits.length) {
+            growLength(len);
+        }
+        bits[len - 1] ^= TWO_N_ARRAY[pos & RIGHT_BITS];
+        if (len > actualArrayLength) {
+            actualArrayLength = len;
+        }
+        isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength
- 1] == 0));
+        needClear();
     }
 
     /**
@@ -500,31 +584,37 @@
      * @see #flip(int)
      */
     public void flip(int pos1, int pos2) {
-        if (pos1 >= 0 && pos2 >= 0 && pos2 >= pos1) {
-            if (pos1 == pos2) {
-                return;
-            }
-            if (pos2 >= bits.length * ELM_SIZE) {
-                growBits(pos2);
-            }
+        if (pos1 < 0 || pos2 < 0 || pos2 < pos1) {
+            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+        }
 
-            int idx1 = pos1 / ELM_SIZE;
-            int idx2 = (pos2 - 1) / ELM_SIZE;
-            long factor1 = (~0L) << (pos1 % ELM_SIZE);
-            long factor2 = (~0L) >>> (ELM_SIZE - (pos2 % ELM_SIZE));
+        if (pos1 == pos2) {
+            return;
+        }
+        int len2 = ((pos2 - 1) >> OFFSET) + 1;
+        if (len2 > bits.length) {
+            growLength(len2);
+        }
 
-            if (idx1 == idx2) {
-                bits[idx1] ^= (factor1 & factor2);
-            } else {
-                bits[idx1] ^= factor1;
-                bits[idx2] ^= factor2;
-                for (int i = idx1 + 1; i < idx2; i++) {
-                    bits[i] ^= (~0L);
-                }
-            }
+        int idx1 = pos1 >> OFFSET;
+        int idx2 = (pos2 - 1) >> OFFSET;
+        long factor1 = (~0L) << (pos1 & RIGHT_BITS);
+        long factor2 = (~0L) >>> (ELM_SIZE - (pos2 & RIGHT_BITS));
+
+        if (idx1 == idx2) {
+            bits[idx1] ^= (factor1 & factor2);
         } else {
-            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+            bits[idx1] ^= factor1;
+            bits[idx2] ^= factor2;
+            for (int i = idx1 + 1; i < idx2; i++) {
+                bits[i] ^= (~0L);
+            }
         }
+        if (len2 > actualArrayLength) {
+            actualArrayLength = len2;
+        }
+        isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength
- 1] == 0));
+        needClear();
     }
 
     /**
@@ -538,7 +628,7 @@
      */
     public boolean intersects(BitSet bs) {
         long[] bsBits = bs.bits;
-        int length1 = bits.length, length2 = bsBits.length;
+        int length1 = actualArrayLength, length2 = bs.actualArrayLength;
 
         if (length1 <= length2) {
             for (int i = 0; i < length1; i++) {
@@ -566,10 +656,12 @@
      * @see #or
      * @see #xor
      */
-
     public void and(BitSet bs) {
         long[] bsBits = bs.bits;
-        int length1 = bits.length, length2 = bsBits.length;
+        if (!needClear) {
+            return;
+        }
+        int length1 = actualArrayLength, length2 = bs.actualArrayLength;
         if (length1 <= length2) {
             for (int i = 0; i < length1; i++) {
                 bits[i] &= bsBits[i];
@@ -581,7 +673,9 @@
             for (int i = length2; i < length1; i++) {
                 bits[i] = 0;
             }
+            actualArrayLength = length2;
         }
+        isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength
- 1] == 0));
     }
 
     /**
@@ -593,10 +687,16 @@
      */
     public void andNot(BitSet bs) {
         long[] bsBits = bs.bits;
-        int range = bits.length < bsBits.length ? bits.length : bsBits.length;
+        if (!needClear) {
+            return;
+        }
+        int range = actualArrayLength < bs.actualArrayLength ? actualArrayLength
+                : bs.actualArrayLength;
         for (int i = 0; i < range; i++) {
             bits[i] &= ~bsBits[i];
         }
+        actualArrayLength = range;
+        isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength
- 1] == 0));
     }
 
     /**
@@ -609,15 +709,27 @@
      * @see #and
      */
     public void or(BitSet bs) {
-        int nbits = bs.length();
-        int length = nbits / ELM_SIZE + (nbits % ELM_SIZE > 0 ? 1 : 0);
-        if (length > bits.length) {
-            growBits(nbits - 1);
-        }
-        long[] bsBits = bs.bits;
-        for (int i = 0; i < length; i++) {
-            bits[i] |= bsBits[i];
+        int bsActualLen = bs.getActualArrayLength();
+        if (bsActualLen > bits.length) {
+            long[] tempBits = new long[bsActualLen];
+            System.arraycopy(bs.bits, 0, tempBits, 0, bs.actualArrayLength);
+            for (int i = 0; i < actualArrayLength; i++) {
+                tempBits[i] |= bits[i];
+            }
+            bits = tempBits;
+            actualArrayLength = bsActualLen;
+            isLengthActual = true;
+        } else {
+            long[] bsBits = bs.bits;
+            for (int i = 0; i < bsActualLen; i++) {
+                bits[i] |= bsBits[i];
+            }
+            if (bsActualLen > actualArrayLength) {
+                actualArrayLength = bsActualLen;
+                isLengthActual = true;
+            }
         }
+        needClear();
     }
 
     /**
@@ -630,16 +742,27 @@
      * @see #and
      */
     public void xor(BitSet bs) {
-        int nbits = bs.length();
-        int length = nbits / ELM_SIZE + (nbits % ELM_SIZE > 0 ? 1 : 0);
-        if (length > bits.length) {
-            growBits(nbits - 1);
-        }
-        long[] bsBits = bs.bits;
-        for (int i = 0; i < length; i++) {
-            bits[i] ^= bsBits[i];
+        int bsActualLen = bs.getActualArrayLength();
+        if (bsActualLen > bits.length) {
+            long[] tempBits = new long[bsActualLen];
+            System.arraycopy(bs.bits, 0, tempBits, 0, bs.actualArrayLength);
+            for (int i = 0; i < actualArrayLength; i++) {
+                tempBits[i] ^= bits[i];
+            }
+            bits = tempBits;
+            actualArrayLength = bsActualLen;
+            isLengthActual = !((actualArrayLength > 0) && (bits[actualArrayLength
- 1] == 0));
+        } else {
+            long[] bsBits = bs.bits;
+            for (int i = 0; i < bsActualLen; i++) {
+                bits[i] ^= bsBits[i];
+            }
+            if (bsActualLen > actualArrayLength) {
+                actualArrayLength = bsActualLen;
+                isLengthActual = true;
+            }
         }
-
+        needClear();
     }
 
     /**
@@ -650,7 +773,7 @@
      * @see #length
      */
     public int size() {
-        return bits.length * ELM_SIZE;
+        return bits.length << OFFSET;
     }
 
     /**
@@ -659,19 +782,33 @@
      * @return the length of the BitSet
      */
     public int length() {
-        int idx = bits.length - 1;
+        int idx = actualArrayLength - 1;
         while (idx >= 0 && bits[idx] == 0) {
             --idx;
         }
+        actualArrayLength = idx + 1;
         if (idx == -1) {
             return 0;
         }
         int i = ELM_SIZE - 1;
         long val = bits[idx];
-        while ((val & (1L << i)) == 0 && i > 0) {
+        while ((val & (TWO_N_ARRAY[i])) == 0 && i > 0) {
             i--;
         }
-        return idx * ELM_SIZE + i + 1;
+        return (idx << OFFSET) + i + 1;
+    }
+
+    private final int getActualArrayLength() {
+        if (isLengthActual) {
+            return actualArrayLength;
+        }
+        int idx = actualArrayLength - 1;
+        while (idx >= 0 && bits[idx] == 0) {
+            --idx;
+        }
+        actualArrayLength = idx + 1;
+        isLengthActual = true;
+        return actualArrayLength;
     }
 
     /**
@@ -692,7 +829,7 @@
                 continue;
             }
             for (int j = 0; j < ELM_SIZE; j++) {
-                if (((bits[i] & (1L << j)) != 0)) {
+                if (((bits[i] & (TWO_N_ARRAY[j])) != 0)) {
                     if (comma) {
                         sb.append(", "); //$NON-NLS-1$
                     }
@@ -714,40 +851,41 @@
      * @return -1 if there is no bits that are set to true on or after pos.
      */
     public int nextSetBit(int pos) {
-        if (pos >= 0) {
-            if (pos >= bits.length * ELM_SIZE) {
-                return -1;
-            }
-
-            int idx = pos / ELM_SIZE;
-            // first check in the same bit set element
-            if (bits[idx] != 0L) {
-                for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++) {
-                    if (((bits[idx] & (1L << j)) != 0)) {
-                        return idx * ELM_SIZE + j;
-                    }
-                }
+        if (pos < 0) {
+            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+        }
 
-            }
-            idx++;
-            while (idx < bits.length && bits[idx] == 0L) {
-                idx++;
-            }
-            if (idx == bits.length) {
-                return -1;
-            }
+        if (pos >= actualArrayLength << OFFSET) {
+            return -1;
+        }
 
-            // we know for sure there is a bit set to true in this element
-            // since the bitset value is not 0L
-            for (int j = 0; j < ELM_SIZE; j++) {
-                if (((bits[idx] & (1L << j)) != 0)) {
-                    return idx * ELM_SIZE + j;
+        int idx = pos >> OFFSET;
+        // first check in the same bit set element
+        if (bits[idx] != 0L) {
+            for (int j = pos & RIGHT_BITS; j < ELM_SIZE; j++) {
+                if (((bits[idx] & (TWO_N_ARRAY[j])) != 0)) {
+                    return (idx << OFFSET) + j;
                 }
             }
 
+        }
+        idx++;
+        while (idx < actualArrayLength && bits[idx] == 0L) {
+            idx++;
+        }
+        if (idx == actualArrayLength) {
             return -1;
         }
-        throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+
+        // we know for sure there is a bit set to true in this element
+        // since the bitset value is not 0L
+        for (int j = 0; j < ELM_SIZE; j++) {
+            if (((bits[idx] & (TWO_N_ARRAY[j])) != 0)) {
+                return (idx << OFFSET) + j;
+            }
+        }
+
+        return -1;
     }
 
     /**
@@ -759,41 +897,42 @@
      *         than this bitset's size.
      */
     public int nextClearBit(int pos) {
-        if (pos >= 0) {
-            int bssize = bits.length * ELM_SIZE;
-            if (pos >= bssize) {
-                return pos;
-            }
-
-            int idx = pos / ELM_SIZE;
-            // first check in the same bit set element
-            if (bits[idx] != (~0L)) {
-                for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++) {
-                    if (((bits[idx] & (1L << j)) == 0)) {
-                        return idx * ELM_SIZE + j;
-                    }
-                }
+        if (pos < 0) {
+            throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+        }
 
-            }
-            idx++;
-            while (idx < bits.length && bits[idx] == (~0L)) {
-                idx++;
-            }
-            if (idx == bits.length) {
-                return bssize;
-            }
+        int length = actualArrayLength;
+        int bssize = length << OFFSET;
+        if (pos >= bssize) {
+            return pos;
+        }
 
-            // we know for sure there is a bit set to true in this element
-            // since the bitset value is not 0L
-            for (int j = 0; j < ELM_SIZE; j++) {
-                if (((bits[idx] & (1L << j)) == 0)) {
+        int idx = pos >> OFFSET;
+        // first check in the same bit set element
+        if (bits[idx] != (~0L)) {
+            for (int j = pos % ELM_SIZE; j < ELM_SIZE; j++) {
+                if (((bits[idx] & (TWO_N_ARRAY[j])) == 0)) {
                     return idx * ELM_SIZE + j;
                 }
             }
-
+        }
+        idx++;
+        while (idx < length && bits[idx] == (~0L)) {
+            idx++;
+        }
+        if (idx == length) {
             return bssize;
         }
-        throw new IndexOutOfBoundsException(Msg.getString("K0006")); //$NON-NLS-1$
+
+        // we know for sure there is a bit set to true in this element
+        // since the bitset value is not 0L
+        for (int j = 0; j < ELM_SIZE; j++) {
+            if (((bits[idx] & (TWO_N_ARRAY[j])) == 0)) {
+                return (idx << OFFSET) + j;
+            }
+        }
+
+        return bssize;
     }
 
     /**
@@ -803,12 +942,15 @@
      *         otherwise
      */
     public boolean isEmpty() {
-        for (int idx = 0; idx < bits.length; idx++) {
+        if (!needClear) {
+            return true;
+        }
+        int length = bits.length;
+        for (int idx = 0; idx < length; idx++) {
             if (bits[idx] != 0L) {
                 return false;
             }
         }
-
         return true;
     }
 
@@ -818,17 +960,34 @@
      * @return the number of true bits in the set
      */
     public int cardinality() {
+        if (!needClear) {
+            return 0;
+        }
         int count = 0;
-        for (int idx = 0; idx < bits.length; idx++) {
-            long temp = bits[idx];
-            if (temp != 0L) {
-                for (int i = 0; i < ELM_SIZE; i++) {
-                    if ((temp & (1L << i)) != 0L) {
-                        count++;
-                    }
-                }
-            }
+        int length = bits.length;
+        // FIXME: need to test performance, if still not satisfied, change it to
+        // 256-bits table based
+        for (int idx = 0; idx < length; idx++) {
+            count += pop(bits[idx] & 0xffffffffL);
+            count += pop(bits[idx] >>> 32);
         }
         return count;
+    }
+
+    private final int pop(long x) {
+        x = x - ((x >>> 1) & 0x55555555);
+        x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
+        x = (x + (x >>> 4)) & 0x0f0f0f0f;
+        x = x + (x >>> 8);
+        x = x + (x >>> 16);
+        return (int) x & 0x0000003f;
+    }
+
+    private void readObject(ObjectInputStream ois) throws IOException,
+            ClassNotFoundException {
+        ois.defaultReadObject();
+        this.isLengthActual = false;
+        this.actualArrayLength = bits.length;
+        this.needClear = this.getActualArrayLength() != 0;
     }
 }

Modified: harmony/enhanced/classlib/trunk/modules/luni/src/test/java/tests/api/java/util/BitSetTest.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/java/tests/api/java/util/BitSetTest.java?view=diff&rev=545213&r1=545212&r2=545213
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/luni/src/test/java/tests/api/java/util/BitSetTest.java
(original)
+++ harmony/enhanced/classlib/trunk/modules/luni/src/test/java/tests/api/java/util/BitSetTest.java
Thu Jun  7 08:19:21 2007
@@ -19,6 +19,8 @@
 
 import java.util.BitSet;
 
+import org.apache.harmony.testframework.serialization.SerializationTest;
+
 public class BitSetTest extends junit.framework.TestCase {
 
 	BitSet eightbs;
@@ -159,6 +161,14 @@
 		assertTrue("Test1: Wrong length, " + bs.size(), bs.length() == 0);
 		bs.clear(0);
 		assertTrue("Test2: Wrong length" + bs.size(), bs.length() == 0);
+		
+		bs = new BitSet();
+		try {
+			bs.clear(-1);
+			fail("Should throw IndexOutOfBoundsException");
+		} catch (IndexOutOfBoundsException e) {
+			// expected
+		}
 	}
 
 	/**
@@ -198,7 +208,7 @@
 		initialSize = bs.size();
 		bs.set(0, initialSize);
 		bs.clear(7, 64);
-		assertEquals("Failed to grow BitSet", 128, bs.size());
+		assertEquals("Failed to grow BitSet", 64, bs.size());
 		for (int i = 0; i < 7; i++)
 			assertTrue("Shouldn't have cleared bit " + i, bs.get(i));
 		for (int i = 7; i < 64; i++)
@@ -324,6 +334,14 @@
 		bs = new BitSet();
 		bs.set(63);
 		assertTrue("Test highest bit", bs.get(63));
+		
+		bs = new BitSet();
+		try {
+			bs.get(Integer.MIN_VALUE);
+			fail("Should throw IndexOutOfBoundsException");
+		} catch (IndexOutOfBoundsException e) {
+			// expected
+		}
 	}
 
 	/**
@@ -482,6 +500,14 @@
 
 		eightbs.set(5, true);
 		assertTrue("Should have set bit 5 to false", eightbs.get(5));
+		
+		try {
+            BitSet bs = new BitSet();
+            bs.set(-2147483648, false);
+            fail("Should throw IndexOutOfBoundsException");
+        } catch (IndexOutOfBoundsException e) {
+            // expected
+        }
 	}
 
 	/**
@@ -512,7 +538,7 @@
 		// pos1 and pos2 is in the same bitset element, boundary testing
 		bs = new BitSet(16);
 		bs.set(7, 64);
-		assertEquals("Failed to grow BitSet", 128, bs.size());
+		assertEquals("Failed to grow BitSet", 64, bs.size());
 		for (int i = 0; i < 7; i++)
 			assertTrue("Shouldn't have set bit " + i, !bs.get(i));
 		for (int i = 7; i < 64; i++)
@@ -708,7 +734,7 @@
 		bs.set(7);
 		bs.set(10);
 		bs.flip(7, 64);
-		assertEquals("Failed to grow BitSet", 128, bs.size());
+		assertEquals("Failed to grow BitSet", 64, bs.size());
 		for (int i = 0; i < 7; i++)
 			assertTrue("Shouldn't have flipped bit " + i, !bs.get(i));
 		assertTrue("Failed to flip bit 7", !bs.get(7));
@@ -936,6 +962,14 @@
 		for (int i = 64; i < 128; i++)
 			assertTrue("Failed to clear extra bits in the receiver BitSet", !bs
 					.get(i));
+		
+		bs = new BitSet(64);
+		try {
+			bs.and(null);
+			fail("Should throw NPE");
+		} catch (NullPointerException e) {
+			// expected
+		}
 	}
 
 	/**
@@ -954,6 +988,14 @@
 		bs = new BitSet(0);
 		bs.andNot(bs2);
 		assertEquals("Incorrect size", 0, bs.size());
+		
+		bs = new BitSet(64);
+		try {
+			bs.andNot(null);
+			fail("Should throw NPE");
+		} catch (NullPointerException e) {
+			// expected
+		}
 	}
 
 	/**
@@ -1268,8 +1310,11 @@
 		bs.set(127, 130);
 		bs.set(193);
 		bs.set(450);
+        
 		assertEquals("cardinality() returned wrong value", 48, bs.cardinality());
-
+        
+        
+        
 		bs.flip(0, 500);
 		assertEquals("cardinality() returned wrong value", 452, bs
 				.cardinality());
@@ -1280,8 +1325,39 @@
 		bs.set(0, 500);
 		assertEquals("cardinality() returned wrong value", 500, bs
 				.cardinality());
-	}
-
+        
+        
+        bs.clear();
+        bs.set(0, 64);
+        assertEquals("cardinality() returned wrong value", 64, bs.cardinality());
+	}
+    
+	public void test_serialization() throws Exception{
+        BitSet bs = new BitSet(500);
+        bs.set(5);
+        bs.set(32);
+        bs.set(63);
+        bs.set(64);
+        bs.set(71, 110);
+        bs.set(127, 130);
+        bs.set(193);
+        bs.set(450);        
+        SerializationTest.verifySelf(bs);   
+    }
+    
+    public void test_serializationCompatiblity() throws Exception{
+        BitSet bs = new BitSet(500);
+        bs.set(5);
+        bs.set(32);
+        bs.set(63);
+        bs.set(64);
+        bs.set(71, 110);
+        bs.set(127, 130);
+        bs.set(193);
+        bs.set(450);        
+        SerializationTest.verifyGolden(this, bs);
+    }
+    
 	/**
 	 * helper method to display the contents of a bitset
 	 * 

Added: harmony/enhanced/classlib/trunk/modules/luni/src/test/resources/serialization/tests/api/java/util/BitSetTest.golden.ser
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/luni/src/test/resources/serialization/tests/api/java/util/BitSetTest.golden.ser?view=auto&rev=545213
==============================================================================
Binary file - no diff available.

Propchange: harmony/enhanced/classlib/trunk/modules/luni/src/test/resources/serialization/tests/api/java/util/BitSetTest.golden.ser
------------------------------------------------------------------------------
    svn:mime-type = application/octet-stream



Mime
View raw message