include/utils/VectorImpl.h

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