Mercurial > projects > ldc

annotate druntime/src/compiler/dmd/qsort2.d @ 759:d3eb054172f9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added copy of druntime from DMD 2.020 modified for LDC.
author Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
date Tue, 11 Nov 2008 01:52:37 +0100
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
759
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
1
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
2 /*
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
3 * Placed into Public Domain
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
4 * written by Walter Bright
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
5 * www.digitalmars.com
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
6 *
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
7 * This is a public domain version of qsort.d.
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
8 * All it does is call C's qsort(), but runs a little slower since
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
9 * it needs to synchronize a global variable.
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
10 */
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
11
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
12 /*
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
13 * Modified by Sean Kelly for use with the D Runtime Project
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
14 */
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
15
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
16 module rt.qsort2;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
17
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
18 //debug=qsort;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
19
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
20 private import stdc.stdlib;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
21
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
22 struct Array
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
23 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
24 size_t length;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
25 void* ptr;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
26 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
27
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
28 private TypeInfo tiglobal;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
29
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
30 extern (C) int cmp(void* p1, void* p2)
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
31 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
32 return tiglobal.compare(p1, p2);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
33 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
34
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
35 extern (C) long _adSort(Array a, TypeInfo ti)
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
36 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
37 synchronized
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
38 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
39 tiglobal = ti;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
40 qsort(a.ptr, a.length, cast(size_t)ti.tsize(), &cmp);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
41 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
42 return *cast(long*)(&a);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
43 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
44
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
45
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
46
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
47 unittest
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
48 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
49 debug(qsort) printf("array.sort.unittest()\n");
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
50
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
51 int a[] = new int[10];
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
52
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
53 a[0] = 23;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
54 a[1] = 1;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
55 a[2] = 64;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
56 a[3] = 5;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
57 a[4] = 6;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
58 a[5] = 5;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
59 a[6] = 17;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
60 a[7] = 3;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
61 a[8] = 0;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
62 a[9] = -1;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
63
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
64 a.sort;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
65
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
66 for (int i = 0; i < a.length - 1; i++)
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
67 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
68 //printf("i = %d", i);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
69 //printf(" %d %d\n", a[i], a[i + 1]);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
70 assert(a[i] <= a[i + 1]);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
71 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
72 }