ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/ArrayDeque.java

Comparing jsr166/src/main/java/util/ArrayDeque.java (file contents):
Revision 1.95 by jsr166, Sat Oct 29 19:10:27 2016 UTC vs.
Revision 1.105 by jsr166, Tue Nov 1 21:42:45 2016 UTC

#	Line 90 | Line 90 | public class ArrayDeque<E> extends Abstr
90		*
91		* @param needed the required minimum extra capacity; must be positive
92		*/
93	<	private void grow(int needed) {
93	>	private Object[] grow(int needed) {
94		// overflow-conscious code
95		// checkInvariants();
96		final int oldCapacity = elements.length;
#	Line 110 | Line 110 | public class ArrayDeque<E> extends Abstr
110		Arrays.fill(elements, head, head + newSpace, null);
111		head += newSpace;
112		}
113	+	return elements;
114		// checkInvariants();
115		}
116
#	Line 243 | Line 244 | public class ArrayDeque<E> extends Abstr
244		* but does catch ones that corrupt traversal.  It's a little
245		* surprising that javac allows this abuse of generics.
246		*/
247	<	static final <E> E nonNullElementAt(Object[] elements, int i) {
248	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
247	>	static final <E> E nonNullElementAt(Object[] es, int i) {
248	>	@SuppressWarnings("unchecked") E e = (E) es[i];
249		if (e == null)
250		throw new ConcurrentModificationException();
251		return e;
#	Line 266 | Line 267 | public class ArrayDeque<E> extends Abstr
267		Object[] es;
268		int capacity, h;
269		final int s;
270	<	if ((s = size) == (capacity = (es = elements).length)) {
271	<	grow(1);
271	<	capacity = (es = elements).length;
272	<	}
270	>	if ((s = size) == (capacity = (es = elements).length))
271	>	capacity = (es = grow(1)).length;
272		if ((h = head - 1) < 0) h = capacity - 1;
273		es[head = h] = e;
274		size = s + 1;
#	Line 290 | Line 289 | public class ArrayDeque<E> extends Abstr
289		Object[] es;
290		int capacity;
291		final int s;
292	<	if ((s = size) == (capacity = (es = elements).length)) {
293	<	grow(1);
295	<	capacity = (es = elements).length;
296	<	}
292	>	if ((s = size) == (capacity = (es = elements).length))
293	>	capacity = (es = grow(1)).length;
294		es[add(head, s, capacity)] = e;
295		size = s + 1;
296		// checkInvariants();
#	Line 370 | Line 367 | public class ArrayDeque<E> extends Abstr
367		int s, h;
368		if ((s = size) <= 0)
369		return null;
370	<	final Object[] elements = this.elements;
371	<	@SuppressWarnings("unchecked") E e = (E) elements[h = head];
372	<	elements[h] = null;
373	<	if (++h >= elements.length) h = 0;
370	>	final Object[] es = elements;
371	>	@SuppressWarnings("unchecked") E e = (E) es[h = head];
372	>	es[h] = null;
373	>	if (++h >= es.length) h = 0;
374		head = h;
375		size = s - 1;
376		return e;
#	Line 384 | Line 381 | public class ArrayDeque<E> extends Abstr
381		final int s, tail;
382		if ((s = size) <= 0)
383		return null;
384	<	final Object[] elements = this.elements;
384	>	final Object[] es = elements;
385		@SuppressWarnings("unchecked")
386	<	E e = (E) elements[tail = add(head, s - 1, elements.length)];
387	<	elements[tail] = null;
386	>	E e = (E) es[tail = add(head, s - 1, es.length)];
387	>	es[tail] = null;
388		size = s - 1;
389		return e;
390		}
#	Line 409 | Line 406 | public class ArrayDeque<E> extends Abstr
406		// checkInvariants();
407		final int s;
408		if ((s = size) <= 0) throw new NoSuchElementException();
409	<	final Object[] elements = this.elements;
410	<	return (E) elements[add(head, s - 1, elements.length)];
409	>	final Object[] es = elements;
410	>	return (E) es[add(head, s - 1, es.length)];
411		}
412
413		public E peekFirst() {
#	Line 423 | Line 420 | public class ArrayDeque<E> extends Abstr
420		// checkInvariants();
421		final int s;
422		if ((s = size) <= 0) return null;
423	<	final Object[] elements = this.elements;
424	<	return (E) elements[add(head, s - 1, elements.length)];
423	>	final Object[] es = elements;
424	>	return (E) es[add(head, s - 1, es.length)];
425		}
426
427		/**
#	Line 441 | Line 438 | public class ArrayDeque<E> extends Abstr
438		*/
439		public boolean removeFirstOccurrence(Object o) {
440		if (o != null) {
441	<	final Object[] elements = this.elements;
445	<	final int capacity = elements.length;
441	>	final Object[] es = elements;
442		int i, end, to, todo;
443		todo = (end = (i = head) + size)
444	<	- (to = (capacity - end >= 0) ? end : capacity);
445	<	for (;; to = todo, i = 0, todo = 0) {
444	>	- (to = (es.length - end >= 0) ? end : es.length);
445	>	for (;; to = todo, todo = 0, i = 0) {
446		for (; i < to; i++)
447	<	if (o.equals(elements[i])) {
447	>	if (o.equals(es[i])) {
448		delete(i);
449		return true;
450		}
#	Line 472 | Line 468 | public class ArrayDeque<E> extends Abstr
468		*/
469		public boolean removeLastOccurrence(Object o) {
470		if (o != null) {
471	<	final Object[] elements = this.elements;
476	<	final int capacity = elements.length;
471	>	final Object[] es = elements;
472		int i, to, end, todo;
473		todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
474	<	for (;; to = (i = capacity - 1) - todo, todo = 0) {
474	>	for (;; to = (i = es.length - 1) - todo, todo = 0) {
475		for (; i > to; i--)
476	<	if (o.equals(elements[i])) {
476	>	if (o.equals(es[i])) {
477		delete(i);
478		return true;
479		}
#	Line 614 | Line 609 | public class ArrayDeque<E> extends Abstr
609		*/
610		boolean delete(int i) {
611		// checkInvariants();
612	<	final Object[] elements = this.elements;
613	<	final int capacity = elements.length;
612	>	final Object[] es = elements;
613	>	final int capacity = es.length;
614		final int h = head;
615		int front;              // number of elements before to-be-deleted elt
616		if ((front = i - h) < 0) front += capacity;
#	Line 623 | Line 618 | public class ArrayDeque<E> extends Abstr
618		if (front < back) {
619		// move front elements forwards
620		if (h <= i) {
621	<	System.arraycopy(elements, h, elements, h + 1, front);
621	>	System.arraycopy(es, h, es, h + 1, front);
622		} else { // Wrap around
623	<	System.arraycopy(elements, 0, elements, 1, i);
624	<	elements[0] = elements[capacity - 1];
625	<	System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
623	>	System.arraycopy(es, 0, es, 1, i);
624	>	es[0] = es[capacity - 1];
625	>	System.arraycopy(es, h, es, h + 1, front - (i + 1));
626		}
627	<	elements[h] = null;
627	>	es[h] = null;
628		if ((head = (h + 1)) >= capacity) head = 0;
629		size--;
630		// checkInvariants();
#	Line 638 | Line 633 | public class ArrayDeque<E> extends Abstr
633		// move back elements backwards
634		int tail = tail();
635		if (i <= tail) {
636	<	System.arraycopy(elements, i + 1, elements, i, back);
636	>	System.arraycopy(es, i + 1, es, i, back);
637		} else { // Wrap around
638		int firstLeg = capacity - (i + 1);
639	<	System.arraycopy(elements, i + 1, elements, i, firstLeg);
640	<	elements[capacity - 1] = elements[0];
641	<	System.arraycopy(elements, 1, elements, 0, back - firstLeg - 1);
639	>	System.arraycopy(es, i + 1, es, i, firstLeg);
640	>	es[capacity - 1] = es[0];
641	>	System.arraycopy(es, 1, es, 0, back - firstLeg - 1);
642		}
643	<	elements[tail] = null;
643	>	es[tail] = null;
644		size--;
645		// checkInvariants();
646		return true;
#	Line 710 | Line 705 | public class ArrayDeque<E> extends Abstr
705		public E next() {
706		if (remaining <= 0)
707		throw new NoSuchElementException();
708	<	final Object[] elements = ArrayDeque.this.elements;
709	<	E e = nonNullElementAt(elements, cursor);
708	>	final Object[] es = elements;
709	>	E e = nonNullElementAt(es, cursor);
710		lastRet = cursor;
711	<	if (++cursor >= elements.length) cursor = 0;
711	>	if (++cursor >= es.length) cursor = 0;
712		remaining--;
713		return e;
714		}
#	Line 731 | Line 726 | public class ArrayDeque<E> extends Abstr
726		}
727
728		public void forEachRemaining(Consumer<? super E> action) {
729	+	Objects.requireNonNull(action);
730		final int k;
731		if ((k = remaining) > 0) {
732		remaining = 0;
#	Line 747 | Line 743 | public class ArrayDeque<E> extends Abstr
743		public final E next() {
744		if (remaining <= 0)
745		throw new NoSuchElementException();
746	<	final Object[] elements = ArrayDeque.this.elements;
747	<	E e = nonNullElementAt(elements, cursor);
746	>	final Object[] es = elements;
747	>	E e = nonNullElementAt(es, cursor);
748		lastRet = cursor;
749	<	if (--cursor < 0) cursor = elements.length - 1;
749	>	if (--cursor < 0) cursor = es.length - 1;
750		remaining--;
751		return e;
752		}
#	Line 761 | Line 757 | public class ArrayDeque<E> extends Abstr
757		}
758
759		public final void forEachRemaining(Consumer<? super E> action) {
760	+	Objects.requireNonNull(action);
761		final int k;
762		if ((k = remaining) > 0) {
763		remaining = 0;
764	<	forEachRemainingDescending(action, elements, cursor, k);
764	>	final Object[] es = elements;
765	>	int i, end, to, todo;
766	>	todo = (to = ((end = (i = cursor) - k) >= -1) ? end : -1) - end;
767	>	for (;; to = (i = es.length - 1) - todo, todo = 0) {
768	>	for (; i > to; i--)
769	>	action.accept(nonNullElementAt(es, i));
770	>	if (todo == 0) break;
771	>	}
772		if ((lastRet = cursor - (k - 1)) < 0)
773	<	lastRet += elements.length;
773	>	lastRet += es.length;
774		}
775		}
776		}
#	Line 824 | Line 828 | public class ArrayDeque<E> extends Abstr
828		}
829
830		public void forEachRemaining(Consumer<? super E> action) {
831	+	Objects.requireNonNull(action);
832		final int k = remaining(); // side effect!
833		remaining = 0;
834		ArrayDeque.forEachRemaining(action, elements, cursor, k);
#	Line 855 | Line 860 | public class ArrayDeque<E> extends Abstr
860		@SuppressWarnings("unchecked")
861		public void forEach(Consumer<? super E> action) {
862		Objects.requireNonNull(action);
863	<	final Object[] elements = this.elements;
859	<	final int capacity = elements.length;
863	>	final Object[] es = elements;
864		int i, end, to, todo;
865		todo = (end = (i = head) + size)
866	<	- (to = (capacity - end >= 0) ? end : capacity);
867	<	for (;; to = todo, i = 0, todo = 0) {
866	>	- (to = (es.length - end >= 0) ? end : es.length);
867	>	for (;; to = todo, todo = 0, i = 0) {
868		for (; i < to; i++)
869	<	action.accept((E) elements[i]);
869	>	action.accept((E) es[i]);
870		if (todo == 0) break;
871		}
872		// checkInvariants();
#	Line 874 | Line 878 | public class ArrayDeque<E> extends Abstr
878		* checks for concurrent modification, for use in iterators.
879		*/
880		static <E> void forEachRemaining(
881	<	Consumer<? super E> action, Object[] elements, int i, int remaining) {
878	<	Objects.requireNonNull(action);
879	<	final int capacity = elements.length;
881	>	Consumer<? super E> action, Object[] es, int i, int remaining) {
882		int end, to, todo;
883		todo = (end = i + remaining)
884	<	- (to = (capacity - end >= 0) ? end : capacity);
885	<	for (;; to = todo, i = 0, todo = 0) {
884	>	- (to = (es.length - end >= 0) ? end : es.length);
885	>	for (;; to = todo, todo = 0, i = 0) {
886		for (; i < to; i++)
887	<	action.accept(nonNullElementAt(elements, i));
886	<	if (todo == 0) break;
887	<	}
888	<	}
889	<
890	<	static <E> void forEachRemainingDescending(
891	<	Consumer<? super E> action, Object[] elements, int i, int remaining) {
892	<	Objects.requireNonNull(action);
893	<	final int capacity = elements.length;
894	<	int end, to, todo;
895	<	todo = (to = ((end = i - remaining) >= -1) ? end : -1) - end;
896	<	for (;; to = (i = capacity - 1) - todo, todo = 0) {
897	<	for (; i > to; i--)
898	<	action.accept(nonNullElementAt(elements, i));
887	>	action.accept(nonNullElementAt(es, i));
888		if (todo == 0) break;
889		}
890		}
#	Line 907 | Line 896 | public class ArrayDeque<E> extends Abstr
896		* @param operator the operator to apply to each element
897		* @since TBD
898		*/
899	+	@SuppressWarnings("unchecked")
900		/* public */ void replaceAll(UnaryOperator<E> operator) {
901		Objects.requireNonNull(operator);
902	<	final Object[] elements = this.elements;
913	<	final int capacity = elements.length;
902	>	final Object[] es = elements;
903		int i, end, to, todo;
904		todo = (end = (i = head) + size)
905	<	- (to = (capacity - end >= 0) ? end : capacity);
906	<	for (;; to = todo, i = 0, todo = 0) {
905	>	- (to = (es.length - end >= 0) ? end : es.length);
906	>	for (;; to = todo, todo = 0, i = 0) {
907		for (; i < to; i++)
908	<	elements[i] = operator.apply(elementAt(i));
908	>	es[i] = operator.apply((E) es[i]);
909		if (todo == 0) break;
910		}
911		// checkInvariants();
#	Line 947 | Line 936 | public class ArrayDeque<E> extends Abstr
936		}
937
938		/** Implementation of bulk remove methods. */
939	+	@SuppressWarnings("unchecked")
940		private boolean bulkRemove(Predicate<? super E> filter) {
941		// checkInvariants();
942	<	final Object[] elements = this.elements;
943	<	final int capacity = elements.length;
944	<	int i = head, j = i, remaining = size, deleted = 0;
942	>	final Object[] es = elements;
943	>	int i, end, to, todo;
944	>	todo = (end = (i = head) + size)
945	>	- (to = (es.length - end >= 0) ? end : es.length);
946	>	// Optimize for initial run of non-removed elements
947	>	findFirstRemoved:
948	>	for (;; to = todo, todo = 0, i = 0) {
949	>	for (; i < to; i++)
950	>	if (filter.test((E) es[i]))
951	>	break findFirstRemoved;
952	>	if (todo == 0) return false;
953	>	}
954	>	bulkRemoveModified(filter, i, to, todo);
955	>	return true;
956	>	}
957	>
958	>	/**
959	>	* Helper for bulkRemove, in case of at least one deletion.
960	>	* @param i valid index of first element to be deleted
961	>	*/
962	>	@SuppressWarnings("unchecked")
963	>	private void bulkRemoveModified(
964	>	Predicate<? super E> filter, int i, int to, int todo) {
965	>	final Object[] es = elements;
966	>	final int capacity = es.length;
967	>	// a two-finger algorithm, with hare i and tortoise j
968	>	int j = i++;
969		try {
970	<	for (; remaining > 0; remaining--) {
971	<	@SuppressWarnings("unchecked") E e = (E) elements[i];
972	<	if (filter.test(e))
973	<	deleted++;
974	<	else {
975	<	if (j != i)
976	<	elements[j] = e;
977	<	if (++j >= capacity) j = 0;
978	<	}
979	<	if (++i >= capacity) i = 0;
970	>	for (;;) {
971	>	E e;
972	>	// In this loop, i and j are on the same leg, with i > j
973	>	for (; i < to; i++)
974	>	if (!filter.test(e = (E) es[i]))
975	>	es[j++] = e;
976	>	if (todo == 0) break;
977	>	// In this loop, j is on the first leg, i on the second
978	>	for (to = todo, todo = 0, i = 0; i < to && j < capacity; i++)
979	>	if (!filter.test(e = (E) es[i]))
980	>	es[j++] = e;
981	>	if (i >= to) break;
982	>	j = 0;          // j rejoins i on second leg
983		}
984	<	return deleted > 0;
984	>	bulkRemoveClear(es, j, i);
985	>	// checkInvariants();
986		} catch (Throwable ex) {
987	<	if (deleted > 0)
988	<	for (; remaining > 0; remaining--) {
989	<	elements[j] = elements[i];
990	<	if (++i >= capacity) i = 0;
991	<	if (++j >= capacity) j = 0;
992	<	}
993	<	throw ex;
976	<	} finally {
977	<	size -= deleted;
978	<	clearSlice(elements, j, deleted);
987	>	// copy remaining elements
988	>	for (int remaining = (to - i) + todo; --remaining >= 0;) {
989	>	es[j] = es[i];
990	>	if (++i >= capacity) i = 0;
991	>	if (++j >= capacity) j = 0;
992	>	}
993	>	bulkRemoveClear(es, j, i);
994		// checkInvariants();
995	+	throw ex;
996		}
997		}
998
999		/**
1000	+	* Nulls out all elements from index j upto index i.
1001	+	*/
1002	+	private void bulkRemoveClear(Object[] es, int j, int i) {
1003	+	int deleted;
1004	+	if ((deleted = i - j) <= 0) deleted += es.length;
1005	+	size -= deleted;
1006	+	circularClear(es, j, deleted);
1007	+	}
1008	+
1009	+	/**
1010		* Returns {@code true} if this deque contains the specified element.
1011		* More formally, returns {@code true} if and only if this deque contains
1012		* at least one element {@code e} such that {@code o.equals(e)}.
#	Line 990 | Line 1016 | public class ArrayDeque<E> extends Abstr
1016		*/
1017		public boolean contains(Object o) {
1018		if (o != null) {
1019	<	final Object[] elements = this.elements;
994	<	final int capacity = elements.length;
1019	>	final Object[] es = elements;
1020		int i, end, to, todo;
1021		todo = (end = (i = head) + size)
1022	<	- (to = (capacity - end >= 0) ? end : capacity);
1023	<	for (;; to = todo, i = 0, todo = 0) {
1022	>	- (to = (es.length - end >= 0) ? end : es.length);
1023	>	for (;; to = todo, todo = 0, i = 0) {
1024		for (; i < to; i++)
1025	<	if (o.equals(elements[i]))
1025	>	if (o.equals(es[i]))
1026		return true;
1027		if (todo == 0) break;
1028		}
#	Line 1027 | Line 1052 | public class ArrayDeque<E> extends Abstr
1052		* The deque will be empty after this call returns.
1053		*/
1054		public void clear() {
1055	<	clearSlice(elements, head, size);
1055	>	circularClear(elements, head, size);
1056		size = head = 0;
1057		// checkInvariants();
1058		}
1059
1060		/**
1061		* Nulls out count elements, starting at array index from.
1062	+	* Special case (from == es.length) is treated the same as (from == 0).
1063		*/
1064	<	private static void clearSlice(Object[] elements, int from, int count) {
1065	<	final int capacity = elements.length, end = from + count;
1066	<	final int leg = (capacity - end >= 0) ? end : capacity;
1067	<	Arrays.fill(elements, from, leg, null);
1068	<	if (leg != end)
1069	<	Arrays.fill(elements, 0, end - capacity, null);
1064	>	private static void circularClear(Object[] es, int from, int count) {
1065	>	int end, to, todo;
1066	>	todo = (end = from + count)
1067	>	- (to = (es.length - end >= 0) ? end : es.length);
1068	>	for (;; to = todo, todo = 0, from = 0) {
1069	>	Arrays.fill(es, from, to, null);
1070	>	if (todo == 0) break;
1071	>	}
1072		}
1073
1074		/**
#	Line 1061 | Line 1089 | public class ArrayDeque<E> extends Abstr
1089		}
1090
1091		private <T> T[] toArray(Class<T[]> klazz) {
1092	<	final Object[] elements = this.elements;
1065	<	final int capacity = elements.length;
1066	<	final int head = this.head, end = head + size;
1092	>	final Object[] es = elements;
1093		final T[] a;
1094	<	if (end >= 0) {
1095	<	a = Arrays.copyOfRange(elements, head, end, klazz);
1094	>	final int head, len, end, todo;
1095	>	todo = size - (len = Math.min(size, es.length - (head = this.head)));
1096	>	if ((end = head + size) >= 0) {
1097	>	a = Arrays.copyOfRange(es, head, end, klazz);
1098		} else {
1099		// integer overflow!
1100	<	a = Arrays.copyOfRange(elements, 0, size, klazz);
1101	<	System.arraycopy(elements, head, a, 0, capacity - head);
1100	>	a = Arrays.copyOfRange(es, 0, size, klazz);
1101	>	System.arraycopy(es, head, a, 0, len);
1102		}
1103	<	if (end - capacity > 0)
1104	<	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1103	>	if (todo > 0)
1104	>	System.arraycopy(es, 0, a, len, todo);
1105		return a;
1106		}
1107
#	Line 1115 | Line 1143 | public class ArrayDeque<E> extends Abstr
1143		*/
1144		@SuppressWarnings("unchecked")
1145		public <T> T[] toArray(T[] a) {
1146	<	final int size = this.size;
1147	<	if (size > a.length)
1146	>	final int size;
1147	>	if ((size = this.size) > a.length)
1148		return toArray((Class<T[]>) a.getClass());
1149	<	final Object[] elements = this.elements;
1150	<	final int capacity = elements.length;
1151	<	final int head = this.head, end = head + size;
1152	<	final int front = (capacity - end >= 0) ? size : capacity - head;
1153	<	System.arraycopy(elements, head, a, 0, front);
1154	<	if (front != size)
1155	<	System.arraycopy(elements, 0, a, capacity - head, end - capacity);
1149	>	final Object[] es = elements;
1150	>	int i, j, len, todo;
1151	>	todo = size - (len = Math.min(size, es.length - (i = head)));
1152	>	for (j = 0;; j += len, len = todo, todo = 0, i = 0) {
1153	>	System.arraycopy(es, i, a, j, len);
1154	>	if (todo == 0) break;
1155	>	}
1156		if (size < a.length)
1157		a[size] = null;
1158		return a;
#	Line 1167 | Line 1195 | public class ArrayDeque<E> extends Abstr
1195		s.writeInt(size);
1196
1197		// Write out elements in order.
1198	<	final Object[] elements = this.elements;
1171	<	final int capacity = elements.length;
1198	>	final Object[] es = elements;
1199		int i, end, to, todo;
1200		todo = (end = (i = head) + size)
1201	<	- (to = (capacity - end >= 0) ? end : capacity);
1202	<	for (;; to = todo, i = 0, todo = 0) {
1201	>	- (to = (es.length - end >= 0) ? end : es.length);
1202	>	for (;; to = todo, todo = 0, i = 0) {
1203		for (; i < to; i++)
1204	<	s.writeObject(elements[i]);
1204	>	s.writeObject(es[i]);
1205		if (todo == 0) break;
1206		}
1207		}

Diff Legend

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