The Ecere SDK - sdk/blob - ecere/src/gfx/newFonts/cc/ccmergesort.h

   1 /* *****************************************************************************
   2  * Copyright (c) 2007-2014 Alexis Naveros.
   3  *
   4  * Ecere Corporation has unlimited/unrestricted rights.
   5  * *****************************************************************************/
   6 /*
   7
   8 Templates C style!
   9
  10 #include this whole file with the following definitions set:
  11
  12 #define MSORT_MAIN MyInlinedSortFunction
  13 #define MSORT_CMP MyComparisonFunction
  14 #define MSORT_TYPE int
  15
  16 */
  17
  18
  19 #ifndef CC_MSORT_INLINE
  20
  21 typedef struct
  22 {
  23   void *src;
  24   void *dst;
  25   int count;
  26   int mergeflag;
  27   int depthbit;
  28 } ccMergeSortStack;
  29
  30  #define CC_MSORT_INLINE
  31  #define CC_MSORT_STACK_DEPTH (512)
  32
  33 #endif
  34
  35
  36 #ifndef MSORT_COPY
  37  #define MSORT_COPY(d,s) (*(d)=*(s))
  38  #define CC_MSORT_COPY
  39 #endif
  40
  41
  42 #ifdef MSORT_CONTEXT
  43  #define MSORT_CONTEXT_PARAM , MSORT_CONTEXT context
  44  #define MSORT_CONTEXT_PASS context,
  45  #define MSORT_CONTEXT_PASSLAST , context
  46 #else
  47  #define MSORT_CONTEXT_PARAM
  48  #define MSORT_CONTEXT_PASS
  49  #define MSORT_CONTEXT_PASSLAST
  50 #endif
  51
  52
  53 static MSORT_TYPE *MSORT_MAIN( MSORT_TYPE *src, MSORT_TYPE *tmp, int count MSORT_CONTEXT_PARAM )
  54 {
  55   int swapflag, depthbit, maxdepthbit;
  56   ssize_t leftcount, rightcount;
  57   MSORT_TYPE *dst;
  58   MSORT_TYPE *sl;
  59   MSORT_TYPE *sr;
  60   MSORT_TYPE *dstend;
  61   MSORT_TYPE *dstbase;
  62   MSORT_TYPE *swap;
  63   MSORT_TYPE temp;
  64   ccMergeSortStack stack[CC_MSORT_STACK_DEPTH];
  65   ccMergeSortStack *sp;
  66
  67   if( count <= 1 )
  68     return src;
  69
  70   dst = tmp;
  71   sp = stack;
  72   swapflag = 0;
  73   depthbit = 0;
  74
  75   leftcount = count;
  76   for( maxdepthbit = 1 ; ; maxdepthbit ^= 1 )
  77   {
  78     leftcount = leftcount - ( leftcount >> 1 );
  79     if( leftcount <= 4 )
  80       break;
  81   }
  82
  83   for( ; ; )
  84   {
  85     if( count <= 4 )
  86     {
  87       if( !( depthbit ^ maxdepthbit ) )
  88       {
  89         if( ( count == 4 ) && MSORT_CMP( MSORT_CONTEXT_PASS &src[2], &src[3] ) )
  90         {
  91           MSORT_COPY( &temp, &src[2] );
  92           MSORT_COPY( &src[2], &src[3] );
  93           MSORT_COPY( &src[3], &temp );
  94         }
  95         if( MSORT_CMP( MSORT_CONTEXT_PASS &src[0], &src[1] ) )
  96         {
  97           MSORT_COPY( &temp, &src[0] );
  98           MSORT_COPY( &src[0], &src[1] );
  99           MSORT_COPY( &src[1], &temp );
 100         }
 101         swapflag = 0;
 102       }
 103       else
 104       {
 105         if( count == 4 )
 106         {
 107           if( MSORT_CMP( MSORT_CONTEXT_PASS &src[2], &src[3] ) )
 108           {
 109             MSORT_COPY( &dst[2], &src[3] );
 110             MSORT_COPY( &dst[3], &src[2] );
 111           }
 112           else
 113           {
 114             MSORT_COPY( &dst[2], &src[2] );
 115             MSORT_COPY( &dst[3], &src[3] );
 116           }
 117         }
 118         else if( count == 3 )
 119           MSORT_COPY( &dst[2], &src[2] );
 120         if( MSORT_CMP( MSORT_CONTEXT_PASS &src[0], &src[1] ) )
 121         {
 122           MSORT_COPY( &dst[0], &src[1] );
 123           MSORT_COPY( &dst[1], &src[0] );
 124         }
 125         else
 126         {
 127           MSORT_COPY( &dst[0], &src[0] );
 128           MSORT_COPY( &dst[1], &src[1] );
 129         }
 130         swap = src;
 131         src = dst;
 132         dst = swap;
 133         swapflag = 1;
 134       }
 135     }
 136     else
 137     {
 138       rightcount = count >> 1;
 139       leftcount = count - rightcount;
 140       sp->src = src;
 141       sp->dst = dst;
 142       sp->count = count;
 143       sp->mergeflag = 1;
 144       sp->depthbit = depthbit;
 145       depthbit ^= 1;
 146       sp++;
 147       sp->src = src + leftcount;
 148       sp->dst = dst + leftcount;
 149       sp->count = (int)rightcount;
 150       sp->mergeflag = 0;
 151       sp->depthbit = depthbit;
 152       sp++;
 153       count = (int)leftcount;
 154       continue;
 155     }
 156
 157     for( ; ; )
 158     {
 159       rightcount = count >> 1;
 160       leftcount = count - rightcount;
 161       sl = src;
 162       sr = src + leftcount;
 163       dstbase = dst;
 164       for( ; ; )
 165       {
 166         if( MSORT_CMP( MSORT_CONTEXT_PASS sl, sr ) )
 167         {
 168           MSORT_COPY( dst++, sr++ );
 169           if( --rightcount )
 170             continue;
 171           for( dstend = &dst[leftcount] ; dst < dstend ; )
 172             MSORT_COPY( dst++, sl++ );
 173           break;
 174         }
 175         else
 176         {
 177           MSORT_COPY( dst++, sl++ );
 178           if( --leftcount )
 179             continue;
 180           for( dstend = &dst[rightcount] ; dst < dstend ; )
 181             MSORT_COPY( dst++, sr++ );
 182           break;
 183         }
 184       }
 185       if( sp == stack )
 186         return dstbase;
 187       sp--;
 188       src = sp->src;
 189       dst = sp->dst;
 190       count = sp->count;
 191       depthbit = sp->depthbit;
 192       if( !( sp->mergeflag ) )
 193         break;
 194       swapflag ^= 1;
 195       if( swapflag )
 196       {
 197         src = sp->dst;
 198         dst = sp->src;
 199       }
 200     }
 201   }
 202
 203   return 0;
 204 }
 205
 206
 207 #ifdef CC_MSORT_COPY
 208  #undef MSORT_COPY
 209  #undef CC_MSORT_COPY
 210 #endif
 211
 212 #undef MSORT_CONTEXT_PARAM
 213 #undef MSORT_CONTEXT_PASS
 214 #undef MSORT_CONTEXT_PASSLAST
 215