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