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