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