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 #define LOG_TAG "Vector"
18
19 #include <string.h>
20 #include <stdlib.h>
21 #include <stdio.h>
22
23 #include <cutils/log.h>
24
25 #include <utils/Errors.h>
26 #include <utils/SharedBuffer.h>
27 #include <utils/VectorImpl.h>
28
29 /*****************************************************************************/
30
31
32 namespace android {
33
34 // ----------------------------------------------------------------------------
35
36 const size_t kMinVectorCapacity = 4;
37
max(size_t a,size_t b)38 static inline size_t max(size_t a, size_t b) {
39 return a>b ? a : b;
40 }
41
42 // ----------------------------------------------------------------------------
43
VectorImpl(size_t itemSize,uint32_t flags)44 VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
45 : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize)
46 {
47 }
48
VectorImpl(const VectorImpl & rhs)49 VectorImpl::VectorImpl(const VectorImpl& rhs)
50 : mStorage(rhs.mStorage), mCount(rhs.mCount),
51 mFlags(rhs.mFlags), mItemSize(rhs.mItemSize)
52 {
53 if (mStorage) {
54 SharedBuffer::bufferFromData(mStorage)->acquire();
55 }
56 }
57
~VectorImpl()58 VectorImpl::~VectorImpl()
59 {
60 ALOGW_IF(mCount,
61 "[%p] 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.
65 }
66
operator =(const VectorImpl & rhs)67 VectorImpl& VectorImpl::operator = (const VectorImpl& rhs)
68 {
69 LOG_ALWAYS_FATAL_IF(mItemSize != rhs.mItemSize,
70 "Vector<> have different types (this=%p, rhs=%p)", this, &rhs);
71 if (this != &rhs) {
72 release_storage();
73 if (rhs.mCount) {
74 mStorage = rhs.mStorage;
75 mCount = rhs.mCount;
76 SharedBuffer::bufferFromData(mStorage)->acquire();
77 } else {
78 mStorage = 0;
79 mCount = 0;
80 }
81 }
82 return *this;
83 }
84
editArrayImpl()85 void* VectorImpl::editArrayImpl()
86 {
87 if (mStorage) {
88 SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage)->attemptEdit();
89 if (sb == 0) {
90 sb = SharedBuffer::alloc(capacity() * mItemSize);
91 if (sb) {
92 _do_copy(sb->data(), mStorage, mCount);
93 release_storage();
94 mStorage = sb->data();
95 }
96 }
97 }
98 return mStorage;
99 }
100
capacity() const101 size_t VectorImpl::capacity() const
102 {
103 if (mStorage) {
104 return SharedBuffer::bufferFromData(mStorage)->size() / mItemSize;
105 }
106 return 0;
107 }
108
insertVectorAt(const VectorImpl & vector,size_t index)109 ssize_t VectorImpl::insertVectorAt(const VectorImpl& vector, size_t index)
110 {
111 return insertArrayAt(vector.arrayImpl(), index, vector.size());
112 }
113
appendVector(const VectorImpl & vector)114 ssize_t VectorImpl::appendVector(const VectorImpl& vector)
115 {
116 return insertVectorAt(vector, size());
117 }
118
insertArrayAt(const void * array,size_t index,size_t length)119 ssize_t VectorImpl::insertArrayAt(const void* array, size_t index, size_t length)
120 {
121 if (index > size())
122 return BAD_INDEX;
123 void* where = _grow(index, length);
124 if (where) {
125 _do_copy(where, array, length);
126 }
127 return where ? index : (ssize_t)NO_MEMORY;
128 }
129
appendArray(const void * array,size_t length)130 ssize_t VectorImpl::appendArray(const void* array, size_t length)
131 {
132 return insertArrayAt(array, size(), length);
133 }
134
insertAt(size_t index,size_t numItems)135 ssize_t VectorImpl::insertAt(size_t index, size_t numItems)
136 {
137 return insertAt(0, index, numItems);
138 }
139
insertAt(const void * item,size_t index,size_t numItems)140 ssize_t VectorImpl::insertAt(const void* item, size_t index, size_t numItems)
141 {
142 if (index > size())
143 return BAD_INDEX;
144 void* where = _grow(index, numItems);
145 if (where) {
146 if (item) {
147 _do_splat(where, item, numItems);
148 } else {
149 _do_construct(where, numItems);
150 }
151 }
152 return where ? index : (ssize_t)NO_MEMORY;
153 }
154
sortProxy(const void * lhs,const void * rhs,void * func)155 static int sortProxy(const void* lhs, const void* rhs, void* func)
156 {
157 return (*(VectorImpl::compar_t)func)(lhs, rhs);
158 }
159
sort(VectorImpl::compar_t cmp)160 status_t VectorImpl::sort(VectorImpl::compar_t cmp)
161 {
162 return sort(sortProxy, (void*)cmp);
163 }
164
sort(VectorImpl::compar_r_t cmp,void * state)165 status_t VectorImpl::sort(VectorImpl::compar_r_t cmp, void* state)
166 {
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();
171 if (count > 1) {
172 void* array = const_cast<void*>(arrayImpl());
173 void* temp = 0;
174 ssize_t i = 1;
175 while (i < count) {
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) {
179
180 if (!temp) {
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);
188 } else {
189 _do_destroy(temp, 1);
190 }
191
192 _do_copy(temp, item, 1);
193
194 ssize_t j = i-1;
195 void* next = reinterpret_cast<char*>(array) + mItemSize*(i);
196 do {
197 _do_destroy(next, 1);
198 _do_copy(next, curr, 1);
199 next = curr;
200 --j;
201 curr = reinterpret_cast<char*>(array) + mItemSize*(j);
202 } while (j>=0 && (cmp(curr, temp, state) > 0));
203
204 _do_destroy(next, 1);
205 _do_copy(next, temp, 1);
206 }
207 i++;
208 }
209
210 if (temp) {
211 _do_destroy(temp, 1);
212 free(temp);
213 }
214 }
215 return NO_ERROR;
216 }
217
pop()218 void VectorImpl::pop()
219 {
220 if (size())
221 removeItemsAt(size()-1, 1);
222 }
223
push()224 void VectorImpl::push()
225 {
226 push(0);
227 }
228
push(const void * item)229 void VectorImpl::push(const void* item)
230 {
231 insertAt(item, size());
232 }
233
add()234 ssize_t VectorImpl::add()
235 {
236 return add(0);
237 }
238
add(const void * item)239 ssize_t VectorImpl::add(const void* item)
240 {
241 return insertAt(item, size());
242 }
243
replaceAt(size_t index)244 ssize_t VectorImpl::replaceAt(size_t index)
245 {
246 return replaceAt(0, index);
247 }
248
replaceAt(const void * prototype,size_t index)249 ssize_t VectorImpl::replaceAt(const void* prototype, size_t index)
250 {
251 ALOG_ASSERT(index<size(),
252 "[%p] replace: index=%d, size=%d", this, (int)index, (int)size());
253
254 if (index >= size()) {
255 return BAD_INDEX;
256 }
257
258 void* item = editItemLocation(index);
259 if (item != prototype) {
260 if (item == 0)
261 return NO_MEMORY;
262 _do_destroy(item, 1);
263 if (prototype == 0) {
264 _do_construct(item, 1);
265 } else {
266 _do_copy(item, prototype, 1);
267 }
268 }
269 return ssize_t(index);
270 }
271
removeItemsAt(size_t index,size_t count)272 ssize_t VectorImpl::removeItemsAt(size_t index, size_t count)
273 {
274 ALOG_ASSERT((index+count)<=size(),
275 "[%p] remove: index=%d, count=%d, size=%d",
276 this, (int)index, (int)count, (int)size());
277
278 if ((index+count) > size())
279 return BAD_VALUE;
280 _shrink(index, count);
281 return index;
282 }
283
finish_vector()284 void VectorImpl::finish_vector()
285 {
286 release_storage();
287 mStorage = 0;
288 mCount = 0;
289 }
290
clear()291 void VectorImpl::clear()
292 {
293 _shrink(0, mCount);
294 }
295
editItemLocation(size_t index)296 void* VectorImpl::editItemLocation(size_t index)
297 {
298 ALOG_ASSERT(index<capacity(),
299 "[%p] editItemLocation: index=%d, capacity=%d, count=%d",
300 this, (int)index, (int)capacity(), (int)mCount);
301
302 if (index < capacity()) {
303 void* buffer = editArrayImpl();
304 if (buffer) {
305 return reinterpret_cast<char*>(buffer) + index*mItemSize;
306 }
307 }
308 return 0;
309 }
310
itemLocation(size_t index) const311 const void* VectorImpl::itemLocation(size_t index) const
312 {
313 ALOG_ASSERT(index<capacity(),
314 "[%p] itemLocation: index=%d, capacity=%d, count=%d",
315 this, (int)index, (int)capacity(), (int)mCount);
316
317 if (index < capacity()) {
318 const void* buffer = arrayImpl();
319 if (buffer) {
320 return reinterpret_cast<const char*>(buffer) + index*mItemSize;
321 }
322 }
323 return 0;
324 }
325
setCapacity(size_t new_capacity)326 ssize_t VectorImpl::setCapacity(size_t new_capacity)
327 {
328 size_t current_capacity = capacity();
329 ssize_t amount = new_capacity - size();
330 if (amount <= 0) {
331 // we can't reduce the capacity
332 return current_capacity;
333 }
334 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
335 if (sb) {
336 void* array = sb->data();
337 _do_copy(array, mStorage, size());
338 release_storage();
339 mStorage = const_cast<void*>(array);
340 } else {
341 return NO_MEMORY;
342 }
343 return new_capacity;
344 }
345
resize(size_t size)346 ssize_t VectorImpl::resize(size_t size) {
347 ssize_t result = NO_ERROR;
348 if (size > mCount) {
349 result = insertAt(mCount, size - mCount);
350 } else if (size < mCount) {
351 result = removeItemsAt(size, mCount - size);
352 }
353 return result < 0 ? result : size;
354 }
355
release_storage()356 void VectorImpl::release_storage()
357 {
358 if (mStorage) {
359 const SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage);
360 if (sb->release(SharedBuffer::eKeepStorage) == 1) {
361 _do_destroy(mStorage, mCount);
362 SharedBuffer::dealloc(sb);
363 }
364 }
365 }
366
_grow(size_t where,size_t amount)367 void* VectorImpl::_grow(size_t where, size_t amount)
368 {
369 // ALOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
370 // this, (int)where, (int)amount, (int)mCount, (int)capacity());
371
372 ALOG_ASSERT(where <= mCount,
373 "[%p] _grow: where=%d, amount=%d, count=%d",
374 this, (int)where, (int)amount, (int)mCount); // caller already checked
375
376 const size_t new_size = mCount + amount;
377 if (capacity() < new_size) {
378 const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2);
379 // ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
380 if ((mStorage) &&
381 (mCount==where) &&
382 (mFlags & HAS_TRIVIAL_COPY) &&
383 (mFlags & HAS_TRIVIAL_DTOR))
384 {
385 const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage);
386 SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
387 mStorage = sb->data();
388 } else {
389 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
390 if (sb) {
391 void* array = sb->data();
392 if (where != 0) {
393 _do_copy(array, mStorage, where);
394 }
395 if (where != mCount) {
396 const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize;
397 void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
398 _do_copy(dest, from, mCount-where);
399 }
400 release_storage();
401 mStorage = const_cast<void*>(array);
402 }
403 }
404 } else {
405 void* array = editArrayImpl();
406 if (where != mCount) {
407 const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize;
408 void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
409 _do_move_forward(to, from, mCount - where);
410 }
411 }
412 mCount = new_size;
413 void* free_space = const_cast<void*>(itemLocation(where));
414 return free_space;
415 }
416
_shrink(size_t where,size_t amount)417 void VectorImpl::_shrink(size_t where, size_t amount)
418 {
419 if (!mStorage)
420 return;
421
422 // ALOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
423 // this, (int)where, (int)amount, (int)mCount, (int)capacity());
424
425 ALOG_ASSERT(where + amount <= mCount,
426 "[%p] _shrink: where=%d, amount=%d, count=%d",
427 this, (int)where, (int)amount, (int)mCount); // caller already checked
428
429 const size_t new_size = mCount - amount;
430 if (new_size*3 < capacity()) {
431 const size_t new_capacity = max(kMinVectorCapacity, new_size*2);
432 // ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
433 if ((where == new_size) &&
434 (mFlags & HAS_TRIVIAL_COPY) &&
435 (mFlags & HAS_TRIVIAL_DTOR))
436 {
437 const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage);
438 SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
439 mStorage = sb->data();
440 } else {
441 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
442 if (sb) {
443 void* array = sb->data();
444 if (where != 0) {
445 _do_copy(array, mStorage, where);
446 }
447 if (where != new_size) {
448 const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize;
449 void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
450 _do_copy(dest, from, new_size - where);
451 }
452 release_storage();
453 mStorage = const_cast<void*>(array);
454 }
455 }
456 } else {
457 void* array = editArrayImpl();
458 void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
459 _do_destroy(to, amount);
460 if (where != new_size) {
461 const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
462 _do_move_backward(to, from, new_size - where);
463 }
464 }
465 mCount = new_size;
466 }
467
itemSize() const468 size_t VectorImpl::itemSize() const {
469 return mItemSize;
470 }
471
_do_construct(void * storage,size_t num) const472 void VectorImpl::_do_construct(void* storage, size_t num) const
473 {
474 if (!(mFlags & HAS_TRIVIAL_CTOR)) {
475 do_construct(storage, num);
476 }
477 }
478
_do_destroy(void * storage,size_t num) const479 void VectorImpl::_do_destroy(void* storage, size_t num) const
480 {
481 if (!(mFlags & HAS_TRIVIAL_DTOR)) {
482 do_destroy(storage, num);
483 }
484 }
485
_do_copy(void * dest,const void * from,size_t num) const486 void VectorImpl::_do_copy(void* dest, const void* from, size_t num) const
487 {
488 if (!(mFlags & HAS_TRIVIAL_COPY)) {
489 do_copy(dest, from, num);
490 } else {
491 memcpy(dest, from, num*itemSize());
492 }
493 }
494
_do_splat(void * dest,const void * item,size_t num) const495 void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
496 do_splat(dest, item, num);
497 }
498
_do_move_forward(void * dest,const void * from,size_t num) const499 void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
500 do_move_forward(dest, from, num);
501 }
502
_do_move_backward(void * dest,const void * from,size_t num) const503 void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
504 do_move_backward(dest, from, num);
505 }
506
reservedVectorImpl1()507 void VectorImpl::reservedVectorImpl1() { }
reservedVectorImpl2()508 void VectorImpl::reservedVectorImpl2() { }
reservedVectorImpl3()509 void VectorImpl::reservedVectorImpl3() { }
reservedVectorImpl4()510 void VectorImpl::reservedVectorImpl4() { }
reservedVectorImpl5()511 void VectorImpl::reservedVectorImpl5() { }
reservedVectorImpl6()512 void VectorImpl::reservedVectorImpl6() { }
reservedVectorImpl7()513 void VectorImpl::reservedVectorImpl7() { }
reservedVectorImpl8()514 void VectorImpl::reservedVectorImpl8() { }
515
516 /*****************************************************************************/
517
SortedVectorImpl(size_t itemSize,uint32_t flags)518 SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
519 : VectorImpl(itemSize, flags)
520 {
521 }
522
SortedVectorImpl(const VectorImpl & rhs)523 SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
524 : VectorImpl(rhs)
525 {
526 }
527
~SortedVectorImpl()528 SortedVectorImpl::~SortedVectorImpl()
529 {
530 }
531
operator =(const SortedVectorImpl & rhs)532 SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
533 {
534 return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
535 }
536
indexOf(const void * item) const537 ssize_t SortedVectorImpl::indexOf(const void* item) const
538 {
539 return _indexOrderOf(item);
540 }
541
orderOf(const void * item) const542 size_t SortedVectorImpl::orderOf(const void* item) const
543 {
544 size_t o;
545 _indexOrderOf(item, &o);
546 return o;
547 }
548
_indexOrderOf(const void * item,size_t * order) const549 ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
550 {
551 // binary search
552 ssize_t err = NAME_NOT_FOUND;
553 ssize_t l = 0;
554 ssize_t h = size()-1;
555 ssize_t mid;
556 const void* a = arrayImpl();
557 const size_t s = itemSize();
558 while (l <= h) {
559 mid = l + (h - l)/2;
560 const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
561 const int c = do_compare(curr, item);
562 if (c == 0) {
563 err = l = mid;
564 break;
565 } else if (c < 0) {
566 l = mid + 1;
567 } else {
568 h = mid - 1;
569 }
570 }
571 if (order) *order = l;
572 return err;
573 }
574
add(const void * item)575 ssize_t SortedVectorImpl::add(const void* item)
576 {
577 size_t order;
578 ssize_t index = _indexOrderOf(item, &order);
579 if (index < 0) {
580 index = VectorImpl::insertAt(item, order, 1);
581 } else {
582 index = VectorImpl::replaceAt(item, index);
583 }
584 return index;
585 }
586
merge(const VectorImpl & vector)587 ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
588 {
589 // naive merge...
590 if (!vector.isEmpty()) {
591 const void* buffer = vector.arrayImpl();
592 const size_t is = itemSize();
593 size_t s = vector.size();
594 for (size_t i=0 ; i<s ; i++) {
595 ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
596 if (err<0) {
597 return err;
598 }
599 }
600 }
601 return NO_ERROR;
602 }
603
merge(const SortedVectorImpl & vector)604 ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
605 {
606 // we've merging a sorted vector... nice!
607 ssize_t err = NO_ERROR;
608 if (!vector.isEmpty()) {
609 // first take care of the case where the vectors are sorted together
610 if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
611 err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
612 } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
613 err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
614 } else {
615 // this could be made a little better
616 err = merge(static_cast<const VectorImpl&>(vector));
617 }
618 }
619 return err;
620 }
621
remove(const void * item)622 ssize_t SortedVectorImpl::remove(const void* item)
623 {
624 ssize_t i = indexOf(item);
625 if (i>=0) {
626 VectorImpl::removeItemsAt(i, 1);
627 }
628 return i;
629 }
630
reservedSortedVectorImpl1()631 void SortedVectorImpl::reservedSortedVectorImpl1() { };
reservedSortedVectorImpl2()632 void SortedVectorImpl::reservedSortedVectorImpl2() { };
reservedSortedVectorImpl3()633 void SortedVectorImpl::reservedSortedVectorImpl3() { };
reservedSortedVectorImpl4()634 void SortedVectorImpl::reservedSortedVectorImpl4() { };
reservedSortedVectorImpl5()635 void SortedVectorImpl::reservedSortedVectorImpl5() { };
reservedSortedVectorImpl6()636 void SortedVectorImpl::reservedSortedVectorImpl6() { };
reservedSortedVectorImpl7()637 void SortedVectorImpl::reservedSortedVectorImpl7() { };
reservedSortedVectorImpl8()638 void SortedVectorImpl::reservedSortedVectorImpl8() { };
639
640
641 /*****************************************************************************/
642
643 }; // namespace android
644
645