Mercurial > projects > ldc

annotate lphobos/internal/qsort2.d @ 109:5ab8e92611f9 trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r113] Added initial support for associative arrays (AAs). Fixed some problems with the string runtime support functions. Fixed initialization of array of structs. Fixed slice assignment where LHS is slice but RHS is dynamic array. Fixed problems with result of assignment expressions. Fixed foreach problems with key type mismatches.
author lindquist
date Wed, 21 Nov 2007 04:13:15 +0100
parents 61615fa85940
children 373489eeaf90
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
94
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
1
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
2 /*
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
3 * Placed into Public Domain
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
4 * written by Walter Bright
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
5 * www.digitalmars.com
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
6 *
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
7 * This is a public domain version of qsort.d.
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
8 * All it does is call C's qsort(), but runs a little slower since
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
9 * it needs to synchronize a global variable.
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
10 */
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
11
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
12
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
13 //debug=qsort;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
14
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
15 import std.c.stdlib;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
16
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 94
diff changeset
17 pragma(LLVM_internal, "notypeinfo")
94
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
18 struct Array
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
19 {
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
20 size_t length;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
21 void *ptr;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
22 }
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
23
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
24 private TypeInfo tiglobal;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
25
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
26 extern (C) int cmp(void* p1, void* p2)
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
27 {
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
28 return tiglobal.compare(p1, p2);
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
29 }
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
30
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 94
diff changeset
31 extern (C) Array _adSort(Array a, TypeInfo ti)
94
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
32 {
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
33 synchronized
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
34 {
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
35 tiglobal = ti;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
36 std.c.stdlib.qsort(a.ptr, a.length, cast(size_t)ti.tsize(), &cmp);
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
37 }
109
5ab8e92611f9 [svn r113] Added initial support for associative arrays (AAs).
lindquist
parents: 94
diff changeset
38 return a;
94
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
39 }
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
40
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
41
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
42
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
43 unittest
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
44 {
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
45 debug(qsort) printf("array.sort.unittest()\n");
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
46
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
47 int a[] = new int[10];
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
48
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
49 a[0] = 23;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
50 a[1] = 1;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
51 a[2] = 64;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
52 a[3] = 5;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
53 a[4] = 6;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
54 a[5] = 5;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
55 a[6] = 17;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
56 a[7] = 3;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
57 a[8] = 0;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
58 a[9] = -1;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
59
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
60 a.sort;
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
61
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
62 for (int i = 0; i < a.length - 1; i++)
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
63 {
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
64 //printf("i = %d", i);
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
65 //printf(" %d %d\n", a[i], a[i + 1]);
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
66 assert(a[i] <= a[i + 1]);
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
67 }
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
68 }
61615fa85940 [svn r98] Added support for std.c.stdlib.alloca via pragma(LLVM_internal, "alloca").
lindquist
parents:
diff changeset
69