Merge commit '536dea9d61a032e64bbe584a97463c6638ead009' into HEAD

Change-Id: I5c469a4b738629d99d721cad7ded02d6c35f56d5

48 files changed, 7591 insertions, 0 deletions

diff --git a/include/utils/AndroidThreads.h b/include/utils/AndroidThreads.h
new file mode 100644
index 0000000..4eee14d
--- /dev/null
+++ b/include/utils/AndroidThreads.h
@@ -0,0 +1,128 @@
+/*
+ * 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(HAVE_PTHREADS)
+# 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.
+
+// Get pid for the current thread.
+extern pid_t androidGetTid();
+
+#ifdef HAVE_ANDROID_OS
+// 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/include/utils/Atomic.h b/include/utils/Atomic.h
new file mode 100644
index 0000000..7eb476c
--- /dev/null
+++ b/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/include/utils/BasicHashtable.h b/include/utils/BasicHashtable.h
new file mode 100644
index 0000000..c235d62
--- /dev/null
+++ b/include/utils/BasicHashtable.h
@@ -0,0 +1,402 @@
+/*
+ * 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_BASIC_HASHTABLE_H
+#define ANDROID_BASIC_HASHTABLE_H
+
+#include <stdint.h>
+#include <sys/types.h>
+#include <utils/SharedBuffer.h>
+#include <utils/TypeHelpers.h>
+
+namespace android {
+
+/* Implementation type.  Nothing to see here. */
+class BasicHashtableImpl {
+protected:
+    struct Bucket {
+        // The collision flag indicates that the bucket is part of a collision chain
+        // such that at least two entries both hash to this bucket.  When true, we
+        // may need to seek further along the chain to find the entry.
+        static const uint32_t COLLISION = 0x80000000UL;
+
+        // The present flag indicates that the bucket contains an initialized entry value.
+        static const uint32_t PRESENT   = 0x40000000UL;
+
+        // Mask for 30 bits worth of the hash code that are stored within the bucket to
+        // speed up lookups and rehashing by eliminating the need to recalculate the
+        // hash code of the entry's key.
+        static const uint32_t HASH_MASK = 0x3fffffffUL;
+
+        // Combined value that stores the collision and present flags as well as
+        // a 30 bit hash code.
+        uint32_t cookie;
+
+        // Storage for the entry begins here.
+        char entry[0];
+    };
+
+    BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor,
+            size_t minimumInitialCapacity, float loadFactor);
+    BasicHashtableImpl(const BasicHashtableImpl& other);
+    virtual ~BasicHashtableImpl();
+
+    void dispose();
+
+    inline void edit() {
+        if (mBuckets && !SharedBuffer::bufferFromData(mBuckets)->onlyOwner()) {
+            clone();
+        }
+    }
+
+    void setTo(const BasicHashtableImpl& other);
+    void clear();
+
+    ssize_t next(ssize_t index) const;
+    ssize_t find(ssize_t index, hash_t hash, const void* __restrict__ key) const;
+    size_t add(hash_t hash, const void* __restrict__ entry);
+    void removeAt(size_t index);
+    void rehash(size_t minimumCapacity, float loadFactor);
+
+    const size_t mBucketSize; // number of bytes per bucket including the entry
+    const bool mHasTrivialDestructor; // true if the entry type does not require destruction
+    size_t mCapacity;         // number of buckets that can be filled before exceeding load factor
+    float mLoadFactor;        // load factor
+    size_t mSize;             // number of elements actually in the table
+    size_t mFilledBuckets;    // number of buckets for which collision or present is true
+    size_t mBucketCount;      // number of slots in the mBuckets array
+    void* mBuckets;           // array of buckets, as a SharedBuffer
+
+    inline const Bucket& bucketAt(const void* __restrict__ buckets, size_t index) const {
+        return *reinterpret_cast<const Bucket*>(
+                static_cast<const uint8_t*>(buckets) + index * mBucketSize);
+    }
+
+    inline Bucket& bucketAt(void* __restrict__ buckets, size_t index) const {
+        return *reinterpret_cast<Bucket*>(static_cast<uint8_t*>(buckets) + index * mBucketSize);
+    }
+
+    virtual bool compareBucketKey(const Bucket& bucket, const void* __restrict__ key) const = 0;
+    virtual void initializeBucketEntry(Bucket& bucket, const void* __restrict__ entry) const = 0;
+    virtual void destroyBucketEntry(Bucket& bucket) const = 0;
+
+private:
+    void clone();
+
+    // Allocates a bucket array as a SharedBuffer.
+    void* allocateBuckets(size_t count) const;
+
+    // Releases a bucket array's associated SharedBuffer.
+    void releaseBuckets(void* __restrict__ buckets, size_t count) const;
+
+    // Destroys the contents of buckets (invokes destroyBucketEntry for each
+    // populated bucket if needed).
+    void destroyBuckets(void* __restrict__ buckets, size_t count) const;
+
+    // Copies the content of buckets (copies the cookie and invokes copyBucketEntry
+    // for each populated bucket if needed).
+    void copyBuckets(const void* __restrict__ fromBuckets,
+            void* __restrict__ toBuckets, size_t count) const;
+
+    // Determines the appropriate size of a bucket array to store a certain minimum
+    // number of entries and returns its effective capacity.
+    static void determineCapacity(size_t minimumCapacity, float loadFactor,
+            size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity);
+
+    // Trim a hash code to 30 bits to match what we store in the bucket's cookie.
+    inline static hash_t trimHash(hash_t hash) {
+        return (hash & Bucket::HASH_MASK) ^ (hash >> 30);
+    }
+
+    // Returns the index of the first bucket that is in the collision chain
+    // for the specified hash code, given the total number of buckets.
+    // (Primary hash)
+    inline static size_t chainStart(hash_t hash, size_t count) {
+        return hash % count;
+    }
+
+    // Returns the increment to add to a bucket index to seek to the next bucket
+    // in the collision chain for the specified hash code, given the total number of buckets.
+    // (Secondary hash)
+    inline static size_t chainIncrement(hash_t hash, size_t count) {
+        return ((hash >> 7) | (hash << 25)) % (count - 1) + 1;
+    }
+
+    // Returns the index of the next bucket that is in the collision chain
+    // that is defined by the specified increment, given the total number of buckets.
+    inline static size_t chainSeek(size_t index, size_t increment, size_t count) {
+        return (index + increment) % count;
+    }
+};
+
+/*
+ * A BasicHashtable stores entries that are indexed by hash code in place
+ * within an array.  The basic operations are finding entries by key,
+ * adding new entries and removing existing entries.
+ *
+ * This class provides a very limited set of operations with simple semantics.
+ * It is intended to be used as a building block to construct more complex
+ * and interesting data structures such as HashMap.  Think very hard before
+ * adding anything extra to BasicHashtable, it probably belongs at a
+ * higher level of abstraction.
+ *
+ * TKey: The key type.
+ * TEntry: The entry type which is what is actually stored in the array.
+ *
+ * TKey must support the following contract:
+ *     bool operator==(const TKey& other) const;  // return true if equal
+ *     bool operator!=(const TKey& other) const;  // return true if unequal
+ *
+ * TEntry must support the following contract:
+ *     const TKey& getKey() const;  // get the key from the entry
+ *
+ * This class supports storing entries with duplicate keys.  Of course, it can't
+ * tell them apart during removal so only the first entry will be removed.
+ * We do this because it means that operations like add() can't fail.
+ */
+template <typename TKey, typename TEntry>
+class BasicHashtable : private BasicHashtableImpl {
+public:
+    /* Creates a hashtable with the specified minimum initial capacity.
+     * The underlying array will be created when the first entry is added.
+     *
+     * minimumInitialCapacity: The minimum initial capacity for the hashtable.
+     *     Default is 0.
+     * loadFactor: The desired load factor for the hashtable, between 0 and 1.
+     *     Default is 0.75.
+     */
+    BasicHashtable(size_t minimumInitialCapacity = 0, float loadFactor = 0.75f);
+
+    /* Copies a hashtable.
+     * The underlying storage is shared copy-on-write.
+     */
+    BasicHashtable(const BasicHashtable& other);
+
+    /* Clears and destroys the hashtable.
+     */
+    virtual ~BasicHashtable();
+
+    /* Making this hashtable a copy of the other hashtable.
+     * The underlying storage is shared copy-on-write.
+     *
+     * other: The hashtable to copy.
+     */
+    inline BasicHashtable<TKey, TEntry>& operator =(const BasicHashtable<TKey, TEntry> & other) {
+        setTo(other);
+        return *this;
+    }
+
+    /* Returns the number of entries in the hashtable.
+     */
+    inline size_t size() const {
+        return mSize;
+    }
+
+    /* Returns the capacity of the hashtable, which is the number of elements that can
+     * added to the hashtable without requiring it to be grown.
+     */
+    inline size_t capacity() const {
+        return mCapacity;
+    }
+
+    /* Returns the number of buckets that the hashtable has, which is the size of its
+     * underlying array.
+     */
+    inline size_t bucketCount() const {
+        return mBucketCount;
+    }
+
+    /* Returns the load factor of the hashtable. */
+    inline float loadFactor() const {
+        return mLoadFactor;
+    };
+
+    /* Returns a const reference to the entry at the specified index.
+     *
+     * index:   The index of the entry to retrieve.  Must be a valid index within
+     *          the bounds of the hashtable.
+     */
+    inline const TEntry& entryAt(size_t index) const {
+        return entryFor(bucketAt(mBuckets, index));
+    }
+
+    /* Returns a non-const reference to the entry at the specified index.
+     *
+     * index: The index of the entry to edit.  Must be a valid index within
+     *        the bounds of the hashtable.
+     */
+    inline TEntry& editEntryAt(size_t index) {
+        edit();
+        return entryFor(bucketAt(mBuckets, index));
+    }
+
+    /* Clears the hashtable.
+     * All entries in the hashtable are destroyed immediately.
+     * If you need to do something special with the entries in the hashtable then iterate
+     * over them and do what you need before clearing the hashtable.
+     */
+    inline void clear() {
+        BasicHashtableImpl::clear();
+    }
+
+    /* Returns the index of the next entry in the hashtable given the index of a previous entry.
+     * If the given index is -1, then returns the index of the first entry in the hashtable,
+     * if there is one, or -1 otherwise.
+     * If the given index is not -1, then returns the index of the next entry in the hashtable,
+     * in strictly increasing order, or -1 if there are none left.
+     *
+     * index:   The index of the previous entry that was iterated, or -1 to begin
+     *          iteration at the beginning of the hashtable.
+     */
+    inline ssize_t next(ssize_t index) const {
+        return BasicHashtableImpl::next(index);
+    }
+
+    /* Finds the index of an entry with the specified key.
+     * If the given index is -1, then returns the index of the first matching entry,
+     * otherwise returns the index of the next matching entry.
+     * If the hashtable contains multiple entries with keys that match the requested
+     * key, then the sequence of entries returned is arbitrary.
+     * Returns -1 if no entry was found.
+     *
+     * index:   The index of the previous entry with the specified key, or -1 to
+     *          find the first matching entry.
+     * hash:    The hashcode of the key.
+     * key:     The key.
+     */
+    inline ssize_t find(ssize_t index, hash_t hash, const TKey& key) const {
+        return BasicHashtableImpl::find(index, hash, &key);
+    }
+
+    /* Adds the entry to the hashtable.
+     * Returns the index of the newly added entry.
+     * If an entry with the same key already exists, then a duplicate entry is added.
+     * If the entry will not fit, then the hashtable's capacity is increased and
+     * its contents are rehashed.  See rehash().
+     *
+     * hash:    The hashcode of the key.
+     * entry:   The entry to add.
+     */
+    inline size_t add(hash_t hash, const TEntry& entry) {
+        return BasicHashtableImpl::add(hash, &entry);
+    }
+
+    /* Removes the entry with the specified index from the hashtable.
+     * The entry is destroyed immediately.
+     * The index must be valid.
+     *
+     * The hashtable is not compacted after an item is removed, so it is legal
+     * to continue iterating over the hashtable using next() or find().
+     *
+     * index:   The index of the entry to remove.  Must be a valid index within the
+     *          bounds of the hashtable, and it must refer to an existing entry.
+     */
+    inline void removeAt(size_t index) {
+        BasicHashtableImpl::removeAt(index);
+    }
+
+    /* Rehashes the contents of the hashtable.
+     * Grows the hashtable to at least the specified minimum capacity or the
+     * current number of elements, whichever is larger.
+     *
+     * Rehashing causes all entries to be copied and the entry indices may change.
+     * Although the hash codes are cached by the hashtable, rehashing can be an
+     * expensive operation and should be avoided unless the hashtable's size
+     * needs to be changed.
+     *
+     * Rehashing is the only way to change the capacity or load factor of the
+     * hashtable once it has been created.  It can be used to compact the
+     * hashtable by choosing a minimum capacity that is smaller than the current
+     * capacity (such as 0).
+     *
+     * minimumCapacity: The desired minimum capacity after rehashing.
+     * loadFactor: The desired load factor after rehashing.
+     */
+    inline void rehash(size_t minimumCapacity, float loadFactor) {
+        BasicHashtableImpl::rehash(minimumCapacity, loadFactor);
+    }
+
+    /* Determines whether there is room to add another entry without rehashing.
+     * When this returns true, a subsequent add() operation is guaranteed to
+     * complete without performing a rehash.
+     */
+    inline bool hasMoreRoom() const {
+        return mCapacity > mFilledBuckets;
+    }
+
+protected:
+    static inline const TEntry& entryFor(const Bucket& bucket) {
+        return reinterpret_cast<const TEntry&>(bucket.entry);
+    }
+
+    static inline TEntry& entryFor(Bucket& bucket) {
+        return reinterpret_cast<TEntry&>(bucket.entry);
+    }
+
+    virtual bool compareBucketKey(const Bucket& bucket, const void* __restrict__ key) const;
+    virtual void initializeBucketEntry(Bucket& bucket, const void* __restrict__ entry) const;
+    virtual void destroyBucketEntry(Bucket& bucket) const;
+
+private:
+    // For dumping the raw contents of a hashtable during testing.
+    friend class BasicHashtableTest;
+    inline uint32_t cookieAt(size_t index) const {
+        return bucketAt(mBuckets, index).cookie;
+    }
+};
+
+template <typename TKey, typename TEntry>
+BasicHashtable<TKey, TEntry>::BasicHashtable(size_t minimumInitialCapacity, float loadFactor) :
+        BasicHashtableImpl(sizeof(TEntry), traits<TEntry>::has_trivial_dtor,
+                minimumInitialCapacity, loadFactor) {
+}
+
+template <typename TKey, typename TEntry>
+BasicHashtable<TKey, TEntry>::BasicHashtable(const BasicHashtable<TKey, TEntry>& other) :
+        BasicHashtableImpl(other) {
+}
+
+template <typename TKey, typename TEntry>
+BasicHashtable<TKey, TEntry>::~BasicHashtable() {
+    dispose();
+}
+
+template <typename TKey, typename TEntry>
+bool BasicHashtable<TKey, TEntry>::compareBucketKey(const Bucket& bucket,
+        const void* __restrict__ key) const {
+    return entryFor(bucket).getKey() == *static_cast<const TKey*>(key);
+}
+
+template <typename TKey, typename TEntry>
+void BasicHashtable<TKey, TEntry>::initializeBucketEntry(Bucket& bucket,
+        const void* __restrict__ entry) const {
+    if (!traits<TEntry>::has_trivial_copy) {
+        new (&entryFor(bucket)) TEntry(*(static_cast<const TEntry*>(entry)));
+    } else {
+        memcpy(&entryFor(bucket), entry, sizeof(TEntry));
+    }
+}
+
+template <typename TKey, typename TEntry>
+void BasicHashtable<TKey, TEntry>::destroyBucketEntry(Bucket& bucket) const {
+    if (!traits<TEntry>::has_trivial_dtor) {
+        entryFor(bucket).~TEntry();
+    }
+}
+
+}; // namespace android
+
+#endif // ANDROID_BASIC_HASHTABLE_H
diff --git a/include/utils/BitSet.h b/include/utils/BitSet.h
new file mode 100644
index 0000000..19c03d1
--- /dev/null
+++ b/include/utils/BitSet.h
@@ -0,0 +1,124 @@
+/*
+ * 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(0) { }
+    explicit inline BitSet32(uint32_t value) : value(value) { }
+
+    // Gets the value associated with a particular bit index.
+    static inline uint32_t valueForBit(uint32_t n) { return 0x80000000 >> n; }
+
+    // Clears the bit set.
+    inline void clear() { value = 0; }
+
+    // Returns the number of marked bits in the set.
+    inline uint32_t count() const { return __builtin_popcount(value); }
+
+    // Returns true if the bit set does not contain any marked bits.
+    inline bool isEmpty() const { return ! value; }
+
+    // Returns true if the bit set does not contain any unmarked bits.
+    inline bool isFull() const { return value == 0xffffffff; }
+
+    // Returns true if the specified bit is marked.
+    inline bool hasBit(uint32_t n) const { return value & valueForBit(n); }
+
+    // Marks the specified bit.
+    inline void markBit(uint32_t n) { value |= valueForBit(n); }
+
+    // Clears the specified bit.
+    inline void clearBit(uint32_t n) { value &= ~ valueForBit(n); }
+
+    // Finds the first marked bit in the set.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t firstMarkedBit() const { return __builtin_clz(value); }
+
+    // Finds the first unmarked bit in the set.
+    // Result is undefined if all bits are marked.
+    inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); }
+
+    // Finds the last marked bit in the set.
+    // Result is undefined if all bits are unmarked.
+    inline uint32_t lastMarkedBit() const { return 31 - __builtin_ctz(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() {
+        uint32_t n = firstMarkedBit();
+        clearBit(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() {
+        uint32_t n = firstUnmarkedBit();
+        markBit(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() {
+        uint32_t n = lastMarkedBit();
+        clearBit(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 __builtin_popcount(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;
+    }
+};
+
+ANDROID_BASIC_TYPES_TRAITS(BitSet32)
+
+} // namespace android
+
+#endif // UTILS_BITSET_H
diff --git a/include/utils/BlobCache.h b/include/utils/BlobCache.h
new file mode 100644
index 0000000..7d621e4
--- /dev/null
+++ b/include/utils/BlobCache.h
@@ -0,0 +1,243 @@
+/*
+ ** 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;
+    };
+
+    // 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/include/utils/ByteOrder.h b/include/utils/ByteOrder.h
new file mode 100644
index 0000000..baa3a83
--- /dev/null
+++ b/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>
+#ifdef HAVE_WINSOCK
+#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/include/utils/CallStack.h b/include/utils/CallStack.h
new file mode 100644
index 0000000..61dc832
--- /dev/null
+++ b/include/utils/CallStack.h
@@ -0,0 +1,76 @@
+/*
+ * 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 <stdint.h>
+#include <sys/types.h>
+
+#include <utils/String8.h>
+#include <corkscrew/backtrace.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+class CallStack
+{
+public:
+    enum {
+        MAX_DEPTH = 31
+    };
+
+    CallStack();
+    CallStack(const char* logtag, int32_t ignoreDepth=1,
+            int32_t maxDepth=MAX_DEPTH);
+    CallStack(const CallStack& rhs);
+    ~CallStack();
+
+    CallStack& operator = (const CallStack& rhs);
+    
+    bool operator == (const CallStack& rhs) const;
+    bool operator != (const CallStack& rhs) const;
+    bool operator < (const CallStack& rhs) const;
+    bool operator >= (const CallStack& rhs) const;
+    bool operator > (const CallStack& rhs) const;
+    bool operator <= (const CallStack& rhs) const;
+    
+    const void* operator [] (int index) const;
+    
+    void clear();
+
+    void update(int32_t ignoreDepth=1, int32_t maxDepth=MAX_DEPTH);
+
+    // Dump a stack trace to the log using the supplied logtag
+    void dump(const char* logtag, const char* prefix = 0) const;
+
+    // Return a string (possibly very long) containing the complete stack trace
+    String8 toString(const char* prefix = 0) const;
+    
+    size_t size() const { return mCount; }
+
+private:
+    size_t mCount;
+    backtrace_frame_t mStack[MAX_DEPTH];
+};
+
+}; // namespace android
+
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_CALLSTACK_H
diff --git a/include/utils/Compat.h b/include/utils/Compat.h
new file mode 100644
index 0000000..fb7748e
--- /dev/null
+++ b/include/utils/Compat.h
@@ -0,0 +1,65 @@
+/*
+ * 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>
+
+/* Compatibility definitions for non-Linux (i.e., BSD-based) hosts. */
+#ifndef HAVE_OFF64_T
+#if _FILE_OFFSET_BITS < 64
+#error "_FILE_OFFSET_BITS < 64; large files are not supported on this platform"
+#endif /* _FILE_OFFSET_BITS < 64 */
+
+typedef off_t off64_t;
+
+static inline off64_t lseek64(int fd, off64_t offset, int whence) {
+    return lseek(fd, offset, whence);
+}
+
+#ifdef HAVE_PREAD
+static inline ssize_t pread64(int fd, void* buf, size_t nbytes, off64_t offset) {
+    return pread(fd, buf, nbytes, offset);
+}
+#endif
+
+#endif /* !HAVE_OFF64_T */
+
+#if HAVE_PRINTF_ZD
+#  define ZD "%zd"
+#  define ZD_TYPE ssize_t
+#else
+#  define ZD "%ld"
+#  define ZD_TYPE long
+#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
+
+#endif /* __LIB_UTILS_COMPAT_H */
diff --git a/include/utils/Condition.h b/include/utils/Condition.h
new file mode 100644
index 0000000..e63ba7e
--- /dev/null
+++ b/include/utils/Condition.h
@@ -0,0 +1,147 @@
+/*
+ * 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 <stdint.h>
+#include <sys/types.h>
+#include <time.h>
+
+#if defined(HAVE_PTHREADS)
+# 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();
+    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 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(HAVE_PTHREADS)
+    pthread_cond_t mCond;
+#else
+    void*   mState;
+#endif
+};
+
+// ---------------------------------------------------------------------------
+
+#if defined(HAVE_PTHREADS)
+
+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) {
+#if defined(HAVE_PTHREAD_COND_TIMEDWAIT_RELATIVE)
+    struct timespec ts;
+    ts.tv_sec  = reltime/1000000000;
+    ts.tv_nsec = reltime%1000000000;
+    return -pthread_cond_timedwait_relative_np(&mCond, &mutex.mMutex, &ts);
+#else // HAVE_PTHREAD_COND_TIMEDWAIT_RELATIVE
+    struct timespec ts;
+#if defined(HAVE_POSIX_CLOCKS)
+    clock_gettime(CLOCK_REALTIME, &ts);
+#else // HAVE_POSIX_CLOCKS
+    // we don't support the clocks here.
+    struct timeval t;
+    gettimeofday(&t, NULL);
+    ts.tv_sec = t.tv_sec;
+    ts.tv_nsec= t.tv_usec*1000;
+#endif // HAVE_POSIX_CLOCKS
+    ts.tv_sec += reltime/1000000000;
+    ts.tv_nsec+= reltime%1000000000;
+    if (ts.tv_nsec >= 1000000000) {
+        ts.tv_nsec -= 1000000000;
+        ts.tv_sec  += 1;
+    }
+    return -pthread_cond_timedwait(&mCond, &mutex.mMutex, &ts);
+#endif // HAVE_PTHREAD_COND_TIMEDWAIT_RELATIVE
+}
+inline void Condition::signal() {
+    pthread_cond_signal(&mCond);
+}
+inline void Condition::broadcast() {
+    pthread_cond_broadcast(&mCond);
+}
+
+#endif // HAVE_PTHREADS
+
+// ---------------------------------------------------------------------------
+}; // namespace android
+// ---------------------------------------------------------------------------
+
+#endif // _LIBS_UTILS_CONDITON_H
diff --git a/include/utils/Debug.h b/include/utils/Debug.h
new file mode 100644
index 0000000..08893bd
--- /dev/null
+++ b/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/include/utils/Endian.h b/include/utils/Endian.h
new file mode 100644
index 0000000..19f2504
--- /dev/null
+++ b/include/utils/Endian.h
@@ -0,0 +1,40 @@
+/*
+ * 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(HAVE_ENDIAN_H)
+
+#include <endian.h>
+
+#else /*not HAVE_ENDIAN_H*/
+
+#define __BIG_ENDIAN 0x1000
+#define __LITTLE_ENDIAN 0x0001
+
+#if defined(HAVE_LITTLE_ENDIAN)
+# define __BYTE_ORDER __LITTLE_ENDIAN
+#else
+# define __BYTE_ORDER __BIG_ENDIAN
+#endif
+
+#endif /*not HAVE_ENDIAN_H*/
+
+#endif /*_LIBS_UTILS_ENDIAN_H*/
diff --git a/include/utils/Errors.h b/include/utils/Errors.h
new file mode 100644
index 0000000..0b75b19
--- /dev/null
+++ b/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 HAVE_MS_C_RUNTIME
+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       = 0x80000000,
+
+    NO_MEMORY           = -ENOMEM,
+    INVALID_OPERATION   = -ENOSYS,
+    BAD_VALUE           = -EINVAL,
+    BAD_TYPE            = 0x80000001,
+    NAME_NOT_FOUND      = -ENOENT,
+    PERMISSION_DENIED   = -EPERM,
+    NO_INIT             = -ENODEV,
+    ALREADY_EXISTS      = -EEXIST,
+    DEAD_OBJECT         = -EPIPE,
+    FAILED_TRANSACTION  = 0x80000002,
+    JPARKS_BROKE_IT     = -EPIPE,
+#if !defined(HAVE_MS_C_RUNTIME)
+    BAD_INDEX           = -EOVERFLOW,
+    NOT_ENOUGH_DATA     = -ENODATA,
+    WOULD_BLOCK         = -EWOULDBLOCK, 
+    TIMED_OUT           = -ETIMEDOUT,
+    UNKNOWN_TRANSACTION = -EBADMSG,
+#else    
+    BAD_INDEX           = -E2BIG,
+    NOT_ENOUGH_DATA     = 0x80000003,
+    WOULD_BLOCK         = 0x80000004,
+    TIMED_OUT           = 0x80000005,
+    UNKNOWN_TRANSACTION = 0x80000006,
+#endif    
+    FDS_NOT_ALLOWED     = 0x80000007,
+};
+
+// 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/include/utils/FileMap.h b/include/utils/FileMap.h
new file mode 100644
index 0000000..dfe6d51
--- /dev/null
+++ b/include/utils/FileMap.h
@@ -0,0 +1,136 @@
+/*
+ * 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>
+
+#ifdef HAVE_WIN32_FILEMAP
+#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);
+
+    /*
+     * 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);
+
+    /*
+     * 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; }
+
+    /*
+     * Get a "copy" of the object.
+     */
+    FileMap* acquire(void) { mRefCount++; return this; }
+
+    /*
+     * Call this when mapping is no longer needed.
+     */
+    void release(void) {
+        if (--mRefCount <= 0)
+            delete this;
+    }
+
+    /*
+     * 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:
+    // don't delete objects; call release()
+    ~FileMap(void);
+
+private:
+    // these are not implemented
+    FileMap(const FileMap& src);
+    const FileMap& operator=(const FileMap& src);
+
+    int         mRefCount;      // reference count
+    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"
+#ifdef HAVE_WIN32_FILEMAP
+    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/include/utils/Flattenable.h b/include/utils/Flattenable.h
new file mode 100644
index 0000000..882a8b2
--- /dev/null
+++ b/include/utils/Flattenable.h
@@ -0,0 +1,198 @@
+/*
+ * 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 <sys/types.h>
+#include <utils/Errors.h>
+#include <utils/Debug.h>
+
+namespace android {
+
+
+class FlattenableUtils {
+public:
+    template<int N>
+    static size_t align(size_t size) {
+        COMPILE_TIME_ASSERT_FUNCTION_SCOPE( !(N & (N-1)) );
+        return (size + (N-1)) & ~(N-1);
+    }
+
+    template<int N>
+    static size_t align(void const*& buffer) {
+        COMPILE_TIME_ASSERT_FUNCTION_SCOPE( !(N & (N-1)) );
+        intptr_t b = intptr_t(buffer);
+        buffer = (void*)((intptr_t(buffer) + (N-1)) & ~(N-1));
+        return size_t(intptr_t(buffer) - b);
+    }
+
+    template<int 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*>( intptr_t(buffer) + offset );
+        size -= offset;
+    }
+
+    static void advance(void const*& buffer, size_t& size, size_t offset) {
+        buffer = reinterpret_cast<void const*>( intptr_t(buffer) + offset );
+        size -= offset;
+    }
+
+    // write a POD structure
+    template<typename T>
+    static void write(void*& buffer, size_t& size, const T& value) {
+        *static_cast<T*>(buffer) = value;
+        advance(buffer, size, sizeof(T));
+    }
+
+    // read a POD structure
+    template<typename T>
+    static void read(void const*& buffer, size_t& size, T& value) {
+        value = *static_cast<T const*>(buffer);
+        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/include/utils/Functor.h b/include/utils/Functor.h
new file mode 100644
index 0000000..e24ded4
--- /dev/null
+++ b/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/include/utils/JenkinsHash.h b/include/utils/JenkinsHash.h
new file mode 100644
index 0000000..7da5dbd
--- /dev/null
+++ b/include/utils/JenkinsHash.h
@@ -0,0 +1,48 @@
+/*
+ * 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)) */
+
+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/include/utils/KeyedVector.h b/include/utils/KeyedVector.h
new file mode 100644
index 0000000..c4faae0
--- /dev/null
+++ b/include/utils/KeyedVector.h
@@ -0,0 +1,224 @@
+/*
+ * 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 <cutils/log.h>
+
+#include <utils/SortedVector.h>
+#include <utils/TypeHelpers.h>
+#include <utils/Errors.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;
+};
+
+// KeyedVector<KEY, VALUE> can be trivially moved using memcpy() because its
+// underlying SortedVector can be trivially moved.
+template<typename KEY, typename VALUE> struct trait_trivial_move<KeyedVector<KEY, VALUE> > {
+    enum { value = trait_trivial_move<SortedVector< key_value_pair_t<KEY, VALUE> > >::value };
+};
+
+
+// ---------------------------------------------------------------------------
+
+/**
+ * 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(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 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/include/utils/LinearAllocator.h b/include/utils/LinearAllocator.h
new file mode 100644
index 0000000..4772bc8
--- /dev/null
+++ b/include/utils/LinearAllocator.h
@@ -0,0 +1,97 @@
+/*
+ * Copyright 2012, The Android Open Source Project
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *  * Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *  * Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef ANDROID_LINEARALLOCATOR_H
+#define ANDROID_LINEARALLOCATOR_H
+
+#include <stddef.h>
+
+namespace android {
+
+/**
+ * A memory manager that internally allocates multi-kbyte buffers for placing objects in. It avoids
+ * the overhead of malloc when many objects are allocated. It is most useful when creating many
+ * small objects with a similar lifetime, and doesn't add significant overhead for large
+ * allocations.
+ */
+class LinearAllocator {
+public:
+    LinearAllocator();
+    ~LinearAllocator();
+
+    /**
+     * Reserves and returns a region of memory of at least size 'size', aligning as needed.
+     * Typically this is used in an object's overridden new() method or as a replacement for malloc.
+     *
+     * The lifetime of the returned buffers is tied to that of the LinearAllocator. If calling
+     * delete() on an object stored in a buffer is needed, it should be overridden to use
+     * rewindIfLastAlloc()
+     */
+    void* alloc(size_t size);
+
+    /**
+     * Attempt to deallocate the given buffer, with the LinearAllocator attempting to rewind its
+     * state if possible. No destructors are called.
+     */
+    void rewindIfLastAlloc(void* ptr, size_t allocSize);
+
+    /**
+     * Dump memory usage statistics to the log (allocated and wasted space)
+     */
+    void dumpMemoryStats(const char* prefix = "");
+
+    /**
+     * The number of bytes used for buffers allocated in the LinearAllocator (does not count space
+     * wasted)
+     */
+    size_t usedSize() const { return mTotalAllocated - mWastedSpace; }
+
+private:
+    LinearAllocator(const LinearAllocator& other);
+
+    class Page;
+
+    Page* newPage(size_t pageSize);
+    bool fitsInCurrentPage(size_t size);
+    void ensureNext(size_t size);
+    void* start(Page *p);
+    void* end(Page* p);
+
+    size_t mPageSize;
+    size_t mMaxAllocSize;
+    void* mNext;
+    Page* mCurrentPage;
+    Page* mPages;
+
+    // Memory usage tracking
+    size_t mTotalAllocated;
+    size_t mWastedSpace;
+    size_t mPageCount;
+    size_t mDedicatedPageCount;
+};
+
+}; // namespace android
+
+#endif // ANDROID_LINEARALLOCATOR_H
diff --git a/include/utils/LinearTransform.h b/include/utils/LinearTransform.h
new file mode 100644
index 0000000..04cb355
--- /dev/null
+++ b/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/include/utils/List.h b/include/utils/List.h
new file mode 100644
index 0000000..403cd7f
--- /dev/null
+++ b/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/include/utils/Log.h b/include/utils/Log.h
new file mode 100644
index 0000000..4259c86
--- /dev/null
+++ b/include/utils/Log.h
@@ -0,0 +1,71 @@
+/*
+ * 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 <cutils/log.h>
+#include <sys/types.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/include/utils/Looper.h b/include/utils/Looper.h
new file mode 100644
index 0000000..2e0651a
--- /dev/null
+++ b/include/utils/Looper.h
@@ -0,0 +1,388 @@
+/*
+ * 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 <android/looper.h>
+
+#include <sys/epoll.h>
+
+/*
+ * Declare a concrete type for the NDK's looper forward declaration.
+ */
+struct ALooper {
+};
+
+namespace android {
+
+/**
+ * A message that can be posted to a Looper.
+ */
+struct Message {
+    Message() : what(0) { }
+    Message(int what) : what(what) { }
+
+    /* 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 ALOOPER_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 ALooper_callbackFunc function pointer.
+ */
+class SimpleLooperCallback : public LooperCallback {
+protected:
+    virtual ~SimpleLooperCallback();
+
+public:
+    SimpleLooperCallback(ALooper_callbackFunc callback);
+    virtual int handleEvent(int fd, int events, void* data);
+
+private:
+    ALooper_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 ALooper, public RefBase {
+protected:
+    virtual ~Looper();
+
+public:
+    /**
+     * 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 ALOOPER_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 ALOOPER_POLL_CALLBACK if one or more callbacks were invoked.
+     *
+     * Returns ALOOPER_POLL_TIMEOUT if there was no data before the given
+     * timeout expired.
+     *
+     * Returns ALOOPER_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 ALOOPER_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 ALOOPER_POLL_CALLBACK if providing a non-NULL callback.
+     * "events" are the poll events to wake up on.  Typically this is ALOOPER_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 ALooper_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, ALooper_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);
+
+    /**
+     * Return whether this looper's thread is currently idling -- that is, whether it
+     * stopped waiting for more work to do.  Note that this is intrinsically racy, since
+     * its state can change before you get the result back.
+     */
+    bool isIdling() 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 ALOOPER_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;
+        sp<LooperCallback> callback;
+        void* data;
+    };
+
+    struct Response {
+        int events;
+        Request request;
+    };
+
+    struct MessageEnvelope {
+        MessageEnvelope() : uptime(0) { }
+
+        MessageEnvelope(nsecs_t uptime, const sp<MessageHandler> handler,
+                const Message& message) : uptime(uptime), handler(handler), message(message) {
+        }
+
+        nsecs_t uptime;
+        sp<MessageHandler> handler;
+        Message message;
+    };
+
+    const bool mAllowNonCallbacks; // immutable
+
+    int mWakeReadPipeFd;  // immutable
+    int mWakeWritePipeFd; // 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 mIdling;
+
+    int mEpollFd; // immutable
+
+    // Locked list of file descriptor monitoring requests.
+    KeyedVector<int, Request> mRequests;  // guarded by mLock
+
+    // 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);
+    void awoken();
+    void pushResponse(int events, const Request& request);
+
+    static void initTLSKey();
+    static void threadDestructor(void *st);
+};
+
+} // namespace android
+
+#endif // UTILS_LOOPER_H
diff --git a/include/utils/LruCache.h b/include/utils/LruCache.h
new file mode 100644
index 0000000..053bfaf
--- /dev/null
+++ b/include/utils/LruCache.h
@@ -0,0 +1,237 @@
+/*
+ * 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 <utils/BasicHashtable.h>
+#include <utils/UniquePtr.h>
+
+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);
+
+    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();
+
+    class Iterator {
+    public:
+        Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIndex(-1) {
+        }
+
+        bool next() {
+            mIndex = mCache.mTable->next(mIndex);
+            return mIndex != -1;
+        }
+
+        size_t index() const {
+            return mIndex;
+        }
+
+        const TValue& value() const {
+            return mCache.mTable->entryAt(mIndex).value;
+        }
+
+        const TKey& key() const {
+            return mCache.mTable->entryAt(mIndex).key;
+        }
+    private:
+        const LruCache<TKey, TValue>& mCache;
+        size_t mIndex;
+    };
+
+private:
+    LruCache(const LruCache& that);  // disallow copy constructor
+
+    struct Entry {
+        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 { return key; }
+    };
+
+    void attachToCache(Entry& entry);
+    void detachFromCache(Entry& entry);
+    void rehash(size_t newCapacity);
+
+    UniquePtr<BasicHashtable<TKey, Entry> > mTable;
+    OnEntryRemoved<TKey, TValue>* mListener;
+    Entry* mOldest;
+    Entry* mYoungest;
+    uint32_t mMaxCapacity;
+    TValue mNullValue;
+};
+
+// Implementation is here, because it's fully templated
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
+    mNullValue(NULL), mTable(new BasicHashtable<TKey, Entry>), mYoungest(NULL), mOldest(NULL),
+    mListener(NULL) {
+};
+
+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 mTable->size();
+}
+
+template <typename TKey, typename TValue>
+const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
+    hash_t hash = hash_type(key);
+    ssize_t index = mTable->find(-1, hash, key);
+    if (index == -1) {
+        return mNullValue;
+    }
+    Entry& entry = mTable->editEntryAt(index);
+    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();
+    }
+
+    hash_t hash = hash_type(key);
+    ssize_t index = mTable->find(-1, hash, key);
+    if (index >= 0) {
+        return false;
+    }
+    if (!mTable->hasMoreRoom()) {
+        rehash(mTable->capacity() * 2);
+    }
+
+    // Would it be better to initialize a blank entry and assign key, value?
+    Entry initEntry(key, value);
+    index = mTable->add(hash, initEntry);
+    Entry& entry = mTable->editEntryAt(index);
+    attachToCache(entry);
+    return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::remove(const TKey& key) {
+    hash_t hash = hash_type(key);
+    ssize_t index = mTable->find(-1, hash, key);
+    if (index < 0) {
+        return false;
+    }
+    Entry& entry = mTable->editEntryAt(index);
+    if (mListener) {
+        (*mListener)(entry.key, entry.value);
+    }
+    detachFromCache(entry);
+    mTable->removeAt(index);
+    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>
+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;
+    mTable->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;
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
+    UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
+    Entry* oldest = mOldest;
+
+    mOldest = NULL;
+    mYoungest = NULL;
+    mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
+    for (Entry* p = oldest; p != NULL; p = p->child) {
+        put(p->key, p->value);
+    }
+}
+
+}
+
+#endif // ANDROID_UTILS_LRU_CACHE_H
diff --git a/include/utils/Mutex.h b/include/utils/Mutex.h
new file mode 100644
index 0000000..dd201c8
--- /dev/null
+++ b/include/utils/Mutex.h
@@ -0,0 +1,137 @@
+/*
+ * 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(HAVE_PTHREADS)
+# include <pthread.h>
+#endif
+
+#include <utils/Errors.h>
+
+// ---------------------------------------------------------------------------
+namespace android {
+// ---------------------------------------------------------------------------
+
+class Condition;
+
+/*
+ * 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();
+                Mutex(const char* name);
+                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();
+
+    // Manages the mutex automatically. It'll be locked when Autolock is
+    // constructed and released when Autolock goes out of scope.
+    class Autolock {
+    public:
+        inline Autolock(Mutex& mutex) : mLock(mutex)  { mLock.lock(); }
+        inline 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(HAVE_PTHREADS)
+    pthread_mutex_t mMutex;
+#else
+    void    _init();
+    void*   mState;
+#endif
+};
+
+// ---------------------------------------------------------------------------
+
+#if defined(HAVE_PTHREADS)
+
+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);
+}
+
+#endif // HAVE_PTHREADS
+
+// ---------------------------------------------------------------------------
+
+/*
+ * 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/include/utils/PropertyMap.h b/include/utils/PropertyMap.h
new file mode 100644
index 0000000..a9e674f
--- /dev/null
+++ b/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/include/utils/RWLock.h b/include/utils/RWLock.h
new file mode 100644
index 0000000..90beb5f
--- /dev/null
+++ b/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(HAVE_PTHREADS)
+# include <pthread.h>
+#endif
+
+#include <utils/Errors.h>
+#include <utils/ThreadDefs.h>
+
+// ---------------------------------------------------------------------------
+namespace android {
+// ---------------------------------------------------------------------------
+
+#if defined(HAVE_PTHREADS)
+
+/*
+ * 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();
+                RWLock(const char* name);
+                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 AutoRLock(RWLock& rwlock) : mLock(rwlock)  { mLock.readLock(); }
+        inline ~AutoRLock() { mLock.unlock(); }
+    private:
+        RWLock& mLock;
+    };
+
+    class AutoWLock {
+    public:
+        inline 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 // HAVE_PTHREADS
+
+// ---------------------------------------------------------------------------
+}; // namespace android
+// ---------------------------------------------------------------------------
+
+#endif // _LIBS_UTILS_RWLOCK_H
diff --git a/include/utils/RefBase.h b/include/utils/RefBase.h
new file mode 100644
index 0000000..cbfe13a
--- /dev/null
+++ b/include/utils/RefBase.h
@@ -0,0 +1,546 @@
+/*
+ * 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_REF_BASE_H
+#define ANDROID_REF_BASE_H
+
+#include <cutils/atomic.h>
+
+#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;                                        \
+}
+
+// ---------------------------------------------------------------------------
+
+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;
+};
+
+// ---------------------------------------------------------------------------
+
+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
+    };
+    
+    virtual void            onFirstRef();
+    virtual void            onLastStrongRef(const void* id);
+    virtual bool            onIncStrongAttempted(uint32_t flags, const void* id);
+    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 {
+        android_atomic_inc(&mCount);
+    }
+    inline void decStrong(__attribute__((unused)) const void* id) const {
+        if (android_atomic_dec(&mCount) == 1) {
+            delete static_cast<const T*>(this);
+        }
+    }
+    //! DEBUGGING ONLY: Get current strong ref count.
+    inline int32_t getStrongCount() const {
+        return mCount;
+    }
+
+    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 volatile int32_t mCount;
+};
+
+// ---------------------------------------------------------------------------
+
+template <typename T>
+class wp
+{
+public:
+    typedef typename RefBase::weakref_type weakref_type;
+    
+    inline wp() : m_ptr(0) { }
+
+    wp(T* other);
+    wp(const wp<T>& other);
+    wp(const sp<T>& other);
+    template<typename U> wp(U* other);
+    template<typename U> wp(const sp<U>& other);
+    template<typename U> wp(const wp<U>& other);
+
+    ~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>* d, sp<TYPE> const* s, 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) : s(s), d(d) { }
+        };
+
+        memmove(d, s, n*sizeof(sp<TYPE>));
+        TYPE::renameRefs(n, Renamer(d, s));
+    }
+
+
+    template<typename TYPE> static inline
+    void move_references(wp<TYPE>* d, wp<TYPE> const* s, 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>* d, wp<TYPE> const* s) : s(s), d(d) { }
+        };
+
+        memmove(d, s, n*sizeof(wp<TYPE>));
+        TYPE::renameRefs(n, Renamer(d, s));
+    }
+};
+
+// 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/include/utils/SharedBuffer.h b/include/utils/SharedBuffer.h
new file mode 100644
index 0000000..b670953
--- /dev/null
+++ b/include/utils/SharedBuffer.h
@@ -0,0 +1,137 @@
+/*
+ * 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_SHARED_BUFFER_H
+#define ANDROID_SHARED_BUFFER_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+class SharedBuffer
+{
+public:
+
+    /* flags to use with release() */
+    enum {
+        eKeepStorage = 0x00000001
+    };
+
+    /*! allocate a buffer of size 'size' and acquire() it.
+     *  call release() to free it.
+     */
+    static          SharedBuffer*           alloc(size_t size);
+    
+    /*! free the memory associated with the SharedBuffer.
+     * Fails if there are any users associated with this SharedBuffer.
+     * In other words, the buffer must have been release by all its
+     * users.
+     */
+    static          ssize_t                 dealloc(const SharedBuffer* released);
+
+    //! access the data for read
+    inline          const void*             data() const;
+    
+    //! access the data for read/write
+    inline          void*                   data();
+
+    //! get size of the buffer
+    inline          size_t                  size() const;
+ 
+    //! get back a SharedBuffer object from its data
+    static  inline  SharedBuffer*           bufferFromData(void* data);
+    
+    //! get back a SharedBuffer object from its data
+    static  inline  const SharedBuffer*     bufferFromData(const void* data);
+
+    //! get the size of a SharedBuffer object from its data
+    static  inline  size_t                  sizeFromData(const void* data);
+    
+    //! edit the buffer (get a writtable, or non-const, version of it)
+                    SharedBuffer*           edit() const;
+
+    //! edit the buffer, resizing if needed
+                    SharedBuffer*           editResize(size_t size) const;
+
+    //! like edit() but fails if a copy is required
+                    SharedBuffer*           attemptEdit() const;
+    
+    //! resize and edit the buffer, loose it's content.
+                    SharedBuffer*           reset(size_t size) const;
+
+    //! acquire/release a reference on this buffer
+                    void                    acquire() const;
+                    
+    /*! release a reference on this buffer, with the option of not
+     * freeing the memory associated with it if it was the last reference
+     * returns the previous reference count
+     */     
+                    int32_t                 release(uint32_t flags = 0) const;
+    
+    //! returns wether or not we're the only owner
+    inline          bool                    onlyOwner() const;
+    
+
+private:
+        inline SharedBuffer() { }
+        inline ~SharedBuffer() { }
+        SharedBuffer(const SharedBuffer&);
+        SharedBuffer& operator = (const SharedBuffer&);
+ 
+        // 16 bytes. must be sized to preserve correct alignment.
+        mutable int32_t        mRefs;
+                size_t         mSize;
+                uint32_t       mReserved[2];
+};
+
+// ---------------------------------------------------------------------------
+
+const void* SharedBuffer::data() const {
+    return this + 1;
+}
+
+void* SharedBuffer::data() {
+    return this + 1;
+}
+
+size_t SharedBuffer::size() const {
+    return mSize;
+}
+
+SharedBuffer* SharedBuffer::bufferFromData(void* data) {
+    return data ? static_cast<SharedBuffer *>(data)-1 : 0;
+}
+    
+const SharedBuffer* SharedBuffer::bufferFromData(const void* data) {
+    return data ? static_cast<const SharedBuffer *>(data)-1 : 0;
+}
+
+size_t SharedBuffer::sizeFromData(const void* data) {
+    return data ? bufferFromData(data)->mSize : 0;
+}
+
+bool SharedBuffer::onlyOwner() const {
+    return (mRefs == 1);
+}
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_VECTOR_H
diff --git a/include/utils/Singleton.h b/include/utils/Singleton.h
new file mode 100644
index 0000000..c60680e
--- /dev/null
+++ b/include/utils/Singleton.h
@@ -0,0 +1,77 @@
+/*
+ * 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/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;
+};
+
+/*
+ * 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<> Mutex Singleton< TYPE >::sLock(Mutex::PRIVATE);  \
+    template<> TYPE* Singleton< TYPE >::sInstance(0);           \
+    template class Singleton< TYPE >;
+
+
+// ---------------------------------------------------------------------------
+}; // namespace android
+
+#endif // ANDROID_UTILS_SINGLETON_H
+
diff --git a/include/utils/SortedVector.h b/include/utils/SortedVector.h
new file mode 100644
index 0000000..2d3e82a
--- /dev/null
+++ b/include/utils/SortedVector.h
@@ -0,0 +1,282 @@
+/*
+ * 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 <cutils/log.h>
+
+#include <utils/Vector.h>
+#include <utils/VectorImpl.h>
+#include <utils/TypeHelpers.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); }
+            
+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;
+};
+
+// SortedVector<T> can be trivially moved using memcpy() because moving does not
+// require any change to the underlying SharedBuffer contents or reference count.
+template<typename T> struct trait_trivial_move<SortedVector<T> > { enum { value = true }; };
+
+// ---------------------------------------------------------------------------
+// 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/include/utils/StopWatch.h b/include/utils/StopWatch.h
new file mode 100644
index 0000000..693dd3c
--- /dev/null
+++ b/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/include/utils/String16.h b/include/utils/String16.h
new file mode 100644
index 0000000..d131bfc
--- /dev/null
+++ b/include/utils/String16.h
@@ -0,0 +1,250 @@
+/*
+ * 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 <utils/Errors.h>
+#include <utils/SharedBuffer.h>
+#include <utils/Unicode.h>
+#include <utils/TypeHelpers.h>
+
+// ---------------------------------------------------------------------------
+
+extern "C" {
+
+}
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+// ---------------------------------------------------------------------------
+
+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;
+    inline  size_t              size() const;
+    
+    inline  const SharedBuffer* sharedBuffer() 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;
+            
+            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 size_t String16::size() const
+{
+    return SharedBuffer::sizeFromData(mString)/sizeof(char16_t)-1;
+}
+
+inline const SharedBuffer* String16::sharedBuffer() const
+{
+    return SharedBuffer::bufferFromData(mString);
+}
+
+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/include/utils/String8.h b/include/utils/String8.h
new file mode 100644
index 0000000..ef59470
--- /dev/null
+++ b/include/utils/String8.h
@@ -0,0 +1,395 @@
+/*
+ * 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 <utils/Errors.h>
+#include <utils/SharedBuffer.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;
+    inline  size_t              size() const;
+    inline  size_t              length() const;
+    inline  size_t              bytes() const;
+    inline  bool                isEmpty() const;
+    
+    inline  const SharedBuffer* sharedBuffer() 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;
+
+            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 size_t String8::length() const
+{
+    return SharedBuffer::sizeFromData(mString)-1;
+}
+
+inline size_t String8::size() const
+{
+    return length();
+}
+
+inline bool String8::isEmpty() const
+{
+    return length() == 0;
+}
+
+inline size_t String8::bytes() const
+{
+    return SharedBuffer::sizeFromData(mString)-1;
+}
+
+inline const SharedBuffer* String8::sharedBuffer() const
+{
+    return SharedBuffer::bufferFromData(mString);
+}
+
+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/include/utils/StrongPointer.h b/include/utils/StrongPointer.h
new file mode 100644
index 0000000..aba9577
--- /dev/null
+++ b/include/utils/StrongPointer.h
@@ -0,0 +1,211 @@
+/*
+ * 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);
+    sp(const sp<T>& other);
+    template<typename U> sp(U* other);
+    template<typename U> sp(const sp<U>& other);
+
+    ~sp();
+
+    // Assignment
+
+    sp& operator = (T* other);
+    sp& operator = (const sp<T>& other);
+
+    template<typename U> sp& operator = (const 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> template<typename U>
+sp<T>::sp(U* other)
+        : m_ptr(other) {
+    if (other)
+        ((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>
+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 =(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 =(U* other) {
+    if (other)
+        ((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/include/utils/SystemClock.h b/include/utils/SystemClock.h
new file mode 100644
index 0000000..01db340
--- /dev/null
+++ b/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/include/utils/Thread.h b/include/utils/Thread.h
new file mode 100644
index 0000000..df30611
--- /dev/null
+++ b/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(HAVE_PTHREADS)
+# 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.
+                        Thread(bool canCallJava = true);
+    virtual             ~Thread();
+
+    // Start the thread in threadLoop() which needs to be implemented.
+    virtual status_t    run(    const char* name = 0,
+                                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;
+
+#ifdef HAVE_ANDROID_OS
+    // Return the thread's kernel ID, same as the thread itself calling gettid() or
+    // androidGetTid(), 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;
+#ifdef HAVE_ANDROID_OS
+    // 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/include/utils/ThreadDefs.h b/include/utils/ThreadDefs.h
new file mode 100644
index 0000000..9711c13
--- /dev/null
+++ b/include/utils/ThreadDefs.h
@@ -0,0 +1,70 @@
+/*
+ * 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
+
+typedef void* android_thread_id_t;
+
+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/include/utils/Timers.h b/include/utils/Timers.h
new file mode 100644
index 0000000..d015421
--- /dev/null
+++ b/include/utils/Timers.h
@@ -0,0 +1,106 @@
+/*
+ * 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>
+
+// ------------------------------------------------------------------
+// C API
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef int64_t nsecs_t;       // nano-seconds
+
+static inline nsecs_t seconds_to_nanoseconds(nsecs_t secs)
+{
+    return secs*1000000000;
+}
+
+static inline nsecs_t milliseconds_to_nanoseconds(nsecs_t secs)
+{
+    return secs*1000000;
+}
+
+static inline nsecs_t microseconds_to_nanoseconds(nsecs_t secs)
+{
+    return secs*1000;
+}
+
+static inline nsecs_t nanoseconds_to_seconds(nsecs_t secs)
+{
+    return secs/1000000000;
+}
+
+static inline nsecs_t nanoseconds_to_milliseconds(nsecs_t secs)
+{
+    return secs/1000000;
+}
+
+static inline nsecs_t nanoseconds_to_microseconds(nsecs_t secs)
+{
+    return secs/1000;
+}
+
+static inline nsecs_t s2ns(nsecs_t v)  {return seconds_to_nanoseconds(v);}
+static inline nsecs_t ms2ns(nsecs_t v) {return milliseconds_to_nanoseconds(v);}
+static inline nsecs_t us2ns(nsecs_t v) {return microseconds_to_nanoseconds(v);}
+static inline nsecs_t ns2s(nsecs_t v)  {return nanoseconds_to_seconds(v);}
+static inline nsecs_t ns2ms(nsecs_t v) {return nanoseconds_to_milliseconds(v);}
+static inline nsecs_t ns2us(nsecs_t v) {return nanoseconds_to_microseconds(v);}
+
+static inline nsecs_t seconds(nsecs_t v)      { return s2ns(v); }
+static inline nsecs_t milliseconds(nsecs_t v) { return ms2ns(v); }
+static 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/include/utils/Tokenizer.h b/include/utils/Tokenizer.h
new file mode 100644
index 0000000..bb25f37
--- /dev/null
+++ b/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/include/utils/Trace.h b/include/utils/Trace.h
new file mode 100644
index 0000000..6ee343d
--- /dev/null
+++ b/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
+
+#ifdef HAVE_ANDROID_OS
+
+#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 the beginning and end of the current scope.  To trace
+// the correct start and end times this macro should be declared first in the
+// scope body.
+#define ATRACE_NAME(name) android::ScopedTrace ___tracer(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 // HAVE_ANDROID_OS
+
+#define ATRACE_NAME(...)
+#define ATRACE_CALL()
+
+#endif // HAVE_ANDROID_OS
+
+#endif // ANDROID_TRACE_H
diff --git a/include/utils/TypeHelpers.h b/include/utils/TypeHelpers.h
new file mode 100644
index 0000000..13c9081
--- /dev/null
+++ b/include/utils/TypeHelpers.h
@@ -0,0 +1,302 @@
+/*
+ * 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 <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--) {
+            new(p++) TYPE;
+        }
+    }
+}
+
+template<typename TYPE> inline
+void destroy_type(TYPE* p, size_t n) {
+    if (!traits<TYPE>::has_trivial_dtor) {
+        while (n--) {
+            p->~TYPE();
+            p++;
+        }
+    }
+}
+
+template<typename TYPE> inline
+void copy_type(TYPE* d, const TYPE* s, size_t n) {
+    if (!traits<TYPE>::has_trivial_copy) {
+        while (n--) {
+            new(d) TYPE(*s);
+            d++, s++;
+        }
+    } else {
+        memcpy(d,s,n*sizeof(TYPE));
+    }
+}
+
+template<typename TYPE> inline
+void splat_type(TYPE* where, const TYPE* what, size_t n) {
+    if (!traits<TYPE>::has_trivial_copy) {
+        while (n--) {
+            new(where) TYPE(*what);
+            where++;
+        }
+    } else {
+        while (n--) {
+            *where++ = *what;
+        }
+    }
+}
+
+template<typename TYPE> inline
+void move_forward_type(TYPE* d, const TYPE* s, size_t n = 1) {
+    if ((traits<TYPE>::has_trivial_dtor && traits<TYPE>::has_trivial_copy) 
+            || traits<TYPE>::has_trivial_move) 
+    {
+        memmove(d,s,n*sizeof(TYPE));
+    } else {
+        d += n;
+        s += n;
+        while (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> inline
+void move_backward_type(TYPE* d, const TYPE* s, size_t n = 1) {
+    if ((traits<TYPE>::has_trivial_dtor && traits<TYPE>::has_trivial_copy) 
+            || traits<TYPE>::has_trivial_move) 
+    {
+        memmove(d,s,n*sizeof(TYPE));
+    } else {
+        while (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(const KEY& k, const VALUE& v) : key(k), value(v)  { }
+    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.
+ * Assumes pointers are 32bit. */
+#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) { \
+                return hash_type(*reinterpret_cast<const R*>(&value)); }
+
+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/include/utils/Unicode.h b/include/utils/Unicode.h
new file mode 100644
index 0000000..c8c87c3
--- /dev/null
+++ b/include/utils/Unicode.h
@@ -0,0 +1,175 @@
+/*
+ * 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" {
+
+typedef uint32_t char32_t;
+typedef uint16_t char16_t;
+
+// 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);
+
+// Version of comparison that supports embedded nulls.
+// 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 null-terminated when dst_len is fully used (like strncpy).
+ *
+ * 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 null-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 null-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 null-terminated, like strncpy)
+ */
+void utf32_to_utf8(const char32_t* src, size_t src_len, char* dst);
+
+/**
+ * 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
+ * NULL terminator.
+ */
+void utf16_to_utf8(const char16_t* src, size_t src_len, char* dst);
+
+/**
+ * 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 null-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 NULL 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".
+ */
+ssize_t utf8_to_utf16_length(const uint8_t* src, size_t srcLen);
+
+/**
+ * Convert UTF-8 to UTF-16 including surrogate pairs.
+ * Returns a pointer to the end of the string (where a null terminator might go
+ * if you wanted to add one).
+ */
+char16_t* utf8_to_utf16_no_null_terminator(const uint8_t* src, size_t srcLen, char16_t* dst);
+
+/**
+ * Convert UTF-8 to UTF-16 including surrogate pairs. The destination buffer
+ * must be large enough to hold the result as measured by utf8_to_utf16_length
+ * plus an added NULL terminator.
+ */
+void utf8_to_utf16(const uint8_t* src, size_t srcLen, char16_t* dst);
+
+/**
+ * Like utf8_to_utf16_no_null_terminator, but you can supply a maximum length of the
+ * decoded string.  The decoded string will fill up to that length; if it is longer
+ * the returned pointer will be to the character after dstLen.
+ */
+char16_t* utf8_to_utf16_n(const uint8_t* src, size_t srcLen, char16_t* dst, size_t dstLen);
+
+}
+
+#endif
diff --git a/include/utils/UniquePtr.h b/include/utils/UniquePtr.h
new file mode 100644
index 0000000..bc62fe6
--- /dev/null
+++ b/include/utils/UniquePtr.h
@@ -0,0 +1,239 @@
+/*
+ * 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.
+ */
+
+/* === NOTE === NOTE === NOTE === NOTE === NOTE === NOTE === NOTE === NOTE ===
+ *
+ * THIS IS A COPY OF libcore/include/UniquePtr.h AND AS SUCH THAT IS THE
+ * CANONICAL SOURCE OF THIS FILE. PLEASE KEEP THEM IN SYNC.
+ *
+ * === NOTE === NOTE === NOTE === NOTE === NOTE === NOTE === NOTE === NOTE ===
+ */
+
+#ifndef UNIQUE_PTR_H_included
+#define UNIQUE_PTR_H_included
+
+#include <cstdlib> // For NULL.
+
+// Default deleter for pointer types.
+template <typename T>
+struct DefaultDelete {
+    enum { type_must_be_complete = sizeof(T) };
+    DefaultDelete() {}
+    void operator()(T* p) const {
+        delete p;
+    }
+};
+
+// Default deleter for array types.
+template <typename T>
+struct DefaultDelete<T[]> {
+    enum { type_must_be_complete = sizeof(T) };
+    void operator()(T* p) const {
+        delete[] p;
+    }
+};
+
+// A smart pointer that deletes the given pointer on destruction.
+// Equivalent to C++0x's std::unique_ptr (a combination of boost::scoped_ptr
+// and boost::scoped_array).
+// Named to be in keeping with Android style but also to avoid
+// collision with any other implementation, until we can switch over
+// to unique_ptr.
+// Use thus:
+//   UniquePtr<C> c(new C);
+template <typename T, typename D = DefaultDelete<T> >
+class UniquePtr {
+public:
+    // Construct a new UniquePtr, taking ownership of the given raw pointer.
+    explicit UniquePtr(T* ptr = NULL) : mPtr(ptr) {
+    }
+
+    ~UniquePtr() {
+        reset();
+    }
+
+    // Accessors.
+    T& operator*() const { return *mPtr; }
+    T* operator->() const { return mPtr; }
+    T* get() const { return mPtr; }
+
+    // Returns the raw pointer and hands over ownership to the caller.
+    // The pointer will not be deleted by UniquePtr.
+    T* release() __attribute__((warn_unused_result)) {
+        T* result = mPtr;
+        mPtr = NULL;
+        return result;
+    }
+
+    // Takes ownership of the given raw pointer.
+    // If this smart pointer previously owned a different raw pointer, that
+    // raw pointer will be freed.
+    void reset(T* ptr = NULL) {
+        if (ptr != mPtr) {
+            D()(mPtr);
+            mPtr = ptr;
+        }
+    }
+
+private:
+    // The raw pointer.
+    T* mPtr;
+
+    // Comparing unique pointers is probably a mistake, since they're unique.
+    template <typename T2> bool operator==(const UniquePtr<T2>& p) const;
+    template <typename T2> bool operator!=(const UniquePtr<T2>& p) const;
+
+    // Disallow copy and assignment.
+    UniquePtr(const UniquePtr&);
+    void operator=(const UniquePtr&);
+};
+
+// Partial specialization for array types. Like std::unique_ptr, this removes
+// operator* and operator-> but adds operator[].
+template <typename T, typename D>
+class UniquePtr<T[], D> {
+public:
+    explicit UniquePtr(T* ptr = NULL) : mPtr(ptr) {
+    }
+
+    ~UniquePtr() {
+        reset();
+    }
+
+    T& operator[](size_t i) const {
+        return mPtr[i];
+    }
+    T* get() const { return mPtr; }
+
+    T* release() __attribute__((warn_unused_result)) {
+        T* result = mPtr;
+        mPtr = NULL;
+        return result;
+    }
+
+    void reset(T* ptr = NULL) {
+        if (ptr != mPtr) {
+            D()(mPtr);
+            mPtr = ptr;
+        }
+    }
+
+private:
+    T* mPtr;
+
+    // Disallow copy and assignment.
+    UniquePtr(const UniquePtr&);
+    void operator=(const UniquePtr&);
+};
+
+#if UNIQUE_PTR_TESTS
+
+// Run these tests with:
+// g++ -g -DUNIQUE_PTR_TESTS -x c++ UniquePtr.h && ./a.out
+
+#include <stdio.h>
+
+static void assert(bool b) {
+    if (!b) {
+        fprintf(stderr, "FAIL\n");
+        abort();
+    }
+    fprintf(stderr, "OK\n");
+}
+static int cCount = 0;
+struct C {
+    C() { ++cCount; }
+    ~C() { --cCount; }
+};
+static bool freed = false;
+struct Freer {
+    void operator()(int* p) {
+        assert(*p == 123);
+        free(p);
+        freed = true;
+    }
+};
+
+int main(int argc, char* argv[]) {
+    //
+    // UniquePtr<T> tests...
+    //
+
+    // Can we free a single object?
+    {
+        UniquePtr<C> c(new C);
+        assert(cCount == 1);
+    }
+    assert(cCount == 0);
+    // Does release work?
+    C* rawC;
+    {
+        UniquePtr<C> c(new C);
+        assert(cCount == 1);
+        rawC = c.release();
+    }
+    assert(cCount == 1);
+    delete rawC;
+    // Does reset work?
+    {
+        UniquePtr<C> c(new C);
+        assert(cCount == 1);
+        c.reset(new C);
+        assert(cCount == 1);
+    }
+    assert(cCount == 0);
+
+    //
+    // UniquePtr<T[]> tests...
+    //
+
+    // Can we free an array?
+    {
+        UniquePtr<C[]> cs(new C[4]);
+        assert(cCount == 4);
+    }
+    assert(cCount == 0);
+    // Does release work?
+    {
+        UniquePtr<C[]> c(new C[4]);
+        assert(cCount == 4);
+        rawC = c.release();
+    }
+    assert(cCount == 4);
+    delete[] rawC;
+    // Does reset work?
+    {
+        UniquePtr<C[]> c(new C[4]);
+        assert(cCount == 4);
+        c.reset(new C[2]);
+        assert(cCount == 2);
+    }
+    assert(cCount == 0);
+
+    //
+    // Custom deleter tests...
+    //
+    assert(!freed);
+    {
+        UniquePtr<int, Freer> i(reinterpret_cast<int*>(malloc(sizeof(int))));
+        *i = 123;
+    }
+    assert(freed);
+    return 0;
+}
+#endif
+
+#endif  // UNIQUE_PTR_H_included
diff --git a/include/utils/Vector.h b/include/utils/Vector.h
new file mode 100644
index 0000000..ed7b725
--- /dev/null
+++ b/include/utils/Vector.h
@@ -0,0 +1,423 @@
+/*
+ * 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 <new>
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <cutils/log.h>
+
+#include <utils/VectorImpl.h>
+#include <utils/TypeHelpers.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(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;
+};
+
+// Vector<T> can be trivially moved using memcpy() because moving does not
+// require any change to the underlying SharedBuffer contents or reference count.
+template<typename T> struct trait_trivial_move<Vector<T> > { enum { value = true }; };
+
+// ---------------------------------------------------------------------------
+// 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((VectorImpl::compar_t)cmp);
+}
+
+template<class TYPE> inline
+status_t Vector<TYPE>::sort(Vector<TYPE>::compar_r_t cmp, void* state) {
+    return VectorImpl::sort((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/include/utils/VectorImpl.h b/include/utils/VectorImpl.h
new file mode 100644
index 0000000..21ad71c
--- /dev/null
+++ b/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);
+                            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/include/utils/ashmem.h b/include/utils/ashmem.h
new file mode 100644
index 0000000..0854775
--- /dev/null
+++ b/include/utils/ashmem.h
@@ -0,0 +1,41 @@
+/* utils/ashmem.h
+ **
+ ** Copyright 2008 The Android Open Source Project
+ **
+ ** This file is dual licensed.  It may be redistributed and/or modified
+ ** under the terms of the Apache 2.0 License OR version 2 of the GNU
+ ** General Public License.
+ */
+
+#ifndef _UTILS_ASHMEM_H
+#define _UTILS_ASHMEM_H
+
+#include <linux/limits.h>
+#include <linux/ioctl.h>
+
+#define ASHMEM_NAME_LEN		256
+
+#define ASHMEM_NAME_DEF		"dev/ashmem"
+
+/* Return values from ASHMEM_PIN: Was the mapping purged while unpinned? */
+#define ASHMEM_NOT_REAPED	0
+#define ASHMEM_WAS_REAPED	1
+
+/* Return values from ASHMEM_UNPIN: Is the mapping now pinned or unpinned? */
+#define ASHMEM_NOW_UNPINNED	0
+#define ASHMEM_NOW_PINNED	1
+
+#define __ASHMEMIOC		0x77
+
+#define ASHMEM_SET_NAME		_IOW(__ASHMEMIOC, 1, char[ASHMEM_NAME_LEN])
+#define ASHMEM_GET_NAME		_IOR(__ASHMEMIOC, 2, char[ASHMEM_NAME_LEN])
+#define ASHMEM_SET_SIZE		_IOW(__ASHMEMIOC, 3, size_t)
+#define ASHMEM_GET_SIZE		_IO(__ASHMEMIOC, 4)
+#define ASHMEM_SET_PROT_MASK	_IOW(__ASHMEMIOC, 5, unsigned long)
+#define ASHMEM_GET_PROT_MASK	_IO(__ASHMEMIOC, 6)
+#define ASHMEM_PIN		_IO(__ASHMEMIOC, 7)
+#define ASHMEM_UNPIN		_IO(__ASHMEMIOC, 8)
+#define ASHMEM_ISPINNED		_IO(__ASHMEMIOC, 9)
+#define ASHMEM_PURGE_ALL_CACHES	_IO(__ASHMEMIOC, 10)
+
+#endif	/* _UTILS_ASHMEM_H */
diff --git a/include/utils/misc.h b/include/utils/misc.h
new file mode 100644
index 0000000..6cccec3
--- /dev/null
+++ b/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/include/utils/threads.h b/include/utils/threads.h
new file mode 100644
index 0000000..9de3382
--- /dev/null
+++ b/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