ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166e/extra/ReadMostlyVector.java
(Generate patch)

Comparing jsr166/src/jsr166e/extra/ReadMostlyVector.java (file contents):
Revision 1.5 by dl, Sat Jul 16 16:05:32 2011 UTC vs.
Revision 1.13 by jsr166, Fri Aug 5 17:08:04 2011 UTC

# Line 19 | Line 19 | import java.util.*;
19   * best-effort in the presence of concurrent modifications, and do
20   * <em>NOT</em> throw {@link ConcurrentModificationException}.  An
21   * iterator's {@code next()} method returns consecutive elements as
22 < * they appear in the underlying array upon each access. Alternatvely,
22 > * they appear in the underlying array upon each access. Alternatively,
23   * method {@link #snapshotIterator} may be used for deterministic
24   * traversals, at the expense of making a copy, and unavailability of
25   * method {@code Iterator.remove}.
# Line 57 | Line 57 | public class ReadMostlyVector<E> impleme
57      private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
58  
59      // fields are non-private to simpify nested class access
60 <    Object[] array;
60 >    volatile Object[] array;
61      final SequenceLock lock;
62 <    int count;
62 >    volatile int count;
63      final int capacityIncrement;
64  
65      /**
# Line 129 | Line 129 | public class ReadMostlyVector<E> impleme
129      }
130  
131      // For explanation, see CopyOnWriteArrayList
132 <    final void grow(int minCapacity) {
132 >    final Object[] grow(int minCapacity) {
133          int oldCapacity = array.length;
134          int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
135                                           capacityIncrement : oldCapacity);
# Line 137 | Line 137 | public class ReadMostlyVector<E> impleme
137              newCapacity = minCapacity;
138          if (newCapacity - MAX_ARRAY_SIZE > 0)
139              newCapacity = hugeCapacity(minCapacity);
140 <        array = Arrays.copyOf(array, newCapacity);
140 >        return array = Arrays.copyOf(array, newCapacity);
141      }
142  
143      static int hugeCapacity(int minCapacity) {
# Line 161 | Line 161 | public class ReadMostlyVector<E> impleme
161              Object e = items[i];
162              if (lock.getSequence() != seq)
163                  break;
164 <            if (x == null? e == null : x.equals(e))
164 >            if ((x == null) ? e == null : x.equals(e))
165                  return i;
166          }
167          return -1;
# Line 171 | Line 171 | public class ReadMostlyVector<E> impleme
171          Object[] items = array;
172          for (int i = index; i < fence; ++i) {
173              Object e = items[i];
174 <            if (x == null? e == null : x.equals(e))
174 >            if ((x == null) ? e == null : x.equals(e))
175                  return i;
176          }
177          return -1;
# Line 183 | Line 183 | public class ReadMostlyVector<E> impleme
183              Object e = items[i];
184              if (lock.getSequence() != seq)
185                  break;
186 <            if (x == null? e == null : x.equals(e))
186 >            if ((x == null) ? e == null : x.equals(e))
187                  return i;
188          }
189          return -1;
# Line 193 | Line 193 | public class ReadMostlyVector<E> impleme
193          Object[] items = array;
194          for (int i = index; i >= origin; --i) {
195              Object e = items[i];
196 <            if (x == null? e == null : x.equals(e))
196 >            if ((x == null) ? e == null : x.equals(e))
197                  return i;
198          }
199          return -1;
# Line 201 | Line 201 | public class ReadMostlyVector<E> impleme
201  
202      final void rawAdd(Object e) {
203          int n = count;
204 <        if (n >= array.length)
205 <            grow(n + 1);
206 <        array[n] = e;
204 >        Object[] items = array;
205 >        if (n >= items.length)
206 >            items = grow(n + 1);
207 >        items[n] = e;
208          count = n + 1;
209      }
210  
211      final void rawAddAt(int index, Object e) {
212          int n = count;
213 +        Object[] items = array;
214          if (index > n)
215              throw new ArrayIndexOutOfBoundsException(index);
216 <        if (n >= array.length)
217 <            grow(n + 1);
216 >        if (n >= items.length)
217 >            items = grow(n + 1);
218          if (index < n)
219 <            System.arraycopy(array, index, array, index + 1, n - index);
220 <        array[index] = e;
219 >            System.arraycopy(items, index, items, index + 1, n - index);
220 >        items[index] = e;
221          count = n + 1;
222      }
223  
224      final boolean rawAddAllAt(int index, Object[] elements) {
225          int n = count;
226 +        Object[] items = array;
227          if (index < 0 || index > n)
228              throw new ArrayIndexOutOfBoundsException(index);
229          int len = elements.length;
230          if (len == 0)
231              return false;
232          int newCount = n + len;
233 <        if (newCount >= array.length)
234 <            grow(newCount);
235 <        int mv = count - index;
233 >        if (newCount >= items.length)
234 >            items = grow(newCount);
235 >        int mv = n - index;
236          if (mv > 0)
237 <            System.arraycopy(array, index, array, index + len, mv);
238 <        System.arraycopy(elements, 0, array, index, len);
237 >            System.arraycopy(items, index, items, index + len, mv);
238 >        System.arraycopy(elements, 0, items, index, len);
239          count = newCount;
240          return true;
241      }
242  
243      final boolean rawRemoveAt(int index) {
244          int n = count - 1;
245 +        Object[] items = array;
246          if (index < 0 || index > n)
247              return false;
248          int mv = n - index;
249          if (mv > 0)
250 <            System.arraycopy(array, index + 1, array, index, mv);
251 <        array[n] = null;
250 >            System.arraycopy(items, index + 1, items, index, mv);
251 >        items[n] = null;
252          count = n;
253          return true;
254      }
# Line 281 | Line 285 | public class ReadMostlyVector<E> impleme
285          if (c != this) {
286              lock.lock();
287              try {
288 +                Object[] items = array;
289                  int i = origin;
290                  int n = count;
291                  int fence = bound < 0 || bound > n ? n : bound;
292                  while (i >= 0 && i < fence) {
293 <                    if (c.contains(array[i]))
293 >                    if (c.contains(items[i]))
294                          ++i;
295                      else {
296                          --fence;
297 <                        int mv = --count - i;
297 >                        int mv = --n - i;
298                          if (mv > 0)
299 <                            System.arraycopy(array, i + 1, array, i, mv);
295 <                        removed = true;
299 >                            System.arraycopy(items, i + 1, items, i, mv);
300                      }
301                  }
302 +                if (count != n) {
303 +                    count = n;
304 +                    removed = true;
305 +                }
306              } finally {
307                  lock.unlock();
308              }
# Line 306 | Line 314 | public class ReadMostlyVector<E> impleme
314          int n = count;
315          int fence = bound < 0 || bound > n ? n : bound;
316          if (origin >= 0 && origin < fence) {
317 +            Object[] items = array;
318              int removed = fence - origin;
319              int newCount = n - removed;
320              int mv = n - (origin + removed);
321              if (mv > 0)
322 <                System.arraycopy(array, origin + removed, array, origin, mv);
322 >                System.arraycopy(items, origin + removed, items, origin, mv);
323              for (int i = n; i < newCount; ++i)
324 <                array[i] = null;
324 >                items[i] = null;
325              count = newCount;
326          }
327      }
# Line 324 | Line 333 | public class ReadMostlyVector<E> impleme
333          try {
334              for (;;) {
335                  long seq = lock.awaitAvailability();
336 +                int n = count;
337                  Object[] items = array;
338                  int len = items.length;
329 –                int n = count;
339                  if (n > len)
340                      continue;
341                  int fence = bound < 0 || bound > n ? n : bound;
# Line 335 | Line 344 | public class ReadMostlyVector<E> impleme
344                  else {
345                      contained = true;
346                      for (Object e : c) {
347 <                        int idx = (locked?
347 >                        int idx = (locked ?
348                                     rawIndexOf(e, origin, fence) :
349                                     validatedIndexOf(e, items, origin,
350                                                      fence, seq));
# Line 407 | Line 416 | public class ReadMostlyVector<E> impleme
416                  hash = 1;
417                  long seq = lock.awaitAvailability();
418                  Object[] items = array;
410 –                int len = items.length;
419                  int n = count;
420 +                int len = items.length;
421                  if (n > len)
422                      continue;
423                  int fence = bound < 0 || bound > n ? n : bound;
# Line 438 | Line 447 | public class ReadMostlyVector<E> impleme
447              outer:for (;;) {
448                  long seq = lock.awaitAvailability();
449                  Object[] items = array;
441 –                int len = items.length;
450                  int n = count;
451 +                int len = items.length;
452                  if (n > len)
453                      continue;
454                  int fence = bound < 0 || bound > n ? n : bound;
# Line 485 | Line 494 | public class ReadMostlyVector<E> impleme
494                  result = null;
495                  long seq = lock.awaitAvailability();
496                  Object[] items = array;
488 –                int len = items.length;
497                  int n = count;
498 +                int len = items.length;
499                  if (n > len)
500                      continue;
501                  int fence = bound < 0 || bound > n ? n : bound;
# Line 514 | Line 523 | public class ReadMostlyVector<E> impleme
523              for (;;) {
524                  long seq = lock.awaitAvailability();
525                  Object[] items = array;
517 –                int len = items.length;
526                  int n = count;
527 +                int len = items.length;
528                  if (n > len)
529                      continue;
530                  int fence = bound < 0 || bound > n ? n : bound;
# Line 524 | Line 533 | public class ReadMostlyVector<E> impleme
533                      rlen = 0;
534                  if (origin < 0 || alen >= rlen) {
535                      if (rlen > 0)
536 <                        System.arraycopy(array, 0, a, origin, rlen);
536 >                        System.arraycopy(items, 0, a, origin, rlen);
537                      if (alen > rlen)
538                          a[rlen] = null;
539                      result = a;
540                  }
541                  else
542 <                    result = (T[]) Arrays.copyOfRange(array, origin,
542 >                    result = (T[]) Arrays.copyOfRange(items, origin,
543                                                        fence, a.getClass());
544                  if (lock.getSequence() == seq)
545                      break;
# Line 575 | Line 584 | public class ReadMostlyVector<E> impleme
584          SequenceLock lock = this.lock;
585          lock.lock();
586          try {
587 <            int newCount = count + len;
588 <            if (newCount >= array.length)
589 <                grow(newCount);
590 <            System.arraycopy(elements, 0, array, count, len);
587 >            Object[] items = array;
588 >            int n = count;
589 >            int newCount = n + len;
590 >            if (newCount >= items.length)
591 >                items = grow(newCount);
592 >            System.arraycopy(elements, 0, items, n, len);
593              count = newCount;
594          } finally {
595              lock.unlock();
# Line 603 | Line 614 | public class ReadMostlyVector<E> impleme
614          SequenceLock lock = this.lock;
615          lock.lock();
616          try {
617 <            for (int i = 0; i < count; i++)
618 <                array[i] = null;
617 >            int n = count;
618 >            Object[] items = array;
619 >            for (int i = 0; i < n; i++)
620 >                items[i] = null;
621              count = 0;
622          } finally {
623              lock.unlock();
# Line 631 | Line 644 | public class ReadMostlyVector<E> impleme
644          SequenceLock lock = this.lock;
645          for (;;) {
646              long seq = lock.awaitAvailability();
634 –            Object[] items = array;
647              int n = count;
648 +            Object[] items = array;
649              if (n > items.length)
650                  continue;
651              Object e; boolean ex;
# Line 659 | Line 672 | public class ReadMostlyVector<E> impleme
672  
673      public int indexOf(Object o) {
674          SequenceLock lock = this.lock;
675 <        long seq = lock.awaitAvailability();
676 <        Object[] items = array;
677 <        int n = count;
678 <        if (n <= items.length) {
679 <            boolean valid = true;
680 <            for (int i = 0; i < n; ++i) {
681 <                Object e = items[i];
682 <                if (lock.getSequence() == seq) {
683 <                    if (o == null? e == null : o.equals(e))
675 >        for (;;) {
676 >            long seq = lock.awaitAvailability();
677 >            Object[] items = array;
678 >            int n = count;
679 >            if (n <= items.length) {
680 >                for (int i = 0; i < n; ++i) {
681 >                    Object e = items[i];
682 >                    if (lock.getSequence() != seq) {
683 >                        lock.lock();
684 >                        try {
685 >                            return rawIndexOf(o, 0, count);
686 >                        } finally {
687 >                            lock.unlock();
688 >                        }
689 >                    }
690 >                    else if ((o == null) ? e == null : o.equals(e))
691                          return i;
692                  }
673 –                else {
674 –                    valid = false;
675 –                    break;
676 –                }
677 –            }
678 –            if (valid)
693                  return -1;
694 <        }
681 <        lock.lock();
682 <        try {
683 <            return rawIndexOf(o, 0, count);
684 <        } finally {
685 <            lock.unlock();
694 >            }
695          }
696      }
697  
698      public boolean isEmpty() {
690 –        long ignore = lock.getSequence();
699          return count == 0;
700      }
701  
702      public Iterator<E> iterator() {
703 <        return new Itr(this, 0);
703 >        return new Itr<E>(this, 0);
704      }
705  
706      public int lastIndexOf(Object o) {
707          SequenceLock lock = this.lock;
708 <        long seq = lock.awaitAvailability();
709 <        Object[] items = array;
710 <        int n = count;
711 <        if (n <= items.length) {
712 <            int idx = validatedLastIndexOf(o, items, n - 1, 0, seq);
713 <            if (lock.getSequence() == seq)
714 <                return idx;
715 <        }
716 <        lock.lock();
717 <        try {
718 <            return rawLastIndexOf(o, count - 1, 0);
719 <        } finally {
720 <            lock.unlock();
708 >        for (;;) {
709 >            long seq = lock.awaitAvailability();
710 >            Object[] items = array;
711 >            int n = count;
712 >            if (n <= items.length) {
713 >                for (int i = n - 1; i >= 0; --i) {
714 >                    Object e = items[i];
715 >                    if (lock.getSequence() != seq) {
716 >                        lock.lock();
717 >                        try {
718 >                            return rawLastIndexOf(o, 0, count);
719 >                        } finally {
720 >                            lock.unlock();
721 >                        }
722 >                    }
723 >                    else if ((o == null) ? e == null : o.equals(e))
724 >                        return i;
725 >                }
726 >                return -1;
727 >            }
728          }
729      }
730  
731      public ListIterator<E> listIterator() {
732 <        return new Itr(this, 0);
732 >        return new Itr<E>(this, 0);
733      }
734  
735      public ListIterator<E> listIterator(int index) {
736 <        return new Itr(this, index);
736 >        return new Itr<E>(this, index);
737      }
738  
739      public E remove(int index) {
# Line 761 | Line 776 | public class ReadMostlyVector<E> impleme
776          SequenceLock lock = this.lock;
777          lock.lock();
778          try {
779 +            Object[] items = array;
780              if (index < 0 || index >= count)
781                  throw new ArrayIndexOutOfBoundsException(index);
782 <            oldValue = array[index];
783 <            array[index] = element;
782 >            oldValue = items[index];
783 >            items[index] = element;
784          } finally {
785              lock.unlock();
786          }
# Line 772 | Line 788 | public class ReadMostlyVector<E> impleme
788      }
789  
790      public int size() {
775 –        long ignore = lock.getSequence();
791          return count;
792      }
793  
# Line 781 | Line 796 | public class ReadMostlyVector<E> impleme
796          int ssize = toIndex - fromIndex;
797          if (fromIndex < 0 || toIndex > c || ssize < 0)
798              throw new IndexOutOfBoundsException();
799 <        return new ReadMostlyVectorSublist(this, fromIndex, ssize);
799 >        return new ReadMostlyVectorSublist<E>(this, fromIndex, ssize);
800      }
801  
802      public Object[] toArray() {
# Line 802 | Line 817 | public class ReadMostlyVector<E> impleme
817       * Append the element if not present.
818       *
819       * @param e element to be added to this list, if absent
820 <     * @return <tt>true</tt> if the element was added
820 >     * @return {@code true} if the element was added
821       */
822      public boolean addIfAbsent(E e) {
823          boolean added;
# Line 857 | Line 872 | public class ReadMostlyVector<E> impleme
872       * Returns an iterator operating over a snapshot copy of the
873       * elements of this collection created upon construction of the
874       * iterator. The iterator does <em>NOT</em> support the
875 <     * <tt>remove</tt> method.
875 >     * {@code remove} method.
876       *
877       * @return an iterator over the elements in this list in proper sequence
878       */
# Line 1009 | Line 1024 | public class ReadMostlyVector<E> impleme
1024              if (newSize > n)
1025                  grow(newSize);
1026              else {
1027 +                Object[] items = array;
1028                  for (int i = newSize ; i < n ; i++)
1029 <                    array[i] = null;
1029 >                    items[i] = null;
1030              }
1031              count = newSize;
1032          } finally {
# Line 1034 | Line 1050 | public class ReadMostlyVector<E> impleme
1050          SequenceLock lock = this.lock;
1051          lock.lock();
1052          try {
1053 <            if (count < array.length)
1054 <                array = Arrays.copyOf(array, count);
1053 >            Object[] items = array;
1054 >            int n = count;
1055 >            if (n < items.length)
1056 >                array = Arrays.copyOf(items, n);
1057          } finally {
1058              lock.unlock();
1059          }
# Line 1057 | Line 1075 | public class ReadMostlyVector<E> impleme
1075  
1076      /** See {@link Vector#elements} */
1077      public Enumeration<E> elements() {
1078 <        return new Itr(this, 0);
1078 >        return new Itr<E>(this, 0);
1079      }
1080  
1081      /** See {@link Vector#capacity} */
1082      public int capacity() {
1065 –        long ignore = lock.getSequence();
1083          return array.length;
1084      }
1085  
# Line 1103 | Line 1120 | public class ReadMostlyVector<E> impleme
1120  
1121      // other methods
1122  
1123 <    public Object clone() {
1123 >    public ReadMostlyVector<E> clone() {
1124          SequenceLock lock = this.lock;
1125          Object[] a = null;
1126          boolean retry = false;
# Line 1123 | Line 1140 | public class ReadMostlyVector<E> impleme
1140                  lock.unlock();
1141              }
1142          }
1143 <        return new ReadMostlyVector(a, n, capacityIncrement);
1143 >        return new ReadMostlyVector<E>(a, n, capacityIncrement);
1144      }
1145  
1146      private void writeObject(java.io.ObjectOutputStream s)
# Line 1413 | Line 1430 | public class ReadMostlyVector<E> impleme
1430          }
1431  
1432          public Iterator<E> iterator() {
1433 <            return new SubItr(this, offset);
1433 >            return new SubItr<E>(this, offset);
1434          }
1435  
1436          public int lastIndexOf(Object o) {
# Line 1437 | Line 1454 | public class ReadMostlyVector<E> impleme
1454          }
1455  
1456          public ListIterator<E> listIterator() {
1457 <            return new SubItr(this, offset);
1457 >            return new SubItr<E>(this, offset);
1458          }
1459  
1460          public ListIterator<E> listIterator(int index) {
1461 <            return new SubItr(this, index + offset);
1461 >            return new SubItr<E>(this, index + offset);
1462          }
1463  
1464          public E remove(int index) {
# Line 1501 | Line 1518 | public class ReadMostlyVector<E> impleme
1518              int ssize = toIndex - fromIndex;
1519              if (fromIndex < 0 || toIndex > c || ssize < 0)
1520                  throw new IndexOutOfBoundsException();
1521 <            return new ReadMostlyVectorSublist(list, offset+fromIndex, ssize);
1521 >            return new ReadMostlyVectorSublist<E>(list, offset+fromIndex, ssize);
1522          }
1523  
1524          public Object[] toArray() {

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines