1cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project/* 2cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Copyright (C) 2005 The Android Open Source Project 3cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 4cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * you may not use this file except in compliance with the License. 6cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * You may obtain a copy of the License at 7cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 8cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 10cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * See the License for the specific language governing permissions and 14cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * limitations under the License. 15cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 16cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 17cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#ifndef ANDROID_VECTOR_IMPL_H 18cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#define ANDROID_VECTOR_IMPL_H 19cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 20cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <assert.h> 21cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <stdint.h> 22cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <sys/types.h> 23cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#include <utils/Errors.h> 24cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 25cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// --------------------------------------------------------------------------- 26cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// No user serviceable parts in here... 27cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// --------------------------------------------------------------------------- 28cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 29cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectnamespace android { 30cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 31cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project/*! 32cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * Implementation of the guts of the vector<> class 33cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * this ensures backward binary compatibility and 34cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * reduces code size. 35cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * For performance reasons, we expose mStorage and mCount 36cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * so these fields are set in stone. 37cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project * 38cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project */ 39cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 40cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectclass VectorImpl 41cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 42cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectpublic: 43cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project enum { // flags passed to the ctor 44cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project HAS_TRIVIAL_CTOR = 0x00000001, 45cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project HAS_TRIVIAL_DTOR = 0x00000002, 46cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project HAS_TRIVIAL_COPY = 0x00000004, 47cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project }; 48cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 49cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project VectorImpl(size_t itemSize, uint32_t flags); 50cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project VectorImpl(const VectorImpl& rhs); 51cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project virtual ~VectorImpl(); 52cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 53cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /*! must be called from subclasses destructor */ 54cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void finish_vector(); 55cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 56cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project VectorImpl& operator = (const VectorImpl& rhs); 57cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 58cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /*! C-style array access */ 59cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project inline const void* arrayImpl() const { return mStorage; } 60cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* editArrayImpl(); 61cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 62cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /*! vector stats */ 63cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project inline size_t size() const { return mCount; } 64cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project inline bool isEmpty() const { return mCount == 0; } 65cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project size_t capacity() const; 66cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t setCapacity(size_t size); 67b73559d86c9017166da28e1d59a884f13417426dJesse Hall ssize_t resize(size_t size); 68cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 699efaaa43595307786dbf06760823c25cb16b1925Jeff Brown /*! append/insert another vector or array */ 70cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t insertVectorAt(const VectorImpl& vector, size_t index); 71cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t appendVector(const VectorImpl& vector); 729efaaa43595307786dbf06760823c25cb16b1925Jeff Brown ssize_t insertArrayAt(const void* array, size_t index, size_t length); 739efaaa43595307786dbf06760823c25cb16b1925Jeff Brown ssize_t appendArray(const void* array, size_t length); 74cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 75cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /*! add/insert/replace items */ 76cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t insertAt(size_t where, size_t numItems = 1); 77cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t insertAt(const void* item, size_t where, size_t numItems = 1); 78cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void pop(); 79cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void push(); 80cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void push(const void* item); 81cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t add(); 829efaaa43595307786dbf06760823c25cb16b1925Jeff Brown ssize_t add(const void* item); 83cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t replaceAt(size_t index); 84cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t replaceAt(const void* item, size_t index); 85cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 86cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project /*! remove items */ 87cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t removeItemsAt(size_t index, size_t count = 1); 88cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void clear(); 89cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 90cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const void* itemLocation(size_t index) const; 91cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* editItemLocation(size_t index); 92cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 93cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project typedef int (*compar_t)(const void* lhs, const void* rhs); 94cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project typedef int (*compar_r_t)(const void* lhs, const void* rhs, void* state); 95cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project status_t sort(compar_t cmp); 96cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project status_t sort(compar_r_t cmp, void* state); 97cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 98cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectprotected: 99cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project size_t itemSize() const; 100cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void release_storage(); 101cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 102cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project virtual void do_construct(void* storage, size_t num) const = 0; 103cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project virtual void do_destroy(void* storage, size_t num) const = 0; 104cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project virtual void do_copy(void* dest, const void* from, size_t num) const = 0; 105cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project virtual void do_splat(void* dest, const void* item, size_t num) const = 0; 106cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project virtual void do_move_forward(void* dest, const void* from, size_t num) const = 0; 107cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project virtual void do_move_backward(void* dest, const void* from, size_t num) const = 0; 108cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 109cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectprivate: 110cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void* _grow(size_t where, size_t amount); 111cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void _shrink(size_t where, size_t amount); 112cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 113cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project inline void _do_construct(void* storage, size_t num) const; 114cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project inline void _do_destroy(void* storage, size_t num) const; 115cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project inline void _do_copy(void* dest, const void* from, size_t num) const; 116cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project inline void _do_splat(void* dest, const void* item, size_t num) const; 117cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project inline void _do_move_forward(void* dest, const void* from, size_t num) const; 118cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project inline void _do_move_backward(void* dest, const void* from, size_t num) const; 119cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 120cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // These 2 fields are exposed in the inlines below, 121cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // so they're set in stone. 122cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void * mStorage; // base address of the vector 123cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project size_t mCount; // number of items 124cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 125cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const uint32_t mFlags; 126cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project const size_t mItemSize; 127cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project}; 128cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 129cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 130cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 131cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectclass SortedVectorImpl : public VectorImpl 132cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project{ 133cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectpublic: 134cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project SortedVectorImpl(size_t itemSize, uint32_t flags); 1352a929968e1038d1940bab08a678263db3c2655eaChih-Hung Hsieh explicit SortedVectorImpl(const VectorImpl& rhs); 136cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project virtual ~SortedVectorImpl(); 137cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 138cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project SortedVectorImpl& operator = (const SortedVectorImpl& rhs); 139cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 140cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project //! finds the index of an item 141cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t indexOf(const void* item) const; 142cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 143cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project //! finds where this item should be inserted 144cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project size_t orderOf(const void* item) const; 145cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 146cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project //! add an item in the right place (or replaces it if there is one) 147cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t add(const void* item); 148cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 149cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project //! merges a vector into this one 150cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t merge(const VectorImpl& vector); 151cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t merge(const SortedVectorImpl& vector); 152cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 153cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project //! removes an item 154cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t remove(const void* item); 155cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 156cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectprotected: 157cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project virtual int do_compare(const void* lhs, const void* rhs) const = 0; 158cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 159cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Projectprivate: 160cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t _indexOrderOf(const void* item, size_t* order = 0) const; 161cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 162cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // these are made private, because they can't be used on a SortedVector 163cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project // (they don't have an implementation either) 164cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t add(); 165cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void pop(); 166cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void push(); 167cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project void push(const void* item); 168cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t insertVectorAt(const VectorImpl& vector, size_t index); 169cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t appendVector(const VectorImpl& vector); 1709efaaa43595307786dbf06760823c25cb16b1925Jeff Brown ssize_t insertArrayAt(const void* array, size_t index, size_t length); 1719efaaa43595307786dbf06760823c25cb16b1925Jeff Brown ssize_t appendArray(const void* array, size_t length); 172cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t insertAt(size_t where, size_t numItems = 1); 173cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t insertAt(const void* item, size_t where, size_t numItems = 1); 174cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t replaceAt(size_t index); 175cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project ssize_t replaceAt(const void* item, size_t index); 176cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project}; 177cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 178cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project}; // namespace android 179cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 180cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 181cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project// --------------------------------------------------------------------------- 182cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project 183cbb1011c95e0c25c29e40e203a6a31bccd029da3The Android Open Source Project#endif // ANDROID_VECTOR_IMPL_H 184