auto import from //depot/cupcake/@135843

8 files changed, 1941 insertions, 0 deletions

diff --git a/libpixelflinger/tinyutils/KeyedVector.h b/libpixelflinger/tinyutils/KeyedVector.h
new file mode 100644
index 0000000..1be2094
--- /dev/null
+++ b/libpixelflinger/tinyutils/KeyedVector.h
@@ -0,0 +1,193 @@
+/*
+ *  keyed_vector.h
+ *  Android  
+ *
+ *  Created on 11/18/05.
+ *  Copyright 2005 The Android Open Source Project
+ *
+ */
+
+#ifndef ANDROID_KEYED_VECTOR_H
+#define ANDROID_KEYED_VECTOR_H
+
+#include <assert.h>
+#include <stdint.h>
+#include <sys/types.h>
+
+#include "tinyutils/SortedVector.h"
+#include "tinyutils/TypeHelpers.h"
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+template <typename KEY, typename VALUE>
+class KeyedVector
+{
+public:
+    typedef KEY    key_type;
+    typedef VALUE  value_type;
+
+    inline                  KeyedVector();
+
+    /*
+     * empty the vector
+     */
+
+    inline  void            clear()                     { mVector.clear(); }
+
+    /*! 
+     * vector stats
+     */
+
+    //! returns number of items in the vector
+    inline  size_t          size() const                { return mVector.size(); }
+    //! returns wether or not the vector is empty
+    inline  bool            isEmpty() const             { return mVector.isEmpty(); }
+    //! returns how many items can be stored without reallocating the backing store
+    inline  size_t          capacity() const            { return mVector.capacity(); }
+    //! setst the capacity. capacity can never be reduced less than size()
+    inline ssize_t          setCapacity(size_t size)    { return mVector.setCapacity(size); }
+    
+    /*! 
+     * accessors
+     */
+            const VALUE&    valueFor(const KEY& key) const;
+            const VALUE&    valueAt(size_t index) const;
+            const KEY&      keyAt(size_t index) const;
+            ssize_t         indexOfKey(const KEY& key) const;
+
+    /*!
+     * modifing the array
+     */
+
+            VALUE&          editValueFor(const KEY& key);
+            VALUE&          editValueAt(size_t index);
+
+            /*! 
+             * add/insert/replace items
+             */
+             
+            ssize_t         add(const KEY& key, const VALUE& item);
+            ssize_t         replaceValueFor(const KEY& key, const VALUE& item);
+            ssize_t         replaceValueAt(size_t index, const VALUE& item);
+
+    /*!
+     * remove items
+     */
+
+            ssize_t         removeItem(const KEY& key);
+            ssize_t         removeItemsAt(size_t index, size_t count = 1);
+            
+private:
+            SortedVector< key_value_pair_t<KEY, VALUE> >    mVector;
+};
+
+// ---------------------------------------------------------------------------
+
+/**
+ * Variation of KeyedVector that holds a default value to return when
+ * valueFor() is called with a key that doesn't exist.
+ */
+template <typename KEY, typename VALUE>
+class DefaultKeyedVector : public KeyedVector<KEY, VALUE>
+{
+public:
+    inline                  DefaultKeyedVector(const VALUE& defValue = VALUE());
+            const VALUE&    valueFor(const KEY& key) const;
+
+private:
+            VALUE                                           mDefault;
+};
+
+// ---------------------------------------------------------------------------
+
+template<typename KEY, typename VALUE> inline
+KeyedVector<KEY,VALUE>::KeyedVector()
+{
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::indexOfKey(const KEY& key) const {
+    return mVector.indexOf( key_value_pair_t<KEY,VALUE>(key) );
+}
+
+template<typename KEY, typename VALUE> inline
+const VALUE& KeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
+    ssize_t i = indexOfKey(key);
+    assert(i>=0);
+    return mVector.itemAt(i).value;
+}
+
+template<typename KEY, typename VALUE> inline
+const VALUE& KeyedVector<KEY,VALUE>::valueAt(size_t index) const {
+    return mVector.itemAt(index).value;
+}
+
+template<typename KEY, typename VALUE> inline
+const KEY& KeyedVector<KEY,VALUE>::keyAt(size_t index) const {
+    return mVector.itemAt(index).key;
+}
+
+template<typename KEY, typename VALUE> inline
+VALUE& KeyedVector<KEY,VALUE>::editValueFor(const KEY& key) {
+    ssize_t i = indexOfKey(key);
+    assert(i>=0);
+    return mVector.editItemAt(i).value;
+}
+
+template<typename KEY, typename VALUE> inline
+VALUE& KeyedVector<KEY,VALUE>::editValueAt(size_t index) {
+    return mVector.editItemAt(index).value;
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::add(const KEY& key, const VALUE& value) {
+    return mVector.add( key_value_pair_t<KEY,VALUE>(key, value) );
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::replaceValueFor(const KEY& key, const VALUE& value) {
+    key_value_pair_t<KEY,VALUE> pair(key, value);
+    mVector.remove(pair);
+    return mVector.add(pair);
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::replaceValueAt(size_t index, const VALUE& item) {
+    if (index<size()) {
+        mVector.editValueAt(index).value = item;
+        return index;
+    }
+    return BAD_INDEX;
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY,VALUE>::removeItem(const KEY& key) {
+    return mVector.remove(key_value_pair_t<KEY,VALUE>(key));
+}
+
+template<typename KEY, typename VALUE> inline
+ssize_t KeyedVector<KEY, VALUE>::removeItemsAt(size_t index, size_t count) {
+    return mVector.removeItemsAt(index, count);
+}
+
+// ---------------------------------------------------------------------------
+
+template<typename KEY, typename VALUE> inline
+DefaultKeyedVector<KEY,VALUE>::DefaultKeyedVector(const VALUE& defValue)
+    : mDefault(defValue)
+{
+}
+
+template<typename KEY, typename VALUE> inline
+const VALUE& DefaultKeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
+    ssize_t i = indexOfKey(key);
+    return i >= 0 ? KeyedVector<KEY,VALUE>::valueAt(i) : mDefault;
+}
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_KEYED_VECTOR_H
diff --git a/libpixelflinger/tinyutils/SharedBuffer.cpp b/libpixelflinger/tinyutils/SharedBuffer.cpp
new file mode 100644
index 0000000..ef781a7
--- /dev/null
+++ b/libpixelflinger/tinyutils/SharedBuffer.cpp
@@ -0,0 +1,106 @@
+/*
+ *  SharedBuffer.cpp
+ *  Android  
+ *
+ *  Copyright 2005 The Android Open Source Project
+ *
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include <cutils/atomic.h>
+
+#include "tinyutils/SharedBuffer.h"
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+SharedBuffer* SharedBuffer::alloc(size_t size)
+{
+    SharedBuffer* sb = static_cast<SharedBuffer *>(malloc(sizeof(SharedBuffer) + size));
+    if (sb) {
+        sb->mRefs = 1;
+        sb->mSize = size;
+    }
+    return sb;
+}
+
+
+ssize_t SharedBuffer::dealloc(const SharedBuffer* released)
+{
+    if (released->mRefs != 0) return -1; // XXX: invalid operation
+    free(const_cast<SharedBuffer*>(released));
+    return 0;
+}
+
+SharedBuffer* SharedBuffer::edit() const
+{
+    if (onlyOwner()) {
+        return const_cast<SharedBuffer*>(this);
+    }
+    SharedBuffer* sb = alloc(mSize);
+    if (sb) {
+        memcpy(sb->data(), data(), size());
+        release();
+    }
+    return sb;    
+}
+
+SharedBuffer* SharedBuffer::editResize(size_t newSize) const
+{
+    if (onlyOwner()) {
+        SharedBuffer* buf = const_cast<SharedBuffer*>(this);
+        if (buf->mSize == newSize) return buf;
+        buf = (SharedBuffer*)realloc(buf, sizeof(SharedBuffer) + newSize);
+        if (buf != NULL) {
+            buf->mSize = newSize;
+            return buf;
+        }
+    }
+    SharedBuffer* sb = alloc(newSize);
+    if (sb) {
+        const size_t mySize = mSize;
+        memcpy(sb->data(), data(), newSize < mySize ? newSize : mySize);
+        release();
+    }
+    return sb;    
+}
+
+SharedBuffer* SharedBuffer::attemptEdit() const
+{
+    if (onlyOwner()) {
+        return const_cast<SharedBuffer*>(this);
+    }
+    return 0;
+}
+
+SharedBuffer* SharedBuffer::reset(size_t new_size) const
+{
+    // cheap-o-reset.
+    SharedBuffer* sb = alloc(new_size);
+    if (sb) {
+        release();
+    }
+    return sb;
+}
+
+void SharedBuffer::acquire() const {
+    android_atomic_inc(&mRefs);
+}
+
+int32_t SharedBuffer::release(uint32_t flags) const
+{
+    int32_t prev = 1;
+    if (onlyOwner() || ((prev = android_atomic_dec(&mRefs)) == 1)) {
+        mRefs = 0;
+        if ((flags & eKeepStorage) == 0) {
+            free(const_cast<SharedBuffer*>(this));
+        }
+    }
+    return prev;
+}
+
+
+}; // namespace android
diff --git a/libpixelflinger/tinyutils/SharedBuffer.h b/libpixelflinger/tinyutils/SharedBuffer.h
new file mode 100644
index 0000000..9f63121
--- /dev/null
+++ b/libpixelflinger/tinyutils/SharedBuffer.h
@@ -0,0 +1,138 @@
+/*
+ *  SharedBuffer.h
+ *  Android  
+ *
+ *  Copyright 2005 The Android Open Source Project
+ *
+ */
+
+#ifndef ANDROID_SHARED_BUFFER_H
+#define ANDROID_SHARED_BUFFER_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+class SharedBuffer
+{
+public:
+
+    /* flags to use with release() */
+    enum {
+        eKeepStorage = 0x00000001
+    };
+
+    /*! allocate a buffer of size 'size' and acquire() it.
+     *  call release() to free it.
+     */
+    static          SharedBuffer*           alloc(size_t size);
+    
+    /*! free the memory associated with the SharedBuffer.
+     * Fails if there are any users associated with this SharedBuffer.
+     * In other words, the buffer must have been release by all its
+     * users.
+     */
+    static          ssize_t                 dealloc(const SharedBuffer* released);
+    
+    //! get the SharedBuffer from the data pointer
+    static  inline  const SharedBuffer*     sharedBuffer(const void* data);
+
+    //! access the data for read
+    inline          const void*             data() const;
+    
+    //! access the data for read/write
+    inline          void*                   data();
+
+    //! get size of the buffer
+    inline          size_t                  size() const;
+ 
+    //! get back a SharedBuffer object from its data
+    static  inline  SharedBuffer*           bufferFromData(void* data);
+    
+    //! get back a SharedBuffer object from its data
+    static  inline  const SharedBuffer*     bufferFromData(const void* data);
+
+    //! get the size of a SharedBuffer object from its data
+    static  inline  size_t                  sizeFromData(const void* data);
+    
+    //! edit the buffer (get a writtable, or non-const, version of it)
+                    SharedBuffer*           edit() const;
+
+    //! edit the buffer, resizing if needed
+                    SharedBuffer*           editResize(size_t size) const;
+
+    //! like edit() but fails if a copy is required
+                    SharedBuffer*           attemptEdit() const;
+    
+    //! resize and edit the buffer, loose it's content.
+                    SharedBuffer*           reset(size_t size) const;
+
+    //! acquire/release a reference on this buffer
+                    void                    acquire() const;
+                    
+    /*! release a reference on this buffer, with the option of not
+     * freeing the memory associated with it if it was the last reference
+     * returns the previous reference count
+     */     
+                    int32_t                 release(uint32_t flags = 0) const;
+    
+    //! returns wether or not we're the only owner
+    inline          bool                    onlyOwner() const;
+    
+
+private:
+        inline SharedBuffer() { }
+        inline ~SharedBuffer() { }
+        inline SharedBuffer(const SharedBuffer&);
+ 
+        // 16 bytes. must be sized to preserve correct alingment.
+        mutable int32_t        mRefs;
+                size_t         mSize;
+                uint32_t       mReserved[2];
+};
+
+// ---------------------------------------------------------------------------
+
+const SharedBuffer* SharedBuffer::sharedBuffer(const void* data) {
+    return data ? reinterpret_cast<const SharedBuffer *>(data)-1 : 0;
+}
+
+const void* SharedBuffer::data() const {
+    return this + 1;
+}
+
+void* SharedBuffer::data() {
+    return this + 1;
+}
+
+size_t SharedBuffer::size() const {
+    return mSize;
+}
+
+SharedBuffer* SharedBuffer::bufferFromData(void* data)
+{
+    return ((SharedBuffer*)data)-1;
+}
+    
+const SharedBuffer* SharedBuffer::bufferFromData(const void* data)
+{
+    return ((const SharedBuffer*)data)-1;
+}
+
+size_t SharedBuffer::sizeFromData(const void* data)
+{
+    return (((const SharedBuffer*)data)-1)->mSize;
+}
+
+bool SharedBuffer::onlyOwner() const {
+    return (mRefs == 1);
+}
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_VECTOR_H
diff --git a/libpixelflinger/tinyutils/TypeHelpers.h b/libpixelflinger/tinyutils/TypeHelpers.h
new file mode 100644
index 0000000..9500c90
--- /dev/null
+++ b/libpixelflinger/tinyutils/TypeHelpers.h
@@ -0,0 +1,245 @@
+/*
+ *  TypeHelpers.h
+ *  
+ *  Copyright 2005 The Android Open Source Project
+ *
+ */
+
+#ifndef ANDROID_TYPE_HELPERS_H
+#define ANDROID_TYPE_HELPERS_H
+
+#include <new>
+#include <stdint.h>
+#include <string.h>
+#include <sys/types.h>
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+/*
+ * Types traits
+ */
+    
+template <typename T> struct trait_trivial_ctor  { enum { value = false }; };
+template <typename T> struct trait_trivial_dtor  { enum { value = false }; };
+template <typename T> struct trait_trivial_copy  { enum { value = false }; };
+template <typename T> struct trait_trivial_assign{ enum { value = false }; };
+
+template <typename T> struct trait_pointer     { enum { value = false }; };    
+template <typename T> struct trait_pointer<T*> { enum { value = true }; };
+
+#define ANDROID_BASIC_TYPES_TRAITS( T )                                       \
+    template<> struct trait_trivial_ctor< T >  { enum { value = true }; };    \
+    template<> struct trait_trivial_dtor< T >  { enum { value = true }; };    \
+    template<> struct trait_trivial_copy< T >  { enum { value = true }; };    \
+    template<> struct trait_trivial_assign< T >{ enum { value = true }; }; 
+
+#define ANDROID_TYPE_TRAITS( T, ctor, dtor, copy, assign )                    \
+    template<> struct trait_trivial_ctor< T >  { enum { value = ctor }; };    \
+    template<> struct trait_trivial_dtor< T >  { enum { value = dtor }; };    \
+    template<> struct trait_trivial_copy< T >  { enum { value = copy }; };    \
+    template<> struct trait_trivial_assign< T >{ enum { value = assign }; }; 
+
+template <typename TYPE>
+struct traits {
+    enum {
+        is_pointer          = trait_pointer<TYPE>::value,
+        has_trivial_ctor    = is_pointer || trait_trivial_ctor<TYPE>::value,
+        has_trivial_dtor    = is_pointer || trait_trivial_dtor<TYPE>::value,
+        has_trivial_copy    = is_pointer || trait_trivial_copy<TYPE>::value,
+        has_trivial_assign  = is_pointer || trait_trivial_assign<TYPE>::value   
+    };
+};
+
+template <typename T, typename U>
+struct aggregate_traits {
+    enum {
+        is_pointer          = false,
+        has_trivial_ctor    = traits<T>::has_trivial_ctor && traits<U>::has_trivial_ctor,
+        has_trivial_dtor    = traits<T>::has_trivial_dtor && traits<U>::has_trivial_dtor,
+        has_trivial_copy    = traits<T>::has_trivial_copy && traits<U>::has_trivial_copy,
+        has_trivial_assign  = traits<T>::has_trivial_assign && traits<U>::has_trivial_assign
+    };
+};
+
+// ---------------------------------------------------------------------------
+
+/*
+ * basic types traits
+ */
+ 
+ANDROID_BASIC_TYPES_TRAITS( void );
+ANDROID_BASIC_TYPES_TRAITS( bool );
+ANDROID_BASIC_TYPES_TRAITS( char );
+ANDROID_BASIC_TYPES_TRAITS( unsigned char );
+ANDROID_BASIC_TYPES_TRAITS( short );
+ANDROID_BASIC_TYPES_TRAITS( unsigned short );
+ANDROID_BASIC_TYPES_TRAITS( int );
+ANDROID_BASIC_TYPES_TRAITS( unsigned int );
+ANDROID_BASIC_TYPES_TRAITS( long );
+ANDROID_BASIC_TYPES_TRAITS( unsigned long );
+ANDROID_BASIC_TYPES_TRAITS( long long );
+ANDROID_BASIC_TYPES_TRAITS( unsigned long long );
+ANDROID_BASIC_TYPES_TRAITS( float );
+ANDROID_BASIC_TYPES_TRAITS( double );
+
+// ---------------------------------------------------------------------------
+
+    
+/*
+ * compare and order types
+ */
+
+template<typename TYPE> inline
+int strictly_order_type(const TYPE& lhs, const TYPE& rhs) {
+    return (lhs < rhs) ? 1 : 0;
+}
+
+template<typename TYPE> inline
+int compare_type(const TYPE& lhs, const TYPE& rhs) {
+    return strictly_order_type(rhs, lhs) - strictly_order_type(lhs, rhs);
+}
+
+/*
+ * create, destroy, copy and assign types...
+ */
+ 
+template<typename TYPE> inline
+void construct_type(TYPE* p, size_t n) {
+    if (!traits<TYPE>::has_trivial_ctor) {
+        while (n--) {
+            new(p++) TYPE;
+        }
+    }
+}
+
+template<typename TYPE> inline
+void destroy_type(TYPE* p, size_t n) {
+    if (!traits<TYPE>::has_trivial_dtor) {
+        while (n--) {
+            p->~TYPE();
+            p++;
+        }
+    }
+}
+
+template<typename TYPE> inline
+void copy_type(TYPE* d, const TYPE* s, size_t n) {
+    if (!traits<TYPE>::has_trivial_copy) {
+        while (n--) {
+            new(d) TYPE(*s);
+            d++, s++;
+        }
+    } else {
+        memcpy(d,s,n*sizeof(TYPE));
+    }
+}
+
+template<typename TYPE> inline
+void assign_type(TYPE* d, const TYPE* s, size_t n) {
+    if (!traits<TYPE>::has_trivial_assign) {
+        while (n--) {
+            *d++ = *s++;
+        }
+    } else {
+        memcpy(d,s,n*sizeof(TYPE));
+    }
+}
+
+template<typename TYPE> inline
+void splat_type(TYPE* where, const TYPE* what, size_t n) {
+    if (!traits<TYPE>::has_trivial_copy) {
+        while (n--) {
+            new(where) TYPE(*what);
+            where++;
+        }
+    } else {
+         while (n--) {
+             *where++ = *what;
+        }
+    }
+}
+
+template<typename TYPE> inline
+void move_forward_type(TYPE* d, const TYPE* s, size_t n = 1) {
+    if (!traits<TYPE>::has_trivial_copy || !traits<TYPE>::has_trivial_dtor) {
+        d += n;
+        s += n;
+        while (n--) {
+            --d, --s;
+            if (!traits<TYPE>::has_trivial_copy) {
+                new(d) TYPE(*s);
+            } else {
+                *d = *s;
+            }
+            if (!traits<TYPE>::has_trivial_dtor) {
+                s->~TYPE();
+            }
+        }
+    } else {
+        memmove(d,s,n*sizeof(TYPE));
+    }
+}
+
+template<typename TYPE> inline
+void move_backward_type(TYPE* d, const TYPE* s, size_t n = 1) {
+    if (!traits<TYPE>::has_trivial_copy || !traits<TYPE>::has_trivial_dtor) {
+        while (n--) {
+            if (!traits<TYPE>::has_trivial_copy) {
+                new(d) TYPE(*s);
+            } else {
+                *d = *s;
+            }
+            if (!traits<TYPE>::has_trivial_dtor) {
+                s->~TYPE();
+            }
+            d++, s++;
+        }
+    } else {
+        memmove(d,s,n*sizeof(TYPE));
+    }
+}
+// ---------------------------------------------------------------------------
+
+/*
+ * a key/value pair
+ */
+
+template <typename KEY, typename VALUE>
+struct key_value_pair_t {
+    KEY     key;
+    VALUE   value;
+    key_value_pair_t() { }
+    key_value_pair_t(const key_value_pair_t& o) : key(o.key), value(o.value) { }
+    key_value_pair_t(const KEY& k, const VALUE& v) : key(k), value(v)  { }
+    key_value_pair_t(const KEY& k) : key(k) { }
+    inline bool operator < (const key_value_pair_t& o) const {
+        return strictly_order_type(key, o.key);
+    }
+};
+
+template<>
+template <typename K, typename V>
+struct trait_trivial_ctor< key_value_pair_t<K, V> >
+{ enum { value = aggregate_traits<K,V>::has_trivial_ctor }; };
+template<> 
+template <typename K, typename V>
+struct trait_trivial_dtor< key_value_pair_t<K, V> >
+{ enum { value = aggregate_traits<K,V>::has_trivial_dtor }; };
+template<> 
+template <typename K, typename V>
+struct trait_trivial_copy< key_value_pair_t<K, V> >
+{ enum { value = aggregate_traits<K,V>::has_trivial_copy }; };
+template<> 
+template <typename K, typename V>
+struct trait_trivial_assign< key_value_pair_t<K, V> >
+{ enum { value = aggregate_traits<K,V>::has_trivial_assign};};
+
+// ---------------------------------------------------------------------------
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_TYPE_HELPERS_H
diff --git a/libpixelflinger/tinyutils/Vector.h b/libpixelflinger/tinyutils/Vector.h
new file mode 100644
index 0000000..182bc7b
--- /dev/null
+++ b/libpixelflinger/tinyutils/Vector.h
@@ -0,0 +1,352 @@
+/*
+ *  vector.h
+ *  Android  
+ *
+ *  Copyright 2005 The Android Open Source Project
+ *
+ */
+
+#ifndef ANDROID_VECTOR_H
+#define ANDROID_VECTOR_H
+
+#include <new>
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <cutils/log.h>
+
+#include "tinyutils/VectorImpl.h"
+#include "tinyutils/TypeHelpers.h"
+
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+/*!
+ * The main templated vector class ensuring type safety
+ * while making use of VectorImpl.
+ * This is the class users want to use.
+ */
+
+template <class TYPE>
+class Vector : private VectorImpl
+{
+public:
+            typedef TYPE    value_type;
+    
+    /*! 
+     * Constructors and destructors
+     */
+    
+                            Vector();
+                            Vector(const Vector<TYPE>& rhs);
+    virtual                 ~Vector();
+
+    /*! copy operator */
+            const Vector<TYPE>&     operator = (const Vector<TYPE>& rhs) const;
+            Vector<TYPE>&           operator = (const Vector<TYPE>& rhs);    
+
+    /*
+     * empty the vector
+     */
+
+    inline  void            clear()             { VectorImpl::clear(); }
+
+    /*! 
+     * vector stats
+     */
+
+    //! returns number of items in the vector
+    inline  size_t          size() const                { return VectorImpl::size(); }
+    //! returns wether or not the vector is empty
+    inline  bool            isEmpty() const             { return VectorImpl::isEmpty(); }
+    //! returns how many items can be stored without reallocating the backing store
+    inline  size_t          capacity() const            { return VectorImpl::capacity(); }
+    //! setst the capacity. capacity can never be reduced less than size()
+    inline  ssize_t         setCapacity(size_t size)    { return VectorImpl::setCapacity(size); }
+
+    /*! 
+     * C-style array access
+     */
+     
+    //! read-only C-style access 
+    inline  const TYPE*     array() const;
+    //! read-write C-style access
+            TYPE*           editArray();
+    
+    /*! 
+     * accessors
+     */
+
+    //! read-only access to an item at a given index
+    inline  const TYPE&     operator [] (size_t index) const;
+    //! alternate name for operator []
+    inline  const TYPE&     itemAt(size_t index) const;
+    //! stack-usage of the vector. returns the top of the stack (last element)
+            const TYPE&     top() const;
+    //! same as operator [], but allows to access the vector backward (from the end) with a negative index
+            const TYPE&     mirrorItemAt(ssize_t index) const;
+
+    /*!
+     * modifing the array
+     */
+
+    //! copy-on write support, grants write access to an item
+            TYPE&           editItemAt(size_t index);
+    //! grants right acces to the top of the stack (last element)
+            TYPE&           editTop();
+
+            /*! 
+             * append/insert another vector
+             */
+            
+    //! insert another vector at a given index
+            ssize_t         insertVectorAt(const Vector<TYPE>& vector, size_t index);
+
+    //! append another vector at the end of this one
+            ssize_t         appendVector(const Vector<TYPE>& vector);
+
+
+            /*! 
+             * add/insert/replace items
+             */
+             
+    //! insert one or several items initialized with their default constructor
+    inline  ssize_t         insertAt(size_t index, size_t numItems = 1);
+    //! insert on onr several items initialized from a prototype item
+            ssize_t         insertAt(const TYPE& prototype_item, size_t index, size_t numItems = 1);
+    //! pop the top of the stack (removes the last element). No-op if the stack's empty
+    inline  void            pop();
+    //! pushes an item initialized with its default constructor
+    inline  void            push();
+    //! pushes an item on the top of the stack
+            void            push(const TYPE& item);
+    //! same as push() but returns the index the item was added at (or an error)
+    inline  ssize_t         add();
+    //! same as push() but returns the index the item was added at (or an error)
+            ssize_t         add(const TYPE& item);            
+    //! replace an item with a new one initialized with its default constructor
+    inline  ssize_t         replaceAt(size_t index);
+    //! replace an item with a new one
+            ssize_t         replaceAt(const TYPE& item, size_t index);
+
+    /*!
+     * remove items
+     */
+
+    //! remove several items
+    inline  ssize_t         removeItemsAt(size_t index, size_t count = 1);
+    //! remove one item
+    inline  ssize_t         removeAt(size_t index)  { return removeItemsAt(index); }
+
+    /*!
+     * sort (stable) the array
+     */
+     
+     typedef int (*compar_t)(const TYPE* lhs, const TYPE* rhs);
+     typedef int (*compar_r_t)(const TYPE* lhs, const TYPE* rhs, void* state);
+     
+     inline status_t        sort(compar_t cmp);
+     inline status_t        sort(compar_r_t cmp, void* state);
+
+protected:
+    virtual void    do_construct(void* storage, size_t num) const;
+    virtual void    do_destroy(void* storage, size_t num) const;
+    virtual void    do_copy(void* dest, const void* from, size_t num) const;
+    virtual void    do_splat(void* dest, const void* item, size_t num) const;
+    virtual void    do_move_forward(void* dest, const void* from, size_t num) const;
+    virtual void    do_move_backward(void* dest, const void* from, size_t num) const;
+};
+
+
+// ---------------------------------------------------------------------------
+// No user serviceable parts from here...
+// ---------------------------------------------------------------------------
+
+template<class TYPE> inline
+Vector<TYPE>::Vector()
+    : VectorImpl(sizeof(TYPE),
+                ((traits<TYPE>::has_trivial_ctor   ? HAS_TRIVIAL_CTOR   : 0)
+                |(traits<TYPE>::has_trivial_dtor   ? HAS_TRIVIAL_DTOR   : 0)
+                |(traits<TYPE>::has_trivial_copy   ? HAS_TRIVIAL_COPY   : 0)
+                |(traits<TYPE>::has_trivial_assign ? HAS_TRIVIAL_ASSIGN : 0))
+                )
+{
+}
+
+template<class TYPE> inline
+Vector<TYPE>::Vector(const Vector<TYPE>& rhs)
+    : VectorImpl(rhs) {
+}
+
+template<class TYPE> inline
+Vector<TYPE>::~Vector() {
+    finish_vector();
+}
+
+template<class TYPE> inline
+Vector<TYPE>& Vector<TYPE>::operator = (const Vector<TYPE>& rhs) {
+    VectorImpl::operator = (rhs);
+    return *this; 
+}
+
+template<class TYPE> inline
+const Vector<TYPE>& Vector<TYPE>::operator = (const Vector<TYPE>& rhs) const {
+    VectorImpl::operator = (rhs);
+    return *this; 
+}
+
+template<class TYPE> inline
+const TYPE* Vector<TYPE>::array() const {
+    return static_cast<const TYPE *>(arrayImpl());
+}
+
+template<class TYPE> inline
+TYPE* Vector<TYPE>::editArray() {
+    return static_cast<TYPE *>(editArrayImpl());
+}
+
+
+template<class TYPE> inline
+const TYPE& Vector<TYPE>::operator[](size_t index) const {
+    LOG_FATAL_IF( index>=size(),
+                  "itemAt: index %d is past size %d", (int)index, (int)size() );
+    return *(array() + index);
+}
+
+template<class TYPE> inline
+const TYPE& Vector<TYPE>::itemAt(size_t index) const {
+    return operator[](index);
+}
+
+template<class TYPE> inline
+const TYPE& Vector<TYPE>::mirrorItemAt(ssize_t index) const {
+    LOG_FATAL_IF( (index>0 ? index : -index)>=size(),
+                  "mirrorItemAt: index %d is past size %d",
+                  (int)index, (int)size() );
+    return *(array() + ((index<0) ? (size()-index) : index));
+}
+
+template<class TYPE> inline
+const TYPE& Vector<TYPE>::top() const {
+    return *(array() + size() - 1);
+}
+
+template<class TYPE> inline
+TYPE& Vector<TYPE>::editItemAt(size_t index) {
+    return *( static_cast<TYPE *>(editItemLocation(index)) );
+}
+
+template<class TYPE> inline
+TYPE& Vector<TYPE>::editTop() {
+    return *( static_cast<TYPE *>(editItemLocation(size()-1)) );
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::insertVectorAt(const Vector<TYPE>& vector, size_t index) {
+    return VectorImpl::insertVectorAt(reinterpret_cast<const VectorImpl&>(vector), index);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::appendVector(const Vector<TYPE>& vector) {
+    return VectorImpl::appendVector(reinterpret_cast<const VectorImpl&>(vector));
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::insertAt(const TYPE& item, size_t index, size_t numItems) {
+    return VectorImpl::insertAt(&item, index, numItems);
+}
+
+template<class TYPE> inline
+void Vector<TYPE>::push(const TYPE& item) {
+    return VectorImpl::push(&item);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::add(const TYPE& item) {
+    return VectorImpl::add(&item);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::replaceAt(const TYPE& item, size_t index) {
+    return VectorImpl::replaceAt(&item, index);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::insertAt(size_t index, size_t numItems) {
+    return VectorImpl::insertAt(index, numItems);
+}
+
+template<class TYPE> inline
+void Vector<TYPE>::pop() {
+    VectorImpl::pop();
+}
+
+template<class TYPE> inline
+void Vector<TYPE>::push() {
+    VectorImpl::push();
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::add() {
+    return VectorImpl::add();
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::replaceAt(size_t index) {
+    return VectorImpl::replaceAt(index);
+}
+
+template<class TYPE> inline
+ssize_t Vector<TYPE>::removeItemsAt(size_t index, size_t count) {
+    return VectorImpl::removeItemsAt(index, count);
+}
+
+template<class TYPE> inline
+status_t Vector<TYPE>::sort(Vector<TYPE>::compar_t cmp) {
+    return VectorImpl::sort((VectorImpl::compar_t)cmp);
+}
+
+template<class TYPE> inline
+status_t Vector<TYPE>::sort(Vector<TYPE>::compar_r_t cmp, void* state) {
+    return VectorImpl::sort((VectorImpl::compar_r_t)cmp, state);
+}
+
+// ---------------------------------------------------------------------------
+
+template<class TYPE>
+void Vector<TYPE>::do_construct(void* storage, size_t num) const {
+    construct_type( reinterpret_cast<TYPE*>(storage), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_destroy(void* storage, size_t num) const {
+    destroy_type( reinterpret_cast<TYPE*>(storage), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_copy(void* dest, const void* from, size_t num) const {
+    copy_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_splat(void* dest, const void* item, size_t num) const {
+    splat_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(item), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_move_forward(void* dest, const void* from, size_t num) const {
+    move_forward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
+}
+
+template<class TYPE>
+void Vector<TYPE>::do_move_backward(void* dest, const void* from, size_t num) const {
+    move_backward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
+}
+
+}; // namespace android
+
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_VECTOR_H
diff --git a/libpixelflinger/tinyutils/VectorImpl.cpp b/libpixelflinger/tinyutils/VectorImpl.cpp
new file mode 100644
index 0000000..a049706
--- /dev/null
+++ b/libpixelflinger/tinyutils/VectorImpl.cpp
@@ -0,0 +1,552 @@
+/*
+ *  vector_impl.cpp
+ *  Android  
+ *
+ *  Copyright 2005 The Android Open Source Project
+ *
+ */
+
+#define LOG_TAG "Vector"
+
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <errno.h>
+
+#include <cutils/log.h>
+
+#include "tinyutils/SharedBuffer.h"
+#include "tinyutils/VectorImpl.h"
+
+/*****************************************************************************/
+
+
+namespace android {
+
+enum {
+    NO_ERROR          = 0,    // No errors.
+    NO_MEMORY           = -ENOMEM,
+    BAD_VALUE           = -EINVAL,
+    BAD_INDEX           = -EOVERFLOW,
+    NAME_NOT_FOUND      = -ENOENT,
+};
+
+// ----------------------------------------------------------------------------
+
+const size_t kMinVectorCapacity = 4;
+
+static inline size_t max(size_t a, size_t b) {
+    return a>b ? a : b;
+}
+
+// ----------------------------------------------------------------------------
+
+VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
+    : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize)
+{
+}
+
+VectorImpl::VectorImpl(const VectorImpl& rhs)
+    :   mStorage(rhs.mStorage), mCount(rhs.mCount),
+        mFlags(rhs.mFlags), mItemSize(rhs.mItemSize)
+{
+    if (mStorage) {
+        SharedBuffer::sharedBuffer(mStorage)->acquire();
+    }
+}
+
+VectorImpl::~VectorImpl()
+{
+    LOG_ASSERT(!mCount,
+        "[%p] "
+        "subclasses of VectorImpl must call finish_vector()"
+        " in their destructor. Leaking %d bytes.",
+        this, (int)(mCount*mItemSize));
+    // We can't call _do_destroy() here because the vtable is already gone. 
+}
+
+VectorImpl& VectorImpl::operator = (const VectorImpl& rhs)
+{
+    LOG_ASSERT(mItemSize == rhs.mItemSize,
+        "Vector<> have different types (this=%p, rhs=%p)", this, &rhs);
+    if (this != &rhs) {
+        release_storage();
+        if (rhs.mCount) {
+            mStorage = rhs.mStorage;
+            mCount = rhs.mCount;
+            SharedBuffer::sharedBuffer(mStorage)->acquire();
+        } else {
+            mStorage = 0;
+            mCount = 0;
+        }
+    }
+    return *this;
+}
+
+void* VectorImpl::editArrayImpl()
+{
+    if (mStorage) {
+        SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage)->attemptEdit();
+        if (sb == 0) {
+            sb = SharedBuffer::alloc(capacity() * mItemSize);
+            if (sb) {
+                _do_copy(sb->data(), mStorage, mCount);
+                release_storage();
+                mStorage = sb->data();
+            }
+        }
+    }
+    return mStorage;
+}
+
+size_t VectorImpl::capacity() const
+{
+    if (mStorage) {
+        return SharedBuffer::sharedBuffer(mStorage)->size() / mItemSize;
+    }
+    return 0;
+}
+
+ssize_t VectorImpl::insertVectorAt(const VectorImpl& vector, size_t index)
+{
+    if (index > size())
+        return BAD_INDEX;
+    void* where = _grow(index, vector.size());
+    if (where) {
+        _do_copy(where, vector.arrayImpl(), vector.size());
+    }
+    return where ? index : (ssize_t)NO_MEMORY;
+}
+
+ssize_t VectorImpl::appendVector(const VectorImpl& vector)
+{
+    return insertVectorAt(vector, size());
+}
+
+ssize_t VectorImpl::insertAt(size_t index, size_t numItems)
+{
+    return insertAt(0, index, numItems);
+}
+
+ssize_t VectorImpl::insertAt(const void* item, size_t index, size_t numItems)
+{
+    if (index > size())
+        return BAD_INDEX;
+    void* where = _grow(index, numItems);
+    if (where) {
+        if (item) {
+            _do_splat(where, item, numItems);
+        } else {
+            _do_construct(where, numItems);
+        }
+    }
+    return where ? index : (ssize_t)NO_MEMORY;
+}
+
+void VectorImpl::pop()
+{
+    if (size())
+        removeItemsAt(size()-1, 1);
+}
+
+void VectorImpl::push()
+{
+    push(0);
+}
+
+void VectorImpl::push(const void* item)
+{
+    insertAt(item, size());
+}
+
+ssize_t VectorImpl::add()
+{
+    return add(0);
+}
+
+ssize_t VectorImpl::add(const void* item)
+{
+    return insertAt(item, size());
+}
+
+ssize_t VectorImpl::replaceAt(size_t index)
+{
+    return replaceAt(0, index);
+}
+
+ssize_t VectorImpl::replaceAt(const void* prototype, size_t index)
+{
+    LOG_ASSERT(index<size(),
+        "[%p] replace: index=%d, size=%d", this, (int)index, (int)size());
+
+    void* item = editItemLocation(index);
+    if (item == 0)
+        return NO_MEMORY;
+    _do_destroy(item, 1);
+    if (prototype == 0) {
+        _do_construct(item, 1);
+    } else {
+        _do_copy(item, prototype, 1);
+    }
+    return ssize_t(index);
+}
+
+ssize_t VectorImpl::removeItemsAt(size_t index, size_t count)
+{
+    LOG_ASSERT((index+count)<=size(),
+        "[%p] remove: index=%d, count=%d, size=%d",
+               this, (int)index, (int)count, (int)size());
+
+    if ((index+count) > size())
+        return BAD_VALUE;
+   _shrink(index, count);
+   return index;
+}
+
+void VectorImpl::finish_vector()
+{
+    release_storage();
+    mStorage = 0;
+    mCount = 0;
+}
+
+void VectorImpl::clear()
+{
+    _shrink(0, mCount);
+}
+
+void* VectorImpl::editItemLocation(size_t index)
+{
+    LOG_ASSERT(index<capacity(),
+        "[%p] itemLocation: index=%d, capacity=%d, count=%d",
+        this, (int)index, (int)capacity(), (int)mCount);
+            
+    void* buffer = editArrayImpl();
+    if (buffer)
+        return reinterpret_cast<char*>(buffer) + index*mItemSize;
+    return 0;
+}
+
+const void* VectorImpl::itemLocation(size_t index) const
+{
+    LOG_ASSERT(index<capacity(),
+        "[%p] editItemLocation: index=%d, capacity=%d, count=%d",
+        this, (int)index, (int)capacity(), (int)mCount);
+
+    const  void* buffer = arrayImpl();
+    if (buffer)
+        return reinterpret_cast<const char*>(buffer) + index*mItemSize;
+    return 0;
+}
+
+ssize_t VectorImpl::setCapacity(size_t new_capacity)
+{
+    size_t current_capacity = capacity();
+    ssize_t amount = new_capacity - size();
+    if (amount <= 0) {
+        // we can't reduce the capacity
+        return current_capacity;
+    } 
+    SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
+    if (sb) {
+        void* array = sb->data();
+        _do_copy(array, mStorage, size());
+        release_storage();
+        mStorage = const_cast<void*>(array);
+    } else {
+        return NO_MEMORY;
+    }
+    return new_capacity;
+}
+
+void VectorImpl::release_storage()
+{
+    if (mStorage) {
+        const SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage);
+        if (sb->release(SharedBuffer::eKeepStorage) == 1) {
+            _do_destroy(mStorage, mCount);
+            SharedBuffer::dealloc(sb);
+        } 
+    }
+}
+
+void* VectorImpl::_grow(size_t where, size_t amount)
+{
+//    LOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
+//        this, (int)where, (int)amount, (int)mCount, (int)capacity());
+
+    if (where > mCount)
+        where = mCount;
+      
+    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);
+        if ((mStorage) &&
+            (mCount==where) &&
+            (mFlags & HAS_TRIVIAL_COPY) &&
+            (mFlags & HAS_TRIVIAL_DTOR))
+        {
+            const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
+            SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
+            mStorage = sb->data();
+        } else {
+            SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
+            if (sb) {
+                void* array = sb->data();
+                if (where>0) {
+                    _do_copy(array, mStorage, where);
+                }
+                if (mCount>where) {
+                    const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize;
+                    void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
+                    _do_copy(dest, from, mCount-where);
+                }
+                release_storage();
+                mStorage = const_cast<void*>(array);
+            }
+        }
+    } else {
+        ssize_t s = mCount-where;
+        if (s>0) {
+            void* array = editArrayImpl();    
+            void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
+            const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize;
+            _do_move_forward(to, from, s);
+        }
+    }
+    mCount += amount;
+    void* free_space = const_cast<void*>(itemLocation(where));
+    return free_space;
+}
+
+void VectorImpl::_shrink(size_t where, size_t amount)
+{
+    if (!mStorage)
+        return;
+
+//    LOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
+//        this, (int)where, (int)amount, (int)mCount, (int)capacity());
+
+    if (where >= mCount)
+        where = mCount - amount;
+
+    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);
+        if ((where == mCount-amount) &&
+            (mFlags & HAS_TRIVIAL_COPY) &&
+            (mFlags & HAS_TRIVIAL_DTOR))
+        {
+            const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
+            SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
+            mStorage = sb->data();
+        } else {
+            SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
+            if (sb) {
+                void* array = sb->data();
+                if (where>0) {
+                    _do_copy(array, mStorage, where);
+                }
+                if (mCount > where+amount) {
+                    const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize;
+                    void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
+                    _do_copy(dest, from, mCount-(where+amount));
+                }
+                release_storage();
+                mStorage = const_cast<void*>(array);
+            }
+        }
+    } else {
+        void* array = editArrayImpl();    
+        void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
+        _do_destroy(to, amount);
+        ssize_t s = mCount-(where+amount);
+        if (s>0) {
+            const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
+            _do_move_backward(to, from, s);
+        }
+    }
+
+    // adjust the number of items...
+    mCount -= amount;
+}
+
+size_t VectorImpl::itemSize() const {
+    return mItemSize;
+}
+
+void VectorImpl::_do_construct(void* storage, size_t num) const
+{
+    if (!(mFlags & HAS_TRIVIAL_CTOR)) {
+        do_construct(storage, num);
+    }
+}
+
+void VectorImpl::_do_destroy(void* storage, size_t num) const
+{
+    if (!(mFlags & HAS_TRIVIAL_DTOR)) {
+        do_destroy(storage, num);
+    }
+}
+
+void VectorImpl::_do_copy(void* dest, const void* from, size_t num) const
+{
+    if (!(mFlags & HAS_TRIVIAL_COPY)) {
+        do_copy(dest, from, num);
+    } else {
+        memcpy(dest, from, num*itemSize());
+    }
+}
+
+void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
+    do_splat(dest, item, num);
+}
+
+void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
+    do_move_forward(dest, from, num);
+}
+
+void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
+    do_move_backward(dest, from, num);
+}
+
+void VectorImpl::reservedVectorImpl1() { }
+void VectorImpl::reservedVectorImpl2() { }
+void VectorImpl::reservedVectorImpl3() { }
+void VectorImpl::reservedVectorImpl4() { }
+void VectorImpl::reservedVectorImpl5() { }
+void VectorImpl::reservedVectorImpl6() { }
+void VectorImpl::reservedVectorImpl7() { }
+void VectorImpl::reservedVectorImpl8() { }
+
+/*****************************************************************************/
+
+SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
+    : VectorImpl(itemSize, flags)
+{
+}
+
+SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
+: VectorImpl(rhs)
+{
+}
+
+SortedVectorImpl::~SortedVectorImpl()
+{
+}
+
+SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
+{
+    return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
+}
+
+ssize_t SortedVectorImpl::indexOf(const void* item) const
+{
+    return _indexOrderOf(item);
+}
+
+size_t SortedVectorImpl::orderOf(const void* item) const
+{
+    size_t o;
+    _indexOrderOf(item, &o);
+    return o;
+}
+
+ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
+{
+    // binary search
+    ssize_t err = NAME_NOT_FOUND;
+    ssize_t l = 0;
+    ssize_t h = size()-1;
+    ssize_t mid;
+    const void* a = arrayImpl();
+    const size_t s = itemSize();
+    while (l <= h) {
+        mid = l + (h - l)/2;
+        const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
+        const int c = do_compare(curr, item);
+        if (c == 0) {
+            err = l = mid;
+            break;
+        } else if (c < 0) {
+            l = mid + 1;
+        } else {
+            h = mid - 1;
+        }
+    }
+    if (order) *order = l;
+    return err;
+}
+
+ssize_t SortedVectorImpl::add(const void* item)
+{
+    size_t order;
+    ssize_t index = _indexOrderOf(item, &order);
+    if (index < 0) {
+        index = VectorImpl::insertAt(item, order, 1);
+    } else {
+        index = VectorImpl::replaceAt(item, index);
+    }
+    return index;
+}
+
+ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
+{
+    // naive merge...
+    if (!vector.isEmpty()) {
+        const void* buffer = vector.arrayImpl();
+        const size_t is = itemSize();
+        size_t s = vector.size();
+        for (size_t i=0 ; i<s ; i++) {
+            ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
+            if (err<0) {
+                return err;
+            }
+        }
+    }
+    return NO_ERROR;
+}
+
+ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
+{
+    // we've merging a sorted vector... nice!
+    ssize_t err = NO_ERROR;
+    if (!vector.isEmpty()) {
+        // first take care of the case where the vectors are sorted together
+        if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
+            err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
+        } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
+            err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
+        } else {
+            // this could be made a little better
+            err = merge(static_cast<const VectorImpl&>(vector));
+        }
+    }
+    return err;
+}
+
+ssize_t SortedVectorImpl::remove(const void* item)
+{
+    ssize_t i = indexOf(item);
+    if (i>=0) {
+        VectorImpl::removeItemsAt(i, 1);
+    }
+    return i;
+}
+
+void SortedVectorImpl::reservedSortedVectorImpl1() { };
+void SortedVectorImpl::reservedSortedVectorImpl2() { };
+void SortedVectorImpl::reservedSortedVectorImpl3() { };
+void SortedVectorImpl::reservedSortedVectorImpl4() { };
+void SortedVectorImpl::reservedSortedVectorImpl5() { };
+void SortedVectorImpl::reservedSortedVectorImpl6() { };
+void SortedVectorImpl::reservedSortedVectorImpl7() { };
+void SortedVectorImpl::reservedSortedVectorImpl8() { };
+
+
+/*****************************************************************************/
+
+}; // namespace android
+
diff --git a/libpixelflinger/tinyutils/VectorImpl.h b/libpixelflinger/tinyutils/VectorImpl.h
new file mode 100644
index 0000000..e868eca
--- /dev/null
+++ b/libpixelflinger/tinyutils/VectorImpl.h
@@ -0,0 +1,185 @@
+/*
+ *  vector_impl.h
+ *  Android  
+ *
+ *  Copyright 2005 The Android Open Source Project
+ *
+ */
+
+#ifndef ANDROID_VECTOR_IMPL_H
+#define ANDROID_VECTOR_IMPL_H
+
+#include <assert.h>
+#include <stdint.h>
+#include <sys/types.h>
+
+// ---------------------------------------------------------------------------
+// No user serviceable parts in here...
+// ---------------------------------------------------------------------------
+
+namespace android {
+
+/*!
+ * Implementation of the guts of the vector<> class
+ * this ensures backward binary compatibility and
+ * reduces code size.
+ * For performance reasons, we expose mStorage and mCount
+ * so these fields are set in stone.
+ *
+ */
+
+class VectorImpl
+{
+public:
+    enum { // flags passed to the ctor
+        HAS_TRIVIAL_CTOR    = 0x00000001,
+        HAS_TRIVIAL_DTOR    = 0x00000002,
+        HAS_TRIVIAL_COPY    = 0x00000004,
+        HAS_TRIVIAL_ASSIGN  = 0x00000008
+    };
+
+                            VectorImpl(size_t itemSize, uint32_t flags);
+                            VectorImpl(const VectorImpl& rhs);
+    virtual                 ~VectorImpl();
+
+    /*! must be called from subclasses destructor */
+            void            finish_vector();
+
+            VectorImpl&     operator = (const VectorImpl& rhs);    
+            
+    /*! C-style array access */
+    inline  const void*     arrayImpl() const       { return mStorage; }
+            void*           editArrayImpl();
+            
+    /*! vector stats */
+    inline  size_t          size() const        { return mCount; }
+    inline  bool            isEmpty() const     { return mCount == 0; }
+            size_t          capacity() const;
+            ssize_t         setCapacity(size_t size);
+
+            /*! append/insert another vector */
+            ssize_t         insertVectorAt(const VectorImpl& vector, size_t index);
+            ssize_t         appendVector(const VectorImpl& vector);
+            
+            /*! add/insert/replace items */
+            ssize_t         insertAt(size_t where, size_t numItems = 1);
+            ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
+            void            pop();
+            void            push();
+            void            push(const void* item);
+            ssize_t         add();
+            ssize_t         add(const void* item);
+            ssize_t         replaceAt(size_t index);
+            ssize_t         replaceAt(const void* item, size_t index);
+
+            /*! remove items */
+            ssize_t         removeItemsAt(size_t index, size_t count = 1);
+            void            clear();
+
+            const void*     itemLocation(size_t index) const;
+            void*           editItemLocation(size_t index);
+
+protected:
+            size_t          itemSize() const;
+            void            release_storage();
+
+    virtual void            do_construct(void* storage, size_t num) const = 0;
+    virtual void            do_destroy(void* storage, size_t num) const = 0;
+    virtual void            do_copy(void* dest, const void* from, size_t num) const = 0;
+    virtual void            do_splat(void* dest, const void* item, size_t num) const = 0;
+    virtual void            do_move_forward(void* dest, const void* from, size_t num) const = 0;
+    virtual void            do_move_backward(void* dest, const void* from, size_t num) const = 0;
+
+    // take care of FBC...
+    virtual void            reservedVectorImpl1();
+    virtual void            reservedVectorImpl2();
+    virtual void            reservedVectorImpl3();
+    virtual void            reservedVectorImpl4();
+    virtual void            reservedVectorImpl5();
+    virtual void            reservedVectorImpl6();
+    virtual void            reservedVectorImpl7();
+    virtual void            reservedVectorImpl8();
+    
+private:
+        void* _grow(size_t where, size_t amount);
+        void  _shrink(size_t where, size_t amount);
+
+        inline void _do_construct(void* storage, size_t num) const;
+        inline void _do_destroy(void* storage, size_t num) const;
+        inline void _do_copy(void* dest, const void* from, size_t num) const;
+        inline void _do_splat(void* dest, const void* item, size_t num) const;
+        inline void _do_move_forward(void* dest, const void* from, size_t num) const;
+        inline void _do_move_backward(void* dest, const void* from, size_t num) const;
+
+            // These 2 fields are exposed in the inlines below,
+            // so they're set in stone.
+            void *      mStorage;   // base address of the vector
+            size_t      mCount;     // number of items
+
+    const   uint32_t    mFlags;
+    const   size_t      mItemSize;
+};
+
+
+
+class SortedVectorImpl : public VectorImpl
+{
+public:
+                            SortedVectorImpl(size_t itemSize, uint32_t flags);
+                            SortedVectorImpl(const VectorImpl& rhs);
+    virtual                 ~SortedVectorImpl();
+    
+    SortedVectorImpl&     operator = (const SortedVectorImpl& rhs);    
+
+    //! finds the index of an item
+            ssize_t         indexOf(const void* item) const;
+
+    //! finds where this item should be inserted
+            size_t          orderOf(const void* item) const;
+
+    //! add an item in the right place (or replaces it if there is one)
+            ssize_t         add(const void* item);
+
+    //! merges a vector into this one
+            ssize_t         merge(const VectorImpl& vector);
+            ssize_t         merge(const SortedVectorImpl& vector);
+             
+    //! removes an item
+            ssize_t         remove(const void* item);
+        
+protected:
+    virtual int             do_compare(const void* lhs, const void* rhs) const = 0;
+
+    // take care of FBC...
+    virtual void            reservedSortedVectorImpl1();
+    virtual void            reservedSortedVectorImpl2();
+    virtual void            reservedSortedVectorImpl3();
+    virtual void            reservedSortedVectorImpl4();
+    virtual void            reservedSortedVectorImpl5();
+    virtual void            reservedSortedVectorImpl6();
+    virtual void            reservedSortedVectorImpl7();
+    virtual void            reservedSortedVectorImpl8();
+
+private:
+            ssize_t         _indexOrderOf(const void* item, size_t* order = 0) const;
+
+            // these are made private, because they can't be used on a SortedVector
+            // (they don't have an implementation either)
+            ssize_t         add();
+            void            pop();
+            void            push();
+            void            push(const void* item);
+            ssize_t         insertVectorAt(const VectorImpl& vector, size_t index);
+            ssize_t         appendVector(const VectorImpl& vector);
+            ssize_t         insertAt(size_t where, size_t numItems = 1);
+            ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
+            ssize_t         replaceAt(size_t index);
+            ssize_t         replaceAt(const void* item, size_t index);
+};
+
+}; // namespace android
+
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_VECTOR_IMPL_H
diff --git a/libpixelflinger/tinyutils/smartpointer.h b/libpixelflinger/tinyutils/smartpointer.h
new file mode 100644
index 0000000..88032d7
--- /dev/null
+++ b/libpixelflinger/tinyutils/smartpointer.h
@@ -0,0 +1,170 @@
+/*
+ *  smartpointer.h
+ *  Android  
+ *
+ *  Copyright 2005 The Android Open Source Project
+ *
+ */
+
+#ifndef ANDROID_SMART_POINTER_H
+#define ANDROID_SMART_POINTER_H
+
+#include <stdint.h>
+#include <sys/types.h>
+#include <stdlib.h>
+
+// ---------------------------------------------------------------------------
+namespace android {
+
+// ---------------------------------------------------------------------------
+
+#define COMPARE(_op_)                                           \
+inline bool operator _op_ (const sp<T>& o) const {              \
+    return m_ptr _op_ o.m_ptr;                                  \
+}                                                               \
+inline bool operator _op_ (const T* o) const {                  \
+    return m_ptr _op_ o;                                        \
+}                                                               \
+template<typename U>                                            \
+inline bool operator _op_ (const sp<U>& o) const {              \
+    return m_ptr _op_ o.m_ptr;                                  \
+}                                                               \
+template<typename U>                                            \
+inline bool operator _op_ (const U* o) const {                  \
+    return m_ptr _op_ o;                                        \
+}
+
+// ---------------------------------------------------------------------------
+
+template <typename T>
+class sp
+{
+public:
+    inline sp() : m_ptr(0) { }
+
+    sp(T* other);
+    sp(const sp<T>& other);
+    template<typename U> sp(U* other);
+    template<typename U> sp(const sp<U>& other);
+
+    ~sp();
+    
+    // Assignment
+
+    sp& operator = (T* other);
+    sp& operator = (const sp<T>& other);
+    
+    template<typename U> sp& operator = (const sp<U>& other);
+    template<typename U> sp& operator = (U* other);
+    
+    // Reset
+    void clear();
+    
+    // Accessors
+
+    inline  T&      operator* () const  { return *m_ptr; }
+    inline  T*      operator-> () const { return m_ptr;  }
+    inline  T*      get() const         { return m_ptr; }
+
+    // Operators
+        
+    COMPARE(==)
+    COMPARE(!=)
+    COMPARE(>)
+    COMPARE(<)
+    COMPARE(<=)
+    COMPARE(>=)
+
+private:    
+    template<typename Y> friend class sp;
+
+    T*              m_ptr;
+};
+
+// ---------------------------------------------------------------------------
+// No user serviceable parts below here.
+
+template<typename T>
+sp<T>::sp(T* other)
+    : m_ptr(other)
+{
+    if (other) other->incStrong(this);
+}
+
+template<typename T>
+sp<T>::sp(const sp<T>& other)
+    : m_ptr(other.m_ptr)
+{
+    if (m_ptr) m_ptr->incStrong(this);
+}
+
+template<typename T> template<typename U>
+sp<T>::sp(U* other) : m_ptr(other)
+{
+    if (other) other->incStrong(this);
+}
+
+template<typename T> template<typename U>
+sp<T>::sp(const sp<U>& other)
+    : m_ptr(other.m_ptr)
+{
+    if (m_ptr) m_ptr->incStrong(this);
+}
+
+template<typename T>
+sp<T>::~sp()
+{
+    if (m_ptr) m_ptr->decStrong(this);
+}
+
+template<typename T>
+sp<T>& sp<T>::operator = (const sp<T>& other) {
+    if (other.m_ptr) other.m_ptr->incStrong(this);
+    if (m_ptr) m_ptr->decStrong(this);
+    m_ptr = other.m_ptr;
+    return *this;
+}
+
+template<typename T>
+sp<T>& sp<T>::operator = (T* other)
+{
+    if (other) other->incStrong(this);
+    if (m_ptr) m_ptr->decStrong(this);
+    m_ptr = other;
+    return *this;
+}
+
+template<typename T> template<typename U>
+sp<T>& sp<T>::operator = (const sp<U>& other)
+{
+    if (other.m_ptr) other.m_ptr->incStrong(this);
+    if (m_ptr) m_ptr->decStrong(this);
+    m_ptr = other.m_ptr;
+    return *this;
+}
+
+template<typename T> template<typename U>
+sp<T>& sp<T>::operator = (U* other)
+{
+    if (other) other->incStrong(this);
+    if (m_ptr) m_ptr->decStrong(this);
+    m_ptr = other;
+    return *this;
+}
+
+template<typename T>
+void sp<T>::clear()
+{
+    if (m_ptr) {
+        m_ptr->decStrong(this);
+        m_ptr = 0;
+    }
+}
+
+// ---------------------------------------------------------------------------
+
+}; // namespace android
+
+// ---------------------------------------------------------------------------
+
+#endif // ANDROID_SMART_POINTER_H