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            if (sb) {
388                mStorage = sb->data();
389            } else {
390                return NULL;
391            }
392        } else {
393            SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
394            if (sb) {
395                void* array = sb->data();
396                if (where != 0) {
397                    _do_copy(array, mStorage, where);
398                }
399                if (where != mCount) {
400                    const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize;
401                    void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
402                    _do_copy(dest, from, mCount-where);
403                }
404                release_storage();
405                mStorage = const_cast<void*>(array);
406            } else {
407                return NULL;
408            }
409        }
410    } else {
411        void* array = editArrayImpl();
412        if (where != mCount) {
413            const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize;
414            void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
415            _do_move_forward(to, from, mCount - where);
416        }
417    }
418    mCount = new_size;
419    void* free_space = const_cast<void*>(itemLocation(where));
420    return free_space;
421}
422
423void VectorImpl::_shrink(size_t where, size_t amount)
424{
425    if (!mStorage)
426        return;
427
428//    ALOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
429//        this, (int)where, (int)amount, (int)mCount, (int)capacity());
430
431    ALOG_ASSERT(where + amount <= mCount,
432            "[%p] _shrink: where=%d, amount=%d, count=%d",
433            this, (int)where, (int)amount, (int)mCount); // caller already checked
434
435    const size_t new_size = mCount - amount;
436    if (new_size*3 < capacity()) {
437        const size_t new_capacity = max(kMinVectorCapacity, new_size*2);
438//        ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
439        if ((where == new_size) &&
440            (mFlags & HAS_TRIVIAL_COPY) &&
441            (mFlags & HAS_TRIVIAL_DTOR))
442        {
443            const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage);
444            SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
445            if (sb) {
446                mStorage = sb->data();
447            } else {
448                return;
449            }
450        } else {
451            SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
452            if (sb) {
453                void* array = sb->data();
454                if (where != 0) {
455                    _do_copy(array, mStorage, where);
456                }
457                if (where != new_size) {
458                    const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize;
459                    void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
460                    _do_copy(dest, from, new_size - where);
461                }
462                release_storage();
463                mStorage = const_cast<void*>(array);
464            } else{
465                return;
466            }
467        }
468    } else {
469        void* array = editArrayImpl();
470        void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
471        _do_destroy(to, amount);
472        if (where != new_size) {
473            const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
474            _do_move_backward(to, from, new_size - where);
475        }
476    }
477    mCount = new_size;
478}
479
480size_t VectorImpl::itemSize() const {
481    return mItemSize;
482}
483
484void VectorImpl::_do_construct(void* storage, size_t num) const
485{
486    if (!(mFlags & HAS_TRIVIAL_CTOR)) {
487        do_construct(storage, num);
488    }
489}
490
491void VectorImpl::_do_destroy(void* storage, size_t num) const
492{
493    if (!(mFlags & HAS_TRIVIAL_DTOR)) {
494        do_destroy(storage, num);
495    }
496}
497
498void VectorImpl::_do_copy(void* dest, const void* from, size_t num) const
499{
500    if (!(mFlags & HAS_TRIVIAL_COPY)) {
501        do_copy(dest, from, num);
502    } else {
503        memcpy(dest, from, num*itemSize());
504    }
505}
506
507void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
508    do_splat(dest, item, num);
509}
510
511void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
512    do_move_forward(dest, from, num);
513}
514
515void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
516    do_move_backward(dest, from, num);
517}
518
519/*****************************************************************************/
520
521SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
522    : VectorImpl(itemSize, flags)
523{
524}
525
526SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
527: VectorImpl(rhs)
528{
529}
530
531SortedVectorImpl::~SortedVectorImpl()
532{
533}
534
535SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
536{
537    return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
538}
539
540ssize_t SortedVectorImpl::indexOf(const void* item) const
541{
542    return _indexOrderOf(item);
543}
544
545size_t SortedVectorImpl::orderOf(const void* item) const
546{
547    size_t o;
548    _indexOrderOf(item, &o);
549    return o;
550}
551
552ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
553{
554    // binary search
555    ssize_t err = NAME_NOT_FOUND;
556    ssize_t l = 0;
557    ssize_t h = size()-1;
558    ssize_t mid;
559    const void* a = arrayImpl();
560    const size_t s = itemSize();
561    while (l <= h) {
562        mid = l + (h - l)/2;
563        const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
564        const int c = do_compare(curr, item);
565        if (c == 0) {
566            err = l = mid;
567            break;
568        } else if (c < 0) {
569            l = mid + 1;
570        } else {
571            h = mid - 1;
572        }
573    }
574    if (order) *order = l;
575    return err;
576}
577
578ssize_t SortedVectorImpl::add(const void* item)
579{
580    size_t order;
581    ssize_t index = _indexOrderOf(item, &order);
582    if (index < 0) {
583        index = VectorImpl::insertAt(item, order, 1);
584    } else {
585        index = VectorImpl::replaceAt(item, index);
586    }
587    return index;
588}
589
590ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
591{
592    // naive merge...
593    if (!vector.isEmpty()) {
594        const void* buffer = vector.arrayImpl();
595        const size_t is = itemSize();
596        size_t s = vector.size();
597        for (size_t i=0 ; i<s ; i++) {
598            ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
599            if (err<0) {
600                return err;
601            }
602        }
603    }
604    return NO_ERROR;
605}
606
607ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
608{
609    // we've merging a sorted vector... nice!
610    ssize_t err = NO_ERROR;
611    if (!vector.isEmpty()) {
612        // first take care of the case where the vectors are sorted together
613        if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
614            err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
615        } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
616            err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
617        } else {
618            // this could be made a little better
619            err = merge(static_cast<const VectorImpl&>(vector));
620        }
621    }
622    return err;
623}
624
625ssize_t SortedVectorImpl::remove(const void* item)
626{
627    ssize_t i = indexOf(item);
628    if (i>=0) {
629        VectorImpl::removeItemsAt(i, 1);
630    }
631    return i;
632}
633
634/*****************************************************************************/
635
636}; // namespace android
637
638