diff --git a/include/binder/CursorWindow.h b/include/binder/CursorWindow.h
index f0284de..8a2979a 100644
--- a/include/binder/CursorWindow.h
+++ b/include/binder/CursorWindow.h
@@ -31,8 +31,8 @@
 
 #else
 
-#define IF_LOG_WINDOW() IF_LOG(LOG_DEBUG, "CursorWindow")
-#define LOG_WINDOW(...) LOG(LOG_DEBUG, "CursorWindow", __VA_ARGS__)
+#define IF_LOG_WINDOW() IF_ALOG(LOG_DEBUG, "CursorWindow")
+#define LOG_WINDOW(...) ALOG(LOG_DEBUG, "CursorWindow", __VA_ARGS__)
 
 #endif
 
diff --git a/include/gui/SensorChannel.h b/include/gui/BitTube.h
similarity index 89%
rename from include/gui/SensorChannel.h
rename to include/gui/BitTube.h
index bb54618..76389a0 100644
--- a/include/gui/SensorChannel.h
+++ b/include/gui/BitTube.h
@@ -28,14 +28,15 @@
 // ----------------------------------------------------------------------------
 class Parcel;
 
-class SensorChannel : public RefBase
+class BitTube : public RefBase
 {
 public:
 
-            SensorChannel();
-            SensorChannel(const Parcel& data);
-    virtual ~SensorChannel();
+            BitTube();
+            BitTube(const Parcel& data);
+    virtual ~BitTube();
 
+    status_t initCheck() const;
     int getFd() const;
     ssize_t write(void const* vaddr, size_t size);
     ssize_t read(void* vaddr, size_t size);
diff --git a/include/gui/ISensorEventConnection.h b/include/gui/ISensorEventConnection.h
index ed4e4cc..749065e 100644
--- a/include/gui/ISensorEventConnection.h
+++ b/include/gui/ISensorEventConnection.h
@@ -28,14 +28,14 @@
 namespace android {
 // ----------------------------------------------------------------------------
 
-class SensorChannel;
+class BitTube;
 
 class ISensorEventConnection : public IInterface
 {
 public:
     DECLARE_META_INTERFACE(SensorEventConnection);
 
-    virtual sp<SensorChannel> getSensorChannel() const = 0;
+    virtual sp<BitTube> getSensorChannel() const = 0;
     virtual status_t enableDisable(int handle, bool enabled) = 0;
     virtual status_t setEventRate(int handle, nsecs_t ns) = 0;
 };
diff --git a/include/gui/SensorEventQueue.h b/include/gui/SensorEventQueue.h
index 97dd391..ef7c6e3 100644
--- a/include/gui/SensorEventQueue.h
+++ b/include/gui/SensorEventQueue.h
@@ -24,7 +24,7 @@
 #include <utils/RefBase.h>
 #include <utils/Timers.h>
 
-#include <gui/SensorChannel.h>
+#include <gui/BitTube.h>
 
 // ----------------------------------------------------------------------------
 
@@ -71,7 +71,7 @@
 private:
     sp<Looper> getLooper() const;
     sp<ISensorEventConnection> mSensorEventConnection;
-    sp<SensorChannel> mSensorChannel;
+    sp<BitTube> mSensorChannel;
     mutable Mutex mLock;
     mutable sp<Looper> mLooper;
 };
diff --git a/include/utils/BasicHashtable.h b/include/utils/BasicHashtable.h
new file mode 100644
index 0000000..fdf9738
--- /dev/null
+++ b/include/utils/BasicHashtable.h
@@ -0,0 +1,393 @@
+/*
+ * 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);
+
+    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);
+    }
+
+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/CallStack.h b/include/utils/CallStack.h
index 8817120..079e20c 100644
--- a/include/utils/CallStack.h
+++ b/include/utils/CallStack.h
@@ -21,6 +21,7 @@
 #include <sys/types.h>
 
 #include <utils/String8.h>
+#include <corkscrew/backtrace.h>
 
 // ---------------------------------------------------------------------------
 
@@ -61,11 +62,8 @@
     size_t size() const { return mCount; }
 
 private:
-    // Internal helper function
-    String8 toStringSingleLevel(const char* prefix, int32_t level) const;
-
-    size_t      mCount;
-    const void* mStack[MAX_DEPTH];
+    size_t mCount;
+    backtrace_frame_t mStack[MAX_DEPTH];
 };
 
 }; // namespace android
diff --git a/include/utils/GenerationCache.h b/include/utils/GenerationCache.h
index bb9ddd6..83cda86 100644
--- a/include/utils/GenerationCache.h
+++ b/include/utils/GenerationCache.h
@@ -34,17 +34,17 @@
 
 template<typename EntryKey, typename EntryValue>
 struct Entry: public LightRefBase<Entry<EntryKey, EntryValue> > {
-    Entry() { }
-    Entry(const Entry<EntryKey, EntryValue>& e):
-            key(e.key), value(e.value), parent(e.parent), child(e.child) { }
-    Entry(sp<Entry<EntryKey, EntryValue> > e):
-            key(e->key), value(e->value), parent(e->parent), child(e->child) { }
+    Entry(const Entry<EntryKey, EntryValue>& e) :
+            key(e.key), value(e.value),
+            parent(e.parent), child(e.child) { }
+    Entry(const EntryKey& key, const EntryValue& value) :
+            key(key), value(value) { }
 
     EntryKey key;
     EntryValue value;
 
-    sp<Entry<EntryKey, EntryValue> > parent;
-    sp<Entry<EntryKey, EntryValue> > child;
+    sp<Entry<EntryKey, EntryValue> > parent; // next older entry
+    sp<Entry<EntryKey, EntryValue> > child;  // next younger entry
 }; // struct Entry
 
 /**
@@ -62,23 +62,20 @@
 
     void setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener);
 
+    size_t size() const;
+
     void clear();
 
-    bool contains(K key) const;
-    V get(K key);
-    K getKeyAt(uint32_t index) const;
-    bool put(K key, V value);
-    V remove(K key);
-    V removeOldest();
-    V getValueAt(uint32_t index) const;
+    bool contains(const K& key) const;
+    const K& getKeyAt(size_t index) const;
+    const V& getValueAt(size_t index) const;
 
-    uint32_t size() const;
+    const V& get(const K& key);
+    bool put(const K& key, const V& value);
 
-    void addToCache(sp<Entry<K, V> > entry, K key, V value);
-    void attachToCache(sp<Entry<K, V> > entry);
-    void detachFromCache(sp<Entry<K, V> > entry);
-
-    V removeAt(ssize_t index);
+    void removeAt(ssize_t index);
+    bool remove(const K& key);
+    bool removeOldest();
 
 private:
     KeyedVector<K, sp<Entry<K, V> > > mCache;
@@ -88,6 +85,9 @@
 
     sp<Entry<K, V> > mOldest;
     sp<Entry<K, V> > mYoungest;
+
+    void attachToCache(const sp<Entry<K, V> >& entry);
+    void detachFromCache(const sp<Entry<K, V> >& entry);
 }; // class GenerationCache
 
 template<typename K, typename V>
@@ -130,45 +130,44 @@
 }
 
 template<typename K, typename V>
-bool GenerationCache<K, V>::contains(K key) const {
+bool GenerationCache<K, V>::contains(const K& key) const {
     return mCache.indexOfKey(key) >= 0;
 }
 
 template<typename K, typename V>
-K GenerationCache<K, V>::getKeyAt(uint32_t index) const {
+const K& GenerationCache<K, V>::getKeyAt(size_t index) const {
     return mCache.keyAt(index);
 }
 
 template<typename K, typename V>
-V GenerationCache<K, V>::getValueAt(uint32_t index) const {
+const V& GenerationCache<K, V>::getValueAt(size_t index) const {
     return mCache.valueAt(index)->value;
 }
 
 template<typename K, typename V>
-V GenerationCache<K, V>::get(K key) {
+const V& GenerationCache<K, V>::get(const K& key) {
     ssize_t index = mCache.indexOfKey(key);
     if (index >= 0) {
-        sp<Entry<K, V> > entry = mCache.valueAt(index);
-        if (entry.get()) {
-            detachFromCache(entry);
-            attachToCache(entry);
-            return entry->value;
-        }
+        const sp<Entry<K, V> >& entry = mCache.valueAt(index);
+        detachFromCache(entry);
+        attachToCache(entry);
+        return entry->value;
     }
 
     return NULL;
 }
 
 template<typename K, typename V>
-bool GenerationCache<K, V>::put(K key, V value) {
+bool GenerationCache<K, V>::put(const K& key, const V& value) {
     if (mMaxCapacity != kUnlimitedCapacity && mCache.size() >= mMaxCapacity) {
         removeOldest();
     }
 
     ssize_t index = mCache.indexOfKey(key);
     if (index < 0) {
-        sp<Entry<K, V> > entry = new Entry<K, V>;
-        addToCache(entry, key, value);
+        sp<Entry<K, V> > entry = new Entry<K, V>(key, value);
+        mCache.add(key, entry);
+        attachToCache(entry);
         return true;
     }
 
@@ -176,49 +175,44 @@
 }
 
 template<typename K, typename V>
-void GenerationCache<K, V>::addToCache(sp<Entry<K, V> > entry, K key, V value) {
-    entry->key = key;
-    entry->value = value;
-    mCache.add(key, entry);
-    attachToCache(entry);
-}
-
-template<typename K, typename V>
-V GenerationCache<K, V>::remove(K key) {
+bool GenerationCache<K, V>::remove(const K& key) {
     ssize_t index = mCache.indexOfKey(key);
     if (index >= 0) {
-        return removeAt(index);
+        removeAt(index);
+        return true;
     }
 
-    return NULL;
+    return false;
 }
 
 template<typename K, typename V>
-V GenerationCache<K, V>::removeAt(ssize_t index) {
+void GenerationCache<K, V>::removeAt(ssize_t index) {
     sp<Entry<K, V> > entry = mCache.valueAt(index);
     if (mListener) {
         (*mListener)(entry->key, entry->value);
     }
     mCache.removeItemsAt(index, 1);
     detachFromCache(entry);
-
-    return entry->value;
 }
 
 template<typename K, typename V>
-V GenerationCache<K, V>::removeOldest() {
+bool GenerationCache<K, V>::removeOldest() {
     if (mOldest.get()) {
         ssize_t index = mCache.indexOfKey(mOldest->key);
         if (index >= 0) {
-            return removeAt(index);
+            removeAt(index);
+            return true;
         }
+        LOGE("GenerationCache: removeOldest failed to find the item in the cache "
+                "with the given key, but we know it must be in there.  "
+                "Is the key comparator kaput?");
     }
 
-    return NULL;
+    return false;
 }
 
 template<typename K, typename V>
-void GenerationCache<K, V>::attachToCache(sp<Entry<K, V> > entry) {
+void GenerationCache<K, V>::attachToCache(const sp<Entry<K, V> >& entry) {
     if (!mYoungest.get()) {
         mYoungest = mOldest = entry;
     } else {
@@ -229,20 +223,16 @@
 }
 
 template<typename K, typename V>
-void GenerationCache<K, V>::detachFromCache(sp<Entry<K, V> > entry) {
+void GenerationCache<K, V>::detachFromCache(const sp<Entry<K, V> >& entry) {
     if (entry->parent.get()) {
         entry->parent->child = entry->child;
+    } else {
+        mOldest = entry->child;
     }
 
     if (entry->child.get()) {
         entry->child->parent = entry->parent;
-    }
-
-    if (mOldest == entry) {
-        mOldest = entry->child;
-    }
-
-    if (mYoungest == entry) {
+    } else {
         mYoungest = entry->parent;
     }
 
diff --git a/include/utils/TypeHelpers.h b/include/utils/TypeHelpers.h
index a1663f3..7538817 100644
--- a/include/utils/TypeHelpers.h
+++ b/include/utils/TypeHelpers.h
@@ -213,6 +213,9 @@
 
 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() { }
@@ -222,6 +225,12 @@
     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<>
@@ -243,6 +252,41 @@
 
 // ---------------------------------------------------------------------------
 
+/*
+ * 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(char)
+ANDROID_INT32_HASH(unsigned char)
+ANDROID_INT32_HASH(short)
+ANDROID_INT32_HASH(unsigned short)
+ANDROID_INT32_HASH(int)
+ANDROID_INT32_HASH(unsigned int)
+ANDROID_INT64_HASH(long)
+ANDROID_INT64_HASH(unsigned long)
+ANDROID_REINTERPRET_HASH(float, uint32_t)
+ANDROID_REINTERPRET_HASH(double, uint64_t)
+
+template <typename T> inline hash_t hash_type(const T*& value) {
+    return hash_type(uintptr_t(value));
+}
+
 }; // namespace android
 
 // ---------------------------------------------------------------------------
diff --git a/libs/binder/BpBinder.cpp b/libs/binder/BpBinder.cpp
index 5de87ec..e8fb1d9 100644
--- a/libs/binder/BpBinder.cpp
+++ b/libs/binder/BpBinder.cpp
@@ -24,8 +24,8 @@
 
 #include <stdio.h>
 
-//#undef LOGV
-//#define LOGV(...) fprintf(stderr, __VA_ARGS__)
+//#undef ALOGV
+//#define ALOGV(...) fprintf(stderr, __VA_ARGS__)
 
 namespace android {
 
@@ -73,7 +73,7 @@
 void BpBinder::ObjectManager::kill()
 {
     const size_t N = mObjects.size();
-    LOGV("Killing %d objects in manager %p", N, this);
+    ALOGV("Killing %d objects in manager %p", N, this);
     for (size_t i=0; i<N; i++) {
         const entry_t& e = mObjects.valueAt(i);
         if (e.func != NULL) {
@@ -92,7 +92,7 @@
     , mObitsSent(0)
     , mObituaries(NULL)
 {
-    LOGV("Creating BpBinder %p handle %d\n", this, mHandle);
+    ALOGV("Creating BpBinder %p handle %d\n", this, mHandle);
 
     extendObjectLifetime(OBJECT_LIFETIME_WEAK);
     IPCThreadState::self()->incWeakHandle(handle);
@@ -190,7 +190,7 @@
                 if (!mObituaries) {
                     return NO_MEMORY;
                 }
-                LOGV("Requesting death notification: %p handle %d\n", this, mHandle);
+                ALOGV("Requesting death notification: %p handle %d\n", this, mHandle);
                 getWeakRefs()->incWeak(this);
                 IPCThreadState* self = IPCThreadState::self();
                 self->requestDeathNotification(mHandle, this);
@@ -226,7 +226,7 @@
             }
             mObituaries->removeAt(i);
             if (mObituaries->size() == 0) {
-                LOGV("Clearing death notification: %p handle %d\n", this, mHandle);
+                ALOGV("Clearing death notification: %p handle %d\n", this, mHandle);
                 IPCThreadState* self = IPCThreadState::self();
                 self->clearDeathNotification(mHandle, this);
                 self->flushCommands();
@@ -242,7 +242,7 @@
 
 void BpBinder::sendObituary()
 {
-    LOGV("Sending obituary for proxy %p handle %d, mObitsSent=%s\n",
+    ALOGV("Sending obituary for proxy %p handle %d, mObitsSent=%s\n",
         this, mHandle, mObitsSent ? "true" : "false");
 
     mAlive = 0;
@@ -251,7 +251,7 @@
     mLock.lock();
     Vector<Obituary>* obits = mObituaries;
     if(obits != NULL) {
-        LOGV("Clearing sent death notification: %p handle %d\n", this, mHandle);
+        ALOGV("Clearing sent death notification: %p handle %d\n", this, mHandle);
         IPCThreadState* self = IPCThreadState::self();
         self->clearDeathNotification(mHandle, this);
         self->flushCommands();
@@ -260,7 +260,7 @@
     mObitsSent = 1;
     mLock.unlock();
 
-    LOGV("Reporting death of proxy %p for %d recipients\n",
+    ALOGV("Reporting death of proxy %p for %d recipients\n",
         this, obits ? obits->size() : 0);
 
     if (obits != NULL) {
@@ -276,7 +276,7 @@
 void BpBinder::reportOneDeath(const Obituary& obit)
 {
     sp<DeathRecipient> recipient = obit.recipient.promote();
-    LOGV("Reporting death to recipient: %p\n", recipient.get());
+    ALOGV("Reporting death to recipient: %p\n", recipient.get());
     if (recipient == NULL) return;
 
     recipient->binderDied(this);
@@ -288,7 +288,7 @@
     object_cleanup_func func)
 {
     AutoMutex _l(mLock);
-    LOGV("Attaching object %p to binder %p (manager=%p)", object, this, &mObjects);
+    ALOGV("Attaching object %p to binder %p (manager=%p)", object, this, &mObjects);
     mObjects.attach(objectID, object, cleanupCookie, func);
 }
 
@@ -311,7 +311,7 @@
 
 BpBinder::~BpBinder()
 {
-    LOGV("Destroying BpBinder %p handle %d\n", this, mHandle);
+    ALOGV("Destroying BpBinder %p handle %d\n", this, mHandle);
 
     IPCThreadState* ipc = IPCThreadState::self();
 
@@ -338,15 +338,15 @@
 
 void BpBinder::onFirstRef()
 {
-    LOGV("onFirstRef BpBinder %p handle %d\n", this, mHandle);
+    ALOGV("onFirstRef BpBinder %p handle %d\n", this, mHandle);
     IPCThreadState* ipc = IPCThreadState::self();
     if (ipc) ipc->incStrongHandle(mHandle);
 }
 
 void BpBinder::onLastStrongRef(const void* id)
 {
-    LOGV("onLastStrongRef BpBinder %p handle %d\n", this, mHandle);
-    IF_LOGV() {
+    ALOGV("onLastStrongRef BpBinder %p handle %d\n", this, mHandle);
+    IF_ALOGV() {
         printRefs();
     }
     IPCThreadState* ipc = IPCThreadState::self();
@@ -355,7 +355,7 @@
 
 bool BpBinder::onIncStrongAttempted(uint32_t flags, const void* id)
 {
-    LOGV("onIncStrongAttempted BpBinder %p handle %d\n", this, mHandle);
+    ALOGV("onIncStrongAttempted BpBinder %p handle %d\n", this, mHandle);
     IPCThreadState* ipc = IPCThreadState::self();
     return ipc ? ipc->attemptIncStrongHandle(mHandle) == NO_ERROR : false;
 }
diff --git a/libs/binder/IPCThreadState.cpp b/libs/binder/IPCThreadState.cpp
index 5ccf87f..6965702 100644
--- a/libs/binder/IPCThreadState.cpp
+++ b/libs/binder/IPCThreadState.cpp
@@ -56,12 +56,12 @@
 
 #else
 
-#define IF_LOG_TRANSACTIONS() IF_LOG(LOG_VERBOSE, "transact")
-#define IF_LOG_COMMANDS() IF_LOG(LOG_VERBOSE, "ipc")
-#define LOG_REMOTEREFS(...) LOG(LOG_DEBUG, "remoterefs", __VA_ARGS__)
-#define IF_LOG_REMOTEREFS() IF_LOG(LOG_DEBUG, "remoterefs")
-#define LOG_THREADPOOL(...) LOG(LOG_DEBUG, "threadpool", __VA_ARGS__)
-#define LOG_ONEWAY(...) LOG(LOG_DEBUG, "ipc", __VA_ARGS__)
+#define IF_LOG_TRANSACTIONS() IF_ALOG(LOG_VERBOSE, "transact")
+#define IF_LOG_COMMANDS() IF_ALOG(LOG_VERBOSE, "ipc")
+#define LOG_REMOTEREFS(...) ALOG(LOG_DEBUG, "remoterefs", __VA_ARGS__)
+#define IF_LOG_REMOTEREFS() IF_ALOG(LOG_DEBUG, "remoterefs")
+#define LOG_THREADPOOL(...) ALOG(LOG_DEBUG, "threadpool", __VA_ARGS__)
+#define LOG_ONEWAY(...) ALOG(LOG_DEBUG, "ipc", __VA_ARGS__)
 
 #endif
 
diff --git a/libs/binder/Parcel.cpp b/libs/binder/Parcel.cpp
index 6b4c1a6..6cd43aa 100644
--- a/libs/binder/Parcel.cpp
+++ b/libs/binder/Parcel.cpp
@@ -44,7 +44,7 @@
 #endif
 
 #define LOG_REFS(...)
-//#define LOG_REFS(...) LOG(LOG_DEBUG, "Parcel", __VA_ARGS__)
+//#define LOG_REFS(...) ALOG(LOG_DEBUG, "Parcel", __VA_ARGS__)
 
 // ---------------------------------------------------------------------------
 
@@ -330,7 +330,7 @@
     err = continueWrite(size);
     if (err == NO_ERROR) {
         mDataSize = size;
-        LOGV("setDataSize Setting data size of %p to %d\n", this, mDataSize);
+        ALOGV("setDataSize Setting data size of %p to %d\n", this, mDataSize);
     }
     return err;
 }
@@ -534,10 +534,10 @@
 {
     //printf("Finish write of %d\n", len);
     mDataPos += len;
-    LOGV("finishWrite Setting data pos of %p to %d\n", this, mDataPos);
+    ALOGV("finishWrite Setting data pos of %p to %d\n", this, mDataPos);
     if (mDataPos > mDataSize) {
         mDataSize = mDataPos;
-        LOGV("finishWrite Setting data size of %p to %d\n", this, mDataSize);
+        ALOGV("finishWrite Setting data size of %p to %d\n", this, mDataSize);
     }
     //printf("New pos=%d, size=%d\n", mDataPos, mDataSize);
     return NO_ERROR;
@@ -722,7 +722,15 @@
 
 status_t Parcel::writeDupFileDescriptor(int fd)
 {
-    return writeFileDescriptor(dup(fd), true /*takeOwnership*/);
+    int dupFd = dup(fd);
+    if (dupFd < 0) {
+        return -errno;
+    }
+    status_t err = writeFileDescriptor(dupFd, true /*takeOwnership*/);
+    if (err) {
+        close(dupFd);
+    }
+    return err;
 }
 
 status_t Parcel::writeBlob(size_t len, WritableBlob* outBlob)
@@ -730,7 +738,7 @@
     status_t status;
 
     if (!mAllowFds || len <= IN_PLACE_BLOB_LIMIT) {
-        LOGV("writeBlob: write in place");
+        ALOGV("writeBlob: write in place");
         status = writeInt32(0);
         if (status) return status;
 
@@ -741,7 +749,7 @@
         return NO_ERROR;
     }
 
-    LOGV("writeBlob: write to ashmem");
+    ALOGV("writeBlob: write to ashmem");
     int fd = ashmem_create_region("Parcel Blob", len);
     if (fd < 0) return NO_MEMORY;
 
@@ -865,7 +873,7 @@
     if ((mDataPos+PAD_SIZE(len)) >= mDataPos && (mDataPos+PAD_SIZE(len)) <= mDataSize) {
         memcpy(outData, mData+mDataPos, len);
         mDataPos += PAD_SIZE(len);
-        LOGV("read Setting data pos of %p to %d\n", this, mDataPos);
+        ALOGV("read Setting data pos of %p to %d\n", this, mDataPos);
         return NO_ERROR;
     }
     return NOT_ENOUGH_DATA;
@@ -876,7 +884,7 @@
     if ((mDataPos+PAD_SIZE(len)) >= mDataPos && (mDataPos+PAD_SIZE(len)) <= mDataSize) {
         const void* data = mData+mDataPos;
         mDataPos += PAD_SIZE(len);
-        LOGV("readInplace Setting data pos of %p to %d\n", this, mDataPos);
+        ALOGV("readInplace Setting data pos of %p to %d\n", this, mDataPos);
         return data;
     }
     return NULL;
@@ -987,7 +995,7 @@
         if (eos) {
             const size_t len = eos - str;
             mDataPos += PAD_SIZE(len+1);
-            LOGV("readCString Setting data pos of %p to %d\n", this, mDataPos);
+            ALOGV("readCString Setting data pos of %p to %d\n", this, mDataPos);
             return str;
         }
     }
@@ -1102,7 +1110,7 @@
     if (status) return status;
 
     if (!useAshmem) {
-        LOGV("readBlob: read in place");
+        ALOGV("readBlob: read in place");
         const void* ptr = readInplace(len);
         if (!ptr) return BAD_VALUE;
 
@@ -1110,7 +1118,7 @@
         return NO_ERROR;
     }
 
-    LOGV("readBlob: read from ashmem");
+    ALOGV("readBlob: read from ashmem");
     int fd = readFileDescriptor();
     if (fd == int(BAD_TYPE)) return BAD_VALUE;
 
@@ -1164,7 +1172,7 @@
             // When transferring a NULL object, we don't write it into
             // the object list, so we don't want to check for it when
             // reading.
-            LOGV("readObject Setting data pos of %p to %d\n", this, mDataPos);
+            ALOGV("readObject Setting data pos of %p to %d\n", this, mDataPos);
             return obj;
         }
         
@@ -1174,7 +1182,7 @@
         size_t opos = mNextObjectHint;
         
         if (N > 0) {
-            LOGV("Parcel %p looking for obj at %d, hint=%d\n",
+            ALOGV("Parcel %p looking for obj at %d, hint=%d\n",
                  this, DPOS, opos);
             
             // Start at the current hint position, looking for an object at
@@ -1188,10 +1196,10 @@
             }
             if (OBJS[opos] == DPOS) {
                 // Found it!
-                LOGV("Parcel found obj %d at index %d with forward search",
+                ALOGV("Parcel found obj %d at index %d with forward search",
                      this, DPOS, opos);
                 mNextObjectHint = opos+1;
-                LOGV("readObject Setting data pos of %p to %d\n", this, mDataPos);
+                ALOGV("readObject Setting data pos of %p to %d\n", this, mDataPos);
                 return obj;
             }
         
@@ -1201,10 +1209,10 @@
             }
             if (OBJS[opos] == DPOS) {
                 // Found it!
-                LOGV("Parcel found obj %d at index %d with backward search",
+                ALOGV("Parcel found obj %d at index %d with backward search",
                      this, DPOS, opos);
                 mNextObjectHint = opos+1;
-                LOGV("readObject Setting data pos of %p to %d\n", this, mDataPos);
+                ALOGV("readObject Setting data pos of %p to %d\n", this, mDataPos);
                 return obj;
             }
         }
@@ -1260,7 +1268,7 @@
     mDataSize = mDataCapacity = dataSize;
     //LOGI("setDataReference Setting data size of %p to %lu (pid=%d)\n", this, mDataSize, getpid());
     mDataPos = 0;
-    LOGV("setDataReference Setting data pos of %p to %d\n", this, mDataPos);
+    ALOGV("setDataReference Setting data pos of %p to %d\n", this, mDataPos);
     mObjects = const_cast<size_t*>(objects);
     mObjectsSize = mObjectsCapacity = objectsCount;
     mNextObjectHint = 0;
@@ -1370,8 +1378,8 @@
     }
     
     mDataSize = mDataPos = 0;
-    LOGV("restartWrite Setting data size of %p to %d\n", this, mDataSize);
-    LOGV("restartWrite Setting data pos of %p to %d\n", this, mDataPos);
+    ALOGV("restartWrite Setting data size of %p to %d\n", this, mDataSize);
+    ALOGV("restartWrite Setting data pos of %p to %d\n", this, mDataPos);
         
     free(mObjects);
     mObjects = NULL;
@@ -1445,7 +1453,7 @@
         mData = data;
         mObjects = objects;
         mDataSize = (mDataSize < desired) ? mDataSize : desired;
-        LOGV("continueWrite Setting data size of %p to %d\n", this, mDataSize);
+        ALOGV("continueWrite Setting data size of %p to %d\n", this, mDataSize);
         mDataCapacity = desired;
         mObjectsSize = mObjectsCapacity = objectsSize;
         mNextObjectHint = 0;
@@ -1485,11 +1493,11 @@
         } else {
             if (mDataSize > desired) {
                 mDataSize = desired;
-                LOGV("continueWrite Setting data size of %p to %d\n", this, mDataSize);
+                ALOGV("continueWrite Setting data size of %p to %d\n", this, mDataSize);
             }
             if (mDataPos > desired) {
                 mDataPos = desired;
-                LOGV("continueWrite Setting data pos of %p to %d\n", this, mDataPos);
+                ALOGV("continueWrite Setting data pos of %p to %d\n", this, mDataPos);
             }
         }
         
@@ -1508,8 +1516,8 @@
         
         mData = data;
         mDataSize = mDataPos = 0;
-        LOGV("continueWrite Setting data size of %p to %d\n", this, mDataSize);
-        LOGV("continueWrite Setting data pos of %p to %d\n", this, mDataPos);
+        ALOGV("continueWrite Setting data size of %p to %d\n", this, mDataSize);
+        ALOGV("continueWrite Setting data pos of %p to %d\n", this, mDataPos);
         mDataCapacity = desired;
     }
 
@@ -1523,8 +1531,8 @@
     mDataSize = 0;
     mDataCapacity = 0;
     mDataPos = 0;
-    LOGV("initState Setting data size of %p to %d\n", this, mDataSize);
-    LOGV("initState Setting data pos of %p to %d\n", this, mDataPos);
+    ALOGV("initState Setting data size of %p to %d\n", this, mDataSize);
+    ALOGV("initState Setting data pos of %p to %d\n", this, mDataPos);
     mObjects = NULL;
     mObjectsSize = 0;
     mObjectsCapacity = 0;
diff --git a/libs/binder/ProcessState.cpp b/libs/binder/ProcessState.cpp
index f5288c8..f06a59e 100644
--- a/libs/binder/ProcessState.cpp
+++ b/libs/binder/ProcessState.cpp
@@ -288,7 +288,7 @@
         int32_t s = android_atomic_add(1, &mThreadPoolSeq);
         char buf[32];
         sprintf(buf, "Binder Thread #%d", s);
-        LOGV("Spawning new pooled thread, name=%s\n", buf);
+        ALOGV("Spawning new pooled thread, name=%s\n", buf);
         sp<Thread> t = new PoolThread(isMain);
         t->run(buf);
     }
diff --git a/libs/gui/Android.mk b/libs/gui/Android.mk
index 9767568..b7e3ee3 100644
--- a/libs/gui/Android.mk
+++ b/libs/gui/Android.mk
@@ -2,11 +2,11 @@
 include $(CLEAR_VARS)
 
 LOCAL_SRC_FILES:= \
+	BitTube.cpp \
 	ISensorEventConnection.cpp \
 	ISensorServer.cpp \
 	ISurfaceTexture.cpp \
 	Sensor.cpp \
-	SensorChannel.cpp \
 	SensorEventQueue.cpp \
 	SensorManager.cpp \
 	SurfaceTexture.cpp \
diff --git a/libs/gui/BitTube.cpp b/libs/gui/BitTube.cpp
new file mode 100644
index 0000000..c632b43
--- /dev/null
+++ b/libs/gui/BitTube.cpp
@@ -0,0 +1,115 @@
+/*
+ * 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.
+ */
+
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <unistd.h>
+#include <fcntl.h>
+
+#include <utils/Errors.h>
+
+#include <binder/Parcel.h>
+
+#include <gui/BitTube.h>
+
+namespace android {
+// ----------------------------------------------------------------------------
+
+BitTube::BitTube()
+    : mSendFd(-1), mReceiveFd(-1)
+{
+    int fds[2];
+    if (pipe(fds) == 0) {
+        mReceiveFd = fds[0];
+        mSendFd = fds[1];
+        fcntl(mReceiveFd, F_SETFL, O_NONBLOCK);
+        fcntl(mSendFd, F_SETFL, O_NONBLOCK);
+    } else {
+        mReceiveFd = -errno;
+        LOGE("BitTube: pipe creation failed (%s)", strerror(-mReceiveFd));
+    }
+}
+
+BitTube::BitTube(const Parcel& data)
+    : mSendFd(-1), mReceiveFd(-1)
+{
+    mReceiveFd = dup(data.readFileDescriptor());
+    if (mReceiveFd >= 0) {
+        fcntl(mReceiveFd, F_SETFL, O_NONBLOCK);
+    } else {
+        mReceiveFd = -errno;
+        LOGE("BitTube(Parcel): can't dup filedescriptor (%s)",
+                strerror(-mReceiveFd));
+    }
+}
+
+BitTube::~BitTube()
+{
+    if (mSendFd >= 0)
+        close(mSendFd);
+
+    if (mReceiveFd >= 0)
+        close(mReceiveFd);
+}
+
+status_t BitTube::initCheck() const
+{
+    if (mReceiveFd < 0) {
+        return status_t(mReceiveFd);
+    }
+    return NO_ERROR;
+}
+
+int BitTube::getFd() const
+{
+    return mReceiveFd;
+}
+
+ssize_t BitTube::write(void const* vaddr, size_t size)
+{
+    ssize_t err, len;
+    do {
+        len = ::write(mSendFd, vaddr, size);
+        err = len < 0 ? errno : 0;
+    } while (err == EINTR);
+    return err == 0 ? len : -err;
+
+}
+
+ssize_t BitTube::read(void* vaddr, size_t size)
+{
+    ssize_t err, len;
+    do {
+        len = ::read(mReceiveFd, vaddr, size);
+        err = len < 0 ? errno : 0;
+    } while (err == EINTR);
+    return err == 0 ? len : -err;
+}
+
+status_t BitTube::writeToParcel(Parcel* reply) const
+{
+    if (mReceiveFd < 0)
+        return -EINVAL;
+
+    status_t result = reply->writeDupFileDescriptor(mReceiveFd);
+    close(mReceiveFd);
+    mReceiveFd = -1;
+    return result;
+}
+
+// ----------------------------------------------------------------------------
+}; // namespace android
diff --git a/libs/gui/ISensorEventConnection.cpp b/libs/gui/ISensorEventConnection.cpp
index a5083fe..0e51e8e 100644
--- a/libs/gui/ISensorEventConnection.cpp
+++ b/libs/gui/ISensorEventConnection.cpp
@@ -25,7 +25,7 @@
 #include <binder/IInterface.h>
 
 #include <gui/ISensorEventConnection.h>
-#include <gui/SensorChannel.h>
+#include <gui/BitTube.h>
 
 namespace android {
 // ----------------------------------------------------------------------------
@@ -44,12 +44,12 @@
     {
     }
 
-    virtual sp<SensorChannel> getSensorChannel() const
+    virtual sp<BitTube> getSensorChannel() const
     {
         Parcel data, reply;
         data.writeInterfaceToken(ISensorEventConnection::getInterfaceDescriptor());
         remote()->transact(GET_SENSOR_CHANNEL, data, &reply);
-        return new SensorChannel(reply);
+        return new BitTube(reply);
     }
 
     virtual status_t enableDisable(int handle, bool enabled)
@@ -83,7 +83,7 @@
     switch(code) {
         case GET_SENSOR_CHANNEL: {
             CHECK_INTERFACE(ISensorEventConnection, data, reply);
-            sp<SensorChannel> channel(getSensorChannel());
+            sp<BitTube> channel(getSensorChannel());
             channel->writeToParcel(reply);
             return NO_ERROR;
         } break;
diff --git a/libs/gui/SensorChannel.cpp b/libs/gui/SensorChannel.cpp
deleted file mode 100644
index 147e1c2..0000000
--- a/libs/gui/SensorChannel.cpp
+++ /dev/null
@@ -1,93 +0,0 @@
-/*
- * 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.
- */
-
-#include <stdint.h>
-#include <sys/types.h>
-
-#include <unistd.h>
-#include <fcntl.h>
-
-#include <utils/Errors.h>
-
-#include <binder/Parcel.h>
-
-#include <gui/SensorChannel.h>
-
-namespace android {
-// ----------------------------------------------------------------------------
-
-SensorChannel::SensorChannel()
-    : mSendFd(-1), mReceiveFd(-1)
-{
-    int fds[2];
-    if (pipe(fds) == 0) {
-        mReceiveFd = fds[0];
-        mSendFd = fds[1];
-        fcntl(mReceiveFd, F_SETFL, O_NONBLOCK);
-        fcntl(mSendFd, F_SETFL, O_NONBLOCK);
-    }
-}
-
-SensorChannel::SensorChannel(const Parcel& data)
-    : mSendFd(-1), mReceiveFd(-1)
-{
-    mReceiveFd = dup(data.readFileDescriptor());
-    fcntl(mReceiveFd, F_SETFL, O_NONBLOCK);
-}
-
-SensorChannel::~SensorChannel()
-{
-    if (mSendFd >= 0)
-        close(mSendFd);
-
-    if (mReceiveFd >= 0)
-        close(mReceiveFd);
-}
-
-int SensorChannel::getFd() const
-{
-    return mReceiveFd;
-}
-
-ssize_t SensorChannel::write(void const* vaddr, size_t size)
-{
-    ssize_t len = ::write(mSendFd, vaddr, size);
-    if (len < 0)
-        return -errno;
-    return len;
-}
-
-ssize_t SensorChannel::read(void* vaddr, size_t size)
-{
-    ssize_t len = ::read(mReceiveFd, vaddr, size);
-    if (len < 0)
-        return -errno;
-    return len;
-}
-
-status_t SensorChannel::writeToParcel(Parcel* reply) const
-{
-    if (mReceiveFd < 0)
-        return -EINVAL;
-
-    status_t result = reply->writeDupFileDescriptor(mReceiveFd);
-    close(mReceiveFd);
-    mReceiveFd = -1;
-    return result;
-}
-
-// ----------------------------------------------------------------------------
-}; // namespace android
diff --git a/libs/gui/SensorEventQueue.cpp b/libs/gui/SensorEventQueue.cpp
index f935524..ee21c45 100644
--- a/libs/gui/SensorEventQueue.cpp
+++ b/libs/gui/SensorEventQueue.cpp
@@ -24,7 +24,7 @@
 #include <utils/Looper.h>
 
 #include <gui/Sensor.h>
-#include <gui/SensorChannel.h>
+#include <gui/BitTube.h>
 #include <gui/SensorEventQueue.h>
 #include <gui/ISensorEventConnection.h>
 
@@ -104,7 +104,7 @@
     do {
         result = looper->pollOnce(-1);
         if (result == ALOOPER_EVENT_ERROR) {
-            LOGE("SensorChannel::waitForEvent error (errno=%d)", errno);
+            LOGE("SensorEventQueue::waitForEvent error (errno=%d)", errno);
             result = -EPIPE; // unknown error, so we make up one
             break;
         }
diff --git a/libs/gui/SurfaceTexture.cpp b/libs/gui/SurfaceTexture.cpp
index beb23f6..b4d01a9 100644
--- a/libs/gui/SurfaceTexture.cpp
+++ b/libs/gui/SurfaceTexture.cpp
@@ -44,7 +44,7 @@
 #endif
 
 // Macros for including the SurfaceTexture name in log messages
-#define ST_LOGV(x, ...) LOGV("[%s] "x, mName.string(), ##__VA_ARGS__)
+#define ST_LOGV(x, ...) ALOGV("[%s] "x, mName.string(), ##__VA_ARGS__)
 #define ST_LOGD(x, ...) LOGD("[%s] "x, mName.string(), ##__VA_ARGS__)
 #define ST_LOGI(x, ...) LOGI("[%s] "x, mName.string(), ##__VA_ARGS__)
 #define ST_LOGW(x, ...) LOGW("[%s] "x, mName.string(), ##__VA_ARGS__)
diff --git a/libs/gui/SurfaceTextureClient.cpp b/libs/gui/SurfaceTextureClient.cpp
index 48070d6..3d47f05 100644
--- a/libs/gui/SurfaceTextureClient.cpp
+++ b/libs/gui/SurfaceTextureClient.cpp
@@ -136,13 +136,13 @@
 }
 
 int SurfaceTextureClient::dequeueBuffer(android_native_buffer_t** buffer) {
-    LOGV("SurfaceTextureClient::dequeueBuffer");
+    ALOGV("SurfaceTextureClient::dequeueBuffer");
     Mutex::Autolock lock(mMutex);
     int buf = -1;
     status_t result = mSurfaceTexture->dequeueBuffer(&buf, mReqWidth, mReqHeight,
             mReqFormat, mReqUsage);
     if (result < 0) {
-        LOGV("dequeueBuffer: ISurfaceTexture::dequeueBuffer(%d, %d, %d, %d)"
+        ALOGV("dequeueBuffer: ISurfaceTexture::dequeueBuffer(%d, %d, %d, %d)"
              "failed: %d", mReqWidth, mReqHeight, mReqFormat, mReqUsage,
              result);
         return result;
@@ -165,7 +165,7 @@
 }
 
 int SurfaceTextureClient::cancelBuffer(android_native_buffer_t* buffer) {
-    LOGV("SurfaceTextureClient::cancelBuffer");
+    ALOGV("SurfaceTextureClient::cancelBuffer");
     Mutex::Autolock lock(mMutex);
     int i = getSlotFromBufferLocked(buffer);
     if (i < 0) {
@@ -205,18 +205,18 @@
 }
 
 int SurfaceTextureClient::lockBuffer(android_native_buffer_t* buffer) {
-    LOGV("SurfaceTextureClient::lockBuffer");
+    ALOGV("SurfaceTextureClient::lockBuffer");
     Mutex::Autolock lock(mMutex);
     return OK;
 }
 
 int SurfaceTextureClient::queueBuffer(android_native_buffer_t* buffer) {
-    LOGV("SurfaceTextureClient::queueBuffer");
+    ALOGV("SurfaceTextureClient::queueBuffer");
     Mutex::Autolock lock(mMutex);
     int64_t timestamp;
     if (mTimestamp == NATIVE_WINDOW_TIMESTAMP_AUTO) {
         timestamp = systemTime(SYSTEM_TIME_MONOTONIC);
-        LOGV("SurfaceTextureClient::queueBuffer making up timestamp: %.2f ms",
+        ALOGV("SurfaceTextureClient::queueBuffer making up timestamp: %.2f ms",
              timestamp / 1000000.f);
     } else {
         timestamp = mTimestamp;
@@ -234,7 +234,7 @@
 }
 
 int SurfaceTextureClient::query(int what, int* value) const {
-    LOGV("SurfaceTextureClient::query");
+    ALOGV("SurfaceTextureClient::query");
     { // scope for the lock
         Mutex::Autolock lock(mMutex);
         switch (what) {
@@ -402,7 +402,7 @@
 
 
 int SurfaceTextureClient::connect(int api) {
-    LOGV("SurfaceTextureClient::connect");
+    ALOGV("SurfaceTextureClient::connect");
     Mutex::Autolock lock(mMutex);
     int err = mSurfaceTexture->connect(api,
             &mDefaultWidth, &mDefaultHeight, &mTransformHint);
@@ -413,7 +413,7 @@
 }
 
 int SurfaceTextureClient::disconnect(int api) {
-    LOGV("SurfaceTextureClient::disconnect");
+    ALOGV("SurfaceTextureClient::disconnect");
     Mutex::Autolock lock(mMutex);
     freeAllBuffers();
     int err = mSurfaceTexture->disconnect(api);
@@ -431,7 +431,7 @@
 
 int SurfaceTextureClient::setUsage(uint32_t reqUsage)
 {
-    LOGV("SurfaceTextureClient::setUsage");
+    ALOGV("SurfaceTextureClient::setUsage");
     Mutex::Autolock lock(mMutex);
     mReqUsage = reqUsage;
     return OK;
@@ -439,7 +439,7 @@
 
 int SurfaceTextureClient::setCrop(Rect const* rect)
 {
-    LOGV("SurfaceTextureClient::setCrop");
+    ALOGV("SurfaceTextureClient::setCrop");
     Mutex::Autolock lock(mMutex);
 
     Rect realRect;
@@ -457,7 +457,7 @@
 
 int SurfaceTextureClient::setBufferCount(int bufferCount)
 {
-    LOGV("SurfaceTextureClient::setBufferCount");
+    ALOGV("SurfaceTextureClient::setBufferCount");
     Mutex::Autolock lock(mMutex);
 
     status_t err = mSurfaceTexture->setBufferCount(bufferCount);
@@ -473,7 +473,7 @@
 
 int SurfaceTextureClient::setBuffersDimensions(int w, int h)
 {
-    LOGV("SurfaceTextureClient::setBuffersDimensions");
+    ALOGV("SurfaceTextureClient::setBuffersDimensions");
     Mutex::Autolock lock(mMutex);
 
     if (w<0 || h<0)
@@ -493,7 +493,7 @@
 
 int SurfaceTextureClient::setBuffersFormat(int format)
 {
-    LOGV("SurfaceTextureClient::setBuffersFormat");
+    ALOGV("SurfaceTextureClient::setBuffersFormat");
     Mutex::Autolock lock(mMutex);
 
     if (format<0)
@@ -506,7 +506,7 @@
 
 int SurfaceTextureClient::setScalingMode(int mode)
 {
-    LOGV("SurfaceTextureClient::setScalingMode(%d)", mode);
+    ALOGV("SurfaceTextureClient::setScalingMode(%d)", mode);
     Mutex::Autolock lock(mMutex);
     // mode is validated on the server
     status_t err = mSurfaceTexture->setScalingMode(mode);
@@ -518,7 +518,7 @@
 
 int SurfaceTextureClient::setBuffersTransform(int transform)
 {
-    LOGV("SurfaceTextureClient::setBuffersTransform");
+    ALOGV("SurfaceTextureClient::setBuffersTransform");
     Mutex::Autolock lock(mMutex);
     status_t err = mSurfaceTexture->setTransform(transform);
     return err;
@@ -526,7 +526,7 @@
 
 int SurfaceTextureClient::setBuffersTimestamp(int64_t timestamp)
 {
-    LOGV("SurfaceTextureClient::setBuffersTimestamp");
+    ALOGV("SurfaceTextureClient::setBuffersTimestamp");
     Mutex::Autolock lock(mMutex);
     mTimestamp = timestamp;
     return NO_ERROR;
diff --git a/libs/gui/tests/SurfaceTexture_test.cpp b/libs/gui/tests/SurfaceTexture_test.cpp
index 6d1b951..c79e69a 100644
--- a/libs/gui/tests/SurfaceTexture_test.cpp
+++ b/libs/gui/tests/SurfaceTexture_test.cpp
@@ -1385,12 +1385,12 @@
         // test.
         void waitForFrame() {
             Mutex::Autolock lock(mMutex);
-            LOGV("+waitForFrame");
+            ALOGV("+waitForFrame");
             while (!mFrameAvailable) {
                 mFrameAvailableCondition.wait(mMutex);
             }
             mFrameAvailable = false;
-            LOGV("-waitForFrame");
+            ALOGV("-waitForFrame");
         }
 
         // Allow the producer to return from its swapBuffers call and continue
@@ -1398,23 +1398,23 @@
         // thread once for every frame expected by the test.
         void finishFrame() {
             Mutex::Autolock lock(mMutex);
-            LOGV("+finishFrame");
+            ALOGV("+finishFrame");
             mFrameFinished = true;
             mFrameFinishCondition.signal();
-            LOGV("-finishFrame");
+            ALOGV("-finishFrame");
         }
 
         // This should be called by SurfaceTexture on the producer thread.
         virtual void onFrameAvailable() {
             Mutex::Autolock lock(mMutex);
-            LOGV("+onFrameAvailable");
+            ALOGV("+onFrameAvailable");
             mFrameAvailable = true;
             mFrameAvailableCondition.signal();
             while (!mFrameFinished) {
                 mFrameFinishCondition.wait(mMutex);
             }
             mFrameFinished = false;
-            LOGV("-onFrameAvailable");
+            ALOGV("-onFrameAvailable");
         }
 
     protected:
@@ -1500,9 +1500,9 @@
             for (int i = 0; i < NUM_ITERATIONS; i++) {
                 glClearColor(0.0f, 1.0f, 0.0f, 1.0f);
                 glClear(GL_COLOR_BUFFER_BIT);
-                LOGV("+swapBuffers");
+                ALOGV("+swapBuffers");
                 swapBuffers();
-                LOGV("-swapBuffers");
+                ALOGV("-swapBuffers");
             }
         }
     };
@@ -1511,9 +1511,9 @@
 
     for (int i = 0; i < NUM_ITERATIONS; i++) {
         mFC->waitForFrame();
-        LOGV("+updateTexImage");
+        ALOGV("+updateTexImage");
         mST->updateTexImage();
-        LOGV("-updateTexImage");
+        ALOGV("-updateTexImage");
         mFC->finishFrame();
 
         // TODO: Add frame verification once RGB TEX_EXTERNAL_OES is supported!
@@ -1529,9 +1529,9 @@
             for (int i = 0; i < NUM_ITERATIONS; i++) {
                 glClearColor(0.0f, 1.0f, 0.0f, 1.0f);
                 glClear(GL_COLOR_BUFFER_BIT);
-                LOGV("+swapBuffers");
+                ALOGV("+swapBuffers");
                 swapBuffers();
-                LOGV("-swapBuffers");
+                ALOGV("-swapBuffers");
             }
         }
     };
@@ -1541,9 +1541,9 @@
     for (int i = 0; i < NUM_ITERATIONS; i++) {
         mFC->waitForFrame();
         mFC->finishFrame();
-        LOGV("+updateTexImage");
+        ALOGV("+updateTexImage");
         mST->updateTexImage();
-        LOGV("-updateTexImage");
+        ALOGV("-updateTexImage");
 
         // TODO: Add frame verification once RGB TEX_EXTERNAL_OES is supported!
     }
@@ -1559,9 +1559,9 @@
             for (int i = 0; i < NUM_ITERATIONS; i++) {
                 glClearColor(0.0f, 1.0f, 0.0f, 1.0f);
                 glClear(GL_COLOR_BUFFER_BIT);
-                LOGV("+swapBuffers");
+                ALOGV("+swapBuffers");
                 swapBuffers();
-                LOGV("-swapBuffers");
+                ALOGV("-swapBuffers");
             }
         }
     };
@@ -1610,9 +1610,9 @@
     for (int i = 0; i < NUM_ITERATIONS-3; i++) {
         mFC->waitForFrame();
         mFC->finishFrame();
-        LOGV("+updateTexImage");
+        ALOGV("+updateTexImage");
         mST->updateTexImage();
-        LOGV("-updateTexImage");
+        ALOGV("-updateTexImage");
     }
 }
 
diff --git a/libs/utils/Android.mk b/libs/utils/Android.mk
index 831d9e3..544ab74 100644
--- a/libs/utils/Android.mk
+++ b/libs/utils/Android.mk
@@ -21,6 +21,7 @@
 	Asset.cpp \
 	AssetDir.cpp \
 	AssetManager.cpp \
+	BasicHashtable.cpp \
 	BlobCache.cpp \
 	BufferedTextOutput.cpp \
 	CallStack.cpp \
@@ -105,7 +106,8 @@
 	libz \
 	liblog \
 	libcutils \
-	libdl
+	libdl \
+	libcorkscrew
 
 LOCAL_MODULE:= libutils
 include $(BUILD_SHARED_LIBRARY)
diff --git a/libs/utils/Asset.cpp b/libs/utils/Asset.cpp
index a18294b..7fd2c87 100644
--- a/libs/utils/Asset.cpp
+++ b/libs/utils/Asset.cpp
@@ -585,7 +585,7 @@
             return NULL;
         }
 
-        LOGV("Asset %p allocating buffer size %d (smaller than threshold)", this, (int)allocLen);
+        ALOGV("Asset %p allocating buffer size %d (smaller than threshold)", this, (int)allocLen);
         if (mLength > 0) {
             long oldPosn = ftell(mFp);
             fseek(mFp, mStart, SEEK_SET);
@@ -597,7 +597,7 @@
             fseek(mFp, oldPosn, SEEK_SET);
         }
 
-        LOGV(" getBuffer: loaded into buffer\n");
+        ALOGV(" getBuffer: loaded into buffer\n");
 
         mBuf = buf;
         return mBuf;
@@ -610,7 +610,7 @@
             return NULL;
         }
 
-        LOGV(" getBuffer: mapped\n");
+        ALOGV(" getBuffer: mapped\n");
 
         mMap = map;
         if (!wordAligned) {
@@ -648,13 +648,13 @@
     if ((((size_t)data)&0x3) == 0) {
         // We can return this directly if it is aligned on a word
         // boundary.
-        LOGV("Returning aligned FileAsset %p (%s).", this,
+        ALOGV("Returning aligned FileAsset %p (%s).", this,
                 getAssetSource());
         return data;
     }
     // If not aligned on a word boundary, then we need to copy it into
     // our own buffer.
-    LOGV("Copying FileAsset %p (%s) to buffer size %d to make it aligned.", this,
+    ALOGV("Copying FileAsset %p (%s) to buffer size %d to make it aligned.", this,
             getAssetSource(), (int)mLength);
     unsigned char* buf = new unsigned char[mLength];
     if (buf == NULL) {
diff --git a/libs/utils/AssetManager.cpp b/libs/utils/AssetManager.cpp
index 22034c5..203e6fa 100644
--- a/libs/utils/AssetManager.cpp
+++ b/libs/utils/AssetManager.cpp
@@ -167,7 +167,7 @@
         }
     }
 
-    LOGV("In %p Asset %s path: %s", this,
+    ALOGV("In %p Asset %s path: %s", this,
          ap.type == kFileTypeDirectory ? "dir" : "zip", ap.path.string());
 
     mAssetPaths.add(ap);
@@ -498,7 +498,7 @@
     size_t i = mAssetPaths.size();
     while (i > 0) {
         i--;
-        LOGV("Looking for asset '%s' in '%s'\n",
+        ALOGV("Looking for asset '%s' in '%s'\n",
                 assetName.string(), mAssetPaths.itemAt(i).path.string());
         Asset* pAsset = openNonAssetInPathLocked(assetName.string(), mode, mAssetPaths.itemAt(i));
         if (pAsset != NULL) {
@@ -532,7 +532,7 @@
     size_t i = mAssetPaths.size();
     while (i > 0) {
         i--;
-        LOGV("Looking for non-asset '%s' in '%s'\n", fileName, mAssetPaths.itemAt(i).path.string());
+        ALOGV("Looking for non-asset '%s' in '%s'\n", fileName, mAssetPaths.itemAt(i).path.string());
         Asset* pAsset = openNonAssetInPathLocked(
             fileName, mode, mAssetPaths.itemAt(i));
         if (pAsset != NULL) {
@@ -556,7 +556,7 @@
         loadFileNameCacheLocked();
 
     if (which < mAssetPaths.size()) {
-        LOGV("Looking for non-asset '%s' in '%s'\n", fileName,
+        ALOGV("Looking for non-asset '%s' in '%s'\n", fileName,
                 mAssetPaths.itemAt(which).path.string());
         Asset* pAsset = openNonAssetInPathLocked(
             fileName, mode, mAssetPaths.itemAt(which));
@@ -621,7 +621,7 @@
         bool shared = true;
         const asset_path& ap = mAssetPaths.itemAt(i);
         Asset* idmap = openIdmapLocked(ap);
-        LOGV("Looking for resource asset in '%s'\n", ap.path.string());
+        ALOGV("Looking for resource asset in '%s'\n", ap.path.string());
         if (ap.type != kFileTypeDirectory) {
             if (i == 0) {
                 // The first item is typically the framework resources,
@@ -633,7 +633,7 @@
                 ass = const_cast<AssetManager*>(this)->
                     mZipSet.getZipResourceTableAsset(ap.path);
                 if (ass == NULL) {
-                    LOGV("loading resource table %s\n", ap.path.string());
+                    ALOGV("loading resource table %s\n", ap.path.string());
                     ass = const_cast<AssetManager*>(this)->
                         openNonAssetInPathLocked("resources.arsc",
                                                  Asset::ACCESS_BUFFER,
@@ -648,7 +648,7 @@
                     // If this is the first resource table in the asset
                     // manager, then we are going to cache it so that we
                     // can quickly copy it out for others.
-                    LOGV("Creating shared resources for %s", ap.path.string());
+                    ALOGV("Creating shared resources for %s", ap.path.string());
                     sharedRes = new ResTable();
                     sharedRes->add(ass, (void*)(i+1), false, idmap);
                     sharedRes = const_cast<AssetManager*>(this)->
@@ -656,7 +656,7 @@
                 }
             }
         } else {
-            LOGV("loading resource table %s\n", ap.path.string());
+            ALOGV("loading resource table %s\n", ap.path.string());
             Asset* ass = const_cast<AssetManager*>(this)->
                 openNonAssetInPathLocked("resources.arsc",
                                          Asset::ACCESS_BUFFER,
@@ -668,12 +668,12 @@
                 mResources = rt = new ResTable();
                 updateResourceParamsLocked();
             }
-            LOGV("Installing resource asset %p in to table %p\n", ass, mResources);
+            ALOGV("Installing resource asset %p in to table %p\n", ass, mResources);
             if (sharedRes != NULL) {
-                LOGV("Copying existing resources for %s", ap.path.string());
+                ALOGV("Copying existing resources for %s", ap.path.string());
                 rt->add(sharedRes);
             } else {
-                LOGV("Parsing resources for %s", ap.path.string());
+                ALOGV("Parsing resources for %s", ap.path.string());
                 rt->add(ass, (void*)(i+1), !shared, idmap);
             }
 
@@ -725,7 +725,7 @@
         ass = const_cast<AssetManager*>(this)->
             openAssetFromFileLocked(ap.idmap, Asset::ACCESS_BUFFER);
         if (ass) {
-            LOGV("loading idmap %s\n", ap.idmap.string());
+            ALOGV("loading idmap %s\n", ap.idmap.string());
         } else {
             LOGW("failed to load idmap %s\n", ap.idmap.string());
         }
@@ -1019,7 +1019,7 @@
  */
 ZipFileRO* AssetManager::getZipFileLocked(const asset_path& ap)
 {
-    LOGV("getZipFileLocked() in %p\n", this);
+    ALOGV("getZipFileLocked() in %p\n", this);
 
     return mZipSet.getZip(ap.path);
 }
@@ -1086,12 +1086,12 @@
 
     if (method == ZipFileRO::kCompressStored) {
         pAsset = Asset::createFromUncompressedMap(dataMap, mode);
-        LOGV("Opened uncompressed entry %s in zip %s mode %d: %p", entryName.string(),
+        ALOGV("Opened uncompressed entry %s in zip %s mode %d: %p", entryName.string(),
                 dataMap->getFileName(), mode, pAsset);
     } else {
         pAsset = Asset::createFromCompressedMap(dataMap, method,
             uncompressedLen, mode);
-        LOGV("Opened compressed entry %s in zip %s mode %d: %p", entryName.string(),
+        ALOGV("Opened compressed entry %s in zip %s mode %d: %p", entryName.string(),
                 dataMap->getFileName(), mode, pAsset);
     }
     if (pAsset == NULL) {
@@ -1146,10 +1146,10 @@
         i--;
         const asset_path& ap = mAssetPaths.itemAt(i);
         if (ap.type == kFileTypeRegular) {
-            LOGV("Adding directory %s from zip %s", dirName, ap.path.string());
+            ALOGV("Adding directory %s from zip %s", dirName, ap.path.string());
             scanAndMergeZipLocked(pMergedInfo, ap, kAssetsRoot, dirName);
         } else {
-            LOGV("Adding directory %s from dir %s", dirName, ap.path.string());
+            ALOGV("Adding directory %s from dir %s", dirName, ap.path.string());
             scanAndMergeDirLocked(pMergedInfo, ap, kAssetsRoot, dirName);
         }
     }
@@ -1200,10 +1200,10 @@
     if (which < mAssetPaths.size()) {
         const asset_path& ap = mAssetPaths.itemAt(which);
         if (ap.type == kFileTypeRegular) {
-            LOGV("Adding directory %s from zip %s", dirName, ap.path.string());
+            ALOGV("Adding directory %s from zip %s", dirName, ap.path.string());
             scanAndMergeZipLocked(pMergedInfo, ap, NULL, dirName);
         } else {
-            LOGV("Adding directory %s from dir %s", dirName, ap.path.string());
+            ALOGV("Adding directory %s from dir %s", dirName, ap.path.string());
             scanAndMergeDirLocked(pMergedInfo, ap, NULL, dirName);
         }
     }
@@ -1325,7 +1325,7 @@
 
             matchIdx = AssetDir::FileInfo::findEntry(pMergedInfo, match);
             if (matchIdx > 0) {
-                LOGV("Excluding '%s' [%s]\n",
+                ALOGV("Excluding '%s' [%s]\n",
                     pMergedInfo->itemAt(matchIdx).getFileName().string(),
                     pMergedInfo->itemAt(matchIdx).getSourceName().string());
                 pMergedInfo->removeAt(matchIdx);
@@ -1365,7 +1365,7 @@
     struct dirent* entry;
     FileType fileType;
 
-    LOGV("Scanning dir '%s'\n", path.string());
+    ALOGV("Scanning dir '%s'\n", path.string());
 
     dir = opendir(path.string());
     if (dir == NULL)
@@ -1782,7 +1782,7 @@
 {
     //LOGI("Creating SharedZip %p %s\n", this, (const char*)mPath);
     mZipFile = new ZipFileRO;
-    LOGV("+++ opening zip '%s'\n", mPath.string());
+    ALOGV("+++ opening zip '%s'\n", mPath.string());
     if (mZipFile->open(mPath.string()) != NO_ERROR) {
         LOGD("failed to open Zip archive '%s'\n", mPath.string());
         delete mZipFile;
@@ -1811,7 +1811,7 @@
 
 Asset* AssetManager::SharedZip::getResourceTableAsset()
 {
-    LOGV("Getting from SharedZip %p resource asset %p\n", this, mResourceTableAsset);
+    ALOGV("Getting from SharedZip %p resource asset %p\n", this, mResourceTableAsset);
     return mResourceTableAsset;
 }
 
@@ -1833,7 +1833,7 @@
 
 ResTable* AssetManager::SharedZip::getResourceTable()
 {
-    LOGV("Getting from SharedZip %p resource table %p\n", this, mResourceTable);
+    ALOGV("Getting from SharedZip %p resource table %p\n", this, mResourceTable);
     return mResourceTable;
 }
 
@@ -1867,7 +1867,7 @@
     }
     if (mZipFile != NULL) {
         delete mZipFile;
-        LOGV("Closed '%s'\n", mPath.string());
+        ALOGV("Closed '%s'\n", mPath.string());
     }
 }
 
diff --git a/libs/utils/BasicHashtable.cpp b/libs/utils/BasicHashtable.cpp
new file mode 100644
index 0000000..fb8ec9f
--- /dev/null
+++ b/libs/utils/BasicHashtable.cpp
@@ -0,0 +1,338 @@
+/*
+ * 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.
+ */
+
+#define LOG_TAG "BasicHashtable"
+
+#include <math.h>
+
+#include <utils/Log.h>
+#include <utils/BasicHashtable.h>
+#include <utils/misc.h>
+
+namespace android {
+
+BasicHashtableImpl::BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor,
+        size_t minimumInitialCapacity, float loadFactor) :
+        mBucketSize(entrySize + sizeof(Bucket)), mHasTrivialDestructor(hasTrivialDestructor),
+        mLoadFactor(loadFactor), mSize(0),
+        mFilledBuckets(0), mBuckets(NULL) {
+    determineCapacity(minimumInitialCapacity, mLoadFactor, &mBucketCount, &mCapacity);
+}
+
+BasicHashtableImpl::BasicHashtableImpl(const BasicHashtableImpl& other) :
+        mBucketSize(other.mBucketSize), mHasTrivialDestructor(other.mHasTrivialDestructor),
+        mCapacity(other.mCapacity), mLoadFactor(other.mLoadFactor),
+        mSize(other.mSize), mFilledBuckets(other.mFilledBuckets),
+        mBucketCount(other.mBucketCount), mBuckets(other.mBuckets) {
+    if (mBuckets) {
+        SharedBuffer::bufferFromData(mBuckets)->acquire();
+    }
+}
+
+void BasicHashtableImpl::dispose() {
+    if (mBuckets) {
+        releaseBuckets(mBuckets, mBucketCount);
+    }
+}
+
+void BasicHashtableImpl::clone() {
+    if (mBuckets) {
+        void* newBuckets = allocateBuckets(mBucketCount);
+        copyBuckets(mBuckets, newBuckets, mBucketCount);
+        releaseBuckets(mBuckets, mBucketCount);
+        mBuckets = newBuckets;
+    }
+}
+
+void BasicHashtableImpl::setTo(const BasicHashtableImpl& other) {
+    if (mBuckets) {
+        releaseBuckets(mBuckets, mBucketCount);
+    }
+
+    mCapacity = other.mCapacity;
+    mLoadFactor = other.mLoadFactor;
+    mSize = other.mSize;
+    mFilledBuckets = other.mFilledBuckets;
+    mBucketCount = other.mBucketCount;
+    mBuckets = other.mBuckets;
+
+    if (mBuckets) {
+        SharedBuffer::bufferFromData(mBuckets)->acquire();
+    }
+}
+
+void BasicHashtableImpl::clear() {
+    if (mBuckets) {
+        if (mFilledBuckets) {
+            SharedBuffer* sb = SharedBuffer::bufferFromData(mBuckets);
+            if (sb->onlyOwner()) {
+                destroyBuckets(mBuckets, mBucketCount);
+                for (size_t i = 0; i < mSize; i++) {
+                    Bucket& bucket = bucketAt(mBuckets, i);
+                    bucket.cookie = 0;
+                }
+            } else {
+                releaseBuckets(mBuckets, mBucketCount);
+                mBuckets = NULL;
+            }
+            mFilledBuckets = 0;
+        }
+        mSize = 0;
+    }
+}
+
+ssize_t BasicHashtableImpl::next(ssize_t index) const {
+    if (mSize) {
+        while (size_t(++index) < mBucketCount) {
+            const Bucket& bucket = bucketAt(mBuckets, index);
+            if (bucket.cookie & Bucket::PRESENT) {
+                return index;
+            }
+        }
+    }
+    return -1;
+}
+
+ssize_t BasicHashtableImpl::find(ssize_t index, hash_t hash,
+        const void* __restrict__ key) const {
+    if (!mSize) {
+        return -1;
+    }
+
+    hash = trimHash(hash);
+    if (index < 0) {
+        index = chainStart(hash, mBucketCount);
+
+        const Bucket& bucket = bucketAt(mBuckets, size_t(index));
+        if (bucket.cookie & Bucket::PRESENT) {
+            if (compareBucketKey(bucket, key)) {
+                return index;
+            }
+        } else {
+            if (!(bucket.cookie & Bucket::COLLISION)) {
+                return -1;
+            }
+        }
+    }
+
+    size_t inc = chainIncrement(hash, mBucketCount);
+    for (;;) {
+        index = chainSeek(index, inc, mBucketCount);
+
+        const Bucket& bucket = bucketAt(mBuckets, size_t(index));
+        if (bucket.cookie & Bucket::PRESENT) {
+            if ((bucket.cookie & Bucket::HASH_MASK) == hash
+                    && compareBucketKey(bucket, key)) {
+                return index;
+            }
+        }
+        if (!(bucket.cookie & Bucket::COLLISION)) {
+            return -1;
+        }
+    }
+}
+
+size_t BasicHashtableImpl::add(hash_t hash, const void* entry) {
+    if (!mBuckets) {
+        mBuckets = allocateBuckets(mBucketCount);
+    } else {
+        edit();
+    }
+
+    hash = trimHash(hash);
+    for (;;) {
+        size_t index = chainStart(hash, mBucketCount);
+        Bucket* bucket = &bucketAt(mBuckets, size_t(index));
+        if (bucket->cookie & Bucket::PRESENT) {
+            size_t inc = chainIncrement(hash, mBucketCount);
+            do {
+                bucket->cookie |= Bucket::COLLISION;
+                index = chainSeek(index, inc, mBucketCount);
+                bucket = &bucketAt(mBuckets, size_t(index));
+            } while (bucket->cookie & Bucket::PRESENT);
+        }
+
+        uint32_t collision = bucket->cookie & Bucket::COLLISION;
+        if (!collision) {
+            if (mFilledBuckets >= mCapacity) {
+                rehash(mCapacity * 2, mLoadFactor);
+                continue;
+            }
+            mFilledBuckets += 1;
+        }
+
+        bucket->cookie = collision | Bucket::PRESENT | hash;
+        mSize += 1;
+        initializeBucketEntry(*bucket, entry);
+        return index;
+    }
+}
+
+void BasicHashtableImpl::removeAt(size_t index) {
+    edit();
+
+    Bucket& bucket = bucketAt(mBuckets, index);
+    bucket.cookie &= ~Bucket::PRESENT;
+    if (!(bucket.cookie & Bucket::COLLISION)) {
+        mFilledBuckets -= 1;
+    }
+    mSize -= 1;
+    if (!mHasTrivialDestructor) {
+        destroyBucketEntry(bucket);
+    }
+}
+
+void BasicHashtableImpl::rehash(size_t minimumCapacity, float loadFactor) {
+    if (minimumCapacity < mSize) {
+        minimumCapacity = mSize;
+    }
+    size_t newBucketCount, newCapacity;
+    determineCapacity(minimumCapacity, loadFactor, &newBucketCount, &newCapacity);
+
+    if (newBucketCount != mBucketCount || newCapacity != mCapacity) {
+        if (mBuckets) {
+            void* newBuckets;
+            if (mSize) {
+                newBuckets = allocateBuckets(newBucketCount);
+                for (size_t i = 0; i < mBucketCount; i++) {
+                    const Bucket& fromBucket = bucketAt(mBuckets, i);
+                    if (fromBucket.cookie & Bucket::PRESENT) {
+                        hash_t hash = fromBucket.cookie & Bucket::HASH_MASK;
+                        size_t index = chainStart(hash, newBucketCount);
+                        Bucket* toBucket = &bucketAt(newBuckets, size_t(index));
+                        if (toBucket->cookie & Bucket::PRESENT) {
+                            size_t inc = chainIncrement(hash, newBucketCount);
+                            do {
+                                toBucket->cookie |= Bucket::COLLISION;
+                                index = chainSeek(index, inc, newBucketCount);
+                                toBucket = &bucketAt(newBuckets, size_t(index));
+                            } while (toBucket->cookie & Bucket::PRESENT);
+                        }
+                        toBucket->cookie = Bucket::PRESENT | hash;
+                        initializeBucketEntry(*toBucket, fromBucket.entry);
+                    }
+                }
+            } else {
+                newBuckets = NULL;
+            }
+            releaseBuckets(mBuckets, mBucketCount);
+            mBuckets = newBuckets;
+            mFilledBuckets = mSize;
+        }
+        mBucketCount = newBucketCount;
+        mCapacity = newCapacity;
+    }
+    mLoadFactor = loadFactor;
+}
+
+void* BasicHashtableImpl::allocateBuckets(size_t count) const {
+    size_t bytes = count * mBucketSize;
+    SharedBuffer* sb = SharedBuffer::alloc(bytes);
+    LOG_ALWAYS_FATAL_IF(!sb, "Could not allocate %u bytes for hashtable with %u buckets.",
+            uint32_t(bytes), uint32_t(count));
+    void* buckets = sb->data();
+    for (size_t i = 0; i < count; i++) {
+        Bucket& bucket = bucketAt(buckets, i);
+        bucket.cookie = 0;
+    }
+    return buckets;
+}
+
+void BasicHashtableImpl::releaseBuckets(void* __restrict__ buckets, size_t count) const {
+    SharedBuffer* sb = SharedBuffer::bufferFromData(buckets);
+    if (sb->release(SharedBuffer::eKeepStorage) == 1) {
+        destroyBuckets(buckets, count);
+        SharedBuffer::dealloc(sb);
+    }
+}
+
+void BasicHashtableImpl::destroyBuckets(void* __restrict__ buckets, size_t count) const {
+    if (!mHasTrivialDestructor) {
+        for (size_t i = 0; i < count; i++) {
+            Bucket& bucket = bucketAt(buckets, i);
+            if (bucket.cookie & Bucket::PRESENT) {
+                destroyBucketEntry(bucket);
+            }
+        }
+    }
+}
+
+void BasicHashtableImpl::copyBuckets(const void* __restrict__ fromBuckets,
+        void* __restrict__ toBuckets, size_t count) const {
+    for (size_t i = 0; i < count; i++) {
+        const Bucket& fromBucket = bucketAt(fromBuckets, i);
+        Bucket& toBucket = bucketAt(toBuckets, i);
+        toBucket.cookie = fromBucket.cookie;
+        if (fromBucket.cookie & Bucket::PRESENT) {
+            initializeBucketEntry(toBucket, fromBucket.entry);
+        }
+    }
+}
+
+// Table of 31-bit primes where each prime is no less than twice as large
+// as the previous one.  Generated by "primes.py".
+static size_t PRIMES[] = {
+    5,
+    11,
+    23,
+    47,
+    97,
+    197,
+    397,
+    797,
+    1597,
+    3203,
+    6421,
+    12853,
+    25717,
+    51437,
+    102877,
+    205759,
+    411527,
+    823117,
+    1646237,
+    3292489,
+    6584983,
+    13169977,
+    26339969,
+    52679969,
+    105359939,
+    210719881,
+    421439783,
+    842879579,
+    1685759167,
+    0,
+};
+
+void BasicHashtableImpl::determineCapacity(size_t minimumCapacity, float loadFactor,
+        size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity) {
+    LOG_ALWAYS_FATAL_IF(loadFactor <= 0.0f || loadFactor > 1.0f,
+            "Invalid load factor %0.3f.  Must be in the range (0, 1].", loadFactor);
+
+    size_t count = ceilf(minimumCapacity / loadFactor) + 1;
+    size_t i = 0;
+    while (count > PRIMES[i] && i < NELEM(PRIMES)) {
+        i++;
+    }
+    count = PRIMES[i];
+    LOG_ALWAYS_FATAL_IF(!count, "Could not determine required number of buckets for "
+            "hashtable with minimum capacity %u and load factor %0.3f.",
+            uint32_t(minimumCapacity), loadFactor);
+    *outBucketCount = count;
+    *outCapacity = ceilf((count - 1) * loadFactor);
+}
+
+}; // namespace android
diff --git a/libs/utils/BlobCache.cpp b/libs/utils/BlobCache.cpp
index d38aae9..4970828 100644
--- a/libs/utils/BlobCache.cpp
+++ b/libs/utils/BlobCache.cpp
@@ -48,23 +48,23 @@
     mRandState[1] = (now >> 16) & 0xFFFF;
     mRandState[2] = (now >> 32) & 0xFFFF;
 #endif
-    LOGV("initializing random seed using %lld", now);
+    ALOGV("initializing random seed using %lld", now);
 }
 
 void BlobCache::set(const void* key, size_t keySize, const void* value,
         size_t valueSize) {
     if (mMaxKeySize < keySize) {
-        LOGV("set: not caching because the key is too large: %d (limit: %d)",
+        ALOGV("set: not caching because the key is too large: %d (limit: %d)",
                 keySize, mMaxKeySize);
         return;
     }
     if (mMaxValueSize < valueSize) {
-        LOGV("set: not caching because the value is too large: %d (limit: %d)",
+        ALOGV("set: not caching because the value is too large: %d (limit: %d)",
                 valueSize, mMaxValueSize);
         return;
     }
     if (mMaxTotalSize < keySize + valueSize) {
-        LOGV("set: not caching because the combined key/value size is too "
+        ALOGV("set: not caching because the combined key/value size is too "
                 "large: %d (limit: %d)", keySize + valueSize, mMaxTotalSize);
         return;
     }
@@ -93,7 +93,7 @@
                     clean();
                     continue;
                 } else {
-                    LOGV("set: not caching new key/value pair because the "
+                    ALOGV("set: not caching new key/value pair because the "
                             "total cache size limit would be exceeded: %d "
                             "(limit: %d)",
                             keySize + valueSize, mMaxTotalSize);
@@ -102,7 +102,7 @@
             }
             mCacheEntries.add(CacheEntry(keyBlob, valueBlob));
             mTotalSize = newTotalSize;
-            LOGV("set: created new cache entry with %d byte key and %d byte value",
+            ALOGV("set: created new cache entry with %d byte key and %d byte value",
                     keySize, valueSize);
         } else {
             // Update the existing cache entry.
@@ -115,7 +115,7 @@
                     clean();
                     continue;
                 } else {
-                    LOGV("set: not caching new value because the total cache "
+                    ALOGV("set: not caching new value because the total cache "
                             "size limit would be exceeded: %d (limit: %d)",
                             keySize + valueSize, mMaxTotalSize);
                     break;
@@ -123,7 +123,7 @@
             }
             mCacheEntries.editItemAt(index).setValue(valueBlob);
             mTotalSize = newTotalSize;
-            LOGV("set: updated existing cache entry with %d byte key and %d byte "
+            ALOGV("set: updated existing cache entry with %d byte key and %d byte "
                     "value", keySize, valueSize);
         }
         break;
@@ -133,7 +133,7 @@
 size_t BlobCache::get(const void* key, size_t keySize, void* value,
         size_t valueSize) {
     if (mMaxKeySize < keySize) {
-        LOGV("get: not searching because the key is too large: %d (limit %d)",
+        ALOGV("get: not searching because the key is too large: %d (limit %d)",
                 keySize, mMaxKeySize);
         return 0;
     }
@@ -141,7 +141,7 @@
     CacheEntry dummyEntry(dummyKey, NULL);
     ssize_t index = mCacheEntries.indexOf(dummyEntry);
     if (index < 0) {
-        LOGV("get: no cache entry found for key of size %d", keySize);
+        ALOGV("get: no cache entry found for key of size %d", keySize);
         return 0;
     }
 
@@ -150,10 +150,10 @@
     sp<Blob> valueBlob(mCacheEntries[index].getValue());
     size_t valueBlobSize = valueBlob->getSize();
     if (valueBlobSize <= valueSize) {
-        LOGV("get: copying %d bytes to caller's buffer", valueBlobSize);
+        ALOGV("get: copying %d bytes to caller's buffer", valueBlobSize);
         memcpy(value, valueBlob->getData(), valueBlobSize);
     } else {
-        LOGV("get: caller's buffer is too small for value: %d (needs %d)",
+        ALOGV("get: caller's buffer is too small for value: %d (needs %d)",
                 valueSize, valueBlobSize);
     }
     return valueBlobSize;
diff --git a/libs/utils/CallStack.cpp b/libs/utils/CallStack.cpp
index 55b6024..c2a5e55 100644
--- a/libs/utils/CallStack.cpp
+++ b/libs/utils/CallStack.cpp
@@ -17,218 +17,33 @@
 #define LOG_TAG "CallStack"
 
 #include <string.h>
-#include <stdlib.h>
-#include <stdio.h>
-
-#if HAVE_DLADDR
-#include <dlfcn.h>
-#endif
-
-#if HAVE_CXXABI
-#include <cxxabi.h>
-#endif
-
-#include <unwind.h>
 
 #include <utils/Log.h>
 #include <utils/Errors.h>
 #include <utils/CallStack.h>
-#include <utils/threads.h>
-
+#include <corkscrew/backtrace.h>
 
 /*****************************************************************************/
 namespace android {
 
-
-typedef struct {
-    size_t count;
-    size_t ignore;
-    const void** addrs;
-} stack_crawl_state_t;
-
-static
-_Unwind_Reason_Code trace_function(_Unwind_Context *context, void *arg)
-{
-    stack_crawl_state_t* state = (stack_crawl_state_t*)arg;
-    if (state->count) {
-        void* ip = (void*)_Unwind_GetIP(context);
-        if (ip) {
-            if (state->ignore) {
-                state->ignore--;
-            } else {
-                state->addrs[0] = ip; 
-                state->addrs++;
-                state->count--;
-            }
-        }
-    }
-    return _URC_NO_REASON;
+CallStack::CallStack() :
+        mCount(0) {
 }
 
-static
-int backtrace(const void** addrs, size_t ignore, size_t size)
-{
-    stack_crawl_state_t state;
-    state.count = size;
-    state.ignore = ignore;
-    state.addrs = addrs;
-    _Unwind_Backtrace(trace_function, (void*)&state);
-    return size - state.count;
-}
-
-/*****************************************************************************/
-
-static 
-const char *lookup_symbol(const void* addr, void **offset, char* name, size_t bufSize)
-{
-#if HAVE_DLADDR
-    Dl_info info;
-    if (dladdr(addr, &info)) {
-        *offset = info.dli_saddr;
-        return info.dli_sname;
-    }
-#endif
-    return NULL;
-}
-
-static 
-int32_t linux_gcc_demangler(const char *mangled_name, char *unmangled_name, size_t buffersize)
-{
-    size_t out_len = 0;
-#if HAVE_CXXABI
-    int status = 0;
-    char *demangled = abi::__cxa_demangle(mangled_name, 0, &out_len, &status);
-    if (status == 0) {
-        // OK
-        if (out_len < buffersize) memcpy(unmangled_name, demangled, out_len);
-        else out_len = 0;
-        free(demangled);
-    } else {
-        out_len = 0;
-    }
-#endif
-    return out_len;
-}
-
-/*****************************************************************************/
-
-class MapInfo {
-    struct mapinfo {
-        struct mapinfo *next;
-        uint64_t start;
-        uint64_t end;
-        char name[];
-    };
-
-    const char *map_to_name(uint64_t pc, const char* def, uint64_t* start) {
-        mapinfo* mi = getMapInfoList();
-        while(mi) {
-            if ((pc >= mi->start) && (pc < mi->end)) {
-                if (start) 
-                    *start = mi->start;
-                return mi->name;
-            }
-            mi = mi->next;
-        }
-        if (start) 
-            *start = 0;
-        return def;
-    }
-
-    mapinfo *parse_maps_line(char *line) {
-        mapinfo *mi;
-        int len = strlen(line);
-        if (len < 1) return 0;
-        line[--len] = 0;
-        if (len < 50) return 0;
-        if (line[20] != 'x') return 0;
-        mi = (mapinfo*)malloc(sizeof(mapinfo) + (len - 47));
-        if (mi == 0) return 0;
-        mi->start = strtoull(line, 0, 16);
-        mi->end = strtoull(line + 9, 0, 16);
-        mi->next = 0;
-        strcpy(mi->name, line + 49);
-        return mi;
-    }
-
-    mapinfo* getMapInfoList() {
-        Mutex::Autolock _l(mLock);
-        if (milist == 0) {
-            char data[1024];
-            FILE *fp;
-            sprintf(data, "/proc/%d/maps", getpid());
-            fp = fopen(data, "r");
-            if (fp) {
-                while(fgets(data, 1024, fp)) {
-                    mapinfo *mi = parse_maps_line(data);
-                    if(mi) {
-                        mi->next = milist;
-                        milist = mi;
-                    }
-                }
-                fclose(fp);
-            }
-        }
-        return milist;
-    }
-    mapinfo*    milist;
-    Mutex       mLock;
-    static MapInfo sMapInfo;
-
-public:
-    MapInfo()
-     : milist(0) {
-    }
-
-    ~MapInfo() {
-        while (milist) {
-            mapinfo *next = milist->next;
-            free(milist);
-            milist = next;
-        }
-    }
-    
-    static const char *mapAddressToName(const void* pc, const char* def,
-            void const** start) 
-    {
-        uint64_t s;
-        char const* name = sMapInfo.map_to_name(uint64_t(uintptr_t(pc)), def, &s);
-        if (start) {
-            *start = (void*)s;
-        }
-        return name;
-    }
-
-};
-
-/*****************************************************************************/
-
-MapInfo MapInfo::sMapInfo;
-
-/*****************************************************************************/
-
-CallStack::CallStack()
-    : mCount(0)
-{
-}
-
-CallStack::CallStack(const CallStack& rhs)
-    : mCount(rhs.mCount)
-{
+CallStack::CallStack(const CallStack& rhs) :
+        mCount(rhs.mCount) {
     if (mCount) {
-        memcpy(mStack, rhs.mStack, mCount*sizeof(void*));
+        memcpy(mStack, rhs.mStack, mCount * sizeof(backtrace_frame_t));
     }
 }
 
-CallStack::~CallStack()
-{
+CallStack::~CallStack() {
 }
 
-CallStack& CallStack::operator = (const CallStack& rhs)
-{
+CallStack& CallStack::operator = (const CallStack& rhs) {
     mCount = rhs.mCount;
     if (mCount) {
-        memcpy(mStack, rhs.mStack, mCount*sizeof(void*));
+        memcpy(mStack, rhs.mStack, mCount * sizeof(backtrace_frame_t));
     }
     return *this;
 }
@@ -236,7 +51,7 @@
 bool CallStack::operator == (const CallStack& rhs) const {
     if (mCount != rhs.mCount)
         return false;
-    return !mCount || (memcmp(mStack, rhs.mStack, mCount*sizeof(void*)) == 0);
+    return !mCount || memcmp(mStack, rhs.mStack, mCount * sizeof(backtrace_frame_t)) == 0;
 }
 
 bool CallStack::operator != (const CallStack& rhs) const {
@@ -246,7 +61,7 @@
 bool CallStack::operator < (const CallStack& rhs) const {
     if (mCount != rhs.mCount)
         return mCount < rhs.mCount;
-    return memcmp(mStack, rhs.mStack, mCount*sizeof(void*)) < 0;
+    return memcmp(mStack, rhs.mStack, mCount * sizeof(backtrace_frame_t)) < 0;
 }
 
 bool CallStack::operator >= (const CallStack& rhs) const {
@@ -256,7 +71,7 @@
 bool CallStack::operator > (const CallStack& rhs) const {
     if (mCount != rhs.mCount)
         return mCount > rhs.mCount;
-    return memcmp(mStack, rhs.mStack, mCount*sizeof(void*)) > 0;
+    return memcmp(mStack, rhs.mStack, mCount * sizeof(backtrace_frame_t)) > 0;
 }
 
 bool CallStack::operator <= (const CallStack& rhs) const {
@@ -266,84 +81,49 @@
 const void* CallStack::operator [] (int index) const {
     if (index >= int(mCount))
         return 0;
-    return mStack[index];
+    return reinterpret_cast<const void*>(mStack[index].absolute_pc);
 }
 
-
-void CallStack::clear()
-{
+void CallStack::clear() {
     mCount = 0;
 }
 
-void CallStack::update(int32_t ignoreDepth, int32_t maxDepth)
-{
-    if (maxDepth > MAX_DEPTH)
+void CallStack::update(int32_t ignoreDepth, int32_t maxDepth) {
+    if (maxDepth > MAX_DEPTH) {
         maxDepth = MAX_DEPTH;
-    mCount = backtrace(mStack, ignoreDepth, maxDepth);
-}
-
-// Return the stack frame name on the designated level
-String8 CallStack::toStringSingleLevel(const char* prefix, int32_t level) const
-{
-    String8 res;
-    char namebuf[1024];
-    char tmp[256];
-    char tmp1[32];
-    char tmp2[32];
-    void *offs;
-
-    const void* ip = mStack[level];
-    if (!ip) return res;
-
-    if (prefix) res.append(prefix);
-    snprintf(tmp1, 32, "#%02d  ", level);
-    res.append(tmp1);
-
-    const char* name = lookup_symbol(ip, &offs, namebuf, sizeof(namebuf));
-    if (name) {
-        if (linux_gcc_demangler(name, tmp, 256) != 0)
-            name = tmp;
-        snprintf(tmp1, 32, "0x%p: <", ip);
-        snprintf(tmp2, 32, ">+0x%p", offs);
-        res.append(tmp1);
-        res.append(name);
-        res.append(tmp2);
-    } else { 
-        void const* start = 0;
-        name = MapInfo::mapAddressToName(ip, "<unknown>", &start);
-        snprintf(tmp, 256, "pc %08lx  %s", 
-                long(uintptr_t(ip)-uintptr_t(start)), name);
-        res.append(tmp);
     }
-    res.append("\n");
-
-    return res;
+    ssize_t count = unwind_backtrace(mStack, ignoreDepth + 1, maxDepth);
+    mCount = count > 0 ? count : 0;
 }
 
-// Dump a stack trace to the log
-void CallStack::dump(const char* prefix) const
-{
-    /* 
-     * Sending a single long log may be truncated since the stack levels can
-     * get very deep. So we request function names of each frame individually.
-     */
-    for (int i=0; i<int(mCount); i++) {
-        LOGD("%s", toStringSingleLevel(prefix, i).string());
+void CallStack::dump(const char* prefix) const {
+    backtrace_symbol_t symbols[mCount];
+
+    get_backtrace_symbols(mStack, mCount, symbols);
+    for (size_t i = 0; i < mCount; i++) {
+        char line[MAX_BACKTRACE_LINE_LENGTH];
+        format_backtrace_line(i, &mStack[i], &symbols[i],
+                line, MAX_BACKTRACE_LINE_LENGTH);
+        LOGD("%s%s", prefix, line);
     }
+    free_backtrace_symbols(symbols, mCount);
 }
 
-// Return a string (possibly very long) containing the complete stack trace
-String8 CallStack::toString(const char* prefix) const
-{
-    String8 res;
+String8 CallStack::toString(const char* prefix) const {
+    String8 str;
+    backtrace_symbol_t symbols[mCount];
 
-    for (int i=0; i<int(mCount); i++) {
-        res.append(toStringSingleLevel(prefix, i).string());
+    get_backtrace_symbols(mStack, mCount, symbols);
+    for (size_t i = 0; i < mCount; i++) {
+        char line[MAX_BACKTRACE_LINE_LENGTH];
+        format_backtrace_line(i, &mStack[i], &symbols[i],
+                line, MAX_BACKTRACE_LINE_LENGTH);
+        str.append(prefix);
+        str.append(line);
+        str.append("\n");
     }
-
-    return res;
+    free_backtrace_symbols(symbols, mCount);
+    return str;
 }
 
-/*****************************************************************************/
-
 }; // namespace android
diff --git a/libs/utils/FileMap.cpp b/libs/utils/FileMap.cpp
index c220a90..294f7b6 100644
--- a/libs/utils/FileMap.cpp
+++ b/libs/utils/FileMap.cpp
@@ -190,7 +190,7 @@
 
     assert(mBasePtr != NULL);
 
-    LOGV("MAP: base %p/%d data %p/%d\n",
+    ALOGV("MAP: base %p/%d data %p/%d\n",
         mBasePtr, (int) mBaseLength, mDataPtr, (int) mDataLength);
 
     return true;
diff --git a/libs/utils/RefBase.cpp b/libs/utils/RefBase.cpp
index 37d061c..959b382 100644
--- a/libs/utils/RefBase.cpp
+++ b/libs/utils/RefBase.cpp
@@ -421,7 +421,7 @@
             // destroy the object now.
             delete impl->mBase;
         } else {
-            // LOGV("Freeing refs %p of old RefBase %p\n", this, impl->mBase);
+            // ALOGV("Freeing refs %p of old RefBase %p\n", this, impl->mBase);
             delete impl;
         }
     } else {
diff --git a/libs/utils/ResourceTypes.cpp b/libs/utils/ResourceTypes.cpp
index 6cf01c8..6a9e91d 100644
--- a/libs/utils/ResourceTypes.cpp
+++ b/libs/utils/ResourceTypes.cpp
@@ -69,7 +69,7 @@
 
 static void printToLogFunc(void* cookie, const char* txt)
 {
-    LOGV("%s", txt);
+    ALOGV("%s", txt);
 }
 
 // Standard C isspace() is only required to look at the low byte of its input, so
@@ -1867,7 +1867,7 @@
     const bool notDeviceEndian = htods(0xf0) != 0xf0;
 
     LOAD_TABLE_NOISY(
-        LOGV("Adding resources to ResTable: data=%p, size=0x%x, cookie=%p, asset=%p, copy=%d "
+        ALOGV("Adding resources to ResTable: data=%p, size=0x%x, cookie=%p, asset=%p, copy=%d "
              "idmap=%p\n", data, size, cookie, asset, copyData, idmap));
     
     if (copyData || notDeviceEndian) {
@@ -2122,7 +2122,7 @@
                                           resID, &overlayResID);
             if (retval == NO_ERROR && overlayResID != 0x0) {
                 // for this loop iteration, this is the type and entry we really want
-                LOGV("resource map 0x%08x -> 0x%08x\n", resID, overlayResID);
+                ALOGV("resource map 0x%08x -> 0x%08x\n", resID, overlayResID);
                 T = Res_GETTYPE(overlayResID);
                 E = Res_GETENTRY(overlayResID);
             } else {
@@ -2401,7 +2401,7 @@
                                           resID, &overlayResID);
             if (retval == NO_ERROR && overlayResID != 0x0) {
                 // for this loop iteration, this is the type and entry we really want
-                LOGV("resource map 0x%08x -> 0x%08x\n", resID, overlayResID);
+                ALOGV("resource map 0x%08x -> 0x%08x\n", resID, overlayResID);
                 T = Res_GETTYPE(overlayResID);
                 E = Res_GETENTRY(overlayResID);
             } else {
@@ -2413,9 +2413,9 @@
         const ResTable_type* type;
         const ResTable_entry* entry;
         const Type* typeClass;
-        LOGV("Getting entry pkg=%p, t=%d, e=%d\n", package, T, E);
+        ALOGV("Getting entry pkg=%p, t=%d, e=%d\n", package, T, E);
         ssize_t offset = getEntry(package, T, E, &mParams, &type, &entry, &typeClass);
-        LOGV("Resulting offset=%d\n", offset);
+        ALOGV("Resulting offset=%d\n", offset);
         if (offset <= 0) {
             // No {entry, appropriate config} pair found in package. If this
             // package is an overlay package (ip != 0), this simply means the
@@ -3898,9 +3898,9 @@
 void ResTable::getLocales(Vector<String8>* locales) const
 {
     Vector<ResTable_config> configs;
-    LOGV("calling getConfigurations");
+    ALOGV("calling getConfigurations");
     getConfigurations(&configs);
-    LOGV("called getConfigurations size=%d", (int)configs.size());
+    ALOGV("called getConfigurations size=%d", (int)configs.size());
     const size_t I = configs.size();
     for (size_t i=0; i<I; i++) {
         char locale[6];
@@ -3924,13 +3924,13 @@
     const ResTable_type** outType, const ResTable_entry** outEntry,
     const Type** outTypeClass) const
 {
-    LOGV("Getting entry from package %p\n", package);
+    ALOGV("Getting entry from package %p\n", package);
     const ResTable_package* const pkg = package->package;
 
     const Type* allTypes = package->getType(typeIndex);
-    LOGV("allTypes=%p\n", allTypes);
+    ALOGV("allTypes=%p\n", allTypes);
     if (allTypes == NULL) {
-        LOGV("Skipping entry type index 0x%02x because type is NULL!\n", typeIndex);
+        ALOGV("Skipping entry type index 0x%02x because type is NULL!\n", typeIndex);
         return 0;
     }
 
diff --git a/libs/utils/StreamingZipInflater.cpp b/libs/utils/StreamingZipInflater.cpp
index 00498bd..59a46f9 100644
--- a/libs/utils/StreamingZipInflater.cpp
+++ b/libs/utils/StreamingZipInflater.cpp
@@ -77,7 +77,7 @@
 }
 
 void StreamingZipInflater::initInflateState() {
-    LOGV("Initializing inflate state");
+    ALOGV("Initializing inflate state");
 
     memset(&mInflateState, 0, sizeof(mInflateState));
     mInflateState.zalloc = Z_NULL;
@@ -152,13 +152,13 @@
             mInflateState.avail_out = mOutBufSize;
 
             /*
-            LOGV("Inflating to outbuf: avail_in=%u avail_out=%u next_in=%p next_out=%p",
+            ALOGV("Inflating to outbuf: avail_in=%u avail_out=%u next_in=%p next_out=%p",
                     mInflateState.avail_in, mInflateState.avail_out,
                     mInflateState.next_in, mInflateState.next_out);
             */
             int result = Z_OK;
             if (mStreamNeedsInit) {
-                LOGV("Initializing zlib to inflate");
+                ALOGV("Initializing zlib to inflate");
                 result = inflateInit2(&mInflateState, -MAX_WBITS);
                 mStreamNeedsInit = false;
             }
@@ -192,7 +192,7 @@
         size_t toRead = min_of(mInBufSize, mInTotalSize - mInNextChunkOffset);
         if (toRead > 0) {
             ssize_t didRead = ::read(mFd, mInBuf, toRead);
-            //LOGV("Reading input chunk, size %08x didread %08x", toRead, didRead);
+            //ALOGV("Reading input chunk, size %08x didread %08x", toRead, didRead);
             if (didRead < 0) {
                 // TODO: error
                 LOGE("Error reading asset data");
diff --git a/libs/utils/Threads.cpp b/libs/utils/Threads.cpp
index 5dbcb75..fe4b8e6 100644
--- a/libs/utils/Threads.cpp
+++ b/libs/utils/Threads.cpp
@@ -205,7 +205,7 @@
 
     delete pDetails;
 
-    LOG(LOG_VERBOSE, "thread", "thread exiting\n");
+    ALOG(LOG_VERBOSE, "thread", "thread exiting\n");
     return (unsigned int) result;
 }
 
@@ -232,7 +232,7 @@
     if (hThread == NULL)
 #endif
     {
-        LOG(LOG_WARN, "thread", "WARNING: thread create failed\n");
+        ALOG(LOG_WARN, "thread", "WARNING: thread create failed\n");
         return false;
     }
 
@@ -470,7 +470,7 @@
 void Mutex::unlock()
 {
     if (!ReleaseMutex((HANDLE) mState))
-        LOG(LOG_WARN, "thread", "WARNING: bad result from unlocking mutex\n");
+        ALOG(LOG_WARN, "thread", "WARNING: bad result from unlocking mutex\n");
 }
 
 status_t Mutex::tryLock()
@@ -479,7 +479,7 @@
 
     dwWaitResult = WaitForSingleObject((HANDLE) mState, 0);
     if (dwWaitResult != WAIT_OBJECT_0 && dwWaitResult != WAIT_TIMEOUT)
-        LOG(LOG_WARN, "thread", "WARNING: bad result from try-locking mutex\n");
+        ALOG(LOG_WARN, "thread", "WARNING: bad result from try-locking mutex\n");
     return (dwWaitResult == WAIT_OBJECT_0) ? 0 : -1;
 }
 
diff --git a/libs/utils/Timers.cpp b/libs/utils/Timers.cpp
index 64a29f5..64b4701 100644
--- a/libs/utils/Timers.cpp
+++ b/libs/utils/Timers.cpp
@@ -113,7 +113,7 @@
 /*static*/ void DurationTimer::addToTimeval(struct timeval* ptv, long usec)
 {
     if (usec < 0) {
-        LOG(LOG_WARN, "", "Negative values not supported in addToTimeval\n");
+        ALOG(LOG_WARN, "", "Negative values not supported in addToTimeval\n");
         return;
     }
 
diff --git a/libs/utils/VectorImpl.cpp b/libs/utils/VectorImpl.cpp
index bfb37a6..4a90296 100644
--- a/libs/utils/VectorImpl.cpp
+++ b/libs/utils/VectorImpl.cpp
@@ -346,7 +346,7 @@
 
 void* VectorImpl::_grow(size_t where, size_t amount)
 {
-//    LOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
+//    ALOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
 //        this, (int)where, (int)amount, (int)mCount, (int)capacity());
 
     LOG_ASSERT(where <= mCount,
@@ -356,7 +356,7 @@
     const size_t new_size = mCount + amount;
     if (capacity() < new_size) {
         const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2);
-//        LOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
+//        ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
         if ((mStorage) &&
             (mCount==where) &&
             (mFlags & HAS_TRIVIAL_COPY) &&
@@ -399,7 +399,7 @@
     if (!mStorage)
         return;
 
-//    LOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
+//    ALOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
 //        this, (int)where, (int)amount, (int)mCount, (int)capacity());
 
     LOG_ASSERT(where + amount <= mCount,
@@ -409,7 +409,7 @@
     const size_t new_size = mCount - amount;
     if (new_size*3 < capacity()) {
         const size_t new_capacity = max(kMinVectorCapacity, new_size*2);
-//        LOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
+//        ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
         if ((where == new_size) &&
             (mFlags & HAS_TRIVIAL_COPY) &&
             (mFlags & HAS_TRIVIAL_DTOR))
diff --git a/libs/utils/ZipFileRO.cpp b/libs/utils/ZipFileRO.cpp
index b18c383..d880f55 100644
--- a/libs/utils/ZipFileRO.cpp
+++ b/libs/utils/ZipFileRO.cpp
@@ -222,7 +222,7 @@
             free(scanBuf);
             return false;
         } else if (header != kLFHSignature) {
-            LOGV("Not a Zip archive (found 0x%08x)\n", header);
+            ALOGV("Not a Zip archive (found 0x%08x)\n", header);
             free(scanBuf);
             return false;
         }
@@ -264,7 +264,7 @@
     int i;
     for (i = readAmount - kEOCDLen; i >= 0; i--) {
         if (scanBuf[i] == 0x50 && get4LE(&scanBuf[i]) == kEOCDSignature) {
-            LOGV("+++ Found EOCD at buf+%d\n", i);
+            ALOGV("+++ Found EOCD at buf+%d\n", i);
             break;
         }
     }
@@ -299,7 +299,7 @@
         return false;
     }
 
-    LOGV("+++ numEntries=%d dirSize=%d dirOffset=%d\n",
+    ALOGV("+++ numEntries=%d dirSize=%d dirOffset=%d\n",
         numEntries, dirSize, dirOffset);
 
     mDirectoryMap = new FileMap();
@@ -372,7 +372,7 @@
             goto bail;
         }
     }
-    LOGV("+++ zip good scan %d entries\n", numEntries);
+    ALOGV("+++ zip good scan %d entries\n", numEntries);
     result = true;
 
 bail:
diff --git a/libs/utils/ZipUtils.cpp b/libs/utils/ZipUtils.cpp
index 9138878..76725b4 100644
--- a/libs/utils/ZipUtils.cpp
+++ b/libs/utils/ZipUtils.cpp
@@ -95,7 +95,7 @@
         if (zstream.avail_in == 0) {
             getSize = (compRemaining > kReadBufSize) ?
                         kReadBufSize : compRemaining;
-            LOGV("+++ reading %ld bytes (%ld left)\n",
+            ALOGV("+++ reading %ld bytes (%ld left)\n",
                 getSize, compRemaining);
 
             int cc = read(fd, readBuf, getSize);
@@ -207,7 +207,7 @@
         if (zstream.avail_in == 0) {
             getSize = (compRemaining > kReadBufSize) ?
                         kReadBufSize : compRemaining;
-            LOGV("+++ reading %ld bytes (%ld left)\n",
+            ALOGV("+++ reading %ld bytes (%ld left)\n",
                 getSize, compRemaining);
 
             int cc = fread(readBuf, 1, getSize, fp);
diff --git a/libs/utils/primes.py b/libs/utils/primes.py
new file mode 100755
index 0000000..e161dd8
--- /dev/null
+++ b/libs/utils/primes.py
@@ -0,0 +1,47 @@
+#!/usr/bin/env python2.6
+#
+# 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.
+#
+
+#
+# Generates a table of prime numbers for use in BasicHashtable.cpp.
+#
+# Each prime is chosen such that it is a little more than twice as large as
+# the previous prime in the table.  This makes it easier to choose a new
+# hashtable size when the underlying array is grown by as nominal factor
+# of two each time.
+#
+
+def is_odd_prime(n):
+  limit = (n - 1) / 2
+  d = 3
+  while d <= limit:
+    if n % d == 0:
+      return False
+    d += 2
+  return True
+
+print "static size_t PRIMES[] = {"
+
+n = 5
+max = 2**31 - 1
+while n < max:
+  print "    %d," % (n)
+  n = n * 2 + 1
+  while not is_odd_prime(n):
+    n += 2
+
+print "    0,"
+print "};"
diff --git a/libs/utils/tests/Android.mk b/libs/utils/tests/Android.mk
index b97f52f..58230f4 100644
--- a/libs/utils/tests/Android.mk
+++ b/libs/utils/tests/Android.mk
@@ -4,9 +4,10 @@
 
 # Build the unit tests.
 test_src_files := \
+	BasicHashtable_test.cpp \
 	BlobCache_test.cpp \
-	ObbFile_test.cpp \
 	Looper_test.cpp \
+	ObbFile_test.cpp \
 	String8_test.cpp \
 	Unicode_test.cpp \
 	ZipFileRO_test.cpp \
diff --git a/libs/utils/tests/BasicHashtable_test.cpp b/libs/utils/tests/BasicHashtable_test.cpp
new file mode 100644
index 0000000..764082d
--- /dev/null
+++ b/libs/utils/tests/BasicHashtable_test.cpp
@@ -0,0 +1,577 @@
+/*
+ * 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.
+ */
+
+#define LOG_TAG "BasicHashtable_test"
+
+#include <utils/BasicHashtable.h>
+#include <cutils/log.h>
+#include <gtest/gtest.h>
+#include <unistd.h>
+
+namespace android {
+
+typedef int SimpleKey;
+typedef int SimpleValue;
+typedef key_value_pair_t<SimpleKey, SimpleValue> SimpleEntry;
+typedef BasicHashtable<SimpleKey, SimpleEntry> SimpleHashtable;
+
+struct ComplexKey {
+    int k;
+
+    explicit ComplexKey(int k) : k(k) {
+        instanceCount += 1;
+    }
+
+    ComplexKey(const ComplexKey& other) : k(other.k) {
+        instanceCount += 1;
+    }
+
+    ~ComplexKey() {
+        instanceCount -= 1;
+    }
+
+    bool operator ==(const ComplexKey& other) const {
+        return k == other.k;
+    }
+
+    bool operator !=(const ComplexKey& other) const {
+        return k != other.k;
+    }
+
+    static ssize_t instanceCount;
+};
+
+ssize_t ComplexKey::instanceCount = 0;
+
+template<> inline hash_t hash_type(const ComplexKey& value) {
+    return hash_type(value.k);
+}
+
+struct ComplexValue {
+    int v;
+
+    explicit ComplexValue(int v) : v(v) {
+        instanceCount += 1;
+    }
+
+    ComplexValue(const ComplexValue& other) : v(other.v) {
+        instanceCount += 1;
+    }
+
+    ~ComplexValue() {
+        instanceCount -= 1;
+    }
+
+    static ssize_t instanceCount;
+};
+
+ssize_t ComplexValue::instanceCount = 0;
+
+typedef key_value_pair_t<ComplexKey, ComplexValue> ComplexEntry;
+typedef BasicHashtable<ComplexKey, ComplexEntry> ComplexHashtable;
+
+class BasicHashtableTest : public testing::Test {
+protected:
+    virtual void SetUp() {
+        ComplexKey::instanceCount = 0;
+        ComplexValue::instanceCount = 0;
+    }
+
+    virtual void TearDown() {
+        ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+    }
+
+    void assertInstanceCount(ssize_t keys, ssize_t values) {
+        if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) {
+            FAIL() << "Expected " << keys << " keys and " << values << " values "
+                    "but there were actually " << ComplexKey::instanceCount << " keys and "
+                    << ComplexValue::instanceCount << " values";
+        }
+    }
+
+public:
+    template <typename TKey, typename TEntry>
+    static void cookieAt(const BasicHashtable<TKey, TEntry>& h, size_t index,
+            bool* collision, bool* present, hash_t* hash) {
+        uint32_t cookie = h.cookieAt(index);
+        *collision = cookie & BasicHashtable<TKey, TEntry>::Bucket::COLLISION;
+        *present = cookie & BasicHashtable<TKey, TEntry>::Bucket::PRESENT;
+        *hash = cookie & BasicHashtable<TKey, TEntry>::Bucket::HASH_MASK;
+    }
+
+    template <typename TKey, typename TEntry>
+    static const void* getBuckets(const BasicHashtable<TKey, TEntry>& h) {
+        return h.mBuckets;
+    }
+};
+
+template <typename TKey, typename TValue>
+static size_t add(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h,
+        const TKey& key, const TValue& value) {
+    return h.add(hash_type(key), key_value_pair_t<TKey, TValue>(key, value));
+}
+
+template <typename TKey, typename TValue>
+static ssize_t find(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h,
+        ssize_t index, const TKey& key) {
+    return h.find(index, hash_type(key), key);
+}
+
+template <typename TKey, typename TValue>
+static bool remove(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h,
+        const TKey& key) {
+    ssize_t index = find(h, -1, key);
+    if (index >= 0) {
+        h.removeAt(index);
+        return true;
+    }
+    return false;
+}
+
+template <typename TEntry>
+static void getKeyValue(const TEntry& entry, int* key, int* value);
+
+template <> void getKeyValue(const SimpleEntry& entry, int* key, int* value) {
+    *key = entry.key;
+    *value = entry.value;
+}
+
+template <> void getKeyValue(const ComplexEntry& entry, int* key, int* value) {
+    *key = entry.key.k;
+    *value = entry.value.v;
+}
+
+template <typename TKey, typename TValue>
+static void dump(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h) {
+    LOGD("hashtable %p, size=%u, capacity=%u, bucketCount=%u",
+            &h, h.size(), h.capacity(), h.bucketCount());
+    for (size_t i = 0; i < h.bucketCount(); i++) {
+        bool collision, present;
+        hash_t hash;
+        BasicHashtableTest::cookieAt(h, i, &collision, &present, &hash);
+        if (present) {
+            int key, value;
+            getKeyValue(h.entryAt(i), &key, &value);
+            LOGD("  [%3u] = collision=%d, present=%d, hash=0x%08x, key=%3d, value=%3d, "
+                    "hash_type(key)=0x%08x",
+                    i, collision, present, hash, key, value, hash_type(key));
+        } else {
+            LOGD("  [%3u] = collision=%d, present=%d",
+                    i, collision, present);
+        }
+    }
+}
+
+TEST_F(BasicHashtableTest, DefaultConstructor_WithDefaultProperties) {
+    SimpleHashtable h;
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(3U, h.capacity());
+    EXPECT_EQ(5U, h.bucketCount());
+    EXPECT_EQ(0.75f, h.loadFactor());
+}
+
+TEST_F(BasicHashtableTest, Constructor_WithNonUnityLoadFactor) {
+    SimpleHashtable h(52, 0.8f);
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(77U, h.capacity());
+    EXPECT_EQ(97U, h.bucketCount());
+    EXPECT_EQ(0.8f, h.loadFactor());
+}
+
+TEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndExactCapacity) {
+    SimpleHashtable h(46, 1.0f);
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f
+    EXPECT_EQ(47U, h.bucketCount());
+    EXPECT_EQ(1.0f, h.loadFactor());
+}
+
+TEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndInexactCapacity) {
+    SimpleHashtable h(42, 1.0f);
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f
+    EXPECT_EQ(47U, h.bucketCount());
+    EXPECT_EQ(1.0f, h.loadFactor());
+}
+
+TEST_F(BasicHashtableTest, FindAddFindRemoveFind_OneEntry) {
+    SimpleHashtable h;
+    ssize_t index = find(h, -1, 8);
+    ASSERT_EQ(-1, index);
+
+    index = add(h, 8, 1);
+    ASSERT_EQ(1U, h.size());
+
+    ASSERT_EQ(index, find(h, -1, 8));
+    ASSERT_EQ(8, h.entryAt(index).key);
+    ASSERT_EQ(1, h.entryAt(index).value);
+
+    index = find(h, index, 8);
+    ASSERT_EQ(-1, index);
+
+    ASSERT_TRUE(remove(h, 8));
+    ASSERT_EQ(0U, h.size());
+
+    index = find(h, -1, 8);
+    ASSERT_EQ(-1, index);
+}
+
+TEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithUniqueKey) {
+    const size_t N = 11;
+
+    SimpleHashtable h;
+    for (size_t i = 0; i < N; i++) {
+        ssize_t index = find(h, -1, int(i));
+        ASSERT_EQ(-1, index);
+
+        index = add(h, int(i), int(i * 10));
+        ASSERT_EQ(i + 1, h.size());
+
+        ASSERT_EQ(index, find(h, -1, int(i)));
+        ASSERT_EQ(int(i), h.entryAt(index).key);
+        ASSERT_EQ(int(i * 10), h.entryAt(index).value);
+
+        index = find(h, index, int(i));
+        ASSERT_EQ(-1, index);
+    }
+
+    for (size_t i = N; --i > 0; ) {
+        ASSERT_TRUE(remove(h, int(i))) << "i = " << i;
+        ASSERT_EQ(i, h.size());
+
+        ssize_t index = find(h, -1, int(i));
+        ASSERT_EQ(-1, index);
+    }
+}
+
+TEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithDuplicateKey) {
+    const size_t N = 11;
+    const int K = 1;
+
+    SimpleHashtable h;
+    for (size_t i = 0; i < N; i++) {
+        ssize_t index = find(h, -1, K);
+        if (i == 0) {
+            ASSERT_EQ(-1, index);
+        } else {
+            ASSERT_NE(-1, index);
+        }
+
+        add(h, K, int(i));
+        ASSERT_EQ(i + 1, h.size());
+
+        index = -1;
+        int values = 0;
+        for (size_t j = 0; j <= i; j++) {
+            index = find(h, index, K);
+            ASSERT_GE(index, 0);
+            ASSERT_EQ(K, h.entryAt(index).key);
+            values |= 1 << h.entryAt(index).value;
+        }
+        ASSERT_EQ(values, (1 << (i + 1)) - 1);
+
+        index = find(h, index, K);
+        ASSERT_EQ(-1, index);
+    }
+
+    for (size_t i = N; --i > 0; ) {
+        ASSERT_TRUE(remove(h, K)) << "i = " << i;
+        ASSERT_EQ(i, h.size());
+
+        ssize_t index = -1;
+        for (size_t j = 0; j < i; j++) {
+            index = find(h, index, K);
+            ASSERT_GE(index, 0);
+            ASSERT_EQ(K, h.entryAt(index).key);
+        }
+
+        index = find(h, index, K);
+        ASSERT_EQ(-1, index);
+    }
+}
+
+TEST_F(BasicHashtableTest, Clear_WhenAlreadyEmpty_DoesNothing) {
+    SimpleHashtable h;
+    h.clear();
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(3U, h.capacity());
+    EXPECT_EQ(5U, h.bucketCount());
+    EXPECT_EQ(0.75f, h.loadFactor());
+}
+
+TEST_F(BasicHashtableTest, Clear_AfterElementsAdded_RemovesThem) {
+    SimpleHashtable h;
+    add(h, 0, 0);
+    add(h, 1, 0);
+    h.clear();
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(3U, h.capacity());
+    EXPECT_EQ(5U, h.bucketCount());
+    EXPECT_EQ(0.75f, h.loadFactor());
+}
+
+TEST_F(BasicHashtableTest, Clear_AfterElementsAdded_DestroysThem) {
+    ComplexHashtable h;
+    add(h, ComplexKey(0), ComplexValue(0));
+    add(h, ComplexKey(1), ComplexValue(0));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+
+    h.clear();
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(3U, h.capacity());
+    EXPECT_EQ(5U, h.bucketCount());
+    EXPECT_EQ(0.75f, h.loadFactor());
+}
+
+TEST_F(BasicHashtableTest, Remove_AfterElementsAdded_DestroysThem) {
+    ComplexHashtable h;
+    add(h, ComplexKey(0), ComplexValue(0));
+    add(h, ComplexKey(1), ComplexValue(0));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+
+    ASSERT_TRUE(remove(h, ComplexKey(0)));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1));
+
+    ASSERT_TRUE(remove(h, ComplexKey(1)));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(3U, h.capacity());
+    EXPECT_EQ(5U, h.bucketCount());
+    EXPECT_EQ(0.75f, h.loadFactor());
+}
+
+TEST_F(BasicHashtableTest, Destructor_AfterElementsAdded_DestroysThem) {
+    {
+        ComplexHashtable h;
+        add(h, ComplexKey(0), ComplexValue(0));
+        add(h, ComplexKey(1), ComplexValue(0));
+        ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+    } // h is destroyed here
+
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+}
+
+TEST_F(BasicHashtableTest, Next_WhenEmpty_ReturnsMinusOne) {
+    SimpleHashtable h;
+
+    ASSERT_EQ(-1, h.next(-1));
+}
+
+TEST_F(BasicHashtableTest, Next_WhenNonEmpty_IteratesOverAllEntries) {
+    const int N = 88;
+
+    SimpleHashtable h;
+    for (int i = 0; i < N; i++) {
+        add(h, i, i * 10);
+    }
+
+    bool set[N];
+    memset(set, 0, sizeof(bool) * N);
+    int count = 0;
+    for (ssize_t index = -1; (index = h.next(index)) != -1; ) {
+        ASSERT_GE(index, 0);
+        ASSERT_LT(size_t(index), h.bucketCount());
+
+        const SimpleEntry& entry = h.entryAt(index);
+        ASSERT_GE(entry.key, 0);
+        ASSERT_LT(entry.key, N);
+        ASSERT_EQ(false, set[entry.key]);
+        ASSERT_EQ(entry.key * 10, entry.value);
+
+        set[entry.key] = true;
+        count += 1;
+    }
+    ASSERT_EQ(N, count);
+}
+
+TEST_F(BasicHashtableTest, Add_RehashesOnDemand) {
+    SimpleHashtable h;
+    size_t initialCapacity = h.capacity();
+    size_t initialBucketCount = h.bucketCount();
+
+    for (size_t i = 0; i < initialCapacity; i++) {
+        add(h, int(i), 0);
+    }
+
+    EXPECT_EQ(initialCapacity, h.size());
+    EXPECT_EQ(initialCapacity, h.capacity());
+    EXPECT_EQ(initialBucketCount, h.bucketCount());
+
+    add(h, -1, -1);
+
+    EXPECT_EQ(initialCapacity + 1, h.size());
+    EXPECT_GT(h.capacity(), initialCapacity);
+    EXPECT_GT(h.bucketCount(), initialBucketCount);
+    EXPECT_GT(h.bucketCount(), h.capacity());
+}
+
+TEST_F(BasicHashtableTest, Rehash_WhenCapacityAndBucketCountUnchanged_DoesNothing) {
+    ComplexHashtable h;
+    add(h, ComplexKey(0), ComplexValue(0));
+    const void* oldBuckets = getBuckets(h);
+    ASSERT_NE((void*)NULL, oldBuckets);
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1));
+
+    h.rehash(h.capacity(), h.loadFactor());
+
+    ASSERT_EQ(oldBuckets, getBuckets(h));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1));
+}
+
+TEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasNoBuckets_ButDoesNotAllocateBuckets) {
+    ComplexHashtable h;
+    ASSERT_EQ((void*)NULL, getBuckets(h));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+
+    h.rehash(9, 1.0f);
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(10U, h.capacity());
+    EXPECT_EQ(11U, h.bucketCount());
+    EXPECT_EQ(1.0f, h.loadFactor());
+    EXPECT_EQ((void*)NULL, getBuckets(h));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+}
+
+TEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasBuckets_ReleasesBucketsAndSetsCapacity) {
+    ComplexHashtable h(10);
+    add(h, ComplexKey(0), ComplexValue(0));
+    ASSERT_TRUE(remove(h, ComplexKey(0)));
+    ASSERT_NE((void*)NULL, getBuckets(h));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+
+    h.rehash(0, 0.75f);
+
+    EXPECT_EQ(0U, h.size());
+    EXPECT_EQ(3U, h.capacity());
+    EXPECT_EQ(5U, h.bucketCount());
+    EXPECT_EQ(0.75f, h.loadFactor());
+    EXPECT_EQ((void*)NULL, getBuckets(h));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+}
+
+TEST_F(BasicHashtableTest, Rehash_WhenLessThanCurrentCapacity_ShrinksBuckets) {
+    ComplexHashtable h(10);
+    add(h, ComplexKey(0), ComplexValue(0));
+    add(h, ComplexKey(1), ComplexValue(1));
+    const void* oldBuckets = getBuckets(h);
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+
+    h.rehash(0, 0.75f);
+
+    EXPECT_EQ(2U, h.size());
+    EXPECT_EQ(3U, h.capacity());
+    EXPECT_EQ(5U, h.bucketCount());
+    EXPECT_EQ(0.75f, h.loadFactor());
+    EXPECT_NE(oldBuckets, getBuckets(h));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+}
+
+TEST_F(BasicHashtableTest, CopyOnWrite) {
+    ComplexHashtable h1;
+    add(h1, ComplexKey(0), ComplexValue(0));
+    add(h1, ComplexKey(1), ComplexValue(1));
+    const void* originalBuckets = getBuckets(h1);
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+    ssize_t index0 = find(h1, -1, ComplexKey(0));
+    EXPECT_GE(index0, 0);
+
+    // copy constructor acquires shared reference
+    ComplexHashtable h2(h1);
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+    ASSERT_EQ(originalBuckets, getBuckets(h2));
+    EXPECT_EQ(h1.size(), h2.size());
+    EXPECT_EQ(h1.capacity(), h2.capacity());
+    EXPECT_EQ(h1.bucketCount(), h2.bucketCount());
+    EXPECT_EQ(h1.loadFactor(), h2.loadFactor());
+    EXPECT_EQ(index0, find(h2, -1, ComplexKey(0)));
+
+    // operator= acquires shared reference
+    ComplexHashtable h3;
+    h3 = h2;
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+    ASSERT_EQ(originalBuckets, getBuckets(h3));
+    EXPECT_EQ(h1.size(), h3.size());
+    EXPECT_EQ(h1.capacity(), h3.capacity());
+    EXPECT_EQ(h1.bucketCount(), h3.bucketCount());
+    EXPECT_EQ(h1.loadFactor(), h3.loadFactor());
+    EXPECT_EQ(index0, find(h3, -1, ComplexKey(0)));
+
+    // editEntryAt copies shared contents
+    h1.editEntryAt(index0).value.v = 42;
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4));
+    ASSERT_NE(originalBuckets, getBuckets(h1));
+    EXPECT_EQ(42, h1.entryAt(index0).value.v);
+    EXPECT_EQ(0, h2.entryAt(index0).value.v);
+    EXPECT_EQ(0, h3.entryAt(index0).value.v);
+
+    // clear releases reference to shared contents
+    h2.clear();
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4));
+    EXPECT_EQ(0U, h2.size());
+    ASSERT_NE(originalBuckets, getBuckets(h2));
+
+    // operator= acquires shared reference, destroys unshared contents
+    h1 = h3;
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+    ASSERT_EQ(originalBuckets, getBuckets(h1));
+    EXPECT_EQ(h3.size(), h1.size());
+    EXPECT_EQ(h3.capacity(), h1.capacity());
+    EXPECT_EQ(h3.bucketCount(), h1.bucketCount());
+    EXPECT_EQ(h3.loadFactor(), h1.loadFactor());
+    EXPECT_EQ(index0, find(h1, -1, ComplexKey(0)));
+
+    // add copies shared contents
+    add(h1, ComplexKey(2), ComplexValue(2));
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(5, 5));
+    ASSERT_NE(originalBuckets, getBuckets(h1));
+    EXPECT_EQ(3U, h1.size());
+    EXPECT_EQ(0U, h2.size());
+    EXPECT_EQ(2U, h3.size());
+
+    // remove copies shared contents
+    h1 = h3;
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+    ASSERT_EQ(originalBuckets, getBuckets(h1));
+    h1.removeAt(index0);
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(3, 3));
+    ASSERT_NE(originalBuckets, getBuckets(h1));
+    EXPECT_EQ(1U, h1.size());
+    EXPECT_EQ(0U, h2.size());
+    EXPECT_EQ(2U, h3.size());
+
+    // rehash copies shared contents
+    h1 = h3;
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
+    ASSERT_EQ(originalBuckets, getBuckets(h1));
+    h1.rehash(10, 1.0f);
+    ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4));
+    ASSERT_NE(originalBuckets, getBuckets(h1));
+    EXPECT_EQ(2U, h1.size());
+    EXPECT_EQ(0U, h2.size());
+    EXPECT_EQ(2U, h3.size());
+}
+
+} // namespace android