1 /*
2 * Copyright 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 #include <errno.h>
23
24 #include <cutils/log.h>
25
26 #include "Errors.h"
27 #include "SharedBuffer.h"
28 #include "VectorImpl.h"
29
30 /*****************************************************************************/
31
32
33 namespace android {
34 namespace tinyutils {
35
36 // ----------------------------------------------------------------------------
37
38 const size_t kMinVectorCapacity = 4;
39
max(size_t a,size_t b)40 static inline size_t max(size_t a, size_t b) {
41 return a>b ? a : b;
42 }
43
44 // ----------------------------------------------------------------------------
45
VectorImpl(size_t itemSize,uint32_t flags)46 VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
47 : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize)
48 {
49 }
50
VectorImpl(const VectorImpl & rhs)51 VectorImpl::VectorImpl(const VectorImpl& rhs)
52 : mStorage(rhs.mStorage), mCount(rhs.mCount),
53 mFlags(rhs.mFlags), mItemSize(rhs.mItemSize)
54 {
55 if (mStorage) {
56 SharedBuffer::sharedBuffer(mStorage)->acquire();
57 }
58 }
59
~VectorImpl()60 VectorImpl::~VectorImpl()
61 {
62 ALOG_ASSERT(!mCount,
63 "[%p] "
64 "subclasses of VectorImpl must call finish_vector()"
65 " in their destructor. Leaking %d bytes.",
66 this, (int)(mCount*mItemSize));
67 // We can't call _do_destroy() here because the vtable is already gone.
68 }
69
operator =(const VectorImpl & rhs)70 VectorImpl& VectorImpl::operator = (const VectorImpl& rhs)
71 {
72 ALOG_ASSERT(mItemSize == rhs.mItemSize,
73 "Vector<> have different types (this=%p, rhs=%p)", this, &rhs);
74 if (this != &rhs) {
75 release_storage();
76 if (rhs.mCount) {
77 mStorage = rhs.mStorage;
78 mCount = rhs.mCount;
79 SharedBuffer::sharedBuffer(mStorage)->acquire();
80 } else {
81 mStorage = 0;
82 mCount = 0;
83 }
84 }
85 return *this;
86 }
87
editArrayImpl()88 void* VectorImpl::editArrayImpl()
89 {
90 if (mStorage) {
91 SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage)->attemptEdit();
92 if (sb == 0) {
93 sb = SharedBuffer::alloc(capacity() * mItemSize);
94 if (sb) {
95 _do_copy(sb->data(), mStorage, mCount);
96 release_storage();
97 mStorage = sb->data();
98 }
99 }
100 }
101 return mStorage;
102 }
103
capacity() const104 size_t VectorImpl::capacity() const
105 {
106 if (mStorage) {
107 return SharedBuffer::sharedBuffer(mStorage)->size() / mItemSize;
108 }
109 return 0;
110 }
111
insertVectorAt(const VectorImpl & vector,size_t index)112 ssize_t VectorImpl::insertVectorAt(const VectorImpl& vector, size_t index)
113 {
114 if (index > size())
115 return BAD_INDEX;
116 void* where = _grow(index, vector.size());
117 if (where) {
118 _do_copy(where, vector.arrayImpl(), vector.size());
119 }
120 return where ? index : (ssize_t)NO_MEMORY;
121 }
122
appendVector(const VectorImpl & vector)123 ssize_t VectorImpl::appendVector(const VectorImpl& vector)
124 {
125 return insertVectorAt(vector, size());
126 }
127
insertAt(size_t index,size_t numItems)128 ssize_t VectorImpl::insertAt(size_t index, size_t numItems)
129 {
130 return insertAt(0, index, numItems);
131 }
132
insertAt(const void * item,size_t index,size_t numItems)133 ssize_t VectorImpl::insertAt(const void* item, size_t index, size_t numItems)
134 {
135 if (index > size())
136 return BAD_INDEX;
137 void* where = _grow(index, numItems);
138 if (where) {
139 if (item) {
140 _do_splat(where, item, numItems);
141 } else {
142 _do_construct(where, numItems);
143 }
144 }
145 return where ? index : (ssize_t)NO_MEMORY;
146 }
147
pop()148 void VectorImpl::pop()
149 {
150 if (size())
151 removeItemsAt(size()-1, 1);
152 }
153
push()154 void VectorImpl::push()
155 {
156 push(0);
157 }
158
push(const void * item)159 void VectorImpl::push(const void* item)
160 {
161 insertAt(item, size());
162 }
163
add()164 ssize_t VectorImpl::add()
165 {
166 return add(0);
167 }
168
add(const void * item)169 ssize_t VectorImpl::add(const void* item)
170 {
171 return insertAt(item, size());
172 }
173
replaceAt(size_t index)174 ssize_t VectorImpl::replaceAt(size_t index)
175 {
176 return replaceAt(0, index);
177 }
178
replaceAt(const void * prototype,size_t index)179 ssize_t VectorImpl::replaceAt(const void* prototype, size_t index)
180 {
181 ALOG_ASSERT(index<size(),
182 "[%p] replace: index=%d, size=%d", this, (int)index, (int)size());
183
184 void* item = editItemLocation(index);
185 if (item == 0)
186 return NO_MEMORY;
187 _do_destroy(item, 1);
188 if (prototype == 0) {
189 _do_construct(item, 1);
190 } else {
191 _do_copy(item, prototype, 1);
192 }
193 return ssize_t(index);
194 }
195
removeItemsAt(size_t index,size_t count)196 ssize_t VectorImpl::removeItemsAt(size_t index, size_t count)
197 {
198 ALOG_ASSERT((index+count)<=size(),
199 "[%p] remove: index=%d, count=%d, size=%d",
200 this, (int)index, (int)count, (int)size());
201
202 if ((index+count) > size())
203 return BAD_VALUE;
204 _shrink(index, count);
205 return index;
206 }
207
finish_vector()208 void VectorImpl::finish_vector()
209 {
210 release_storage();
211 mStorage = 0;
212 mCount = 0;
213 }
214
clear()215 void VectorImpl::clear()
216 {
217 _shrink(0, mCount);
218 }
219
editItemLocation(size_t index)220 void* VectorImpl::editItemLocation(size_t index)
221 {
222 ALOG_ASSERT(index<capacity(),
223 "[%p] itemLocation: index=%d, capacity=%d, count=%d",
224 this, (int)index, (int)capacity(), (int)mCount);
225
226 void* buffer = editArrayImpl();
227 if (buffer)
228 return reinterpret_cast<char*>(buffer) + index*mItemSize;
229 return 0;
230 }
231
itemLocation(size_t index) const232 const void* VectorImpl::itemLocation(size_t index) const
233 {
234 ALOG_ASSERT(index<capacity(),
235 "[%p] editItemLocation: index=%d, capacity=%d, count=%d",
236 this, (int)index, (int)capacity(), (int)mCount);
237
238 const void* buffer = arrayImpl();
239 if (buffer)
240 return reinterpret_cast<const char*>(buffer) + index*mItemSize;
241 return 0;
242 }
243
setCapacity(size_t new_capacity)244 ssize_t VectorImpl::setCapacity(size_t new_capacity)
245 {
246 size_t current_capacity = capacity();
247 ssize_t amount = new_capacity - size();
248 if (amount <= 0) {
249 // we can't reduce the capacity
250 return current_capacity;
251 }
252 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
253 if (sb) {
254 void* array = sb->data();
255 _do_copy(array, mStorage, size());
256 release_storage();
257 mStorage = const_cast<void*>(array);
258 } else {
259 return NO_MEMORY;
260 }
261 return new_capacity;
262 }
263
release_storage()264 void VectorImpl::release_storage()
265 {
266 if (mStorage) {
267 const SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage);
268 if (sb->release(SharedBuffer::eKeepStorage) == 1) {
269 _do_destroy(mStorage, mCount);
270 SharedBuffer::dealloc(sb);
271 }
272 }
273 }
274
_grow(size_t where,size_t amount)275 void* VectorImpl::_grow(size_t where, size_t amount)
276 {
277 // ALOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
278 // this, (int)where, (int)amount, (int)mCount, (int)capacity());
279
280 if (where > mCount)
281 where = mCount;
282
283 const size_t new_size = mCount + amount;
284 if (capacity() < new_size) {
285 const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2);
286 // ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
287 if ((mStorage) &&
288 (mCount==where) &&
289 (mFlags & HAS_TRIVIAL_COPY) &&
290 (mFlags & HAS_TRIVIAL_DTOR))
291 {
292 const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
293 SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
294 mStorage = sb->data();
295 } else {
296 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
297 if (sb) {
298 void* array = sb->data();
299 if (where>0) {
300 _do_copy(array, mStorage, where);
301 }
302 if (mCount>where) {
303 const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize;
304 void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
305 _do_copy(dest, from, mCount-where);
306 }
307 release_storage();
308 mStorage = const_cast<void*>(array);
309 }
310 }
311 } else {
312 ssize_t s = mCount-where;
313 if (s>0) {
314 void* array = editArrayImpl();
315 void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
316 const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize;
317 _do_move_forward(to, from, s);
318 }
319 }
320 mCount += amount;
321 void* free_space = const_cast<void*>(itemLocation(where));
322 return free_space;
323 }
324
_shrink(size_t where,size_t amount)325 void VectorImpl::_shrink(size_t where, size_t amount)
326 {
327 if (!mStorage)
328 return;
329
330 // ALOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
331 // this, (int)where, (int)amount, (int)mCount, (int)capacity());
332
333 if (where >= mCount)
334 where = mCount - amount;
335
336 const size_t new_size = mCount - amount;
337 if (new_size*3 < capacity()) {
338 const size_t new_capacity = max(kMinVectorCapacity, new_size*2);
339 // ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
340 if ((where == mCount-amount) &&
341 (mFlags & HAS_TRIVIAL_COPY) &&
342 (mFlags & HAS_TRIVIAL_DTOR))
343 {
344 const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
345 SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
346 mStorage = sb->data();
347 } else {
348 SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
349 if (sb) {
350 void* array = sb->data();
351 if (where>0) {
352 _do_copy(array, mStorage, where);
353 }
354 if (mCount > where+amount) {
355 const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize;
356 void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
357 _do_copy(dest, from, mCount-(where+amount));
358 }
359 release_storage();
360 mStorage = const_cast<void*>(array);
361 }
362 }
363 } else {
364 void* array = editArrayImpl();
365 void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
366 _do_destroy(to, amount);
367 ssize_t s = mCount-(where+amount);
368 if (s>0) {
369 const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
370 _do_move_backward(to, from, s);
371 }
372 }
373
374 // adjust the number of items...
375 mCount -= amount;
376 }
377
itemSize() const378 size_t VectorImpl::itemSize() const {
379 return mItemSize;
380 }
381
_do_construct(void * storage,size_t num) const382 void VectorImpl::_do_construct(void* storage, size_t num) const
383 {
384 if (!(mFlags & HAS_TRIVIAL_CTOR)) {
385 do_construct(storage, num);
386 }
387 }
388
_do_destroy(void * storage,size_t num) const389 void VectorImpl::_do_destroy(void* storage, size_t num) const
390 {
391 if (!(mFlags & HAS_TRIVIAL_DTOR)) {
392 do_destroy(storage, num);
393 }
394 }
395
_do_copy(void * dest,const void * from,size_t num) const396 void VectorImpl::_do_copy(void* dest, const void* from, size_t num) const
397 {
398 if (!(mFlags & HAS_TRIVIAL_COPY)) {
399 do_copy(dest, from, num);
400 } else {
401 memcpy(dest, from, num*itemSize());
402 }
403 }
404
_do_splat(void * dest,const void * item,size_t num) const405 void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
406 do_splat(dest, item, num);
407 }
408
_do_move_forward(void * dest,const void * from,size_t num) const409 void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
410 do_move_forward(dest, from, num);
411 }
412
_do_move_backward(void * dest,const void * from,size_t num) const413 void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
414 do_move_backward(dest, from, num);
415 }
416
reservedVectorImpl1()417 void VectorImpl::reservedVectorImpl1() { }
reservedVectorImpl2()418 void VectorImpl::reservedVectorImpl2() { }
reservedVectorImpl3()419 void VectorImpl::reservedVectorImpl3() { }
reservedVectorImpl4()420 void VectorImpl::reservedVectorImpl4() { }
reservedVectorImpl5()421 void VectorImpl::reservedVectorImpl5() { }
reservedVectorImpl6()422 void VectorImpl::reservedVectorImpl6() { }
reservedVectorImpl7()423 void VectorImpl::reservedVectorImpl7() { }
reservedVectorImpl8()424 void VectorImpl::reservedVectorImpl8() { }
425
426 /*****************************************************************************/
427
SortedVectorImpl(size_t itemSize,uint32_t flags)428 SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
429 : VectorImpl(itemSize, flags)
430 {
431 }
432
SortedVectorImpl(const VectorImpl & rhs)433 SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
434 : VectorImpl(rhs)
435 {
436 }
437
~SortedVectorImpl()438 SortedVectorImpl::~SortedVectorImpl()
439 {
440 }
441
operator =(const SortedVectorImpl & rhs)442 SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
443 {
444 return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
445 }
446
indexOf(const void * item) const447 ssize_t SortedVectorImpl::indexOf(const void* item) const
448 {
449 return _indexOrderOf(item);
450 }
451
orderOf(const void * item) const452 size_t SortedVectorImpl::orderOf(const void* item) const
453 {
454 size_t o;
455 _indexOrderOf(item, &o);
456 return o;
457 }
458
_indexOrderOf(const void * item,size_t * order) const459 ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
460 {
461 // binary search
462 ssize_t err = NAME_NOT_FOUND;
463 ssize_t l = 0;
464 ssize_t h = size()-1;
465 ssize_t mid;
466 const void* a = arrayImpl();
467 const size_t s = itemSize();
468 while (l <= h) {
469 mid = l + (h - l)/2;
470 const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
471 const int c = do_compare(curr, item);
472 if (c == 0) {
473 err = l = mid;
474 break;
475 } else if (c < 0) {
476 l = mid + 1;
477 } else {
478 h = mid - 1;
479 }
480 }
481 if (order) *order = l;
482 return err;
483 }
484
add(const void * item)485 ssize_t SortedVectorImpl::add(const void* item)
486 {
487 size_t order;
488 ssize_t index = _indexOrderOf(item, &order);
489 if (index < 0) {
490 index = VectorImpl::insertAt(item, order, 1);
491 } else {
492 index = VectorImpl::replaceAt(item, index);
493 }
494 return index;
495 }
496
merge(const VectorImpl & vector)497 ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
498 {
499 // naive merge...
500 if (!vector.isEmpty()) {
501 const void* buffer = vector.arrayImpl();
502 const size_t is = itemSize();
503 size_t s = vector.size();
504 for (size_t i=0 ; i<s ; i++) {
505 ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
506 if (err<0) {
507 return err;
508 }
509 }
510 }
511 return NO_ERROR;
512 }
513
merge(const SortedVectorImpl & vector)514 ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
515 {
516 // we've merging a sorted vector... nice!
517 ssize_t err = NO_ERROR;
518 if (!vector.isEmpty()) {
519 // first take care of the case where the vectors are sorted together
520 if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
521 err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
522 } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
523 err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
524 } else {
525 // this could be made a little better
526 err = merge(static_cast<const VectorImpl&>(vector));
527 }
528 }
529 return err;
530 }
531
remove(const void * item)532 ssize_t SortedVectorImpl::remove(const void* item)
533 {
534 ssize_t i = indexOf(item);
535 if (i>=0) {
536 VectorImpl::removeItemsAt(i, 1);
537 }
538 return i;
539 }
540
reservedSortedVectorImpl1()541 void SortedVectorImpl::reservedSortedVectorImpl1() { };
reservedSortedVectorImpl2()542 void SortedVectorImpl::reservedSortedVectorImpl2() { };
reservedSortedVectorImpl3()543 void SortedVectorImpl::reservedSortedVectorImpl3() { };
reservedSortedVectorImpl4()544 void SortedVectorImpl::reservedSortedVectorImpl4() { };
reservedSortedVectorImpl5()545 void SortedVectorImpl::reservedSortedVectorImpl5() { };
reservedSortedVectorImpl6()546 void SortedVectorImpl::reservedSortedVectorImpl6() { };
reservedSortedVectorImpl7()547 void SortedVectorImpl::reservedSortedVectorImpl7() { };
reservedSortedVectorImpl8()548 void SortedVectorImpl::reservedSortedVectorImpl8() { };
549
550
551 /*****************************************************************************/
552
553 } // namespace tinyutils
554 } // namespace android
555
556