11 extern int __ecereVMethodID_class_OnUnserialize;
12 extern int __ecereVMethodID_class_OnCompare;
14 // qsort_r/_s wrappers adapted from public domain code by Isaac Turner
15 #if !defined(ECERE_BOOTSTRAP)
16 #if (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined __bsdi__ || defined OpenBSD3_1 || defined OpenBSD3_9 || defined __OpenBSD__ || \
17 defined __NetBSD__ || defined __DragonFly__ || defined AMIGA)
19 extern void qsort_r(void *base, uintsize nel, uintsize width, void *arg, int (*compare)(void *, const void *, const void *));
20 #elif defined(__WIN32__)
21 extern void qsort_s(void *base, uintsize nel, uintsize width, int (*compare)(void *, const void *, const void *), void * arg);
22 #elif (defined __GLIBC__ && ((__GLIBC__ > 2) || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)))
24 extern void qsort_r(void *base, uintsize nel, uintsize width, int(* compare)(const void *, const void *, void *), void *arg);
29 // Quick Sort algorithm adapted from public domain code by Darel Rex Finley
30 static inline void quickSort(void *base, uintsize nel, uintsize w, char * piv, int (*compare)(void *, const void *, const void *), void *arg)
32 #define MAX_LEVELS 300
33 uintsize beg[MAX_LEVELS], end[MAX_LEVELS];
40 uintsize L = beg[frame], R = end[frame]-1;
43 memcpy(piv, (char *)base + L*w, w);
46 while(compare(arg, (char *)base + (R*w), piv) >= 0 && L < R) R--;
49 memcpy((char *)base + L*w, (char *)base + R*w, w);
52 while(compare(arg, (char *)base + (L*w), piv) <= 0 && L < R) L++;
55 memcpy((char *)base + R*w, (char *)base + L*w, w);
59 memcpy((char *)base + L*w, piv, w);
61 end[frame+1] = end[frame];
64 // Process smaller partition first
65 if(end[frame]-beg[frame] > end[frame-1]-beg[frame-1])
68 swap = beg[frame]; beg[frame] = beg[frame-1]; beg[frame-1] = swap;
69 swap = end[frame]; end[frame] = end[frame-1]; end[frame-1] = swap;
78 static struct SortRData { void *arg; int (*compare)(void *, const void *, const void *); };
80 static inline int compareDeref (SortRData cs, const void **a, const void **b) { return cs.compare(cs.arg, *a, *b); }
81 static inline int compareDescDeref (SortRData cs, const void **a, const void **b) { return -cs.compare(cs.arg, *a, *b); }
82 static inline int compareDesc (SortRData cs, const void * a, const void * b) { return -cs.compare(cs.arg, a, b); }
84 static inline int compareArgLast (const void * a, const void * b, SortRData cs) { return cs.compare(cs.arg, a, b); }
85 static inline int compareDerefArgLast (const void **a, const void **b, SortRData cs) { return cs.compare(cs.arg, *a, *b); }
86 static inline int compareDescDerefArgLast (const void **a, const void **b, SortRData cs) { return -cs.compare(cs.arg, *a, *b); }
87 static inline int compareDescArgLast (const void * a, const void * b, SortRData cs) { return -cs.compare(cs.arg, a, b); }
89 static inline void _qsortrx(void *base, uintsize nel, uintsize width,
90 int (*compare)(void *arg, const void *a, const void *b),
91 int (*optCompareArgLast)(const void *a, const void *b, void *arg),
93 bool deref, bool ascending)
95 #if defined(GLIBC) && !defined(ECERE_BOOTSTRAP)
96 if(!deref && ascending && optCompareArgLast)
97 qsort_r(base, nel, width, optCompareArgLast, arg);
100 SortRData s { arg, compare };
101 #define compare_fn !deref && ascending ? compareArgLast : !deref ? compareDescArgLast : ascending ? compareDerefArgLast : compareDescDerefArgLast
102 qsort_r(base, nel, width, compare_fn, s);
106 if(!deref && ascending)
108 #if defined(BSD) && !defined(ECERE_BOOTSTRAP)
109 qsort_r(base, nel, width, arg, compare);
110 #elif defined(__WIN32__) && !defined(ECERE_BOOTSTRAP)
111 qsort_s(base, nel, width, compare, arg);
114 char * buf = new char[width];
115 quickSort(base, nel, width, buf, compare, arg);
122 SortRData s { arg, compare };
123 #define compare_fn !deref ? compareDesc : ascending ? compareDeref : compareDescDeref
124 #if defined(BSD) && !defined(ECERE_BOOTSTRAP)
125 qsort_r(base, nel, width, s, compare_fn);
126 #elif defined(__WIN32__) && !defined(ECERE_BOOTSTRAP)
127 qsort_s(base, nel, width, compare_fn, s);
130 char * buf = new char[width];
131 quickSort(base, nel, width, buf, compare_fn, s);
140 public void qsortrx(void *base, uintsize nel, uintsize width,
141 int (*compare)(void *arg, const void *a, const void *b),
142 int (*optCompareArgLast)(const void *a, const void *b, void *arg),
144 bool deref, bool ascending)
146 _qsortrx(base, nel, width, compare, optCompareArgLast, arg, deref, ascending);
149 public void qsortr(void *base, uintsize nel, uintsize width, int (*compare)(void *arg, const void *a, const void *b), void *arg)
151 _qsortrx(base, nel, width, compare, null, arg, false, true);
154 public class Array : Container
168 void OnUnserialize(IOChannel channel)
170 Array array = eInstance_New(_class); //.fullName);
172 Class Dclass = class(D);
176 //printf("%d %ss\n", count, Dclass.name);
181 for(c = 0; c < count; c++)
182 ((void (*)(void *, void *, void *))(void *)Dclass._vTbl[__ecereVMethodID_class_OnUnserialize])
183 (Dclass, ((byte *)array.array) + Dclass.typeSize * c, channel);
187 // Generic iterator support
188 IteratorPointer GetFirst() { return (IteratorPointer)array; }
189 IteratorPointer GetLast() { return (IteratorPointer)(array ? (array + (count - 1)) : null); }
190 IteratorPointer GetPrev(IteratorPointer ip)
193 return (IteratorPointer)((item && item > array) ? (item - 1) : null);
195 IteratorPointer GetNext(IteratorPointer ip)
198 return (IteratorPointer)((item && item < array + count - 1) ? (item + 1) : null);
200 T GetData(IteratorPointer ip)
205 bool SetData(IteratorPointer ip, T value)
211 IteratorPointer GetAtPosition(const I pos, bool create, bool * justAdded)
213 if((int)pos > count && create)
215 if((int)pos + 1 > minAllocSize)
216 array = renew array T[(int)pos + 1];
217 count = (int)pos + 1;
218 if(justAdded) *justAdded = true;
219 #if !defined(MEMINFO) && defined(MEMTRACKING)
222 MemBlock block = (MemBlock)((byte *)array - sizeof(class MemBlock));
223 block._class = class(T);
227 return ((int)pos < count && array) ? (IteratorPointer)(array + (int)pos) : null;
229 IteratorPointer Insert(IteratorPointer ip, T value)
233 int offset = after ? (after - array) : 0;
234 if(count + 1 > minAllocSize)
236 array = renew array T[count + 1];
237 if(after) after = array + offset;
239 memmove(after ? (after + 2) : (array + 1), after ? (after + 1) : array, (count - offset) * class(T).typeSize);
245 return (IteratorPointer)(after ? (after + 1) : array);
247 uint tsize = class(T).typeSize;
248 byte * pos = ip ? ((byte *)ip + tsize) : (byte *)array;
249 if(count+1 > minAllocSize)
251 int offset = pos - (byte *)array;
252 array = renew array T[count + 1];
253 pos = (byte *)array+offset;
255 memmove(pos + tsize, pos, (byte *)array+(count++) * tsize - pos);
257 return (IteratorPointer)pos;
260 IteratorPointer Add(T value)
262 if(count + 1 > minAllocSize)
263 array = renew array T[count + 1];
264 array[count] = value;
265 return (IteratorPointer)(array + (count++));
268 void Remove(IteratorPointer ip)
271 memmove(it, it + 1, (count - (it - array) - 1) * class(T).typeSize);
273 if(count + 1 > minAllocSize)
274 array = renew array T[count];
277 void Move(IteratorPointer ip, IteratorPointer afterIp)
281 T * after = (T *)afterIp;
285 virtual void RemoveAll()
287 if(minAllocSize && array)
288 array = renew0 array T[minAllocSize];
294 virtual int GetCount() { return count; }
298 get { return count; }
303 if(value > minAllocSize)
304 array = renew0 array T[value];
305 else if(value > count)
306 memset((byte *)array + count * class(T).typeSize, 0, (value - count) * class(T).typeSize);
308 #if !defined(MEMINFO) && defined(MEMTRACKING)
311 MemBlock block = (MemBlock)((byte *)array - sizeof(class MemBlock));
312 block._class = class(T);
319 property uint minAllocSize
321 get { return minAllocSize; }
324 if(minAllocSize != value)
327 array = renew array T[value];
328 minAllocSize = value;
330 #if !defined(MEMINFO) && defined(MEMTRACKING)
333 MemBlock block = (MemBlock)((byte *)array - sizeof(class MemBlock));
334 block._class = class(T);
340 virtual void Copy(Container source)
342 count = source.GetCount();
343 if(count > minAllocSize)
344 array = renew array T[count];
346 #if !defined(MEMINFO) && defined(MEMTRACKING)
349 MemBlock block = (MemBlock)((byte *)array - sizeof(class MemBlock));
350 block._class = class(T);
354 // TOFIX: Precomp fails on (BuiltInContainer *)
355 if((source._class == class(BuiltInContainer) && ((struct BuiltInContainer *)source)->type.type != structClass ) ||
356 eClass_IsDerived(source._class, class(Array)))
358 memcpy(array, ((Array)source).array, count * class(T).typeSize);
364 for(c = 0, i = source.GetFirst(); i; i = source.GetNext(i), c++)
366 D data = source.GetData(i);
375 for(c = 0; c<count; c++)
385 void Delete(IteratorPointer item)
392 void Sort(bool ascending)
394 Class Dclass = class(D);
395 bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
396 _qsortrx(array, count, Dclass.typeSize, (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare], null, Dclass, !byRef, ascending);