首页 > 代码库 > CSharpGL(36)通用的非托管数组排序方法
CSharpGL(36)通用的非托管数组排序方法
CSharpGL(36)通用的非托管数组排序方法
如果OpenGL要渲染半透明物体，一个方法是根据顶点到窗口的距离排序，按照从远到近的顺序依次渲染。所以本篇介绍对 UnmanagedArray<T> 进行排序的几种方法。
+BIT祝威+悄悄在此留下版了个权的信息说：
UnmanagedArray<T>
首先重新介绍一下非托管数组这个东西。一个 UnmanagedArray<float> 与一个 float[] 是一样的用处，只不过 UnmanagedArray<float> 是用 Marshal.AllocHGlobal(memSize); 在非托管内存上申请的空间。
1 namespace CSharpGL 2 { 3 /// <summary> 4 /// unmanaged huge array. 5 /// <para>Check http://www.cnblogs.com/bitzhuwei/p/huge-unmanged-array-in-csharp.html </para> 6 /// </summary> 7 /// <typeparam name="T">sbyte, byte, char, short, ushort, int, uint, long, ulong, float, double, decimal, bool or other struct types. enum not supported.</typeparam> 8 public sealed unsafe class UnmanagedArray<T> : UnmanagedArrayBase where T : struct 9 {10 public UnmanagedArray(int count)11 : base(count, Marshal.SizeOf(typeof(T)))12 {13 }14 }15 16 /// <summary>17 /// Base type of unmanaged array.18 /// <para>Similar to array in <code>int array[Length];</code></para>19 /// </summary>20 public abstract class UnmanagedArrayBase : IDisposable21 {22 /// <summary>23 /// 此非托管数组中的数据在内存中的起始地址24 /// Start position of array; Head of array; first element‘s position of array.25 /// <para>Similar to <code>array</code> in <code>int array[Length];</code></para>26 /// </summary>27 public IntPtr Header { get; private set; }28 29 /// <summary>30 /// How many elements?31 /// <para>Similar to <code>Length</code> in <code>int array[Length];</code></para>32 /// </summary>33 public int Length { get; private set; }34 35 /// <summary>36 /// 单个元素的字节数。37 /// <para>How manay bytes for one element of array?</para>38 /// </summary>39 protected int elementSize;40 41 /// <summary>42 /// 申请到的字节数。（元素的总数 * 单个元素的字节数）。43 /// <para>How many bytes for total array?</para>44 /// <para>Length * elementSize</para>45 /// </summary>46 public int ByteLength47 {48 get { return (this.Length * this.elementSize); }49 }50 51 protected UnmanagedArrayBase(int elementCount, int elementSize)52 {53 this.Length = elementCount;54 this.elementSize = elementSize;55 int memSize = this.Length * this.elementSize;56 this.Header = Marshal.AllocHGlobal(memSize);57 }58 }59 }
UnmanagedArray<float>
下面我们以 UnmanagedArray<float> 为例，实现对非托管数组的排序。（下面是快速排序算法）
1 public static void Sort(this UnmanagedArray<float> array, bool descending) 2 { 3 QuickSort(array, 0, array.Length - 1, descending); 4 } 5 6 public static void Sort(UnmanagedArray<float> array, int start, int length, bool descending) 7 { 8 QuickSort(array, start, start + length - 1, descending); 9 }10 11 private static void QuickSort(UnmanagedArray<float> array, int start, int end, bool descending)12 {13 if (start >= end) { return; }14 15 Stack<int> stack = new Stack<int>();16 stack.Push(end);17 stack.Push(start);18 QuickSort(array, descending, stack);19 }20 21 private static void QuickSort(UnmanagedArray<float> array, bool descending, Stack<int> stack)22 {23 while (stack.Count > 0)24 {25 int start = stack.Pop();26 int end = stack.Pop();27 int index = QuickSortPartion(array, start, end, descending);28 if (start < index - 1)29 {30 stack.Push(index - 1); stack.Push(start);31 }32 if (index + 1 < end)33 {34 stack.Push(end); stack.Push(index + 1);35 }36 }37 }38 39 private static unsafe int QuickSortPartion(UnmanagedArray<float> array, int start, int end, bool descending)40 {41 float* pointer = (float*)array.Header.ToPointer();42 float pivot, startValue, endValue;43 pivot = pointer[start];44 while (start < end)45 {46 startValue =http://www.mamicode.com/ pointer[start];47 while ((start < end)48 && ((descending && (startValue.CompareTo(pivot) > 0))49 || (!descending) && (startValue.CompareTo(pivot) < 0)))50 {51 start++;52 startValue =http://www.mamicode.com/ pointer[start];53 }54 55 endValue =http://www.mamicode.com/ pointer[end];56 while ((start < end)57 && ((descending && (endValue.CompareTo(pivot) < 0))58 || (!descending) && (endValue.CompareTo(pivot) > 0)))59 {60 end--;61 endValue =http://www.mamicode.com/ pointer[end];62 }63 64 if (start < end)65 {66 pointer[end] = startValue;67 pointer[start] = endValue;68 }69 }70 71 return start;72 }
原本我以为把这个方法改写一下，用 T代替具体的 float ，就可以实现对任意 T where T : struct,IComparable<T> 的排序，但是VS报了这样的编译错误：无法获取托管类型(“T”)的地址和大小，或无法声明指向它的指针。
看来C#不允许将泛型T作为unsafe里的数组的类型。那么只能用下面的几种方式变通一下。
Marshal
Marshal 有这样2个方法：
1 // 从非托管数组中读取一个元素2 public static object PtrToStructure(IntPtr ptr, Type structureType);3 // 向非托管数组写入一个元素4 public static void StructureToPtr(object structure, IntPtr ptr, bool fDeleteOld);
用这2个方法就可以实现对非托管数组的读写操作。于是泛型版本( UnmagedArray<T> )的排序算法就实现了。
1 public static void Sort<T>(this UnmanagedArray<T> array, bool descending) where T : struct, IComparable<T> 2 { 3 QuickSort(array, 0, array.Length - 1, descending); 4 } 5 6 public static void Sort<T>(this UnmanagedArray<T> array, int start, int length, bool descending) where T : struct, IComparable<T> 7 { 8 QuickSort(array, start, start + length - 1, descending); 9 }10 11 private static void QuickSort<T>(UnmanagedArray<T> array, int start, int end, bool descending) where T : struct, IComparable<T>12 {13 if (start >= end) { return; }14 15 var stack = new Stack<int>();16 stack.Push(end);17 stack.Push(start);18 QuickSort(array, descending, stack);19 }20 21 private static void QuickSort<T>(UnmanagedArray<T> array, bool descending, Stack<int> stack) where T : struct, IComparable<T>22 {23 IntPtr pointer = array.Header;24 Type type = typeof(T);25 int elementSize = Marshal.SizeOf(type);26 27 while (stack.Count > 0)28 {29 int start = stack.Pop();30 int end = stack.Pop();31 int index = QuickSortPartion(array, start, end, descending, type, elementSize);32 if (start < index - 1)33 {34 stack.Push(index - 1); stack.Push(start);35 }36 if (index + 1 < end)37 {38 stack.Push(end); stack.Push(index + 1);39 }40 }41 }42 43 private static int QuickSortPartion<T>(UnmanagedArray<T> array, int start, int end, bool descending, Type type, int elementSize) where T : struct, IComparable<T>44 {45 IntPtr pointer = array.Header;46 IntPtr pivotIndex, startIndex, endIndex;47 T pivot, startValue, endValue;48 pivotIndex = new IntPtr((int)pointer + start * elementSize);49 pivot = (T)Marshal.PtrToStructure(pivotIndex, type);50 while (start < end)51 {52 startIndex = new IntPtr((int)pointer + start * elementSize);53 startValue =http://www.mamicode.com/ (T)Marshal.PtrToStructure(startIndex, type);54 while ((start < end)55 && ((descending && (startValue.CompareTo(pivot) > 0))56 || ((!descending) && (startValue.CompareTo(pivot) < 0))))57 {58 start++;59 startIndex = new IntPtr((int)pointer + start * elementSize);60 startValue =http://www.mamicode.com/ (T)Marshal.PtrToStructure(startIndex, type);61 }62 63 endIndex = new IntPtr((int)pointer + end * elementSize);64 endValue =http://www.mamicode.com/ (T)Marshal.PtrToStructure(endIndex, type);65 while ((start < end)66 && ((descending && (endValue.CompareTo(pivot) < 0))67 || ((!descending) && (endValue.CompareTo(pivot) > 0))))68 {69 end--;70 endIndex = new IntPtr((int)pointer + end * elementSize);71 endValue =http://www.mamicode.com/ (T)Marshal.PtrToStructure(endIndex, type);72 }73 74 if (start < end)75 {76 Marshal.StructureToPtr(endValue, startIndex, true);77 Marshal.StructureToPtr(startValue, endIndex, true);78 }79 }80 81 return start;82 }
虽然可用，但是用Marshal读写非托管数组效率比较低（使用了装箱拆箱操作）。于是我有了下面这个思路。
+BIT祝威+悄悄在此留下版了个权的信息说：
CodeProvider
我们知道C#现有的类库是支持动态生成和调用C#代码的。因此，我可以在调用 Sort<T>(this UnmanagedArray<T> array, bool descending) 时，临时为具体的T生成一个排序方法，然后去调用这个方法。这就不需要使用 Marshal 了。
具体步骤如下。
准备模板
为了便于编码、维护，我们先准备一个排序代码的模板。模板里的TemplateStructType纯属一个占位符，在使用的时候我们先用具体的类型把它替换掉，就成了我们需要的源代码。
1 using System; 2 using System.Collections.Generic; 3 using System.Runtime.InteropServices; 4 5 namespace CSharpGL 6 { 7 /// <summary> 8 /// Helper class for sorting unmanaged array. 9 /// </summary>10 public static partial class SortingHelper11 {12 ///// <summary>13 ///// Sort unmanaged array specified with <paramref name="array"/> at specified area.14 ///// </summary>15 ///// <param name="array"></param>16 ///// <param name="descending">true for descending sort; otherwise false.</param>17 //public static void Sort(this UnmanagedArray<TemplateStructType> array, bool descending)18 //{19 // QuickSort(array, 0, array.Length - 1, descending);20 //}21 22 /// <summary>23 /// Sort unmanaged array specified with <paramref name="array"/> at specified area.24 /// </summary>25 /// <param name="array"></param>26 /// <param name="start">index of first value to be sorted.</param>27 /// <param name="length">length of <paramref name="array"/> to bo sorted.</param>28 /// <param name="descending">true for descending sort; otherwise false.</param>29 public static void Sort(UnmanagedArray<TemplateStructType> array, int start, int length, bool descending)30 {31 QuickSort(array, start, start + length - 1, descending);32 }33 34 private static void QuickSort(UnmanagedArray<TemplateStructType> array, int start, int end, bool descending)35 {36 if (start >= end) { return; }37 38 Stack<int> stack = new Stack<int>();39 stack.Push(end);40 stack.Push(start);41 QuickSort(array, descending, stack);42 }43 44 private static void QuickSort(UnmanagedArray<TemplateStructType> array, bool descending, Stack<int> stack)45 {46 while (stack.Count > 0)47 {48 int start = stack.Pop();49 int end = stack.Pop();50 int index = QuickSortPartion(array, start, end, descending);51 if (start < index - 1)52 {53 stack.Push(index - 1); stack.Push(start);54 }55 if (index + 1 < end)56 {57 stack.Push(end); stack.Push(index + 1);58 }59 }60 }61 62 private static unsafe int QuickSortPartion(UnmanagedArray<TemplateStructType> array, int start, int end, bool descending)63 {64 TemplateStructType* pointer = (TemplateStructType*)array.Header.ToPointer();65 TemplateStructType pivot, startValue, endValue;66 pivot = pointer[start];67 while (start < end)68 {69 startValue =http://www.mamicode.com/ pointer[start];70 while ((start < end)71 && ((descending && (startValue.CompareTo(pivot) > 0))72 || (!descending) && (startValue.CompareTo(pivot) < 0)))73 {74 start++;75 startValue =http://www.mamicode.com/ pointer[start];76 }77 78 endValue =http://www.mamicode.com/ pointer[end];79 while ((start < end)80 && ((descending && (endValue.CompareTo(pivot) < 0))81 || (!descending) && (endValue.CompareTo(pivot) > 0)))82 {83 end--;84 endValue =http://www.mamicode.com/ pointer[end];85 }86 87 if (start < end)88 {89 pointer[end] = startValue;90 pointer[start] = endValue;91 }92 }93 94 return start;95 }96 }97 }
嵌入的资源
然后把这个模板文件设置为嵌入的资源，以便于调用。
动态生成和调用代码
利用CSharpCodeProvider来把源代码编译为Assembly并调用。
1 public static void Sort<T>(this UnmanagedArray<T> array, bool descending) where T : struct, IComparable<T> 2 { 3 Type type = typeof(T); 4 string order = ManifestResourceLoader.LoadTextFile(@"Resources\SortingHelper.Order`1.cs"); 5 order = order.Replace("TemplateStructType", type.FullName); 6 var codeProvider = new CSharpCodeProvider(); 7 var option = new CompilerParameters(); 8 option.GenerateInMemory = true; 9 option.CompilerOptions = "/unsafe";10 option.ReferencedAssemblies.Add("System.dll");11 option.ReferencedAssemblies.Add("CSharpGL.dll");12 CompilerResults result = codeProvider.CompileAssemblyFromSource(option,13 order);14 Assembly asm = result.CompiledAssembly;15 Type sortingHelper = asm.GetType("CSharpGL.SortingHelper");16 Type unmanagedArrayGeneric = typeof(UnmanagedArray<>);17 Type unmanagedArray = unmanagedArrayGeneric.MakeGenericType(type);18 MethodInfo method = sortingHelper.GetMethod("Sort", new Type[] { unmanagedArray, typeof(int), typeof(int), typeof(bool) });19 method.Invoke(null, new object[] { array, 0, array.Length, descending });20 }
+BIT祝威+悄悄在此留下版了个权的信息说：
总结
还有一种利用emit的方法，我就暂时不研究了。
CSharpGL(36)通用的非托管数组排序方法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。