blob: c4ec2ff97f66658c2ff43ab7a5df065e73550651 [file] [log] [blame]
The Android Open Source Project9066cfe2009-03-03 19:31:44 -08001/*
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,
The Android Open Source Project9066cfe2009-03-03 19:31:44 -080047 };
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
Jeff Brown5c225b12010-06-16 01:53:36 -070068 /*! append/insert another vector or array */
The Android Open Source Project9066cfe2009-03-03 19:31:44 -080069 ssize_t insertVectorAt(const VectorImpl& vector, size_t index);
70 ssize_t appendVector(const VectorImpl& vector);
Jeff Brown5c225b12010-06-16 01:53:36 -070071 ssize_t insertArrayAt(const void* array, size_t index, size_t length);
72 ssize_t appendArray(const void* array, size_t length);
The Android Open Source Project9066cfe2009-03-03 19:31:44 -080073
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();
Jeff Brown5c225b12010-06-16 01:53:36 -070081 ssize_t add(const void* item);
The Android Open Source Project9066cfe2009-03-03 19:31:44 -080082 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);
Jeff Brown5c225b12010-06-16 01:53:36 -0700189 ssize_t insertArrayAt(const void* array, size_t index, size_t length);
190 ssize_t appendArray(const void* array, size_t length);
The Android Open Source Project9066cfe2009-03-03 19:31:44 -0800191 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