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