Mercurial > projects > ldc

annotate druntime/src/compiler/dmd/qsort.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 Portions of this file are:
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
3 Copyright Prototronics, 1987
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
4 Totem Lake P.O. 8117
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
5 Kirkland, Washington 98034
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
6 (206) 820-1972
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
7 Licensed to Digital Mars.
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
8
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
9 June 11, 1987 from Ray Gardner's
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
10 Denver, Colorado) public domain version
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 Use qsort2.d instead of this file if a redistributable version of
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
13 _adSort() is required.
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.qsort;
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 /*
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
19 ** Sorts an array starting at base, of length nbr_elements, each
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
20 ** element of size width_bytes, ordered via compare_function; which
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
21 ** is called as (*comp_fp)(ptr_to_element1, ptr_to_element2)
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
22 ** and returns < 0 if element1 < element2, 0 if element1 = element2,
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
23 ** > 0 if element1 > element2. Most of the refinements are due to
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
24 ** R. Sedgewick. See "Implementing Quicksort Programs", Comm. ACM,
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
25 ** Oct. 1978, and Corrigendum, Comm. ACM, June 1979.
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 //debug=qsort; // uncomment to turn on debugging printf's
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
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
31 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
32 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
33 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
34 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
35 }
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
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
38 private const int _maxspan = 7; // subarrays of _maxspan or fewer elements
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
39 // will be sorted by a simple insertion sort
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
40
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
41 /* Adjust _maxspan according to relative cost of a swap and a compare. Reduce
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
42 _maxspan (not less than 1) if a swap is very expensive such as when you have
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
43 an array of large structures to be sorted, rather than an array of pointers to
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
44 structures. The default value is optimized for a high cost for compares. */
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 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
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 byte* base;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
50 byte*[40] stack; // stack
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
51 byte** sp; // stack pointer
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
52 byte* i, j, limit; // scan and limit pointers
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
53 uint thresh; // size of _maxspan elements in bytes
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
54 uint width = ti.tsize();
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
55
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
56 base = cast(byte *)a.ptr;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
57 thresh = _maxspan * width; // init threshold
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
58 sp = stack.ptr; // init stack pointer
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
59 limit = base + a.length * width; // pointer past end of array
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
60 while (1) // repeat until done then return
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
61 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
62 while (limit - base > thresh) // if more than _maxspan elements
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 //swap middle, base
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
65 ti.swap((cast(uint)(limit - base) >> 1) -
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
66 (((cast(uint)(limit - base) >> 1)) % width) + base, base);
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 i = base + width; // i scans from left to right
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
69 j = limit - width; // j scans from right to left
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
70
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
71 if (ti.compare(i, j) > 0) // Sedgewick's
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
72 ti.swap(i, j); // three-element sort
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
73 if (ti.compare(base, j) > 0) // sets things up
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
74 ti.swap(base, j); // so that
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
75 if (ti.compare(i, base) > 0) // *i <= *base <= *j
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
76 ti.swap(i, base); // *base is the pivot element
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
77
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
78 while (1)
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
79 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
80 do // move i right until *i >= pivot
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
81 i += width;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
82 while (ti.compare(i, base) < 0);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
83 do // move j left until *j <= pivot
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
84 j -= width;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
85 while (ti.compare(j, base) > 0);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
86 if (i > j) // break loop if pointers crossed
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
87 break;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
88 ti.swap(i, j); // else swap elements, keep scanning
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
89 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
90 ti.swap(base, j); // move pivot into correct place
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
91 if (j - base > limit - i) // if left subarray is larger...
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
92 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
93 sp[0] = base; // stack left subarray base
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
94 sp[1] = j; // and limit
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
95 base = i; // sort the right subarray
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
96 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
97 else // else right subarray is larger
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
98 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
99 sp[0] = i; // stack right subarray base
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
100 sp[1] = limit; // and limit
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
101 limit = j; // sort the left subarray
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
102 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
103 sp += 2; // increment stack pointer
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
104 assert(sp < cast(byte**)stack + stack.length);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
105 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
106
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
107 // Insertion sort on remaining subarray
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
108 i = base + width;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
109 while (i < limit)
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
110 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
111 j = i;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
112 while (j > base && ti.compare(j - width, j) > 0)
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
113 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
114 ti.swap(j - width, j);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
115 j -= width;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
116 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
117 i += width;
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
118 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
119
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
120 if (sp > stack.ptr) // if any entries on stack...
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
121 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
122 sp -= 2; // pop the base and limit
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
123 base = sp[0];
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
124 limit = sp[1];
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
125 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
126 else // else stack empty, all done
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
127 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
128 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
129 assert(0);
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
130 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
131
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
132
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
133 unittest
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
134 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
135 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
136
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
137 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
138
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
139 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
140 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
141 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
142 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
143 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
144 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
145 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
146 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
147 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
148 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
149
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
150 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
151
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
152 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
153 {
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
154 //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
155 //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
156 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
157 }
d3eb054172f9 Added copy of druntime from DMD 2.020 modified for LDC.
Tomas Lindquist Olsen <tomas.l.olsen@gmail.com>
parents:
diff changeset
158 }