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_SORTED_VECTOR_H 18 #define ANDROID_SORTED_VECTOR_H 19 20 #include <assert.h> 21 #include <stdint.h> 22 #include <sys/types.h> 23 24 #include <log/log.h> 25 #include <utils/TypeHelpers.h> 26 #include <utils/Vector.h> 27 #include <utils/VectorImpl.h> 28 29 // --------------------------------------------------------------------------- 30 31 namespace android { 32 33 template <class TYPE> 34 class SortedVector : private SortedVectorImpl 35 { 36 friend class Vector<TYPE>; 37 38 public: 39 typedef TYPE value_type; 40 41 /*! 42 * Constructors and destructors 43 */ 44 45 SortedVector(); 46 SortedVector(const SortedVector<TYPE>& rhs); 47 virtual ~SortedVector(); 48 49 /*! copy operator */ 50 const SortedVector<TYPE>& operator = (const SortedVector<TYPE>& rhs) const; 51 SortedVector<TYPE>& operator = (const SortedVector<TYPE>& rhs); 52 53 /* 54 * empty the vector 55 */ 56 57 inline void clear() { VectorImpl::clear(); } 58 59 /*! 60 * vector stats 61 */ 62 63 //! returns number of items in the vector 64 inline size_t size() const { return VectorImpl::size(); } 65 //! returns whether or not the vector is empty 66 inline bool isEmpty() const { return VectorImpl::isEmpty(); } 67 //! returns how many items can be stored without reallocating the backing store 68 inline size_t capacity() const { return VectorImpl::capacity(); } 69 //! sets the capacity. capacity can never be reduced less than size() 70 inline ssize_t setCapacity(size_t size) { return VectorImpl::setCapacity(size); } 71 72 /*! 73 * C-style array access 74 */ 75 76 //! read-only C-style access 77 inline const TYPE* array() const; 78 79 //! read-write C-style access. BE VERY CAREFUL when modifying the array 80 //! you must keep it sorted! You usually don't use this function. 81 TYPE* editArray(); 82 83 //! finds the index of an item 84 ssize_t indexOf(const TYPE& item) const; 85 86 //! finds where this item should be inserted 87 size_t orderOf(const TYPE& item) const; 88 89 90 /*! 91 * accessors 92 */ 93 94 //! read-only access to an item at a given index 95 inline const TYPE& operator [] (size_t index) const; 96 //! alternate name for operator [] 97 inline const TYPE& itemAt(size_t index) const; 98 //! stack-usage of the vector. returns the top of the stack (last element) 99 const TYPE& top() const; 100 101 /*! 102 * modifying the array 103 */ 104 105 //! add an item in the right place (and replace the one that is there) 106 ssize_t add(const TYPE& item); 107 108 //! editItemAt() MUST NOT change the order of this item 109 TYPE& editItemAt(size_t index) { 110 return *( static_cast<TYPE *>(VectorImpl::editItemLocation(index)) ); 111 } 112 113 //! merges a vector into this one 114 ssize_t merge(const Vector<TYPE>& vector); 115 ssize_t merge(const SortedVector<TYPE>& vector); 116 117 //! removes an item 118 ssize_t remove(const TYPE&); 119 120 //! remove several items 121 inline ssize_t removeItemsAt(size_t index, size_t count = 1); 122 //! remove one item 123 inline ssize_t removeAt(size_t index) { return removeItemsAt(index); } 124 125 /* 126 * these inlines add some level of compatibility with STL. 127 */ 128 typedef TYPE* iterator; 129 typedef TYPE const* const_iterator; 130 131 inline iterator begin() { return editArray(); } 132 inline iterator end() { return editArray() + size(); } 133 inline const_iterator begin() const { return array(); } 134 inline const_iterator end() const { return array() + size(); } 135 inline void reserve(size_t n) { setCapacity(n); } 136 inline bool empty() const{ return isEmpty(); } 137 inline iterator erase(iterator pos) { 138 ssize_t index = removeItemsAt(pos-array()); 139 return begin() + index; 140 } 141 142 protected: 143 virtual void do_construct(void* storage, size_t num) const; 144 virtual void do_destroy(void* storage, size_t num) const; 145 virtual void do_copy(void* dest, const void* from, size_t num) const; 146 virtual void do_splat(void* dest, const void* item, size_t num) const; 147 virtual void do_move_forward(void* dest, const void* from, size_t num) const; 148 virtual void do_move_backward(void* dest, const void* from, size_t num) const; 149 virtual int do_compare(const void* lhs, const void* rhs) const; 150 }; 151 152 // --------------------------------------------------------------------------- 153 // No user serviceable parts from here... 154 // --------------------------------------------------------------------------- 155 156 template<class TYPE> inline 157 SortedVector<TYPE>::SortedVector() 158 : SortedVectorImpl(sizeof(TYPE), 159 ((traits<TYPE>::has_trivial_ctor ? HAS_TRIVIAL_CTOR : 0) 160 |(traits<TYPE>::has_trivial_dtor ? HAS_TRIVIAL_DTOR : 0) 161 |(traits<TYPE>::has_trivial_copy ? HAS_TRIVIAL_COPY : 0)) 162 ) 163 { 164 } 165 166 template<class TYPE> inline 167 SortedVector<TYPE>::SortedVector(const SortedVector<TYPE>& rhs) 168 : SortedVectorImpl(rhs) { 169 } 170 171 template<class TYPE> inline 172 SortedVector<TYPE>::~SortedVector() { 173 finish_vector(); 174 } 175 176 template<class TYPE> inline 177 SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) { 178 SortedVectorImpl::operator = (rhs); 179 return *this; 180 } 181 182 template<class TYPE> inline 183 const SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) const { 184 SortedVectorImpl::operator = (rhs); 185 return *this; 186 } 187 188 template<class TYPE> inline 189 const TYPE* SortedVector<TYPE>::array() const { 190 return static_cast<const TYPE *>(arrayImpl()); 191 } 192 193 template<class TYPE> inline 194 TYPE* SortedVector<TYPE>::editArray() { 195 return static_cast<TYPE *>(editArrayImpl()); 196 } 197 198 199 template<class TYPE> inline 200 const TYPE& SortedVector<TYPE>::operator[](size_t index) const { 201 LOG_FATAL_IF(index>=size(), 202 "%s: index=%u out of range (%u)", __PRETTY_FUNCTION__, 203 int(index), int(size())); 204 return *(array() + index); 205 } 206 207 template<class TYPE> inline 208 const TYPE& SortedVector<TYPE>::itemAt(size_t index) const { 209 return operator[](index); 210 } 211 212 template<class TYPE> inline 213 const TYPE& SortedVector<TYPE>::top() const { 214 return *(array() + size() - 1); 215 } 216 217 template<class TYPE> inline 218 ssize_t SortedVector<TYPE>::add(const TYPE& item) { 219 return SortedVectorImpl::add(&item); 220 } 221 222 template<class TYPE> inline 223 ssize_t SortedVector<TYPE>::indexOf(const TYPE& item) const { 224 return SortedVectorImpl::indexOf(&item); 225 } 226 227 template<class TYPE> inline 228 size_t SortedVector<TYPE>::orderOf(const TYPE& item) const { 229 return SortedVectorImpl::orderOf(&item); 230 } 231 232 template<class TYPE> inline 233 ssize_t SortedVector<TYPE>::merge(const Vector<TYPE>& vector) { 234 return SortedVectorImpl::merge(reinterpret_cast<const VectorImpl&>(vector)); 235 } 236 237 template<class TYPE> inline 238 ssize_t SortedVector<TYPE>::merge(const SortedVector<TYPE>& vector) { 239 return SortedVectorImpl::merge(reinterpret_cast<const SortedVectorImpl&>(vector)); 240 } 241 242 template<class TYPE> inline 243 ssize_t SortedVector<TYPE>::remove(const TYPE& item) { 244 return SortedVectorImpl::remove(&item); 245 } 246 247 template<class TYPE> inline 248 ssize_t SortedVector<TYPE>::removeItemsAt(size_t index, size_t count) { 249 return VectorImpl::removeItemsAt(index, count); 250 } 251 252 // --------------------------------------------------------------------------- 253 254 template<class TYPE> 255 UTILS_VECTOR_NO_CFI void SortedVector<TYPE>::do_construct(void* storage, size_t num) const { 256 construct_type( reinterpret_cast<TYPE*>(storage), num ); 257 } 258 259 template<class TYPE> 260 void SortedVector<TYPE>::do_destroy(void* storage, size_t num) const { 261 destroy_type( reinterpret_cast<TYPE*>(storage), num ); 262 } 263 264 template<class TYPE> 265 UTILS_VECTOR_NO_CFI void SortedVector<TYPE>::do_copy(void* dest, const void* from, size_t num) const { 266 copy_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num ); 267 } 268 269 template<class TYPE> 270 UTILS_VECTOR_NO_CFI void SortedVector<TYPE>::do_splat(void* dest, const void* item, size_t num) const { 271 splat_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(item), num ); 272 } 273 274 template<class TYPE> 275 UTILS_VECTOR_NO_CFI void SortedVector<TYPE>::do_move_forward(void* dest, const void* from, size_t num) const { 276 move_forward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num ); 277 } 278 279 template<class TYPE> 280 UTILS_VECTOR_NO_CFI void SortedVector<TYPE>::do_move_backward(void* dest, const void* from, size_t num) const { 281 move_backward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num ); 282 } 283 284 template<class TYPE> 285 int SortedVector<TYPE>::do_compare(const void* lhs, const void* rhs) const { 286 return compare_type( *reinterpret_cast<const TYPE*>(lhs), *reinterpret_cast<const TYPE*>(rhs) ); 287 } 288 289 }; // namespace android 290 291 292 // --------------------------------------------------------------------------- 293 294 #endif // ANDROID_SORTED_VECTOR_H 295
