The Ecere SDK - sdk/blob - ecere/src/com/containers/Array.ec

   1 namespace com;
   2
   3 import "Container"
   4
   5 #ifdef _DEBUG
   6 // #define MEMTRACKING
   7 #endif
   8
   9 default:
  10 extern int __ecereVMethodID_class_OnUnserialize;
  11 extern int __ecereVMethodID_class_OnCompare;
  12
  13 // qsort_r/_s wrappers adapted from public domain code by Isaac Turner
  14 #if !defined(ECERE_BOOTSTRAP)
  15 #if (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined __bsdi__ || defined OpenBSD3_1 || defined OpenBSD3_9 || defined __OpenBSD__ || \
  16      defined __NetBSD__ || defined __DragonFly__ || defined AMIGA)
  17    #define BSD
  18    extern void qsort_r(void *base, uintsize nel, uintsize width, void *arg, int (*compare)(void *, const void *, const void *));
  19 #elif defined(__WIN32__)
  20    extern void qsort_s(void *base, uintsize nel, uintsize width, int (*compare)(void *, const void *, const void *), void * arg);
  21 #elif (defined __GLIBC__ && ((__GLIBC__ > 2) || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)))
  22    #define GLIBC
  23    extern void qsort_r(void *base, uintsize nel, uintsize width, int(* compare)(const void *, const void *, void *), void *arg);
  24 #endif
  25 #endif
  26 private:
  27
  28 // Quick Sort algorithm adapted from public domain code by Darel Rex Finley
  29 static inline void quickSort(void *base, uintsize nel, uintsize w, char * piv, int (*compare)(void *, const void *, const void *), void *arg)
  30 {
  31    #define MAX_LEVELS  300
  32    uintsize beg[MAX_LEVELS], end[MAX_LEVELS];
  33    int frame = 0;
  34
  35    beg[0] = 0;
  36    end[0] = nel;
  37    while(frame >= 0)
  38    {
  39       uintsize L = beg[frame], R = end[frame]-1;
  40       if(L < R)
  41       {
  42          memcpy(piv, (char *)base + L*w, w);
  43          while(L < R)
  44          {
  45             while(compare(arg, (char *)base + (R*w), piv) >= 0 && L < R) R--;
  46             if(L < R)
  47             {
  48                memcpy((char *)base + L*w, (char *)base + R*w, w);
  49                L++;
  50             }
  51             while(compare(arg, (char *)base + (L*w), piv) <= 0 && L < R) L++;
  52             if(L < R)
  53             {
  54                memcpy((char *)base + R*w, (char *)base + L*w, w);
  55                R--;
  56             }
  57          }
  58          memcpy((char *)base + L*w, piv, w);
  59          beg[frame+1] = L+1;
  60          end[frame+1] = end[frame];
  61          end[frame++] = L;
  62
  63          // Process smaller partition first
  64          if(end[frame]-beg[frame] > end[frame-1]-beg[frame-1])
  65          {
  66             uintsize swap;
  67             swap = beg[frame]; beg[frame] = beg[frame-1]; beg[frame-1] = swap;
  68             swap = end[frame]; end[frame] = end[frame-1]; end[frame-1] = swap;
  69          }
  70       }
  71       else
  72          frame--;
  73    }
  74    #undef MAX_LEVELS
  75 }
  76
  77 static struct SortRData { void *arg; int (*compare)(void *, const void *, const void *); };
  78
  79 static inline int compareDeref            (SortRData cs, const void **a, const void **b)  { return  cs.compare(cs.arg, *a, *b); }
  80 static inline int compareDescDeref        (SortRData cs, const void **a, const void **b)  { return -cs.compare(cs.arg, *a, *b); }
  81 static inline int compareDesc             (SortRData cs, const void * a, const void * b)  { return -cs.compare(cs.arg,  a,  b); }
  82
  83 static inline int compareArgLast          (const void * a, const void * b, SortRData cs)  { return  cs.compare(cs.arg,  a,  b); }
  84 static inline int compareDerefArgLast     (const void **a, const void **b, SortRData cs)  { return  cs.compare(cs.arg, *a, *b); }
  85 static inline int compareDescDerefArgLast (const void **a, const void **b, SortRData cs)  { return -cs.compare(cs.arg, *a, *b); }
  86 static inline int compareDescArgLast      (const void * a, const void * b, SortRData cs)  { return -cs.compare(cs.arg,  a,  b); }
  87
  88 static inline void _qsortrx(void *base, uintsize nel, uintsize width,
  89    int (*compare)(void *arg, const void *a, const void *b),
  90    int (*optCompareArgLast)(const void *a, const void *b, void *arg),
  91    void *arg,
  92    bool deref, bool ascending)
  93 {
  94 #if defined(GLIBC) && !defined(ECERE_BOOTSTRAP)
  95    if(!deref && ascending && optCompareArgLast)
  96       qsort_r(base, nel, width, optCompareArgLast, arg);
  97    else
  98    {
  99       SortRData s { arg, compare };
 100       #define compare_fn !deref && ascending ? compareArgLast : !deref ? compareDescArgLast : ascending ? compareDerefArgLast : compareDescDerefArgLast
 101       qsort_r(base, nel, width, compare_fn, s);
 102       #undef compare_fn
 103    }
 104 #else
 105    if(!deref && ascending)
 106    {
 107    #if defined(BSD) && !defined(ECERE_BOOTSTRAP)
 108       qsort_r(base, nel, width, arg, compare);
 109    #elif defined(__WIN32__) && !defined(ECERE_BOOTSTRAP)
 110       qsort_s(base, nel, width, compare, arg);
 111    #else
 112       {
 113          char * buf = new char[width];
 114          quickSort(base, nel, width, buf, compare, arg);
 115          delete buf;
 116       }
 117    #endif
 118    }
 119    else
 120    {
 121       SortRData s { arg, compare };
 122       #define compare_fn   !deref ? compareDesc : ascending ? compareDeref : compareDescDeref
 123    #if defined(BSD) && !defined(ECERE_BOOTSTRAP)
 124       qsort_r(base, nel, width, s, compare_fn);
 125    #elif defined(__WIN32__) && !defined(ECERE_BOOTSTRAP)
 126       qsort_s(base, nel, width, compare_fn, s);
 127    #else
 128       {
 129          char * buf = new char[width];
 130          quickSort(base, nel, width, buf, compare_fn, s);
 131          delete buf;
 132       }
 133    #endif
 134       #undef compare_fn
 135    }
 136 #endif
 137 }
 138
 139 public void qsortrx(void *base, uintsize nel, uintsize width,
 140    int (*compare)(void *arg, const void *a, const void *b),
 141    int (*optCompareArgLast)(const void *a, const void *b, void *arg),
 142    void *arg,
 143    bool deref, bool ascending)
 144 {
 145    _qsortrx(base, nel, width, compare, optCompareArgLast, arg, deref, ascending);
 146 }
 147
 148 public void qsortr(void *base, uintsize nel, uintsize width, int (*compare)(void *arg, const void *a, const void *b), void *arg)
 149 {
 150    _qsortrx(base, nel, width, compare, null, arg, false, true);
 151 }
 152
 153 public class Array : Container
 154 {
 155    class_fixed
 156
 157 public:
 158    T * array;
 159    uint count;
 160    uint minAllocSize;
 161
 162    ~Array()
 163    {
 164       delete array;
 165    }
 166
 167    void OnUnserialize(IOChannel channel)
 168    {
 169       Array array = eInstance_New(_class); //.fullName);
 170       uint count, c;
 171       Class Dclass = class(D);
 172       channel.Get(count);
 173 #ifdef _DEBUG
 174       //printf("%d %ss\n", count, Dclass.name);
 175       if(count > 10000)
 176          printf("Bug");
 177 #endif
 178       array.size = count;
 179       for(c = 0; c < count; c++)
 180          ((void (*)(void *, void *, void *))(void *)Dclass._vTbl[__ecereVMethodID_class_OnUnserialize])
 181             (Dclass, ((byte *)array.array) + Dclass.typeSize * c, channel);
 182       this = array;
 183    }
 184
 185    // Generic iterator support
 186    IteratorPointer GetFirst() { return (IteratorPointer)array; }
 187    IteratorPointer GetLast() { return (IteratorPointer)(array ? (array + (count - 1)) : null); }
 188    IteratorPointer GetPrev(IteratorPointer ip)
 189    {
 190       T * item = (T *)ip;
 191       return (IteratorPointer)((item && item > array) ? (item - 1) : null);
 192    }
 193    IteratorPointer GetNext(IteratorPointer ip)
 194    {
 195       T * item = (T *)ip;
 196       return (IteratorPointer)((item && item < array + count - 1) ? (item + 1) : null);
 197    }
 198    T GetData(IteratorPointer ip)
 199    {
 200       T * item = (T *)ip;
 201       return *item;
 202    }
 203    bool SetData(IteratorPointer ip, T value)
 204    {
 205       T * item = (T *)ip;
 206       *item = value;
 207       return true;
 208    }
 209    IteratorPointer GetAtPosition(const I pos, bool create, bool * justAdded)
 210    {
 211       if((int)pos > count && create)
 212       {
 213          if((int)pos + 1 > minAllocSize)
 214             array = renew array T[(int)pos + 1];
 215          count = (int)pos + 1;
 216          if(justAdded) *justAdded = true;
 217 #if !defined(MEMINFO) && defined(MEMTRACKING)
 218          if(array)
 219          {
 220             MemBlock block = (MemBlock)((byte *)array - sizeof(class MemBlock));
 221             block._class = class(T);
 222          }
 223 #endif
 224       }
 225       return ((int)pos < count && array) ? (IteratorPointer)(array + (int)pos) : null;
 226    }
 227    IteratorPointer Insert(IteratorPointer ip, T value)
 228    {
 229 /*
 230       T * after = (T *)ip;
 231       int offset = after ? (after - array) : 0;
 232       if(count + 1 > minAllocSize)
 233       {
 234          array = renew array T[count + 1];
 235          if(after) after = array + offset;
 236       }
 237       memmove(after ? (after + 2) : (array + 1), after ? (after + 1) : array, (count - offset) * class(T).typeSize);
 238       if(after)
 239          after[1] = value;
 240       else
 241          array[0] = value;
 242       count++;
 243       return (IteratorPointer)(after ? (after + 1) : array);
 244 */
 245       uint tsize = class(T).typeSize;
 246       byte * pos = ip ? ((byte *)ip + tsize) : (byte *)array;
 247       if(count+1 > minAllocSize)
 248       {
 249          int offset = pos - (byte *)array;
 250          array = renew array T[count + 1];
 251          pos = (byte *)array+offset;
 252       }
 253       memmove(pos + tsize, pos, (byte *)array+(count++) * tsize - pos);
 254       *(T*)pos = value;
 255       return (IteratorPointer)pos;
 256    }
 257
 258    IteratorPointer Add(T value)
 259    {
 260       if(count + 1 > minAllocSize)
 261          array = renew array T[count + 1];
 262       array[count] = value;
 263       return (IteratorPointer)(array + (count++));
 264    }
 265
 266    void Remove(IteratorPointer ip)
 267    {
 268       T * it = (T *)ip;
 269       memmove(it, it + 1, (count - (it - array) - 1) * class(T).typeSize);
 270       count--;
 271       if(count + 1 > minAllocSize)
 272          array = renew array T[count];
 273    }
 274
 275    void Move(IteratorPointer ip, IteratorPointer afterIp)
 276    {
 277       /*
 278       T * it = (T *)ip;
 279       T * after = (T *)afterIp;
 280       */
 281    }
 282
 283    virtual void RemoveAll()
 284    {
 285       if(minAllocSize && array)
 286          array = renew0 array T[minAllocSize];
 287       else
 288          delete array;
 289       count = 0;
 290    }
 291
 292    virtual int GetCount() { return count; }
 293
 294    property uint size
 295    {
 296       get { return count; }
 297       set
 298       {
 299          if(count != value)
 300          {
 301             if(value > minAllocSize)
 302                array = renew0 array T[value];
 303             else if(value > count)
 304                memset((byte *)array + count * class(T).typeSize, 0, (value - count) * class(T).typeSize);
 305             count = value;
 306 #if !defined(MEMINFO) && defined(MEMTRACKING)
 307             if(array)
 308             {
 309                MemBlock block = (MemBlock)((byte *)array - sizeof(class MemBlock));
 310                block._class = class(T);
 311             }
 312 #endif
 313          }
 314       }
 315    }
 316
 317    property uint minAllocSize
 318    {
 319       get { return minAllocSize; }
 320       set
 321       {
 322          if(minAllocSize != value)
 323          {
 324             if(value > count)
 325                array = renew array T[value];
 326             minAllocSize = value;
 327          }
 328 #if !defined(MEMINFO) && defined(MEMTRACKING)
 329          if(array)
 330          {
 331             MemBlock block = (MemBlock)((byte *)array - sizeof(class MemBlock));
 332             block._class = class(T);
 333          }
 334 #endif
 335       }
 336    }
 337
 338    virtual void Copy(Container source)
 339    {
 340       count = source.GetCount();
 341       if(count > minAllocSize)
 342          array = renew array T[count];
 343
 344 #if !defined(MEMINFO) && defined(MEMTRACKING)
 345          if(array)
 346          {
 347             MemBlock block = (MemBlock)((byte *)array - sizeof(class MemBlock));
 348             block._class = class(T);
 349          }
 350 #endif
 351
 352       // TOFIX: Precomp fails on (BuiltInContainer *)
 353       if((source._class == class(BuiltInContainer) && ((struct BuiltInContainer *)source)->type.type != structClass ) ||
 354          eClass_IsDerived(source._class, class(Array)))
 355       {
 356          memcpy(array, ((Array)source).array, count * class(T).typeSize);
 357       }
 358       else
 359       {
 360          IteratorPointer i;
 361          int c;
 362          for(c = 0, i = source.GetFirst(); i; i = source.GetNext(i), c++)
 363          {
 364             D data = source.GetData(i);
 365             array[c] = data;
 366          }
 367       }
 368    }
 369
 370    void Free()
 371    {
 372       int c;
 373       for(c = 0; c<count; c++)
 374       {
 375          T data = array[c];
 376          delete data;
 377       }
 378       delete array;
 379       count = 0;
 380       minAllocSize = 0;
 381    }
 382
 383    void Delete(IteratorPointer item)
 384    {
 385       T data = *(T*)item;
 386       delete data;
 387       Remove(item);
 388    }
 389
 390    void Sort(bool ascending)
 391    {
 392       Class Dclass = class(D);
 393       bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
 394       _qsortrx(array, count, Dclass.typeSize, (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare], null, Dclass, !byRef, ascending);
 395    }
 396 };