Use ArrayList as children
Such that traversal is O(n) instead of O(n²)
Test: WindowContainerTests
Bug: 32668632
Change-Id: Ie52026a76a0f65c71ff6bd35d13b3d0c5d44bb3f
diff --git a/services/core/java/com/android/server/wm/WindowContainer.java b/services/core/java/com/android/server/wm/WindowContainer.java
index 84ba139..ca8c484 100644
--- a/services/core/java/com/android/server/wm/WindowContainer.java
+++ b/services/core/java/com/android/server/wm/WindowContainer.java
@@ -16,6 +16,11 @@
package com.android.server.wm;
+import static android.content.pm.ActivityInfo.SCREEN_ORIENTATION_BEHIND;
+import static android.content.pm.ActivityInfo.SCREEN_ORIENTATION_UNSET;
+import static android.content.pm.ActivityInfo.SCREEN_ORIENTATION_UNSPECIFIED;
+import static android.content.res.Configuration.EMPTY;
+
import android.annotation.CallSuper;
import android.content.res.Configuration;
import android.util.Pools;
@@ -27,11 +32,6 @@
import java.util.function.Consumer;
import java.util.function.Predicate;
-import static android.content.pm.ActivityInfo.SCREEN_ORIENTATION_BEHIND;
-import static android.content.pm.ActivityInfo.SCREEN_ORIENTATION_UNSET;
-import static android.content.pm.ActivityInfo.SCREEN_ORIENTATION_UNSPECIFIED;
-import static android.content.res.Configuration.EMPTY;
-
/**
* Defines common functionality for classes that can hold windows directly or through their
* children in a hierarchy form.
@@ -52,7 +52,7 @@
// List of children for this window container. List is in z-order as the children appear on
// screen with the top-most window container at the tail of the list.
- protected final LinkedList<E> mChildren = new LinkedList();
+ protected final WindowList<E> mChildren = new WindowList<E>();
/** Contains override configuration settings applied to this window container. */
private Configuration mOverrideConfiguration = new Configuration();
@@ -258,7 +258,7 @@
case POSITION_TOP:
if (mChildren.peekLast() != child) {
mChildren.remove(child);
- mChildren.addLast(child);
+ mChildren.add(child);
}
if (includingParents && getParent() != null) {
getParent().positionChildAt(POSITION_TOP, this /* child */,
@@ -649,7 +649,7 @@
}
if (mParent != null && mParent == other.mParent) {
- final LinkedList<WindowContainer> list = mParent.mChildren;
+ final WindowList<WindowContainer> list = mParent.mChildren;
return list.indexOf(this) > list.indexOf(other) ? 1 : -1;
}
@@ -685,7 +685,7 @@
// The position of the first non-common ancestor in the common ancestor list determines
// which is greater the which.
- final LinkedList<WindowContainer> list = commonAncestor.mChildren;
+ final WindowList<WindowContainer> list = commonAncestor.mChildren;
return list.indexOf(thisParentChain.peekLast()) > list.indexOf(otherParentChain.peekLast())
? 1 : -1;
}
diff --git a/services/core/java/com/android/server/wm/WindowList.java b/services/core/java/com/android/server/wm/WindowList.java
new file mode 100644
index 0000000..dfeba40
--- /dev/null
+++ b/services/core/java/com/android/server/wm/WindowList.java
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * 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.android.server.wm;
+
+import java.util.ArrayList;
+
+/**
+ * An {@link ArrayList} with extended functionality to be used as the children data structure in
+ * {@link WindowContainer}.
+ */
+class WindowList<E> extends ArrayList<E> {
+
+ void addFirst(E e) {
+ add(0, e);
+ }
+
+ E peekLast() {
+ return size() > 0 ? get(size() - 1) : null;
+ }
+
+ E peekFirst() {
+ return size() > 0 ? get(0) : null;
+ }
+}
diff --git a/services/tests/servicestests/src/com/android/server/wm/WindowTestUtils.java b/services/tests/servicestests/src/com/android/server/wm/WindowTestUtils.java
index d9349ed..b83532c 100644
--- a/services/tests/servicestests/src/com/android/server/wm/WindowTestUtils.java
+++ b/services/tests/servicestests/src/com/android/server/wm/WindowTestUtils.java
@@ -115,11 +115,11 @@
}
WindowState getFirstChild() {
- return mChildren.getFirst();
+ return mChildren.peekFirst();
}
WindowState getLastChild() {
- return mChildren.getLast();
+ return mChildren.peekLast();
}
int positionInParent() {