1cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project/* 2cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Copyright (C) 2005 The Android Open Source Project 3cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 4cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * you may not use this file except in compliance with the License. 6cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * You may obtain a copy of the License at 7cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 8cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 10cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * See the License for the specific language governing permissions and 14cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * limitations under the License. 15cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 16cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 17cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#define LOG_TAG "Vector" 18cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 19cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <string.h> 20cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <stdlib.h> 21cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <stdio.h> 22cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 23bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian#include <cutils/log.h> 24bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian 25cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <utils/Errors.h> 26cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <utils/SharedBuffer.h> 27cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <utils/VectorImpl.h> 28cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 29cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project/*****************************************************************************/ 30cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 31cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 32cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectnamespace android { 33cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 34cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// ---------------------------------------------------------------------------- 35cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 36cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectconst size_t kMinVectorCapacity = 4; 37cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 38cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectstatic inline size_t max(size_t a, size_t b) { 39cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return a>b ? a : b; 40cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 41cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 42cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// ---------------------------------------------------------------------------- 43cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 44cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source ProjectVectorImpl::VectorImpl(size_t itemSize, uint32_t flags) 45cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize) 46cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 47cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 48cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 49cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source ProjectVectorImpl::VectorImpl(const VectorImpl& rhs) 50cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project : mStorage(rhs.mStorage), mCount(rhs.mCount), 51cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mFlags(rhs.mFlags), mItemSize(rhs.mItemSize) 52cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 53cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (mStorage) { 54e79aadd143a6467d70969e3cd4cb31a1623870f3Mathias Agopian SharedBuffer::bufferFromData(mStorage)->acquire(); 55cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 56cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 57cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 58cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source ProjectVectorImpl::~VectorImpl() 59cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 60bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian ALOGW_IF(mCount, 61bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian "[%p] subclasses of VectorImpl must call finish_vector()" 62cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project " in their destructor. Leaking %d bytes.", 63cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project this, (int)(mCount*mItemSize)); 64cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // We can't call _do_destroy() here because the vtable is already gone. 65cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 66cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 67cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source ProjectVectorImpl& VectorImpl::operator = (const VectorImpl& rhs) 68cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 69bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian LOG_ALWAYS_FATAL_IF(mItemSize != rhs.mItemSize, 70cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project "Vector<> have different types (this=%p, rhs=%p)", this, &rhs); 71cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (this != &rhs) { 72cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project release_storage(); 73cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (rhs.mCount) { 74cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mStorage = rhs.mStorage; 75cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mCount = rhs.mCount; 76e79aadd143a6467d70969e3cd4cb31a1623870f3Mathias Agopian SharedBuffer::bufferFromData(mStorage)->acquire(); 77cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 78cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mStorage = 0; 79cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mCount = 0; 80cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 81cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 82cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return *this; 83cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 84cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 85cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid* VectorImpl::editArrayImpl() 86cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 87cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (mStorage) { 88e79aadd143a6467d70969e3cd4cb31a1623870f3Mathias Agopian SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage)->attemptEdit(); 89cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (sb == 0) { 90cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project sb = SharedBuffer::alloc(capacity() * mItemSize); 91cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (sb) { 92cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_copy(sb->data(), mStorage, mCount); 93cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project release_storage(); 94cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mStorage = sb->data(); 95cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 96cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 97cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 98cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return mStorage; 99cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 100cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 101cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectsize_t VectorImpl::capacity() const 102cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 103cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (mStorage) { 104e79aadd143a6467d70969e3cd4cb31a1623870f3Mathias Agopian return SharedBuffer::bufferFromData(mStorage)->size() / mItemSize; 105cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 106cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return 0; 107cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 108cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 109cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t VectorImpl::insertVectorAt(const VectorImpl& vector, size_t index) 110cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 1119efaaa43595307786dbf06760823c25cb16b1925Jeff Brown return insertArrayAt(vector.arrayImpl(), index, vector.size()); 112cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 113cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 114cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t VectorImpl::appendVector(const VectorImpl& vector) 115cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 116cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return insertVectorAt(vector, size()); 117cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 118cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 1199efaaa43595307786dbf06760823c25cb16b1925Jeff Brownssize_t VectorImpl::insertArrayAt(const void* array, size_t index, size_t length) 1209efaaa43595307786dbf06760823c25cb16b1925Jeff Brown{ 1219efaaa43595307786dbf06760823c25cb16b1925Jeff Brown if (index > size()) 1229efaaa43595307786dbf06760823c25cb16b1925Jeff Brown return BAD_INDEX; 1239efaaa43595307786dbf06760823c25cb16b1925Jeff Brown void* where = _grow(index, length); 1249efaaa43595307786dbf06760823c25cb16b1925Jeff Brown if (where) { 1259efaaa43595307786dbf06760823c25cb16b1925Jeff Brown _do_copy(where, array, length); 1269efaaa43595307786dbf06760823c25cb16b1925Jeff Brown } 1279efaaa43595307786dbf06760823c25cb16b1925Jeff Brown return where ? index : (ssize_t)NO_MEMORY; 1289efaaa43595307786dbf06760823c25cb16b1925Jeff Brown} 1299efaaa43595307786dbf06760823c25cb16b1925Jeff Brown 1309efaaa43595307786dbf06760823c25cb16b1925Jeff Brownssize_t VectorImpl::appendArray(const void* array, size_t length) 1319efaaa43595307786dbf06760823c25cb16b1925Jeff Brown{ 1329efaaa43595307786dbf06760823c25cb16b1925Jeff Brown return insertArrayAt(array, size(), length); 1339efaaa43595307786dbf06760823c25cb16b1925Jeff Brown} 1349efaaa43595307786dbf06760823c25cb16b1925Jeff Brown 135cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t VectorImpl::insertAt(size_t index, size_t numItems) 136cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 137cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return insertAt(0, index, numItems); 138cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 139cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 140cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t VectorImpl::insertAt(const void* item, size_t index, size_t numItems) 141cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 142cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (index > size()) 143cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return BAD_INDEX; 144cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* where = _grow(index, numItems); 145cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (where) { 146cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (item) { 147cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_splat(where, item, numItems); 148cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 149cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_construct(where, numItems); 150cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 151cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 152cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return where ? index : (ssize_t)NO_MEMORY; 153cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 154cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 155cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectstatic int sortProxy(const void* lhs, const void* rhs, void* func) 156cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 157cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return (*(VectorImpl::compar_t)func)(lhs, rhs); 158cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 159cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 160cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectstatus_t VectorImpl::sort(VectorImpl::compar_t cmp) 161cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 162cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return sort(sortProxy, (void*)cmp); 163cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 164cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 165cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectstatus_t VectorImpl::sort(VectorImpl::compar_r_t cmp, void* state) 166cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 167cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // the sort must be stable. we're using insertion sort which 168cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // is well suited for small and already sorted arrays 169cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // for big arrays, it could be better to use mergesort 170cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const ssize_t count = size(); 171cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (count > 1) { 172cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* array = const_cast<void*>(arrayImpl()); 173cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* temp = 0; 174cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t i = 1; 175cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project while (i < count) { 176cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* item = reinterpret_cast<char*>(array) + mItemSize*(i); 177cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* curr = reinterpret_cast<char*>(array) + mItemSize*(i-1); 178cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (cmp(curr, item, state) > 0) { 179cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 180cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (!temp) { 181cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // we're going to have to modify the array... 182cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project array = editArrayImpl(); 183cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (!array) return NO_MEMORY; 184cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project temp = malloc(mItemSize); 185cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (!temp) return NO_MEMORY; 186cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project item = reinterpret_cast<char*>(array) + mItemSize*(i); 187cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project curr = reinterpret_cast<char*>(array) + mItemSize*(i-1); 18815d0edcba018d99a356077c8769148e769585a48Mathias Agopian } else { 18915d0edcba018d99a356077c8769148e769585a48Mathias Agopian _do_destroy(temp, 1); 190cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 191cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 192cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_copy(temp, item, 1); 193cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 194cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t j = i-1; 195cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* next = reinterpret_cast<char*>(array) + mItemSize*(i); 196cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project do { 19715d0edcba018d99a356077c8769148e769585a48Mathias Agopian _do_destroy(next, 1); 198cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_copy(next, curr, 1); 199cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project next = curr; 200cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project --j; 201cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project curr = reinterpret_cast<char*>(array) + mItemSize*(j); 202cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } while (j>=0 && (cmp(curr, temp, state) > 0)); 203cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 20415d0edcba018d99a356077c8769148e769585a48Mathias Agopian _do_destroy(next, 1); 205cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_copy(next, temp, 1); 206cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 207cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project i++; 208cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 209cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 210cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (temp) { 211cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_destroy(temp, 1); 212cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project free(temp); 213cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 214cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 215cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return NO_ERROR; 216cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 217cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 218cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::pop() 219cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 220cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (size()) 221cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project removeItemsAt(size()-1, 1); 222cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 223cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 224cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::push() 225cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 226cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project push(0); 227cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 228cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 229cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::push(const void* item) 230cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 231cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project insertAt(item, size()); 232cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 233cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 234cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t VectorImpl::add() 235cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 236cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return add(0); 237cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 238cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 2399efaaa43595307786dbf06760823c25cb16b1925Jeff Brownssize_t VectorImpl::add(const void* item) 240cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 2419efaaa43595307786dbf06760823c25cb16b1925Jeff Brown return insertAt(item, size()); 242cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 243cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 244cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t VectorImpl::replaceAt(size_t index) 245cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 246cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return replaceAt(0, index); 247cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 248cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 249cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t VectorImpl::replaceAt(const void* prototype, size_t index) 250cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 251ae07445e9793724324b93bb593fe20be2a386707Steve Block ALOG_ASSERT(index<size(), 252cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project "[%p] replace: index=%d, size=%d", this, (int)index, (int)size()); 253cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 254bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian if (index >= size()) { 255bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian return BAD_INDEX; 256bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian } 257bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian 258cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* item = editItemLocation(index); 259bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if (item != prototype) { 260bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if (item == 0) 261bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown return NO_MEMORY; 262bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown _do_destroy(item, 1); 263bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if (prototype == 0) { 264bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown _do_construct(item, 1); 265bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown } else { 266bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown _do_copy(item, prototype, 1); 267bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown } 268cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 269cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return ssize_t(index); 270cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 271cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 272cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t VectorImpl::removeItemsAt(size_t index, size_t count) 273cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 274ae07445e9793724324b93bb593fe20be2a386707Steve Block ALOG_ASSERT((index+count)<=size(), 275cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project "[%p] remove: index=%d, count=%d, size=%d", 276cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project this, (int)index, (int)count, (int)size()); 277cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 278cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if ((index+count) > size()) 279cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return BAD_VALUE; 280cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _shrink(index, count); 281cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return index; 282cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 283cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 284cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::finish_vector() 285cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 286cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project release_storage(); 287cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mStorage = 0; 288cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mCount = 0; 289cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 290cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 291cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::clear() 292cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 293cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _shrink(0, mCount); 294cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 295cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 296cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid* VectorImpl::editItemLocation(size_t index) 297cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 298ae07445e9793724324b93bb593fe20be2a386707Steve Block ALOG_ASSERT(index<capacity(), 299266a7d6223c90dd9707304f581d5e6c340335604Mathias Agopian "[%p] editItemLocation: index=%d, capacity=%d, count=%d", 300cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project this, (int)index, (int)capacity(), (int)mCount); 301bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian 302bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian if (index < capacity()) { 303bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian void* buffer = editArrayImpl(); 304bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian if (buffer) { 305bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian return reinterpret_cast<char*>(buffer) + index*mItemSize; 306bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian } 307bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian } 308cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return 0; 309cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 310cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 311cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectconst void* VectorImpl::itemLocation(size_t index) const 312cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 313ae07445e9793724324b93bb593fe20be2a386707Steve Block ALOG_ASSERT(index<capacity(), 314266a7d6223c90dd9707304f581d5e6c340335604Mathias Agopian "[%p] itemLocation: index=%d, capacity=%d, count=%d", 315cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project this, (int)index, (int)capacity(), (int)mCount); 316cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 317bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian if (index < capacity()) { 318bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian const void* buffer = arrayImpl(); 319bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian if (buffer) { 320bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian return reinterpret_cast<const char*>(buffer) + index*mItemSize; 321bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian } 322bdf73c7efcfdefe990f55541b71e7869ac378090Mathias Agopian } 323cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return 0; 324cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 325cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 326cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t VectorImpl::setCapacity(size_t new_capacity) 327cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 328cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project size_t current_capacity = capacity(); 329cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t amount = new_capacity - size(); 330cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (amount <= 0) { 331cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // we can't reduce the capacity 332cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return current_capacity; 333cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 334cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 335cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (sb) { 336cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* array = sb->data(); 337cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_copy(array, mStorage, size()); 338cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project release_storage(); 339cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mStorage = const_cast<void*>(array); 340cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 341cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return NO_MEMORY; 342cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 343cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return new_capacity; 344cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 345cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 346b73559d86c9017166da28e1d59a884f13417426dJesse Hallssize_t VectorImpl::resize(size_t size) { 347b73559d86c9017166da28e1d59a884f13417426dJesse Hall ssize_t result = NO_ERROR; 348b73559d86c9017166da28e1d59a884f13417426dJesse Hall if (size > mCount) { 349b73559d86c9017166da28e1d59a884f13417426dJesse Hall result = insertAt(mCount, size - mCount); 350b73559d86c9017166da28e1d59a884f13417426dJesse Hall } else if (size < mCount) { 351b73559d86c9017166da28e1d59a884f13417426dJesse Hall result = removeItemsAt(size, mCount - size); 352b73559d86c9017166da28e1d59a884f13417426dJesse Hall } 353b73559d86c9017166da28e1d59a884f13417426dJesse Hall return result < 0 ? result : size; 354b73559d86c9017166da28e1d59a884f13417426dJesse Hall} 355b73559d86c9017166da28e1d59a884f13417426dJesse Hall 356cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::release_storage() 357cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 358cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (mStorage) { 359e79aadd143a6467d70969e3cd4cb31a1623870f3Mathias Agopian const SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage); 360cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (sb->release(SharedBuffer::eKeepStorage) == 1) { 361cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_destroy(mStorage, mCount); 362cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project SharedBuffer::dealloc(sb); 363cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 364cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 365cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 366cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 367cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid* VectorImpl::_grow(size_t where, size_t amount) 368cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 369b37fbe9f810545bf62468fea5958325caa3635beSteve Block// ALOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d", 370cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// this, (int)where, (int)amount, (int)mCount, (int)capacity()); 371cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 372ae07445e9793724324b93bb593fe20be2a386707Steve Block ALOG_ASSERT(where <= mCount, 373aa5daede6a9e72f7611b19aa4e580a98878e6825Jeff Brown "[%p] _grow: where=%d, amount=%d, count=%d", 374aa5daede6a9e72f7611b19aa4e580a98878e6825Jeff Brown this, (int)where, (int)amount, (int)mCount); // caller already checked 375aa5daede6a9e72f7611b19aa4e580a98878e6825Jeff Brown 376cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const size_t new_size = mCount + amount; 377cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (capacity() < new_size) { 378cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2); 379b37fbe9f810545bf62468fea5958325caa3635beSteve Block// ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity); 380cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if ((mStorage) && 381cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project (mCount==where) && 382cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project (mFlags & HAS_TRIVIAL_COPY) && 383cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project (mFlags & HAS_TRIVIAL_DTOR)) 384cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project { 385e79aadd143a6467d70969e3cd4cb31a1623870f3Mathias Agopian const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage); 386cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); 387eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao if (sb) { 388eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao mStorage = sb->data(); 389eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao } else { 390eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao return NULL; 391eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao } 392cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 393cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 394cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (sb) { 395cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* array = sb->data(); 396bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if (where != 0) { 397cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_copy(array, mStorage, where); 398cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 399bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if (where != mCount) { 400cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize; 401cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 402cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_copy(dest, from, mCount-where); 403cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 404cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project release_storage(); 405cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mStorage = const_cast<void*>(array); 406eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao } else { 407eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao return NULL; 408cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 409cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 410cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 41103b168a69bd155be2675d7dffa342a30990259f7Mathias Agopian void* array = editArrayImpl(); 412bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if (where != mCount) { 413cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize; 414bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 415bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown _do_move_forward(to, from, mCount - where); 416cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 417cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 418bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown mCount = new_size; 419cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* free_space = const_cast<void*>(itemLocation(where)); 420cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return free_space; 421cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 422cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 423cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::_shrink(size_t where, size_t amount) 424cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 425cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (!mStorage) 426cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return; 427cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 428b37fbe9f810545bf62468fea5958325caa3635beSteve Block// ALOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d", 429cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// this, (int)where, (int)amount, (int)mCount, (int)capacity()); 430cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 431ae07445e9793724324b93bb593fe20be2a386707Steve Block ALOG_ASSERT(where + amount <= mCount, 432aa5daede6a9e72f7611b19aa4e580a98878e6825Jeff Brown "[%p] _shrink: where=%d, amount=%d, count=%d", 433aa5daede6a9e72f7611b19aa4e580a98878e6825Jeff Brown this, (int)where, (int)amount, (int)mCount); // caller already checked 434cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 435cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const size_t new_size = mCount - amount; 436cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (new_size*3 < capacity()) { 437cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const size_t new_capacity = max(kMinVectorCapacity, new_size*2); 438b37fbe9f810545bf62468fea5958325caa3635beSteve Block// ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity); 439bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if ((where == new_size) && 440cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project (mFlags & HAS_TRIVIAL_COPY) && 441cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project (mFlags & HAS_TRIVIAL_DTOR)) 442cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project { 443e79aadd143a6467d70969e3cd4cb31a1623870f3Mathias Agopian const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage); 444cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); 445eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao if (sb) { 446eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao mStorage = sb->data(); 447eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao } else { 448eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao return; 449eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao } 450cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 451cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 452cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (sb) { 453cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* array = sb->data(); 454bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if (where != 0) { 455cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_copy(array, mStorage, where); 456cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 457bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if (where != new_size) { 458cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize; 459cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize; 460bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown _do_copy(dest, from, new_size - where); 461cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 462cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project release_storage(); 463cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mStorage = const_cast<void*>(array); 464eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao } else{ 465eb0eb4f79fca083009aa7a6b6e28ddcdbcbd1214Shuo Gao return; 466cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 467cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 468cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 469bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown void* array = editArrayImpl(); 470cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize; 471cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _do_destroy(to, amount); 472bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown if (where != new_size) { 473cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 474bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown _do_move_backward(to, from, new_size - where); 475cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 476cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 477bbbd761de125b50ac83047bccb0b6e0e32ce74a1Jeff Brown mCount = new_size; 478cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 479cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 480cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectsize_t VectorImpl::itemSize() const { 481cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return mItemSize; 482cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 483cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 484cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::_do_construct(void* storage, size_t num) const 485cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 486cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_CTOR)) { 487cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project do_construct(storage, num); 488cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 489cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 490cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 491cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::_do_destroy(void* storage, size_t num) const 492cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 493cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_DTOR)) { 494cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project do_destroy(storage, num); 495cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 496cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 497cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 498cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::_do_copy(void* dest, const void* from, size_t num) const 499cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 500cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_COPY)) { 501cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project do_copy(dest, from, num); 502cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 503cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project memcpy(dest, from, num*itemSize()); 504cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 505cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 506cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 507cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::_do_splat(void* dest, const void* item, size_t num) const { 508cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project do_splat(dest, item, num); 509cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 510cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 511cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const { 512cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project do_move_forward(dest, from, num); 513cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 514cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 515cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectvoid VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const { 516cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project do_move_backward(dest, from, num); 517cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 518cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 519cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project/*****************************************************************************/ 520cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 521cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source ProjectSortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags) 522cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project : VectorImpl(itemSize, flags) 523cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 524cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 525cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 526cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source ProjectSortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs) 527cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project: VectorImpl(rhs) 528cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 529cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 530cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 531cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source ProjectSortedVectorImpl::~SortedVectorImpl() 532cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 533cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 534cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 535cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source ProjectSortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs) 536cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 537cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) ); 538cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 539cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 540cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t SortedVectorImpl::indexOf(const void* item) const 541cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 542cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return _indexOrderOf(item); 543cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 544cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 545cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectsize_t SortedVectorImpl::orderOf(const void* item) const 546cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 547cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project size_t o; 548cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project _indexOrderOf(item, &o); 549cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return o; 550cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 551cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 552cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const 553cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 554cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // binary search 555cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t err = NAME_NOT_FOUND; 556cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t l = 0; 557cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t h = size()-1; 558cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t mid; 559cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const void* a = arrayImpl(); 560cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const size_t s = itemSize(); 561cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project while (l <= h) { 562cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project mid = l + (h - l)/2; 563cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const void* const curr = reinterpret_cast<const char *>(a) + (mid*s); 564cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const int c = do_compare(curr, item); 565cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (c == 0) { 566cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project err = l = mid; 567cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project break; 568cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else if (c < 0) { 569cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project l = mid + 1; 570cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 571cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project h = mid - 1; 572cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 573cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 574cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (order) *order = l; 575cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return err; 576cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 577cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 578cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t SortedVectorImpl::add(const void* item) 579cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 580cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project size_t order; 581cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t index = _indexOrderOf(item, &order); 582cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (index < 0) { 583cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project index = VectorImpl::insertAt(item, order, 1); 584cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 585cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project index = VectorImpl::replaceAt(item, index); 586cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 587cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return index; 588cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 589cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 590cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t SortedVectorImpl::merge(const VectorImpl& vector) 591cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 592cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // naive merge... 593cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (!vector.isEmpty()) { 594cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const void* buffer = vector.arrayImpl(); 595cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const size_t is = itemSize(); 596cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project size_t s = vector.size(); 597cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project for (size_t i=0 ; i<s ; i++) { 598cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is ); 599cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (err<0) { 600cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return err; 601cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 602cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 603cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 604cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return NO_ERROR; 605cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 606cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 607cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector) 608cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 609cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // we've merging a sorted vector... nice! 610cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t err = NO_ERROR; 611cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (!vector.isEmpty()) { 612cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // first take care of the case where the vectors are sorted together 613cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) { 614cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0); 615cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) { 616cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector)); 617cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } else { 618cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // this could be made a little better 619cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project err = merge(static_cast<const VectorImpl&>(vector)); 620cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 621cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 622cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return err; 623cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 624cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 625cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectssize_t SortedVectorImpl::remove(const void* item) 626cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 627cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t i = indexOf(item); 628cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project if (i>=0) { 629cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project VectorImpl::removeItemsAt(i, 1); 630cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project } 631cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project return i; 632cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project} 633cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 634cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project/*****************************************************************************/ 635cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 636cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project}; // namespace android 637cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 638