libphobos/libdruntime/core/internal/qsort.d

   1 /**
   2  * This is a public domain version of qsort.d.  All it does is call C's
   3  * qsort().
   4  *
   5  * Copyright: Copyright Digital Mars 2000 - 2010.
   6  * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
   7  * Authors:   Walter Bright, Martin Nowak
   8  */
   9 module core.internal.qsort;
  10
  11 //debug=qsort;
  12
  13 import core.stdc.stdlib;
  14
  15 version (OSX)
  16     version = Darwin;
  17 else version (iOS)
  18     version = Darwin;
  19 else version (TVOS)
  20     version = Darwin;
  21 else version (WatchOS)
  22     version = Darwin;
  23
  24 // qsort_r was added in glibc in 2.8. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88127
  25 version (CRuntime_Glibc)
  26 {
  27     version (GNU)
  28     {
  29         import gcc.config : Have_Qsort_R;
  30         enum Glibc_Qsort_R = Have_Qsort_R;
  31     }
  32     else
  33     {
  34         enum Glibc_Qsort_R = true;
  35     }
  36 }
  37 else
  38 {
  39     enum Glibc_Qsort_R = false;
  40 }
  41
  42 static if (Glibc_Qsort_R)
  43 {
  44     alias extern (C) int function(scope const void *, scope const void *, scope void *) Cmp;
  45     extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, Cmp cmp, scope void *arg);
  46
  47     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
  48     {
  49         extern (C) int cmp(scope const void* p1, scope const void* p2, scope void* ti)
  50         {
  51             return (cast(TypeInfo)ti).compare(p1, p2);
  52         }
  53         qsort_r(a.ptr, a.length, ti.tsize, &cmp, cast(void*)ti);
  54         return a;
  55     }
  56 }
  57 else version (FreeBSD)
  58 {
  59     alias extern (C) int function(scope void *, scope const void *, scope const void *) Cmp;
  60     extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, scope void *thunk, Cmp cmp);
  61
  62     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
  63     {
  64         extern (C) int cmp(scope void* ti, scope const void* p1, scope const void* p2)
  65         {
  66             return (cast(TypeInfo)ti).compare(p1, p2);
  67         }
  68         qsort_r(a.ptr, a.length, ti.tsize, cast(void*)ti, &cmp);
  69         return a;
  70     }
  71 }
  72 else version (DragonFlyBSD)
  73 {
  74     alias extern (C) int function(scope void *, scope const void *, scope const void *) Cmp;
  75     extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, scope void *thunk, Cmp cmp);
  76
  77     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
  78     {
  79         extern (C) int cmp(scope void* ti, scope const void* p1, scope const void* p2)
  80         {
  81             return (cast(TypeInfo)ti).compare(p1, p2);
  82         }
  83         qsort_r(a.ptr, a.length, ti.tsize, cast(void*)ti, &cmp);
  84         return a;
  85     }
  86 }
  87 else version (Darwin)
  88 {
  89     alias extern (C) int function(scope void *, scope const void *, scope const void *) Cmp;
  90     extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, scope void *thunk, Cmp cmp);
  91
  92     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
  93     {
  94         extern (C) int cmp(scope void* ti, scope const void* p1, scope const void* p2)
  95         {
  96             return (cast(TypeInfo)ti).compare(p1, p2);
  97         }
  98         qsort_r(a.ptr, a.length, ti.tsize, cast(void*)ti, &cmp);
  99         return a;
 100     }
 101 }
 102 else version (CRuntime_UClibc)
 103 {
 104     alias extern (C) int function(scope const void *, scope const void *, scope void *) __compar_d_fn_t;
 105     extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, __compar_d_fn_t cmp, scope void *arg);
 106
 107     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
 108     {
 109         extern (C) int cmp(scope const void* p1, scope const void* p2, scope void* ti)
 110         {
 111             return (cast(TypeInfo)ti).compare(p1, p2);
 112         }
 113         qsort_r(a.ptr, a.length, ti.tsize, &cmp, cast(void*)ti);
 114         return a;
 115     }
 116 }
 117 else
 118 {
 119     private TypeInfo tiglobal;
 120
 121     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
 122     {
 123         extern (C) int cmp(scope const void* p1, scope const void* p2)
 124         {
 125             return tiglobal.compare(p1, p2);
 126         }
 127         tiglobal = ti;
 128         qsort(a.ptr, a.length, ti.tsize, &cmp);
 129         return a;
 130     }
 131 }
 132
 133 unittest
 134 {
 135     debug(qsort) printf("array.sort.unittest()\n");
 136
 137     int[] a = new int[10];
 138
 139     a[0] = 23;
 140     a[1] = 1;
 141     a[2] = 64;
 142     a[3] = 5;
 143     a[4] = 6;
 144     a[5] = 5;
 145     a[6] = 17;
 146     a[7] = 3;
 147     a[8] = 0;
 148     a[9] = -1;
 149
 150     _adSort(*cast(void[]*)&a, typeid(a[0]));
 151
 152     for (int i = 0; i < a.length - 1; i++)
 153     {
 154         //printf("i = %d", i);
 155         //printf(" %d %d\n", a[i], a[i + 1]);
 156         assert(a[i] <= a[i + 1]);
 157     }
 158 }
 159
 160 unittest
 161 {
 162     debug(qsort) printf("struct.sort.unittest()\n");
 163
 164     static struct TestStruct
 165     {
 166         int value;
 167
 168         int opCmp(const TestStruct rhs) const
 169         {
 170             return value <= rhs.value ?
 171                 value < rhs.value ? -1 : 0 : 1;
 172         }
 173     }
 174
 175     TestStruct[] a = new TestStruct[10];
 176
 177     a[0] = TestStruct(23);
 178     a[1] = TestStruct(1);
 179     a[2] = TestStruct(64);
 180     a[3] = TestStruct(5);
 181     a[4] = TestStruct(6);
 182     a[5] = TestStruct(5);
 183     a[6] = TestStruct(17);
 184     a[7] = TestStruct(3);
 185     a[8] = TestStruct(0);
 186     a[9] = TestStruct(-1);
 187
 188     _adSort(*cast(void[]*)&a, typeid(TestStruct));
 189
 190     for (int i = 0; i < a.length - 1; i++)
 191     {
 192         //printf("i = %d", i);
 193         //printf(" %d %d\n", a[i], a[i + 1]);
 194         assert(a[i] <= a[i + 1]);
 195     }
 196 }