Merge "Exporting C++ headers from system/core" am: 812b7d5d52 am: f484dd3401 am: a252f11da3

am: 5a8f555e49

Change-Id: Id449aadc3b9e6e263d351ce031b1f7f7bb4672b8

47 files changed, 7654 insertions, 0 deletions

diff --git a/libutils/include/utils/AndroidThreads.h b/libutils/include/utils/AndroidThreads.h
new file mode 100644
index 000000000..4c2dd49f6
--- /dev/null
+++ b/libutils/include/utils/AndroidThreads.h
@@ -0,0 +1,125 @@
+/*
+ * Copyright (C) 2007 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 _LIBS_UTILS_ANDROID_THREADS_H
+#define _LIBS_UTILS_ANDROID_THREADS_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+#if !defined(_WIN32)
+# include <pthread.h>
+#endif
+
+#include <utils/ThreadDefs.h>
+
+// ---------------------------------------------------------------------------
+// C API
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// Create and run a new thread.
+extern int androidCreateThread(android_thread_func_t, void *);
+
+// Create thread with lots of parameters
+extern int androidCreateThreadEtc(android_thread_func_t entryFunction,
+                                  void *userData,
+                                  const char* threadName,
+                                  int32_t threadPriority,
+                                  size_t threadStackSize,
+                                  android_thread_id_t *threadId);
+
+// Get some sort of unique identifier for the current thread.
+extern android_thread_id_t androidGetThreadId();
+
+// Low-level thread creation -- never creates threads that can
+// interact with the Java VM.
+extern int androidCreateRawThreadEtc(android_thread_func_t entryFunction,
+                                     void *userData,
+                                     const char* threadName,
+                                     int32_t threadPriority,
+                                     size_t threadStackSize,
+                                     android_thread_id_t *threadId);
+
+// set the same of the running thread
+extern void androidSetThreadName(const char* name);
+
+// Used by the Java Runtime to control how threads are created, so that
+// they can be proper and lovely Java threads.
+typedef int (*android_create_thread_fn)(android_thread_func_t entryFunction,
+                                        void *userData,
+                                        const char* threadName,
+                                        int32_t threadPriority,
+                                        size_t threadStackSize,
+                                        android_thread_id_t *threadId);
+
+extern void androidSetCreateThreadFunc(android_create_thread_fn func);
+
+// ------------------------------------------------------------------
+// Extra functions working with raw pids.
+
+#if defined(__ANDROID__)
+// Change the priority AND scheduling group of a particular thread.  The priority
+// should be one of the ANDROID_PRIORITY constants.  Returns INVALID_OPERATION
+// if the priority set failed, else another value if just the group set failed;
+// in either case errno is set.  Thread ID zero means current thread.
+extern int androidSetThreadPriority(pid_t tid, int prio);
+
+// Get the current priority of a particular thread. Returns one of the
+// ANDROID_PRIORITY constants or a negative result in case of error.
+extern int androidGetThreadPriority(pid_t tid);
+#endif
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+// ----------------------------------------------------------------------------
+// C++ API
+#ifdef __cplusplus
+namespace android {
+// ----------------------------------------------------------------------------
+
+// Create and run a new thread.
+inline bool createThread(thread_func_t f, void *a) {
+    return androidCreateThread(f, a) ? true : false;
+}
+
+// Create thread with lots of parameters
+inline bool createThreadEtc(thread_func_t entryFunction,
+                            void *userData,
+                            const char* threadName = "android:unnamed_thread",
+                            int32_t threadPriority = PRIORITY_DEFAULT,
+                            size_t threadStackSize = 0,
+                            thread_id_t *threadId = 0)
+{
+    return androidCreateThreadEtc(entryFunction, userData, threadName,
+        threadPriority, threadStackSize, threadId) ? true : false;
+}
+
+// Get some sort of unique identifier for the current thread.
+inline thread_id_t getThreadId() {
+    return androidGetThreadId();
+}
+
+// ----------------------------------------------------------------------------
+}; // namespace android
+#endif  // __cplusplus
+// ----------------------------------------------------------------------------
+
+#endif // _LIBS_UTILS_ANDROID_THREADS_H
diff --git a/libutils/include/utils/Atomic.h b/libutils/include/utils/Atomic.h
new file mode 100644
index 000000000..7eb476c94
--- /dev/null
+++ b/libutils/include/utils/Atomic.h
@@ -0,0 +1,22 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_UTILS_ATOMIC_H
+#define ANDROID_UTILS_ATOMIC_H
+
+#include <cutils/atomic.h>
+
+#endif // ANDROID_UTILS_ATOMIC_H
diff --git a/libutils/include/utils/BitSet.h b/libutils/include/utils/BitSet.h
new file mode 100644
index 000000000..8c612931d
--- /dev/null
+++ b/libutils/include/utils/BitSet.h
@@ -0,0 +1,294 @@
+/*
+ * 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>
+#include <utils/TypeHelpers.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(0UL) { }
+    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 0x80000000UL >> n; }
+
+    // Clears the bit set.
+    inline void clear() { clear(value); }
+
+    static inline void clear(uint32_t& value) { value = 0UL; }
+
+    // Returns the number of marked bits in the set.
+    inline uint32_t count() const { return count(value); }
+
+    static inline uint32_t count(uint32_t value) { return __builtin_popcountl(value); }
+
+    // Returns true if the bit set does not contain any marked bits.
+    inline bool isEmpty() const { return isEmpty(value); }
+
+    static inline bool isEmpty(uint32_t value) { return ! value; }
+
+    // Returns true if the bit set does not contain any unmarked bits.
+    inline bool isFull() const { return isFull(value); }
+
+    static inline bool isFull(uint32_t value) { return value == 0xffffffffUL; }
+
+    // Returns true if the specified bit is marked.
+    inline bool hasBit(uint32_t n) const { return hasBit(value, n); }
+
+    static inline bool hasBit(uint32_t value, uint32_t n) { return value & valueForBit(n); }
+
+    // Marks the specified bit.
+    inline void markBit(uint32_t n) { markBit(value, n); }
+
+    static inline void markBit (uint32_t& value, uint32_t n) { value |= valueForBit(n); }
+
+    // Clears the specified bit.
+    inline void clearBit(uint32_t n) { clearBit(value, n); }
+
+    static inline void clearBit(uint32_t& value, 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 firstMarkedBit(value); }
+
+    static uint32_t firstMarkedBit(uint32_t value) { return clz_checked(value); }
+
+    // Finds the first unmarked bit in the set.
+    // Result is undefined if all bits are marked.
+    inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); }
+
+    static inline uint32_t firstUnmarkedBit(uint32_t value) { return clz_checked(~ value); }
+
+    // Finds the last marked bit in the set.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); }
+
+    static inline uint32_t lastMarkedBit(uint32_t value) { return 31 - ctz_checked(value); }
+
+    // Finds the first marked bit in the set and clears it.  Returns the bit index.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); }
+
+    static inline uint32_t clearFirstMarkedBit(uint32_t& value) {
+        uint32_t n = firstMarkedBit(value);
+        clearBit(value, n);
+        return n;
+    }
+
+    // Finds the first unmarked bit in the set and marks it.  Returns the bit index.
+    // Result is undefined if all bits are marked.
+    inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); }
+
+    static inline uint32_t markFirstUnmarkedBit(uint32_t& value) {
+        uint32_t n = firstUnmarkedBit(value);
+        markBit(value, n);
+        return n;
+    }
+
+    // Finds the last marked bit in the set and clears it.  Returns the bit index.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); }
+
+    static inline uint32_t clearLastMarkedBit(uint32_t& value) {
+        uint32_t n = lastMarkedBit(value);
+        clearBit(value, n);
+        return n;
+    }
+
+    // Gets the index of the specified bit in the set, which is the number of
+    // marked bits that appear before the specified bit.
+    inline uint32_t getIndexOfBit(uint32_t n) const {
+        return getIndexOfBit(value, n);
+    }
+
+    static inline uint32_t getIndexOfBit(uint32_t value, uint32_t n) {
+        return __builtin_popcountl(value & ~(0xffffffffUL >> n));
+    }
+
+    inline bool operator== (const BitSet32& other) const { return value == other.value; }
+    inline bool operator!= (const BitSet32& other) const { return value != other.value; }
+    inline BitSet32 operator& (const BitSet32& other) const {
+        return BitSet32(value & other.value);
+    }
+    inline BitSet32& operator&= (const BitSet32& other) {
+        value &= other.value;
+        return *this;
+    }
+    inline BitSet32 operator| (const BitSet32& other) const {
+        return BitSet32(value | other.value);
+    }
+    inline BitSet32& operator|= (const BitSet32& other) {
+        value |= other.value;
+        return *this;
+    }
+
+private:
+    // We use these helpers as the signature of __builtin_c{l,t}z has "unsigned int" for the
+    // input, which is only guaranteed to be 16b, not 32. The compiler should optimize this away.
+    static inline uint32_t clz_checked(uint32_t value) {
+        if (sizeof(unsigned int) == sizeof(uint32_t)) {
+            return __builtin_clz(value);
+        } else {
+            return __builtin_clzl(value);
+        }
+    }
+
+    static inline uint32_t ctz_checked(uint32_t value) {
+        if (sizeof(unsigned int) == sizeof(uint32_t)) {
+            return __builtin_ctz(value);
+        } else {
+            return __builtin_ctzl(value);
+        }
+    }
+};
+
+ANDROID_BASIC_TYPES_TRAITS(BitSet32)
+
+// A simple set of 64 bits that can be individually marked or cleared.
+struct BitSet64 {
+    uint64_t value;
+
+    inline BitSet64() : value(0ULL) { }
+    explicit inline BitSet64(uint64_t value) : value(value) { }
+
+    // Gets the value associated with a particular bit index.
+    static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; }
+
+    // Clears the bit set.
+    inline void clear() { clear(value); }
+
+    static inline void clear(uint64_t& value) { value = 0ULL; }
+
+    // Returns the number of marked bits in the set.
+    inline uint32_t count() const { return count(value); }
+
+    static inline uint32_t count(uint64_t value) { return __builtin_popcountll(value); }
+
+    // Returns true if the bit set does not contain any marked bits.
+    inline bool isEmpty() const { return isEmpty(value); }
+
+    static inline bool isEmpty(uint64_t value) { return ! value; }
+
+    // Returns true if the bit set does not contain any unmarked bits.
+    inline bool isFull() const { return isFull(value); }
+
+    static inline bool isFull(uint64_t value) { return value == 0xffffffffffffffffULL; }
+
+    // Returns true if the specified bit is marked.
+    inline bool hasBit(uint32_t n) const { return hasBit(value, n); }
+
+    static inline bool hasBit(uint64_t value, uint32_t n) { return value & valueForBit(n); }
+
+    // Marks the specified bit.
+    inline void markBit(uint32_t n) { markBit(value, n); }
+
+    static inline void markBit(uint64_t& value, uint32_t n) { value |= valueForBit(n); }
+
+    // Clears the specified bit.
+    inline void clearBit(uint32_t n) { clearBit(value, n); }
+
+    static inline void clearBit(uint64_t& value, 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 firstMarkedBit(value); }
+
+    static inline uint32_t firstMarkedBit(uint64_t value) { return __builtin_clzll(value); }
+
+    // Finds the first unmarked bit in the set.
+    // Result is undefined if all bits are marked.
+    inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); }
+
+    static inline uint32_t firstUnmarkedBit(uint64_t value) { return __builtin_clzll(~ value); }
+
+    // Finds the last marked bit in the set.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); }
+
+    static inline uint32_t lastMarkedBit(uint64_t value) { return 63 - __builtin_ctzll(value); }
+
+    // Finds the first marked bit in the set and clears it.  Returns the bit index.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); }
+
+    static inline uint32_t clearFirstMarkedBit(uint64_t& value) {
+        uint64_t n = firstMarkedBit(value);
+        clearBit(value, n);
+        return n;
+    }
+
+    // Finds the first unmarked bit in the set and marks it.  Returns the bit index.
+    // Result is undefined if all bits are marked.
+    inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); }
+
+    static inline uint32_t markFirstUnmarkedBit(uint64_t& value) {
+        uint64_t n = firstUnmarkedBit(value);
+        markBit(value, n);
+        return n;
+    }
+
+    // Finds the last marked bit in the set and clears it.  Returns the bit index.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); }
+
+    static inline uint32_t clearLastMarkedBit(uint64_t& value) {
+        uint64_t n = lastMarkedBit(value);
+        clearBit(value, n);
+        return n;
+    }
+
+    // Gets the index of the specified bit in the set, which is the number of
+    // marked bits that appear before the specified bit.
+    inline uint32_t getIndexOfBit(uint32_t n) const { return getIndexOfBit(value, n); }
+
+    static inline uint32_t getIndexOfBit(uint64_t value, uint32_t n) {
+        return __builtin_popcountll(value & ~(0xffffffffffffffffULL >> n));
+    }
+
+    inline bool operator== (const BitSet64& other) const { return value == other.value; }
+    inline bool operator!= (const BitSet64& other) const { return value != other.value; }
+    inline BitSet64 operator& (const BitSet64& other) const {
+        return BitSet64(value & other.value);
+    }
+    inline BitSet64& operator&= (const BitSet64& other) {
+        value &= other.value;
+        return *this;
+    }
+    inline BitSet64 operator| (const BitSet64& other) const {
+        return BitSet64(value | other.value);
+    }
+    inline BitSet64& operator|= (const BitSet64& other) {
+        value |= other.value;
+        return *this;
+    }
+};
+
+ANDROID_BASIC_TYPES_TRAITS(BitSet64)
+
+} // namespace android
+
+#endif // UTILS_BITSET_H
diff --git a/libutils/include/utils/BlobCache.h b/libutils/include/utils/BlobCache.h
new file mode 100644
index 000000000..65dca9fb4
--- /dev/null
+++ b/libutils/include/utils/BlobCache.h
@@ -0,0 +1,249 @@
+/*
+ ** Copyright 2011, 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 ANDROID_BLOB_CACHE_H
+#define ANDROID_BLOB_CACHE_H
+
+#include <stddef.h>
+
+#include <utils/Flattenable.h>
+#include <utils/RefBase.h>
+#include <utils/SortedVector.h>
+#include <utils/threads.h>
+
+namespace android {
+
+// A BlobCache is an in-memory cache for binary key/value pairs.  A BlobCache
+// does NOT provide any thread-safety guarantees.
+//
+// The cache contents can be serialized to an in-memory buffer or mmap'd file
+// and then reloaded in a subsequent execution of the program.  This
+// serialization is non-portable and the data should only be used by the device
+// that generated it.
+class BlobCache : public RefBase {
+
+public:
+
+    // Create an empty blob cache. The blob cache will cache key/value pairs
+    // with key and value sizes less than or equal to maxKeySize and
+    // maxValueSize, respectively. The total combined size of ALL cache entries
+    // (key sizes plus value sizes) will not exceed maxTotalSize.
+    BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize);
+
+    // set inserts a new binary value into the cache and associates it with the
+    // given binary key.  If the key or value are too large for the cache then
+    // the cache remains unchanged.  This includes the case where a different
+    // value was previously associated with the given key - the old value will
+    // remain in the cache.  If the given key and value are small enough to be
+    // put in the cache (based on the maxKeySize, maxValueSize, and maxTotalSize
+    // values specified to the BlobCache constructor), then the key/value pair
+    // will be in the cache after set returns.  Note, however, that a subsequent
+    // call to set may evict old key/value pairs from the cache.
+    //
+    // Preconditions:
+    //   key != NULL
+    //   0 < keySize
+    //   value != NULL
+    //   0 < valueSize
+    void set(const void* key, size_t keySize, const void* value,
+            size_t valueSize);
+
+    // get retrieves from the cache the binary value associated with a given
+    // binary key.  If the key is present in the cache then the length of the
+    // binary value associated with that key is returned.  If the value argument
+    // is non-NULL and the size of the cached value is less than valueSize bytes
+    // then the cached value is copied into the buffer pointed to by the value
+    // argument.  If the key is not present in the cache then 0 is returned and
+    // the buffer pointed to by the value argument is not modified.
+    //
+    // Note that when calling get multiple times with the same key, the later
+    // calls may fail, returning 0, even if earlier calls succeeded.  The return
+    // value must be checked for each call.
+    //
+    // Preconditions:
+    //   key != NULL
+    //   0 < keySize
+    //   0 <= valueSize
+    size_t get(const void* key, size_t keySize, void* value, size_t valueSize);
+
+
+    // getFlattenedSize returns the number of bytes needed to store the entire
+    // serialized cache.
+    size_t getFlattenedSize() const;
+
+    // flatten serializes the current contents of the cache into the memory
+    // pointed to by 'buffer'.  The serialized cache contents can later be
+    // loaded into a BlobCache object using the unflatten method.  The contents
+    // of the BlobCache object will not be modified.
+    //
+    // Preconditions:
+    //   size >= this.getFlattenedSize()
+    status_t flatten(void* buffer, size_t size) const;
+
+    // unflatten replaces the contents of the cache with the serialized cache
+    // contents in the memory pointed to by 'buffer'.  The previous contents of
+    // the BlobCache will be evicted from the cache.  If an error occurs while
+    // unflattening the serialized cache contents then the BlobCache will be
+    // left in an empty state.
+    //
+    status_t unflatten(void const* buffer, size_t size);
+
+private:
+    // Copying is disallowed.
+    BlobCache(const BlobCache&);
+    void operator=(const BlobCache&);
+
+    // A random function helper to get around MinGW not having nrand48()
+    long int blob_random();
+
+    // clean evicts a randomly chosen set of entries from the cache such that
+    // the total size of all remaining entries is less than mMaxTotalSize/2.
+    void clean();
+
+    // isCleanable returns true if the cache is full enough for the clean method
+    // to have some effect, and false otherwise.
+    bool isCleanable() const;
+
+    // A Blob is an immutable sized unstructured data blob.
+    class Blob : public RefBase {
+    public:
+        Blob(const void* data, size_t size, bool copyData);
+        ~Blob();
+
+        bool operator<(const Blob& rhs) const;
+
+        const void* getData() const;
+        size_t getSize() const;
+
+    private:
+        // Copying is not allowed.
+        Blob(const Blob&);
+        void operator=(const Blob&);
+
+        // mData points to the buffer containing the blob data.
+        const void* mData;
+
+        // mSize is the size of the blob data in bytes.
+        size_t mSize;
+
+        // mOwnsData indicates whether or not this Blob object should free the
+        // memory pointed to by mData when the Blob gets destructed.
+        bool mOwnsData;
+    };
+
+    // A CacheEntry is a single key/value pair in the cache.
+    class CacheEntry {
+    public:
+        CacheEntry();
+        CacheEntry(const sp<Blob>& key, const sp<Blob>& value);
+        CacheEntry(const CacheEntry& ce);
+
+        bool operator<(const CacheEntry& rhs) const;
+        const CacheEntry& operator=(const CacheEntry&);
+
+        sp<Blob> getKey() const;
+        sp<Blob> getValue() const;
+
+        void setValue(const sp<Blob>& value);
+
+    private:
+
+        // mKey is the key that identifies the cache entry.
+        sp<Blob> mKey;
+
+        // mValue is the cached data associated with the key.
+        sp<Blob> mValue;
+    };
+
+    // A Header is the header for the entire BlobCache serialization format. No
+    // need to make this portable, so we simply write the struct out.
+    struct Header {
+        // mMagicNumber is the magic number that identifies the data as
+        // serialized BlobCache contents.  It must always contain 'Blb$'.
+        uint32_t mMagicNumber;
+
+        // mBlobCacheVersion is the serialization format version.
+        uint32_t mBlobCacheVersion;
+
+        // mDeviceVersion is the device-specific version of the cache.  This can
+        // be used to invalidate the cache.
+        uint32_t mDeviceVersion;
+
+        // mNumEntries is number of cache entries following the header in the
+        // data.
+        size_t mNumEntries;
+
+        // mBuildId is the build id of the device when the cache was created.
+        // When an update to the build happens (via an OTA or other update) this
+        // is used to invalidate the cache.
+        int mBuildIdLength;
+        char mBuildId[];
+    };
+
+    // An EntryHeader is the header for a serialized cache entry.  No need to
+    // make this portable, so we simply write the struct out.  Each EntryHeader
+    // is followed imediately by the key data and then the value data.
+    //
+    // The beginning of each serialized EntryHeader is 4-byte aligned, so the
+    // number of bytes that a serialized cache entry will occupy is:
+    //
+    //   ((sizeof(EntryHeader) + keySize + valueSize) + 3) & ~3
+    //
+    struct EntryHeader {
+        // mKeySize is the size of the entry key in bytes.
+        size_t mKeySize;
+
+        // mValueSize is the size of the entry value in bytes.
+        size_t mValueSize;
+
+        // mData contains both the key and value data for the cache entry.  The
+        // key comes first followed immediately by the value.
+        uint8_t mData[];
+    };
+
+    // mMaxKeySize is the maximum key size that will be cached. Calls to
+    // BlobCache::set with a keySize parameter larger than mMaxKeySize will
+    // simply not add the key/value pair to the cache.
+    const size_t mMaxKeySize;
+
+    // mMaxValueSize is the maximum value size that will be cached. Calls to
+    // BlobCache::set with a valueSize parameter larger than mMaxValueSize will
+    // simply not add the key/value pair to the cache.
+    const size_t mMaxValueSize;
+
+    // mMaxTotalSize is the maximum size that all cache entries can occupy. This
+    // includes space for both keys and values. When a call to BlobCache::set
+    // would otherwise cause this limit to be exceeded, either the key/value
+    // pair passed to BlobCache::set will not be cached or other cache entries
+    // will be evicted from the cache to make room for the new entry.
+    const size_t mMaxTotalSize;
+
+    // mTotalSize is the total combined size of all keys and values currently in
+    // the cache.
+    size_t mTotalSize;
+
+    // mRandState is the pseudo-random number generator state. It is passed to
+    // nrand48 to generate random numbers when needed.
+    unsigned short mRandState[3];
+
+    // mCacheEntries stores all the cache entries that are resident in memory.
+    // Cache entries are added to it by the 'set' method.
+    SortedVector<CacheEntry> mCacheEntries;
+};
+
+}
+
+#endif // ANDROID_BLOB_CACHE_H
diff --git a/libutils/include/utils/ByteOrder.h b/libutils/include/utils/ByteOrder.h
new file mode 100644
index 000000000..44ea13df8
--- /dev/null
+++ b/libutils/include/utils/ByteOrder.h
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2006 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 _LIBS_UTILS_BYTE_ORDER_H
+#define _LIBS_UTILS_BYTE_ORDER_H
+
+#include <stdint.h>
+#include <sys/types.h>
+#if defined(_WIN32)
+#include <winsock2.h>
+#else
+#include <netinet/in.h>
+#endif
+
+/*
+ * These macros are like the hton/ntoh byte swapping macros,
+ * except they allow you to swap to and from the "device" byte
+ * order.  The device byte order is the endianness of the target
+ * device -- for the ARM CPUs we use today, this is little endian.
+ *
+ * Note that the byte swapping functions have not been optimized
+ * much; performance is currently not an issue for them since the
+ * intent is to allow us to avoid byte swapping on the device.
+ */
+
+static inline uint32_t android_swap_long(uint32_t v)
+{
+    return (v<<24) | ((v<<8)&0x00FF0000) | ((v>>8)&0x0000FF00) | (v>>24);
+}
+
+static inline uint16_t android_swap_short(uint16_t v)
+{
+    return (v<<8) | (v>>8);
+}
+
+#define DEVICE_BYTE_ORDER LITTLE_ENDIAN
+
+#if BYTE_ORDER == DEVICE_BYTE_ORDER
+
+#define	dtohl(x)	(x)
+#define	dtohs(x)	(x)
+#define	htodl(x)	(x)
+#define	htods(x)	(x)
+
+#else
+
+#define	dtohl(x)	(android_swap_long(x))
+#define	dtohs(x)	(android_swap_short(x))
+#define	htodl(x)	(android_swap_long(x))
+#define	htods(x)	(android_swap_short(x))
+
+#endif
+
+#if BYTE_ORDER == LITTLE_ENDIAN
+#define fromlel(x) (x)
+#define fromles(x) (x)
+#define tolel(x) (x)
+#define toles(x) (x)
+#else
+#define fromlel(x) (android_swap_long(x))
+#define fromles(x) (android_swap_short(x))
+#define tolel(x) (android_swap_long(x))
+#define toles(x) (android_swap_short(x))
+#endif
+
+#endif // _LIBS_UTILS_BYTE_ORDER_H
diff --git a/libutils/include/utils/CallStack.h b/libutils/include/utils/CallStack.h
new file mode 100644
index 000000000..27e89f462
--- /dev/null
+++ b/libutils/include/utils/CallStack.h
@@ -0,0 +1,72 @@
+/*
+ * Copyright (C) 2007 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 ANDROID_CALLSTACK_H
+#define ANDROID_CALLSTACK_H
+
+#include <android/log.h>
+#include <backtrace/backtrace_constants.h>
+#include <utils/String8.h>
+#include <utils/Vector.h>
+
+#include <stdint.h>
+#include <sys/types.h>
+
+namespace android {
+
+class Printer;
+
+// Collect/print the call stack (function, file, line) traces for a single thread.
+class CallStack {
+public:
+    // Create an empty call stack. No-op.
+    CallStack();
+    // Create a callstack with the current thread's stack trace.
+    // Immediately dump it to logcat using the given logtag.
+    CallStack(const char* logtag, int32_t ignoreDepth=1);
+    ~CallStack();
+
+    // Reset the stack frames (same as creating an empty call stack).
+    void clear() { mFrameLines.clear(); }
+
+    // Immediately collect the stack traces for the specified thread.
+    // The default is to dump the stack of the current call.
+    void update(int32_t ignoreDepth=1, pid_t tid=BACKTRACE_CURRENT_THREAD);
+
+    // Dump a stack trace to the log using the supplied logtag.
+    void log(const char* logtag,
+             android_LogPriority priority = ANDROID_LOG_DEBUG,
+             const char* prefix = 0) const;
+
+    // Dump a stack trace to the specified file descriptor.
+    void dump(int fd, int indent = 0, const char* prefix = 0) const;
+
+    // Return a string (possibly very long) containing the complete stack trace.
+    String8 toString(const char* prefix = 0) const;
+
+    // Dump a serialized representation of the stack trace to the specified printer.
+    void print(Printer& printer) const;
+
+    // Get the count of stack frames that are in this call stack.
+    size_t size() const { return mFrameLines.size(); }
+
+private:
+    Vector<String8> mFrameLines;
+};
+
+}; // namespace android
+
+#endif // ANDROID_CALLSTACK_H
diff --git a/libutils/include/utils/Compat.h b/libutils/include/utils/Compat.h
new file mode 100644
index 000000000..2709e3b32
--- /dev/null
+++ b/libutils/include/utils/Compat.h
@@ -0,0 +1,83 @@
+/*
+ * 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 __LIB_UTILS_COMPAT_H
+#define __LIB_UTILS_COMPAT_H
+
+#include <unistd.h>
+
+#if defined(__APPLE__)
+
+/* Mac OS has always had a 64-bit off_t, so it doesn't have off64_t. */
+
+typedef off_t off64_t;
+
+static inline off64_t lseek64(int fd, off64_t offset, int whence) {
+    return lseek(fd, offset, whence);
+}
+
+static inline ssize_t pread64(int fd, void* buf, size_t nbytes, off64_t offset) {
+    return pread(fd, buf, nbytes, offset);
+}
+
+static inline ssize_t pwrite64(int fd, const void* buf, size_t nbytes, off64_t offset) {
+    return pwrite(fd, buf, nbytes, offset);
+}
+
+#endif /* __APPLE__ */
+
+#if defined(_WIN32)
+#define O_CLOEXEC O_NOINHERIT
+#define O_NOFOLLOW 0
+#define DEFFILEMODE 0666
+#endif /* _WIN32 */
+
+#define ZD "%zd"
+#define ZD_TYPE ssize_t
+
+/*
+ * Needed for cases where something should be constexpr if possible, but not
+ * being constexpr is fine if in pre-C++11 code (such as a const static float
+ * member variable).
+ */
+#if __cplusplus >= 201103L
+#define CONSTEXPR constexpr
+#else
+#define CONSTEXPR
+#endif
+
+/*
+ * TEMP_FAILURE_RETRY is defined by some, but not all, versions of
+ * <unistd.h>. (Alas, it is not as standard as we'd hoped!) So, if it's
+ * not already defined, then define it here.
+ */
+#ifndef TEMP_FAILURE_RETRY
+/* Used to retry syscalls that can return EINTR. */
+#define TEMP_FAILURE_RETRY(exp) ({         \
+    typeof (exp) _rc;                      \
+    do {                                   \
+        _rc = (exp);                       \
+    } while (_rc == -1 && errno == EINTR); \
+    _rc; })
+#endif
+
+#if defined(_WIN32)
+#define OS_PATH_SEPARATOR '\\'
+#else
+#define OS_PATH_SEPARATOR '/'
+#endif
+
+#endif /* __LIB_UTILS_COMPAT_H */
diff --git a/libutils/include/utils/Condition.h b/libutils/include/utils/Condition.h
new file mode 100644
index 000000000..25a53aa23
--- /dev/null
+++ b/libutils/include/utils/Condition.h
@@ -0,0 +1,165 @@
+/*
+ * Copyright (C) 2007 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 _LIBS_UTILS_CONDITION_H
+#define _LIBS_UTILS_CONDITION_H
+
+#include <limits.h>
+#include <stdint.h>
+#include <sys/types.h>
+#include <time.h>
+
+#if !defined(_WIN32)
+# include <pthread.h>
+#endif
+
+#include <utils/Errors.h>
+#include <utils/Mutex.h>
+#include <utils/Timers.h>
+
+// ---------------------------------------------------------------------------
+namespace android {
+// ---------------------------------------------------------------------------
+
+/*
+ * Condition variable class.  The implementation is system-dependent.
+ *
+ * Condition variables are paired up with mutexes.  Lock the mutex,
+ * call wait(), then either re-wait() if things aren't quite what you want,
+ * or unlock the mutex and continue.  All threads calling wait() must
+ * use the same mutex for a given Condition.
+ */
+class Condition {
+public:
+    enum {
+        PRIVATE = 0,
+        SHARED = 1
+    };
+
+    enum WakeUpType {
+        WAKE_UP_ONE = 0,
+        WAKE_UP_ALL = 1
+    };
+
+    Condition();
+    explicit Condition(int type);
+    ~Condition();
+    // Wait on the condition variable.  Lock the mutex before calling.
+    status_t wait(Mutex& mutex);
+    // same with relative timeout
+    status_t waitRelative(Mutex& mutex, nsecs_t reltime);
+    // Signal the condition variable, allowing exactly one thread to continue.
+    void signal();
+    // Signal the condition variable, allowing one or all threads to continue.
+    void signal(WakeUpType type) {
+        if (type == WAKE_UP_ONE) {
+            signal();
+        } else {
+            broadcast();
+        }
+    }
+    // Signal the condition variable, allowing all threads to continue.
+    void broadcast();
+
+private:
+#if !defined(_WIN32)
+    pthread_cond_t mCond;
+#else
+    void*   mState;
+#endif
+};
+
+// ---------------------------------------------------------------------------
+
+#if !defined(_WIN32)
+
+inline Condition::Condition() {
+    pthread_cond_init(&mCond, NULL);
+}
+inline Condition::Condition(int type) {
+    if (type == SHARED) {
+        pthread_condattr_t attr;
+        pthread_condattr_init(&attr);
+        pthread_condattr_setpshared(&attr, PTHREAD_PROCESS_SHARED);
+        pthread_cond_init(&mCond, &attr);
+        pthread_condattr_destroy(&attr);
+    } else {
+        pthread_cond_init(&mCond, NULL);
+    }
+}
+inline Condition::~Condition() {
+    pthread_cond_destroy(&mCond);
+}
+inline status_t Condition::wait(Mutex& mutex) {
+    return -pthread_cond_wait(&mCond, &mutex.mMutex);
+}
+inline status_t Condition::waitRelative(Mutex& mutex, nsecs_t reltime) {
+    struct timespec ts;
+#if defined(__linux__)
+    clock_gettime(CLOCK_REALTIME, &ts);
+#else // __APPLE__
+    // Apple doesn't support POSIX clocks.
+    struct timeval t;
+    gettimeofday(&t, NULL);
+    ts.tv_sec = t.tv_sec;
+    ts.tv_nsec = t.tv_usec*1000;
+#endif
+
+    // On 32-bit devices, tv_sec is 32-bit, but `reltime` is 64-bit.
+    int64_t reltime_sec = reltime/1000000000;
+
+    ts.tv_nsec += static_cast<long>(reltime%1000000000);
+    if (reltime_sec < INT64_MAX && ts.tv_nsec >= 1000000000) {
+        ts.tv_nsec -= 1000000000;
+        ++reltime_sec;
+    }
+
+    int64_t time_sec = ts.tv_sec;
+    if (time_sec > INT64_MAX - reltime_sec) {
+        time_sec = INT64_MAX;
+    } else {
+        time_sec += reltime_sec;
+    }
+
+    ts.tv_sec = (time_sec > LONG_MAX) ? LONG_MAX : static_cast<long>(time_sec);
+
+    return -pthread_cond_timedwait(&mCond, &mutex.mMutex, &ts);
+}
+inline void Condition::signal() {
+    /*
+     * POSIX says pthread_cond_signal wakes up "one or more" waiting threads.
+     * However bionic follows the glibc guarantee which wakes up "exactly one"
+     * waiting thread.
+     *
+     * man 3 pthread_cond_signal
+     *   pthread_cond_signal restarts one of the threads that are waiting on
+     *   the condition variable cond. If no threads are waiting on cond,
+     *   nothing happens. If several threads are waiting on cond, exactly one
+     *   is restarted, but it is not specified which.
+     */
+    pthread_cond_signal(&mCond);
+}
+inline void Condition::broadcast() {
+    pthread_cond_broadcast(&mCond);
+}
+
+#endif // !defined(_WIN32)
+
+// ---------------------------------------------------------------------------
+}; // namespace android
+// ---------------------------------------------------------------------------
+
+#endif // _LIBS_UTILS_CONDITON_H
diff --git a/libutils/include/utils/Debug.h b/libutils/include/utils/Debug.h
new file mode 100644
index 000000000..08893bdaa
--- /dev/null
+++ b/libutils/include/utils/Debug.h
@@ -0,0 +1,48 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_UTILS_DEBUG_H
+#define ANDROID_UTILS_DEBUG_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+namespace android {
+// ---------------------------------------------------------------------------
+
+#ifdef __cplusplus
+template<bool> struct CompileTimeAssert;
+template<> struct CompileTimeAssert<true> {};
+#define COMPILE_TIME_ASSERT(_exp) \
+    template class CompileTimeAssert< (_exp) >;
+#endif
+#define COMPILE_TIME_ASSERT_FUNCTION_SCOPE(_exp) \
+    CompileTimeAssert<( _exp )>();
+
+// ---------------------------------------------------------------------------
+
+#ifdef __cplusplus
+template<bool C, typename LSH, typename RHS> struct CompileTimeIfElse;
+template<typename LHS, typename RHS> 
+struct CompileTimeIfElse<true,  LHS, RHS> { typedef LHS TYPE; };
+template<typename LHS, typename RHS> 
+struct CompileTimeIfElse<false, LHS, RHS> { typedef RHS TYPE; };
+#endif
+
+// ---------------------------------------------------------------------------
+}; // namespace android
+
+#endif // ANDROID_UTILS_DEBUG_H
diff --git a/libutils/include/utils/Endian.h b/libutils/include/utils/Endian.h
new file mode 100644
index 000000000..591cae0d3
--- /dev/null
+++ b/libutils/include/utils/Endian.h
@@ -0,0 +1,35 @@
+/*
+ * Copyright (C) 2005 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.
+ */
+
+//
+// Android endian-ness defines.
+//
+#ifndef _LIBS_UTILS_ENDIAN_H
+#define _LIBS_UTILS_ENDIAN_H
+
+#if defined(__APPLE__) || defined(_WIN32)
+
+#define __BIG_ENDIAN 0x1000
+#define __LITTLE_ENDIAN 0x0001
+#define __BYTE_ORDER __LITTLE_ENDIAN
+
+#else
+
+#include <endian.h>
+
+#endif
+
+#endif /*_LIBS_UTILS_ENDIAN_H*/
diff --git a/libutils/include/utils/Errors.h b/libutils/include/utils/Errors.h
new file mode 100644
index 000000000..16e1fa2c2
--- /dev/null
+++ b/libutils/include/utils/Errors.h
@@ -0,0 +1,88 @@
+/*
+ * Copyright (C) 2007 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 ANDROID_ERRORS_H
+#define ANDROID_ERRORS_H
+
+#include <sys/types.h>
+#include <errno.h>
+
+namespace android {
+
+// use this type to return error codes
+#ifdef _WIN32
+typedef int         status_t;
+#else
+typedef int32_t     status_t;
+#endif
+
+/* the MS C runtime lacks a few error codes */
+
+/*
+ * Error codes. 
+ * All error codes are negative values.
+ */
+
+// Win32 #defines NO_ERROR as well.  It has the same value, so there's no
+// real conflict, though it's a bit awkward.
+#ifdef _WIN32
+# undef NO_ERROR
+#endif
+
+enum {
+    OK                = 0,    // Everything's swell.
+    NO_ERROR          = 0,    // No errors.
+
+    UNKNOWN_ERROR       = (-2147483647-1), // INT32_MIN value
+
+    NO_MEMORY           = -ENOMEM,
+    INVALID_OPERATION   = -ENOSYS,
+    BAD_VALUE           = -EINVAL,
+    BAD_TYPE            = (UNKNOWN_ERROR + 1),
+    NAME_NOT_FOUND      = -ENOENT,
+    PERMISSION_DENIED   = -EPERM,
+    NO_INIT             = -ENODEV,
+    ALREADY_EXISTS      = -EEXIST,
+    DEAD_OBJECT         = -EPIPE,
+    FAILED_TRANSACTION  = (UNKNOWN_ERROR + 2),
+#if !defined(_WIN32)
+    BAD_INDEX           = -EOVERFLOW,
+    NOT_ENOUGH_DATA     = -ENODATA,
+    WOULD_BLOCK         = -EWOULDBLOCK, 
+    TIMED_OUT           = -ETIMEDOUT,
+    UNKNOWN_TRANSACTION = -EBADMSG,
+#else    
+    BAD_INDEX           = -E2BIG,
+    NOT_ENOUGH_DATA     = (UNKNOWN_ERROR + 3),
+    WOULD_BLOCK         = (UNKNOWN_ERROR + 4),
+    TIMED_OUT           = (UNKNOWN_ERROR + 5),
+    UNKNOWN_TRANSACTION = (UNKNOWN_ERROR + 6),
+#endif    
+    FDS_NOT_ALLOWED     = (UNKNOWN_ERROR + 7),
+    UNEXPECTED_NULL     = (UNKNOWN_ERROR + 8),
+};
+
+// Restore define; enumeration is in "android" namespace, so the value defined
+// there won't work for Win32 code in a different namespace.
+#ifdef _WIN32
+# define NO_ERROR 0L
+#endif
+
+}; // namespace android
+    
+// ---------------------------------------------------------------------------
+    
+#endif // ANDROID_ERRORS_H
diff --git a/libutils/include/utils/FastStrcmp.h b/libutils/include/utils/FastStrcmp.h
new file mode 100644
index 000000000..3844e7d96
--- /dev/null
+++ b/libutils/include/utils/FastStrcmp.h
@@ -0,0 +1,54 @@
+/*
+ * Copyright (C) 2014-2016 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 _ANDROID_UTILS_FASTSTRCMP_H__
+#define _ANDROID_UTILS_FASTSTRCMP_H__
+
+#ifdef __cplusplus
+
+// Optimized for instruction cache locality
+//
+// Template class fastcmp used to create more time-efficient str*cmp
+// functions by pre-checking the first character before resorting
+// to calling the underlying string function.  Profiled with a
+// measurable speedup when used in hot code.  Usage is of the form:
+//
+//  fastcmp<strncmp>(str1, str2, len)
+//
+// NB: Does not work for the case insensitive str*cmp functions.
+// NB: Returns boolean, do not use if expecting to check negative value.
+//     Thus not semantically identical to the expected function behavior.
+
+template <int (*cmp)(const char *l, const char *r, const size_t s)>
+static inline int fastcmp(const char *l, const char *r, const size_t s) {
+    return (*l != *r) || cmp(l + 1, r + 1, s - 1);
+}
+
+template <int (*cmp)(const void *l, const void *r, const size_t s)>
+static inline int fastcmp(const void *lv, const void *rv, const size_t s) {
+    const char *l = static_cast<const char *>(lv);
+    const char *r = static_cast<const char *>(rv);
+    return (*l != *r) || cmp(l + 1, r + 1, s - 1);
+}
+
+template <int (*cmp)(const char *l, const char *r)>
+static inline int fastcmp(const char *l, const char *r) {
+    return (*l != *r) || cmp(l + 1, r + 1);
+}
+
+#endif
+
+#endif // _ANDROID_UTILS_FASTSTRCMP_H__
diff --git a/libutils/include/utils/FileMap.h b/libutils/include/utils/FileMap.h
new file mode 100644
index 000000000..7d372e1dc
--- /dev/null
+++ b/libutils/include/utils/FileMap.h
@@ -0,0 +1,129 @@
+/*
+ * Copyright (C) 2006 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.
+ */
+
+//
+// Encapsulate a shared file mapping.
+//
+#ifndef __LIBS_FILE_MAP_H
+#define __LIBS_FILE_MAP_H
+
+#include <sys/types.h>
+
+#include <utils/Compat.h>
+
+#if defined(__MINGW32__)
+// Ensure that we always pull in winsock2.h before windows.h
+#if defined(_WIN32)
+#include <winsock2.h>
+#endif
+#include <windows.h>
+#endif
+
+namespace android {
+
+/*
+ * This represents a memory-mapped file.  It might be the entire file or
+ * only part of it.  This requires a little bookkeeping because the mapping
+ * needs to be aligned on page boundaries, and in some cases we'd like to
+ * have multiple references to the mapped area without creating additional
+ * maps.
+ *
+ * This always uses MAP_SHARED.
+ *
+ * TODO: we should be able to create a new FileMap that is a subset of
+ * an existing FileMap and shares the underlying mapped pages.  Requires
+ * completing the refcounting stuff and possibly introducing the notion
+ * of a FileMap hierarchy.
+ */
+class FileMap {
+public:
+    FileMap(void);
+
+    FileMap(FileMap&& f);
+    FileMap& operator=(FileMap&& f);
+
+    /*
+     * Create a new mapping on an open file.
+     *
+     * Closing the file descriptor does not unmap the pages, so we don't
+     * claim ownership of the fd.
+     *
+     * Returns "false" on failure.
+     */
+    bool create(const char* origFileName, int fd,
+                off64_t offset, size_t length, bool readOnly);
+
+    ~FileMap(void);
+
+    /*
+     * Return the name of the file this map came from, if known.
+     */
+    const char* getFileName(void) const { return mFileName; }
+    
+    /*
+     * Get a pointer to the piece of the file we requested.
+     */
+    void* getDataPtr(void) const { return mDataPtr; }
+
+    /*
+     * Get the length we requested.
+     */
+    size_t getDataLength(void) const { return mDataLength; }
+
+    /*
+     * Get the data offset used to create this map.
+     */
+    off64_t getDataOffset(void) const { return mDataOffset; }
+
+    /*
+     * This maps directly to madvise() values, but allows us to avoid
+     * including <sys/mman.h> everywhere.
+     */
+    enum MapAdvice {
+        NORMAL, RANDOM, SEQUENTIAL, WILLNEED, DONTNEED
+    };
+
+    /*
+     * Apply an madvise() call to the entire file.
+     *
+     * Returns 0 on success, -1 on failure.
+     */
+    int advise(MapAdvice advice);
+
+protected:
+
+private:
+    // these are not implemented
+    FileMap(const FileMap& src);
+    const FileMap& operator=(const FileMap& src);
+
+    char*       mFileName;      // original file name, if known
+    void*       mBasePtr;       // base of mmap area; page aligned
+    size_t      mBaseLength;    // length, measured from "mBasePtr"
+    off64_t     mDataOffset;    // offset used when map was created
+    void*       mDataPtr;       // start of requested data, offset from base
+    size_t      mDataLength;    // length, measured from "mDataPtr"
+#if defined(__MINGW32__)
+    HANDLE      mFileHandle;    // Win32 file handle
+    HANDLE      mFileMapping;   // Win32 file mapping handle
+#endif
+
+    static long mPageSize;
+};
+
+}; // namespace android
+
+#endif // __LIBS_FILE_MAP_H
diff --git a/libutils/include/utils/Flattenable.h b/libutils/include/utils/Flattenable.h
new file mode 100644
index 000000000..22b811a14
--- /dev/null
+++ b/libutils/include/utils/Flattenable.h
@@ -0,0 +1,205 @@
+/*
+ * 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 ANDROID_UTILS_FLATTENABLE_H
+#define ANDROID_UTILS_FLATTENABLE_H
+
+
+#include <stdint.h>
+#include <string.h>
+#include <sys/types.h>
+#include <utils/Errors.h>
+#include <utils/Debug.h>
+
+#include <type_traits>
+
+namespace android {
+
+
+class FlattenableUtils {
+public:
+    template<size_t N>
+    static size_t align(size_t size) {
+        COMPILE_TIME_ASSERT_FUNCTION_SCOPE( !(N & (N-1)) );
+        return (size + (N-1)) & ~(N-1);
+    }
+
+    template<size_t N>
+    static size_t align(void const*& buffer) {
+        COMPILE_TIME_ASSERT_FUNCTION_SCOPE( !(N & (N-1)) );
+        uintptr_t b = uintptr_t(buffer);
+        buffer = reinterpret_cast<void*>((uintptr_t(buffer) + (N-1)) & ~(N-1));
+        return size_t(uintptr_t(buffer) - b);
+    }
+
+    template<size_t N>
+    static size_t align(void*& buffer) {
+        return align<N>( const_cast<void const*&>(buffer) );
+    }
+
+    static void advance(void*& buffer, size_t& size, size_t offset) {
+        buffer = reinterpret_cast<void*>( uintptr_t(buffer) + offset );
+        size -= offset;
+    }
+
+    static void advance(void const*& buffer, size_t& size, size_t offset) {
+        buffer = reinterpret_cast<void const*>( uintptr_t(buffer) + offset );
+        size -= offset;
+    }
+
+    // write a POD structure
+    template<typename T>
+    static void write(void*& buffer, size_t& size, const T& value) {
+        static_assert(std::is_trivially_copyable<T>::value,
+                      "Cannot flatten a non-trivially-copyable type");
+        memcpy(buffer, &value, sizeof(T));
+        advance(buffer, size, sizeof(T));
+    }
+
+    // read a POD structure
+    template<typename T>
+    static void read(void const*& buffer, size_t& size, T& value) {
+        static_assert(std::is_trivially_copyable<T>::value,
+                      "Cannot unflatten a non-trivially-copyable type");
+        memcpy(&value, buffer, sizeof(T));
+        advance(buffer, size, sizeof(T));
+    }
+};
+
+
+/*
+ * The Flattenable protocol allows an object to serialize itself out
+ * to a byte-buffer and an array of file descriptors.
+ * Flattenable objects must implement this protocol.
+ */
+
+template <typename T>
+class Flattenable {
+public:
+    // size in bytes of the flattened object
+    inline size_t getFlattenedSize() const;
+
+    // number of file descriptors to flatten
+    inline size_t getFdCount() const;
+
+    // flattens the object into buffer.
+    // size should be at least of getFlattenedSize()
+    // file descriptors are written in the fds[] array but ownership is
+    // not transfered (ie: they must be dupped by the caller of
+    // flatten() if needed).
+    inline status_t flatten(void*& buffer, size_t& size, int*& fds, size_t& count) const;
+
+    // unflattens the object from buffer.
+    // size should be equal to the value of getFlattenedSize() when the
+    // object was flattened.
+    // unflattened file descriptors are found in the fds[] array and
+    // don't need to be dupped(). ie: the caller of unflatten doesn't
+    // keep ownership. If a fd is not retained by unflatten() it must be
+    // explicitly closed.
+    inline status_t unflatten(void const*& buffer, size_t& size, int const*& fds, size_t& count);
+};
+
+template<typename T>
+inline size_t Flattenable<T>::getFlattenedSize() const {
+    return static_cast<T const*>(this)->T::getFlattenedSize();
+}
+template<typename T>
+inline size_t Flattenable<T>::getFdCount() const {
+    return static_cast<T const*>(this)->T::getFdCount();
+}
+template<typename T>
+inline status_t Flattenable<T>::flatten(
+        void*& buffer, size_t& size, int*& fds, size_t& count) const {
+    return static_cast<T const*>(this)->T::flatten(buffer, size, fds, count);
+}
+template<typename T>
+inline status_t Flattenable<T>::unflatten(
+        void const*& buffer, size_t& size, int const*& fds, size_t& count) {
+    return static_cast<T*>(this)->T::unflatten(buffer, size, fds, count);
+}
+
+/*
+ * LightFlattenable is a protocol allowing object to serialize themselves out
+ * to a byte-buffer. Because it doesn't handle file-descriptors,
+ * LightFlattenable is usually more size efficient than Flattenable.
+ * LightFlattenable objects must implement this protocol.
+ */
+template <typename T>
+class LightFlattenable {
+public:
+    // returns whether this object always flatten into the same size.
+    // for efficiency, this should always be inline.
+    inline bool isFixedSize() const;
+
+    // returns size in bytes of the flattened object. must be a constant.
+    inline size_t getFlattenedSize() const;
+
+    // flattens the object into buffer.
+    inline status_t flatten(void* buffer, size_t size) const;
+
+    // unflattens the object from buffer of given size.
+    inline status_t unflatten(void const* buffer, size_t size);
+};
+
+template <typename T>
+inline bool LightFlattenable<T>::isFixedSize() const {
+    return static_cast<T const*>(this)->T::isFixedSize();
+}
+template <typename T>
+inline size_t LightFlattenable<T>::getFlattenedSize() const {
+    return static_cast<T const*>(this)->T::getFlattenedSize();
+}
+template <typename T>
+inline status_t LightFlattenable<T>::flatten(void* buffer, size_t size) const {
+    return static_cast<T const*>(this)->T::flatten(buffer, size);
+}
+template <typename T>
+inline status_t LightFlattenable<T>::unflatten(void const* buffer, size_t size) {
+    return static_cast<T*>(this)->T::unflatten(buffer, size);
+}
+
+/*
+ * LightFlattenablePod is an implementation of the LightFlattenable protocol
+ * for POD (plain-old-data) objects.
+ * Simply derive from LightFlattenablePod<Foo> to make Foo flattenable; no
+ * need to implement any methods; obviously Foo must be a POD structure.
+ */
+template <typename T>
+class LightFlattenablePod : public LightFlattenable<T> {
+public:
+    inline bool isFixedSize() const {
+        return true;
+    }
+
+    inline size_t getFlattenedSize() const {
+        return sizeof(T);
+    }
+    inline status_t flatten(void* buffer, size_t size) const {
+        if (size < sizeof(T)) return NO_MEMORY;
+        *reinterpret_cast<T*>(buffer) = *static_cast<T const*>(this);
+        return NO_ERROR;
+    }
+    inline status_t unflatten(void const* buffer, size_t) {
+        *static_cast<T*>(this) = *reinterpret_cast<T const*>(buffer);
+        return NO_ERROR;
+    }
+};
+
+
+}; // namespace android
+
+
+#endif /* ANDROID_UTILS_FLATTENABLE_H */
diff --git a/libutils/include/utils/Functor.h b/libutils/include/utils/Functor.h
new file mode 100644
index 000000000..09ea614b6
--- /dev/null
+++ b/libutils/include/utils/Functor.h
@@ -0,0 +1,33 @@
+/*
+ * Copyright (C) 2011 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 ANDROID_FUNCTOR_H
+#define ANDROID_FUNCTOR_H
+
+#include <utils/Errors.h>
+
+namespace  android {
+
+class Functor {
+public:
+    Functor() {}
+    virtual ~Functor() {}
+    virtual status_t operator ()(int /*what*/, void* /*data*/) { return NO_ERROR; }
+};
+
+}; // namespace android
+
+#endif // ANDROID_FUNCTOR_H
diff --git a/libutils/include/utils/JenkinsHash.h b/libutils/include/utils/JenkinsHash.h
new file mode 100644
index 000000000..027c10c7e
--- /dev/null
+++ b/libutils/include/utils/JenkinsHash.h
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2012 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.
+ */
+
+/* Implementation of Jenkins one-at-a-time hash function. These choices are
+ * optimized for code size and portability, rather than raw speed. But speed
+ * should still be quite good.
+ **/
+
+#ifndef ANDROID_JENKINS_HASH_H
+#define ANDROID_JENKINS_HASH_H
+
+#include <utils/TypeHelpers.h>
+
+namespace android {
+
+/* The Jenkins hash of a sequence of 32 bit words A, B, C is:
+ * Whiten(Mix(Mix(Mix(0, A), B), C)) */
+
+#ifdef __clang__
+__attribute__((no_sanitize("integer")))
+#endif
+inline uint32_t JenkinsHashMix(uint32_t hash, uint32_t data) {
+    hash += data;
+    hash += (hash << 10);
+    hash ^= (hash >> 6);
+    return hash;
+}
+
+hash_t JenkinsHashWhiten(uint32_t hash);
+
+/* Helpful utility functions for hashing data in 32 bit chunks */
+uint32_t JenkinsHashMixBytes(uint32_t hash, const uint8_t* bytes, size_t size);
+
+uint32_t JenkinsHashMixShorts(uint32_t hash, const uint16_t* shorts, size_t size);
+
+}
+
+#endif // ANDROID_JENKINS_HASH_H
diff --git a/libutils/include/utils/KeyedVector.h b/libutils/include/utils/KeyedVector.h
new file mode 100644
index 000000000..f93ad6e21
--- /dev/null
+++ b/libutils/include/utils/KeyedVector.h
@@ -0,0 +1,216 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_KEYED_VECTOR_H
+#define ANDROID_KEYED_VECTOR_H
+
+#include <assert.h>
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <log/log.h>
+#include <utils/Errors.h>
+#include <utils/SortedVector.h>
+#include <utils/TypeHelpers.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+template <typename KEY, typename VALUE>
+class KeyedVector
+{
+public:
+    typedef KEY    key_type;
+    typedef VALUE  value_type;
+
+    inline                  KeyedVector();
+
+    /*
+     * empty the vector
+     */
+
+    inline  void            clear()                     { mVector.clear(); }
+
+    /*! 
+     * vector stats
+     */
+
+    //! returns number of items in the vector
+    inline  size_t          size() const                { return mVector.size(); }
+    //! returns whether or not the vector is empty
+    inline  bool            isEmpty() const             { return mVector.isEmpty(); }
+    //! returns how many items can be stored without reallocating the backing store
+    inline  size_t          capacity() const            { return mVector.capacity(); }
+    //! sets the capacity. capacity can never be reduced less than size()
+    inline ssize_t          setCapacity(size_t size)    { return mVector.setCapacity(size); }
+
+    // returns true if the arguments is known to be identical to this vector
+    inline bool isIdenticalTo(const KeyedVector& rhs) const;
+
+    /*! 
+     * accessors
+     */
+            const VALUE&    valueFor(const KEY& key) const;
+            const VALUE&    valueAt(size_t index) const;
+            const KEY&      keyAt(size_t index) const;
+            ssize_t         indexOfKey(const KEY& key) const;
+            const VALUE&    operator[] (size_t index) const;
+
+    /*!
+     * modifying the array
+     */
+
+            VALUE&          editValueFor(const KEY& key);
+            VALUE&          editValueAt(size_t index);
+
+            /*! 
+             * add/insert/replace items
+             */
+             
+            ssize_t         add(const KEY& key, const VALUE& item);
+            ssize_t         replaceValueFor(const KEY& key, const VALUE& item);
+            ssize_t         replaceValueAt(size_t index, const VALUE& item);
+
+    /*!
+     * remove items
+     */
+
+            ssize_t         removeItem(const KEY& key);
+            ssize_t         removeItemsAt(size_t index, size_t count = 1);
+            
+private:
+            SortedVector< key_value_pair_t<KEY, VALUE> >    mVector;
+};
+
+// ---------------------------------------------------------------------------
+
+/**
+ * Variation of KeyedVector that holds a default value to return when
+ * valueFor() is called with a key that doesn't exist.
+ */
+template <typename KEY, typename VALUE>
+class DefaultKeyedVector : public KeyedVector<KEY, VALUE>
+{
+public:
+    inline                  DefaultKeyedVector(const VALUE& defValue = VALUE());
+            const VALUE&    valueFor(const KEY& key) const;
+
+private:
+            VALUE                                           mDefault;
+};
+
+// ---------------------------------------------------------------------------
+
+template<typename KEY, typename VALUE> inline
+KeyedVector<KEY,VALUE>::KeyedVector()
+{
+}
+
+template<typename KEY, typename VALUE> inline
+bool KeyedVector<KEY,VALUE>::isIdenticalTo(const KeyedVector<KEY,VALUE>& rhs) const {
+    return mVector.array() == rhs.mVector.array();
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::indexOfKey(const KEY& key) const {
+    return mVector.indexOf( key_value_pair_t<KEY,VALUE>(key) );
+}
+
+template<typename KEY, typename VALUE> inline
+const VALUE& KeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
+    ssize_t i = this->indexOfKey(key);
+    LOG_ALWAYS_FATAL_IF(i<0, "%s: key not found", __PRETTY_FUNCTION__);
+    return mVector.itemAt(i).value;
+}
+
+template<typename KEY, typename VALUE> inline
+const VALUE& KeyedVector<KEY,VALUE>::valueAt(size_t index) const {
+    return mVector.itemAt(index).value;
+}
+
+template<typename KEY, typename VALUE> inline
+const VALUE& KeyedVector<KEY,VALUE>::operator[] (size_t index) const {
+    return valueAt(index);
+}
+
+template<typename KEY, typename VALUE> inline
+const KEY& KeyedVector<KEY,VALUE>::keyAt(size_t index) const {
+    return mVector.itemAt(index).key;
+}
+
+template<typename KEY, typename VALUE> inline
+VALUE& KeyedVector<KEY,VALUE>::editValueFor(const KEY& key) {
+    ssize_t i = this->indexOfKey(key);
+    LOG_ALWAYS_FATAL_IF(i<0, "%s: key not found", __PRETTY_FUNCTION__);
+    return mVector.editItemAt(static_cast<size_t>(i)).value;
+}
+
+template<typename KEY, typename VALUE> inline
+VALUE& KeyedVector<KEY,VALUE>::editValueAt(size_t index) {
+    return mVector.editItemAt(index).value;
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::add(const KEY& key, const VALUE& value) {
+    return mVector.add( key_value_pair_t<KEY,VALUE>(key, value) );
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::replaceValueFor(const KEY& key, const VALUE& value) {
+    key_value_pair_t<KEY,VALUE> pair(key, value);
+    mVector.remove(pair);
+    return mVector.add(pair);
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::replaceValueAt(size_t index, const VALUE& item) {
+    if (index<size()) {
+        mVector.editItemAt(index).value = item;
+        return static_cast<ssize_t>(index);
+    }
+    return BAD_INDEX;
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::removeItem(const KEY& key) {
+    return mVector.remove(key_value_pair_t<KEY,VALUE>(key));
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY, VALUE>::removeItemsAt(size_t index, size_t count) {
+    return mVector.removeItemsAt(index, count);
+}
+
+// ---------------------------------------------------------------------------
+
+template<typename KEY, typename VALUE> inline
+DefaultKeyedVector<KEY,VALUE>::DefaultKeyedVector(const VALUE& defValue)
+    : mDefault(defValue)
+{
+}
+
+template<typename KEY, typename VALUE> inline
+const VALUE& DefaultKeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
+    ssize_t i = this->indexOfKey(key);
+    return i >= 0 ? KeyedVector<KEY,VALUE>::valueAt(i) : mDefault;
+}
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_KEYED_VECTOR_H
diff --git a/libutils/include/utils/LinearTransform.h b/libutils/include/utils/LinearTransform.h
new file mode 100644
index 000000000..04cb355c7
--- /dev/null
+++ b/libutils/include/utils/LinearTransform.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright (C) 2011 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 _LIBS_UTILS_LINEAR_TRANSFORM_H
+#define _LIBS_UTILS_LINEAR_TRANSFORM_H
+
+#include <stdint.h>
+
+namespace android {
+
+// LinearTransform defines a structure which hold the definition of a
+// transformation from single dimensional coordinate system A into coordinate
+// system B (and back again).  Values in A and in B are 64 bit, the linear
+// scale factor is expressed as a rational number using two 32 bit values.
+//
+// Specifically, let
+// f(a) = b
+// F(b) = f^-1(b) = a
+// then
+//
+// f(a) = (((a - a_zero) * a_to_b_numer) / a_to_b_denom) + b_zero;
+//
+// and
+//
+// F(b) = (((b - b_zero) * a_to_b_denom) / a_to_b_numer) + a_zero;
+//
+struct LinearTransform {
+  int64_t  a_zero;
+  int64_t  b_zero;
+  int32_t  a_to_b_numer;
+  uint32_t a_to_b_denom;
+
+  // Transform from A->B
+  // Returns true on success, or false in the case of a singularity or an
+  // overflow.
+  bool doForwardTransform(int64_t a_in, int64_t* b_out) const;
+
+  // Transform from B->A
+  // Returns true on success, or false in the case of a singularity or an
+  // overflow.
+  bool doReverseTransform(int64_t b_in, int64_t* a_out) const;
+
+  // Helpers which will reduce the fraction N/D using Euclid's method.
+  template <class T> static void reduce(T* N, T* D);
+  static void reduce(int32_t* N, uint32_t* D);
+};
+
+
+}
+
+#endif  // _LIBS_UTILS_LINEAR_TRANSFORM_H
diff --git a/libutils/include/utils/List.h b/libutils/include/utils/List.h
new file mode 100644
index 000000000..403cd7f1e
--- /dev/null
+++ b/libutils/include/utils/List.h
@@ -0,0 +1,332 @@
+/*
+ * Copyright (C) 2005 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.
+ */
+
+//
+// Templated list class.  Normally we'd use STL, but we don't have that.
+// This class mimics STL's interfaces.
+//
+// Objects are copied into the list with the '=' operator or with copy-
+// construction, so if the compiler's auto-generated versions won't work for
+// you, define your own.
+//
+// The only class you want to use from here is "List".
+//
+#ifndef _LIBS_UTILS_LIST_H
+#define _LIBS_UTILS_LIST_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+namespace android {
+
+/*
+ * Doubly-linked list.  Instantiate with "List<MyClass> myList".
+ *
+ * Objects added to the list are copied using the assignment operator,
+ * so this must be defined.
+ */
+template<typename T> 
+class List 
+{
+protected:
+    /*
+     * One element in the list.
+     */
+    class _Node {
+    public:
+        explicit _Node(const T& val) : mVal(val) {}
+        ~_Node() {}
+        inline T& getRef() { return mVal; }
+        inline const T& getRef() const { return mVal; }
+        inline _Node* getPrev() const { return mpPrev; }
+        inline _Node* getNext() const { return mpNext; }
+        inline void setVal(const T& val) { mVal = val; }
+        inline void setPrev(_Node* ptr) { mpPrev = ptr; }
+        inline void setNext(_Node* ptr) { mpNext = ptr; }
+    private:
+        friend class List;
+        friend class _ListIterator;
+        T           mVal;
+        _Node*      mpPrev;
+        _Node*      mpNext;
+    };
+
+    /*
+     * Iterator for walking through the list.
+     */
+    
+    template <typename TYPE>
+    struct CONST_ITERATOR {
+        typedef _Node const * NodePtr;
+        typedef const TYPE Type;
+    };
+    
+    template <typename TYPE>
+    struct NON_CONST_ITERATOR {
+        typedef _Node* NodePtr;
+        typedef TYPE Type;
+    };
+    
+    template<
+        typename U,
+        template <class> class Constness
+    > 
+    class _ListIterator {
+        typedef _ListIterator<U, Constness>     _Iter;
+        typedef typename Constness<U>::NodePtr  _NodePtr;
+        typedef typename Constness<U>::Type     _Type;
+
+        explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}
+
+    public:
+        _ListIterator() {}
+        _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}
+        ~_ListIterator() {}
+        
+        // this will handle conversions from iterator to const_iterator
+        // (and also all convertible iterators)
+        // Here, in this implementation, the iterators can be converted
+        // if the nodes can be converted
+        template<typename V> explicit 
+        _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}
+        
+
+        /*
+         * Dereference operator.  Used to get at the juicy insides.
+         */
+        _Type& operator*() const { return mpNode->getRef(); }
+        _Type* operator->() const { return &(mpNode->getRef()); }
+
+        /*
+         * Iterator comparison.
+         */
+        inline bool operator==(const _Iter& right) const { 
+            return mpNode == right.mpNode; }
+        
+        inline bool operator!=(const _Iter& right) const { 
+            return mpNode != right.mpNode; }
+
+        /*
+         * handle comparisons between iterator and const_iterator
+         */
+        template<typename OTHER>
+        inline bool operator==(const OTHER& right) const { 
+            return mpNode == right.mpNode; }
+        
+        template<typename OTHER>
+        inline bool operator!=(const OTHER& right) const { 
+            return mpNode != right.mpNode; }
+
+        /*
+         * Incr/decr, used to move through the list.
+         */
+        inline _Iter& operator++() {     // pre-increment
+            mpNode = mpNode->getNext();
+            return *this;
+        }
+        const _Iter operator++(int) {    // post-increment
+            _Iter tmp(*this);
+            mpNode = mpNode->getNext();
+            return tmp;
+        }
+        inline _Iter& operator--() {     // pre-increment
+            mpNode = mpNode->getPrev();
+            return *this;
+        }
+        const _Iter operator--(int) {   // post-increment
+            _Iter tmp(*this);
+            mpNode = mpNode->getPrev();
+            return tmp;
+        }
+
+        inline _NodePtr getNode() const { return mpNode; }
+
+        _NodePtr mpNode;    /* should be private, but older gcc fails */
+    private:
+        friend class List;
+    };
+
+public:
+    List() {
+        prep();
+    }
+    List(const List<T>& src) {      // copy-constructor
+        prep();
+        insert(begin(), src.begin(), src.end());
+    }
+    virtual ~List() {
+        clear();
+        delete[] (unsigned char*) mpMiddle;
+    }
+
+    typedef _ListIterator<T, NON_CONST_ITERATOR> iterator;
+    typedef _ListIterator<T, CONST_ITERATOR> const_iterator;
+
+    List<T>& operator=(const List<T>& right);
+
+    /* returns true if the list is empty */
+    inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }
+
+    /* return #of elements in list */
+    size_t size() const {
+        return size_t(distance(begin(), end()));
+    }
+
+    /*
+     * Return the first element or one past the last element.  The
+     * _Node* we're returning is converted to an "iterator" by a
+     * constructor in _ListIterator.
+     */
+    inline iterator begin() { 
+        return iterator(mpMiddle->getNext()); 
+    }
+    inline const_iterator begin() const { 
+        return const_iterator(const_cast<_Node const*>(mpMiddle->getNext())); 
+    }
+    inline iterator end() { 
+        return iterator(mpMiddle); 
+    }
+    inline const_iterator end() const { 
+        return const_iterator(const_cast<_Node const*>(mpMiddle)); 
+    }
+
+    /* add the object to the head or tail of the list */
+    void push_front(const T& val) { insert(begin(), val); }
+    void push_back(const T& val) { insert(end(), val); }
+
+    /* insert before the current node; returns iterator at new node */
+    iterator insert(iterator posn, const T& val) 
+    {
+        _Node* newNode = new _Node(val);        // alloc & copy-construct
+        newNode->setNext(posn.getNode());
+        newNode->setPrev(posn.getNode()->getPrev());
+        posn.getNode()->getPrev()->setNext(newNode);
+        posn.getNode()->setPrev(newNode);
+        return iterator(newNode);
+    }
+
+    /* insert a range of elements before the current node */
+    void insert(iterator posn, const_iterator first, const_iterator last) {
+        for ( ; first != last; ++first)
+            insert(posn, *first);
+    }
+
+    /* remove one entry; returns iterator at next node */
+    iterator erase(iterator posn) {
+        _Node* pNext = posn.getNode()->getNext();
+        _Node* pPrev = posn.getNode()->getPrev();
+        pPrev->setNext(pNext);
+        pNext->setPrev(pPrev);
+        delete posn.getNode();
+        return iterator(pNext);
+    }
+
+    /* remove a range of elements */
+    iterator erase(iterator first, iterator last) {
+        while (first != last)
+            erase(first++);     // don't erase than incr later!
+        return iterator(last);
+    }
+
+    /* remove all contents of the list */
+    void clear() {
+        _Node* pCurrent = mpMiddle->getNext();
+        _Node* pNext;
+
+        while (pCurrent != mpMiddle) {
+            pNext = pCurrent->getNext();
+            delete pCurrent;
+            pCurrent = pNext;
+        }
+        mpMiddle->setPrev(mpMiddle);
+        mpMiddle->setNext(mpMiddle);
+    }
+
+    /*
+     * Measure the distance between two iterators.  On exist, "first"
+     * will be equal to "last".  The iterators must refer to the same
+     * list.
+     *
+     * FIXME: This is actually a generic iterator function. It should be a 
+     * template function at the top-level with specializations for things like
+     * vector<>, which can just do pointer math). Here we limit it to
+     * _ListIterator of the same type but different constness.
+     */
+    template<
+        typename U,
+        template <class> class CL,
+        template <class> class CR
+    > 
+    ptrdiff_t distance(
+            _ListIterator<U, CL> first, _ListIterator<U, CR> last) const 
+    {
+        ptrdiff_t count = 0;
+        while (first != last) {
+            ++first;
+            ++count;
+        }
+        return count;
+    }
+
+private:
+    /*
+     * I want a _Node but don't need it to hold valid data.  More
+     * to the point, I don't want T's constructor to fire, since it
+     * might have side-effects or require arguments.  So, we do this
+     * slightly uncouth storage alloc.
+     */
+    void prep() {
+        mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];
+        mpMiddle->setPrev(mpMiddle);
+        mpMiddle->setNext(mpMiddle);
+    }
+
+    /*
+     * This node plays the role of "pointer to head" and "pointer to tail".
+     * It sits in the middle of a circular list of nodes.  The iterator
+     * runs around the circle until it encounters this one.
+     */
+    _Node*      mpMiddle;
+};
+
+/*
+ * Assignment operator.
+ *
+ * The simplest way to do this would be to clear out the target list and
+ * fill it with the source.  However, we can speed things along by
+ * re-using existing elements.
+ */
+template<class T>
+List<T>& List<T>::operator=(const List<T>& right)
+{
+    if (this == &right)
+        return *this;       // self-assignment
+    iterator firstDst = begin();
+    iterator lastDst = end();
+    const_iterator firstSrc = right.begin();
+    const_iterator lastSrc = right.end();
+    while (firstSrc != lastSrc && firstDst != lastDst)
+        *firstDst++ = *firstSrc++;
+    if (firstSrc == lastSrc)        // ran out of elements in source?
+        erase(firstDst, lastDst);   // yes, erase any extras
+    else
+        insert(lastDst, firstSrc, lastSrc);     // copy remaining over
+    return *this;
+}
+
+}; // namespace android
+
+#endif // _LIBS_UTILS_LIST_H
diff --git a/libutils/include/utils/Log.h b/libutils/include/utils/Log.h
new file mode 100644
index 000000000..5276a498d
--- /dev/null
+++ b/libutils/include/utils/Log.h
@@ -0,0 +1,72 @@
+/*
+ * Copyright (C) 2005 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.
+ */
+
+//
+// C/C++ logging functions.  See the logging documentation for API details.
+//
+// We'd like these to be available from C code (in case we import some from
+// somewhere), so this has a C interface.
+//
+// The output will be correct when the log file is shared between multiple
+// threads and/or multiple processes so long as the operating system
+// supports O_APPEND.  These calls have mutex-protected data structures
+// and so are NOT reentrant.  Do not use LOG in a signal handler.
+//
+#ifndef _LIBS_UTILS_LOG_H
+#define _LIBS_UTILS_LOG_H
+
+#include <sys/types.h>
+
+#include <log/log.h>
+
+#ifdef __cplusplus
+
+namespace android {
+
+/*
+ * A very simple utility that yells in the log when an operation takes too long.
+ */
+class LogIfSlow {
+public:
+    LogIfSlow(const char* tag, android_LogPriority priority,
+            int timeoutMillis, const char* message);
+    ~LogIfSlow();
+
+private:
+    const char* const mTag;
+    const android_LogPriority mPriority;
+    const int mTimeoutMillis;
+    const char* const mMessage;
+    const int64_t mStart;
+};
+
+/*
+ * Writes the specified debug log message if this block takes longer than the
+ * specified number of milliseconds to run.  Includes the time actually taken.
+ *
+ * {
+ *     ALOGD_IF_SLOW(50, "Excessive delay doing something.");
+ *     doSomething();
+ * }
+ */
+#define ALOGD_IF_SLOW(timeoutMillis, message) \
+    android::LogIfSlow _logIfSlow(LOG_TAG, ANDROID_LOG_DEBUG, timeoutMillis, message);
+
+} // namespace android
+
+#endif // __cplusplus
+
+#endif // _LIBS_UTILS_LOG_H
diff --git a/libutils/include/utils/Looper.h b/libutils/include/utils/Looper.h
new file mode 100644
index 000000000..a62e67f5f
--- /dev/null
+++ b/libutils/include/utils/Looper.h
@@ -0,0 +1,487 @@
+/*
+ * 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_LOOPER_H
+#define UTILS_LOOPER_H
+
+#include <utils/threads.h>
+#include <utils/RefBase.h>
+#include <utils/KeyedVector.h>
+#include <utils/Timers.h>
+
+#include <sys/epoll.h>
+
+namespace android {
+
+/*
+ * NOTE: Since Looper is used to implement the NDK ALooper, the Looper
+ * enums and the signature of Looper_callbackFunc need to align with
+ * that implementation.
+ */
+
+/**
+ * For callback-based event loops, this is the prototype of the function
+ * that is called when a file descriptor event occurs.
+ * It is given the file descriptor it is associated with,
+ * a bitmask of the poll events that were triggered (typically EVENT_INPUT),
+ * and the data pointer that was originally supplied.
+ *
+ * Implementations should return 1 to continue receiving callbacks, or 0
+ * to have this file descriptor and callback unregistered from the looper.
+ */
+typedef int (*Looper_callbackFunc)(int fd, int events, void* data);
+
+/**
+ * A message that can be posted to a Looper.
+ */
+struct Message {
+    Message() : what(0) { }
+    Message(int w) : what(w) { }
+
+    /* The message type. (interpretation is left up to the handler) */
+    int what;
+};
+
+
+/**
+ * Interface for a Looper message handler.
+ *
+ * The Looper holds a strong reference to the message handler whenever it has
+ * a message to deliver to it.  Make sure to call Looper::removeMessages
+ * to remove any pending messages destined for the handler so that the handler
+ * can be destroyed.
+ */
+class MessageHandler : public virtual RefBase {
+protected:
+    virtual ~MessageHandler();
+
+public:
+    /**
+     * Handles a message.
+     */
+    virtual void handleMessage(const Message& message) = 0;
+};
+
+
+/**
+ * A simple proxy that holds a weak reference to a message handler.
+ */
+class WeakMessageHandler : public MessageHandler {
+protected:
+    virtual ~WeakMessageHandler();
+
+public:
+    WeakMessageHandler(const wp<MessageHandler>& handler);
+    virtual void handleMessage(const Message& message);
+
+private:
+    wp<MessageHandler> mHandler;
+};
+
+
+/**
+ * A looper callback.
+ */
+class LooperCallback : public virtual RefBase {
+protected:
+    virtual ~LooperCallback();
+
+public:
+    /**
+     * Handles a poll event for the given file descriptor.
+     * It is given the file descriptor it is associated with,
+     * a bitmask of the poll events that were triggered (typically EVENT_INPUT),
+     * and the data pointer that was originally supplied.
+     *
+     * Implementations should return 1 to continue receiving callbacks, or 0
+     * to have this file descriptor and callback unregistered from the looper.
+     */
+    virtual int handleEvent(int fd, int events, void* data) = 0;
+};
+
+/**
+ * Wraps a Looper_callbackFunc function pointer.
+ */
+class SimpleLooperCallback : public LooperCallback {
+protected:
+    virtual ~SimpleLooperCallback();
+
+public:
+    SimpleLooperCallback(Looper_callbackFunc callback);
+    virtual int handleEvent(int fd, int events, void* data);
+
+private:
+    Looper_callbackFunc mCallback;
+};
+
+/**
+ * A polling loop that supports monitoring file descriptor events, optionally
+ * using callbacks.  The implementation uses epoll() internally.
+ *
+ * A looper can be associated with a thread although there is no requirement that it must be.
+ */
+class Looper : public RefBase {
+protected:
+    virtual ~Looper();
+
+public:
+    enum {
+        /**
+         * Result from Looper_pollOnce() and Looper_pollAll():
+         * The poll was awoken using wake() before the timeout expired
+         * and no callbacks were executed and no other file descriptors were ready.
+         */
+        POLL_WAKE = -1,
+
+        /**
+         * Result from Looper_pollOnce() and Looper_pollAll():
+         * One or more callbacks were executed.
+         */
+        POLL_CALLBACK = -2,
+
+        /**
+         * Result from Looper_pollOnce() and Looper_pollAll():
+         * The timeout expired.
+         */
+        POLL_TIMEOUT = -3,
+
+        /**
+         * Result from Looper_pollOnce() and Looper_pollAll():
+         * An error occurred.
+         */
+        POLL_ERROR = -4,
+    };
+
+    /**
+     * Flags for file descriptor events that a looper can monitor.
+     *
+     * These flag bits can be combined to monitor multiple events at once.
+     */
+    enum {
+        /**
+         * The file descriptor is available for read operations.
+         */
+        EVENT_INPUT = 1 << 0,
+
+        /**
+         * The file descriptor is available for write operations.
+         */
+        EVENT_OUTPUT = 1 << 1,
+
+        /**
+         * The file descriptor has encountered an error condition.
+         *
+         * The looper always sends notifications about errors; it is not necessary
+         * to specify this event flag in the requested event set.
+         */
+        EVENT_ERROR = 1 << 2,
+
+        /**
+         * The file descriptor was hung up.
+         * For example, indicates that the remote end of a pipe or socket was closed.
+         *
+         * The looper always sends notifications about hangups; it is not necessary
+         * to specify this event flag in the requested event set.
+         */
+        EVENT_HANGUP = 1 << 3,
+
+        /**
+         * The file descriptor is invalid.
+         * For example, the file descriptor was closed prematurely.
+         *
+         * The looper always sends notifications about invalid file descriptors; it is not necessary
+         * to specify this event flag in the requested event set.
+         */
+        EVENT_INVALID = 1 << 4,
+    };
+
+    enum {
+        /**
+         * Option for Looper_prepare: this looper will accept calls to
+         * Looper_addFd() that do not have a callback (that is provide NULL
+         * for the callback).  In this case the caller of Looper_pollOnce()
+         * or Looper_pollAll() MUST check the return from these functions to
+         * discover when data is available on such fds and process it.
+         */
+        PREPARE_ALLOW_NON_CALLBACKS = 1<<0
+    };
+
+    /**
+     * Creates a looper.
+     *
+     * If allowNonCallbaks is true, the looper will allow file descriptors to be
+     * registered without associated callbacks.  This assumes that the caller of
+     * pollOnce() is prepared to handle callback-less events itself.
+     */
+    Looper(bool allowNonCallbacks);
+
+    /**
+     * Returns whether this looper instance allows the registration of file descriptors
+     * using identifiers instead of callbacks.
+     */
+    bool getAllowNonCallbacks() const;
+
+    /**
+     * Waits for events to be available, 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 an event appears.
+     *
+     * Returns POLL_WAKE if the poll was awoken using wake() before
+     * the timeout expired and no callbacks were invoked and no other file
+     * descriptors were ready.
+     *
+     * Returns POLL_CALLBACK if one or more callbacks were invoked.
+     *
+     * Returns POLL_TIMEOUT if there was no data before the given
+     * timeout expired.
+     *
+     * Returns POLL_ERROR if an error occurred.
+     *
+     * Returns a value >= 0 containing an identifier if its file descriptor has data
+     * and it has no callback function (requiring the caller here to handle it).
+     * In this (and only this) case outFd, outEvents and outData will contain the poll
+     * events and data associated with the fd, otherwise they will be set to NULL.
+     *
+     * This method does not return until it has finished invoking the appropriate callbacks
+     * for all file descriptors that were signalled.
+     */
+    int pollOnce(int timeoutMillis, int* outFd, int* outEvents, void** outData);
+    inline int pollOnce(int timeoutMillis) {
+        return pollOnce(timeoutMillis, NULL, NULL, NULL);
+    }
+
+    /**
+     * Like pollOnce(), but performs all pending callbacks until all
+     * data has been consumed or a file descriptor is available with no callback.
+     * This function will never return POLL_CALLBACK.
+     */
+    int pollAll(int timeoutMillis, int* outFd, int* outEvents, void** outData);
+    inline int pollAll(int timeoutMillis) {
+        return pollAll(timeoutMillis, NULL, NULL, NULL);
+    }
+
+    /**
+     * Wakes the poll asynchronously.
+     *
+     * This method can be called on any thread.
+     * This method returns immediately.
+     */
+    void wake();
+
+    /**
+     * Adds a new file descriptor to be polled by the looper.
+     * If the same file descriptor was previously added, it is replaced.
+     *
+     * "fd" is the file descriptor to be added.
+     * "ident" is an identifier for this event, which is returned from pollOnce().
+     * The identifier must be >= 0, or POLL_CALLBACK if providing a non-NULL callback.
+     * "events" are the poll events to wake up on.  Typically this is EVENT_INPUT.
+     * "callback" is the function to call when there is an event on the file descriptor.
+     * "data" is a private data pointer to supply to the callback.
+     *
+     * There are two main uses of this function:
+     *
+     * (1) If "callback" is non-NULL, then this function will be called when there is
+     * data on the file descriptor.  It should execute any events it has pending,
+     * appropriately reading from the file descriptor.  The 'ident' is ignored in this case.
+     *
+     * (2) If "callback" is NULL, the 'ident' will be returned by Looper_pollOnce
+     * when its file descriptor has data available, requiring the caller to take
+     * care of processing it.
+     *
+     * Returns 1 if the file descriptor was added, 0 if the arguments were invalid.
+     *
+     * This method can be called on any thread.
+     * This method may block briefly if it needs to wake the poll.
+     *
+     * The callback may either be specified as a bare function pointer or as a smart
+     * pointer callback object.  The smart pointer should be preferred because it is
+     * easier to avoid races when the callback is removed from a different thread.
+     * See removeFd() for details.
+     */
+    int addFd(int fd, int ident, int events, Looper_callbackFunc callback, void* data);
+    int addFd(int fd, int ident, int events, const sp<LooperCallback>& callback, void* data);
+
+    /**
+     * Removes a previously added file descriptor from the looper.
+     *
+     * When this method returns, it is safe to close the file descriptor since the looper
+     * 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 0 or by calling this method, then it can be guaranteed to not be invoked
+     * again at any later time unless registered anew.
+     *
+     * A simple way to avoid this problem is to use the version of addFd() that takes
+     * a sp<LooperCallback> instead of a bare function pointer.  The LooperCallback will
+     * be released at the appropriate time by the Looper.
+     *
+     * Returns 1 if the file descriptor was removed, 0 if none was previously registered.
+     *
+     * This method can be called on any thread.
+     * This method may block briefly if it needs to wake the poll.
+     */
+    int removeFd(int fd);
+
+    /**
+     * Enqueues a message to be processed by the specified handler.
+     *
+     * The handler must not be null.
+     * This method can be called on any thread.
+     */
+    void sendMessage(const sp<MessageHandler>& handler, const Message& message);
+
+    /**
+     * Enqueues a message to be processed by the specified handler after all pending messages
+     * after the specified delay.
+     *
+     * The time delay is specified in uptime nanoseconds.
+     * The handler must not be null.
+     * This method can be called on any thread.
+     */
+    void sendMessageDelayed(nsecs_t uptimeDelay, const sp<MessageHandler>& handler,
+            const Message& message);
+
+    /**
+     * Enqueues a message to be processed by the specified handler after all pending messages
+     * at the specified time.
+     *
+     * The time is specified in uptime nanoseconds.
+     * The handler must not be null.
+     * This method can be called on any thread.
+     */
+    void sendMessageAtTime(nsecs_t uptime, const sp<MessageHandler>& handler,
+            const Message& message);
+
+    /**
+     * Removes all messages for the specified handler from the queue.
+     *
+     * The handler must not be null.
+     * This method can be called on any thread.
+     */
+    void removeMessages(const sp<MessageHandler>& handler);
+
+    /**
+     * Removes all messages of a particular type for the specified handler from the queue.
+     *
+     * The handler must not be null.
+     * This method can be called on any thread.
+     */
+    void removeMessages(const sp<MessageHandler>& handler, int what);
+
+    /**
+     * Returns whether this looper's thread is currently polling for more work to do.
+     * This is a good signal that the loop is still alive rather than being stuck
+     * handling a callback.  Note that this method is intrinsically racy, since the
+     * state of the loop can change before you get the result back.
+     */
+    bool isPolling() const;
+
+    /**
+     * Prepares a looper associated with the calling thread, and returns it.
+     * If the thread already has a looper, it is returned.  Otherwise, a new
+     * one is created, associated with the thread, and returned.
+     *
+     * The opts may be PREPARE_ALLOW_NON_CALLBACKS or 0.
+     */
+    static sp<Looper> prepare(int opts);
+
+    /**
+     * Sets the given looper to be associated with the calling thread.
+     * If another looper is already associated with the thread, it is replaced.
+     *
+     * If "looper" is NULL, removes the currently associated looper.
+     */
+    static void setForThread(const sp<Looper>& looper);
+
+    /**
+     * Returns the looper associated with the calling thread, or NULL if
+     * there is not one.
+     */
+    static sp<Looper> getForThread();
+
+private:
+    struct Request {
+        int fd;
+        int ident;
+        int events;
+        int seq;
+        sp<LooperCallback> callback;
+        void* data;
+
+        void initEventItem(struct epoll_event* eventItem) const;
+    };
+
+    struct Response {
+        int events;
+        Request request;
+    };
+
+    struct MessageEnvelope {
+        MessageEnvelope() : uptime(0) { }
+
+        MessageEnvelope(nsecs_t u, const sp<MessageHandler> h,
+                const Message& m) : uptime(u), handler(h), message(m) {
+        }
+
+        nsecs_t uptime;
+        sp<MessageHandler> handler;
+        Message message;
+    };
+
+    const bool mAllowNonCallbacks; // immutable
+
+    int mWakeEventFd;  // immutable
+    Mutex mLock;
+
+    Vector<MessageEnvelope> mMessageEnvelopes; // guarded by mLock
+    bool mSendingMessage; // guarded by mLock
+
+    // Whether we are currently waiting for work.  Not protected by a lock,
+    // any use of it is racy anyway.
+    volatile bool mPolling;
+
+    int mEpollFd; // guarded by mLock but only modified on the looper thread
+    bool mEpollRebuildRequired; // guarded by mLock
+
+    // Locked list of file descriptor monitoring requests.
+    KeyedVector<int, Request> mRequests;  // guarded by mLock
+    int mNextRequestSeq;
+
+    // This state is only used privately by pollOnce and does not require a lock since
+    // it runs on a single thread.
+    Vector<Response> mResponses;
+    size_t mResponseIndex;
+    nsecs_t mNextMessageUptime; // set to LLONG_MAX when none
+
+    int pollInner(int timeoutMillis);
+    int removeFd(int fd, int seq);
+    void awoken();
+    void pushResponse(int events, const Request& request);
+    void rebuildEpollLocked();
+    void scheduleEpollRebuildLocked();
+
+    static void initTLSKey();
+    static void threadDestructor(void *st);
+    static void initEpollEvent(struct epoll_event* eventItem);
+};
+
+} // namespace android
+
+#endif // UTILS_LOOPER_H
diff --git a/libutils/include/utils/LruCache.h b/libutils/include/utils/LruCache.h
new file mode 100644
index 000000000..89dccd613
--- /dev/null
+++ b/libutils/include/utils/LruCache.h
@@ -0,0 +1,298 @@
+/*
+ * Copyright (C) 2012 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 ANDROID_UTILS_LRU_CACHE_H
+#define ANDROID_UTILS_LRU_CACHE_H
+
+#include <memory>
+#include <unordered_set>
+
+#include "utils/TypeHelpers.h"  // hash_t
+
+namespace android {
+
+/**
+ * GenerationCache callback used when an item is removed
+ */
+template<typename EntryKey, typename EntryValue>
+class OnEntryRemoved {
+public:
+    virtual ~OnEntryRemoved() { };
+    virtual void operator()(EntryKey& key, EntryValue& value) = 0;
+}; // class OnEntryRemoved
+
+template <typename TKey, typename TValue>
+class LruCache {
+public:
+    explicit LruCache(uint32_t maxCapacity);
+    virtual ~LruCache();
+
+    enum Capacity {
+        kUnlimitedCapacity,
+    };
+
+    void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
+    size_t size() const;
+    const TValue& get(const TKey& key);
+    bool put(const TKey& key, const TValue& value);
+    bool remove(const TKey& key);
+    bool removeOldest();
+    void clear();
+    const TValue& peekOldestValue();
+
+private:
+    LruCache(const LruCache& that);  // disallow copy constructor
+
+    // Super class so that we can have entries having only a key reference, for searches.
+    class KeyedEntry {
+    public:
+        virtual const TKey& getKey() const = 0;
+        // Make sure the right destructor is executed so that keys and values are deleted.
+        virtual ~KeyedEntry() {}
+    };
+
+    class Entry final : public KeyedEntry {
+    public:
+        TKey key;
+        TValue value;
+        Entry* parent;
+        Entry* child;
+
+        Entry(TKey _key, TValue _value) : key(_key), value(_value), parent(NULL), child(NULL) {
+        }
+        const TKey& getKey() const final { return key; }
+    };
+
+    class EntryForSearch : public KeyedEntry {
+    public:
+        const TKey& key;
+        EntryForSearch(const TKey& key_) : key(key_) {
+        }
+        const TKey& getKey() const final { return key; }
+    };
+
+    struct HashForEntry : public std::unary_function<KeyedEntry*, hash_t> {
+        size_t operator() (const KeyedEntry* entry) const {
+            return hash_type(entry->getKey());
+        };
+    };
+
+    struct EqualityForHashedEntries : public std::unary_function<KeyedEntry*, hash_t> {
+        bool operator() (const KeyedEntry* lhs, const KeyedEntry* rhs) const {
+            return lhs->getKey() == rhs->getKey();
+        };
+    };
+
+    // All entries in the set will be Entry*. Using the weaker KeyedEntry as to allow entries
+    // that have only a key reference, for searching.
+    typedef std::unordered_set<KeyedEntry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;
+
+    void attachToCache(Entry& entry);
+    void detachFromCache(Entry& entry);
+
+    typename LruCacheSet::iterator findByKey(const TKey& key) {
+        EntryForSearch entryForSearch(key);
+        typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
+        return result;
+    }
+
+    std::unique_ptr<LruCacheSet> mSet;
+    OnEntryRemoved<TKey, TValue>* mListener;
+    Entry* mOldest;
+    Entry* mYoungest;
+    uint32_t mMaxCapacity;
+    TValue mNullValue;
+
+public:
+    // To be used like:
+    // while (it.next()) {
+    //   it.value(); it.key();
+    // }
+    class Iterator {
+    public:
+        Iterator(const LruCache<TKey, TValue>& cache):
+                mCache(cache), mIterator(mCache.mSet->begin()), mBeginReturned(false) {
+        }
+
+        bool next() {
+            if (mIterator == mCache.mSet->end()) {
+                return false;
+            }
+            if (!mBeginReturned) {
+                // mIterator has been initialized to the beginning and
+                // hasn't been returned. Do not advance:
+                mBeginReturned = true;
+            } else {
+                std::advance(mIterator, 1);
+            }
+            bool ret = (mIterator != mCache.mSet->end());
+            return ret;
+        }
+
+        const TValue& value() const {
+            // All the elements in the set are of type Entry. See comment in the definition
+            // of LruCacheSet above.
+            return reinterpret_cast<Entry *>(*mIterator)->value;
+        }
+
+        const TKey& key() const {
+            return (*mIterator)->getKey();
+        }
+    private:
+        const LruCache<TKey, TValue>& mCache;
+        typename LruCacheSet::iterator mIterator;
+        bool mBeginReturned;
+    };
+};
+
+// Implementation is here, because it's fully templated
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
+    : mSet(new LruCacheSet())
+    , mListener(NULL)
+    , mOldest(NULL)
+    , mYoungest(NULL)
+    , mMaxCapacity(maxCapacity)
+    , mNullValue(0) {
+    mSet->max_load_factor(1.0);
+};
+
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::~LruCache() {
+    // Need to delete created entries.
+    clear();
+};
+
+template<typename K, typename V>
+void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
+    mListener = listener;
+}
+
+template <typename TKey, typename TValue>
+size_t LruCache<TKey, TValue>::size() const {
+    return mSet->size();
+}
+
+template <typename TKey, typename TValue>
+const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
+    typename LruCacheSet::const_iterator find_result = findByKey(key);
+    if (find_result == mSet->end()) {
+        return mNullValue;
+    }
+    // All the elements in the set are of type Entry. See comment in the definition
+    // of LruCacheSet above.
+    Entry *entry = reinterpret_cast<Entry*>(*find_result);
+    detachFromCache(*entry);
+    attachToCache(*entry);
+    return entry->value;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
+    if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
+        removeOldest();
+    }
+
+    if (findByKey(key) != mSet->end()) {
+        return false;
+    }
+
+    Entry* newEntry = new Entry(key, value);
+    mSet->insert(newEntry);
+    attachToCache(*newEntry);
+    return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::remove(const TKey& key) {
+    typename LruCacheSet::const_iterator find_result = findByKey(key);
+    if (find_result == mSet->end()) {
+        return false;
+    }
+    // All the elements in the set are of type Entry. See comment in the definition
+    // of LruCacheSet above.
+    Entry* entry = reinterpret_cast<Entry*>(*find_result);
+    mSet->erase(entry);
+    if (mListener) {
+        (*mListener)(entry->key, entry->value);
+    }
+    detachFromCache(*entry);
+    delete entry;
+    return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::removeOldest() {
+    if (mOldest != NULL) {
+        return remove(mOldest->key);
+        // TODO: should probably abort if false
+    }
+    return false;
+}
+
+template <typename TKey, typename TValue>
+const TValue& LruCache<TKey, TValue>::peekOldestValue() {
+    if (mOldest) {
+        return mOldest->value;
+    }
+    return mNullValue;
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::clear() {
+    if (mListener) {
+        for (Entry* p = mOldest; p != NULL; p = p->child) {
+            (*mListener)(p->key, p->value);
+        }
+    }
+    mYoungest = NULL;
+    mOldest = NULL;
+    for (auto entry : *mSet.get()) {
+        delete entry;
+    }
+    mSet->clear();
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
+    if (mYoungest == NULL) {
+        mYoungest = mOldest = &entry;
+    } else {
+        entry.parent = mYoungest;
+        mYoungest->child = &entry;
+        mYoungest = &entry;
+    }
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
+    if (entry.parent != NULL) {
+        entry.parent->child = entry.child;
+    } else {
+        mOldest = entry.child;
+    }
+    if (entry.child != NULL) {
+        entry.child->parent = entry.parent;
+    } else {
+        mYoungest = entry.parent;
+    }
+
+    entry.parent = NULL;
+    entry.child = NULL;
+}
+
+}
+#endif // ANDROID_UTILS_LRU_CACHE_H
diff --git a/libutils/include/utils/Mutex.h b/libutils/include/utils/Mutex.h
new file mode 100644
index 000000000..d106185f0
--- /dev/null
+++ b/libutils/include/utils/Mutex.h
@@ -0,0 +1,167 @@
+/*
+ * Copyright (C) 2007 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 _LIBS_UTILS_MUTEX_H
+#define _LIBS_UTILS_MUTEX_H
+
+#include <stdint.h>
+#include <sys/types.h>
+#include <time.h>
+
+#if !defined(_WIN32)
+# include <pthread.h>
+#endif
+
+#include <utils/Errors.h>
+#include <utils/Timers.h>
+
+// ---------------------------------------------------------------------------
+namespace android {
+// ---------------------------------------------------------------------------
+
+class Condition;
+
+/*
+ * NOTE: This class is for code that builds on Win32.  Its usage is
+ * deprecated for code which doesn't build for Win32.  New code which
+ * doesn't build for Win32 should use std::mutex and std::lock_guard instead.
+ *
+ * Simple mutex class.  The implementation is system-dependent.
+ *
+ * The mutex must be unlocked by the thread that locked it.  They are not
+ * recursive, i.e. the same thread can't lock it multiple times.
+ */
+class Mutex {
+public:
+    enum {
+        PRIVATE = 0,
+        SHARED = 1
+    };
+
+                Mutex();
+    explicit    Mutex(const char* name);
+    explicit    Mutex(int type, const char* name = NULL);
+                ~Mutex();
+
+    // lock or unlock the mutex
+    status_t    lock();
+    void        unlock();
+
+    // lock if possible; returns 0 on success, error otherwise
+    status_t    tryLock();
+
+#if defined(__ANDROID__)
+    // Lock the mutex, but don't wait longer than timeoutNs (relative time).
+    // Returns 0 on success, TIMED_OUT for failure due to timeout expiration.
+    //
+    // OSX doesn't have pthread_mutex_timedlock() or equivalent. To keep
+    // capabilities consistent across host OSes, this method is only available
+    // when building Android binaries.
+    //
+    // FIXME?: pthread_mutex_timedlock is based on CLOCK_REALTIME,
+    // which is subject to NTP adjustments, and includes time during suspend,
+    // so a timeout may occur even though no processes could run.
+    // Not holding a partial wakelock may lead to a system suspend.
+    status_t    timedLock(nsecs_t timeoutNs);
+#endif
+
+    // Manages the mutex automatically. It'll be locked when Autolock is
+    // constructed and released when Autolock goes out of scope.
+    class Autolock {
+    public:
+        inline explicit Autolock(Mutex& mutex) : mLock(mutex)  { mLock.lock(); }
+        inline explicit Autolock(Mutex* mutex) : mLock(*mutex) { mLock.lock(); }
+        inline ~Autolock() { mLock.unlock(); }
+    private:
+        Mutex& mLock;
+    };
+
+private:
+    friend class Condition;
+
+    // A mutex cannot be copied
+                Mutex(const Mutex&);
+    Mutex&      operator = (const Mutex&);
+
+#if !defined(_WIN32)
+    pthread_mutex_t mMutex;
+#else
+    void    _init();
+    void*   mState;
+#endif
+};
+
+// ---------------------------------------------------------------------------
+
+#if !defined(_WIN32)
+
+inline Mutex::Mutex() {
+    pthread_mutex_init(&mMutex, NULL);
+}
+inline Mutex::Mutex(__attribute__((unused)) const char* name) {
+    pthread_mutex_init(&mMutex, NULL);
+}
+inline Mutex::Mutex(int type, __attribute__((unused)) const char* name) {
+    if (type == SHARED) {
+        pthread_mutexattr_t attr;
+        pthread_mutexattr_init(&attr);
+        pthread_mutexattr_setpshared(&attr, PTHREAD_PROCESS_SHARED);
+        pthread_mutex_init(&mMutex, &attr);
+        pthread_mutexattr_destroy(&attr);
+    } else {
+        pthread_mutex_init(&mMutex, NULL);
+    }
+}
+inline Mutex::~Mutex() {
+    pthread_mutex_destroy(&mMutex);
+}
+inline status_t Mutex::lock() {
+    return -pthread_mutex_lock(&mMutex);
+}
+inline void Mutex::unlock() {
+    pthread_mutex_unlock(&mMutex);
+}
+inline status_t Mutex::tryLock() {
+    return -pthread_mutex_trylock(&mMutex);
+}
+#if defined(__ANDROID__)
+inline status_t Mutex::timedLock(nsecs_t timeoutNs) {
+    timeoutNs += systemTime(SYSTEM_TIME_REALTIME);
+    const struct timespec ts = {
+        /* .tv_sec = */ static_cast<time_t>(timeoutNs / 1000000000),
+        /* .tv_nsec = */ static_cast<long>(timeoutNs % 1000000000),
+    };
+    return -pthread_mutex_timedlock(&mMutex, &ts);
+}
+#endif
+
+#endif // !defined(_WIN32)
+
+// ---------------------------------------------------------------------------
+
+/*
+ * Automatic mutex.  Declare one of these at the top of a function.
+ * When the function returns, it will go out of scope, and release the
+ * mutex.
+ */
+
+typedef Mutex::Autolock AutoMutex;
+
+// ---------------------------------------------------------------------------
+}; // namespace android
+// ---------------------------------------------------------------------------
+
+#endif // _LIBS_UTILS_MUTEX_H
diff --git a/libutils/include/utils/NativeHandle.h b/libutils/include/utils/NativeHandle.h
new file mode 100644
index 000000000..b82516879
--- /dev/null
+++ b/libutils/include/utils/NativeHandle.h
@@ -0,0 +1,56 @@
+/*
+ * Copyright 2014 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 ANDROID_NATIVE_HANDLE_H
+#define ANDROID_NATIVE_HANDLE_H
+
+#include <utils/RefBase.h>
+#include <utils/StrongPointer.h>
+
+typedef struct native_handle native_handle_t;
+
+namespace android {
+
+class NativeHandle: public LightRefBase<NativeHandle> {
+public:
+    // Create a refcounted wrapper around a native_handle_t, and declare
+    // whether the wrapper owns the handle (so that it should clean up the
+    // handle upon destruction) or not.
+    // If handle is NULL, no NativeHandle will be created.
+    static sp<NativeHandle> create(native_handle_t* handle, bool ownsHandle);
+
+    const native_handle_t* handle() const {
+        return mHandle;
+    }
+
+private:
+    // for access to the destructor
+    friend class LightRefBase<NativeHandle>;
+
+    NativeHandle(native_handle_t* handle, bool ownsHandle);
+    virtual ~NativeHandle();
+
+    native_handle_t* mHandle;
+    bool mOwnsHandle;
+
+    // non-copyable
+    NativeHandle(const NativeHandle&);
+    NativeHandle& operator=(const NativeHandle&);
+};
+
+} // namespace android
+
+#endif // ANDROID_NATIVE_HANDLE_H
diff --git a/libutils/include/utils/Printer.h b/libutils/include/utils/Printer.h
new file mode 100644
index 000000000..bb6628767
--- /dev/null
+++ b/libutils/include/utils/Printer.h
@@ -0,0 +1,119 @@
+/*
+ * Copyright (C) 2013 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 ANDROID_PRINTER_H
+#define ANDROID_PRINTER_H
+
+#include <android/log.h>
+
+namespace android {
+
+// Interface for printing to an arbitrary data stream
+class Printer {
+public:
+    // Print a new line specified by 'string'. \n is appended automatically.
+    // -- Assumes that the string has no new line in it.
+    virtual void printLine(const char* string = "") = 0;
+
+    // Print a new line specified by the format string. \n is appended automatically.
+    // -- Assumes that the resulting string has no new line in it.
+    virtual void printFormatLine(const char* format, ...) __attribute__((format (printf, 2, 3)));
+
+protected:
+    Printer();
+    virtual ~Printer();
+}; // class Printer
+
+// Print to logcat
+class LogPrinter : public Printer {
+public:
+    // Create a printer using the specified logcat and log priority
+    // - Unless ignoreBlankLines is false, print blank lines to logcat
+    // (Note that the default ALOG behavior is to ignore blank lines)
+    LogPrinter(const char* logtag,
+               android_LogPriority priority = ANDROID_LOG_DEBUG,
+               const char* prefix = 0,
+               bool ignoreBlankLines = false);
+
+    // Print the specified line to logcat. No \n at the end is necessary.
+    virtual void printLine(const char* string);
+
+private:
+    void printRaw(const char* string);
+
+    const char* mLogTag;
+    android_LogPriority mPriority;
+    const char* mPrefix;
+    bool mIgnoreBlankLines;
+}; // class LogPrinter
+
+// Print to a file descriptor
+class FdPrinter : public Printer {
+public:
+    // Create a printer using the specified file descriptor.
+    // - Each line will be prefixed with 'indent' number of blank spaces.
+    // - In addition, each line will be prefixed with the 'prefix' string.
+    FdPrinter(int fd, unsigned int indent = 0, const char* prefix = 0);
+
+    // Print the specified line to the file descriptor. \n is appended automatically.
+    virtual void printLine(const char* string);
+
+private:
+    enum {
+        MAX_FORMAT_STRING = 20,
+    };
+
+    int mFd;
+    unsigned int mIndent;
+    const char* mPrefix;
+    char mFormatString[MAX_FORMAT_STRING];
+}; // class FdPrinter
+
+class String8;
+
+// Print to a String8
+class String8Printer : public Printer {
+public:
+    // Create a printer using the specified String8 as the target.
+    // - In addition, each line will be prefixed with the 'prefix' string.
+    // - target's memory lifetime must be a superset of this String8Printer.
+    String8Printer(String8* target, const char* prefix = 0);
+
+    // Append the specified line to the String8. \n is appended automatically.
+    virtual void printLine(const char* string);
+
+private:
+    String8* mTarget;
+    const char* mPrefix;
+}; // class String8Printer
+
+// Print to an existing Printer by adding a prefix to each line
+class PrefixPrinter : public Printer {
+public:
+    // Create a printer using the specified printer as the target.
+    PrefixPrinter(Printer& printer, const char* prefix);
+
+    // Print the line (prefixed with prefix) using the printer.
+    virtual void printLine(const char* string);
+
+private:
+    Printer& mPrinter;
+    const char* mPrefix;
+};
+
+}; // namespace android
+
+#endif // ANDROID_PRINTER_H
diff --git a/libutils/include/utils/ProcessCallStack.h b/libutils/include/utils/ProcessCallStack.h
new file mode 100644
index 000000000..32458b8b1
--- /dev/null
+++ b/libutils/include/utils/ProcessCallStack.h
@@ -0,0 +1,79 @@
+/*
+ * Copyright (C) 2013 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 ANDROID_PROCESS_CALLSTACK_H
+#define ANDROID_PROCESS_CALLSTACK_H
+
+#include <utils/CallStack.h>
+#include <android/log.h>
+#include <utils/KeyedVector.h>
+#include <utils/String8.h>
+
+#include <time.h>
+#include <sys/types.h>
+
+namespace android {
+
+class Printer;
+
+// Collect/print the call stack (function, file, line) traces for all threads in a process.
+class ProcessCallStack {
+public:
+    // Create an empty call stack. No-op.
+    ProcessCallStack();
+    // Copy the existing process callstack (no other side effects).
+    ProcessCallStack(const ProcessCallStack& rhs);
+    ~ProcessCallStack();
+
+    // Immediately collect the stack traces for all threads.
+    void update();
+
+    // Print all stack traces to the log using the supplied logtag.
+    void log(const char* logtag, android_LogPriority priority = ANDROID_LOG_DEBUG,
+             const char* prefix = 0) const;
+
+    // Dump all stack traces to the specified file descriptor.
+    void dump(int fd, int indent = 0, const char* prefix = 0) const;
+
+    // Return a string (possibly very long) containing all the stack traces.
+    String8 toString(const char* prefix = 0) const;
+
+    // Dump a serialized representation of all the stack traces to the specified printer.
+    void print(Printer& printer) const;
+
+    // Get the number of threads whose stack traces were collected.
+    size_t size() const;
+
+private:
+    void printInternal(Printer& printer, Printer& csPrinter) const;
+
+    // Reset the process's stack frames and metadata.
+    void clear();
+
+    struct ThreadInfo {
+        CallStack callStack;
+        String8 threadName;
+    };
+
+    // tid -> ThreadInfo
+    KeyedVector<pid_t, ThreadInfo> mThreadMap;
+    // Time that update() was last called
+    struct tm mTimeUpdated;
+};
+
+}; // namespace android
+
+#endif // ANDROID_PROCESS_CALLSTACK_H
diff --git a/libutils/include/utils/PropertyMap.h b/libutils/include/utils/PropertyMap.h
new file mode 100644
index 000000000..a9e674f9a
--- /dev/null
+++ b/libutils/include/utils/PropertyMap.h
@@ -0,0 +1,106 @@
+/*
+ * 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_PROPERTY_MAP_H
+#define _UTILS_PROPERTY_MAP_H
+
+#include <utils/KeyedVector.h>
+#include <utils/String8.h>
+#include <utils/Errors.h>
+#include <utils/Tokenizer.h>
+
+namespace android {
+
+/*
+ * Provides a mechanism for passing around string-based property key / value pairs
+ * and loading them from property files.
+ *
+ * The property files have the following simple structure:
+ *
+ * # Comment
+ * key = value
+ *
+ * Keys and values are any sequence of printable ASCII characters.
+ * The '=' separates the key from the value.
+ * The key and value may not contain whitespace.
+ *
+ * The '\' character is reserved for escape sequences and is not currently supported.
+ * The '"" character is reserved for quoting and is not currently supported.
+ * Files that contain the '\' or '"' character will fail to parse.
+ *
+ * The file must not contain duplicate keys.
+ *
+ * TODO Support escape sequences and quoted values when needed.
+ */
+class PropertyMap {
+public:
+    /* Creates an empty property map. */
+    PropertyMap();
+    ~PropertyMap();
+
+    /* Clears the property map. */
+    void clear();
+
+    /* Adds a property.
+     * Replaces the property with the same key if it is already present.
+     */
+    void addProperty(const String8& key, const String8& value);
+
+    /* Returns true if the property map contains the specified key. */
+    bool hasProperty(const String8& key) const;
+
+    /* Gets the value of a property and parses it.
+     * Returns true and sets outValue if the key was found and its value was parsed successfully.
+     * Otherwise returns false and does not modify outValue.  (Also logs a warning.)
+     */
+    bool tryGetProperty(const String8& key, String8& outValue) const;
+    bool tryGetProperty(const String8& key, bool& outValue) const;
+    bool tryGetProperty(const String8& key, int32_t& outValue) const;
+    bool tryGetProperty(const String8& key, float& outValue) const;
+
+    /* Adds all values from the specified property map. */
+    void addAll(const PropertyMap* map);
+
+    /* Gets the underlying property map. */
+    inline const KeyedVector<String8, String8>& getProperties() const { return mProperties; }
+
+    /* Loads a property map from a file. */
+    static status_t load(const String8& filename, PropertyMap** outMap);
+
+private:
+    class Parser {
+        PropertyMap* mMap;
+        Tokenizer* mTokenizer;
+
+    public:
+        Parser(PropertyMap* map, Tokenizer* tokenizer);
+        ~Parser();
+        status_t parse();
+
+    private:
+        status_t parseType();
+        status_t parseKey();
+        status_t parseKeyProperty();
+        status_t parseModifier(const String8& token, int32_t* outMetaState);
+        status_t parseCharacterLiteral(char16_t* outCharacter);
+    };
+
+    KeyedVector<String8, String8> mProperties;
+};
+
+} // namespace android
+
+#endif // _UTILS_PROPERTY_MAP_H
diff --git a/libutils/include/utils/RWLock.h b/libutils/include/utils/RWLock.h
new file mode 100644
index 000000000..d5b81d3a8
--- /dev/null
+++ b/libutils/include/utils/RWLock.h
@@ -0,0 +1,126 @@
+/*
+ * Copyright (C) 2007 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 _LIBS_UTILS_RWLOCK_H
+#define _LIBS_UTILS_RWLOCK_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+#if !defined(_WIN32)
+# include <pthread.h>
+#endif
+
+#include <utils/Errors.h>
+#include <utils/ThreadDefs.h>
+
+// ---------------------------------------------------------------------------
+namespace android {
+// ---------------------------------------------------------------------------
+
+#if !defined(_WIN32)
+
+/*
+ * Simple mutex class.  The implementation is system-dependent.
+ *
+ * The mutex must be unlocked by the thread that locked it.  They are not
+ * recursive, i.e. the same thread can't lock it multiple times.
+ */
+class RWLock {
+public:
+    enum {
+        PRIVATE = 0,
+        SHARED = 1
+    };
+
+                RWLock();
+    explicit    RWLock(const char* name);
+    explicit    RWLock(int type, const char* name = NULL);
+                ~RWLock();
+
+    status_t    readLock();
+    status_t    tryReadLock();
+    status_t    writeLock();
+    status_t    tryWriteLock();
+    void        unlock();
+
+    class AutoRLock {
+    public:
+        inline explicit AutoRLock(RWLock& rwlock) : mLock(rwlock)  { mLock.readLock(); }
+        inline ~AutoRLock() { mLock.unlock(); }
+    private:
+        RWLock& mLock;
+    };
+
+    class AutoWLock {
+    public:
+        inline explicit AutoWLock(RWLock& rwlock) : mLock(rwlock)  { mLock.writeLock(); }
+        inline ~AutoWLock() { mLock.unlock(); }
+    private:
+        RWLock& mLock;
+    };
+
+private:
+    // A RWLock cannot be copied
+                RWLock(const RWLock&);
+   RWLock&      operator = (const RWLock&);
+
+   pthread_rwlock_t mRWLock;
+};
+
+inline RWLock::RWLock() {
+    pthread_rwlock_init(&mRWLock, NULL);
+}
+inline RWLock::RWLock(__attribute__((unused)) const char* name) {
+    pthread_rwlock_init(&mRWLock, NULL);
+}
+inline RWLock::RWLock(int type, __attribute__((unused)) const char* name) {
+    if (type == SHARED) {
+        pthread_rwlockattr_t attr;
+        pthread_rwlockattr_init(&attr);
+        pthread_rwlockattr_setpshared(&attr, PTHREAD_PROCESS_SHARED);
+        pthread_rwlock_init(&mRWLock, &attr);
+        pthread_rwlockattr_destroy(&attr);
+    } else {
+        pthread_rwlock_init(&mRWLock, NULL);
+    }
+}
+inline RWLock::~RWLock() {
+    pthread_rwlock_destroy(&mRWLock);
+}
+inline status_t RWLock::readLock() {
+    return -pthread_rwlock_rdlock(&mRWLock);
+}
+inline status_t RWLock::tryReadLock() {
+    return -pthread_rwlock_tryrdlock(&mRWLock);
+}
+inline status_t RWLock::writeLock() {
+    return -pthread_rwlock_wrlock(&mRWLock);
+}
+inline status_t RWLock::tryWriteLock() {
+    return -pthread_rwlock_trywrlock(&mRWLock);
+}
+inline void RWLock::unlock() {
+    pthread_rwlock_unlock(&mRWLock);
+}
+
+#endif // !defined(_WIN32)
+
+// ---------------------------------------------------------------------------
+}; // namespace android
+// ---------------------------------------------------------------------------
+
+#endif // _LIBS_UTILS_RWLOCK_H
diff --git a/libutils/include/utils/RefBase.h b/libutils/include/utils/RefBase.h
new file mode 100644
index 000000000..36016cde6
--- /dev/null
+++ b/libutils/include/utils/RefBase.h
@@ -0,0 +1,731 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+
+// SOME COMMENTS ABOUT USAGE:
+
+// This provides primarily wp<> weak pointer types and RefBase, which work
+// together with sp<> from <StrongPointer.h>.
+
+// sp<> (and wp<>) are a type of smart pointer that use a well defined protocol
+// to operate. As long as the object they are templated with implements that
+// protocol, these smart pointers work. In several places the platform
+// instantiates sp<> with non-RefBase objects; the two are not tied to each
+// other.
+
+// RefBase is such an implementation and it supports strong pointers, weak
+// pointers and some magic features for the binder.
+
+// So, when using RefBase objects, you have the ability to use strong and weak
+// pointers through sp<> and wp<>.
+
+// Normally, when the last strong pointer goes away, the object is destroyed,
+// i.e. it's destructor is called. HOWEVER, parts of its associated memory is not
+// freed until the last weak pointer is released.
+
+// Weak pointers are essentially "safe" pointers. They are always safe to
+// access through promote(). They may return nullptr if the object was
+// destroyed because it ran out of strong pointers. This makes them good candidates
+// for keys in a cache for instance.
+
+// Weak pointers remain valid for comparison purposes even after the underlying
+// object has been destroyed. Even if object A is destroyed and its memory reused
+// for B, A remaining weak pointer to A will not compare equal to one to B.
+// This again makes them attractive for use as keys.
+
+// How is this supposed / intended to be used?
+
+// Our recommendation is to use strong references (sp<>) when there is an
+// ownership relation. e.g. when an object "owns" another one, use a strong
+// ref. And of course use strong refs as arguments of functions (it's extremely
+// rare that a function will take a wp<>).
+
+// Typically a newly allocated object will immediately be used to initialize
+// a strong pointer, which may then be used to construct or assign to other
+// strong and weak pointers.
+
+// Use weak references when there are no ownership relation. e.g. the keys in a
+// cache (you cannot use plain pointers because there is no safe way to acquire
+// a strong reference from a vanilla pointer).
+
+// This implies that two objects should never (or very rarely) have sp<> on
+// each other, because they can't both own each other.
+
+
+// Caveats with reference counting
+
+// Obviously, circular strong references are a big problem; this creates leaks
+// and it's hard to debug -- except it's in fact really easy because RefBase has
+// tons of debugging code for that. It can basically tell you exactly where the
+// leak is.
+
+// Another problem has to do with destructors with side effects. You must
+// assume that the destructor of reference counted objects can be called AT ANY
+// TIME. For instance code as simple as this:
+
+// void setStuff(const sp<Stuff>& stuff) {
+//   std::lock_guard<std::mutex> lock(mMutex);
+//   mStuff = stuff;
+// }
+
+// is very dangerous. This code WILL deadlock one day or another.
+
+// What isn't obvious is that ~Stuff() can be called as a result of the
+// assignment. And it gets called with the lock held. First of all, the lock is
+// protecting mStuff, not ~Stuff(). Secondly, if ~Stuff() uses its own internal
+// mutex, now you have mutex ordering issues.  Even worse, if ~Stuff() is
+// virtual, now you're calling into "user" code (potentially), by that, I mean,
+// code you didn't even write.
+
+// A correct way to write this code is something like:
+
+// void setStuff(const sp<Stuff>& stuff) {
+//   std::unique_lock<std::mutex> lock(mMutex);
+//   sp<Stuff> hold = mStuff;
+//   mStuff = stuff;
+//   lock.unlock();
+// }
+
+// More importantly, reference counted objects should do as little work as
+// possible in their destructor, or at least be mindful that their destructor
+// could be called from very weird and unintended places.
+
+// Other more specific restrictions for wp<> and sp<>:
+
+// Do not construct a strong pointer to "this" in an object's constructor.
+// The onFirstRef() callback would be made on an incompletely constructed
+// object.
+// Construction of a weak pointer to "this" in an object's constructor is also
+// discouraged. But the implementation was recently changed so that, in the
+// absence of extendObjectLifetime() calls, weak pointers no longer impact
+// object lifetime, and hence this no longer risks premature deallocation,
+// and hence usually works correctly.
+
+// Such strong or weak pointers can be safely created in the RefBase onFirstRef()
+// callback.
+
+// Use of wp::unsafe_get() for any purpose other than debugging is almost
+// always wrong.  Unless you somehow know that there is a longer-lived sp<> to
+// the same object, it may well return a pointer to a deallocated object that
+// has since been reallocated for a different purpose. (And if you know there
+// is a longer-lived sp<>, why not use an sp<> directly?) A wp<> should only be
+// dereferenced by using promote().
+
+// Any object inheriting from RefBase should always be destroyed as the result
+// of a reference count decrement, not via any other means.  Such objects
+// should never be stack allocated, or appear directly as data members in other
+// objects. Objects inheriting from RefBase should have their strong reference
+// count incremented as soon as possible after construction. Usually this
+// will be done via construction of an sp<> to the object, but may instead
+// involve other means of calling RefBase::incStrong().
+// Explicitly deleting or otherwise destroying a RefBase object with outstanding
+// wp<> or sp<> pointers to it will result in an abort or heap corruption.
+
+// It is particularly important not to mix sp<> and direct storage management
+// since the sp from raw pointer constructor is implicit. Thus if a RefBase-
+// -derived object of type T is managed without ever incrementing its strong
+// count, and accidentally passed to f(sp<T>), a strong pointer to the object
+// will be temporarily constructed and destroyed, prematurely deallocating the
+// object, and resulting in heap corruption. None of this would be easily
+// visible in the source.
+
+// Extra Features:
+
+// RefBase::extendObjectLifetime() can be used to prevent destruction of the
+// object while there are still weak references. This is really special purpose
+// functionality to support Binder.
+
+// Wp::promote(), implemented via the attemptIncStrong() member function, is
+// used to try to convert a weak pointer back to a strong pointer.  It's the
+// normal way to try to access the fields of an object referenced only through
+// a wp<>.  Binder code also sometimes uses attemptIncStrong() directly.
+
+// RefBase provides a number of additional callbacks for certain reference count
+// events, as well as some debugging facilities.
+
+// Debugging support can be enabled by turning on DEBUG_REFS in RefBase.cpp.
+// Otherwise little checking is provided.
+
+// Thread safety:
+
+// Like std::shared_ptr, sp<> and wp<> allow concurrent accesses to DIFFERENT
+// sp<> and wp<> instances that happen to refer to the same underlying object.
+// They do NOT support concurrent access (where at least one access is a write)
+// to THE SAME sp<> or wp<>.  In effect, their thread-safety properties are
+// exactly like those of T*, NOT atomic<T*>.
+
+#ifndef ANDROID_REF_BASE_H
+#define ANDROID_REF_BASE_H
+
+#include <atomic>
+
+#include <stdint.h>
+#include <sys/types.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <utils/StrongPointer.h>
+#include <utils/TypeHelpers.h>
+
+// ---------------------------------------------------------------------------
+namespace android {
+
+class TextOutput;
+TextOutput& printWeakPointer(TextOutput& to, const void* val);
+
+// ---------------------------------------------------------------------------
+
+#define COMPARE_WEAK(_op_)                                      \
+inline bool operator _op_ (const sp<T>& o) const {              \
+    return m_ptr _op_ o.m_ptr;                                  \
+}                                                               \
+inline bool operator _op_ (const T* o) const {                  \
+    return m_ptr _op_ o;                                        \
+}                                                               \
+template<typename U>                                            \
+inline bool operator _op_ (const sp<U>& o) const {              \
+    return m_ptr _op_ o.m_ptr;                                  \
+}                                                               \
+template<typename U>                                            \
+inline bool operator _op_ (const U* o) const {                  \
+    return m_ptr _op_ o;                                        \
+}
+
+// ---------------------------------------------------------------------------
+
+// RefererenceRenamer is pure abstract, there is no virtual method
+// implementation to put in a translation unit in order to silence the
+// weak vtables warning.
+#if defined(__clang__)
+#pragma clang diagnostic push
+#pragma clang diagnostic ignored "-Wweak-vtables"
+#endif
+
+class ReferenceRenamer {
+protected:
+    // destructor is purposedly not virtual so we avoid code overhead from
+    // subclasses; we have to make it protected to guarantee that it
+    // cannot be called from this base class (and to make strict compilers
+    // happy).
+    ~ReferenceRenamer() { }
+public:
+    virtual void operator()(size_t i) const = 0;
+};
+
+#if defined(__clang__)
+#pragma clang diagnostic pop
+#endif
+
+// ---------------------------------------------------------------------------
+
+class RefBase
+{
+public:
+            void            incStrong(const void* id) const;
+            void            decStrong(const void* id) const;
+    
+            void            forceIncStrong(const void* id) const;
+
+            //! DEBUGGING ONLY: Get current strong ref count.
+            int32_t         getStrongCount() const;
+
+    class weakref_type
+    {
+    public:
+        RefBase*            refBase() const;
+        
+        void                incWeak(const void* id);
+        void                decWeak(const void* id);
+        
+        // acquires a strong reference if there is already one.
+        bool                attemptIncStrong(const void* id);
+        
+        // acquires a weak reference if there is already one.
+        // This is not always safe. see ProcessState.cpp and BpBinder.cpp
+        // for proper use.
+        bool                attemptIncWeak(const void* id);
+
+        //! DEBUGGING ONLY: Get current weak ref count.
+        int32_t             getWeakCount() const;
+
+        //! DEBUGGING ONLY: Print references held on object.
+        void                printRefs() const;
+
+        //! DEBUGGING ONLY: Enable tracking for this object.
+        // enable -- enable/disable tracking
+        // retain -- when tracking is enable, if true, then we save a stack trace
+        //           for each reference and dereference; when retain == false, we
+        //           match up references and dereferences and keep only the 
+        //           outstanding ones.
+        
+        void                trackMe(bool enable, bool retain);
+    };
+    
+            weakref_type*   createWeak(const void* id) const;
+            
+            weakref_type*   getWeakRefs() const;
+
+            //! DEBUGGING ONLY: Print references held on object.
+    inline  void            printRefs() const { getWeakRefs()->printRefs(); }
+
+            //! DEBUGGING ONLY: Enable tracking of object.
+    inline  void            trackMe(bool enable, bool retain)
+    { 
+        getWeakRefs()->trackMe(enable, retain); 
+    }
+
+    typedef RefBase basetype;
+
+protected:
+                            RefBase();
+    virtual                 ~RefBase();
+    
+    //! Flags for extendObjectLifetime()
+    enum {
+        OBJECT_LIFETIME_STRONG  = 0x0000,
+        OBJECT_LIFETIME_WEAK    = 0x0001,
+        OBJECT_LIFETIME_MASK    = 0x0001
+    };
+    
+            void            extendObjectLifetime(int32_t mode);
+            
+    //! Flags for onIncStrongAttempted()
+    enum {
+        FIRST_INC_STRONG = 0x0001
+    };
+    
+    // Invoked after creation of initial strong pointer/reference.
+    virtual void            onFirstRef();
+    // Invoked when either the last strong reference goes away, or we need to undo
+    // the effect of an unnecessary onIncStrongAttempted.
+    virtual void            onLastStrongRef(const void* id);
+    // Only called in OBJECT_LIFETIME_WEAK case.  Returns true if OK to promote to
+    // strong reference. May have side effects if it returns true.
+    // The first flags argument is always FIRST_INC_STRONG.
+    // TODO: Remove initial flag argument.
+    virtual bool            onIncStrongAttempted(uint32_t flags, const void* id);
+    // Invoked in the OBJECT_LIFETIME_WEAK case when the last reference of either
+    // kind goes away.  Unused.
+    // TODO: Remove.
+    virtual void            onLastWeakRef(const void* id);
+
+private:
+    friend class weakref_type;
+    class weakref_impl;
+    
+                            RefBase(const RefBase& o);
+            RefBase&        operator=(const RefBase& o);
+
+private:
+    friend class ReferenceMover;
+
+    static void renameRefs(size_t n, const ReferenceRenamer& renamer);
+
+    static void renameRefId(weakref_type* ref,
+            const void* old_id, const void* new_id);
+
+    static void renameRefId(RefBase* ref,
+            const void* old_id, const void* new_id);
+
+        weakref_impl* const mRefs;
+};
+
+// ---------------------------------------------------------------------------
+
+template <class T>
+class LightRefBase
+{
+public:
+    inline LightRefBase() : mCount(0) { }
+    inline void incStrong(__attribute__((unused)) const void* id) const {
+        mCount.fetch_add(1, std::memory_order_relaxed);
+    }
+    inline void decStrong(__attribute__((unused)) const void* id) const {
+        if (mCount.fetch_sub(1, std::memory_order_release) == 1) {
+            std::atomic_thread_fence(std::memory_order_acquire);
+            delete static_cast<const T*>(this);
+        }
+    }
+    //! DEBUGGING ONLY: Get current strong ref count.
+    inline int32_t getStrongCount() const {
+        return mCount.load(std::memory_order_relaxed);
+    }
+
+    typedef LightRefBase<T> basetype;
+
+protected:
+    inline ~LightRefBase() { }
+
+private:
+    friend class ReferenceMover;
+    inline static void renameRefs(size_t /*n*/,
+            const ReferenceRenamer& /*renamer*/) { }
+    inline static void renameRefId(T* /*ref*/,
+            const void* /*old_id*/ , const void* /*new_id*/) { }
+
+private:
+    mutable std::atomic<int32_t> mCount;
+};
+
+// This is a wrapper around LightRefBase that simply enforces a virtual
+// destructor to eliminate the template requirement of LightRefBase
+class VirtualLightRefBase : public LightRefBase<VirtualLightRefBase> {
+public:
+    virtual ~VirtualLightRefBase();
+};
+
+// ---------------------------------------------------------------------------
+
+template <typename T>
+class wp
+{
+public:
+    typedef typename RefBase::weakref_type weakref_type;
+    
+    inline wp() : m_ptr(0) { }
+
+    wp(T* other);  // NOLINT(implicit)
+    wp(const wp<T>& other);
+    explicit wp(const sp<T>& other);
+    template<typename U> wp(U* other);  // NOLINT(implicit)
+    template<typename U> wp(const sp<U>& other);  // NOLINT(implicit)
+    template<typename U> wp(const wp<U>& other);  // NOLINT(implicit)
+
+    ~wp();
+    
+    // Assignment
+
+    wp& operator = (T* other);
+    wp& operator = (const wp<T>& other);
+    wp& operator = (const sp<T>& other);
+    
+    template<typename U> wp& operator = (U* other);
+    template<typename U> wp& operator = (const wp<U>& other);
+    template<typename U> wp& operator = (const sp<U>& other);
+    
+    void set_object_and_refs(T* other, weakref_type* refs);
+
+    // promotion to sp
+    
+    sp<T> promote() const;
+
+    // Reset
+    
+    void clear();
+
+    // Accessors
+    
+    inline  weakref_type* get_refs() const { return m_refs; }
+    
+    inline  T* unsafe_get() const { return m_ptr; }
+
+    // Operators
+
+    COMPARE_WEAK(==)
+    COMPARE_WEAK(!=)
+    COMPARE_WEAK(>)
+    COMPARE_WEAK(<)
+    COMPARE_WEAK(<=)
+    COMPARE_WEAK(>=)
+
+    inline bool operator == (const wp<T>& o) const {
+        return (m_ptr == o.m_ptr) && (m_refs == o.m_refs);
+    }
+    template<typename U>
+    inline bool operator == (const wp<U>& o) const {
+        return m_ptr == o.m_ptr;
+    }
+
+    inline bool operator > (const wp<T>& o) const {
+        return (m_ptr == o.m_ptr) ? (m_refs > o.m_refs) : (m_ptr > o.m_ptr);
+    }
+    template<typename U>
+    inline bool operator > (const wp<U>& o) const {
+        return (m_ptr == o.m_ptr) ? (m_refs > o.m_refs) : (m_ptr > o.m_ptr);
+    }
+
+    inline bool operator < (const wp<T>& o) const {
+        return (m_ptr == o.m_ptr) ? (m_refs < o.m_refs) : (m_ptr < o.m_ptr);
+    }
+    template<typename U>
+    inline bool operator < (const wp<U>& o) const {
+        return (m_ptr == o.m_ptr) ? (m_refs < o.m_refs) : (m_ptr < o.m_ptr);
+    }
+                         inline bool operator != (const wp<T>& o) const { return m_refs != o.m_refs; }
+    template<typename U> inline bool operator != (const wp<U>& o) const { return !operator == (o); }
+                         inline bool operator <= (const wp<T>& o) const { return !operator > (o); }
+    template<typename U> inline bool operator <= (const wp<U>& o) const { return !operator > (o); }
+                         inline bool operator >= (const wp<T>& o) const { return !operator < (o); }
+    template<typename U> inline bool operator >= (const wp<U>& o) const { return !operator < (o); }
+
+private:
+    template<typename Y> friend class sp;
+    template<typename Y> friend class wp;
+
+    T*              m_ptr;
+    weakref_type*   m_refs;
+};
+
+template <typename T>
+TextOutput& operator<<(TextOutput& to, const wp<T>& val);
+
+#undef COMPARE_WEAK
+
+// ---------------------------------------------------------------------------
+// No user serviceable parts below here.
+
+template<typename T>
+wp<T>::wp(T* other)
+    : m_ptr(other)
+{
+    if (other) m_refs = other->createWeak(this);
+}
+
+template<typename T>
+wp<T>::wp(const wp<T>& other)
+    : m_ptr(other.m_ptr), m_refs(other.m_refs)
+{
+    if (m_ptr) m_refs->incWeak(this);
+}
+
+template<typename T>
+wp<T>::wp(const sp<T>& other)
+    : m_ptr(other.m_ptr)
+{
+    if (m_ptr) {
+        m_refs = m_ptr->createWeak(this);
+    }
+}
+
+template<typename T> template<typename U>
+wp<T>::wp(U* other)
+    : m_ptr(other)
+{
+    if (other) m_refs = other->createWeak(this);
+}
+
+template<typename T> template<typename U>
+wp<T>::wp(const wp<U>& other)
+    : m_ptr(other.m_ptr)
+{
+    if (m_ptr) {
+        m_refs = other.m_refs;
+        m_refs->incWeak(this);
+    }
+}
+
+template<typename T> template<typename U>
+wp<T>::wp(const sp<U>& other)
+    : m_ptr(other.m_ptr)
+{
+    if (m_ptr) {
+        m_refs = m_ptr->createWeak(this);
+    }
+}
+
+template<typename T>
+wp<T>::~wp()
+{
+    if (m_ptr) m_refs->decWeak(this);
+}
+
+template<typename T>
+wp<T>& wp<T>::operator = (T* other)
+{
+    weakref_type* newRefs =
+        other ? other->createWeak(this) : 0;
+    if (m_ptr) m_refs->decWeak(this);
+    m_ptr = other;
+    m_refs = newRefs;
+    return *this;
+}
+
+template<typename T>
+wp<T>& wp<T>::operator = (const wp<T>& other)
+{
+    weakref_type* otherRefs(other.m_refs);
+    T* otherPtr(other.m_ptr);
+    if (otherPtr) otherRefs->incWeak(this);
+    if (m_ptr) m_refs->decWeak(this);
+    m_ptr = otherPtr;
+    m_refs = otherRefs;
+    return *this;
+}
+
+template<typename T>
+wp<T>& wp<T>::operator = (const sp<T>& other)
+{
+    weakref_type* newRefs =
+        other != NULL ? other->createWeak(this) : 0;
+    T* otherPtr(other.m_ptr);
+    if (m_ptr) m_refs->decWeak(this);
+    m_ptr = otherPtr;
+    m_refs = newRefs;
+    return *this;
+}
+
+template<typename T> template<typename U>
+wp<T>& wp<T>::operator = (U* other)
+{
+    weakref_type* newRefs =
+        other ? other->createWeak(this) : 0;
+    if (m_ptr) m_refs->decWeak(this);
+    m_ptr = other;
+    m_refs = newRefs;
+    return *this;
+}
+
+template<typename T> template<typename U>
+wp<T>& wp<T>::operator = (const wp<U>& other)
+{
+    weakref_type* otherRefs(other.m_refs);
+    U* otherPtr(other.m_ptr);
+    if (otherPtr) otherRefs->incWeak(this);
+    if (m_ptr) m_refs->decWeak(this);
+    m_ptr = otherPtr;
+    m_refs = otherRefs;
+    return *this;
+}
+
+template<typename T> template<typename U>
+wp<T>& wp<T>::operator = (const sp<U>& other)
+{
+    weakref_type* newRefs =
+        other != NULL ? other->createWeak(this) : 0;
+    U* otherPtr(other.m_ptr);
+    if (m_ptr) m_refs->decWeak(this);
+    m_ptr = otherPtr;
+    m_refs = newRefs;
+    return *this;
+}
+
+template<typename T>
+void wp<T>::set_object_and_refs(T* other, weakref_type* refs)
+{
+    if (other) refs->incWeak(this);
+    if (m_ptr) m_refs->decWeak(this);
+    m_ptr = other;
+    m_refs = refs;
+}
+
+template<typename T>
+sp<T> wp<T>::promote() const
+{
+    sp<T> result;
+    if (m_ptr && m_refs->attemptIncStrong(&result)) {
+        result.set_pointer(m_ptr);
+    }
+    return result;
+}
+
+template<typename T>
+void wp<T>::clear()
+{
+    if (m_ptr) {
+        m_refs->decWeak(this);
+        m_ptr = 0;
+    }
+}
+
+template <typename T>
+inline TextOutput& operator<<(TextOutput& to, const wp<T>& val)
+{
+    return printWeakPointer(to, val.unsafe_get());
+}
+
+// ---------------------------------------------------------------------------
+
+// this class just serves as a namespace so TYPE::moveReferences can stay
+// private.
+class ReferenceMover {
+public:
+    // it would be nice if we could make sure no extra code is generated
+    // for sp<TYPE> or wp<TYPE> when TYPE is a descendant of RefBase:
+    // Using a sp<RefBase> override doesn't work; it's a bit like we wanted
+    // a template<typename TYPE inherits RefBase> template...
+
+    template<typename TYPE> static inline
+    void move_references(sp<TYPE>* dest, sp<TYPE> const* src, size_t n) {
+
+        class Renamer : public ReferenceRenamer {
+            sp<TYPE>* d_;
+            sp<TYPE> const* s_;
+            virtual void operator()(size_t i) const {
+                // The id are known to be the sp<>'s this pointer
+                TYPE::renameRefId(d_[i].get(), &s_[i], &d_[i]);
+            }
+        public:
+            Renamer(sp<TYPE>* d, sp<TYPE> const* s) : d_(d), s_(s) { }
+            virtual ~Renamer() { }
+        };
+
+        memmove(dest, src, n*sizeof(sp<TYPE>));
+        TYPE::renameRefs(n, Renamer(dest, src));
+    }
+
+
+    template<typename TYPE> static inline
+    void move_references(wp<TYPE>* dest, wp<TYPE> const* src, size_t n) {
+
+        class Renamer : public ReferenceRenamer {
+            wp<TYPE>* d_;
+            wp<TYPE> const* s_;
+            virtual void operator()(size_t i) const {
+                // The id are known to be the wp<>'s this pointer
+                TYPE::renameRefId(d_[i].get_refs(), &s_[i], &d_[i]);
+            }
+        public:
+            Renamer(wp<TYPE>* rd, wp<TYPE> const* rs) : d_(rd), s_(rs) { }
+            virtual ~Renamer() { }
+        };
+
+        memmove(dest, src, n*sizeof(wp<TYPE>));
+        TYPE::renameRefs(n, Renamer(dest, src));
+    }
+};
+
+// specialization for moving sp<> and wp<> types.
+// these are used by the [Sorted|Keyed]Vector<> implementations
+// sp<> and wp<> need to be handled specially, because they do not
+// have trivial copy operation in the general case (see RefBase.cpp
+// when DEBUG ops are enabled), but can be implemented very
+// efficiently in most cases.
+
+template<typename TYPE> inline
+void move_forward_type(sp<TYPE>* d, sp<TYPE> const* s, size_t n) {
+    ReferenceMover::move_references(d, s, n);
+}
+
+template<typename TYPE> inline
+void move_backward_type(sp<TYPE>* d, sp<TYPE> const* s, size_t n) {
+    ReferenceMover::move_references(d, s, n);
+}
+
+template<typename TYPE> inline
+void move_forward_type(wp<TYPE>* d, wp<TYPE> const* s, size_t n) {
+    ReferenceMover::move_references(d, s, n);
+}
+
+template<typename TYPE> inline
+void move_backward_type(wp<TYPE>* d, wp<TYPE> const* s, size_t n) {
+    ReferenceMover::move_references(d, s, n);
+}
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_REF_BASE_H
diff --git a/libutils/include/utils/Singleton.h b/libutils/include/utils/Singleton.h
new file mode 100644
index 000000000..7cc4c18be
--- /dev/null
+++ b/libutils/include/utils/Singleton.h
@@ -0,0 +1,85 @@
+/*
+ * Copyright (C) 2007 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 ANDROID_UTILS_SINGLETON_H
+#define ANDROID_UTILS_SINGLETON_H
+
+#include <stdint.h>
+#include <sys/types.h>
+#include <utils/Mutex.h>
+#include <utils/threads.h>
+#include <cutils/compiler.h>
+
+namespace android {
+// ---------------------------------------------------------------------------
+
+template <typename TYPE>
+class ANDROID_API Singleton
+{
+public:
+    static TYPE& getInstance() {
+        Mutex::Autolock _l(sLock);
+        TYPE* instance = sInstance;
+        if (instance == 0) {
+            instance = new TYPE();
+            sInstance = instance;
+        }
+        return *instance;
+    }
+
+    static bool hasInstance() {
+        Mutex::Autolock _l(sLock);
+        return sInstance != 0;
+    }
+    
+protected:
+    ~Singleton() { }
+    Singleton() { }
+
+private:
+    Singleton(const Singleton&);
+    Singleton& operator = (const Singleton&);
+    static Mutex sLock;
+    static TYPE* sInstance;
+};
+
+template <typename TYPE>
+Mutex Singleton<TYPE>::sLock;
+
+template <typename TYPE>
+TYPE* Singleton<TYPE>::sInstance;
+
+/*
+ * use ANDROID_SINGLETON_STATIC_INSTANCE(TYPE) in your implementation file
+ * (eg: <TYPE>.cpp) to create the static instance of Singleton<>'s attributes,
+ * and avoid to have a copy of them in each compilation units Singleton<TYPE>
+ * is used.
+ * NOTE: we use a version of Mutex ctor that takes a parameter, because
+ * for some unknown reason using the default ctor doesn't emit the variable!
+ */
+
+#define ANDROID_SINGLETON_STATIC_INSTANCE(TYPE)                 \
+    template<> ::android::Mutex  \
+        (::android::Singleton< TYPE >::sLock)(::android::Mutex::PRIVATE);  \
+    template<> TYPE* ::android::Singleton< TYPE >::sInstance(0);  \
+    template class ::android::Singleton< TYPE >;
+
+
+// ---------------------------------------------------------------------------
+}; // namespace android
+
+#endif // ANDROID_UTILS_SINGLETON_H
+
diff --git a/libutils/include/utils/SortedVector.h b/libutils/include/utils/SortedVector.h
new file mode 100644
index 000000000..d57465d33
--- /dev/null
+++ b/libutils/include/utils/SortedVector.h
@@ -0,0 +1,294 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_SORTED_VECTOR_H
+#define ANDROID_SORTED_VECTOR_H
+
+#include <assert.h>
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <log/log.h>
+#include <utils/TypeHelpers.h>
+#include <utils/Vector.h>
+#include <utils/VectorImpl.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+template <class TYPE>
+class SortedVector : private SortedVectorImpl
+{
+    friend class Vector<TYPE>;
+
+public:
+            typedef TYPE    value_type;
+
+    /*!
+     * Constructors and destructors
+     */
+
+                            SortedVector();
+                            SortedVector(const SortedVector<TYPE>& rhs);
+    virtual                 ~SortedVector();
+
+    /*! copy operator */
+    const SortedVector<TYPE>&   operator = (const SortedVector<TYPE>& rhs) const;
+    SortedVector<TYPE>&         operator = (const SortedVector<TYPE>& rhs);
+
+    /*
+     * empty the vector
+     */
+
+    inline  void            clear()             { VectorImpl::clear(); }
+
+    /*!
+     * vector stats
+     */
+
+    //! returns number of items in the vector
+    inline  size_t          size() const                { return VectorImpl::size(); }
+    //! returns whether or not the vector is empty
+    inline  bool            isEmpty() const             { return VectorImpl::isEmpty(); }
+    //! returns how many items can be stored without reallocating the backing store
+    inline  size_t          capacity() const            { return VectorImpl::capacity(); }
+    //! sets the capacity. capacity can never be reduced less than size()
+    inline  ssize_t         setCapacity(size_t size)    { return VectorImpl::setCapacity(size); }
+
+    /*!
+     * C-style array access
+     */
+
+    //! read-only C-style access
+    inline  const TYPE*     array() const;
+
+    //! read-write C-style access. BE VERY CAREFUL when modifying the array
+    //! you must keep it sorted! You usually don't use this function.
+            TYPE*           editArray();
+
+            //! finds the index of an item
+            ssize_t         indexOf(const TYPE& item) const;
+
+            //! finds where this item should be inserted
+            size_t          orderOf(const TYPE& item) const;
+
+
+    /*!
+     * accessors
+     */
+
+    //! read-only access to an item at a given index
+    inline  const TYPE&     operator [] (size_t index) const;
+    //! alternate name for operator []
+    inline  const TYPE&     itemAt(size_t index) const;
+    //! stack-usage of the vector. returns the top of the stack (last element)
+            const TYPE&     top() const;
+
+    /*!
+     * modifying the array
+     */
+
+            //! add an item in the right place (and replace the one that is there)
+            ssize_t         add(const TYPE& item);
+
+            //! editItemAt() MUST NOT change the order of this item
+            TYPE&           editItemAt(size_t index) {
+                return *( static_cast<TYPE *>(VectorImpl::editItemLocation(index)) );
+            }
+
+            //! merges a vector into this one
+            ssize_t         merge(const Vector<TYPE>& vector);
+            ssize_t         merge(const SortedVector<TYPE>& vector);
+
+            //! removes an item
+            ssize_t         remove(const TYPE&);
+
+    //! remove several items
+    inline  ssize_t         removeItemsAt(size_t index, size_t count = 1);
+    //! remove one item
+    inline  ssize_t         removeAt(size_t index)  { return removeItemsAt(index); }
+
+    /*
+     * these inlines add some level of compatibility with STL.
+     */
+    typedef TYPE* iterator;
+    typedef TYPE const* const_iterator;
+
+    inline iterator begin() { return editArray(); }
+    inline iterator end()   { return editArray() + size(); }
+    inline const_iterator begin() const { return array(); }
+    inline const_iterator end() const   { return array() + size(); }
+    inline void reserve(size_t n) { setCapacity(n); }
+    inline bool empty() const{ return isEmpty(); }
+    inline iterator erase(iterator pos) {
+        ssize_t index = removeItemsAt(pos-array());
+        return begin() + index;
+    }
+
+protected:
+    virtual void    do_construct(void* storage, size_t num) const;
+    virtual void    do_destroy(void* storage, size_t num) const;
+    virtual void    do_copy(void* dest, const void* from, size_t num) const;
+    virtual void    do_splat(void* dest, const void* item, size_t num) const;
+    virtual void    do_move_forward(void* dest, const void* from, size_t num) const;
+    virtual void    do_move_backward(void* dest, const void* from, size_t num) const;
+    virtual int     do_compare(const void* lhs, const void* rhs) const;
+};
+
+// ---------------------------------------------------------------------------
+// No user serviceable parts from here...
+// ---------------------------------------------------------------------------
+
+template<class TYPE> inline
+SortedVector<TYPE>::SortedVector()
+    : SortedVectorImpl(sizeof(TYPE),
+                ((traits<TYPE>::has_trivial_ctor   ? HAS_TRIVIAL_CTOR   : 0)
+                |(traits<TYPE>::has_trivial_dtor   ? HAS_TRIVIAL_DTOR   : 0)
+                |(traits<TYPE>::has_trivial_copy   ? HAS_TRIVIAL_COPY   : 0))
+                )
+{
+}
+
+template<class TYPE> inline
+SortedVector<TYPE>::SortedVector(const SortedVector<TYPE>& rhs)
+    : SortedVectorImpl(rhs) {
+}
+
+template<class TYPE> inline
+SortedVector<TYPE>::~SortedVector() {
+    finish_vector();
+}
+
+template<class TYPE> inline
+SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) {
+    SortedVectorImpl::operator = (rhs);
+    return *this;
+}
+
+template<class TYPE> inline
+const SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) const {
+    SortedVectorImpl::operator = (rhs);
+    return *this;
+}
+
+template<class TYPE> inline
+const TYPE* SortedVector<TYPE>::array() const {
+    return static_cast<const TYPE *>(arrayImpl());
+}
+
+template<class TYPE> inline
+TYPE* SortedVector<TYPE>::editArray() {
+    return static_cast<TYPE *>(editArrayImpl());
+}
+
+
+template<class TYPE> inline
+const TYPE& SortedVector<TYPE>::operator[](size_t index) const {
+    LOG_FATAL_IF(index>=size(),
+            "%s: index=%u out of range (%u)", __PRETTY_FUNCTION__,
+            int(index), int(size()));
+    return *(array() + index);
+}
+
+template<class TYPE> inline
+const TYPE& SortedVector<TYPE>::itemAt(size_t index) const {
+    return operator[](index);
+}
+
+template<class TYPE> inline
+const TYPE& SortedVector<TYPE>::top() const {
+    return *(array() + size() - 1);
+}
+
+template<class TYPE> inline
+ssize_t SortedVector<TYPE>::add(const TYPE& item) {
+    return SortedVectorImpl::add(&item);
+}
+
+template<class TYPE> inline
+ssize_t SortedVector<TYPE>::indexOf(const TYPE& item) const {
+    return SortedVectorImpl::indexOf(&item);
+}
+
+template<class TYPE> inline
+size_t SortedVector<TYPE>::orderOf(const TYPE& item) const {
+    return SortedVectorImpl::orderOf(&item);
+}
+
+template<class TYPE> inline
+ssize_t SortedVector<TYPE>::merge(const Vector<TYPE>& vector) {
+    return SortedVectorImpl::merge(reinterpret_cast<const VectorImpl&>(vector));
+}
+
+template<class TYPE> inline
+ssize_t SortedVector<TYPE>::merge(const SortedVector<TYPE>& vector) {
+    return SortedVectorImpl::merge(reinterpret_cast<const SortedVectorImpl&>(vector));
+}
+
+template<class TYPE> inline
+ssize_t SortedVector<TYPE>::remove(const TYPE& item) {
+    return SortedVectorImpl::remove(&item);
+}
+
+template<class TYPE> inline
+ssize_t SortedVector<TYPE>::removeItemsAt(size_t index, size_t count) {
+    return VectorImpl::removeItemsAt(index, count);
+}
+
+// ---------------------------------------------------------------------------
+
+template<class TYPE>
+void SortedVector<TYPE>::do_construct(void* storage, size_t num) const {
+    construct_type( reinterpret_cast<TYPE*>(storage), num );
+}
+
+template<class TYPE>
+void SortedVector<TYPE>::do_destroy(void* storage, size_t num) const {
+    destroy_type( reinterpret_cast<TYPE*>(storage), num );
+}
+
+template<class TYPE>
+void SortedVector<TYPE>::do_copy(void* dest, const void* from, size_t num) const {
+    copy_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
+}
+
+template<class TYPE>
+void SortedVector<TYPE>::do_splat(void* dest, const void* item, size_t num) const {
+    splat_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(item), num );
+}
+
+template<class TYPE>
+void SortedVector<TYPE>::do_move_forward(void* dest, const void* from, size_t num) const {
+    move_forward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
+}
+
+template<class TYPE>
+void SortedVector<TYPE>::do_move_backward(void* dest, const void* from, size_t num) const {
+    move_backward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
+}
+
+template<class TYPE>
+int SortedVector<TYPE>::do_compare(const void* lhs, const void* rhs) const {
+    return compare_type( *reinterpret_cast<const TYPE*>(lhs), *reinterpret_cast<const TYPE*>(rhs) );
+}
+
+}; // namespace android
+
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_SORTED_VECTOR_H
diff --git a/libutils/include/utils/StopWatch.h b/libutils/include/utils/StopWatch.h
new file mode 100644
index 000000000..693dd3ccf
--- /dev/null
+++ b/libutils/include/utils/StopWatch.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_STOPWATCH_H
+#define ANDROID_STOPWATCH_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <utils/Timers.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+class StopWatch
+{
+public:
+        StopWatch(  const char *name,
+                    int clock = SYSTEM_TIME_MONOTONIC,
+                    uint32_t flags = 0);
+        ~StopWatch();
+        
+        const char* name() const;
+        nsecs_t     lap();
+        nsecs_t     elapsedTime() const;
+
+        void        reset();
+        
+private:
+    const char*     mName;
+    int             mClock;
+    uint32_t        mFlags;
+    
+    struct lap_t {
+        nsecs_t     soFar;
+        nsecs_t     thisLap;
+    };
+    
+    nsecs_t         mStartTime;
+    lap_t           mLaps[8];
+    int             mNumLaps;
+};
+
+
+}; // namespace android
+
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_STOPWATCH_H
diff --git a/libutils/include/utils/String16.h b/libutils/include/utils/String16.h
new file mode 100644
index 000000000..07c4de746
--- /dev/null
+++ b/libutils/include/utils/String16.h
@@ -0,0 +1,248 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_STRING16_H
+#define ANDROID_STRING16_H
+
+#include <string> // for std::string
+
+#include <utils/Errors.h>
+#include <utils/String8.h>
+#include <utils/TypeHelpers.h>
+
+// ---------------------------------------------------------------------------
+
+extern "C" {
+
+}
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+// ---------------------------------------------------------------------------
+
+class SharedBuffer;
+class String8;
+class TextOutput;
+
+//! This is a string holding UTF-16 characters.
+class String16
+{
+public:
+    /* use String16(StaticLinkage) if you're statically linking against
+     * libutils and declaring an empty static String16, e.g.:
+     *
+     *   static String16 sAStaticEmptyString(String16::kEmptyString);
+     *   static String16 sAnotherStaticEmptyString(sAStaticEmptyString);
+     */
+    enum StaticLinkage { kEmptyString };
+
+                                String16();
+    explicit                    String16(StaticLinkage);
+                                String16(const String16& o);
+                                String16(const String16& o,
+                                         size_t len,
+                                         size_t begin=0);
+    explicit                    String16(const char16_t* o);
+    explicit                    String16(const char16_t* o, size_t len);
+    explicit                    String16(const String8& o);
+    explicit                    String16(const char* o);
+    explicit                    String16(const char* o, size_t len);
+
+                                ~String16();
+
+    inline  const char16_t*     string() const;
+
+    static inline std::string   std_string(const String16& str);
+            size_t              size() const;
+            void                setTo(const String16& other);
+            status_t            setTo(const char16_t* other);
+            status_t            setTo(const char16_t* other, size_t len);
+            status_t            setTo(const String16& other,
+                                      size_t len,
+                                      size_t begin=0);
+
+            status_t            append(const String16& other);
+            status_t            append(const char16_t* other, size_t len);
+
+    inline  String16&           operator=(const String16& other);
+
+    inline  String16&           operator+=(const String16& other);
+    inline  String16            operator+(const String16& other) const;
+
+            status_t            insert(size_t pos, const char16_t* chrs);
+            status_t            insert(size_t pos,
+                                       const char16_t* chrs, size_t len);
+
+            ssize_t             findFirst(char16_t c) const;
+            ssize_t             findLast(char16_t c) const;
+
+            bool                startsWith(const String16& prefix) const;
+            bool                startsWith(const char16_t* prefix) const;
+
+            bool                contains(const char16_t* chrs) const;
+
+            status_t            makeLower();
+
+            status_t            replaceAll(char16_t replaceThis,
+                                           char16_t withThis);
+
+            status_t            remove(size_t len, size_t begin=0);
+
+    inline  int                 compare(const String16& other) const;
+
+    inline  bool                operator<(const String16& other) const;
+    inline  bool                operator<=(const String16& other) const;
+    inline  bool                operator==(const String16& other) const;
+    inline  bool                operator!=(const String16& other) const;
+    inline  bool                operator>=(const String16& other) const;
+    inline  bool                operator>(const String16& other) const;
+
+    inline  bool                operator<(const char16_t* other) const;
+    inline  bool                operator<=(const char16_t* other) const;
+    inline  bool                operator==(const char16_t* other) const;
+    inline  bool                operator!=(const char16_t* other) const;
+    inline  bool                operator>=(const char16_t* other) const;
+    inline  bool                operator>(const char16_t* other) const;
+
+    inline                      operator const char16_t*() const;
+
+private:
+            const char16_t*     mString;
+};
+
+// String16 can be trivially moved using memcpy() because moving does not
+// require any change to the underlying SharedBuffer contents or reference count.
+ANDROID_TRIVIAL_MOVE_TRAIT(String16)
+
+// ---------------------------------------------------------------------------
+// No user servicable parts below.
+
+inline int compare_type(const String16& lhs, const String16& rhs)
+{
+    return lhs.compare(rhs);
+}
+
+inline int strictly_order_type(const String16& lhs, const String16& rhs)
+{
+    return compare_type(lhs, rhs) < 0;
+}
+
+inline const char16_t* String16::string() const
+{
+    return mString;
+}
+
+inline std::string String16::std_string(const String16& str)
+{
+    return std::string(String8(str).string());
+}
+
+inline String16& String16::operator=(const String16& other)
+{
+    setTo(other);
+    return *this;
+}
+
+inline String16& String16::operator+=(const String16& other)
+{
+    append(other);
+    return *this;
+}
+
+inline String16 String16::operator+(const String16& other) const
+{
+    String16 tmp(*this);
+    tmp += other;
+    return tmp;
+}
+
+inline int String16::compare(const String16& other) const
+{
+    return strzcmp16(mString, size(), other.mString, other.size());
+}
+
+inline bool String16::operator<(const String16& other) const
+{
+    return strzcmp16(mString, size(), other.mString, other.size()) < 0;
+}
+
+inline bool String16::operator<=(const String16& other) const
+{
+    return strzcmp16(mString, size(), other.mString, other.size()) <= 0;
+}
+
+inline bool String16::operator==(const String16& other) const
+{
+    return strzcmp16(mString, size(), other.mString, other.size()) == 0;
+}
+
+inline bool String16::operator!=(const String16& other) const
+{
+    return strzcmp16(mString, size(), other.mString, other.size()) != 0;
+}
+
+inline bool String16::operator>=(const String16& other) const
+{
+    return strzcmp16(mString, size(), other.mString, other.size()) >= 0;
+}
+
+inline bool String16::operator>(const String16& other) const
+{
+    return strzcmp16(mString, size(), other.mString, other.size()) > 0;
+}
+
+inline bool String16::operator<(const char16_t* other) const
+{
+    return strcmp16(mString, other) < 0;
+}
+
+inline bool String16::operator<=(const char16_t* other) const
+{
+    return strcmp16(mString, other) <= 0;
+}
+
+inline bool String16::operator==(const char16_t* other) const
+{
+    return strcmp16(mString, other) == 0;
+}
+
+inline bool String16::operator!=(const char16_t* other) const
+{
+    return strcmp16(mString, other) != 0;
+}
+
+inline bool String16::operator>=(const char16_t* other) const
+{
+    return strcmp16(mString, other) >= 0;
+}
+
+inline bool String16::operator>(const char16_t* other) const
+{
+    return strcmp16(mString, other) > 0;
+}
+
+inline String16::operator const char16_t*() const
+{
+    return mString;
+}
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_STRING16_H
diff --git a/libutils/include/utils/String8.h b/libutils/include/utils/String8.h
new file mode 100644
index 000000000..1d12994d1
--- /dev/null
+++ b/libutils/include/utils/String8.h
@@ -0,0 +1,404 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_STRING8_H
+#define ANDROID_STRING8_H
+
+#include <string> // for std::string
+
+#include <utils/Errors.h>
+#include <utils/Unicode.h>
+#include <utils/TypeHelpers.h>
+
+#include <string.h> // for strcmp
+#include <stdarg.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+class String16;
+class TextOutput;
+
+//! This is a string holding UTF-8 characters. Does not allow the value more
+// than 0x10FFFF, which is not valid unicode codepoint.
+class String8
+{
+public:
+    /* use String8(StaticLinkage) if you're statically linking against
+     * libutils and declaring an empty static String8, e.g.:
+     *
+     *   static String8 sAStaticEmptyString(String8::kEmptyString);
+     *   static String8 sAnotherStaticEmptyString(sAStaticEmptyString);
+     */
+    enum StaticLinkage { kEmptyString };
+
+                                String8();
+    explicit                    String8(StaticLinkage);
+                                String8(const String8& o);
+    explicit                    String8(const char* o);
+    explicit                    String8(const char* o, size_t numChars);
+
+    explicit                    String8(const String16& o);
+    explicit                    String8(const char16_t* o);
+    explicit                    String8(const char16_t* o, size_t numChars);
+    explicit                    String8(const char32_t* o);
+    explicit                    String8(const char32_t* o, size_t numChars);
+                                ~String8();
+
+    static inline const String8 empty();
+
+    static String8              format(const char* fmt, ...) __attribute__((format (printf, 1, 2)));
+    static String8              formatV(const char* fmt, va_list args);
+
+    inline  const char*         string() const;
+    static inline std::string   std_string(const String8& str);
+    inline  size_t              size() const;
+    inline  size_t              bytes() const;
+    inline  bool                isEmpty() const;
+
+            size_t              length() const;
+
+            void                clear();
+
+            void                setTo(const String8& other);
+            status_t            setTo(const char* other);
+            status_t            setTo(const char* other, size_t numChars);
+            status_t            setTo(const char16_t* other, size_t numChars);
+            status_t            setTo(const char32_t* other,
+                                      size_t length);
+
+            status_t            append(const String8& other);
+            status_t            append(const char* other);
+            status_t            append(const char* other, size_t numChars);
+
+            status_t            appendFormat(const char* fmt, ...)
+                    __attribute__((format (printf, 2, 3)));
+            status_t            appendFormatV(const char* fmt, va_list args);
+
+            // Note that this function takes O(N) time to calculate the value.
+            // No cache value is stored.
+            size_t              getUtf32Length() const;
+            int32_t             getUtf32At(size_t index,
+                                           size_t *next_index) const;
+            void                getUtf32(char32_t* dst) const;
+
+    inline  String8&            operator=(const String8& other);
+    inline  String8&            operator=(const char* other);
+
+    inline  String8&            operator+=(const String8& other);
+    inline  String8             operator+(const String8& other) const;
+
+    inline  String8&            operator+=(const char* other);
+    inline  String8             operator+(const char* other) const;
+
+    inline  int                 compare(const String8& other) const;
+
+    inline  bool                operator<(const String8& other) const;
+    inline  bool                operator<=(const String8& other) const;
+    inline  bool                operator==(const String8& other) const;
+    inline  bool                operator!=(const String8& other) const;
+    inline  bool                operator>=(const String8& other) const;
+    inline  bool                operator>(const String8& other) const;
+
+    inline  bool                operator<(const char* other) const;
+    inline  bool                operator<=(const char* other) const;
+    inline  bool                operator==(const char* other) const;
+    inline  bool                operator!=(const char* other) const;
+    inline  bool                operator>=(const char* other) const;
+    inline  bool                operator>(const char* other) const;
+
+    inline                      operator const char*() const;
+
+            char*               lockBuffer(size_t size);
+            void                unlockBuffer();
+            status_t            unlockBuffer(size_t size);
+
+            // return the index of the first byte of other in this at or after
+            // start, or -1 if not found
+            ssize_t             find(const char* other, size_t start = 0) const;
+
+            // return true if this string contains the specified substring
+    inline  bool                contains(const char* other) const;
+
+            // removes all occurrence of the specified substring
+            // returns true if any were found and removed
+            bool                removeAll(const char* other);
+
+            void                toLower();
+            void                toLower(size_t start, size_t numChars);
+            void                toUpper();
+            void                toUpper(size_t start, size_t numChars);
+
+
+    /*
+     * These methods operate on the string as if it were a path name.
+     */
+
+    /*
+     * Set the filename field to a specific value.
+     *
+     * Normalizes the filename, removing a trailing '/' if present.
+     */
+    void setPathName(const char* name);
+    void setPathName(const char* name, size_t numChars);
+
+    /*
+     * Get just the filename component.
+     *
+     * "/tmp/foo/bar.c" --> "bar.c"
+     */
+    String8 getPathLeaf(void) const;
+
+    /*
+     * Remove the last (file name) component, leaving just the directory
+     * name.
+     *
+     * "/tmp/foo/bar.c" --> "/tmp/foo"
+     * "/tmp" --> "" // ????? shouldn't this be "/" ???? XXX
+     * "bar.c" --> ""
+     */
+    String8 getPathDir(void) const;
+
+    /*
+     * Retrieve the front (root dir) component.  Optionally also return the
+     * remaining components.
+     *
+     * "/tmp/foo/bar.c" --> "tmp" (remain = "foo/bar.c")
+     * "/tmp" --> "tmp" (remain = "")
+     * "bar.c" --> "bar.c" (remain = "")
+     */
+    String8 walkPath(String8* outRemains = NULL) const;
+
+    /*
+     * Return the filename extension.  This is the last '.' and any number
+     * of characters that follow it.  The '.' is included in case we
+     * decide to expand our definition of what constitutes an extension.
+     *
+     * "/tmp/foo/bar.c" --> ".c"
+     * "/tmp" --> ""
+     * "/tmp/foo.bar/baz" --> ""
+     * "foo.jpeg" --> ".jpeg"
+     * "foo." --> ""
+     */
+    String8 getPathExtension(void) const;
+
+    /*
+     * Return the path without the extension.  Rules for what constitutes
+     * an extension are described in the comment for getPathExtension().
+     *
+     * "/tmp/foo/bar.c" --> "/tmp/foo/bar"
+     */
+    String8 getBasePath(void) const;
+
+    /*
+     * Add a component to the pathname.  We guarantee that there is
+     * exactly one path separator between the old path and the new.
+     * If there is no existing name, we just copy the new name in.
+     *
+     * If leaf is a fully qualified path (i.e. starts with '/', it
+     * replaces whatever was there before.
+     */
+    String8& appendPath(const char* leaf);
+    String8& appendPath(const String8& leaf)  { return appendPath(leaf.string()); }
+
+    /*
+     * Like appendPath(), but does not affect this string.  Returns a new one instead.
+     */
+    String8 appendPathCopy(const char* leaf) const
+                                             { String8 p(*this); p.appendPath(leaf); return p; }
+    String8 appendPathCopy(const String8& leaf) const { return appendPathCopy(leaf.string()); }
+
+    /*
+     * Converts all separators in this string to /, the default path separator.
+     *
+     * If the default OS separator is backslash, this converts all
+     * backslashes to slashes, in-place. Otherwise it does nothing.
+     * Returns self.
+     */
+    String8& convertToResPath();
+
+private:
+            status_t            real_append(const char* other, size_t numChars);
+            char*               find_extension(void) const;
+
+            const char* mString;
+};
+
+// String8 can be trivially moved using memcpy() because moving does not
+// require any change to the underlying SharedBuffer contents or reference count.
+ANDROID_TRIVIAL_MOVE_TRAIT(String8)
+
+// ---------------------------------------------------------------------------
+// No user servicable parts below.
+
+inline int compare_type(const String8& lhs, const String8& rhs)
+{
+    return lhs.compare(rhs);
+}
+
+inline int strictly_order_type(const String8& lhs, const String8& rhs)
+{
+    return compare_type(lhs, rhs) < 0;
+}
+
+inline const String8 String8::empty() {
+    return String8();
+}
+
+inline const char* String8::string() const
+{
+    return mString;
+}
+
+inline std::string String8::std_string(const String8& str)
+{
+    return std::string(str.string());
+}
+
+inline size_t String8::size() const
+{
+    return length();
+}
+
+inline bool String8::isEmpty() const
+{
+    return length() == 0;
+}
+
+inline size_t String8::bytes() const
+{
+    return length();
+}
+
+inline bool String8::contains(const char* other) const
+{
+    return find(other) >= 0;
+}
+
+inline String8& String8::operator=(const String8& other)
+{
+    setTo(other);
+    return *this;
+}
+
+inline String8& String8::operator=(const char* other)
+{
+    setTo(other);
+    return *this;
+}
+
+inline String8& String8::operator+=(const String8& other)
+{
+    append(other);
+    return *this;
+}
+
+inline String8 String8::operator+(const String8& other) const
+{
+    String8 tmp(*this);
+    tmp += other;
+    return tmp;
+}
+
+inline String8& String8::operator+=(const char* other)
+{
+    append(other);
+    return *this;
+}
+
+inline String8 String8::operator+(const char* other) const
+{
+    String8 tmp(*this);
+    tmp += other;
+    return tmp;
+}
+
+inline int String8::compare(const String8& other) const
+{
+    return strcmp(mString, other.mString);
+}
+
+inline bool String8::operator<(const String8& other) const
+{
+    return strcmp(mString, other.mString) < 0;
+}
+
+inline bool String8::operator<=(const String8& other) const
+{
+    return strcmp(mString, other.mString) <= 0;
+}
+
+inline bool String8::operator==(const String8& other) const
+{
+    return strcmp(mString, other.mString) == 0;
+}
+
+inline bool String8::operator!=(const String8& other) const
+{
+    return strcmp(mString, other.mString) != 0;
+}
+
+inline bool String8::operator>=(const String8& other) const
+{
+    return strcmp(mString, other.mString) >= 0;
+}
+
+inline bool String8::operator>(const String8& other) const
+{
+    return strcmp(mString, other.mString) > 0;
+}
+
+inline bool String8::operator<(const char* other) const
+{
+    return strcmp(mString, other) < 0;
+}
+
+inline bool String8::operator<=(const char* other) const
+{
+    return strcmp(mString, other) <= 0;
+}
+
+inline bool String8::operator==(const char* other) const
+{
+    return strcmp(mString, other) == 0;
+}
+
+inline bool String8::operator!=(const char* other) const
+{
+    return strcmp(mString, other) != 0;
+}
+
+inline bool String8::operator>=(const char* other) const
+{
+    return strcmp(mString, other) >= 0;
+}
+
+inline bool String8::operator>(const char* other) const
+{
+    return strcmp(mString, other) > 0;
+}
+
+inline String8::operator const char*() const
+{
+    return mString;
+}
+
+}  // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_STRING8_H
diff --git a/libutils/include/utils/StrongPointer.h b/libutils/include/utils/StrongPointer.h
new file mode 100644
index 000000000..294e6b6f4
--- /dev/null
+++ b/libutils/include/utils/StrongPointer.h
@@ -0,0 +1,245 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_STRONG_POINTER_H
+#define ANDROID_STRONG_POINTER_H
+
+#include <cutils/atomic.h>
+
+#include <stdint.h>
+#include <sys/types.h>
+#include <stdlib.h>
+
+// ---------------------------------------------------------------------------
+namespace android {
+
+template<typename T> class wp;
+
+// ---------------------------------------------------------------------------
+
+#define COMPARE(_op_)                                           \
+inline bool operator _op_ (const sp<T>& o) const {              \
+    return m_ptr _op_ o.m_ptr;                                  \
+}                                                               \
+inline bool operator _op_ (const T* o) const {                  \
+    return m_ptr _op_ o;                                        \
+}                                                               \
+template<typename U>                                            \
+inline bool operator _op_ (const sp<U>& o) const {              \
+    return m_ptr _op_ o.m_ptr;                                  \
+}                                                               \
+template<typename U>                                            \
+inline bool operator _op_ (const U* o) const {                  \
+    return m_ptr _op_ o;                                        \
+}                                                               \
+inline bool operator _op_ (const wp<T>& o) const {              \
+    return m_ptr _op_ o.m_ptr;                                  \
+}                                                               \
+template<typename U>                                            \
+inline bool operator _op_ (const wp<U>& o) const {              \
+    return m_ptr _op_ o.m_ptr;                                  \
+}
+
+// ---------------------------------------------------------------------------
+
+template<typename T>
+class sp {
+public:
+    inline sp() : m_ptr(0) { }
+
+    sp(T* other);  // NOLINT(implicit)
+    sp(const sp<T>& other);
+    sp(sp<T>&& other);
+    template<typename U> sp(U* other);  // NOLINT(implicit)
+    template<typename U> sp(const sp<U>& other);  // NOLINT(implicit)
+    template<typename U> sp(sp<U>&& other);  // NOLINT(implicit)
+
+    ~sp();
+
+    // Assignment
+
+    sp& operator = (T* other);
+    sp& operator = (const sp<T>& other);
+    sp& operator = (sp<T>&& other);
+
+    template<typename U> sp& operator = (const sp<U>& other);
+    template<typename U> sp& operator = (sp<U>&& other);
+    template<typename U> sp& operator = (U* other);
+
+    //! Special optimization for use by ProcessState (and nobody else).
+    void force_set(T* other);
+
+    // Reset
+
+    void clear();
+
+    // Accessors
+
+    inline  T&      operator* () const  { return *m_ptr; }
+    inline  T*      operator-> () const { return m_ptr;  }
+    inline  T*      get() const         { return m_ptr; }
+
+    // Operators
+
+    COMPARE(==)
+    COMPARE(!=)
+    COMPARE(>)
+    COMPARE(<)
+    COMPARE(<=)
+    COMPARE(>=)
+
+private:    
+    template<typename Y> friend class sp;
+    template<typename Y> friend class wp;
+    void set_pointer(T* ptr);
+    T* m_ptr;
+};
+
+#undef COMPARE
+
+// ---------------------------------------------------------------------------
+// No user serviceable parts below here.
+
+template<typename T>
+sp<T>::sp(T* other)
+        : m_ptr(other) {
+    if (other)
+        other->incStrong(this);
+}
+
+template<typename T>
+sp<T>::sp(const sp<T>& other)
+        : m_ptr(other.m_ptr) {
+    if (m_ptr)
+        m_ptr->incStrong(this);
+}
+
+template<typename T>
+sp<T>::sp(sp<T>&& other)
+        : m_ptr(other.m_ptr) {
+    other.m_ptr = nullptr;
+}
+
+template<typename T> template<typename U>
+sp<T>::sp(U* other)
+        : m_ptr(other) {
+    if (other)
+        (static_cast<T*>(other))->incStrong(this);
+}
+
+template<typename T> template<typename U>
+sp<T>::sp(const sp<U>& other)
+        : m_ptr(other.m_ptr) {
+    if (m_ptr)
+        m_ptr->incStrong(this);
+}
+
+template<typename T> template<typename U>
+sp<T>::sp(sp<U>&& other)
+        : m_ptr(other.m_ptr) {
+    other.m_ptr = nullptr;
+}
+
+template<typename T>
+sp<T>::~sp() {
+    if (m_ptr)
+        m_ptr->decStrong(this);
+}
+
+template<typename T>
+sp<T>& sp<T>::operator =(const sp<T>& other) {
+    T* otherPtr(other.m_ptr);
+    if (otherPtr)
+        otherPtr->incStrong(this);
+    if (m_ptr)
+        m_ptr->decStrong(this);
+    m_ptr = otherPtr;
+    return *this;
+}
+
+template<typename T>
+sp<T>& sp<T>::operator =(sp<T>&& other) {
+    if (m_ptr)
+        m_ptr->decStrong(this);
+    m_ptr = other.m_ptr;
+    other.m_ptr = nullptr;
+    return *this;
+}
+
+template<typename T>
+sp<T>& sp<T>::operator =(T* other) {
+    if (other)
+        other->incStrong(this);
+    if (m_ptr)
+        m_ptr->decStrong(this);
+    m_ptr = other;
+    return *this;
+}
+
+template<typename T> template<typename U>
+sp<T>& sp<T>::operator =(const sp<U>& other) {
+    T* otherPtr(other.m_ptr);
+    if (otherPtr)
+        otherPtr->incStrong(this);
+    if (m_ptr)
+        m_ptr->decStrong(this);
+    m_ptr = otherPtr;
+    return *this;
+}
+
+template<typename T> template<typename U>
+sp<T>& sp<T>::operator =(sp<U>&& other) {
+    if (m_ptr)
+        m_ptr->decStrong(this);
+    m_ptr = other.m_ptr;
+    other.m_ptr = nullptr;
+    return *this;
+}
+
+template<typename T> template<typename U>
+sp<T>& sp<T>::operator =(U* other) {
+    if (other)
+        (static_cast<T*>(other))->incStrong(this);
+    if (m_ptr)
+        m_ptr->decStrong(this);
+    m_ptr = other;
+    return *this;
+}
+
+template<typename T>
+void sp<T>::force_set(T* other) {
+    other->forceIncStrong(this);
+    m_ptr = other;
+}
+
+template<typename T>
+void sp<T>::clear() {
+    if (m_ptr) {
+        m_ptr->decStrong(this);
+        m_ptr = 0;
+    }
+}
+
+template<typename T>
+void sp<T>::set_pointer(T* ptr) {
+    m_ptr = ptr;
+}
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_STRONG_POINTER_H
diff --git a/libutils/include/utils/SystemClock.h b/libutils/include/utils/SystemClock.h
new file mode 100644
index 000000000..01db34078
--- /dev/null
+++ b/libutils/include/utils/SystemClock.h
@@ -0,0 +1,32 @@
+/*
+ * 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 ANDROID_UTILS_SYSTEMCLOCK_H
+#define ANDROID_UTILS_SYSTEMCLOCK_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+namespace android {
+
+int64_t uptimeMillis();
+int64_t elapsedRealtime();
+int64_t elapsedRealtimeNano();
+
+}; // namespace android
+
+#endif // ANDROID_UTILS_SYSTEMCLOCK_H
+
diff --git a/libutils/include/utils/Thread.h b/libutils/include/utils/Thread.h
new file mode 100644
index 000000000..a261fc8d9
--- /dev/null
+++ b/libutils/include/utils/Thread.h
@@ -0,0 +1,116 @@
+/*
+ * Copyright (C) 2007 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 _LIBS_UTILS_THREAD_H
+#define _LIBS_UTILS_THREAD_H
+
+#include <stdint.h>
+#include <sys/types.h>
+#include <time.h>
+
+#if !defined(_WIN32)
+# include <pthread.h>
+#endif
+
+#include <utils/Condition.h>
+#include <utils/Errors.h>
+#include <utils/Mutex.h>
+#include <utils/RefBase.h>
+#include <utils/Timers.h>
+#include <utils/ThreadDefs.h>
+
+// ---------------------------------------------------------------------------
+namespace android {
+// ---------------------------------------------------------------------------
+
+class Thread : virtual public RefBase
+{
+public:
+    // Create a Thread object, but doesn't create or start the associated
+    // thread. See the run() method.
+    explicit            Thread(bool canCallJava = true);
+    virtual             ~Thread();
+
+    // Start the thread in threadLoop() which needs to be implemented.
+    virtual status_t    run(    const char* name,
+                                int32_t priority = PRIORITY_DEFAULT,
+                                size_t stack = 0);
+    
+    // Ask this object's thread to exit. This function is asynchronous, when the
+    // function returns the thread might still be running. Of course, this
+    // function can be called from a different thread.
+    virtual void        requestExit();
+
+    // Good place to do one-time initializations
+    virtual status_t    readyToRun();
+    
+    // Call requestExit() and wait until this object's thread exits.
+    // BE VERY CAREFUL of deadlocks. In particular, it would be silly to call
+    // this function from this object's thread. Will return WOULD_BLOCK in
+    // that case.
+            status_t    requestExitAndWait();
+
+    // Wait until this object's thread exits. Returns immediately if not yet running.
+    // Do not call from this object's thread; will return WOULD_BLOCK in that case.
+            status_t    join();
+
+    // Indicates whether this thread is running or not.
+            bool        isRunning() const;
+
+#if defined(__ANDROID__)
+    // Return the thread's kernel ID, same as the thread itself calling gettid(),
+    // or -1 if the thread is not running.
+            pid_t       getTid() const;
+#endif
+
+protected:
+    // exitPending() returns true if requestExit() has been called.
+            bool        exitPending() const;
+    
+private:
+    // Derived class must implement threadLoop(). The thread starts its life
+    // here. There are two ways of using the Thread object:
+    // 1) loop: if threadLoop() returns true, it will be called again if
+    //          requestExit() wasn't called.
+    // 2) once: if threadLoop() returns false, the thread will exit upon return.
+    virtual bool        threadLoop() = 0;
+
+private:
+    Thread& operator=(const Thread&);
+    static  int             _threadLoop(void* user);
+    const   bool            mCanCallJava;
+    // always hold mLock when reading or writing
+            thread_id_t     mThread;
+    mutable Mutex           mLock;
+            Condition       mThreadExitedCondition;
+            status_t        mStatus;
+    // note that all accesses of mExitPending and mRunning need to hold mLock
+    volatile bool           mExitPending;
+    volatile bool           mRunning;
+            sp<Thread>      mHoldSelf;
+#if defined(__ANDROID__)
+    // legacy for debugging, not used by getTid() as it is set by the child thread
+    // and so is not initialized until the child reaches that point
+            pid_t           mTid;
+#endif
+};
+
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+#endif // _LIBS_UTILS_THREAD_H
+// ---------------------------------------------------------------------------
diff --git a/libutils/include/utils/ThreadDefs.h b/libutils/include/utils/ThreadDefs.h
new file mode 100644
index 000000000..ae091e40f
--- /dev/null
+++ b/libutils/include/utils/ThreadDefs.h
@@ -0,0 +1,74 @@
+/*
+ * Copyright (C) 2007 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 _LIBS_UTILS_THREAD_DEFS_H
+#define _LIBS_UTILS_THREAD_DEFS_H
+
+#include <stdint.h>
+#include <sys/types.h>
+#include <system/graphics.h>
+#include <system/thread_defs.h>
+
+// ---------------------------------------------------------------------------
+// C API
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#ifdef _WIN32
+typedef uint32_t android_thread_id_t;
+#else
+typedef void* android_thread_id_t;
+#endif
+
+typedef int (*android_thread_func_t)(void*);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+// ---------------------------------------------------------------------------
+// C++ API
+#ifdef __cplusplus
+namespace android {
+// ---------------------------------------------------------------------------
+
+typedef android_thread_id_t thread_id_t;
+typedef android_thread_func_t thread_func_t;
+
+enum {
+    PRIORITY_LOWEST         = ANDROID_PRIORITY_LOWEST,
+    PRIORITY_BACKGROUND     = ANDROID_PRIORITY_BACKGROUND,
+    PRIORITY_NORMAL         = ANDROID_PRIORITY_NORMAL,
+    PRIORITY_FOREGROUND     = ANDROID_PRIORITY_FOREGROUND,
+    PRIORITY_DISPLAY        = ANDROID_PRIORITY_DISPLAY,
+    PRIORITY_URGENT_DISPLAY = ANDROID_PRIORITY_URGENT_DISPLAY,
+    PRIORITY_AUDIO          = ANDROID_PRIORITY_AUDIO,
+    PRIORITY_URGENT_AUDIO   = ANDROID_PRIORITY_URGENT_AUDIO,
+    PRIORITY_HIGHEST        = ANDROID_PRIORITY_HIGHEST,
+    PRIORITY_DEFAULT        = ANDROID_PRIORITY_DEFAULT,
+    PRIORITY_MORE_FAVORABLE = ANDROID_PRIORITY_MORE_FAVORABLE,
+    PRIORITY_LESS_FAVORABLE = ANDROID_PRIORITY_LESS_FAVORABLE,
+};
+
+// ---------------------------------------------------------------------------
+}; // namespace android
+#endif  // __cplusplus
+// ---------------------------------------------------------------------------
+
+
+#endif // _LIBS_UTILS_THREAD_DEFS_H
diff --git a/libutils/include/utils/Timers.h b/libutils/include/utils/Timers.h
new file mode 100644
index 000000000..54ec47489
--- /dev/null
+++ b/libutils/include/utils/Timers.h
@@ -0,0 +1,108 @@
+/*
+ * Copyright (C) 2005 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.
+ */
+
+//
+// Timer functions.
+//
+#ifndef _LIBS_UTILS_TIMERS_H
+#define _LIBS_UTILS_TIMERS_H
+
+#include <stdint.h>
+#include <sys/types.h>
+#include <sys/time.h>
+
+#include <utils/Compat.h>
+
+// ------------------------------------------------------------------
+// C API
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef int64_t nsecs_t;       // nano-seconds
+
+static CONSTEXPR inline nsecs_t seconds_to_nanoseconds(nsecs_t secs)
+{
+    return secs*1000000000;
+}
+
+static CONSTEXPR inline nsecs_t milliseconds_to_nanoseconds(nsecs_t secs)
+{
+    return secs*1000000;
+}
+
+static CONSTEXPR inline nsecs_t microseconds_to_nanoseconds(nsecs_t secs)
+{
+    return secs*1000;
+}
+
+static CONSTEXPR inline nsecs_t nanoseconds_to_seconds(nsecs_t secs)
+{
+    return secs/1000000000;
+}
+
+static CONSTEXPR inline nsecs_t nanoseconds_to_milliseconds(nsecs_t secs)
+{
+    return secs/1000000;
+}
+
+static CONSTEXPR inline nsecs_t nanoseconds_to_microseconds(nsecs_t secs)
+{
+    return secs/1000;
+}
+
+static CONSTEXPR inline nsecs_t s2ns(nsecs_t v)  {return seconds_to_nanoseconds(v);}
+static CONSTEXPR inline nsecs_t ms2ns(nsecs_t v) {return milliseconds_to_nanoseconds(v);}
+static CONSTEXPR inline nsecs_t us2ns(nsecs_t v) {return microseconds_to_nanoseconds(v);}
+static CONSTEXPR inline nsecs_t ns2s(nsecs_t v)  {return nanoseconds_to_seconds(v);}
+static CONSTEXPR inline nsecs_t ns2ms(nsecs_t v) {return nanoseconds_to_milliseconds(v);}
+static CONSTEXPR inline nsecs_t ns2us(nsecs_t v) {return nanoseconds_to_microseconds(v);}
+
+static CONSTEXPR inline nsecs_t seconds(nsecs_t v)      { return s2ns(v); }
+static CONSTEXPR inline nsecs_t milliseconds(nsecs_t v) { return ms2ns(v); }
+static CONSTEXPR inline nsecs_t microseconds(nsecs_t v) { return us2ns(v); }
+
+enum {
+    SYSTEM_TIME_REALTIME = 0,  // system-wide realtime clock
+    SYSTEM_TIME_MONOTONIC = 1, // monotonic time since unspecified starting point
+    SYSTEM_TIME_PROCESS = 2,   // high-resolution per-process clock
+    SYSTEM_TIME_THREAD = 3,    // high-resolution per-thread clock
+    SYSTEM_TIME_BOOTTIME = 4   // same as SYSTEM_TIME_MONOTONIC, but including CPU suspend time
+};
+
+// return the system-time according to the specified clock
+#ifdef __cplusplus
+nsecs_t systemTime(int clock = SYSTEM_TIME_MONOTONIC);
+#else
+nsecs_t systemTime(int clock);
+#endif // def __cplusplus
+
+/**
+ * Returns the number of milliseconds to wait between the reference time and the timeout time.
+ * If the timeout is in the past relative to the reference time, returns 0.
+ * If the timeout is more than INT_MAX milliseconds in the future relative to the reference time,
+ * such as when timeoutTime == LLONG_MAX, returns -1 to indicate an infinite timeout delay.
+ * Otherwise, returns the difference between the reference time and timeout time
+ * rounded up to the next millisecond.
+ */
+int toMillisecondTimeoutDelay(nsecs_t referenceTime, nsecs_t timeoutTime);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // _LIBS_UTILS_TIMERS_H
diff --git a/libutils/include/utils/Tokenizer.h b/libutils/include/utils/Tokenizer.h
new file mode 100644
index 000000000..bb25f374c
--- /dev/null
+++ b/libutils/include/utils/Tokenizer.h
@@ -0,0 +1,136 @@
+/*
+ * 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_TOKENIZER_H
+#define _UTILS_TOKENIZER_H
+
+#include <assert.h>
+#include <utils/Errors.h>
+#include <utils/FileMap.h>
+#include <utils/String8.h>
+
+namespace android {
+
+/**
+ * A simple tokenizer for loading and parsing ASCII text files line by line.
+ */
+class Tokenizer {
+    Tokenizer(const String8& filename, FileMap* fileMap, char* buffer,
+            bool ownBuffer, size_t length);
+
+public:
+    ~Tokenizer();
+
+    /**
+     * Opens a file and maps it into memory.
+     *
+     * Returns NO_ERROR and a tokenizer for the file, if successful.
+     * Otherwise returns an error and sets outTokenizer to NULL.
+     */
+    static status_t open(const String8& filename, Tokenizer** outTokenizer);
+
+    /**
+     * Prepares to tokenize the contents of a string.
+     *
+     * Returns NO_ERROR and a tokenizer for the string, if successful.
+     * Otherwise returns an error and sets outTokenizer to NULL.
+     */
+    static status_t fromContents(const String8& filename,
+            const char* contents, Tokenizer** outTokenizer);
+
+    /**
+     * Returns true if at the end of the file.
+     */
+    inline bool isEof() const { return mCurrent == getEnd(); }
+
+    /**
+     * Returns true if at the end of the line or end of the file.
+     */
+    inline bool isEol() const { return isEof() || *mCurrent == '\n'; }
+
+    /**
+     * Gets the name of the file.
+     */
+    inline String8 getFilename() const { return mFilename; }
+
+    /**
+     * Gets a 1-based line number index for the current position.
+     */
+    inline int32_t getLineNumber() const { return mLineNumber; }
+
+    /**
+     * Formats a location string consisting of the filename and current line number.
+     * Returns a string like "MyFile.txt:33".
+     */
+    String8 getLocation() const;
+
+    /**
+     * Gets the character at the current position.
+     * Returns null at end of file.
+     */
+    inline char peekChar() const { return isEof() ? '\0' : *mCurrent; }
+
+    /**
+     * Gets the remainder of the current line as a string, excluding the newline character.
+     */
+    String8 peekRemainderOfLine() const;
+
+    /**
+     * Gets the character at the current position and advances past it.
+     * Returns null at end of file.
+     */
+    inline char nextChar() { return isEof() ? '\0' : *(mCurrent++); }
+
+    /**
+     * Gets the next token on this line stopping at the specified delimiters
+     * or the end of the line whichever comes first and advances past it.
+     * Also stops at embedded nulls.
+     * Returns the token or an empty string if the current character is a delimiter
+     * or is at the end of the line.
+     */
+    String8 nextToken(const char* delimiters);
+
+    /**
+     * Advances to the next line.
+     * Does nothing if already at the end of the file.
+     */
+    void nextLine();
+
+    /**
+     * Skips over the specified delimiters in the line.
+     * Also skips embedded nulls.
+     */
+    void skipDelimiters(const char* delimiters);
+
+private:
+    Tokenizer(const Tokenizer& other); // not copyable
+
+    String8 mFilename;
+    FileMap* mFileMap;
+    char* mBuffer;
+    bool mOwnBuffer;
+    size_t mLength;
+
+    const char* mCurrent;
+    int32_t mLineNumber;
+
+    inline const char* getEnd() const { return mBuffer + mLength; }
+
+};
+
+} // namespace android
+
+#endif // _UTILS_TOKENIZER_H
diff --git a/libutils/include/utils/Trace.h b/libutils/include/utils/Trace.h
new file mode 100644
index 000000000..eeba40d65
--- /dev/null
+++ b/libutils/include/utils/Trace.h
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2012 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 ANDROID_TRACE_H
+#define ANDROID_TRACE_H
+
+#if defined(__ANDROID__)
+
+#include <fcntl.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <cutils/compiler.h>
+#include <utils/threads.h>
+#include <cutils/trace.h>
+
+// See <cutils/trace.h> for more ATRACE_* macros.
+
+// ATRACE_NAME traces from its location until the end of its enclosing scope.
+#define _PASTE(x, y) x ## y
+#define PASTE(x, y) _PASTE(x,y)
+#define ATRACE_NAME(name) android::ScopedTrace PASTE(___tracer, __LINE__) (ATRACE_TAG, name)
+// ATRACE_CALL is an ATRACE_NAME that uses the current function name.
+#define ATRACE_CALL() ATRACE_NAME(__FUNCTION__)
+
+namespace android {
+
+class ScopedTrace {
+public:
+inline ScopedTrace(uint64_t tag, const char* name)
+    : mTag(tag) {
+    atrace_begin(mTag,name);
+}
+
+inline ~ScopedTrace() {
+    atrace_end(mTag);
+}
+
+private:
+    uint64_t mTag;
+};
+
+}; // namespace android
+
+#else // !__ANDROID__
+
+#define ATRACE_NAME(...)
+#define ATRACE_CALL()
+
+#endif // __ANDROID__
+
+#endif // ANDROID_TRACE_H
diff --git a/libutils/include/utils/TypeHelpers.h b/libutils/include/utils/TypeHelpers.h
new file mode 100644
index 000000000..2a2522722
--- /dev/null
+++ b/libutils/include/utils/TypeHelpers.h
@@ -0,0 +1,336 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_TYPE_HELPERS_H
+#define ANDROID_TYPE_HELPERS_H
+
+#include <new>
+#include <type_traits>
+
+#include <stdint.h>
+#include <string.h>
+#include <sys/types.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+/*
+ * Types traits
+ */
+
+template <typename T> struct trait_trivial_ctor { enum { value = false }; };
+template <typename T> struct trait_trivial_dtor { enum { value = false }; };
+template <typename T> struct trait_trivial_copy { enum { value = false }; };
+template <typename T> struct trait_trivial_move { enum { value = false }; };
+template <typename T> struct trait_pointer      { enum { value = false }; };    
+template <typename T> struct trait_pointer<T*>  { enum { value = true }; };
+
+template <typename TYPE>
+struct traits {
+    enum {
+        // whether this type is a pointer
+        is_pointer          = trait_pointer<TYPE>::value,
+        // whether this type's constructor is a no-op
+        has_trivial_ctor    = is_pointer || trait_trivial_ctor<TYPE>::value,
+        // whether this type's destructor is a no-op
+        has_trivial_dtor    = is_pointer || trait_trivial_dtor<TYPE>::value,
+        // whether this type type can be copy-constructed with memcpy
+        has_trivial_copy    = is_pointer || trait_trivial_copy<TYPE>::value,
+        // whether this type can be moved with memmove
+        has_trivial_move    = is_pointer || trait_trivial_move<TYPE>::value
+    };
+};
+
+template <typename T, typename U>
+struct aggregate_traits {
+    enum {
+        is_pointer          = false,
+        has_trivial_ctor    = 
+            traits<T>::has_trivial_ctor && traits<U>::has_trivial_ctor,
+        has_trivial_dtor    = 
+            traits<T>::has_trivial_dtor && traits<U>::has_trivial_dtor,
+        has_trivial_copy    = 
+            traits<T>::has_trivial_copy && traits<U>::has_trivial_copy,
+        has_trivial_move    = 
+            traits<T>::has_trivial_move && traits<U>::has_trivial_move
+    };
+};
+
+#define ANDROID_TRIVIAL_CTOR_TRAIT( T ) \
+    template<> struct trait_trivial_ctor< T >   { enum { value = true }; };
+
+#define ANDROID_TRIVIAL_DTOR_TRAIT( T ) \
+    template<> struct trait_trivial_dtor< T >   { enum { value = true }; };
+
+#define ANDROID_TRIVIAL_COPY_TRAIT( T ) \
+    template<> struct trait_trivial_copy< T >   { enum { value = true }; };
+
+#define ANDROID_TRIVIAL_MOVE_TRAIT( T ) \
+    template<> struct trait_trivial_move< T >   { enum { value = true }; };
+
+#define ANDROID_BASIC_TYPES_TRAITS( T ) \
+    ANDROID_TRIVIAL_CTOR_TRAIT( T ) \
+    ANDROID_TRIVIAL_DTOR_TRAIT( T ) \
+    ANDROID_TRIVIAL_COPY_TRAIT( T ) \
+    ANDROID_TRIVIAL_MOVE_TRAIT( T )
+
+// ---------------------------------------------------------------------------
+
+/*
+ * basic types traits
+ */
+
+ANDROID_BASIC_TYPES_TRAITS( void )
+ANDROID_BASIC_TYPES_TRAITS( bool )
+ANDROID_BASIC_TYPES_TRAITS( char )
+ANDROID_BASIC_TYPES_TRAITS( unsigned char )
+ANDROID_BASIC_TYPES_TRAITS( short )
+ANDROID_BASIC_TYPES_TRAITS( unsigned short )
+ANDROID_BASIC_TYPES_TRAITS( int )
+ANDROID_BASIC_TYPES_TRAITS( unsigned int )
+ANDROID_BASIC_TYPES_TRAITS( long )
+ANDROID_BASIC_TYPES_TRAITS( unsigned long )
+ANDROID_BASIC_TYPES_TRAITS( long long )
+ANDROID_BASIC_TYPES_TRAITS( unsigned long long )
+ANDROID_BASIC_TYPES_TRAITS( float )
+ANDROID_BASIC_TYPES_TRAITS( double )
+
+// ---------------------------------------------------------------------------
+
+
+/*
+ * compare and order types
+ */
+
+template<typename TYPE> inline
+int strictly_order_type(const TYPE& lhs, const TYPE& rhs) {
+    return (lhs < rhs) ? 1 : 0;
+}
+
+template<typename TYPE> inline
+int compare_type(const TYPE& lhs, const TYPE& rhs) {
+    return strictly_order_type(rhs, lhs) - strictly_order_type(lhs, rhs);
+}
+
+/*
+ * create, destroy, copy and move types...
+ */
+
+template<typename TYPE> inline
+void construct_type(TYPE* p, size_t n) {
+    if (!traits<TYPE>::has_trivial_ctor) {
+        while (n > 0) {
+            n--;
+            new(p++) TYPE;
+        }
+    }
+}
+
+template<typename TYPE> inline
+void destroy_type(TYPE* p, size_t n) {
+    if (!traits<TYPE>::has_trivial_dtor) {
+        while (n > 0) {
+            n--;
+            p->~TYPE();
+            p++;
+        }
+    }
+}
+
+template<typename TYPE>
+typename std::enable_if<traits<TYPE>::has_trivial_copy>::type
+inline
+copy_type(TYPE* d, const TYPE* s, size_t n) {
+    memcpy(d,s,n*sizeof(TYPE));
+}
+
+template<typename TYPE>
+typename std::enable_if<!traits<TYPE>::has_trivial_copy>::type
+inline
+copy_type(TYPE* d, const TYPE* s, size_t n) {
+    while (n > 0) {
+        n--;
+        new(d) TYPE(*s);
+        d++, s++;
+    }
+}
+
+template<typename TYPE> inline
+void splat_type(TYPE* where, const TYPE* what, size_t n) {
+    if (!traits<TYPE>::has_trivial_copy) {
+        while (n > 0) {
+            n--;
+            new(where) TYPE(*what);
+            where++;
+        }
+    } else {
+        while (n > 0) {
+            n--;
+            *where++ = *what;
+        }
+    }
+}
+
+template<typename TYPE>
+struct use_trivial_move : public std::integral_constant<bool,
+    (traits<TYPE>::has_trivial_dtor && traits<TYPE>::has_trivial_copy)
+    || traits<TYPE>::has_trivial_move
+> {};
+
+template<typename TYPE>
+typename std::enable_if<use_trivial_move<TYPE>::value>::type
+inline
+move_forward_type(TYPE* d, const TYPE* s, size_t n = 1) {
+    memmove(d, s, n*sizeof(TYPE));
+}
+
+template<typename TYPE>
+typename std::enable_if<!use_trivial_move<TYPE>::value>::type
+inline
+move_forward_type(TYPE* d, const TYPE* s, size_t n = 1) {
+    d += n;
+    s += n;
+    while (n > 0) {
+        n--;
+        --d, --s;
+        if (!traits<TYPE>::has_trivial_copy) {
+            new(d) TYPE(*s);
+        } else {
+            *d = *s;
+        }
+        if (!traits<TYPE>::has_trivial_dtor) {
+            s->~TYPE();
+        }
+    }
+}
+
+template<typename TYPE>
+typename std::enable_if<use_trivial_move<TYPE>::value>::type
+inline
+move_backward_type(TYPE* d, const TYPE* s, size_t n = 1) {
+    memmove(d, s, n*sizeof(TYPE));
+}
+
+template<typename TYPE>
+typename std::enable_if<!use_trivial_move<TYPE>::value>::type
+inline
+move_backward_type(TYPE* d, const TYPE* s, size_t n = 1) {
+    while (n > 0) {
+        n--;
+        if (!traits<TYPE>::has_trivial_copy) {
+            new(d) TYPE(*s);
+        } else {
+            *d = *s;
+        }
+        if (!traits<TYPE>::has_trivial_dtor) {
+            s->~TYPE();
+        }
+        d++, s++;
+    }
+}
+
+// ---------------------------------------------------------------------------
+
+/*
+ * a key/value pair
+ */
+
+template <typename KEY, typename VALUE>
+struct key_value_pair_t {
+    typedef KEY key_t;
+    typedef VALUE value_t;
+
+    KEY     key;
+    VALUE   value;
+    key_value_pair_t() { }
+    key_value_pair_t(const key_value_pair_t& o) : key(o.key), value(o.value) { }
+    key_value_pair_t& operator=(const key_value_pair_t& o) {
+        key = o.key;
+        value = o.value;
+        return *this;
+    }
+    key_value_pair_t(const KEY& k, const VALUE& v) : key(k), value(v)  { }
+    explicit key_value_pair_t(const KEY& k) : key(k) { }
+    inline bool operator < (const key_value_pair_t& o) const {
+        return strictly_order_type(key, o.key);
+    }
+    inline const KEY& getKey() const {
+        return key;
+    }
+    inline const VALUE& getValue() const {
+        return value;
+    }
+};
+
+template <typename K, typename V>
+struct trait_trivial_ctor< key_value_pair_t<K, V> >
+{ enum { value = aggregate_traits<K,V>::has_trivial_ctor }; };
+template <typename K, typename V>
+struct trait_trivial_dtor< key_value_pair_t<K, V> >
+{ enum { value = aggregate_traits<K,V>::has_trivial_dtor }; };
+template <typename K, typename V>
+struct trait_trivial_copy< key_value_pair_t<K, V> >
+{ enum { value = aggregate_traits<K,V>::has_trivial_copy }; };
+template <typename K, typename V>
+struct trait_trivial_move< key_value_pair_t<K, V> >
+{ enum { value = aggregate_traits<K,V>::has_trivial_move }; };
+
+// ---------------------------------------------------------------------------
+
+/*
+ * Hash codes.
+ */
+typedef uint32_t hash_t;
+
+template <typename TKey>
+hash_t hash_type(const TKey& key);
+
+/* Built-in hash code specializations */
+#define ANDROID_INT32_HASH(T) \
+        template <> inline hash_t hash_type(const T& value) { return hash_t(value); }
+#define ANDROID_INT64_HASH(T) \
+        template <> inline hash_t hash_type(const T& value) { \
+                return hash_t((value >> 32) ^ value); }
+#define ANDROID_REINTERPRET_HASH(T, R) \
+        template <> inline hash_t hash_type(const T& value) { \
+            R newValue; \
+            static_assert(sizeof(newValue) == sizeof(value), "size mismatch"); \
+            memcpy(&newValue, &value, sizeof(newValue)); \
+            return hash_type(newValue); \
+        }
+
+ANDROID_INT32_HASH(bool)
+ANDROID_INT32_HASH(int8_t)
+ANDROID_INT32_HASH(uint8_t)
+ANDROID_INT32_HASH(int16_t)
+ANDROID_INT32_HASH(uint16_t)
+ANDROID_INT32_HASH(int32_t)
+ANDROID_INT32_HASH(uint32_t)
+ANDROID_INT64_HASH(int64_t)
+ANDROID_INT64_HASH(uint64_t)
+ANDROID_REINTERPRET_HASH(float, uint32_t)
+ANDROID_REINTERPRET_HASH(double, uint64_t)
+
+template <typename T> inline hash_t hash_type(T* const & value) {
+    return hash_type(uintptr_t(value));
+}
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_TYPE_HELPERS_H
diff --git a/libutils/include/utils/Unicode.h b/libutils/include/utils/Unicode.h
new file mode 100644
index 000000000..666b70f4e
--- /dev/null
+++ b/libutils/include/utils/Unicode.h
@@ -0,0 +1,178 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_UNICODE_H
+#define ANDROID_UNICODE_H
+
+#include <sys/types.h>
+#include <stdint.h>
+
+extern "C" {
+
+// Standard string functions on char16_t strings.
+int strcmp16(const char16_t *, const char16_t *);
+int strncmp16(const char16_t *s1, const char16_t *s2, size_t n);
+size_t strlen16(const char16_t *);
+size_t strnlen16(const char16_t *, size_t);
+char16_t *strcpy16(char16_t *, const char16_t *);
+char16_t *strncpy16(char16_t *, const char16_t *, size_t);
+char16_t *strstr16(const char16_t*, const char16_t*);
+
+// Version of comparison that supports embedded NULs.
+// This is different than strncmp() because we don't stop
+// at a nul character and consider the strings to be different
+// if the lengths are different (thus we need to supply the
+// lengths of both strings).  This can also be used when
+// your string is not nul-terminated as it will have the
+// equivalent result as strcmp16 (unlike strncmp16).
+int strzcmp16(const char16_t *s1, size_t n1, const char16_t *s2, size_t n2);
+
+// Version of strzcmp16 for comparing strings in different endianness.
+int strzcmp16_h_n(const char16_t *s1H, size_t n1, const char16_t *s2N, size_t n2);
+
+// Standard string functions on char32_t strings.
+size_t strlen32(const char32_t *);
+size_t strnlen32(const char32_t *, size_t);
+
+/**
+ * Measure the length of a UTF-32 string in UTF-8. If the string is invalid
+ * such as containing a surrogate character, -1 will be returned.
+ */
+ssize_t utf32_to_utf8_length(const char32_t *src, size_t src_len);
+
+/**
+ * Stores a UTF-8 string converted from "src" in "dst", if "dst_length" is not
+ * large enough to store the string, the part of the "src" string is stored
+ * into "dst" as much as possible. See the examples for more detail.
+ * Returns the size actually used for storing the string.
+ * dst" is not nul-terminated when dst_len is fully used (like strncpy).
+ *
+ * \code
+ * Example 1
+ * "src" == \u3042\u3044 (\xE3\x81\x82\xE3\x81\x84)
+ * "src_len" == 2
+ * "dst_len" >= 7
+ * ->
+ * Returned value == 6
+ * "dst" becomes \xE3\x81\x82\xE3\x81\x84\0
+ * (note that "dst" is nul-terminated)
+ *
+ * Example 2
+ * "src" == \u3042\u3044 (\xE3\x81\x82\xE3\x81\x84)
+ * "src_len" == 2
+ * "dst_len" == 5
+ * ->
+ * Returned value == 3
+ * "dst" becomes \xE3\x81\x82\0
+ * (note that "dst" is nul-terminated, but \u3044 is not stored in "dst"
+ * since "dst" does not have enough size to store the character)
+ *
+ * Example 3
+ * "src" == \u3042\u3044 (\xE3\x81\x82\xE3\x81\x84)
+ * "src_len" == 2
+ * "dst_len" == 6
+ * ->
+ * Returned value == 6
+ * "dst" becomes \xE3\x81\x82\xE3\x81\x84
+ * (note that "dst" is NOT nul-terminated, like strncpy)
+ * \endcode
+ */
+void utf32_to_utf8(const char32_t* src, size_t src_len, char* dst, size_t dst_len);
+
+/**
+ * Returns the unicode value at "index".
+ * Returns -1 when the index is invalid (equals to or more than "src_len").
+ * If returned value is positive, it is able to be converted to char32_t, which
+ * is unsigned. Then, if "next_index" is not NULL, the next index to be used is
+ * stored in "next_index". "next_index" can be NULL.
+ */
+int32_t utf32_from_utf8_at(const char *src, size_t src_len, size_t index, size_t *next_index);
+
+
+/**
+ * Returns the UTF-8 length of UTF-16 string "src".
+ */
+ssize_t utf16_to_utf8_length(const char16_t *src, size_t src_len);
+
+/**
+ * Converts a UTF-16 string to UTF-8. The destination buffer must be large
+ * enough to fit the UTF-16 as measured by utf16_to_utf8_length with an added
+ * NUL terminator.
+ */
+void utf16_to_utf8(const char16_t* src, size_t src_len, char* dst, size_t dst_len);
+
+/**
+ * Returns the length of "src" when "src" is valid UTF-8 string.
+ * Returns 0 if src is NULL or 0-length string. Returns -1 when the source
+ * is an invalid string.
+ *
+ * This function should be used to determine whether "src" is valid UTF-8
+ * characters with valid unicode codepoints. "src" must be nul-terminated.
+ *
+ * If you are going to use other utf8_to_... functions defined in this header
+ * with string which may not be valid UTF-8 with valid codepoint (form 0 to
+ * 0x10FFFF), you should use this function before calling others, since the
+ * other functions do not check whether the string is valid UTF-8 or not.
+ *
+ * If you do not care whether "src" is valid UTF-8 or not, you should use
+ * strlen() as usual, which should be much faster.
+ */
+ssize_t utf8_length(const char *src);
+
+/**
+ * Measure the length of a UTF-32 string.
+ */
+size_t utf8_to_utf32_length(const char *src, size_t src_len);
+
+/**
+ * Stores a UTF-32 string converted from "src" in "dst". "dst" must be large
+ * enough to store the entire converted string as measured by
+ * utf8_to_utf32_length plus space for a NUL terminator.
+ */
+void utf8_to_utf32(const char* src, size_t src_len, char32_t* dst);
+
+/**
+ * Returns the UTF-16 length of UTF-8 string "src". Returns -1 in case
+ * it's invalid utf8. No buffer over-read occurs because of bound checks. Using overreadIsFatal you
+ * can ask to log a message and fail in case the invalid utf8 could have caused an override if no
+ * bound checks were used (otherwise -1 is returned).
+ */
+ssize_t utf8_to_utf16_length(const uint8_t* src, size_t srcLen, bool overreadIsFatal = false);
+
+/**
+ * Convert UTF-8 to UTF-16 including surrogate pairs.
+ * Returns a pointer to the end of the string (where a NUL terminator might go
+ * if you wanted to add one). At most dstLen characters are written; it won't emit half a surrogate
+ * pair. If dstLen == 0 nothing is written and dst is returned. If dstLen > SSIZE_MAX it aborts
+ * (this being probably a negative number returned as an error and casted to unsigned).
+ */
+char16_t* utf8_to_utf16_no_null_terminator(
+        const uint8_t* src, size_t srcLen, char16_t* dst, size_t dstLen);
+
+/**
+ * Convert UTF-8 to UTF-16 including surrogate pairs. At most dstLen - 1
+ * characters are written; it won't emit half a surrogate pair; and a NUL terminator is appended
+ * after. dstLen - 1 can be measured beforehand using utf8_to_utf16_length. Aborts if dstLen == 0
+ * (at least one character is needed for the NUL terminator) or dstLen > SSIZE_MAX (the latter
+ * case being likely a negative number returned as an error and casted to unsigned) . Returns a
+ * pointer to the NUL terminator.
+ */
+char16_t *utf8_to_utf16(
+        const uint8_t* src, size_t srcLen, char16_t* dst, size_t dstLen);
+
+}
+
+#endif
diff --git a/libutils/include/utils/Vector.h b/libutils/include/utils/Vector.h
new file mode 100644
index 000000000..28a77b834
--- /dev/null
+++ b/libutils/include/utils/Vector.h
@@ -0,0 +1,419 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_VECTOR_H
+#define ANDROID_VECTOR_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <new>
+
+#include <log/log.h>
+#include <utils/TypeHelpers.h>
+#include <utils/VectorImpl.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+template <typename TYPE>
+class SortedVector;
+
+/*!
+ * The main templated vector class ensuring type safety
+ * while making use of VectorImpl.
+ * This is the class users want to use.
+ */
+
+template <class TYPE>
+class Vector : private VectorImpl
+{
+public:
+            typedef TYPE    value_type;
+    
+    /*! 
+     * Constructors and destructors
+     */
+    
+                            Vector();
+                            Vector(const Vector<TYPE>& rhs);
+    explicit                Vector(const SortedVector<TYPE>& rhs);
+    virtual                 ~Vector();
+
+    /*! copy operator */
+            const Vector<TYPE>&     operator = (const Vector<TYPE>& rhs) const;
+            Vector<TYPE>&           operator = (const Vector<TYPE>& rhs);    
+
+            const Vector<TYPE>&     operator = (const SortedVector<TYPE>& rhs) const;
+            Vector<TYPE>&           operator = (const SortedVector<TYPE>& rhs);
+
+            /*
+     * empty the vector
+     */
+
+    inline  void            clear()             { VectorImpl::clear(); }
+
+    /*! 
+     * vector stats
+     */
+
+    //! returns number of items in the vector
+    inline  size_t          size() const                { return VectorImpl::size(); }
+    //! returns whether or not the vector is empty
+    inline  bool            isEmpty() const             { return VectorImpl::isEmpty(); }
+    //! returns how many items can be stored without reallocating the backing store
+    inline  size_t          capacity() const            { return VectorImpl::capacity(); }
+    //! sets the capacity. capacity can never be reduced less than size()
+    inline  ssize_t         setCapacity(size_t size)    { return VectorImpl::setCapacity(size); }
+
+    /*!
+     * set the size of the vector. items are appended with the default
+     * constructor, or removed from the end as needed.
+     */
+    inline  ssize_t         resize(size_t size)         { return VectorImpl::resize(size); }
+
+    /*!
+     * C-style array access
+     */
+     
+    //! read-only C-style access 
+    inline  const TYPE*     array() const;
+    //! read-write C-style access
+            TYPE*           editArray();
+    
+    /*! 
+     * accessors
+     */
+
+    //! read-only access to an item at a given index
+    inline  const TYPE&     operator [] (size_t index) const;
+    //! alternate name for operator []
+    inline  const TYPE&     itemAt(size_t index) const;
+    //! stack-usage of the vector. returns the top of the stack (last element)
+            const TYPE&     top() const;
+
+    /*!
+     * modifying the array
+     */
+
+    //! copy-on write support, grants write access to an item
+            TYPE&           editItemAt(size_t index);
+    //! grants right access to the top of the stack (last element)
+            TYPE&           editTop();
+
+            /*! 
+             * append/insert another vector
+             */
+            
+    //! insert another vector at a given index
+            ssize_t         insertVectorAt(const Vector<TYPE>& vector, size_t index);
+
+    //! append another vector at the end of this one
+            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 length);
+
+    //! append an array at the end of this vector
+            ssize_t         appendArray(const TYPE* array, size_t length);
+
+            /*! 
+             * add/insert/replace items
+             */
+             
+    //! insert one or several items initialized with their default constructor
+    inline  ssize_t         insertAt(size_t index, size_t numItems = 1);
+    //! insert one or several items initialized from a prototype item
+            ssize_t         insertAt(const TYPE& prototype_item, size_t index, size_t numItems = 1);
+    //! pop the top of the stack (removes the last element). No-op if the stack's empty
+    inline  void            pop();
+    //! pushes an item initialized with its default constructor
+    inline  void            push();
+    //! pushes an item on the top of the stack
+            void            push(const TYPE& item);
+    //! same as push() but returns the index the item was added at (or an error)
+    inline  ssize_t         add();
+    //! same as push() but returns the index the item was added at (or an error)
+            ssize_t         add(const TYPE& item);            
+    //! replace an item with a new one initialized with its default constructor
+    inline  ssize_t         replaceAt(size_t index);
+    //! replace an item with a new one
+            ssize_t         replaceAt(const TYPE& item, size_t index);
+
+    /*!
+     * remove items
+     */
+
+    //! remove several items
+    inline  ssize_t         removeItemsAt(size_t index, size_t count = 1);
+    //! remove one item
+    inline  ssize_t         removeAt(size_t index)  { return removeItemsAt(index); }
+
+    /*!
+     * sort (stable) the array
+     */
+     
+     typedef int (*compar_t)(const TYPE* lhs, const TYPE* rhs);
+     typedef int (*compar_r_t)(const TYPE* lhs, const TYPE* rhs, void* state);
+     
+     inline status_t        sort(compar_t cmp);
+     inline status_t        sort(compar_r_t cmp, void* state);
+
+     // for debugging only
+     inline size_t getItemSize() const { return itemSize(); }
+
+
+     /*
+      * these inlines add some level of compatibility with STL. eventually
+      * we should probably turn things around.
+      */
+     typedef TYPE* iterator;
+     typedef TYPE const* const_iterator;
+
+     inline iterator begin() { return editArray(); }
+     inline iterator end()   { return editArray() + size(); }
+     inline const_iterator begin() const { return array(); }
+     inline const_iterator end() const   { return array() + size(); }
+     inline void reserve(size_t n) { setCapacity(n); }
+     inline bool empty() const{ return isEmpty(); }
+     inline void push_back(const TYPE& item)  { insertAt(item, size(), 1); }
+     inline void push_front(const TYPE& item) { insertAt(item, 0, 1); }
+     inline iterator erase(iterator pos) {
+         ssize_t index = removeItemsAt(static_cast<size_t>(pos-array()));
+         return begin() + index;
+     }
+
+protected:
+    virtual void    do_construct(void* storage, size_t num) const;
+    virtual void    do_destroy(void* storage, size_t num) const;
+    virtual void    do_copy(void* dest, const void* from, size_t num) const;
+    virtual void    do_splat(void* dest, const void* item, size_t num) const;
+    virtual void    do_move_forward(void* dest, const void* from, size_t num) const;
+    virtual void    do_move_backward(void* dest, const void* from, size_t num) const;
+};
+
+// ---------------------------------------------------------------------------
+// No user serviceable parts from here...
+// ---------------------------------------------------------------------------
+
+template<class TYPE> inline
+Vector<TYPE>::Vector()
+    : VectorImpl(sizeof(TYPE),
+                ((traits<TYPE>::has_trivial_ctor   ? HAS_TRIVIAL_CTOR   : 0)
+                |(traits<TYPE>::has_trivial_dtor   ? HAS_TRIVIAL_DTOR   : 0)
+                |(traits<TYPE>::has_trivial_copy   ? HAS_TRIVIAL_COPY   : 0))
+                )
+{
+}
+
+template<class TYPE> inline
+Vector<TYPE>::Vector(const Vector<TYPE>& rhs)
+    : VectorImpl(rhs) {
+}
+
+template<class TYPE> inline
+Vector<TYPE>::Vector(const SortedVector<TYPE>& rhs)
+    : VectorImpl(static_cast<const VectorImpl&>(rhs)) {
+}
+
+template<class TYPE> inline
+Vector<TYPE>::~Vector() {
+    finish_vector();
+}
+
+template<class TYPE> inline
+Vector<TYPE>& Vector<TYPE>::operator = (const Vector<TYPE>& rhs) {
+    VectorImpl::operator = (rhs);
+    return *this; 
+}
+
+template<class TYPE> inline
+const Vector<TYPE>& Vector<TYPE>::operator = (const Vector<TYPE>& rhs) const {
+    VectorImpl::operator = (static_cast<const VectorImpl&>(rhs));
+    return *this;
+}
+
+template<class TYPE> inline
+Vector<TYPE>& Vector<TYPE>::operator = (const SortedVector<TYPE>& rhs) {
+    VectorImpl::operator = (static_cast<const VectorImpl&>(rhs));
+    return *this;
+}
+
+template<class TYPE> inline
+const Vector<TYPE>& Vector<TYPE>::operator = (const SortedVector<TYPE>& rhs) const {
+    VectorImpl::operator = (rhs);
+    return *this; 
+}
+
+template<class TYPE> inline
+const TYPE* Vector<TYPE>::array() const {
+    return static_cast<const TYPE *>(arrayImpl());
+}
+
+template<class TYPE> inline
+TYPE* Vector<TYPE>::editArray() {
+    return static_cast<TYPE *>(editArrayImpl());
+}
+
+
+template<class TYPE> inline
+const TYPE& Vector<TYPE>::operator[](size_t index) const {
+    LOG_FATAL_IF(index>=size(),
+            "%s: index=%u out of range (%u)", __PRETTY_FUNCTION__,
+            int(index), int(size()));
+    return *(array() + index);
+}
+
+template<class TYPE> inline
+const TYPE& Vector<TYPE>::itemAt(size_t index) const {
+    return operator[](index);
+}
+
+template<class TYPE> inline
+const TYPE& Vector<TYPE>::top() const {
+    return *(array() + size() - 1);
+}
+
+template<class TYPE> inline
+TYPE& Vector<TYPE>::editItemAt(size_t index) {
+    return *( static_cast<TYPE *>(editItemLocation(index)) );
+}
+
+template<class TYPE> inline
+TYPE& Vector<TYPE>::editTop() {
+    return *( static_cast<TYPE *>(editItemLocation(size()-1)) );
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::insertVectorAt(const Vector<TYPE>& vector, size_t index) {
+    return VectorImpl::insertVectorAt(reinterpret_cast<const VectorImpl&>(vector), index);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::appendVector(const Vector<TYPE>& vector) {
+    return VectorImpl::appendVector(reinterpret_cast<const VectorImpl&>(vector));
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::insertArrayAt(const TYPE* array, size_t index, size_t length) {
+    return VectorImpl::insertArrayAt(array, index, length);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::appendArray(const TYPE* array, size_t length) {
+    return VectorImpl::appendArray(array, length);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::insertAt(const TYPE& item, size_t index, size_t numItems) {
+    return VectorImpl::insertAt(&item, index, numItems);
+}
+
+template<class TYPE> inline
+void Vector<TYPE>::push(const TYPE& item) {
+    return VectorImpl::push(&item);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::add(const TYPE& item) {
+    return VectorImpl::add(&item);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::replaceAt(const TYPE& item, size_t index) {
+    return VectorImpl::replaceAt(&item, index);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::insertAt(size_t index, size_t numItems) {
+    return VectorImpl::insertAt(index, numItems);
+}
+
+template<class TYPE> inline
+void Vector<TYPE>::pop() {
+    VectorImpl::pop();
+}
+
+template<class TYPE> inline
+void Vector<TYPE>::push() {
+    VectorImpl::push();
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::add() {
+    return VectorImpl::add();
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::replaceAt(size_t index) {
+    return VectorImpl::replaceAt(index);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::removeItemsAt(size_t index, size_t count) {
+    return VectorImpl::removeItemsAt(index, count);
+}
+
+template<class TYPE> inline
+status_t Vector<TYPE>::sort(Vector<TYPE>::compar_t cmp) {
+    return VectorImpl::sort(reinterpret_cast<VectorImpl::compar_t>(cmp));
+}
+
+template<class TYPE> inline
+status_t Vector<TYPE>::sort(Vector<TYPE>::compar_r_t cmp, void* state) {
+    return VectorImpl::sort(reinterpret_cast<VectorImpl::compar_r_t>(cmp), state);
+}
+
+// ---------------------------------------------------------------------------
+
+template<class TYPE>
+void Vector<TYPE>::do_construct(void* storage, size_t num) const {
+    construct_type( reinterpret_cast<TYPE*>(storage), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_destroy(void* storage, size_t num) const {
+    destroy_type( reinterpret_cast<TYPE*>(storage), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_copy(void* dest, const void* from, size_t num) const {
+    copy_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_splat(void* dest, const void* item, size_t num) const {
+    splat_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(item), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_move_forward(void* dest, const void* from, size_t num) const {
+    move_forward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_move_backward(void* dest, const void* from, size_t num) const {
+    move_backward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
+}
+
+}; // namespace android
+
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_VECTOR_H
diff --git a/libutils/include/utils/VectorImpl.h b/libutils/include/utils/VectorImpl.h
new file mode 100644
index 000000000..4dd91fd29
--- /dev/null
+++ b/libutils/include/utils/VectorImpl.h
@@ -0,0 +1,183 @@
+/*
+ * Copyright (C) 2005 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 ANDROID_VECTOR_IMPL_H
+#define ANDROID_VECTOR_IMPL_H
+
+#include <assert.h>
+#include <stdint.h>
+#include <sys/types.h>
+#include <utils/Errors.h>
+
+// ---------------------------------------------------------------------------
+// No user serviceable parts in here...
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+/*!
+ * Implementation of the guts of the vector<> class
+ * this ensures backward binary compatibility and
+ * reduces code size.
+ * For performance reasons, we expose mStorage and mCount
+ * so these fields are set in stone.
+ *
+ */
+
+class VectorImpl
+{
+public:
+    enum { // flags passed to the ctor
+        HAS_TRIVIAL_CTOR    = 0x00000001,
+        HAS_TRIVIAL_DTOR    = 0x00000002,
+        HAS_TRIVIAL_COPY    = 0x00000004,
+    };
+
+                            VectorImpl(size_t itemSize, uint32_t flags);
+                            VectorImpl(const VectorImpl& rhs);
+    virtual                 ~VectorImpl();
+
+    /*! must be called from subclasses destructor */
+            void            finish_vector();
+
+            VectorImpl&     operator = (const VectorImpl& rhs);    
+            
+    /*! C-style array access */
+    inline  const void*     arrayImpl() const       { return mStorage; }
+            void*           editArrayImpl();
+            
+    /*! vector stats */
+    inline  size_t          size() const        { return mCount; }
+    inline  bool            isEmpty() const     { return mCount == 0; }
+            size_t          capacity() const;
+            ssize_t         setCapacity(size_t size);
+            ssize_t         resize(size_t size);
+
+            /*! append/insert another vector or array */
+            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 length);
+            ssize_t         appendArray(const void* array, size_t length);
+            
+            /*! add/insert/replace items */
+            ssize_t         insertAt(size_t where, size_t numItems = 1);
+            ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
+            void            pop();
+            void            push();
+            void            push(const void* item);
+            ssize_t         add();
+            ssize_t         add(const void* item);
+            ssize_t         replaceAt(size_t index);
+            ssize_t         replaceAt(const void* item, size_t index);
+
+            /*! remove items */
+            ssize_t         removeItemsAt(size_t index, size_t count = 1);
+            void            clear();
+
+            const void*     itemLocation(size_t index) const;
+            void*           editItemLocation(size_t index);
+
+            typedef int (*compar_t)(const void* lhs, const void* rhs);
+            typedef int (*compar_r_t)(const void* lhs, const void* rhs, void* state);
+            status_t        sort(compar_t cmp);
+            status_t        sort(compar_r_t cmp, void* state);
+
+protected:
+            size_t          itemSize() const;
+            void            release_storage();
+
+    virtual void            do_construct(void* storage, size_t num) const = 0;
+    virtual void            do_destroy(void* storage, size_t num) const = 0;
+    virtual void            do_copy(void* dest, const void* from, size_t num) const = 0;
+    virtual void            do_splat(void* dest, const void* item, size_t num) const = 0;
+    virtual void            do_move_forward(void* dest, const void* from, size_t num) const = 0;
+    virtual void            do_move_backward(void* dest, const void* from, size_t num) const = 0;
+    
+private:
+        void* _grow(size_t where, size_t amount);
+        void  _shrink(size_t where, size_t amount);
+
+        inline void _do_construct(void* storage, size_t num) const;
+        inline void _do_destroy(void* storage, size_t num) const;
+        inline void _do_copy(void* dest, const void* from, size_t num) const;
+        inline void _do_splat(void* dest, const void* item, size_t num) const;
+        inline void _do_move_forward(void* dest, const void* from, size_t num) const;
+        inline void _do_move_backward(void* dest, const void* from, size_t num) const;
+
+            // These 2 fields are exposed in the inlines below,
+            // so they're set in stone.
+            void *      mStorage;   // base address of the vector
+            size_t      mCount;     // number of items
+
+    const   uint32_t    mFlags;
+    const   size_t      mItemSize;
+};
+
+
+
+class SortedVectorImpl : public VectorImpl
+{
+public:
+                            SortedVectorImpl(size_t itemSize, uint32_t flags);
+    explicit                SortedVectorImpl(const VectorImpl& rhs);
+    virtual                 ~SortedVectorImpl();
+    
+    SortedVectorImpl&     operator = (const SortedVectorImpl& rhs);    
+
+    //! finds the index of an item
+            ssize_t         indexOf(const void* item) const;
+
+    //! finds where this item should be inserted
+            size_t          orderOf(const void* item) const;
+
+    //! add an item in the right place (or replaces it if there is one)
+            ssize_t         add(const void* item);
+
+    //! merges a vector into this one
+            ssize_t         merge(const VectorImpl& vector);
+            ssize_t         merge(const SortedVectorImpl& vector);
+             
+    //! removes an item
+            ssize_t         remove(const void* item);
+        
+protected:
+    virtual int             do_compare(const void* lhs, const void* rhs) const = 0;
+
+private:
+            ssize_t         _indexOrderOf(const void* item, size_t* order = 0) const;
+
+            // these are made private, because they can't be used on a SortedVector
+            // (they don't have an implementation either)
+            ssize_t         add();
+            void            pop();
+            void            push();
+            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 length);
+            ssize_t         appendArray(const void* array, size_t length);
+            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);
+            ssize_t         replaceAt(const void* item, size_t index);
+};
+
+}; // namespace android
+
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_VECTOR_IMPL_H
diff --git a/libutils/include/utils/misc.h b/libutils/include/utils/misc.h
new file mode 100644
index 000000000..6cccec387
--- /dev/null
+++ b/libutils/include/utils/misc.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2005 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.
+ */
+
+//
+// Handy utility functions and portability code.
+//
+#ifndef _LIBS_UTILS_MISC_H
+#define _LIBS_UTILS_MISC_H
+
+#include <utils/Endian.h>
+
+/* get #of elements in a static array */
+#ifndef NELEM
+# define NELEM(x) ((int) (sizeof(x) / sizeof((x)[0])))
+#endif
+
+namespace android {
+
+typedef void (*sysprop_change_callback)(void);
+void add_sysprop_change_callback(sysprop_change_callback cb, int priority);
+void report_sysprop_change();
+
+}; // namespace android
+
+#endif // _LIBS_UTILS_MISC_H
diff --git a/libutils/include/utils/threads.h b/libutils/include/utils/threads.h
new file mode 100644
index 000000000..9de338211
--- /dev/null
+++ b/libutils/include/utils/threads.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2007 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 _LIBS_UTILS_THREADS_H
+#define _LIBS_UTILS_THREADS_H
+
+/*
+ * Please, DO NOT USE!
+ *
+ * This file is here only for legacy reasons. Instead, include directly
+ * the headers you need below.
+ *
+ */
+
+#include <utils/AndroidThreads.h>
+
+#ifdef __cplusplus
+#include <utils/Condition.h>
+#include <utils/Errors.h>
+#include <utils/Mutex.h>
+#include <utils/RWLock.h>
+#include <utils/Thread.h>
+#endif
+
+#endif // _LIBS_UTILS_THREADS_H