VectorImpl.h revision 7c1b96a165f970a09ed239bb4fb3f1b0d8f2a407 
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
29namespace 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
40class VectorImpl
41{
42public:
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
96protected:
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
117private:
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
139class SortedVectorImpl : public VectorImpl
140{
141public:
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
164protected:
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
177private:
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
200