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

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