1edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/* 2edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Copyright (C) 2005 The Android Open Source Project 3edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 4edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * you may not use this file except in compliance with the License. 6edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * You may obtain a copy of the License at 7edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 8edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * 10edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * See the License for the specific language governing permissions and 14edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project * limitations under the License. 15edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project */ 16edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 17edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#define LOG_TAG "Vector" 18edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 19edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <string.h> 20edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <stdlib.h> 21edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <stdio.h> 22edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 2369973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian#include <cutils/log.h> 2469973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian 25edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <utils/Errors.h> 26edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <utils/SharedBuffer.h> 27edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <utils/VectorImpl.h> 28edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 29edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/*****************************************************************************/ 30edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 31edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 32edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectnamespace android { 33edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 34edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 35edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 36edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectconst size_t kMinVectorCapacity = 4; 37edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 38edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatic inline size_t max(size_t a, size_t b) { 39edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return a>b ? a : b; 40edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 41edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 42edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 43edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 44edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectVectorImpl::VectorImpl(size_t itemSize, uint32_t flags) 45edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize) 46edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 47edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 48edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 49edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectVectorImpl::VectorImpl(const VectorImpl& rhs) 50edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project : mStorage(rhs.mStorage), mCount(rhs.mCount), 51edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mFlags(rhs.mFlags), mItemSize(rhs.mItemSize) 52edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 53edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mStorage) { 5450f262fe569b52bb4d44c96de0d296188ce3885eMathias Agopian SharedBuffer::bufferFromData(mStorage)->acquire(); 55edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 56edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 57edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 58edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectVectorImpl::~VectorImpl() 59edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 6069973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian ALOGW_IF(mCount, 6169973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian "[%p] subclasses of VectorImpl must call finish_vector()" 62edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project " in their destructor. Leaking %d bytes.", 63edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)(mCount*mItemSize)); 64edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // We can't call _do_destroy() here because the vtable is already gone. 65edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 66edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 67edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectVectorImpl& VectorImpl::operator = (const VectorImpl& rhs) 68edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 6969973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian LOG_ALWAYS_FATAL_IF(mItemSize != rhs.mItemSize, 70edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "Vector<> have different types (this=%p, rhs=%p)", this, &rhs); 71edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (this != &rhs) { 72edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 73edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (rhs.mCount) { 74edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = rhs.mStorage; 75edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mCount = rhs.mCount; 7650f262fe569b52bb4d44c96de0d296188ce3885eMathias Agopian SharedBuffer::bufferFromData(mStorage)->acquire(); 77edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 78edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = 0; 79edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mCount = 0; 80edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 81edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 82edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return *this; 83edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 84edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 85edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid* VectorImpl::editArrayImpl() 86edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 87edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mStorage) { 8850f262fe569b52bb4d44c96de0d296188ce3885eMathias Agopian SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage)->attemptEdit(); 89edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb == 0) { 90edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project sb = SharedBuffer::alloc(capacity() * mItemSize); 91edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 92edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(sb->data(), mStorage, mCount); 93edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 94edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = sb->data(); 95edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 96edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 97edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 98edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return mStorage; 99edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 100edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 101edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectsize_t VectorImpl::capacity() const 102edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 103edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mStorage) { 10450f262fe569b52bb4d44c96de0d296188ce3885eMathias Agopian return SharedBuffer::bufferFromData(mStorage)->size() / mItemSize; 105edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 106edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return 0; 107edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 108edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 109edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::insertVectorAt(const VectorImpl& vector, size_t index) 110edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 111f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown return insertArrayAt(vector.arrayImpl(), index, vector.size()); 112edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 113edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 114edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::appendVector(const VectorImpl& vector) 115edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 116edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return insertVectorAt(vector, size()); 117edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 118edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 119f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brownssize_t VectorImpl::insertArrayAt(const void* array, size_t index, size_t length) 120f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown{ 121f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown if (index > size()) 122f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown return BAD_INDEX; 123f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown void* where = _grow(index, length); 124f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown if (where) { 125f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown _do_copy(where, array, length); 126f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown } 127f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown return where ? index : (ssize_t)NO_MEMORY; 128f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown} 129f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown 130f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brownssize_t VectorImpl::appendArray(const void* array, size_t length) 131f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown{ 132f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown return insertArrayAt(array, size(), length); 133f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown} 134f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown 135edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::insertAt(size_t index, size_t numItems) 136edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 137edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return insertAt(0, index, numItems); 138edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 139edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 140edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::insertAt(const void* item, size_t index, size_t numItems) 141edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 142edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (index > size()) 143edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return BAD_INDEX; 144edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* where = _grow(index, numItems); 145edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where) { 146edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (item) { 147edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_splat(where, item, numItems); 148edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 149edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_construct(where, numItems); 150edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 151edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 152edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return where ? index : (ssize_t)NO_MEMORY; 153edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 154edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 155edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatic int sortProxy(const void* lhs, const void* rhs, void* func) 156edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 157edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return (*(VectorImpl::compar_t)func)(lhs, rhs); 158edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 159edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 160edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatus_t VectorImpl::sort(VectorImpl::compar_t cmp) 161edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 162edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return sort(sortProxy, (void*)cmp); 163edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 164edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 165edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatus_t VectorImpl::sort(VectorImpl::compar_r_t cmp, void* state) 166edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 167edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // the sort must be stable. we're using insertion sort which 168edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // is well suited for small and already sorted arrays 169edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // for big arrays, it could be better to use mergesort 170edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const ssize_t count = size(); 171edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (count > 1) { 172edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = const_cast<void*>(arrayImpl()); 173edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* temp = 0; 174edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t i = 1; 175edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (i < count) { 176edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* item = reinterpret_cast<char*>(array) + mItemSize*(i); 177edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* curr = reinterpret_cast<char*>(array) + mItemSize*(i-1); 178edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (cmp(curr, item, state) > 0) { 179edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 180edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!temp) { 181edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // we're going to have to modify the array... 182edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project array = editArrayImpl(); 183edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!array) return NO_MEMORY; 184edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project temp = malloc(mItemSize); 185edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!temp) return NO_MEMORY; 186edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project item = reinterpret_cast<char*>(array) + mItemSize*(i); 187edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project curr = reinterpret_cast<char*>(array) + mItemSize*(i-1); 188caeddc7236a41bc51e60d54f5fa0e67cddd7aba6Mathias Agopian } else { 189caeddc7236a41bc51e60d54f5fa0e67cddd7aba6Mathias Agopian _do_destroy(temp, 1); 190edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 191edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 192edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(temp, item, 1); 193edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 194edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t j = i-1; 195edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* next = reinterpret_cast<char*>(array) + mItemSize*(i); 196edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do { 197caeddc7236a41bc51e60d54f5fa0e67cddd7aba6Mathias Agopian _do_destroy(next, 1); 198edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(next, curr, 1); 199edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project next = curr; 200edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project --j; 201edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project curr = reinterpret_cast<char*>(array) + mItemSize*(j); 202edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } while (j>=0 && (cmp(curr, temp, state) > 0)); 203edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 204caeddc7236a41bc51e60d54f5fa0e67cddd7aba6Mathias Agopian _do_destroy(next, 1); 205edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(next, temp, 1); 206edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 207edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project i++; 208edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 209edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 210edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (temp) { 211edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(temp, 1); 212edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project free(temp); 213edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 214edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 215edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_ERROR; 216edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 217edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 218edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::pop() 219edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 220edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (size()) 221edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project removeItemsAt(size()-1, 1); 222edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 223edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 224edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::push() 225edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 226edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project push(0); 227edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 228edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 229edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::push(const void* item) 230edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 231edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project insertAt(item, size()); 232edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 233edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 234edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::add() 235edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 236edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return add(0); 237edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 238edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 239f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brownssize_t VectorImpl::add(const void* item) 240edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 241f4a4ec2063dfd28e04bbfe712f67acee4bdc8e37Jeff Brown return insertAt(item, size()); 242edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 243edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 244edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::replaceAt(size_t index) 245edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 246edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return replaceAt(0, index); 247edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 248edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 249edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::replaceAt(const void* prototype, size_t index) 250edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 2516726347e8950d34ae162fb8d6a3680a871d359e2Steve Block ALOG_ASSERT(index<size(), 252edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "[%p] replace: index=%d, size=%d", this, (int)index, (int)size()); 253edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 25469973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian if (index >= size()) { 25569973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian return BAD_INDEX; 25669973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian } 25769973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian 258edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* item = editItemLocation(index); 259c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if (item != prototype) { 260c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if (item == 0) 261c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown return NO_MEMORY; 262c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown _do_destroy(item, 1); 263c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if (prototype == 0) { 264c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown _do_construct(item, 1); 265c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown } else { 266c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown _do_copy(item, prototype, 1); 267c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown } 268edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 269edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return ssize_t(index); 270edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 271edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 272edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::removeItemsAt(size_t index, size_t count) 273edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 2746726347e8950d34ae162fb8d6a3680a871d359e2Steve Block ALOG_ASSERT((index+count)<=size(), 275edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "[%p] remove: index=%d, count=%d, size=%d", 276edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)index, (int)count, (int)size()); 277edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 278edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if ((index+count) > size()) 279edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return BAD_VALUE; 280edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _shrink(index, count); 281edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return index; 282edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 283edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 284edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::finish_vector() 285edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 286edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 287edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = 0; 288edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mCount = 0; 289edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 290edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 291edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::clear() 292edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 293edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _shrink(0, mCount); 294edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 295edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 296edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid* VectorImpl::editItemLocation(size_t index) 297edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 2986726347e8950d34ae162fb8d6a3680a871d359e2Steve Block ALOG_ASSERT(index<capacity(), 299f6f177f2e282da6dcff3c4725eb66096b196aac5Mathias Agopian "[%p] editItemLocation: index=%d, capacity=%d, count=%d", 300edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)index, (int)capacity(), (int)mCount); 30169973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian 30269973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian if (index < capacity()) { 30369973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian void* buffer = editArrayImpl(); 30469973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian if (buffer) { 30569973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian return reinterpret_cast<char*>(buffer) + index*mItemSize; 30669973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian } 30769973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian } 308edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return 0; 309edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 310edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 311edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectconst void* VectorImpl::itemLocation(size_t index) const 312edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 3136726347e8950d34ae162fb8d6a3680a871d359e2Steve Block ALOG_ASSERT(index<capacity(), 314f6f177f2e282da6dcff3c4725eb66096b196aac5Mathias Agopian "[%p] itemLocation: index=%d, capacity=%d, count=%d", 315edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)index, (int)capacity(), (int)mCount); 316edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 31769973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian if (index < capacity()) { 31869973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian const void* buffer = arrayImpl(); 31969973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian if (buffer) { 32069973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian return reinterpret_cast<const char*>(buffer) + index*mItemSize; 32169973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian } 32269973992d531ae7df20916c6fb3034b08a6d53c4Mathias Agopian } 323edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return 0; 324edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 325edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 326edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::setCapacity(size_t new_capacity) 327edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 328edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t current_capacity = capacity(); 329edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t amount = new_capacity - size(); 330edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (amount <= 0) { 331edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // we can't reduce the capacity 332edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return current_capacity; 333edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 334edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 335edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 336edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = sb->data(); 337edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(array, mStorage, size()); 338edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 339edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = const_cast<void*>(array); 340edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 341edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_MEMORY; 342edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 343edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return new_capacity; 344edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 345edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 346edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::release_storage() 347edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 348edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mStorage) { 34950f262fe569b52bb4d44c96de0d296188ce3885eMathias Agopian const SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage); 350edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb->release(SharedBuffer::eKeepStorage) == 1) { 351edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(mStorage, mCount); 352edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer::dealloc(sb); 353edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 354edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 355edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 356edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 357edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid* VectorImpl::_grow(size_t where, size_t amount) 358edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 3596807e59e0ff943cc6225d46e3c33a8a7eae9b3d7Steve Block// ALOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d", 360edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// this, (int)where, (int)amount, (int)mCount, (int)capacity()); 361edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 3626726347e8950d34ae162fb8d6a3680a871d359e2Steve Block ALOG_ASSERT(where <= mCount, 363686f62fcaf4ce2f48d662fa89fb2e84ee9339c4dJeff Brown "[%p] _grow: where=%d, amount=%d, count=%d", 364686f62fcaf4ce2f48d662fa89fb2e84ee9339c4dJeff Brown this, (int)where, (int)amount, (int)mCount); // caller already checked 365686f62fcaf4ce2f48d662fa89fb2e84ee9339c4dJeff Brown 366edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_size = mCount + amount; 367edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (capacity() < new_size) { 368edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2); 3696807e59e0ff943cc6225d46e3c33a8a7eae9b3d7Steve Block// ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity); 370edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if ((mStorage) && 371edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mCount==where) && 372edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_COPY) && 373edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_DTOR)) 374edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project { 37550f262fe569b52bb4d44c96de0d296188ce3885eMathias Agopian const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage); 376edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); 377edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = sb->data(); 378edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 379edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 380edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 381edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = sb->data(); 382c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if (where != 0) { 383edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(array, mStorage, where); 384edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 385c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if (where != mCount) { 386edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize; 387edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 388edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(dest, from, mCount-where); 389edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 390edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 391edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = const_cast<void*>(array); 392edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 393edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 394edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 395a9611c5d5b61c594b9f5f24b24a665dc1e647f81Mathias Agopian void* array = editArrayImpl(); 396c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if (where != mCount) { 397edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize; 398c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 399c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown _do_move_forward(to, from, mCount - where); 400edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 401edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 402c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown mCount = new_size; 403edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* free_space = const_cast<void*>(itemLocation(where)); 404edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return free_space; 405edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 406edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 407edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_shrink(size_t where, size_t amount) 408edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 409edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!mStorage) 410edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return; 411edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 4126807e59e0ff943cc6225d46e3c33a8a7eae9b3d7Steve Block// ALOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d", 413edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// this, (int)where, (int)amount, (int)mCount, (int)capacity()); 414edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 4156726347e8950d34ae162fb8d6a3680a871d359e2Steve Block ALOG_ASSERT(where + amount <= mCount, 416686f62fcaf4ce2f48d662fa89fb2e84ee9339c4dJeff Brown "[%p] _shrink: where=%d, amount=%d, count=%d", 417686f62fcaf4ce2f48d662fa89fb2e84ee9339c4dJeff Brown this, (int)where, (int)amount, (int)mCount); // caller already checked 418edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 419edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_size = mCount - amount; 420edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (new_size*3 < capacity()) { 421edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_capacity = max(kMinVectorCapacity, new_size*2); 4226807e59e0ff943cc6225d46e3c33a8a7eae9b3d7Steve Block// ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity); 423c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if ((where == new_size) && 424edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_COPY) && 425edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_DTOR)) 426edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project { 42750f262fe569b52bb4d44c96de0d296188ce3885eMathias Agopian const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage); 428edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); 429edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = sb->data(); 430edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 431edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 432edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 433edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = sb->data(); 434c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if (where != 0) { 435edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(array, mStorage, where); 436edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 437c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if (where != new_size) { 438edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize; 439edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize; 440c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown _do_copy(dest, from, new_size - where); 441edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 442edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 443edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = const_cast<void*>(array); 444edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 445edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 446edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 447c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown void* array = editArrayImpl(); 448edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize; 449edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(to, amount); 450c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown if (where != new_size) { 451edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 452c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown _do_move_backward(to, from, new_size - where); 453edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 454edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 455c1053339974b52f7338cd2076f6ef6524a6fcfd5Jeff Brown mCount = new_size; 456edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 457edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 458edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectsize_t VectorImpl::itemSize() const { 459edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return mItemSize; 460edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 461edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 462edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_construct(void* storage, size_t num) const 463edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 464edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_CTOR)) { 465edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_construct(storage, num); 466edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 467edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 468edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 469edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_destroy(void* storage, size_t num) const 470edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 471edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_DTOR)) { 472edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_destroy(storage, num); 473edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 474edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 475edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 476edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_copy(void* dest, const void* from, size_t num) const 477edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 478edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_COPY)) { 479edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_copy(dest, from, num); 480edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 481edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project memcpy(dest, from, num*itemSize()); 482edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 483edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 484edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 485edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_splat(void* dest, const void* item, size_t num) const { 486edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_splat(dest, item, num); 487edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 488edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 489edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const { 490edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_move_forward(dest, from, num); 491edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 492edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 493edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const { 494edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_move_backward(dest, from, num); 495edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 496edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 49704075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid VectorImpl::reservedVectorImpl1() { } 49804075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid VectorImpl::reservedVectorImpl2() { } 49904075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid VectorImpl::reservedVectorImpl3() { } 50004075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid VectorImpl::reservedVectorImpl4() { } 50104075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid VectorImpl::reservedVectorImpl5() { } 50204075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid VectorImpl::reservedVectorImpl6() { } 50304075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid VectorImpl::reservedVectorImpl7() { } 50404075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid VectorImpl::reservedVectorImpl8() { } 50504075569b565c949a6db8b4e8a9f10d281de4d9cDave Burke 506edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/*****************************************************************************/ 507edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 508edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags) 509edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project : VectorImpl(itemSize, flags) 510edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 511edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 512edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 513edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs) 514edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project: VectorImpl(rhs) 515edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 516edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 517edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 518edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl::~SortedVectorImpl() 519edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 520edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 521edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 522edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs) 523edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 524edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) ); 525edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 526edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 527edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::indexOf(const void* item) const 528edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 529edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return _indexOrderOf(item); 530edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 531edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 532edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectsize_t SortedVectorImpl::orderOf(const void* item) const 533edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 534edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t o; 535edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _indexOrderOf(item, &o); 536edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return o; 537edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 538edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 539edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const 540edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 541edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // binary search 542edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t err = NAME_NOT_FOUND; 543edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t l = 0; 544edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t h = size()-1; 545edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t mid; 546edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* a = arrayImpl(); 547edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t s = itemSize(); 548edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (l <= h) { 549edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mid = l + (h - l)/2; 550edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* const curr = reinterpret_cast<const char *>(a) + (mid*s); 551edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const int c = do_compare(curr, item); 552edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (c == 0) { 553edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = l = mid; 554edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project break; 555edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else if (c < 0) { 556edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project l = mid + 1; 557edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 558edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project h = mid - 1; 559edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 560edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 561edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (order) *order = l; 562edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return err; 563edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 564edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 565edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::add(const void* item) 566edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 567edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t order; 568edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t index = _indexOrderOf(item, &order); 569edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (index < 0) { 570edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project index = VectorImpl::insertAt(item, order, 1); 571edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 572edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project index = VectorImpl::replaceAt(item, index); 573edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 574edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return index; 575edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 576edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 577edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::merge(const VectorImpl& vector) 578edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 579edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // naive merge... 580edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!vector.isEmpty()) { 581edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* buffer = vector.arrayImpl(); 582edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t is = itemSize(); 583edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t s = vector.size(); 584edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project for (size_t i=0 ; i<s ; i++) { 585edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is ); 586edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (err<0) { 587edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return err; 588edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 589edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 590edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 591edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_ERROR; 592edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 593edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 594edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector) 595edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 596edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // we've merging a sorted vector... nice! 597edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t err = NO_ERROR; 598edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!vector.isEmpty()) { 599edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // first take care of the case where the vectors are sorted together 600edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) { 601edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0); 602edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) { 603edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector)); 604edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 605edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // this could be made a little better 606edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = merge(static_cast<const VectorImpl&>(vector)); 607edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 608edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 609edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return err; 610edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 611edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 612edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::remove(const void* item) 613edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 614edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t i = indexOf(item); 615edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (i>=0) { 616edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project VectorImpl::removeItemsAt(i, 1); 617edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 618edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return i; 619edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 620edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 62104075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid SortedVectorImpl::reservedSortedVectorImpl1() { }; 62204075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid SortedVectorImpl::reservedSortedVectorImpl2() { }; 62304075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid SortedVectorImpl::reservedSortedVectorImpl3() { }; 62404075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid SortedVectorImpl::reservedSortedVectorImpl4() { }; 62504075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid SortedVectorImpl::reservedSortedVectorImpl5() { }; 62604075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid SortedVectorImpl::reservedSortedVectorImpl6() { }; 62704075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid SortedVectorImpl::reservedSortedVectorImpl7() { }; 62804075569b565c949a6db8b4e8a9f10d281de4d9cDave Burkevoid SortedVectorImpl::reservedSortedVectorImpl8() { }; 62904075569b565c949a6db8b4e8a9f10d281de4d9cDave Burke 63004075569b565c949a6db8b4e8a9f10d281de4d9cDave Burke 631edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/*****************************************************************************/ 632edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 633edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; // namespace android 634edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 635