Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4680 | right-hear | 1 | /** \file grower.h Template class that implements dynamic growing arrays. |
2 | * Yacas implements its own growing array class to ensure correct behaviour |
||
3 | * on all platforms (stl was still in development and not supported on all |
||
4 | * platforms when development started). |
||
5 | * |
||
6 | * grower started 1998 ayal Pinkus |
||
7 | * |
||
8 | */ |
||
9 | |||
10 | #ifndef _GROWER_H_ |
||
11 | #define _GROWER_H_ |
||
12 | |||
13 | #include "yacasbase.h" |
||
14 | #include "lispassert.h" |
||
15 | |||
16 | |||
17 | |||
18 | // Default placement versions of operator new and delete, placed here because I do not want to include |
||
19 | inline void* operator new(size_t, void* __p) throw() { return __p; } |
||
20 | inline void* operator new[](size_t, void* __p) throw() { return __p; } |
||
21 | inline void operator delete (void*, void*) throw() { } |
||
22 | inline void operator delete[](void*, void*) throw() { } |
||
23 | |||
24 | |||
25 | template |
||
26 | inline void constructAt(void * to_obj, const T * from_obj) |
||
27 | { |
||
28 | new (to_obj) T(*from_obj); |
||
29 | } |
||
30 | |||
31 | class ArrOps |
||
32 | { |
||
33 | public: |
||
34 | virtual bool isPOD() const { return false; } |
||
35 | virtual void construct(void * buffer) const = 0; |
||
36 | virtual void construct(void * to_obj, const void * from_obj) const = 0; |
||
37 | virtual void destruct(void * obj) const = 0; |
||
38 | virtual int granularity() const { return 8; } |
||
39 | static void resize(char** pArray, const ArrOps& opers, int& iSize, int& iCapacity, int aSize, int aItemSize, int ext); |
||
40 | static void remove(char** pArray, const ArrOps& opers, int& iSize, int aIndex, int aCount, int aItemSize); |
||
41 | static void reserve(char** pArray, int& iCapacity, int aSize, int aItemSize); |
||
42 | //static void* insert(char** pArray, const ArrOps& opers, int& iSize, void* aData, int aIndex, int aCount, int aSize, int aExtSize); |
||
43 | }; |
||
44 | |||
45 | template |
||
46 | class ArrOpsCustomObj : public ArrOps |
||
47 | { |
||
48 | public: |
||
49 | ArrOpsCustomObj() {} |
||
50 | inline void construct(void * buffer) const |
||
51 | { new (buffer) T; } |
||
52 | inline void construct(void * to_obj, const void * from_obj) const |
||
53 | { constructAt(to_obj, static_cast |
||
54 | inline void destruct(void * obj) const |
||
55 | { /*obj;*/ static_cast |
||
56 | //inline int size() const { return sizeof(T); } |
||
57 | }; |
||
58 | |||
59 | template |
||
60 | class ArrOpsPOD : public ArrOps |
||
61 | { |
||
62 | public: |
||
63 | ArrOpsPOD() {} |
||
64 | inline bool isPOD() const { return true; } |
||
65 | inline void construct(void * buffer) const {} |
||
66 | inline void construct(void * to_obj, const void * from_obj) const |
||
67 | { *static_cast |
||
68 | inline void destruct(void * obj) const {} |
||
69 | //inline int size() const { return sizeof(T); } |
||
70 | }; |
||
71 | |||
72 | template |
||
73 | class ArrOpsCustomPtr : public ArrOps |
||
74 | { |
||
75 | typedef T* TY; |
||
76 | public: |
||
77 | ArrOpsCustomPtr() {} |
||
78 | inline void construct(void * buffer) const |
||
79 | { *static_cast |
||
80 | inline void construct(void * to_obj, const void * from_obj) const |
||
81 | { *static_cast |
||
82 | inline void destruct(void * obj) const {} |
||
83 | //inline int size() const { return sizeof(TY); } |
||
84 | inline int granularity() const { return 8; } |
||
85 | }; |
||
86 | |||
87 | template |
||
88 | class ArrOpsDeletingObj {}; |
||
89 | |||
90 | template |
||
91 | class ArrOpsDeletingPtr : public ArrOpsCustomPtr |
||
92 | { |
||
93 | typedef T* TY; |
||
94 | public: |
||
95 | inline void destruct(void * obj) const |
||
96 | { delete *static_cast |
||
97 | }; |
||
98 | |||
99 | /** template class useful for implementing a dynamic growing array |
||
100 | * for any arbitrary type of object. If using the array to maintain |
||
101 | * objects, please use pointers to the objects, and use the |
||
102 | * CDeletingArrayGrower to automatically delete the objects at destruction. |
||
103 | */ |
||
104 | template |
||
105 | class CArrayGrower : public YacasBase |
||
106 | { |
||
107 | public: |
||
108 | /** ElementType can be used outside this class as the type of the |
||
109 | * object in the array. This is useful in templated functions that |
||
110 | * work on a CArrayGrower without being part of CArrayGrower |
||
111 | */ |
||
112 | typedef LispInt SizeType; |
||
113 | typedef T ElementType; |
||
114 | |||
115 | CArrayGrower() |
||
116 | : iArray(0) |
||
117 | , iSize(0) |
||
118 | , iCapacity(0) |
||
119 | , iArrayOwnedExternally(LispFalse) |
||
120 | { |
||
121 | } |
||
122 | virtual ~CArrayGrower() |
||
123 | { |
||
124 | Clear(); |
||
125 | } |
||
126 | inline void Clear() // oddly, only *one* use outside destructor!? |
||
127 | { |
||
128 | if (iSize) |
||
129 | { |
||
130 | const TOps opers; |
||
131 | if(!opers.isPOD()) |
||
132 | { |
||
133 | while (iSize) |
||
134 | opers.destruct(iArray + --iSize); |
||
135 | } |
||
136 | } |
||
137 | if (!iArrayOwnedExternally) |
||
138 | { |
||
139 | PlatFree(iArray); |
||
140 | } |
||
141 | iArray = 0; |
||
142 | iCapacity = iSize = 0; |
||
143 | iArrayOwnedExternally = LispFalse; |
||
144 | } |
||
145 | inline SizeType Size() const { return iSize; } |
||
146 | |||
147 | inline CArrayGrower(const CArrayGrower |
||
148 | : iArray(0) |
||
149 | , iSize(0) |
||
150 | , iCapacity(0) |
||
151 | , iArrayOwnedExternally(LispFalse) |
||
152 | { |
||
153 | // Make sure we're not accidentally copying a huge array. We want this system to stay efficient... |
||
154 | LISPASSERT(aOther.iSize == 0); |
||
155 | LISPASSERT(aOther.iArrayOwnedExternally == LispFalse); |
||
156 | } |
||
157 | |||
158 | inline const CArrayGrower |
||
159 | { |
||
160 | // Make sure we're not accidentally copying a huge array. We want this system to stay efficient... |
||
161 | LISPASSERT(iArray == 0); |
||
162 | LISPASSERT(iSize == 0); |
||
163 | LISPASSERT(iCapacity == 0); |
||
164 | LISPASSERT(iArrayOwnedExternally == LispFalse); |
||
165 | |||
166 | LISPASSERT(aOther.iSize == 0); |
||
167 | LISPASSERT(aOther.iArrayOwnedExternally == LispFalse); |
||
168 | return *this; |
||
169 | } |
||
170 | |||
171 | private: |
||
172 | |||
173 | void moreCapacity(SizeType aSize, int g) // almost independent of T |
||
174 | { |
||
175 | LISPASSERT(!iArrayOwnedExternally); |
||
176 | LISPASSERT(iCapacity >= 0); |
||
177 | // Compute a new iCapacity >= aSize, with iCapacity % g == 0. |
||
178 | // We assume g is a power of 2. (fwiw, in two's-complement, ~(g-1) == -g. |
||
179 | iCapacity = (aSize + g) & ~(g-1); |
||
180 | if (!iArray) |
||
181 | { |
||
182 | iArray = (ElementType*)PlatAlloc(iCapacity*sizeof(ElementType)); |
||
183 | } |
||
184 | else |
||
185 | { |
||
186 | // we assume 'memcpy' suffices for moving the existing items. |
||
187 | iArray = (ElementType*)PlatReAlloc(iArray,iCapacity*sizeof(ElementType)); |
||
188 | } |
||
189 | } |
||
190 | public: |
||
191 | inline void ResizeTo(SizeType aSize) |
||
192 | { |
||
193 | LISPASSERT(!iArrayOwnedExternally); |
||
194 | TOps opers; |
||
195 | if (aSize > iCapacity) |
||
196 | { |
||
197 | moreCapacity(aSize, opers.granularity()); |
||
198 | } |
||
199 | if (!opers.isPOD()) |
||
200 | { |
||
201 | if (iSize < aSize) |
||
202 | { |
||
203 | for (int ii = iSize; ii < aSize; ii++) |
||
204 | opers.construct(iArray + ii); |
||
205 | } |
||
206 | else |
||
207 | { |
||
208 | for (int ii = aSize; ii < iSize; ii++) |
||
209 | opers.destruct(iArray + ii); |
||
210 | } |
||
211 | } |
||
212 | iSize = aSize; |
||
213 | } |
||
214 | void Delete(SizeType aIndex, SizeType aCount=1) |
||
215 | { |
||
216 | LISPASSERT(aIndex>=0 && aIndex |
||
217 | ArrOps::remove((char**)&iArray, TOps(), iSize, aIndex, aCount, sizeof(ElementType)); |
||
218 | } |
||
219 | inline LispBoolean ArrayOwnedExternally() |
||
220 | { |
||
221 | return iArrayOwnedExternally; |
||
222 | } |
||
223 | public: |
||
224 | /// Access to an element in the array |
||
225 | inline ElementType& operator[](const SizeType aIndex) const |
||
226 | { |
||
227 | return iArray[aIndex]; |
||
228 | } |
||
229 | |||
230 | /// Append an element to an array |
||
231 | template |
||
232 | inline void Append(const Type& aVal) |
||
233 | { |
||
234 | if (iSize >= iCapacity) moreCapacity(iSize+1, TOps().granularity()); |
||
235 | new ((void *)(iArray+iSize)) ElementType(aVal); |
||
236 | ++iSize; |
||
237 | } |
||
238 | |||
239 | /// Insert object aObj at aIndex, aCount times. |
||
240 | inline void Insert(SizeType aIndex, const ElementType& aObj, SizeType aCount=1) |
||
241 | { |
||
242 | const SizeType oldItems = iSize; |
||
243 | LISPASSERT(aIndex <= oldItems && aCount >= 0); |
||
244 | ResizeTo(iSize+aCount); |
||
245 | ElementType * pOld = iArray+oldItems; |
||
246 | ElementType * pEnd = iArray+iSize; |
||
247 | int i = iSize - aIndex; // = (oldItems - aIndex) + aCount |
||
248 | for ( ; i > aCount; i--) |
||
249 | *--pEnd = *--pOld; |
||
250 | while (i-- > 0) |
||
251 | *--pEnd = aObj; |
||
252 | } |
||
253 | |||
254 | /** Set the array to an external array. This means the array will |
||
255 | * not be freed at destruction time |
||
256 | */ |
||
257 | inline void SetExternalArray(ElementType* aArray, SizeType aSize) |
||
258 | { |
||
259 | LISPASSERT(!iArray || iArrayOwnedExternally == LispTrue); |
||
260 | iArray = aArray; |
||
261 | iSize = aSize; |
||
262 | iArrayOwnedExternally = LispTrue; |
||
263 | iCapacity = -10000; // Setting iCapacity should not strictly be necessary, setting it to hugely negative number will hopefully force a fail. |
||
264 | } |
||
265 | |||
266 | /// Copy the array to another array |
||
267 | inline void CopyToExternalArray(ElementType * aArray) |
||
268 | { |
||
269 | PlatMemCopy(aArray,iArray,iSize*sizeof(ElementType)); |
||
270 | } |
||
271 | |||
272 | protected: |
||
273 | inline ElementType * elements() const { return iArray; } |
||
274 | private: |
||
275 | ElementType * iArray; |
||
276 | SizeType iSize; |
||
277 | SizeType iCapacity; |
||
278 | LispBoolean iArrayOwnedExternally; |
||
279 | }; |
||
280 | |||
281 | /** \class CDeletingArrayGrower calls delete on each element in the |
||
282 | * array at destruction time. This is useful if the array is a list |
||
283 | * of pointers to objects. |
||
284 | */ |
||
285 | |||
286 | template |
||
287 | class CDeletingArrayGrower : public CArrayGrower |
||
288 | { |
||
289 | public: |
||
290 | CDeletingArrayGrower() {} |
||
291 | }; |
||
292 | |||
293 | #endif=> |
||
294 | |||
295 |