1/*
2 * Copyright 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_PIXELFLINGER_VECTOR_IMPL_H
18#define ANDROID_PIXELFLINGER_VECTOR_IMPL_H
19
20#include <assert.h>
21#include <stdint.h>
22#include <sys/types.h>
23
24// ---------------------------------------------------------------------------
25// No user serviceable parts in here...
26// ---------------------------------------------------------------------------
27
28namespace android {
29namespace tinyutils {
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
91protected:
92            size_t          itemSize() const;
93            void            release_storage();
94
95    virtual void            do_construct(void* storage, size_t num) const = 0;
96    virtual void            do_destroy(void* storage, size_t num) const = 0;
97    virtual void            do_copy(void* dest, const void* from, size_t num) const = 0;
98    virtual void            do_splat(void* dest, const void* item, size_t num) const = 0;
99    virtual void            do_move_forward(void* dest, const void* from, size_t num) const = 0;
100    virtual void            do_move_backward(void* dest, const void* from, size_t num) const = 0;
101
102    // take care of FBC...
103    virtual void            reservedVectorImpl1();
104    virtual void            reservedVectorImpl2();
105    virtual void            reservedVectorImpl3();
106    virtual void            reservedVectorImpl4();
107    virtual void            reservedVectorImpl5();
108    virtual void            reservedVectorImpl6();
109    virtual void            reservedVectorImpl7();
110    virtual void            reservedVectorImpl8();
111
112private:
113        void* _grow(size_t where, size_t amount);
114        void  _shrink(size_t where, size_t amount);
115
116        inline void _do_construct(void* storage, size_t num) const;
117        inline void _do_destroy(void* storage, size_t num) const;
118        inline void _do_copy(void* dest, const void* from, size_t num) const;
119        inline void _do_splat(void* dest, const void* item, size_t num) const;
120        inline void _do_move_forward(void* dest, const void* from, size_t num) const;
121        inline void _do_move_backward(void* dest, const void* from, size_t num) const;
122
123            // These 2 fields are exposed in the inlines below,
124            // so they're set in stone.
125            void *      mStorage;   // base address of the vector
126            size_t      mCount;     // number of items
127
128    const   uint32_t    mFlags;
129    const   size_t      mItemSize;
130};
131
132
133
134class SortedVectorImpl : public VectorImpl
135{
136public:
137                            SortedVectorImpl(size_t itemSize, uint32_t flags);
138                            SortedVectorImpl(const VectorImpl& rhs);
139    virtual                 ~SortedVectorImpl();
140
141    SortedVectorImpl&     operator = (const SortedVectorImpl& rhs);
142
143    //! finds the index of an item
144            ssize_t         indexOf(const void* item) const;
145
146    //! finds where this item should be inserted
147            size_t          orderOf(const void* item) const;
148
149    //! add an item in the right place (or replaces it if there is one)
150            ssize_t         add(const void* item);
151
152    //! merges a vector into this one
153            ssize_t         merge(const VectorImpl& vector);
154            ssize_t         merge(const SortedVectorImpl& vector);
155
156    //! removes an item
157            ssize_t         remove(const void* item);
158
159protected:
160    virtual int             do_compare(const void* lhs, const void* rhs) const = 0;
161
162    // take care of FBC...
163    virtual void            reservedSortedVectorImpl1();
164    virtual void            reservedSortedVectorImpl2();
165    virtual void            reservedSortedVectorImpl3();
166    virtual void            reservedSortedVectorImpl4();
167    virtual void            reservedSortedVectorImpl5();
168    virtual void            reservedSortedVectorImpl6();
169    virtual void            reservedSortedVectorImpl7();
170    virtual void            reservedSortedVectorImpl8();
171
172private:
173            ssize_t         _indexOrderOf(const void* item, size_t* order = 0) const;
174
175            // these are made private, because they can't be used on a SortedVector
176            // (they don't have an implementation either)
177            ssize_t         add();
178            void            pop();
179            void            push();
180            void            push(const void* item);
181            ssize_t         insertVectorAt(const VectorImpl& vector, size_t index);
182            ssize_t         appendVector(const VectorImpl& vector);
183            ssize_t         insertAt(size_t where, size_t numItems = 1);
184            ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
185            ssize_t         replaceAt(size_t index);
186            ssize_t         replaceAt(const void* item, size_t index);
187};
188
189} // namespace tinyutils
190} // namespace android
191
192
193// ---------------------------------------------------------------------------
194
195#endif // ANDROID_PIXELFLINGER_VECTOR_IMPL_H
196