hschumann2/TempleOS-Source-Code

1 2U0 QSortI64(I64 *base,I64 num, I64 (*fp_compare)(I64 e1,I64 e2))3{/*Quick Sort for width==8.4fp_compare() passes by value instead of ref.5 6For ascending strings: return StrCmp(e1,e2);7For ascending ints   : return e1-e2;8 9Maybe, look at ::/Demo/MultiCore/MPRadix.HC.10*/11  I64 i,*left,*right,pivot;12  if (num>1) {13    left =base;14    right=base+num-1;15    pivot=base[num/2];16    do {17      while ((*fp_compare)(*left,pivot)<0)18        left++;19      while ((*fp_compare)(*right,pivot)>0)20        right--;21      if (left<=right)22        SwapI64(left++,right--);23    } while (left<=right);24    i=right+1-base;25    if (1<i<num)26      QSortI64(base,i,fp_compare);27    i=base+num-left;28    if (1<i<num)29      QSortI64(left,i,fp_compare);30  }31}32 33U0 QSort2a(U8 **base,I64 num,I64 (*fp_compare)(U8 **_e1,U8 **_e2))34{//Not public.For case of width==size(U8 *)==8.35//fp_compare() passes by ref.36  I64 i;37  U8 **left,**right,*pivot;38  left =base;39  right=base+num-1;40  pivot=base[num/2];41  do {42    while ((*fp_compare)(left,&pivot)<0)43      left++;44    while ((*fp_compare)(right,&pivot)>0)45      right--;46    if (left<=right)47      SwapI64(left++,right--);48  } while (left<=right);49  i=right+1-base;50  if (1<i<num)51    QSort2a(base,i,fp_compare);52  i=base+num-left;53  if (1<i<num)54    QSort2a(left,i,fp_compare);55}56U0 QSort2b(U8 *base,I64 num, I64 width,57        I64 (*fp_compare)(U8 *e1,U8 *e2),U8 *tmp)58{//Not public59  I64 i;60  U8 *left,*right,*pivot=tmp+width;61  left =base;62  right=base+(num-1)*width;63  MemCpy(pivot,base+num/2*width,width);64  do {65    while ((*fp_compare)(left,pivot)<0)66      left+=width;67    while ((*fp_compare)(right,pivot)>0)68      right-=width;69    if (left<=right) {70      if (left!=right) {71        MemCpy(tmp,right,width);72        MemCpy(right,left,width);73        MemCpy(left,tmp,width);74      }75      left+=width;76      right-=width;77    }78  } while (left<=right);79  i=1+(right-base)/width;80  if (1<i<num)81    QSort2b(base,i,width,fp_compare,tmp);82  i=num+(base-left)/width;83  if (1<i<num)84    QSort2b(left,i,width,fp_compare,tmp);85}86U0 QSort(U8 *base,I64 num, I64 width, I64 (*fp_compare)(U8 *e1,U8 *e2))87{/*Quick Sort: fp_compare() passes by ref.88 89For ascending strings: return StrCmp(*e1,*e2);90For ascending ints   : return *e1-*e2;91Don't return e1-e2 if numbers can overflow, return -1,0 or 1.92 93Maybe, look at ::/Demo/MultiCore/MPRadix.HC.94*/95  U8 *tmp;96  if (width && num>1) {97    if (width==sizeof(U8 *))    //assign instead of MemCpy for width 898      QSort2a(base,num,fp_compare);99    else {100      tmp=MAlloc(width*2);101      QSort2b(base,num,width,fp_compare,tmp);102      Free(tmp);103    }104  }105}106