← Back to branch summary

~mir-team/mir/in-process-egl+input-conglomeration

« back to all changes in this revision

Viewing changes to 3rd_party/android-deps/utils/SortedVector.h

Merged trunk and fixed issues

Show diffs side-by-side

added added

removed removed

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