1dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/* 2dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * vector_impl.h 3dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Android 4dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * 5dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Copyright 2005 The Android Open Source Project 6dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * 7dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 8dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 9dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#ifndef ANDROID_VECTOR_IMPL_H 10dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#define ANDROID_VECTOR_IMPL_H 11dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 12dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <assert.h> 13dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <stdint.h> 14dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#include <sys/types.h> 15dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 16dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// --------------------------------------------------------------------------- 17dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// No user serviceable parts in here... 18dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// --------------------------------------------------------------------------- 19dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 20dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectnamespace android { 21dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 22dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project/*! 23dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * Implementation of the guts of the vector<> class 24dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * this ensures backward binary compatibility and 25dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * reduces code size. 26dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * For performance reasons, we expose mStorage and mCount 27dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * so these fields are set in stone. 28dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project * 29dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project */ 30dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 31dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectclass VectorImpl 32dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 33dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectpublic: 34dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project enum { // flags passed to the ctor 35dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project HAS_TRIVIAL_CTOR = 0x00000001, 36dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project HAS_TRIVIAL_DTOR = 0x00000002, 37dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project HAS_TRIVIAL_COPY = 0x00000004, 38dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project HAS_TRIVIAL_ASSIGN = 0x00000008 39dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project }; 40dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 41dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project VectorImpl(size_t itemSize, uint32_t flags); 42dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project VectorImpl(const VectorImpl& rhs); 43dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual ~VectorImpl(); 44dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 45dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project /*! must be called from subclasses destructor */ 46dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void finish_vector(); 47dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 48dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project VectorImpl& operator = (const VectorImpl& rhs); 49dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 50dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project /*! C-style array access */ 51dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project inline const void* arrayImpl() const { return mStorage; } 52dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void* editArrayImpl(); 53dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 54dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project /*! vector stats */ 55dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project inline size_t size() const { return mCount; } 56dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project inline bool isEmpty() const { return mCount == 0; } 57dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project size_t capacity() const; 58dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t setCapacity(size_t size); 59dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 60dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project /*! append/insert another vector */ 61dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t insertVectorAt(const VectorImpl& vector, size_t index); 62dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t appendVector(const VectorImpl& vector); 63dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 64dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project /*! add/insert/replace items */ 65dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t insertAt(size_t where, size_t numItems = 1); 66dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t insertAt(const void* item, size_t where, size_t numItems = 1); 67dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void pop(); 68dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void push(); 69dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void push(const void* item); 70dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t add(); 71dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t add(const void* item); 72dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t replaceAt(size_t index); 73dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t replaceAt(const void* item, size_t index); 74dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 75dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project /*! remove items */ 76dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t removeItemsAt(size_t index, size_t count = 1); 77dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void clear(); 78dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 79dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project const void* itemLocation(size_t index) const; 80dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void* editItemLocation(size_t index); 81dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 82dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectprotected: 83dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project size_t itemSize() const; 84dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void release_storage(); 85dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 86dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void do_construct(void* storage, size_t num) const = 0; 87dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void do_destroy(void* storage, size_t num) const = 0; 88dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void do_copy(void* dest, const void* from, size_t num) const = 0; 89dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void do_splat(void* dest, const void* item, size_t num) const = 0; 90dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void do_move_forward(void* dest, const void* from, size_t num) const = 0; 91dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void do_move_backward(void* dest, const void* from, size_t num) const = 0; 92dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 93dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // take care of FBC... 94dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedVectorImpl1(); 95dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedVectorImpl2(); 96dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedVectorImpl3(); 97dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedVectorImpl4(); 98dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedVectorImpl5(); 99dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedVectorImpl6(); 100dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedVectorImpl7(); 101dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedVectorImpl8(); 102dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 103dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectprivate: 104dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void* _grow(size_t where, size_t amount); 105dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void _shrink(size_t where, size_t amount); 106dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 107dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project inline void _do_construct(void* storage, size_t num) const; 108dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project inline void _do_destroy(void* storage, size_t num) const; 109dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project inline void _do_copy(void* dest, const void* from, size_t num) const; 110dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project inline void _do_splat(void* dest, const void* item, size_t num) const; 111dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project inline void _do_move_forward(void* dest, const void* from, size_t num) const; 112dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project inline void _do_move_backward(void* dest, const void* from, size_t num) const; 113dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 114dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // These 2 fields are exposed in the inlines below, 115dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // so they're set in stone. 116dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void * mStorage; // base address of the vector 117dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project size_t mCount; // number of items 118dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 119dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project const uint32_t mFlags; 120dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project const size_t mItemSize; 121dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}; 122dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 123dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 124dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 125dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectclass SortedVectorImpl : public VectorImpl 126dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project{ 127dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectpublic: 128dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project SortedVectorImpl(size_t itemSize, uint32_t flags); 129dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project SortedVectorImpl(const VectorImpl& rhs); 130dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual ~SortedVectorImpl(); 131dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 132dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project SortedVectorImpl& operator = (const SortedVectorImpl& rhs); 133dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 134dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project //! finds the index of an item 135dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t indexOf(const void* item) const; 136dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 137dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project //! finds where this item should be inserted 138dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project size_t orderOf(const void* item) const; 139dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 140dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project //! add an item in the right place (or replaces it if there is one) 141dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t add(const void* item); 142dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 143dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project //! merges a vector into this one 144dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t merge(const VectorImpl& vector); 145dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t merge(const SortedVectorImpl& vector); 146dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 147dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project //! removes an item 148dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t remove(const void* item); 149dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 150dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectprotected: 151dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual int do_compare(const void* lhs, const void* rhs) const = 0; 152dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 153dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // take care of FBC... 154dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedSortedVectorImpl1(); 155dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedSortedVectorImpl2(); 156dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedSortedVectorImpl3(); 157dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedSortedVectorImpl4(); 158dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedSortedVectorImpl5(); 159dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedSortedVectorImpl6(); 160dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedSortedVectorImpl7(); 161dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project virtual void reservedSortedVectorImpl8(); 162dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 163dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Projectprivate: 164dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t _indexOrderOf(const void* item, size_t* order = 0) const; 165dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 166dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // these are made private, because they can't be used on a SortedVector 167dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project // (they don't have an implementation either) 168dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t add(); 169dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void pop(); 170dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void push(); 171dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project void push(const void* item); 172dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t insertVectorAt(const VectorImpl& vector, size_t index); 173dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t appendVector(const VectorImpl& vector); 174dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t insertAt(size_t where, size_t numItems = 1); 175dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t insertAt(const void* item, size_t where, size_t numItems = 1); 176dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t replaceAt(size_t index); 177dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project ssize_t replaceAt(const void* item, size_t index); 178dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}; 179dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 180dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project}; // namespace android 181dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 182dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 183dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project// --------------------------------------------------------------------------- 184dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project 185dd7bc3319deb2b77c5d07a51b7d6cd7e11b5beb0The Android Open Source Project#endif // ANDROID_VECTOR_IMPL_H 186