1/*
2 *  vector_impl.h
3 *  Android
4 *
5 *  Copyright 2005 The Android Open Source Project
6 *
7 */
8
9#ifndef ANDROID_VECTOR_IMPL_H
10#define ANDROID_VECTOR_IMPL_H
11
12#include <assert.h>
13#include <stdint.h>
14#include <sys/types.h>
15
16// ---------------------------------------------------------------------------
17// No user serviceable parts in here...
18// ---------------------------------------------------------------------------
19
20namespace android {
21
22/*!
23 * Implementation of the guts of the vector<> class
24 * this ensures backward binary compatibility and
25 * reduces code size.
26 * For performance reasons, we expose mStorage and mCount
27 * so these fields are set in stone.
28 *
29 */
30
31class VectorImpl
32{
33public:
34    enum { // flags passed to the ctor
35        HAS_TRIVIAL_CTOR    = 0x00000001,
36        HAS_TRIVIAL_DTOR    = 0x00000002,
37        HAS_TRIVIAL_COPY    = 0x00000004,
38        HAS_TRIVIAL_ASSIGN  = 0x00000008
39    };
40
41                            VectorImpl(size_t itemSize, uint32_t flags);
42                            VectorImpl(const VectorImpl& rhs);
43    virtual                 ~VectorImpl();
44
45    /*! must be called from subclasses destructor */
46            void            finish_vector();
47
48            VectorImpl&     operator = (const VectorImpl& rhs);
49
50    /*! C-style array access */
51    inline  const void*     arrayImpl() const       { return mStorage; }
52            void*           editArrayImpl();
53
54    /*! vector stats */
55    inline  size_t          size() const        { return mCount; }
56    inline  bool            isEmpty() const     { return mCount == 0; }
57            size_t          capacity() const;
58            ssize_t         setCapacity(size_t size);
59
60            /*! append/insert another vector */
61            ssize_t         insertVectorAt(const VectorImpl& vector, size_t index);
62            ssize_t         appendVector(const VectorImpl& vector);
63
64            /*! add/insert/replace items */
65            ssize_t         insertAt(size_t where, size_t numItems = 1);
66            ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
67            void            pop();
68            void            push();
69            void            push(const void* item);
70            ssize_t         add();
71            ssize_t         add(const void* item);
72            ssize_t         replaceAt(size_t index);
73            ssize_t         replaceAt(const void* item, size_t index);
74
75            /*! remove items */
76            ssize_t         removeItemsAt(size_t index, size_t count = 1);
77            void            clear();
78
79            const void*     itemLocation(size_t index) const;
80            void*           editItemLocation(size_t index);
81
82protected:
83            size_t          itemSize() const;
84            void            release_storage();
85
86    virtual void            do_construct(void* storage, size_t num) const = 0;
87    virtual void            do_destroy(void* storage, size_t num) const = 0;
88    virtual void            do_copy(void* dest, const void* from, size_t num) const = 0;
89    virtual void            do_splat(void* dest, const void* item, size_t num) const = 0;
90    virtual void            do_move_forward(void* dest, const void* from, size_t num) const = 0;
91    virtual void            do_move_backward(void* dest, const void* from, size_t num) const = 0;
92
93    // take care of FBC...
94    virtual void            reservedVectorImpl1();
95    virtual void            reservedVectorImpl2();
96    virtual void            reservedVectorImpl3();
97    virtual void            reservedVectorImpl4();
98    virtual void            reservedVectorImpl5();
99    virtual void            reservedVectorImpl6();
100    virtual void            reservedVectorImpl7();
101    virtual void            reservedVectorImpl8();
102
103private:
104        void* _grow(size_t where, size_t amount);
105        void  _shrink(size_t where, size_t amount);
106
107        inline void _do_construct(void* storage, size_t num) const;
108        inline void _do_destroy(void* storage, size_t num) const;
109        inline void _do_copy(void* dest, const void* from, size_t num) const;
110        inline void _do_splat(void* dest, const void* item, size_t num) const;
111        inline void _do_move_forward(void* dest, const void* from, size_t num) const;
112        inline void _do_move_backward(void* dest, const void* from, size_t num) const;
113
114            // These 2 fields are exposed in the inlines below,
115            // so they're set in stone.
116            void *      mStorage;   // base address of the vector
117            size_t      mCount;     // number of items
118
119    const   uint32_t    mFlags;
120    const   size_t      mItemSize;
121};
122
123
124
125class SortedVectorImpl : public VectorImpl
126{
127public:
128                            SortedVectorImpl(size_t itemSize, uint32_t flags);
129                            SortedVectorImpl(const VectorImpl& rhs);
130    virtual                 ~SortedVectorImpl();
131
132    SortedVectorImpl&     operator = (const SortedVectorImpl& rhs);
133
134    //! finds the index of an item
135            ssize_t         indexOf(const void* item) const;
136
137    //! finds where this item should be inserted
138            size_t          orderOf(const void* item) const;
139
140    //! add an item in the right place (or replaces it if there is one)
141            ssize_t         add(const void* item);
142
143    //! merges a vector into this one
144            ssize_t         merge(const VectorImpl& vector);
145            ssize_t         merge(const SortedVectorImpl& vector);
146
147    //! removes an item
148            ssize_t         remove(const void* item);
149
150protected:
151    virtual int             do_compare(const void* lhs, const void* rhs) const = 0;
152
153    // take care of FBC...
154    virtual void            reservedSortedVectorImpl1();
155    virtual void            reservedSortedVectorImpl2();
156    virtual void            reservedSortedVectorImpl3();
157    virtual void            reservedSortedVectorImpl4();
158    virtual void            reservedSortedVectorImpl5();
159    virtual void            reservedSortedVectorImpl6();
160    virtual void            reservedSortedVectorImpl7();
161    virtual void            reservedSortedVectorImpl8();
162
163private:
164            ssize_t         _indexOrderOf(const void* item, size_t* order = 0) const;
165
166            // these are made private, because they can't be used on a SortedVector
167            // (they don't have an implementation either)
168            ssize_t         add();
169            void            pop();
170            void            push();
171            void            push(const void* item);
172            ssize_t         insertVectorAt(const VectorImpl& vector, size_t index);
173            ssize_t         appendVector(const VectorImpl& vector);
174            ssize_t         insertAt(size_t where, size_t numItems = 1);
175            ssize_t         insertAt(const void* item, size_t where, size_t numItems = 1);
176            ssize_t         replaceAt(size_t index);
177            ssize_t         replaceAt(const void* item, size_t index);
178};
179
180}; // namespace android
181
182
183// ---------------------------------------------------------------------------
184
185#endif // ANDROID_VECTOR_IMPL_H
186