1 /* 2 * vector_impl.h 3 * Android 4 * 5 * Copyright 2005 The Android Open Source Project 6 * 7 */ 8 9 #ifndef ANDROID_VECTOR_IMPL_H 10 #define ANDROID_VECTOR_IMPL_H 11 12 #include <assert.h> 13 #include <stdint.h> 14 #include <sys/types.h> 15 16 // --------------------------------------------------------------------------- 17 // No user serviceable parts in here... 18 // --------------------------------------------------------------------------- 19 20 namespace android { 21 22 /*! 23 * Implementation of the guts of the vector<> class 24 * this ensures backward binary compatibility and 25 * reduces code size. 26 * For performance reasons, we expose mStorage and mCount 27 * so these fields are set in stone. 28 * 29 */ 30 31 class VectorImpl 32 { 33 public: 34 enum { // flags passed to the ctor 35 HAS_TRIVIAL_CTOR = 0x00000001, 36 HAS_TRIVIAL_DTOR = 0x00000002, 37 HAS_TRIVIAL_COPY = 0x00000004, 38 HAS_TRIVIAL_ASSIGN = 0x00000008 39 }; 40 41 VectorImpl(size_t itemSize, uint32_t flags); 42 VectorImpl(const VectorImpl& rhs); 43 virtual ~VectorImpl(); 44 45 /*! must be called from subclasses destructor */ 46 void finish_vector(); 47 48 VectorImpl& operator = (const VectorImpl& rhs); 49 50 /*! C-style array access */ arrayImpl()51 inline const void* arrayImpl() const { return mStorage; } 52 void* editArrayImpl(); 53 54 /*! vector stats */ size()55 inline size_t size() const { return mCount; } isEmpty()56 inline bool isEmpty() const { return mCount == 0; } 57 size_t capacity() const; 58 ssize_t setCapacity(size_t size); 59 60 /*! append/insert another vector */ 61 ssize_t insertVectorAt(const VectorImpl& vector, size_t index); 62 ssize_t appendVector(const VectorImpl& vector); 63 64 /*! add/insert/replace items */ 65 ssize_t insertAt(size_t where, size_t numItems = 1); 66 ssize_t insertAt(const void* item, size_t where, size_t numItems = 1); 67 void pop(); 68 void push(); 69 void push(const void* item); 70 ssize_t add(); 71 ssize_t add(const void* item); 72 ssize_t replaceAt(size_t index); 73 ssize_t replaceAt(const void* item, size_t index); 74 75 /*! remove items */ 76 ssize_t removeItemsAt(size_t index, size_t count = 1); 77 void clear(); 78 79 const void* itemLocation(size_t index) const; 80 void* editItemLocation(size_t index); 81 82 protected: 83 size_t itemSize() const; 84 void release_storage(); 85 86 virtual void do_construct(void* storage, size_t num) const = 0; 87 virtual void do_destroy(void* storage, size_t num) const = 0; 88 virtual void do_copy(void* dest, const void* from, size_t num) const = 0; 89 virtual void do_splat(void* dest, const void* item, size_t num) const = 0; 90 virtual void do_move_forward(void* dest, const void* from, size_t num) const = 0; 91 virtual void do_move_backward(void* dest, const void* from, size_t num) const = 0; 92 93 // take care of FBC... 94 virtual void reservedVectorImpl1(); 95 virtual void reservedVectorImpl2(); 96 virtual void reservedVectorImpl3(); 97 virtual void reservedVectorImpl4(); 98 virtual void reservedVectorImpl5(); 99 virtual void reservedVectorImpl6(); 100 virtual void reservedVectorImpl7(); 101 virtual void reservedVectorImpl8(); 102 103 private: 104 void* _grow(size_t where, size_t amount); 105 void _shrink(size_t where, size_t amount); 106 107 inline void _do_construct(void* storage, size_t num) const; 108 inline void _do_destroy(void* storage, size_t num) const; 109 inline void _do_copy(void* dest, const void* from, size_t num) const; 110 inline void _do_splat(void* dest, const void* item, size_t num) const; 111 inline void _do_move_forward(void* dest, const void* from, size_t num) const; 112 inline void _do_move_backward(void* dest, const void* from, size_t num) const; 113 114 // These 2 fields are exposed in the inlines below, 115 // so they're set in stone. 116 void * mStorage; // base address of the vector 117 size_t mCount; // number of items 118 119 const uint32_t mFlags; 120 const size_t mItemSize; 121 }; 122 123 124 125 class SortedVectorImpl : public VectorImpl 126 { 127 public: 128 SortedVectorImpl(size_t itemSize, uint32_t flags); 129 SortedVectorImpl(const VectorImpl& rhs); 130 virtual ~SortedVectorImpl(); 131 132 SortedVectorImpl& operator = (const SortedVectorImpl& rhs); 133 134 //! finds the index of an item 135 ssize_t indexOf(const void* item) const; 136 137 //! finds where this item should be inserted 138 size_t orderOf(const void* item) const; 139 140 //! add an item in the right place (or replaces it if there is one) 141 ssize_t add(const void* item); 142 143 //! merges a vector into this one 144 ssize_t merge(const VectorImpl& vector); 145 ssize_t merge(const SortedVectorImpl& vector); 146 147 //! removes an item 148 ssize_t remove(const void* item); 149 150 protected: 151 virtual int do_compare(const void* lhs, const void* rhs) const = 0; 152 153 // take care of FBC... 154 virtual void reservedSortedVectorImpl1(); 155 virtual void reservedSortedVectorImpl2(); 156 virtual void reservedSortedVectorImpl3(); 157 virtual void reservedSortedVectorImpl4(); 158 virtual void reservedSortedVectorImpl5(); 159 virtual void reservedSortedVectorImpl6(); 160 virtual void reservedSortedVectorImpl7(); 161 virtual void reservedSortedVectorImpl8(); 162 163 private: 164 ssize_t _indexOrderOf(const void* item, size_t* order = 0) const; 165 166 // these are made private, because they can't be used on a SortedVector 167 // (they don't have an implementation either) 168 ssize_t add(); 169 void pop(); 170 void push(); 171 void push(const void* item); 172 ssize_t insertVectorAt(const VectorImpl& vector, size_t index); 173 ssize_t appendVector(const VectorImpl& vector); 174 ssize_t insertAt(size_t where, size_t numItems = 1); 175 ssize_t insertAt(const void* item, size_t where, size_t numItems = 1); 176 ssize_t replaceAt(size_t index); 177 ssize_t replaceAt(const void* item, size_t index); 178 }; 179 180 }; // namespace android 181 182 183 // --------------------------------------------------------------------------- 184 185 #endif // ANDROID_VECTOR_IMPL_H 186