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