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