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