1 /* 2 * Copyright (C) 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_VECTOR_IMPL_H 18 #define ANDROID_VECTOR_IMPL_H 19 20 #include <assert.h> 21 #include <stdint.h> 22 #include <sys/types.h> 23 #include <utils/Errors.h> 24 25 // --------------------------------------------------------------------------- 26 // No user serviceable parts in here... 27 // --------------------------------------------------------------------------- 28 29 namespace android { 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 }; 48 49 VectorImpl(size_t itemSize, uint32_t flags); 50 VectorImpl(const VectorImpl& rhs); 51 virtual ~VectorImpl(); 52 53 /*! must be called from subclasses destructor */ 54 void finish_vector(); 55 56 VectorImpl& operator = (const VectorImpl& rhs); 57 58 /*! C-style array access */ arrayImpl()59 inline const void* arrayImpl() const { return mStorage; } 60 void* editArrayImpl(); 61 62 /*! vector stats */ size()63 inline size_t size() const { return mCount; } isEmpty()64 inline bool isEmpty() const { return mCount == 0; } 65 size_t capacity() const; 66 ssize_t setCapacity(size_t size); 67 ssize_t resize(size_t size); 68 69 /*! append/insert another vector or array */ 70 ssize_t insertVectorAt(const VectorImpl& vector, size_t index); 71 ssize_t appendVector(const VectorImpl& vector); 72 ssize_t insertArrayAt(const void* array, size_t index, size_t length); 73 ssize_t appendArray(const void* array, size_t length); 74 75 /*! add/insert/replace items */ 76 ssize_t insertAt(size_t where, size_t numItems = 1); 77 ssize_t insertAt(const void* item, size_t where, size_t numItems = 1); 78 void pop(); 79 void push(); 80 void push(const void* item); 81 ssize_t add(); 82 ssize_t add(const void* item); 83 ssize_t replaceAt(size_t index); 84 ssize_t replaceAt(const void* item, size_t index); 85 86 /*! remove items */ 87 ssize_t removeItemsAt(size_t index, size_t count = 1); 88 void clear(); 89 90 const void* itemLocation(size_t index) const; 91 void* editItemLocation(size_t index); 92 93 typedef int (*compar_t)(const void* lhs, const void* rhs); 94 typedef int (*compar_r_t)(const void* lhs, const void* rhs, void* state); 95 status_t sort(compar_t cmp); 96 status_t sort(compar_r_t cmp, void* state); 97 98 protected: 99 size_t itemSize() const; 100 void release_storage(); 101 102 virtual void do_construct(void* storage, size_t num) const = 0; 103 virtual void do_destroy(void* storage, size_t num) const = 0; 104 virtual void do_copy(void* dest, const void* from, size_t num) const = 0; 105 virtual void do_splat(void* dest, const void* item, size_t num) const = 0; 106 virtual void do_move_forward(void* dest, const void* from, size_t num) const = 0; 107 virtual void do_move_backward(void* dest, const void* from, size_t num) const = 0; 108 109 // take care of FBC... 110 virtual void reservedVectorImpl1(); 111 virtual void reservedVectorImpl2(); 112 virtual void reservedVectorImpl3(); 113 virtual void reservedVectorImpl4(); 114 virtual void reservedVectorImpl5(); 115 virtual void reservedVectorImpl6(); 116 virtual void reservedVectorImpl7(); 117 virtual void reservedVectorImpl8(); 118 119 private: 120 void* _grow(size_t where, size_t amount); 121 void _shrink(size_t where, size_t amount); 122 123 inline void _do_construct(void* storage, size_t num) const; 124 inline void _do_destroy(void* storage, size_t num) const; 125 inline void _do_copy(void* dest, const void* from, size_t num) const; 126 inline void _do_splat(void* dest, const void* item, size_t num) const; 127 inline void _do_move_forward(void* dest, const void* from, size_t num) const; 128 inline void _do_move_backward(void* dest, const void* from, size_t num) const; 129 130 // These 2 fields are exposed in the inlines below, 131 // so they're set in stone. 132 void * mStorage; // base address of the vector 133 size_t mCount; // number of items 134 135 const uint32_t mFlags; 136 const size_t mItemSize; 137 }; 138 139 140 141 class SortedVectorImpl : public VectorImpl 142 { 143 public: 144 SortedVectorImpl(size_t itemSize, uint32_t flags); 145 SortedVectorImpl(const VectorImpl& rhs); 146 virtual ~SortedVectorImpl(); 147 148 SortedVectorImpl& operator = (const SortedVectorImpl& rhs); 149 150 //! finds the index of an item 151 ssize_t indexOf(const void* item) const; 152 153 //! finds where this item should be inserted 154 size_t orderOf(const void* item) const; 155 156 //! add an item in the right place (or replaces it if there is one) 157 ssize_t add(const void* item); 158 159 //! merges a vector into this one 160 ssize_t merge(const VectorImpl& vector); 161 ssize_t merge(const SortedVectorImpl& vector); 162 163 //! removes an item 164 ssize_t remove(const void* item); 165 166 protected: 167 virtual int do_compare(const void* lhs, const void* rhs) const = 0; 168 169 // take care of FBC... 170 virtual void reservedSortedVectorImpl1(); 171 virtual void reservedSortedVectorImpl2(); 172 virtual void reservedSortedVectorImpl3(); 173 virtual void reservedSortedVectorImpl4(); 174 virtual void reservedSortedVectorImpl5(); 175 virtual void reservedSortedVectorImpl6(); 176 virtual void reservedSortedVectorImpl7(); 177 virtual void reservedSortedVectorImpl8(); 178 179 private: 180 ssize_t _indexOrderOf(const void* item, size_t* order = 0) const; 181 182 // these are made private, because they can't be used on a SortedVector 183 // (they don't have an implementation either) 184 ssize_t add(); 185 void pop(); 186 void push(); 187 void push(const void* item); 188 ssize_t insertVectorAt(const VectorImpl& vector, size_t index); 189 ssize_t appendVector(const VectorImpl& vector); 190 ssize_t insertArrayAt(const void* array, size_t index, size_t length); 191 ssize_t appendArray(const void* array, size_t length); 192 ssize_t insertAt(size_t where, size_t numItems = 1); 193 ssize_t insertAt(const void* item, size_t where, size_t numItems = 1); 194 ssize_t replaceAt(size_t index); 195 ssize_t replaceAt(const void* item, size_t index); 196 }; 197 198 }; // namespace android 199 200 201 // --------------------------------------------------------------------------- 202 203 #endif // ANDROID_VECTOR_IMPL_H 204