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    };
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
97protected:
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
118private:
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
140class SortedVectorImpl : public VectorImpl
141{
142public:
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
165protected:
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
178private:
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
203