libphobos/libdruntime/rt/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:   $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
   7  * Authors:   Walter Bright, Martin Nowak
   8  */
   9
  10 /*          Copyright Digital Mars 2000 - 2010.
  11  * Distributed under the Boost Software License, Version 1.0.
  12  *    (See accompanying file LICENSE_1_0.txt or copy at
  13  *          http://www.boost.org/LICENSE_1_0.txt)
  14  */
  15 module rt.qsort;
  16
  17 //debug=qsort;
  18
  19 private import core.stdc.stdlib;
  20
  21 version (OSX)
  22     version = Darwin;
  23 else version (iOS)
  24     version = Darwin;
  25 else version (TVOS)
  26     version = Darwin;
  27 else version (WatchOS)
  28     version = Darwin;
  29
  30 version (CRuntime_Glibc)
  31 {
  32     alias extern (C) int function(scope const void *, scope const void *, scope void *) Cmp;
  33     extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, Cmp cmp, scope void *arg);
  34
  35     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
  36     {
  37         extern (C) int cmp(scope const void* p1, scope const void* p2, scope void* ti)
  38         {
  39             return (cast(TypeInfo)ti).compare(p1, p2);
  40         }
  41         qsort_r(a.ptr, a.length, ti.tsize, &cmp, cast(void*)ti);
  42         return a;
  43     }
  44 }
  45 else version (FreeBSD)
  46 {
  47     alias extern (C) int function(scope void *, scope const void *, scope const void *) Cmp;
  48     extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, scope void *thunk, Cmp cmp);
  49
  50     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
  51     {
  52         extern (C) int cmp(scope void* ti, scope const void* p1, scope const void* p2)
  53         {
  54             return (cast(TypeInfo)ti).compare(p1, p2);
  55         }
  56         qsort_r(a.ptr, a.length, ti.tsize, cast(void*)ti, &cmp);
  57         return a;
  58     }
  59 }
  60 else version (Darwin)
  61 {
  62     alias extern (C) int function(scope void *, scope const void *, scope const void *) Cmp;
  63     extern (C) void qsort_r(scope void *base, size_t nmemb, size_t size, scope void *thunk, Cmp cmp);
  64
  65     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
  66     {
  67         extern (C) int cmp(scope void* ti, scope const void* p1, scope const void* p2)
  68         {
  69             return (cast(TypeInfo)ti).compare(p1, p2);
  70         }
  71         qsort_r(a.ptr, a.length, ti.tsize, cast(void*)ti, &cmp);
  72         return a;
  73     }
  74 }
  75 else
  76 {
  77     private TypeInfo tiglobal;
  78
  79     extern (C) void[] _adSort(return scope void[] a, TypeInfo ti)
  80     {
  81         extern (C) int cmp(scope const void* p1, scope const void* p2)
  82         {
  83             return tiglobal.compare(p1, p2);
  84         }
  85         tiglobal = ti;
  86         qsort(a.ptr, a.length, ti.tsize, &cmp);
  87         return a;
  88     }
  89 }
  90
  91
  92
  93 unittest
  94 {
  95     debug(qsort) printf("array.sort.unittest()\n");
  96
  97     int[] a = new int[10];
  98
  99     a[0] = 23;
 100     a[1] = 1;
 101     a[2] = 64;
 102     a[3] = 5;
 103     a[4] = 6;
 104     a[5] = 5;
 105     a[6] = 17;
 106     a[7] = 3;
 107     a[8] = 0;
 108     a[9] = -1;
 109
 110     _adSort(*cast(void[]*)&a, typeid(a[0]));
 111
 112     for (int i = 0; i < a.length - 1; i++)
 113     {
 114         //printf("i = %d", i);
 115         //printf(" %d %d\n", a[i], a[i + 1]);
 116         assert(a[i] <= a[i + 1]);
 117     }
 118 }