2
* Copyright (C) 2005 The Android Open Source Project
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
8
* http://www.apache.org/licenses/LICENSE-2.0
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.
17
#define LOG_TAG "Vector"
23
#include <utils/Log.h>
24
#include <utils/Errors.h>
25
#include <utils/SharedBuffer.h>
26
#include <utils/VectorImpl.h>
28
/*****************************************************************************/
33
// ----------------------------------------------------------------------------
35
const size_t kMinVectorCapacity = 4;
37
static inline size_t max(size_t a, size_t b) {
41
// ----------------------------------------------------------------------------
43
VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
44
: mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize)
48
VectorImpl::VectorImpl(const VectorImpl& rhs)
49
: mStorage(rhs.mStorage), mCount(rhs.mCount),
50
mFlags(rhs.mFlags), mItemSize(rhs.mItemSize)
53
SharedBuffer::sharedBuffer(mStorage)->acquire();
57
VectorImpl::~VectorImpl()
61
"subclasses of VectorImpl must call finish_vector()"
62
" in their destructor. Leaking %d bytes.",
63
this, (int)(mCount*mItemSize));
64
// We can't call _do_destroy() here because the vtable is already gone.
67
VectorImpl& VectorImpl::operator = (const VectorImpl& rhs)
69
ALOG_ASSERT(mItemSize == rhs.mItemSize,
70
"Vector<> have different types (this=%p, rhs=%p)", this, &rhs);
74
mStorage = rhs.mStorage;
76
SharedBuffer::sharedBuffer(mStorage)->acquire();
85
void* VectorImpl::editArrayImpl()
88
SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage)->attemptEdit();
90
sb = SharedBuffer::alloc(capacity() * mItemSize);
92
_do_copy(sb->data(), mStorage, mCount);
94
mStorage = sb->data();
101
size_t VectorImpl::capacity() const
104
return SharedBuffer::sharedBuffer(mStorage)->size() / mItemSize;
109
ssize_t VectorImpl::insertVectorAt(const VectorImpl& vector, size_t index)
111
return insertArrayAt(vector.arrayImpl(), index, vector.size());
114
ssize_t VectorImpl::appendVector(const VectorImpl& vector)
116
return insertVectorAt(vector, size());
119
ssize_t VectorImpl::insertArrayAt(const void* array, size_t index, size_t length)
123
void* where = _grow(index, length);
125
_do_copy(where, array, length);
127
return where ? index : (ssize_t)NO_MEMORY;
130
ssize_t VectorImpl::appendArray(const void* array, size_t length)
132
return insertArrayAt(array, size(), length);
135
ssize_t VectorImpl::insertAt(size_t index, size_t numItems)
137
return insertAt(0, index, numItems);
140
ssize_t VectorImpl::insertAt(const void* item, size_t index, size_t numItems)
144
void* where = _grow(index, numItems);
147
_do_splat(where, item, numItems);
149
_do_construct(where, numItems);
152
return where ? index : (ssize_t)NO_MEMORY;
155
static int sortProxy(const void* lhs, const void* rhs, void* func)
157
return (*(VectorImpl::compar_t)func)(lhs, rhs);
160
status_t VectorImpl::sort(VectorImpl::compar_t cmp)
162
return sort(sortProxy, (void*)cmp);
165
status_t VectorImpl::sort(VectorImpl::compar_r_t cmp, void* state)
167
// the sort must be stable. we're using insertion sort which
168
// is well suited for small and already sorted arrays
169
// for big arrays, it could be better to use mergesort
170
const ssize_t count = size();
172
void* array = const_cast<void*>(arrayImpl());
176
void* item = reinterpret_cast<char*>(array) + mItemSize*(i);
177
void* curr = reinterpret_cast<char*>(array) + mItemSize*(i-1);
178
if (cmp(curr, item, state) > 0) {
181
// we're going to have to modify the array...
182
array = editArrayImpl();
183
if (!array) return NO_MEMORY;
184
temp = malloc(mItemSize);
185
if (!temp) return NO_MEMORY;
186
item = reinterpret_cast<char*>(array) + mItemSize*(i);
187
curr = reinterpret_cast<char*>(array) + mItemSize*(i-1);
189
_do_destroy(temp, 1);
192
_do_copy(temp, item, 1);
195
void* next = reinterpret_cast<char*>(array) + mItemSize*(i);
197
_do_destroy(next, 1);
198
_do_copy(next, curr, 1);
201
curr = reinterpret_cast<char*>(array) + mItemSize*(j);
202
} while (j>=0 && (cmp(curr, temp, state) > 0));
204
_do_destroy(next, 1);
205
_do_copy(next, temp, 1);
211
_do_destroy(temp, 1);
218
void VectorImpl::pop()
221
removeItemsAt(size()-1, 1);
224
void VectorImpl::push()
229
void VectorImpl::push(const void* item)
231
insertAt(item, size());
234
ssize_t VectorImpl::add()
239
ssize_t VectorImpl::add(const void* item)
241
return insertAt(item, size());
244
ssize_t VectorImpl::replaceAt(size_t index)
246
return replaceAt(0, index);
249
ssize_t VectorImpl::replaceAt(const void* prototype, size_t index)
251
ALOG_ASSERT(index<size(),
252
"[%p] replace: index=%d, size=%d", this, (int)index, (int)size());
254
void* item = editItemLocation(index);
255
if (item != prototype) {
258
_do_destroy(item, 1);
259
if (prototype == 0) {
260
_do_construct(item, 1);
262
_do_copy(item, prototype, 1);
265
return ssize_t(index);
268
ssize_t VectorImpl::removeItemsAt(size_t index, size_t count)
270
ALOG_ASSERT((index+count)<=size(),
271
"[%p] remove: index=%d, count=%d, size=%d",
272
this, (int)index, (int)count, (int)size());
274
if ((index+count) > size())
276
_shrink(index, count);
280
void VectorImpl::finish_vector()
287
void VectorImpl::clear()
292
void* VectorImpl::editItemLocation(size_t index)
294
ALOG_ASSERT(index<capacity(),
295
"[%p] editItemLocation: index=%d, capacity=%d, count=%d",
296
this, (int)index, (int)capacity(), (int)mCount);
298
void* buffer = editArrayImpl();
300
return reinterpret_cast<char*>(buffer) + index*mItemSize;
304
const void* VectorImpl::itemLocation(size_t index) const
306
ALOG_ASSERT(index<capacity(),
307
"[%p] itemLocation: index=%d, capacity=%d, count=%d",
308
this, (int)index, (int)capacity(), (int)mCount);
310
const void* buffer = arrayImpl();
312
return reinterpret_cast<const char*>(buffer) + index*mItemSize;
316
ssize_t VectorImpl::setCapacity(size_t new_capacity)
318
size_t current_capacity = capacity();
319
ssize_t amount = new_capacity - size();
321
// we can't reduce the capacity
322
return current_capacity;
324
SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
326
void* array = sb->data();
327
_do_copy(array, mStorage, size());
329
mStorage = const_cast<void*>(array);
336
void VectorImpl::release_storage()
339
const SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage);
340
if (sb->release(SharedBuffer::eKeepStorage) == 1) {
341
_do_destroy(mStorage, mCount);
342
SharedBuffer::dealloc(sb);
347
void* VectorImpl::_grow(size_t where, size_t amount)
349
// ALOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
350
// this, (int)where, (int)amount, (int)mCount, (int)capacity());
352
ALOG_ASSERT(where <= mCount,
353
"[%p] _grow: where=%d, amount=%d, count=%d",
354
this, (int)where, (int)amount, (int)mCount); // caller already checked
356
const size_t new_size = mCount + amount;
357
if (capacity() < new_size) {
358
const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2);
359
// ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
362
(mFlags & HAS_TRIVIAL_COPY) &&
363
(mFlags & HAS_TRIVIAL_DTOR))
365
const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
366
SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
367
mStorage = sb->data();
369
SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
371
void* array = sb->data();
373
_do_copy(array, mStorage, where);
375
if (where != mCount) {
376
const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize;
377
void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
378
_do_copy(dest, from, mCount-where);
381
mStorage = const_cast<void*>(array);
385
void* array = editArrayImpl();
386
if (where != mCount) {
387
const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize;
388
void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
389
_do_move_forward(to, from, mCount - where);
393
void* free_space = const_cast<void*>(itemLocation(where));
397
void VectorImpl::_shrink(size_t where, size_t amount)
402
// ALOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
403
// this, (int)where, (int)amount, (int)mCount, (int)capacity());
405
ALOG_ASSERT(where + amount <= mCount,
406
"[%p] _shrink: where=%d, amount=%d, count=%d",
407
this, (int)where, (int)amount, (int)mCount); // caller already checked
409
const size_t new_size = mCount - amount;
410
if (new_size*3 < capacity()) {
411
const size_t new_capacity = max(kMinVectorCapacity, new_size*2);
412
// ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
413
if ((where == new_size) &&
414
(mFlags & HAS_TRIVIAL_COPY) &&
415
(mFlags & HAS_TRIVIAL_DTOR))
417
const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
418
SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
419
mStorage = sb->data();
421
SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
423
void* array = sb->data();
425
_do_copy(array, mStorage, where);
427
if (where != new_size) {
428
const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize;
429
void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
430
_do_copy(dest, from, new_size - where);
433
mStorage = const_cast<void*>(array);
437
void* array = editArrayImpl();
438
void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
439
_do_destroy(to, amount);
440
if (where != new_size) {
441
const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
442
_do_move_backward(to, from, new_size - where);
448
size_t VectorImpl::itemSize() const {
452
void VectorImpl::_do_construct(void* storage, size_t num) const
454
if (!(mFlags & HAS_TRIVIAL_CTOR)) {
455
do_construct(storage, num);
459
void VectorImpl::_do_destroy(void* storage, size_t num) const
461
if (!(mFlags & HAS_TRIVIAL_DTOR)) {
462
do_destroy(storage, num);
466
void VectorImpl::_do_copy(void* dest, const void* from, size_t num) const
468
if (!(mFlags & HAS_TRIVIAL_COPY)) {
469
do_copy(dest, from, num);
471
memcpy(dest, from, num*itemSize());
475
void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
476
do_splat(dest, item, num);
479
void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
480
do_move_forward(dest, from, num);
483
void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
484
do_move_backward(dest, from, num);
487
void VectorImpl::reservedVectorImpl1() { }
488
void VectorImpl::reservedVectorImpl2() { }
489
void VectorImpl::reservedVectorImpl3() { }
490
void VectorImpl::reservedVectorImpl4() { }
491
void VectorImpl::reservedVectorImpl5() { }
492
void VectorImpl::reservedVectorImpl6() { }
493
void VectorImpl::reservedVectorImpl7() { }
494
void VectorImpl::reservedVectorImpl8() { }
496
/*****************************************************************************/
498
SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
499
: VectorImpl(itemSize, flags)
503
SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
508
SortedVectorImpl::~SortedVectorImpl()
512
SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
514
return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
517
ssize_t SortedVectorImpl::indexOf(const void* item) const
519
return _indexOrderOf(item);
522
size_t SortedVectorImpl::orderOf(const void* item) const
525
_indexOrderOf(item, &o);
529
ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
532
ssize_t err = NAME_NOT_FOUND;
534
ssize_t h = size()-1;
536
const void* a = arrayImpl();
537
const size_t s = itemSize();
540
const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
541
const int c = do_compare(curr, item);
551
if (order) *order = l;
555
ssize_t SortedVectorImpl::add(const void* item)
558
ssize_t index = _indexOrderOf(item, &order);
560
index = VectorImpl::insertAt(item, order, 1);
562
index = VectorImpl::replaceAt(item, index);
567
ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
570
if (!vector.isEmpty()) {
571
const void* buffer = vector.arrayImpl();
572
const size_t is = itemSize();
573
size_t s = vector.size();
574
for (size_t i=0 ; i<s ; i++) {
575
ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
584
ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
586
// we've merging a sorted vector... nice!
587
ssize_t err = NO_ERROR;
588
if (!vector.isEmpty()) {
589
// first take care of the case where the vectors are sorted together
590
if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
591
err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
592
} else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
593
err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
595
// this could be made a little better
596
err = merge(static_cast<const VectorImpl&>(vector));
602
ssize_t SortedVectorImpl::remove(const void* item)
604
ssize_t i = indexOf(item);
606
VectorImpl::removeItemsAt(i, 1);
611
void SortedVectorImpl::reservedSortedVectorImpl1() { };
612
void SortedVectorImpl::reservedSortedVectorImpl2() { };
613
void SortedVectorImpl::reservedSortedVectorImpl3() { };
614
void SortedVectorImpl::reservedSortedVectorImpl4() { };
615
void SortedVectorImpl::reservedSortedVectorImpl5() { };
616
void SortedVectorImpl::reservedSortedVectorImpl6() { };
617
void SortedVectorImpl::reservedSortedVectorImpl7() { };
618
void SortedVectorImpl::reservedSortedVectorImpl8() { };
621
/*****************************************************************************/
623
}; // namespace android
added
removed
3rd_party/android-input/android/frameworks/native/libs/utils/VectorImpl.cpp
