VectorImpl.cpp revision f6f177f2e282da6dcff3c4725eb66096b196aac5
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 23edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <utils/Log.h> 24edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <utils/Errors.h> 25edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <utils/SharedBuffer.h> 26edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#include <utils/VectorImpl.h> 27edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 28edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/*****************************************************************************/ 29edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 30edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 31edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectnamespace android { 32edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 33edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 34edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 35edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectconst size_t kMinVectorCapacity = 4; 36edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 37edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatic inline size_t max(size_t a, size_t b) { 38edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return a>b ? a : b; 39edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 40edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 41edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// ---------------------------------------------------------------------------- 42edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 43edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectVectorImpl::VectorImpl(size_t itemSize, uint32_t flags) 44edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize) 45edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 46edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 47edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 48edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectVectorImpl::VectorImpl(const VectorImpl& rhs) 49edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project : mStorage(rhs.mStorage), mCount(rhs.mCount), 50edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mFlags(rhs.mFlags), mItemSize(rhs.mItemSize) 51edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 52edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mStorage) { 53edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer::sharedBuffer(mStorage)->acquire(); 54edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 55edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 56edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 57edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectVectorImpl::~VectorImpl() 58edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 59edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT(!mCount, 60edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "[%p] " 61edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "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{ 69edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT(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; 76edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer::sharedBuffer(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) { 88edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::sharedBuffer(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) { 104edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return SharedBuffer::sharedBuffer(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{ 251edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT(index<size(), 252edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "[%p] replace: index=%d, size=%d", this, (int)index, (int)size()); 253edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 254edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* item = editItemLocation(index); 255edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (item == 0) 256edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_MEMORY; 257edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(item, 1); 258edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (prototype == 0) { 259edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_construct(item, 1); 260edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 261edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(item, prototype, 1); 262edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 263edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return ssize_t(index); 264edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 265edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 266edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::removeItemsAt(size_t index, size_t count) 267edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 268edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT((index+count)<=size(), 269edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "[%p] remove: index=%d, count=%d, size=%d", 270edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)index, (int)count, (int)size()); 271edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 272edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if ((index+count) > size()) 273edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return BAD_VALUE; 274edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _shrink(index, count); 275edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return index; 276edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 277edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 278edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::finish_vector() 279edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 280edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 281edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = 0; 282edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mCount = 0; 283edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 284edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 285edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::clear() 286edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 287edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _shrink(0, mCount); 288edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 289edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 290edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid* VectorImpl::editItemLocation(size_t index) 291edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 292edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT(index<capacity(), 293f6f177f2e282da6dcff3c4725eb66096b196aac5Mathias Agopian "[%p] editItemLocation: index=%d, capacity=%d, count=%d", 294edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)index, (int)capacity(), (int)mCount); 295edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 296edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* buffer = editArrayImpl(); 297edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (buffer) 298edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return reinterpret_cast<char*>(buffer) + index*mItemSize; 299edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return 0; 300edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 301edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 302edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectconst void* VectorImpl::itemLocation(size_t index) const 303edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 304edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT(index<capacity(), 305f6f177f2e282da6dcff3c4725eb66096b196aac5Mathias Agopian "[%p] itemLocation: index=%d, capacity=%d, count=%d", 306edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)index, (int)capacity(), (int)mCount); 307edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 308edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* buffer = arrayImpl(); 309edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (buffer) 310edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return reinterpret_cast<const char*>(buffer) + index*mItemSize; 311edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return 0; 312edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 313edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 314edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::setCapacity(size_t new_capacity) 315edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 316edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t current_capacity = capacity(); 317edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t amount = new_capacity - size(); 318edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (amount <= 0) { 319edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // we can't reduce the capacity 320edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return current_capacity; 321edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 322edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 323edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 324edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = sb->data(); 325edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(array, mStorage, size()); 326edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 327edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = const_cast<void*>(array); 328edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 329edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_MEMORY; 330edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 331edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return new_capacity; 332edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 333edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 334edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::release_storage() 335edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 336edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mStorage) { 337edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage); 338edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb->release(SharedBuffer::eKeepStorage) == 1) { 339edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(mStorage, mCount); 340edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer::dealloc(sb); 341edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 342edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 343edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 344edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 345edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid* VectorImpl::_grow(size_t where, size_t amount) 346edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 347edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// LOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d", 348edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// this, (int)where, (int)amount, (int)mCount, (int)capacity()); 349edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 350edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where > mCount) 351edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project where = mCount; 352edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 353edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_size = mCount + amount; 354edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (capacity() < new_size) { 355edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2); 356edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// LOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity); 357edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if ((mStorage) && 358edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mCount==where) && 359edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_COPY) && 360edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_DTOR)) 361edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project { 362edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage); 363edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); 364edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = sb->data(); 365edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 366edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 367edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 368edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = sb->data(); 369edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where>0) { 370edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(array, mStorage, where); 371edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 372edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mCount>where) { 373edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize; 374edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 375edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(dest, from, mCount-where); 376edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 377edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 378edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = const_cast<void*>(array); 379edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 380edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 381edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 382edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t s = mCount-where; 383edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (s>0) { 384edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = editArrayImpl(); 385edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 386edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize; 387edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_move_forward(to, from, s); 388edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 389edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 390edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mCount += amount; 391edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* free_space = const_cast<void*>(itemLocation(where)); 392edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return free_space; 393edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 394edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 395edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_shrink(size_t where, size_t amount) 396edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 397edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!mStorage) 398edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return; 399edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 400edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// LOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d", 401edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// this, (int)where, (int)amount, (int)mCount, (int)capacity()); 402edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 403edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where >= mCount) 404edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project where = mCount - amount; 405edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 406edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_size = mCount - amount; 407edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (new_size*3 < capacity()) { 408edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_capacity = max(kMinVectorCapacity, new_size*2); 409edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// LOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity); 410edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if ((where == mCount-amount) && 411edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_COPY) && 412edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_DTOR)) 413edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project { 414edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage); 415edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); 416edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = sb->data(); 417edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 418edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 419edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 420edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = sb->data(); 421edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where>0) { 422edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(array, mStorage, where); 423edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 424edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mCount > where+amount) { 425edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize; 426edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize; 427edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(dest, from, mCount-(where+amount)); 428edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 429edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 430edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = const_cast<void*>(array); 431edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 432edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 433edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 434edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = editArrayImpl(); 435edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize; 436edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(to, amount); 437edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t s = mCount-(where+amount); 438edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (s>0) { 439edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 440edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_move_backward(to, from, s); 441edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 442edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 443edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 444edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // adjust the number of items... 445edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mCount -= amount; 446edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 447edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 448edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectsize_t VectorImpl::itemSize() const { 449edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return mItemSize; 450edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 451edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 452edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_construct(void* storage, size_t num) const 453edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 454edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_CTOR)) { 455edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_construct(storage, num); 456edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 457edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 458edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 459edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_destroy(void* storage, size_t num) const 460edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 461edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_DTOR)) { 462edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_destroy(storage, num); 463edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 464edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 465edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 466edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_copy(void* dest, const void* from, size_t num) const 467edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 468edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_COPY)) { 469edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_copy(dest, from, num); 470edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 471edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project memcpy(dest, from, num*itemSize()); 472edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 473edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 474edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 475edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_splat(void* dest, const void* item, size_t num) const { 476edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_splat(dest, item, num); 477edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 478edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 479edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const { 480edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_move_forward(dest, from, num); 481edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 482edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 483edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const { 484edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_move_backward(dest, from, num); 485edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 486edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 487edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl1() { } 488edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl2() { } 489edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl3() { } 490edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl4() { } 491edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl5() { } 492edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl6() { } 493edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl7() { } 494edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl8() { } 495edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 496edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/*****************************************************************************/ 497edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 498edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags) 499edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project : VectorImpl(itemSize, flags) 500edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 501edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 502edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 503edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs) 504edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project: VectorImpl(rhs) 505edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 506edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 507edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 508edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl::~SortedVectorImpl() 509edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 510edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 511edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 512edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs) 513edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 514edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) ); 515edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 516edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 517edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::indexOf(const void* item) const 518edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 519edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return _indexOrderOf(item); 520edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 521edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 522edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectsize_t SortedVectorImpl::orderOf(const void* item) const 523edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 524edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t o; 525edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _indexOrderOf(item, &o); 526edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return o; 527edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 528edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 529edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const 530edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 531edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // binary search 532edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t err = NAME_NOT_FOUND; 533edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t l = 0; 534edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t h = size()-1; 535edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t mid; 536edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* a = arrayImpl(); 537edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t s = itemSize(); 538edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (l <= h) { 539edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mid = l + (h - l)/2; 540edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* const curr = reinterpret_cast<const char *>(a) + (mid*s); 541edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const int c = do_compare(curr, item); 542edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (c == 0) { 543edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = l = mid; 544edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project break; 545edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else if (c < 0) { 546edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project l = mid + 1; 547edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 548edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project h = mid - 1; 549edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 550edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 551edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (order) *order = l; 552edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return err; 553edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 554edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 555edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::add(const void* item) 556edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 557edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t order; 558edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t index = _indexOrderOf(item, &order); 559edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (index < 0) { 560edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project index = VectorImpl::insertAt(item, order, 1); 561edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 562edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project index = VectorImpl::replaceAt(item, index); 563edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 564edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return index; 565edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 566edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 567edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::merge(const VectorImpl& vector) 568edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 569edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // naive merge... 570edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!vector.isEmpty()) { 571edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* buffer = vector.arrayImpl(); 572edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t is = itemSize(); 573edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t s = vector.size(); 574edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project for (size_t i=0 ; i<s ; i++) { 575edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is ); 576edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (err<0) { 577edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return err; 578edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 579edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 580edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 581edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_ERROR; 582edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 583edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 584edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector) 585edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 586edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // we've merging a sorted vector... nice! 587edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t err = NO_ERROR; 588edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!vector.isEmpty()) { 589edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // first take care of the case where the vectors are sorted together 590edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) { 591edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0); 592edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) { 593edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector)); 594edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 595edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // this could be made a little better 596edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = merge(static_cast<const VectorImpl&>(vector)); 597edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 598edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 599edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return err; 600edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 601edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 602edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::remove(const void* item) 603edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 604edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t i = indexOf(item); 605edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (i>=0) { 606edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project VectorImpl::removeItemsAt(i, 1); 607edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 608edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return i; 609edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 610edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 611edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl1() { }; 612edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl2() { }; 613edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl3() { }; 614edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl4() { }; 615edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl5() { }; 616edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl6() { }; 617edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl7() { }; 618edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl8() { }; 619edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 620edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 621edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/*****************************************************************************/ 622edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 623edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; // namespace android 624edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 625