blob: 87ae3d51f1ee5f81b4f22fc4aeb6229e55aeb9dc [file] [log] [blame]
The Android Open Source Project9066cfe2009-03-03 19:31:44 -08001/*
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 <utils/Log.h>
24#include <utils/Errors.h>
25#include <utils/SharedBuffer.h>
26#include <utils/VectorImpl.h>
27
28/*****************************************************************************/
29
30
31namespace android {
32
33// ----------------------------------------------------------------------------
34
35const size_t kMinVectorCapacity = 4;
36
37static inline size_t max(size_t a, size_t b) {
38 return a>b ? a : b;
39}
40
41// ----------------------------------------------------------------------------
42
43VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
44 : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize)
45{
46}
47
48VectorImpl::VectorImpl(const VectorImpl& rhs)
49 : mStorage(rhs.mStorage), mCount(rhs.mCount),
50 mFlags(rhs.mFlags), mItemSize(rhs.mItemSize)
51{
52 if (mStorage) {
53 SharedBuffer::sharedBuffer(mStorage)->acquire();
54 }
55}
56
57VectorImpl::~VectorImpl()
58{
59 LOG_ASSERT(!mCount,
60 "[%p] "
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.
65}
66
67VectorImpl& VectorImpl::operator = (const VectorImpl& rhs)
68{
69 LOG_ASSERT(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::sharedBuffer(mStorage)->acquire();
77 } else {
78 mStorage = 0;
79 mCount = 0;
80 }
81 }
82 return *this;
83}
84
85void* VectorImpl::editArrayImpl()
86{
87 if (mStorage) {
88 SharedBuffer* sb = SharedBuffer::sharedBuffer(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
101size_t VectorImpl::capacity() const
102{
103 if (mStorage) {
104 return SharedBuffer::sharedBuffer(mStorage)->size() / mItemSize;
105 }
106 return 0;
107}
108
109ssize_t VectorImpl::insertVectorAt(const VectorImpl& vector, size_t index)
110{
Jeff Brown5c225b12010-06-16 01:53:36 -0700111 return insertArrayAt(vector.arrayImpl(), index, vector.size());
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800112}
113
114ssize_t VectorImpl::appendVector(const VectorImpl& vector)
115{
116 return insertVectorAt(vector, size());
117}
118
Jeff Brown5c225b12010-06-16 01:53:36 -0700119ssize_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
130ssize_t VectorImpl::appendArray(const void* array, size_t length)
131{
132 return insertArrayAt(array, size(), length);
133}
134
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800135ssize_t VectorImpl::insertAt(size_t index, size_t numItems)
136{
137 return insertAt(0, index, numItems);
138}
139
140ssize_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
155static int sortProxy(const void* lhs, const void* rhs, void* func)
156{
157 return (*(VectorImpl::compar_t)func)(lhs, rhs);
158}
159
160status_t VectorImpl::sort(VectorImpl::compar_t cmp)
161{
162 return sort(sortProxy, (void*)cmp);
163}
164
165status_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;
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800186 item = reinterpret_cast<char*>(array) + mItemSize*(i);
187 curr = reinterpret_cast<char*>(array) + mItemSize*(i-1);
Mathias Agopiand7414522010-03-29 13:45:18 -0700188 } else {
189 _do_destroy(temp, 1);
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800190 }
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 {
Mathias Agopiand7414522010-03-29 13:45:18 -0700197 _do_destroy(next, 1);
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800198 _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
Mathias Agopiand7414522010-03-29 13:45:18 -0700204 _do_destroy(next, 1);
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800205 _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
218void VectorImpl::pop()
219{
220 if (size())
221 removeItemsAt(size()-1, 1);
222}
223
224void VectorImpl::push()
225{
226 push(0);
227}
228
229void VectorImpl::push(const void* item)
230{
231 insertAt(item, size());
232}
233
234ssize_t VectorImpl::add()
235{
236 return add(0);
237}
238
Jeff Brown5c225b12010-06-16 01:53:36 -0700239ssize_t VectorImpl::add(const void* item)
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800240{
Jeff Brown5c225b12010-06-16 01:53:36 -0700241 return insertAt(item, size());
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800242}
243
244ssize_t VectorImpl::replaceAt(size_t index)
245{
246 return replaceAt(0, index);
247}
248
249ssize_t VectorImpl::replaceAt(const void* prototype, size_t index)
250{
251 LOG_ASSERT(index<size(),
252 "[%p] replace: index=%d, size=%d", this, (int)index, (int)size());
253
254 void* item = editItemLocation(index);
255 if (item == 0)
256 return NO_MEMORY;
257 _do_destroy(item, 1);
258 if (prototype == 0) {
259 _do_construct(item, 1);
260 } else {
261 _do_copy(item, prototype, 1);
262 }
263 return ssize_t(index);
264}
265
266ssize_t VectorImpl::removeItemsAt(size_t index, size_t count)
267{
268 LOG_ASSERT((index+count)<=size(),
269 "[%p] remove: index=%d, count=%d, size=%d",
270 this, (int)index, (int)count, (int)size());
271
272 if ((index+count) > size())
273 return BAD_VALUE;
274 _shrink(index, count);
275 return index;
276}
277
278void VectorImpl::finish_vector()
279{
280 release_storage();
281 mStorage = 0;
282 mCount = 0;
283}
284
285void VectorImpl::clear()
286{
287 _shrink(0, mCount);
288}
289
290void* VectorImpl::editItemLocation(size_t index)
291{
292 LOG_ASSERT(index<capacity(),
Mathias Agopiancf7e3a52011-07-11 16:26:18 -0700293 "[%p] editItemLocation: index=%d, capacity=%d, count=%d",
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800294 this, (int)index, (int)capacity(), (int)mCount);
295
296 void* buffer = editArrayImpl();
297 if (buffer)
298 return reinterpret_cast<char*>(buffer) + index*mItemSize;
299 return 0;
300}
301
302const void* VectorImpl::itemLocation(size_t index) const
303{
304 LOG_ASSERT(index<capacity(),
Mathias Agopiancf7e3a52011-07-11 16:26:18 -0700305 "[%p] itemLocation: index=%d, capacity=%d, count=%d",
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800306 this, (int)index, (int)capacity(), (int)mCount);
307
308 const void* buffer = arrayImpl();
309 if (buffer)
310 return reinterpret_cast<const char*>(buffer) + index*mItemSize;
311 return 0;
312}
313
314ssize_t VectorImpl::setCapacity(size_t new_capacity)
315{
316 size_t current_capacity = capacity();
317 ssize_t amount = new_capacity - size();
318 if (amount <= 0) {
319 // we can't reduce the capacity
320 return current_capacity;
321 }
322 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
323 if (sb) {
324 void* array = sb->data();
325 _do_copy(array, mStorage, size());
326 release_storage();
327 mStorage = const_cast<void*>(array);
328 } else {
329 return NO_MEMORY;
330 }
331 return new_capacity;
332}
333
334void VectorImpl::release_storage()
335{
336 if (mStorage) {
337 const SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage);
338 if (sb->release(SharedBuffer::eKeepStorage) == 1) {
339 _do_destroy(mStorage, mCount);
340 SharedBuffer::dealloc(sb);
341 }
342 }
343}
344
345void* VectorImpl::_grow(size_t where, size_t amount)
346{
347// LOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
348// this, (int)where, (int)amount, (int)mCount, (int)capacity());
349
350 if (where > mCount)
351 where = mCount;
352
353 const size_t new_size = mCount + amount;
354 if (capacity() < new_size) {
355 const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2);
356// LOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
357 if ((mStorage) &&
358 (mCount==where) &&
359 (mFlags & HAS_TRIVIAL_COPY) &&
360 (mFlags & HAS_TRIVIAL_DTOR))
361 {
362 const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
363 SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
364 mStorage = sb->data();
365 } else {
366 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
367 if (sb) {
368 void* array = sb->data();
369 if (where>0) {
370 _do_copy(array, mStorage, where);
371 }
372 if (mCount>where) {
373 const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize;
374 void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
375 _do_copy(dest, from, mCount-where);
376 }
377 release_storage();
378 mStorage = const_cast<void*>(array);
379 }
380 }
381 } else {
382 ssize_t s = mCount-where;
383 if (s>0) {
384 void* array = editArrayImpl();
385 void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
386 const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize;
387 _do_move_forward(to, from, s);
388 }
389 }
390 mCount += amount;
391 void* free_space = const_cast<void*>(itemLocation(where));
392 return free_space;
393}
394
395void VectorImpl::_shrink(size_t where, size_t amount)
396{
397 if (!mStorage)
398 return;
399
400// LOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
401// this, (int)where, (int)amount, (int)mCount, (int)capacity());
402
403 if (where >= mCount)
404 where = mCount - amount;
405
406 const size_t new_size = mCount - amount;
407 if (new_size*3 < capacity()) {
408 const size_t new_capacity = max(kMinVectorCapacity, new_size*2);
409// LOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
410 if ((where == mCount-amount) &&
411 (mFlags & HAS_TRIVIAL_COPY) &&
412 (mFlags & HAS_TRIVIAL_DTOR))
413 {
414 const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
415 SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800416 mStorage = sb->data();
417 } else {
418 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
419 if (sb) {
420 void* array = sb->data();
421 if (where>0) {
422 _do_copy(array, mStorage, where);
423 }
424 if (mCount > where+amount) {
425 const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize;
426 void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
427 _do_copy(dest, from, mCount-(where+amount));
428 }
429 release_storage();
430 mStorage = const_cast<void*>(array);
431 }
432 }
433 } else {
434 void* array = editArrayImpl();
435 void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
436 _do_destroy(to, amount);
437 ssize_t s = mCount-(where+amount);
438 if (s>0) {
439 const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
440 _do_move_backward(to, from, s);
441 }
442 }
443
444 // adjust the number of items...
445 mCount -= amount;
446}
447
448size_t VectorImpl::itemSize() const {
449 return mItemSize;
450}
451
452void VectorImpl::_do_construct(void* storage, size_t num) const
453{
454 if (!(mFlags & HAS_TRIVIAL_CTOR)) {
455 do_construct(storage, num);
456 }
457}
458
459void VectorImpl::_do_destroy(void* storage, size_t num) const
460{
461 if (!(mFlags & HAS_TRIVIAL_DTOR)) {
462 do_destroy(storage, num);
463 }
464}
465
466void VectorImpl::_do_copy(void* dest, const void* from, size_t num) const
467{
468 if (!(mFlags & HAS_TRIVIAL_COPY)) {
469 do_copy(dest, from, num);
470 } else {
471 memcpy(dest, from, num*itemSize());
472 }
473}
474
475void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
476 do_splat(dest, item, num);
477}
478
479void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
480 do_move_forward(dest, from, num);
481}
482
483void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
484 do_move_backward(dest, from, num);
485}
486
487void VectorImpl::reservedVectorImpl1() { }
488void VectorImpl::reservedVectorImpl2() { }
489void VectorImpl::reservedVectorImpl3() { }
490void VectorImpl::reservedVectorImpl4() { }
491void VectorImpl::reservedVectorImpl5() { }
492void VectorImpl::reservedVectorImpl6() { }
493void VectorImpl::reservedVectorImpl7() { }
494void VectorImpl::reservedVectorImpl8() { }
495
496/*****************************************************************************/
497
498SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
499 : VectorImpl(itemSize, flags)
500{
501}
502
503SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
504: VectorImpl(rhs)
505{
506}
507
508SortedVectorImpl::~SortedVectorImpl()
509{
510}
511
512SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
513{
514 return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
515}
516
517ssize_t SortedVectorImpl::indexOf(const void* item) const
518{
519 return _indexOrderOf(item);
520}
521
522size_t SortedVectorImpl::orderOf(const void* item) const
523{
524 size_t o;
525 _indexOrderOf(item, &o);
526 return o;
527}
528
529ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
530{
531 // binary search
532 ssize_t err = NAME_NOT_FOUND;
533 ssize_t l = 0;
534 ssize_t h = size()-1;
535 ssize_t mid;
536 const void* a = arrayImpl();
537 const size_t s = itemSize();
538 while (l <= h) {
539 mid = l + (h - l)/2;
540 const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
541 const int c = do_compare(curr, item);
542 if (c == 0) {
543 err = l = mid;
544 break;
545 } else if (c < 0) {
546 l = mid + 1;
547 } else {
548 h = mid - 1;
549 }
550 }
551 if (order) *order = l;
552 return err;
553}
554
555ssize_t SortedVectorImpl::add(const void* item)
556{
557 size_t order;
558 ssize_t index = _indexOrderOf(item, &order);
559 if (index < 0) {
560 index = VectorImpl::insertAt(item, order, 1);
561 } else {
562 index = VectorImpl::replaceAt(item, index);
563 }
564 return index;
565}
566
567ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
568{
569 // naive merge...
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 );
576 if (err<0) {
577 return err;
578 }
579 }
580 }
581 return NO_ERROR;
582}
583
584ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
585{
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));
594 } else {
595 // this could be made a little better
596 err = merge(static_cast<const VectorImpl&>(vector));
597 }
598 }
599 return err;
600}
601
602ssize_t SortedVectorImpl::remove(const void* item)
603{
604 ssize_t i = indexOf(item);
605 if (i>=0) {
606 VectorImpl::removeItemsAt(i, 1);
607 }
608 return i;
609}
610
611void SortedVectorImpl::reservedSortedVectorImpl1() { };
612void SortedVectorImpl::reservedSortedVectorImpl2() { };
613void SortedVectorImpl::reservedSortedVectorImpl3() { };
614void SortedVectorImpl::reservedSortedVectorImpl4() { };
615void SortedVectorImpl::reservedSortedVectorImpl5() { };
616void SortedVectorImpl::reservedSortedVectorImpl6() { };
617void SortedVectorImpl::reservedSortedVectorImpl7() { };
618void SortedVectorImpl::reservedSortedVectorImpl8() { };
619
620
621/*****************************************************************************/
622
623}; // namespace android
624