VectorImpl.cpp revision caeddc7236a41bc51e60d54f5fa0e67cddd7aba6
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{ 111edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (index > size()) 112edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return BAD_INDEX; 113edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* where = _grow(index, vector.size()); 114edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where) { 115edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(where, vector.arrayImpl(), vector.size()); 116edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 117edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return where ? index : (ssize_t)NO_MEMORY; 118edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 119edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 120edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::appendVector(const VectorImpl& vector) 121edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 122edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return insertVectorAt(vector, size()); 123edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 124edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 125edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::insertAt(size_t index, size_t numItems) 126edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 127edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return insertAt(0, index, numItems); 128edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 129edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 130edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::insertAt(const void* item, size_t index, size_t numItems) 131edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 132edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (index > size()) 133edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return BAD_INDEX; 134edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* where = _grow(index, numItems); 135edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where) { 136edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (item) { 137edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_splat(where, item, numItems); 138edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 139edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_construct(where, numItems); 140edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 141edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 142edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return where ? index : (ssize_t)NO_MEMORY; 143edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 144edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 145edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatic int sortProxy(const void* lhs, const void* rhs, void* func) 146edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 147edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return (*(VectorImpl::compar_t)func)(lhs, rhs); 148edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 149edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 150edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatus_t VectorImpl::sort(VectorImpl::compar_t cmp) 151edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 152edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return sort(sortProxy, (void*)cmp); 153edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 154edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 155edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectstatus_t VectorImpl::sort(VectorImpl::compar_r_t cmp, void* state) 156edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 157edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // the sort must be stable. we're using insertion sort which 158edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // is well suited for small and already sorted arrays 159edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // for big arrays, it could be better to use mergesort 160edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const ssize_t count = size(); 161edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (count > 1) { 162edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = const_cast<void*>(arrayImpl()); 163edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* temp = 0; 164edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t i = 1; 165edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (i < count) { 166edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* item = reinterpret_cast<char*>(array) + mItemSize*(i); 167edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* curr = reinterpret_cast<char*>(array) + mItemSize*(i-1); 168edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (cmp(curr, item, state) > 0) { 169edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 170edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!temp) { 171edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // we're going to have to modify the array... 172edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project array = editArrayImpl(); 173edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!array) return NO_MEMORY; 174edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project temp = malloc(mItemSize); 175edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!temp) return NO_MEMORY; 176edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project item = reinterpret_cast<char*>(array) + mItemSize*(i); 177edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project curr = reinterpret_cast<char*>(array) + mItemSize*(i-1); 178caeddc7236a41bc51e60d54f5fa0e67cddd7aba6Mathias Agopian } else { 179caeddc7236a41bc51e60d54f5fa0e67cddd7aba6Mathias Agopian _do_destroy(temp, 1); 180edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 181edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 182edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(temp, item, 1); 183edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 184edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t j = i-1; 185edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* next = reinterpret_cast<char*>(array) + mItemSize*(i); 186edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do { 187caeddc7236a41bc51e60d54f5fa0e67cddd7aba6Mathias Agopian _do_destroy(next, 1); 188edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(next, curr, 1); 189edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project next = curr; 190edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project --j; 191edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project curr = reinterpret_cast<char*>(array) + mItemSize*(j); 192edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } while (j>=0 && (cmp(curr, temp, state) > 0)); 193edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 194caeddc7236a41bc51e60d54f5fa0e67cddd7aba6Mathias Agopian _do_destroy(next, 1); 195edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(next, temp, 1); 196edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 197edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project i++; 198edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 199edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 200edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (temp) { 201edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(temp, 1); 202edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project free(temp); 203edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 204edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 205edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_ERROR; 206edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 207edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 208edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::pop() 209edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 210edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (size()) 211edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project removeItemsAt(size()-1, 1); 212edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 213edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 214edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::push() 215edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 216edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project push(0); 217edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 218edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 219edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::push(const void* item) 220edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 221edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project insertAt(item, size()); 222edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 223edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 224edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::add() 225edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 226edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return add(0); 227edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 228edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 229edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::add(const void* item) 230edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 231edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return insertAt(item, size()); 232edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 233edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 234edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::replaceAt(size_t index) 235edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 236edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return replaceAt(0, index); 237edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 238edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 239edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::replaceAt(const void* prototype, size_t index) 240edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 241edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT(index<size(), 242edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "[%p] replace: index=%d, size=%d", this, (int)index, (int)size()); 243edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 244edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* item = editItemLocation(index); 245edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (item == 0) 246edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_MEMORY; 247edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(item, 1); 248edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (prototype == 0) { 249edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_construct(item, 1); 250edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 251edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(item, prototype, 1); 252edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 253edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return ssize_t(index); 254edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 255edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 256edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::removeItemsAt(size_t index, size_t count) 257edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 258edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT((index+count)<=size(), 259edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "[%p] remove: index=%d, count=%d, size=%d", 260edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)index, (int)count, (int)size()); 261edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 262edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if ((index+count) > size()) 263edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return BAD_VALUE; 264edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _shrink(index, count); 265edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return index; 266edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 267edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 268edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::finish_vector() 269edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 270edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 271edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = 0; 272edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mCount = 0; 273edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 274edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 275edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::clear() 276edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 277edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _shrink(0, mCount); 278edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 279edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 280edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid* VectorImpl::editItemLocation(size_t index) 281edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 282edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT(index<capacity(), 283edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "[%p] itemLocation: index=%d, capacity=%d, count=%d", 284edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)index, (int)capacity(), (int)mCount); 285edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 286edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* buffer = editArrayImpl(); 287edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (buffer) 288edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return reinterpret_cast<char*>(buffer) + index*mItemSize; 289edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return 0; 290edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 291edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 292edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectconst void* VectorImpl::itemLocation(size_t index) const 293edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 294edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project LOG_ASSERT(index<capacity(), 295edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project "[%p] editItemLocation: index=%d, capacity=%d, count=%d", 296edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project this, (int)index, (int)capacity(), (int)mCount); 297edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 298edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* buffer = arrayImpl(); 299edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (buffer) 300edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return reinterpret_cast<const char*>(buffer) + index*mItemSize; 301edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return 0; 302edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 303edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 304edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t VectorImpl::setCapacity(size_t new_capacity) 305edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 306edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t current_capacity = capacity(); 307edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t amount = new_capacity - size(); 308edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (amount <= 0) { 309edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // we can't reduce the capacity 310edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return current_capacity; 311edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 312edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 313edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 314edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = sb->data(); 315edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(array, mStorage, size()); 316edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 317edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = const_cast<void*>(array); 318edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 319edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_MEMORY; 320edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 321edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return new_capacity; 322edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 323edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 324edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::release_storage() 325edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 326edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mStorage) { 327edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage); 328edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb->release(SharedBuffer::eKeepStorage) == 1) { 329edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(mStorage, mCount); 330edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer::dealloc(sb); 331edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 332edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 333edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 334edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 335edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid* VectorImpl::_grow(size_t where, size_t amount) 336edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 337edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// LOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d", 338edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// this, (int)where, (int)amount, (int)mCount, (int)capacity()); 339edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 340edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where > mCount) 341edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project where = mCount; 342edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 343edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_size = mCount + amount; 344edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (capacity() < new_size) { 345edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2); 346edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// LOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity); 347edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if ((mStorage) && 348edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mCount==where) && 349edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_COPY) && 350edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_DTOR)) 351edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project { 352edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage); 353edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); 354edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = sb->data(); 355edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 356edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 357edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 358edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = sb->data(); 359edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where>0) { 360edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(array, mStorage, where); 361edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 362edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mCount>where) { 363edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize; 364edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 365edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(dest, from, mCount-where); 366edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 367edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 368edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = const_cast<void*>(array); 369edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 370edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 371edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 372edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t s = mCount-where; 373edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (s>0) { 374edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = editArrayImpl(); 375edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 376edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize; 377edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_move_forward(to, from, s); 378edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 379edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 380edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mCount += amount; 381edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* free_space = const_cast<void*>(itemLocation(where)); 382edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return free_space; 383edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 384edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 385edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_shrink(size_t where, size_t amount) 386edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 387edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!mStorage) 388edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return; 389edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 390edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// LOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d", 391edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// this, (int)where, (int)amount, (int)mCount, (int)capacity()); 392edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 393edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where >= mCount) 394edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project where = mCount - amount; 395edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 396edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_size = mCount - amount; 397edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (new_size*3 < capacity()) { 398edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t new_capacity = max(kMinVectorCapacity, new_size*2); 399edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// LOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity); 400edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if ((where == mCount-amount) && 401edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_COPY) && 402edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project (mFlags & HAS_TRIVIAL_DTOR)) 403edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project { 404edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage); 405edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize); 406edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = sb->data(); 407edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 408edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize); 409edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (sb) { 410edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = sb->data(); 411edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (where>0) { 412edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(array, mStorage, where); 413edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 414edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (mCount > where+amount) { 415edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize; 416edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize; 417edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_copy(dest, from, mCount-(where+amount)); 418edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 419edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project release_storage(); 420edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mStorage = const_cast<void*>(array); 421edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 422edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 423edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 424edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* array = editArrayImpl(); 425edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize; 426edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_destroy(to, amount); 427edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t s = mCount-(where+amount); 428edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (s>0) { 429edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize; 430edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _do_move_backward(to, from, s); 431edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 432edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 433edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 434edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // adjust the number of items... 435edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mCount -= amount; 436edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 437edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 438edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectsize_t VectorImpl::itemSize() const { 439edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return mItemSize; 440edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 441edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 442edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_construct(void* storage, size_t num) const 443edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 444edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_CTOR)) { 445edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_construct(storage, num); 446edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 447edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 448edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 449edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_destroy(void* storage, size_t num) const 450edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 451edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_DTOR)) { 452edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_destroy(storage, num); 453edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 454edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 455edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 456edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_copy(void* dest, const void* from, size_t num) const 457edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 458edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!(mFlags & HAS_TRIVIAL_COPY)) { 459edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_copy(dest, from, num); 460edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 461edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project memcpy(dest, from, num*itemSize()); 462edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 463edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 464edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 465edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_splat(void* dest, const void* item, size_t num) const { 466edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_splat(dest, item, num); 467edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 468edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 469edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const { 470edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_move_forward(dest, from, num); 471edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 472edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 473edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const { 474edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project do_move_backward(dest, from, num); 475edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 476edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 477edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl1() { } 478edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl2() { } 479edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl3() { } 480edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl4() { } 481edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl5() { } 482edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl6() { } 483edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl7() { } 484edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid VectorImpl::reservedVectorImpl8() { } 485edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 486edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/*****************************************************************************/ 487edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 488edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags) 489edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project : VectorImpl(itemSize, flags) 490edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 491edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 492edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 493edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs) 494edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project: VectorImpl(rhs) 495edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 496edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 497edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 498edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl::~SortedVectorImpl() 499edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 500edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 501edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 502edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source ProjectSortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs) 503edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 504edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) ); 505edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 506edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 507edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::indexOf(const void* item) const 508edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 509edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return _indexOrderOf(item); 510edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 511edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 512edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectsize_t SortedVectorImpl::orderOf(const void* item) const 513edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 514edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t o; 515edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project _indexOrderOf(item, &o); 516edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return o; 517edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 518edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 519edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const 520edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 521edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // binary search 522edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t err = NAME_NOT_FOUND; 523edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t l = 0; 524edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t h = size()-1; 525edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t mid; 526edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* a = arrayImpl(); 527edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t s = itemSize(); 528edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project while (l <= h) { 529edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project mid = l + (h - l)/2; 530edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* const curr = reinterpret_cast<const char *>(a) + (mid*s); 531edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const int c = do_compare(curr, item); 532edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (c == 0) { 533edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = l = mid; 534edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project break; 535edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else if (c < 0) { 536edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project l = mid + 1; 537edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 538edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project h = mid - 1; 539edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 540edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 541edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (order) *order = l; 542edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return err; 543edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 544edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 545edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::add(const void* item) 546edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 547edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t order; 548edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t index = _indexOrderOf(item, &order); 549edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (index < 0) { 550edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project index = VectorImpl::insertAt(item, order, 1); 551edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 552edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project index = VectorImpl::replaceAt(item, index); 553edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 554edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return index; 555edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 556edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 557edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::merge(const VectorImpl& vector) 558edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 559edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // naive merge... 560edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!vector.isEmpty()) { 561edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const void* buffer = vector.arrayImpl(); 562edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project const size_t is = itemSize(); 563edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project size_t s = vector.size(); 564edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project for (size_t i=0 ; i<s ; i++) { 565edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is ); 566edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (err<0) { 567edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return err; 568edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 569edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 570edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 571edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return NO_ERROR; 572edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 573edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 574edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector) 575edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 576edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // we've merging a sorted vector... nice! 577edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t err = NO_ERROR; 578edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (!vector.isEmpty()) { 579edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // first take care of the case where the vectors are sorted together 580edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) { 581edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0); 582edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) { 583edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector)); 584edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } else { 585edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project // this could be made a little better 586edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project err = merge(static_cast<const VectorImpl&>(vector)); 587edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 588edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 589edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return err; 590edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 591edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 592edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectssize_t SortedVectorImpl::remove(const void* item) 593edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project{ 594edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project ssize_t i = indexOf(item); 595edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project if (i>=0) { 596edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project VectorImpl::removeItemsAt(i, 1); 597edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project } 598edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project return i; 599edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} 600edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 601edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl1() { }; 602edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl2() { }; 603edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl3() { }; 604edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl4() { }; 605edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl5() { }; 606edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl6() { }; 607edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl7() { }; 608edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Projectvoid SortedVectorImpl::reservedSortedVectorImpl8() { }; 609edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 610edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 611edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project/*****************************************************************************/ 612edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 613edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project}; // namespace android 614edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 615