Use std::deque for EventEntry queues

Remove custom queue implementation from InputDispatcher. This will help
with refactoring some of the manual memory management that is going on
there, which will in turn help understand object lifecycles better. This
will in turn help add some of the focus handling stuff.

Bug: 70668286
Test: SANITIZE_TARGET=hwaddress atest libinput_tests inputflinger_tests
Change-Id: Ifd10b7b137e59569c148c79609ca43a59acb0781

2 files changed, 47 insertions, 122 deletions

diff --git a/services/inputflinger/InputDispatcher.cpp b/services/inputflinger/InputDispatcher.cpp
index 32cb04eaed..656793a9ca 100644
--- a/services/inputflinger/InputDispatcher.cpp
+++ b/services/inputflinger/InputDispatcher.cpp
@@ -48,10 +48,11 @@
 #include <errno.h>
 #include <inttypes.h>
 #include <limits.h>
-#include <sstream>
 #include <stddef.h>
 #include <time.h>
 #include <unistd.h>
+#include <queue>
+#include <sstream>
 
 #include <android-base/chrono_utils.h>
 #include <android-base/stringprintf.h>
@@ -358,7 +359,7 @@ void InputDispatcher::dispatchOnceInnerLocked(nsecs_t* nextWakeupTime) {
     // Ready to start a new event.
     // If we don't already have a pending event, go grab one.
     if (! mPendingEvent) {
-        if (mInboundQueue.isEmpty()) {
+        if (mInboundQueue.empty()) {
             if (isAppSwitchDue) {
                 // The inbound queue is empty so the app switch key we were waiting
                 // for will never arrive.  Stop waiting for it.
@@ -383,7 +384,8 @@ void InputDispatcher::dispatchOnceInnerLocked(nsecs_t* nextWakeupTime) {
             }
         } else {
             // Inbound queue has at least one entry.
-            mPendingEvent = mInboundQueue.dequeueAtHead();
+            mPendingEvent = mInboundQueue.front();
+            mInboundQueue.pop_front();
             traceInboundQueueLengthLocked();
         }
 
@@ -483,8 +485,8 @@ void InputDispatcher::dispatchOnceInnerLocked(nsecs_t* nextWakeupTime) {
 }
 
 bool InputDispatcher::enqueueInboundEventLocked(EventEntry* entry) {
-    bool needWake = mInboundQueue.isEmpty();
-    mInboundQueue.enqueueAtTail(entry);
+    bool needWake = mInboundQueue.empty();
+    mInboundQueue.push_back(entry);
     traceInboundQueueLengthLocked();
 
     switch (entry->type) {
@@ -544,9 +546,10 @@ bool InputDispatcher::enqueueInboundEventLocked(EventEntry* entry) {
 
 void InputDispatcher::addRecentEventLocked(EventEntry* entry) {
     entry->refCount += 1;
-    mRecentQueue.enqueueAtTail(entry);
-    if (mRecentQueue.count() > RECENT_QUEUE_MAX_SIZE) {
-        mRecentQueue.dequeueAtHead()->release();
+    mRecentQueue.push_back(entry);
+    if (mRecentQueue.size() > RECENT_QUEUE_MAX_SIZE) {
+        mRecentQueue.front()->release();
+        mRecentQueue.pop_front();
     }
 }
 
@@ -703,35 +706,36 @@ bool InputDispatcher::isStaleEvent(nsecs_t currentTime, EventEntry* entry) {
 }
 
 bool InputDispatcher::haveCommandsLocked() const {
-    return !mCommandQueue.isEmpty();
+    return !mCommandQueue.empty();
 }
 
 bool InputDispatcher::runCommandsLockedInterruptible() {
-    if (mCommandQueue.isEmpty()) {
+    if (mCommandQueue.empty()) {
         return false;
     }
 
     do {
-        CommandEntry* commandEntry = mCommandQueue.dequeueAtHead();
-
+        CommandEntry* commandEntry = mCommandQueue.front();
+        mCommandQueue.pop_front();
         Command command = commandEntry->command;
         command(*this, commandEntry); // commands are implicitly 'LockedInterruptible'
 
         commandEntry->connection.clear();
         delete commandEntry;
-    } while (! mCommandQueue.isEmpty());
+    } while (!mCommandQueue.empty());
     return true;
 }
 
 InputDispatcher::CommandEntry* InputDispatcher::postCommandLocked(Command command) {
     CommandEntry* commandEntry = new CommandEntry(command);
-    mCommandQueue.enqueueAtTail(commandEntry);
+    mCommandQueue.push_back(commandEntry);
     return commandEntry;
 }
 
 void InputDispatcher::drainInboundQueueLocked() {
-    while (! mInboundQueue.isEmpty()) {
-        EventEntry* entry = mInboundQueue.dequeueAtHead();
+    while (!mInboundQueue.empty()) {
+        EventEntry* entry = mInboundQueue.front();
+        mInboundQueue.pop_front();
         releaseInboundEventLocked(entry);
     }
     traceInboundQueueLengthLocked();
@@ -2915,8 +2919,7 @@ int32_t InputDispatcher::injectInputEvent(const InputEvent* event,
         policyFlags |= POLICY_FLAG_TRUSTED;
     }
 
-    EventEntry* firstInjectedEntry;
-    EventEntry* lastInjectedEntry;
+    std::queue<EventEntry*> injectedEntries;
     switch (event->getType()) {
     case AINPUT_EVENT_TYPE_KEY: {
         KeyEvent keyEvent;
@@ -2949,12 +2952,13 @@ int32_t InputDispatcher::injectInputEvent(const InputEvent* event,
         }
 
         mLock.lock();
-        firstInjectedEntry = new KeyEntry(SYNTHESIZED_EVENT_SEQUENCE_NUM, keyEvent.getEventTime(),
-                keyEvent.getDeviceId(), keyEvent.getSource(), keyEvent.getDisplayId(),
-                policyFlags, action, flags,
-                keyEvent.getKeyCode(), keyEvent.getScanCode(), keyEvent.getMetaState(),
-                keyEvent.getRepeatCount(), keyEvent.getDownTime());
-        lastInjectedEntry = firstInjectedEntry;
+        KeyEntry* injectedEntry =
+                new KeyEntry(SYNTHESIZED_EVENT_SEQUENCE_NUM, keyEvent.getEventTime(),
+                             keyEvent.getDeviceId(), keyEvent.getSource(), keyEvent.getDisplayId(),
+                             policyFlags, action, flags, keyEvent.getKeyCode(),
+                             keyEvent.getScanCode(), keyEvent.getMetaState(),
+                             keyEvent.getRepeatCount(), keyEvent.getDownTime());
+        injectedEntries.push(injectedEntry);
         break;
     }
 
@@ -2982,7 +2986,7 @@ int32_t InputDispatcher::injectInputEvent(const InputEvent* event,
         mLock.lock();
         const nsecs_t* sampleEventTimes = motionEvent->getSampleEventTimes();
         const PointerCoords* samplePointerCoords = motionEvent->getSamplePointerCoords();
-        firstInjectedEntry =
+        MotionEntry* injectedEntry =
                 new MotionEntry(SYNTHESIZED_EVENT_SEQUENCE_NUM, *sampleEventTimes,
                                 motionEvent->getDeviceId(), motionEvent->getSource(),
                                 motionEvent->getDisplayId(), policyFlags, action, actionButton,
@@ -2993,7 +2997,7 @@ int32_t InputDispatcher::injectInputEvent(const InputEvent* event,
                                 motionEvent->getRawYCursorPosition(), motionEvent->getDownTime(),
                                 uint32_t(pointerCount), pointerProperties, samplePointerCoords,
                                 motionEvent->getXOffset(), motionEvent->getYOffset());
-        lastInjectedEntry = firstInjectedEntry;
+        injectedEntries.push(injectedEntry);
         for (size_t i = motionEvent->getHistorySize(); i > 0; i--) {
             sampleEventTimes += 1;
             samplePointerCoords += pointerCount;
@@ -3010,8 +3014,7 @@ int32_t InputDispatcher::injectInputEvent(const InputEvent* event,
                                     motionEvent->getDownTime(), uint32_t(pointerCount),
                                     pointerProperties, samplePointerCoords,
                                     motionEvent->getXOffset(), motionEvent->getYOffset());
-            lastInjectedEntry->next = nextInjectedEntry;
-            lastInjectedEntry = nextInjectedEntry;
+            injectedEntries.push(nextInjectedEntry);
         }
         break;
     }
@@ -3027,13 +3030,12 @@ int32_t InputDispatcher::injectInputEvent(const InputEvent* event,
     }
 
     injectionState->refCount += 1;
-    lastInjectedEntry->injectionState = injectionState;
+    injectedEntries.back()->injectionState = injectionState;
 
     bool needWake = false;
-    for (EventEntry* entry = firstInjectedEntry; entry != nullptr; ) {
-        EventEntry* nextEntry = entry->next;
-        needWake |= enqueueInboundEventLocked(entry);
-        entry = nextEntry;
+    while (!injectedEntries.empty()) {
+        needWake |= enqueueInboundEventLocked(injectedEntries.front());
+        injectedEntries.pop();
     }
 
     mLock.unlock();
@@ -3764,9 +3766,9 @@ void InputDispatcher::dumpDispatchStateLocked(std::string& dump) {
     nsecs_t currentTime = now();
 
     // Dump recently dispatched or dropped events from oldest to newest.
-    if (!mRecentQueue.isEmpty()) {
-        dump += StringPrintf(INDENT "RecentQueue: length=%u\n", mRecentQueue.count());
-        for (EventEntry* entry = mRecentQueue.head; entry; entry = entry->next) {
+    if (!mRecentQueue.empty()) {
+        dump += StringPrintf(INDENT "RecentQueue: length=%zu\n", mRecentQueue.size());
+        for (EventEntry* entry : mRecentQueue) {
             dump += INDENT2;
             entry->appendDescription(dump);
             dump += StringPrintf(", age=%0.1fms\n",
@@ -3788,9 +3790,9 @@ void InputDispatcher::dumpDispatchStateLocked(std::string& dump) {
     }
 
     // Dump inbound events from oldest to newest.
-    if (!mInboundQueue.isEmpty()) {
-        dump += StringPrintf(INDENT "InboundQueue: length=%u\n", mInboundQueue.count());
-        for (EventEntry* entry = mInboundQueue.head; entry; entry = entry->next) {
+    if (!mInboundQueue.empty()) {
+        dump += StringPrintf(INDENT "InboundQueue: length=%zu\n", mInboundQueue.size());
+        for (EventEntry* entry : mInboundQueue) {
             dump += INDENT2;
             entry->appendDescription(dump);
             dump += StringPrintf(", age=%0.1fms\n",
@@ -4506,7 +4508,7 @@ void InputDispatcher::updateDispatchStatistics(nsecs_t currentTime, const EventE
 
 void InputDispatcher::traceInboundQueueLengthLocked() {
     if (ATRACE_ENABLED()) {
-        ATRACE_INT("iq", mInboundQueue.count());
+        ATRACE_INT("iq", mInboundQueue.size());
     }
 }
 
diff --git a/services/inputflinger/InputDispatcher.h b/services/inputflinger/InputDispatcher.h
index d73c4d6dd7..b6c0797045 100644
--- a/services/inputflinger/InputDispatcher.h
+++ b/services/inputflinger/InputDispatcher.h
@@ -451,14 +451,6 @@ public:
     virtual status_t pilferPointers(const sp<IBinder>& token) override;
 
 private:
-    template <typename T>
-    struct Link {
-        T* next;
-        T* prev;
-
-    protected:
-        inline Link() : next(nullptr), prev(nullptr) { }
-    };
 
     struct InjectionState {
         mutable int32_t refCount;
@@ -476,7 +468,7 @@ private:
         ~InjectionState();
     };
 
-    struct EventEntry : Link<EventEntry> {
+    struct EventEntry {
         enum {
             TYPE_CONFIGURATION_CHANGED,
             TYPE_DEVICE_RESET,
@@ -648,7 +640,7 @@ private:
     typedef std::function<void(InputDispatcher&, CommandEntry*)> Command;
 
     class Connection;
-    struct CommandEntry : Link<CommandEntry> {
+    struct CommandEntry {
         explicit CommandEntry(Command command);
         ~CommandEntry();
 
@@ -668,75 +660,6 @@ private:
         sp<IBinder> newToken;
     };
 
-    // Generic queue implementation.
-    template <typename T>
-    struct Queue {
-        T* head;
-        T* tail;
-        uint32_t entryCount;
-
-        inline Queue() : head(nullptr), tail(nullptr), entryCount(0) {
-        }
-
-        inline bool isEmpty() const {
-            return !head;
-        }
-
-        inline void enqueueAtTail(T* entry) {
-            entryCount++;
-            entry->prev = tail;
-            if (tail) {
-                tail->next = entry;
-            } else {
-                head = entry;
-            }
-            entry->next = nullptr;
-            tail = entry;
-        }
-
-        inline void enqueueAtHead(T* entry) {
-            entryCount++;
-            entry->next = head;
-            if (head) {
-                head->prev = entry;
-            } else {
-                tail = entry;
-            }
-            entry->prev = nullptr;
-            head = entry;
-        }
-
-        inline void dequeue(T* entry) {
-            entryCount--;
-            if (entry->prev) {
-                entry->prev->next = entry->next;
-            } else {
-                head = entry->next;
-            }
-            if (entry->next) {
-                entry->next->prev = entry->prev;
-            } else {
-                tail = entry->prev;
-            }
-        }
-
-        inline T* dequeueAtHead() {
-            entryCount--;
-            T* entry = head;
-            head = entry->next;
-            if (head) {
-                head->prev = nullptr;
-            } else {
-                tail = nullptr;
-            }
-            return entry;
-        }
-
-        uint32_t count() const {
-            return entryCount;
-        }
-    };
-
     /* Specifies which events are to be canceled and why. */
     struct CancelationOptions {
         enum Mode {
@@ -928,9 +851,9 @@ private:
     sp<Looper> mLooper;
 
     EventEntry* mPendingEvent GUARDED_BY(mLock);
-    Queue<EventEntry> mInboundQueue GUARDED_BY(mLock);
-    Queue<EventEntry> mRecentQueue GUARDED_BY(mLock);
-    Queue<CommandEntry> mCommandQueue GUARDED_BY(mLock);
+    std::deque<EventEntry*> mInboundQueue GUARDED_BY(mLock);
+    std::deque<EventEntry*> mRecentQueue GUARDED_BY(mLock);
+    std::deque<CommandEntry*> mCommandQueue GUARDED_BY(mLock);
 
     DropReason mLastDropReason GUARDED_BY(mLock);