frameworks/base/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     };
  48
  49                             VectorImpl(size_t itemSize, uint32_t flags);
  50                             VectorImpl(const VectorImpl& rhs);
  51     virtual                 ~VectorImpl();
  52
  53     /*! must be called from subclasses destructor */
  54             void            finish_vector();
  55
  56             VectorImpl&     operator = (const VectorImpl& rhs);
  57
  58     /*! C-style array access */
  59     inline  const void*     arrayImpl() const       { return mStorage; }
  60             void*           editArrayImpl();
  61
  62     /*! vector stats */
  63     inline  size_t          size() const        { return mCount; }
  64     inline  bool            isEmpty() const     { return mCount == 0; }
  65             size_t          capacity() const;
  66             ssize_t         setCapacity(size_t size);
  67
  68             /*! append/insert another vector or array */
  69             ssize_t         insertVectorAt(const VectorImpl& vector, size_t index);
  70             ssize_t         appendVector(const VectorImpl& vector);
  71             ssize_t         insertArrayAt(const void* array, size_t index, size_t length);
  72             ssize_t         appendArray(const void* array, size_t length);
  73
  74             /*! add/insert/replace items */
  75             ssize_t         insertAt(size_t where, size_t numItems = 1);
  76             ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
  77             void            pop();
  78             void            push();
  79             void            push(const void* item);
  80             ssize_t         add();
  81             ssize_t         add(const void* item);
  82             ssize_t         replaceAt(size_t index);
  83             ssize_t         replaceAt(const void* item, size_t index);
  84
  85             /*! remove items */
  86             ssize_t         removeItemsAt(size_t index, size_t count = 1);
  87             void            clear();
  88
  89             const void*     itemLocation(size_t index) const;
  90             void*           editItemLocation(size_t index);
  91
  92             typedef int (*compar_t)(const void* lhs, const void* rhs);
  93             typedef int (*compar_r_t)(const void* lhs, const void* rhs, void* state);
  94             status_t        sort(compar_t cmp);
  95             status_t        sort(compar_r_t cmp, void* state);
  96
  97 protected:
  98             size_t          itemSize() const;
  99             void            release_storage();
 100
 101     virtual void            do_construct(void* storage, size_t num) const = 0;
 102     virtual void            do_destroy(void* storage, size_t num) const = 0;
 103     virtual void            do_copy(void* dest, const void* from, size_t num) const = 0;
 104     virtual void            do_splat(void* dest, const void* item, size_t num) const = 0;
 105     virtual void            do_move_forward(void* dest, const void* from, size_t num) const = 0;
 106     virtual void            do_move_backward(void* dest, const void* from, size_t num) const = 0;
 107
 108     // take care of FBC...
 109     virtual void            reservedVectorImpl1();
 110     virtual void            reservedVectorImpl2();
 111     virtual void            reservedVectorImpl3();
 112     virtual void            reservedVectorImpl4();
 113     virtual void            reservedVectorImpl5();
 114     virtual void            reservedVectorImpl6();
 115     virtual void            reservedVectorImpl7();
 116     virtual void            reservedVectorImpl8();
 117
 118 private:
 119         void* _grow(size_t where, size_t amount);
 120         void  _shrink(size_t where, size_t amount);
 121
 122         inline void _do_construct(void* storage, size_t num) const;
 123         inline void _do_destroy(void* storage, size_t num) const;
 124         inline void _do_copy(void* dest, const void* from, size_t num) const;
 125         inline void _do_splat(void* dest, const void* item, size_t num) const;
 126         inline void _do_move_forward(void* dest, const void* from, size_t num) const;
 127         inline void _do_move_backward(void* dest, const void* from, size_t num) const;
 128
 129             // These 2 fields are exposed in the inlines below,
 130             // so they're set in stone.
 131             void *      mStorage;   // base address of the vector
 132             size_t      mCount;     // number of items
 133
 134     const   uint32_t    mFlags;
 135     const   size_t      mItemSize;
 136 };
 137
 138
 139
 140 class SortedVectorImpl : public VectorImpl
 141 {
 142 public:
 143                             SortedVectorImpl(size_t itemSize, uint32_t flags);
 144                             SortedVectorImpl(const VectorImpl& rhs);
 145     virtual                 ~SortedVectorImpl();
 146
 147     SortedVectorImpl&     operator = (const SortedVectorImpl& rhs);
 148
 149     //! finds the index of an item
 150             ssize_t         indexOf(const void* item) const;
 151
 152     //! finds where this item should be inserted
 153             size_t          orderOf(const void* item) const;
 154
 155     //! add an item in the right place (or replaces it if there is one)
 156             ssize_t         add(const void* item);
 157
 158     //! merges a vector into this one
 159             ssize_t         merge(const VectorImpl& vector);
 160             ssize_t         merge(const SortedVectorImpl& vector);
 161
 162     //! removes an item
 163             ssize_t         remove(const void* item);
 164
 165 protected:
 166     virtual int             do_compare(const void* lhs, const void* rhs) const = 0;
 167
 168     // take care of FBC...
 169     virtual void            reservedSortedVectorImpl1();
 170     virtual void            reservedSortedVectorImpl2();
 171     virtual void            reservedSortedVectorImpl3();
 172     virtual void            reservedSortedVectorImpl4();
 173     virtual void            reservedSortedVectorImpl5();
 174     virtual void            reservedSortedVectorImpl6();
 175     virtual void            reservedSortedVectorImpl7();
 176     virtual void            reservedSortedVectorImpl8();
 177
 178 private:
 179             ssize_t         _indexOrderOf(const void* item, size_t* order = 0) const;
 180
 181             // these are made private, because they can't be used on a SortedVector
 182             // (they don't have an implementation either)
 183             ssize_t         add();
 184             void            pop();
 185             void            push();
 186             void            push(const void* item);
 187             ssize_t         insertVectorAt(const VectorImpl& vector, size_t index);
 188             ssize_t         appendVector(const VectorImpl& vector);
 189             ssize_t         insertArrayAt(const void* array, size_t index, size_t length);
 190             ssize_t         appendArray(const void* array, size_t length);
 191             ssize_t         insertAt(size_t where, size_t numItems = 1);
 192             ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
 193             ssize_t         replaceAt(size_t index);
 194             ssize_t         replaceAt(const void* item, size_t index);
 195 };
 196
 197 }; // namespace android
 198
 199
 200 // ---------------------------------------------------------------------------
 201
 202 #endif // ANDROID_VECTOR_IMPL_H