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
33namespace android {
34namespace tinyutils {
35
36// ----------------------------------------------------------------------------
37
38const size_t kMinVectorCapacity = 4;
39
40static inline size_t max(size_t a, size_t b) {
41    return a>b ? a : b;
42}
43
44// ----------------------------------------------------------------------------
45
46VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
47    : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize)
48{
49}
50
51VectorImpl::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
60VectorImpl::~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
70VectorImpl& 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
88void* 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
104size_t VectorImpl::capacity() const
105{
106    if (mStorage) {
107        return SharedBuffer::sharedBuffer(mStorage)->size() / mItemSize;
108    }
109    return 0;
110}
111
112ssize_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
123ssize_t VectorImpl::appendVector(const VectorImpl& vector)
124{
125    return insertVectorAt(vector, size());
126}
127
128ssize_t VectorImpl::insertAt(size_t index, size_t numItems)
129{
130    return insertAt(0, index, numItems);
131}
132
133ssize_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
148void VectorImpl::pop()
149{
150    if (size())
151        removeItemsAt(size()-1, 1);
152}
153
154void VectorImpl::push()
155{
156    push(0);
157}
158
159void VectorImpl::push(const void* item)
160{
161    insertAt(item, size());
162}
163
164ssize_t VectorImpl::add()
165{
166    return add(0);
167}
168
169ssize_t VectorImpl::add(const void* item)
170{
171    return insertAt(item, size());
172}
173
174ssize_t VectorImpl::replaceAt(size_t index)
175{
176    return replaceAt(0, index);
177}
178
179ssize_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
196ssize_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
208void VectorImpl::finish_vector()
209{
210    release_storage();
211    mStorage = 0;
212    mCount = 0;
213}
214
215void VectorImpl::clear()
216{
217    _shrink(0, mCount);
218}
219
220void* 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
232const 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
244ssize_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
264void 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
275void* 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
325void 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
378size_t VectorImpl::itemSize() const {
379    return mItemSize;
380}
381
382void VectorImpl::_do_construct(void* storage, size_t num) const
383{
384    if (!(mFlags & HAS_TRIVIAL_CTOR)) {
385        do_construct(storage, num);
386    }
387}
388
389void VectorImpl::_do_destroy(void* storage, size_t num) const
390{
391    if (!(mFlags & HAS_TRIVIAL_DTOR)) {
392        do_destroy(storage, num);
393    }
394}
395
396void 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
405void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
406    do_splat(dest, item, num);
407}
408
409void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
410    do_move_forward(dest, from, num);
411}
412
413void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
414    do_move_backward(dest, from, num);
415}
416
417void VectorImpl::reservedVectorImpl1() { }
418void VectorImpl::reservedVectorImpl2() { }
419void VectorImpl::reservedVectorImpl3() { }
420void VectorImpl::reservedVectorImpl4() { }
421void VectorImpl::reservedVectorImpl5() { }
422void VectorImpl::reservedVectorImpl6() { }
423void VectorImpl::reservedVectorImpl7() { }
424void VectorImpl::reservedVectorImpl8() { }
425
426/*****************************************************************************/
427
428SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
429    : VectorImpl(itemSize, flags)
430{
431}
432
433SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
434: VectorImpl(rhs)
435{
436}
437
438SortedVectorImpl::~SortedVectorImpl()
439{
440}
441
442SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
443{
444    return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
445}
446
447ssize_t SortedVectorImpl::indexOf(const void* item) const
448{
449    return _indexOrderOf(item);
450}
451
452size_t SortedVectorImpl::orderOf(const void* item) const
453{
454    size_t o;
455    _indexOrderOf(item, &o);
456    return o;
457}
458
459ssize_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
485ssize_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
497ssize_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
514ssize_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
532ssize_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
541void SortedVectorImpl::reservedSortedVectorImpl1() { };
542void SortedVectorImpl::reservedSortedVectorImpl2() { };
543void SortedVectorImpl::reservedSortedVectorImpl3() { };
544void SortedVectorImpl::reservedSortedVectorImpl4() { };
545void SortedVectorImpl::reservedSortedVectorImpl5() { };
546void SortedVectorImpl::reservedSortedVectorImpl6() { };
547void SortedVectorImpl::reservedSortedVectorImpl7() { };
548void SortedVectorImpl::reservedSortedVectorImpl8() { };
549
550
551/*****************************************************************************/
552
553} // namespace tinyutils
554} // namespace android
555
556