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
24namespace android {
25
26enum {
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
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::sharedBuffer(mStorage)->acquire();
55    }
56}
57
58VectorImpl::~VectorImpl()
59{
60    ALOG_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
68VectorImpl& VectorImpl::operator = (const VectorImpl& rhs)
69{
70    ALOG_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
86void* 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
102size_t VectorImpl::capacity() const
103{
104    if (mStorage) {
105        return SharedBuffer::sharedBuffer(mStorage)->size() / mItemSize;
106    }
107    return 0;
108}
109
110ssize_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
121ssize_t VectorImpl::appendVector(const VectorImpl& vector)
122{
123    return insertVectorAt(vector, size());
124}
125
126ssize_t VectorImpl::insertAt(size_t index, size_t numItems)
127{
128    return insertAt(0, index, numItems);
129}
130
131ssize_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
146void VectorImpl::pop()
147{
148    if (size())
149        removeItemsAt(size()-1, 1);
150}
151
152void VectorImpl::push()
153{
154    push(0);
155}
156
157void VectorImpl::push(const void* item)
158{
159    insertAt(item, size());
160}
161
162ssize_t VectorImpl::add()
163{
164    return add(0);
165}
166
167ssize_t VectorImpl::add(const void* item)
168{
169    return insertAt(item, size());
170}
171
172ssize_t VectorImpl::replaceAt(size_t index)
173{
174    return replaceAt(0, index);
175}
176
177ssize_t VectorImpl::replaceAt(const void* prototype, size_t index)
178{
179    ALOG_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
194ssize_t VectorImpl::removeItemsAt(size_t index, size_t count)
195{
196    ALOG_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
206void VectorImpl::finish_vector()
207{
208    release_storage();
209    mStorage = 0;
210    mCount = 0;
211}
212
213void VectorImpl::clear()
214{
215    _shrink(0, mCount);
216}
217
218void* VectorImpl::editItemLocation(size_t index)
219{
220    ALOG_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
230const void* VectorImpl::itemLocation(size_t index) const
231{
232    ALOG_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
242ssize_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
262void 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
273void* VectorImpl::_grow(size_t where, size_t amount)
274{
275//    ALOGV("_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//        ALOGV("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
323void VectorImpl::_shrink(size_t where, size_t amount)
324{
325    if (!mStorage)
326        return;
327
328//    ALOGV("_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//        ALOGV("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
376size_t VectorImpl::itemSize() const {
377    return mItemSize;
378}
379
380void VectorImpl::_do_construct(void* storage, size_t num) const
381{
382    if (!(mFlags & HAS_TRIVIAL_CTOR)) {
383        do_construct(storage, num);
384    }
385}
386
387void VectorImpl::_do_destroy(void* storage, size_t num) const
388{
389    if (!(mFlags & HAS_TRIVIAL_DTOR)) {
390        do_destroy(storage, num);
391    }
392}
393
394void 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
403void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
404    do_splat(dest, item, num);
405}
406
407void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
408    do_move_forward(dest, from, num);
409}
410
411void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
412    do_move_backward(dest, from, num);
413}
414
415void VectorImpl::reservedVectorImpl1() { }
416void VectorImpl::reservedVectorImpl2() { }
417void VectorImpl::reservedVectorImpl3() { }
418void VectorImpl::reservedVectorImpl4() { }
419void VectorImpl::reservedVectorImpl5() { }
420void VectorImpl::reservedVectorImpl6() { }
421void VectorImpl::reservedVectorImpl7() { }
422void VectorImpl::reservedVectorImpl8() { }
423
424/*****************************************************************************/
425
426SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
427    : VectorImpl(itemSize, flags)
428{
429}
430
431SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
432: VectorImpl(rhs)
433{
434}
435
436SortedVectorImpl::~SortedVectorImpl()
437{
438}
439
440SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
441{
442    return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
443}
444
445ssize_t SortedVectorImpl::indexOf(const void* item) const
446{
447    return _indexOrderOf(item);
448}
449
450size_t SortedVectorImpl::orderOf(const void* item) const
451{
452    size_t o;
453    _indexOrderOf(item, &o);
454    return o;
455}
456
457ssize_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
483ssize_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
495ssize_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
512ssize_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
530ssize_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
539void SortedVectorImpl::reservedSortedVectorImpl1() { };
540void SortedVectorImpl::reservedSortedVectorImpl2() { };
541void SortedVectorImpl::reservedSortedVectorImpl3() { };
542void SortedVectorImpl::reservedSortedVectorImpl4() { };
543void SortedVectorImpl::reservedSortedVectorImpl5() { };
544void SortedVectorImpl::reservedSortedVectorImpl6() { };
545void SortedVectorImpl::reservedSortedVectorImpl7() { };
546void SortedVectorImpl::reservedSortedVectorImpl8() { };
547
548
549/*****************************************************************************/
550
551}; // namespace android
552
553