Native input dispatch rewrite work in progress.

The old dispatch mechanism has been left in place and continues to
be used by default for now.  To enable native input dispatch,
edit the ENABLE_NATIVE_DISPATCH constant in WindowManagerPolicy.

Includes part of the new input event NDK API.  Some details TBD.

To wire up input dispatch, as the ViewRoot adds a window to the
window session it receives an InputChannel object as an output
argument.  The InputChannel encapsulates the file descriptors for a
shared memory region and two pipe end-points.  The ViewRoot then
provides the InputChannel to the InputQueue.  Behind the
scenes, InputQueue simply attaches handlers to the native PollLoop object
that underlies the MessageQueue.  This way MessageQueue doesn't need
to know anything about input dispatch per-se, it just exposes (in native
code) a PollLoop that other components can use to monitor file descriptor
state changes.

There can be zero or more targets for any given input event.  Each
input target is specified by its input channel and some parameters
including flags, an X/Y coordinate offset, and the dispatch timeout.
An input target can request either synchronous dispatch (for foreground apps)
or asynchronous dispatch (fire-and-forget for wallpapers and "outside"
targets).  Currently, finding the appropriate input targets for an event
requires a call back into the WindowManagerServer from native code.
In the future this will be refactored to avoid most of these callbacks
except as required to handle pending focus transitions.

End-to-end event dispatch mostly works!

To do: event injection, rate limiting, ANRs, testing, optimization, etc.

Change-Id: I8c36b2b9e0a2d27392040ecda0f51b636456de25

7 files changed, 296 insertions, 108 deletions

diff --git a/include/utils/BitSet.h b/include/utils/BitSet.h
new file mode 100644
index 0000000..19c8bf0
--- /dev/null
+++ b/include/utils/BitSet.h
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2010 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.
+ */
+
+#ifndef UTILS_BITSET_H
+#define UTILS_BITSET_H
+
+#include <stdint.h>
+
+/*
+ * Contains some bit manipulation helpers.
+ */
+
+namespace android {
+
+// A simple set of 32 bits that can be individually marked or cleared.
+struct BitSet32 {
+    uint32_t value;
+
+    inline BitSet32() : value(0) { }
+    explicit inline BitSet32(uint32_t value) : value(value) { }
+
+    // Gets the value associated with a particular bit index.
+    static inline uint32_t valueForBit(uint32_t n) { return 0x80000000 >> n; }
+
+    // Clears the bit set.
+    inline void clear() { value = 0; }
+
+    // Returns true if the bit set does not contain any marked bits.
+    inline bool isEmpty() const { return ! value; }
+
+    // Returns true if the specified bit is marked.
+    inline bool hasBit(uint32_t n) const { return value & valueForBit(n); }
+
+    // Marks the specified bit.
+    inline void markBit(uint32_t n) { value |= valueForBit(n); }
+
+    // Clears the specified bit.
+    inline void clearBit(uint32_t n) { value &= ~ valueForBit(n); }
+
+    // Finds the first marked bit in the set.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t firstMarkedBit() const { return __builtin_clz(value); }
+
+    // Finds the first unmarked bit in the set.
+    // Result is undefined if all bits are marked.
+    inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); }
+
+    inline bool operator== (const BitSet32& other) const { return value == other.value; }
+    inline bool operator!= (const BitSet32& other) const { return value != other.value; }
+};
+
+} // namespace android
+
+#endif // UTILS_BITSET_H
diff --git a/include/utils/Buffer.h b/include/utils/Buffer.h
deleted file mode 100644
index 8e22b0f..0000000
--- a/include/utils/Buffer.h
+++ /dev/null
@@ -1,107 +0,0 @@
-/*
- * Copyright (C) 2008 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.
- */
-
-#ifndef __UTILS_BUFFER_H__
-#define __UTILS_BUFFER_H__ 1
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-namespace android {
-
-class Buffer
-{
-private:
-    char *buf;
-    int bufsiz;
-    int used;
-    void ensureCapacity(int len);
-
-    void
-    makeRoomFor(int len)
-    {
-        if (len + used >= bufsiz) {
-            bufsiz = (len + used) * 3/2 + 2;
-            char *blah = new char[bufsiz];
-
-            memcpy(blah, buf, used);
-            delete[] buf;
-            buf = blah;
-        }
-    }
-    
-public:
-    Buffer()
-    {
-        bufsiz = 16;
-        buf = new char[bufsiz];
-        clear();
-    }
-
-    ~Buffer()
-    {
-       delete[] buf;
-    }
-
-    void
-    clear()
-    {
-        buf[0] = '\0';
-        used = 0;
-    }
-
-    int
-    length()
-    {
-        return used;
-    }
-
-    void
-    append(const char c)
-    {
-        makeRoomFor(1);
-        buf[used] = c;
-        used++;
-        buf[used] = '\0';
-    }
-
-    void
-    append(const char *s, int len)
-    {
-        makeRoomFor(len);
-
-        memcpy(buf + used, s, len);
-        used += len;
-        buf[used] = '\0';
-    }
-
-    void
-    append(const char *s)
-    {
-        append(s, strlen(s));
-    }
-
-    char *
-    getBytes()
-    {
-        return buf;
-    }
-};
-
-}; // namespace android
-
-#endif
diff --git a/include/utils/PollLoop.h b/include/utils/PollLoop.h
new file mode 100644
index 0000000..2ec39fe
--- /dev/null
+++ b/include/utils/PollLoop.h
@@ -0,0 +1,137 @@
+/*
+ * Copyright (C) 2010 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.
+ */
+
+#ifndef UTILS_POLL_LOOP_H
+#define UTILS_POLL_LOOP_H
+
+#include <utils/Vector.h>
+#include <utils/threads.h>
+
+#include <poll.h>
+
+namespace android {
+
+/**
+ * A basic file descriptor polling loop based on poll() with callbacks.
+ */
+class PollLoop : public RefBase {
+protected:
+    virtual ~PollLoop();
+
+public:
+    PollLoop();
+
+    /**
+     * A callback that it to be invoked when an event occurs on a file descriptor.
+     * Specifies the events that were triggered and the user data provided when the
+     * callback was set.
+     *
+     * Returns true if the callback should be kept, false if it should be removed automatically
+     * after the callback returns.
+     */
+    typedef bool (*Callback)(int fd, int events, void* data);
+
+    /**
+     * Performs a single call to poll() with optional timeout in milliseconds.
+     * Invokes callbacks for all file descriptors on which an event occurred.
+     *
+     * If the timeout is zero, returns immediately without blocking.
+     * If the timeout is negative, waits indefinitely until awoken.
+     *
+     * Returns true if a callback was invoked or if the loop was awoken by wake().
+     * Returns false if a timeout or error occurred.
+     *
+     * This method must only be called on the main thread.
+     * This method blocks until either a file descriptor is signalled, a timeout occurs,
+     * or wake() is called.
+     * This method does not return until it has finished invoking the appropriate callbacks
+     * for all file descriptors that were signalled.
+     */
+    bool pollOnce(int timeoutMillis);
+
+    /**
+     * Wakes the loop asynchronously.
+     *
+     * This method can be called on any thread.
+     * This method returns immediately.
+     */
+    void wake();
+
+    /**
+     * Sets the callback for a file descriptor, replacing the existing one, if any.
+     * It is an error to call this method with events == 0 or callback == NULL.
+     *
+     * Note that a callback can be invoked with the POLLERR, POLLHUP or POLLNVAL events
+     * even if it is not explicitly requested when registered.
+     *
+     * This method can be called on any thread.
+     * This method may block briefly if it needs to wake the poll loop.
+     */
+    void setCallback(int fd, int events, Callback callback, void* data = NULL);
+
+    /**
+     * Removes the callback for a file descriptor, if one exists.
+     *
+     * When this method returns, it is safe to close the file descriptor since the poll loop
+     * will no longer have a reference to it.  However, it is possible for the callback to
+     * already be running or for it to run one last time if the file descriptor was already
+     * signalled.  Calling code is responsible for ensuring that this case is safely handled.
+     * For example, if the callback takes care of removing itself during its own execution either
+     * by returning false or calling this method, then it can be guaranteed to not be invoked
+     * again at any later time unless registered anew.
+     *
+     * This method can be called on any thread.
+     * This method may block briefly if it needs to wake the poll loop.
+     *
+     * Returns true if a callback was actually removed, false if none was registered.
+     */
+    bool removeCallback(int fd);
+
+private:
+    struct RequestedCallback {
+        Callback callback;
+        void* data;
+    };
+
+    struct PendingCallback {
+        int fd;
+        int events;
+        Callback callback;
+        void* data;
+    };
+
+    Mutex mLock;
+    Condition mAwake;
+    bool mPolling;
+
+    int mWakeReadPipeFd;
+    int mWakeWritePipeFd;
+
+    Vector<struct pollfd> mRequestedFds;
+    Vector<RequestedCallback> mRequestedCallbacks;
+
+    Vector<PendingCallback> mPendingCallbacks; // used privately by pollOnce
+
+    void openWakePipe();
+    void closeWakePipe();
+
+    ssize_t getRequestIndexLocked(int fd);
+    void wakeAndLock();
+};
+
+} // namespace android
+
+#endif // UTILS_POLL_LOOP_H
diff --git a/include/utils/Pool.h b/include/utils/Pool.h
new file mode 100644
index 0000000..2ee768e
--- /dev/null
+++ b/include/utils/Pool.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2010 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.
+ */
+
+#ifndef UTILS_POOL_H
+#define UTILS_POOL_H
+
+#include <utils/TypeHelpers.h>
+
+namespace android {
+
+class PoolImpl {
+public:
+    PoolImpl(size_t objSize);
+    ~PoolImpl();
+
+    void* allocImpl();
+    void freeImpl(void* obj);
+
+private:
+    size_t mObjSize;
+};
+
+/*
+ * A homogeneous typed memory pool for fixed size objects.
+ * Not intended to be thread-safe.
+ */
+template<typename T>
+class Pool : private PoolImpl {
+public:
+    /* Creates an initially empty pool. */
+    Pool() : PoolImpl(sizeof(T)) { }
+
+    /* Destroys the pool.
+     * Assumes that the pool is empty. */
+    ~Pool() { }
+
+    /* Allocates an object from the pool, growing the pool if needed. */
+    inline T* alloc() {
+        void* mem = allocImpl();
+        if (! traits<T>::has_trivial_ctor) {
+            return new (mem) T();
+        } else {
+            return static_cast<T*>(mem);
+        }
+    }
+
+    /* Frees an object from the pool. */
+    inline void free(T* obj) {
+        if (! traits<T>::has_trivial_dtor) {
+            obj->~T();
+        }
+        freeImpl(obj);
+    }
+};
+
+} // namespace android
+
+#endif // UTILS_POOL_H
diff --git a/include/utils/StopWatch.h b/include/utils/StopWatch.h
index cc0bebc..693dd3c 100644
--- a/include/utils/StopWatch.h
+++ b/include/utils/StopWatch.h
@@ -37,6 +37,8 @@ public:
         const char* name() const;
         nsecs_t     lap();
         nsecs_t     elapsedTime() const;
+
+        void        reset();
         
 private:
     const char*     mName;
diff --git a/include/utils/Vector.h b/include/utils/Vector.h
index ad59fd6..d40ae16 100644
--- a/include/utils/Vector.h
+++ b/include/utils/Vector.h
@@ -114,6 +114,12 @@ public:
             ssize_t         appendVector(const Vector<TYPE>& vector);
 
 
+    //! insert an array at a given index
+            ssize_t         insertArrayAt(const TYPE* array, size_t index, size_t numItems);
+
+    //! append an array at the end of this vector
+            ssize_t         appendArray(const TYPE* array, size_t numItems);
+
             /*! 
              * add/insert/replace items
              */
@@ -259,6 +265,16 @@ ssize_t Vector<TYPE>::appendVector(const Vector<TYPE>& vector) {
 }
 
 template<class TYPE> inline
+ssize_t Vector<TYPE>::insertArrayAt(const TYPE* array, size_t index, size_t numItems) {
+    return VectorImpl::insertAt(array, index, numItems);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::appendArray(const TYPE* array, size_t numItems) {
+    return VectorImpl::add(array, numItems);
+}
+
+template<class TYPE> inline
 ssize_t Vector<TYPE>::insertAt(const TYPE& item, size_t index, size_t numItems) {
     return VectorImpl::insertAt(&item, index, numItems);
 }
diff --git a/include/utils/VectorImpl.h b/include/utils/VectorImpl.h
index 49b03f1..46a7bc2 100644
--- a/include/utils/VectorImpl.h
+++ b/include/utils/VectorImpl.h
@@ -76,7 +76,7 @@ public:
             void            push();
             void            push(const void* item);
             ssize_t         add();
-            ssize_t         add(const void* item);
+            ssize_t         add(const void* item, size_t numItems = 1);
             ssize_t         replaceAt(size_t index);
             ssize_t         replaceAt(const void* item, size_t index);
 
@@ -184,6 +184,8 @@ private:
             void            push(const void* item);
             ssize_t         insertVectorAt(const VectorImpl& vector, size_t index);
             ssize_t         appendVector(const VectorImpl& vector);
+            ssize_t         insertArrayAt(const void* array, size_t index, size_t numItems);
+            ssize_t         appendArray(const void* array, size_t numItems);
             ssize_t         insertAt(size_t where, size_t numItems = 1);
             ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
             ssize_t         replaceAt(size_t index);