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
clear()57 inline void clear() { VectorImpl::clear(); }
58
59 /*!
60 * vector stats
61 */
62
63 //! returns number of items in the vector
size()64 inline size_t size() const { return VectorImpl::size(); }
65 //! returns whether or not the vector is empty
isEmpty()66 inline bool isEmpty() const { return VectorImpl::isEmpty(); }
67 //! returns how many items can be stored without reallocating the backing store
capacity()68 inline size_t capacity() const { return VectorImpl::capacity(); }
69 //! sets the capacity. capacity can never be reduced less than size()
setCapacity(size_t 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
editItemAt(size_t index)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
removeAt(size_t index)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
begin()131 inline iterator begin() { return editArray(); }
end()132 inline iterator end() { return editArray() + size(); }
begin()133 inline const_iterator begin() const { return array(); }
end()134 inline const_iterator end() const { return array() + size(); }
reserve(size_t n)135 inline void reserve(size_t n) { setCapacity(n); }
empty()136 inline bool empty() const{ return isEmpty(); }
erase(iterator pos)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
SortedVector()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
SortedVector(const SortedVector<TYPE> & rhs)167 SortedVector<TYPE>::SortedVector(const SortedVector<TYPE>& rhs)
168 : SortedVectorImpl(rhs) {
169 }
170
171 template<class TYPE> inline
~SortedVector()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
array()189 const TYPE* SortedVector<TYPE>::array() const {
190 return static_cast<const TYPE *>(arrayImpl());
191 }
192
193 template<class TYPE> inline
editArray()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
itemAt(size_t index)208 const TYPE& SortedVector<TYPE>::itemAt(size_t index) const {
209 return operator[](index);
210 }
211
212 template<class TYPE> inline
top()213 const TYPE& SortedVector<TYPE>::top() const {
214 return *(array() + size() - 1);
215 }
216
217 template<class TYPE> inline
add(const TYPE & item)218 ssize_t SortedVector<TYPE>::add(const TYPE& item) {
219 return SortedVectorImpl::add(&item);
220 }
221
222 template<class TYPE> inline
indexOf(const TYPE & item)223 ssize_t SortedVector<TYPE>::indexOf(const TYPE& item) const {
224 return SortedVectorImpl::indexOf(&item);
225 }
226
227 template<class TYPE> inline
orderOf(const TYPE & item)228 size_t SortedVector<TYPE>::orderOf(const TYPE& item) const {
229 return SortedVectorImpl::orderOf(&item);
230 }
231
232 template<class TYPE> inline
merge(const Vector<TYPE> & vector)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
merge(const SortedVector<TYPE> & vector)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
remove(const TYPE & item)243 ssize_t SortedVector<TYPE>::remove(const TYPE& item) {
244 return SortedVectorImpl::remove(&item);
245 }
246
247 template<class TYPE> inline
removeItemsAt(size_t index,size_t count)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>
do_construct(void * storage,size_t num)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>
do_destroy(void * storage,size_t num)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>
do_copy(void * dest,const void * from,size_t num)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>
do_splat(void * dest,const void * item,size_t num)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>
do_move_forward(void * dest,const void * from,size_t num)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>
do_move_backward(void * dest,const void * from,size_t num)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>
do_compare(const void * lhs,const void * rhs)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