From 612bb885bcef87034070e8e3bfc0b0e953c0f606 Mon Sep 17 00:00:00 2001
From: Jorim Jaggi <jjaggi@google.com>
Date: Tue, 16 May 2017 17:11:18 +0200
Subject: [PATCH] Use ArrayList as children
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

Such that traversal is O(n) instead of O(n²)

Test: WindowContainerTests
Bug: 32668632
Change-Id: Ie52026a76a0f65c71ff6bd35d13b3d0c5d44bb3f
---
 .../com/android/server/wm/WindowContainer.java     | 18 +++++-----
 .../java/com/android/server/wm/WindowList.java     | 38 ++++++++++++++++++++++
 .../src/com/android/server/wm/WindowTestUtils.java |  4 +--
 3 files changed, 49 insertions(+), 11 deletions(-)
 create mode 100644 services/core/java/com/android/server/wm/WindowList.java

diff --git a/services/core/java/com/android/server/wm/WindowContainer.java b/services/core/java/com/android/server/wm/WindowContainer.java
index 84ba139ee5a9..ca8c48440d0e 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.LinkedList;
 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 @@ class WindowContainer<E extends WindowContainer> implements Comparable<WindowCon
 
     // 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 @@ class WindowContainer<E extends WindowContainer> implements Comparable<WindowCon
             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 @@ class WindowContainer<E extends WindowContainer> implements Comparable<WindowCon
         }
 
         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 @@ class WindowContainer<E extends WindowContainer> implements Comparable<WindowCon
 
         // 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 000000000000..dfeba40fa45e
--- /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 d9349ed56132..b83532cfa831 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 @@ public class WindowTestUtils {
         }
 
         WindowState getFirstChild() {
-            return mChildren.getFirst();
+            return mChildren.peekFirst();
         }
 
         WindowState getLastChild() {
-            return mChildren.getLast();
+            return mChildren.peekLast();
         }
 
         int positionInParent() {
-- 
2.11.0