Initial Contribution
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