summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAlex Ray2013-08-02 16:40:08 -0500
committerAlex Ray2013-08-02 16:40:08 -0500
commitd98e07fdf9c338589f263c47ce5c844ed43efad5 (patch)
treed4ff9849df225df1e4c46386fdabe30407ba5513 /libutils/VectorImpl.cpp
parentbe06210c508d5878dcc7d185e5613f4c7e38dfe8 (diff)
downloadplatform-system-core-d98e07fdf9c338589f263c47ce5c844ed43efad5.tar.gz
platform-system-core-d98e07fdf9c338589f263c47ce5c844ed43efad5.tar.xz
platform-system-core-d98e07fdf9c338589f263c47ce5c844ed43efad5.zip
move libs/utils to libutils
Change-Id: I6cf4268599460791414882f91eeb88a992fbd29d
Diffstat (limited to 'libutils/VectorImpl.cpp')
-rw-r--r--libutils/VectorImpl.cpp625
1 files changed, 625 insertions, 0 deletions
diff --git a/libutils/VectorImpl.cpp b/libutils/VectorImpl.cpp
new file mode 100644
index 000000000..5a79647cb
--- /dev/null
+++ b/libutils/VectorImpl.cpp
@@ -0,0 +1,625 @@
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
32namespace android {
33
34// ----------------------------------------------------------------------------
35
36const size_t kMinVectorCapacity = 4;
37
38static inline size_t max(size_t a, size_t b) {
39 return a>b ? a : b;
40}
41
42// ----------------------------------------------------------------------------
43
44VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
45 : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize)
46{
47}
48
49VectorImpl::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
58VectorImpl::~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
67VectorImpl& 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
85void* 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
101size_t VectorImpl::capacity() const
102{
103 if (mStorage) {
104 return SharedBuffer::bufferFromData(mStorage)->size() / mItemSize;
105 }
106 return 0;
107}
108
109ssize_t VectorImpl::insertVectorAt(const VectorImpl& vector, size_t index)
110{
111 return insertArrayAt(vector.arrayImpl(), index, vector.size());
112}
113
114ssize_t VectorImpl::appendVector(const VectorImpl& vector)
115{
116 return insertVectorAt(vector, size());
117}
118
119ssize_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
135ssize_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;
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
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
239ssize_t VectorImpl::add(const void* item)
240{
241 return insertAt(item, size());
242}
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 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
272ssize_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
284void VectorImpl::finish_vector()
285{
286 release_storage();
287 mStorage = 0;
288 mCount = 0;
289}
290
291void VectorImpl::clear()
292{
293 _shrink(0, mCount);
294}
295
296void* 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
311const 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
326ssize_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
346ssize_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
356void 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
367void* 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
417void 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
468size_t VectorImpl::itemSize() const {
469 return mItemSize;
470}
471
472void VectorImpl::_do_construct(void* storage, size_t num) const
473{
474 if (!(mFlags & HAS_TRIVIAL_CTOR)) {
475 do_construct(storage, num);
476 }
477}
478
479void VectorImpl::_do_destroy(void* storage, size_t num) const
480{
481 if (!(mFlags & HAS_TRIVIAL_DTOR)) {
482 do_destroy(storage, num);
483 }
484}
485
486void 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
495void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
496 do_splat(dest, item, num);
497}
498
499void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
500 do_move_forward(dest, from, num);
501}
502
503void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
504 do_move_backward(dest, from, num);
505}
506
507/*****************************************************************************/
508
509SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
510 : VectorImpl(itemSize, flags)
511{
512}
513
514SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
515: VectorImpl(rhs)
516{
517}
518
519SortedVectorImpl::~SortedVectorImpl()
520{
521}
522
523SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
524{
525 return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
526}
527
528ssize_t SortedVectorImpl::indexOf(const void* item) const
529{
530 return _indexOrderOf(item);
531}
532
533size_t SortedVectorImpl::orderOf(const void* item) const
534{
535 size_t o;
536 _indexOrderOf(item, &o);
537 return o;
538}
539
540ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
541{
542 // binary search
543 ssize_t err = NAME_NOT_FOUND;
544 ssize_t l = 0;
545 ssize_t h = size()-1;
546 ssize_t mid;
547 const void* a = arrayImpl();
548 const size_t s = itemSize();
549 while (l <= h) {
550 mid = l + (h - l)/2;
551 const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
552 const int c = do_compare(curr, item);
553 if (c == 0) {
554 err = l = mid;
555 break;
556 } else if (c < 0) {
557 l = mid + 1;
558 } else {
559 h = mid - 1;
560 }
561 }
562 if (order) *order = l;
563 return err;
564}
565
566ssize_t SortedVectorImpl::add(const void* item)
567{
568 size_t order;
569 ssize_t index = _indexOrderOf(item, &order);
570 if (index < 0) {
571 index = VectorImpl::insertAt(item, order, 1);
572 } else {
573 index = VectorImpl::replaceAt(item, index);
574 }
575 return index;
576}
577
578ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
579{
580 // naive merge...
581 if (!vector.isEmpty()) {
582 const void* buffer = vector.arrayImpl();
583 const size_t is = itemSize();
584 size_t s = vector.size();
585 for (size_t i=0 ; i<s ; i++) {
586 ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
587 if (err<0) {
588 return err;
589 }
590 }
591 }
592 return NO_ERROR;
593}
594
595ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
596{
597 // we've merging a sorted vector... nice!
598 ssize_t err = NO_ERROR;
599 if (!vector.isEmpty()) {
600 // first take care of the case where the vectors are sorted together
601 if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
602 err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
603 } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
604 err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
605 } else {
606 // this could be made a little better
607 err = merge(static_cast<const VectorImpl&>(vector));
608 }
609 }
610 return err;
611}
612
613ssize_t SortedVectorImpl::remove(const void* item)
614{
615 ssize_t i = indexOf(item);
616 if (i>=0) {
617 VectorImpl::removeItemsAt(i, 1);
618 }
619 return i;
620}
621
622/*****************************************************************************/
623
624}; // namespace android
625