CSharpGL(36)通用的非托管数组排序方法
如果OpenGL要渲染半透明物体，一个方法是根据顶点到窗口的距离排序，按照从远到近的顺序依次渲染。所以本篇介绍对 UnmanagedArray<T> 进行排序的几种方法。
+BIT祝威+悄悄在此留下版了个权的信息说：
UnmanagedArray<T>
首先重新介绍一下非托管数组这个东西。一个 UnmanagedArray<float> 与一个 float[] 是一样的用处，只不过 UnmanagedArray<float> 是用 Marshal.AllocHGlobal(memSize); 在非托管内存上申请的空间。
namespace CSharpGL
{
/// <summary>
/// unmanaged huge array.
/// <para>Check http://www.cnblogs.com/bitzhuwei/p/huge-unmanged-array-in-csharp.html </para>
/// </summary>
/// <typeparam name="T">sbyte, byte, char, short, ushort, int, uint, long, ulong, float, double, decimal, bool or other struct types. enum not supported.</typeparam>
public sealed unsafe class UnmanagedArray<T> : UnmanagedArrayBase where T : struct
{
public UnmanagedArray(int count)
: base(count, Marshal.SizeOf(typeof(T)))
{
}
} /// <summary>
/// Base type of unmanaged array.
/// <para>Similar to array in <code>int array[Length];</code></para>
/// </summary>
public abstract class UnmanagedArrayBase : IDisposable
{
/// <summary>
/// 此非托管数组中的数据在内存中的起始地址
/// Start position of array; Head of array; first element's position of array.
/// <para>Similar to <code>array</code> in <code>int array[Length];</code></para>
/// </summary>
public IntPtr Header { get; private set; } /// <summary>
/// How many elements?
/// <para>Similar to <code>Length</code> in <code>int array[Length];</code></para>
/// </summary>
public int Length { get; private set; } /// <summary>
/// 单个元素的字节数。
/// <para>How manay bytes for one element of array?</para>
/// </summary>
protected int elementSize; /// <summary>
/// 申请到的字节数。（元素的总数 * 单个元素的字节数）。
/// <para>How many bytes for total array?</para>
/// <para>Length * elementSize</para>
/// </summary>
public int ByteLength
{
get { return (this.Length * this.elementSize); }
} protected UnmanagedArrayBase(int elementCount, int elementSize)
{
this.Length = elementCount;
this.elementSize = elementSize;
int memSize = this.Length * this.elementSize;
this.Header = Marshal.AllocHGlobal(memSize);
}
}
}
UnmanagedArray<T>
UnmanagedArray<float>
下面我们以 UnmanagedArray<float> 为例，实现对非托管数组的排序。（下面是快速排序算法）
public static void Sort(this UnmanagedArray<float> array, bool descending)
{
QuickSort(array, , array.Length - , descending);
} public static void Sort(UnmanagedArray<float> array, int start, int length, bool descending)
{
QuickSort(array, start, start + length - , descending);
} private static void QuickSort(UnmanagedArray<float> array, int start, int end, bool descending)
{
if (start >= end) { return; } Stack<int> stack = new Stack<int>();
stack.Push(end);
stack.Push(start);
QuickSort(array, descending, stack);
} private static void QuickSort(UnmanagedArray<float> array, bool descending, Stack<int> stack)
{
while (stack.Count > )
{
int start = stack.Pop();
int end = stack.Pop();
int index = QuickSortPartion(array, start, end, descending);
if (start < index - )
{
stack.Push(index - ); stack.Push(start);
}
if (index + < end)
{
stack.Push(end); stack.Push(index + );
}
}
} private static unsafe int QuickSortPartion(UnmanagedArray<float> array, int start, int end, bool descending)
{
float* pointer = (float*)array.Header.ToPointer();
float pivot, startValue, endValue;
pivot = pointer[start];
while (start < end)
{
startValue = pointer[start];
while ((start < end)
&& ((descending && (startValue.CompareTo(pivot) > ))
|| (!descending) && (startValue.CompareTo(pivot) < )))
{
start++;
startValue = pointer[start];
} endValue = pointer[end];
while ((start < end)
&& ((descending && (endValue.CompareTo(pivot) < ))
|| (!descending) && (endValue.CompareTo(pivot) > )))
{
end--;
endValue = pointer[end];
} if (start < end)
{
pointer[end] = startValue;
pointer[start] = endValue;
}
} return start;
}
public static void Sort(this UnmanagedArray array, bool descending)
原本我以为把这个方法改写一下，用 T代替具体的 float ，就可以实现对任意 T where T : struct,IComparable<T> 的排序，但是VS报了这样的编译错误：无法获取托管类型(“T”)的地址和大小，或无法声明指向它的指针。
看来C#不允许将泛型T作为unsafe里的数组的类型。那么只能用下面的几种方式变通一下。
Marshal
Marshal 有这样2个方法：
// 从非托管数组中读取一个元素
public static object PtrToStructure(IntPtr ptr, Type structureType);
// 向非托管数组写入一个元素
public static void StructureToPtr(object structure, IntPtr ptr, bool fDeleteOld);
用这2个方法就可以实现对非托管数组的读写操作。于是泛型版本( UnmagedArray<T> )的排序算法就实现了。
public static void Sort<T>(this UnmanagedArray<T> array, bool descending) where T : struct, IComparable<T>
{
QuickSort(array, , array.Length - , descending);
} public static void Sort<T>(this UnmanagedArray<T> array, int start, int length, bool descending) where T : struct, IComparable<T>
{
QuickSort(array, start, start + length - , descending);
} private static void QuickSort<T>(UnmanagedArray<T> array, int start, int end, bool descending) where T : struct, IComparable<T>
{
if (start >= end) { return; } var stack = new Stack<int>();
stack.Push(end);
stack.Push(start);
QuickSort(array, descending, stack);
} private static void QuickSort<T>(UnmanagedArray<T> array, bool descending, Stack<int> stack) where T : struct, IComparable<T>
{
IntPtr pointer = array.Header;
Type type = typeof(T);
int elementSize = Marshal.SizeOf(type); while (stack.Count > )
{
int start = stack.Pop();
int end = stack.Pop();
int index = QuickSortPartion(array, start, end, descending, type, elementSize);
if (start < index - )
{
stack.Push(index - ); stack.Push(start);
}
if (index + < end)
{
stack.Push(end); stack.Push(index + );
}
}
} private static int QuickSortPartion<T>(UnmanagedArray<T> array, int start, int end, bool descending, Type type, int elementSize) where T : struct, IComparable<T>
{
IntPtr pointer = array.Header;
IntPtr pivotIndex, startIndex, endIndex;
T pivot, startValue, endValue;
pivotIndex = new IntPtr((int)pointer + start * elementSize);
pivot = (T)Marshal.PtrToStructure(pivotIndex, type);
while (start < end)
{
startIndex = new IntPtr((int)pointer + start * elementSize);
startValue = (T)Marshal.PtrToStructure(startIndex, type);
while ((start < end)
&& ((descending && (startValue.CompareTo(pivot) > ))
|| ((!descending) && (startValue.CompareTo(pivot) < ))))
{
start++;
startIndex = new IntPtr((int)pointer + start * elementSize);
startValue = (T)Marshal.PtrToStructure(startIndex, type);
} endIndex = new IntPtr((int)pointer + end * elementSize);
endValue = (T)Marshal.PtrToStructure(endIndex, type);
while ((start < end)
&& ((descending && (endValue.CompareTo(pivot) < ))
|| ((!descending) && (endValue.CompareTo(pivot) > ))))
{
end--;
endIndex = new IntPtr((int)pointer + end * elementSize);
endValue = (T)Marshal.PtrToStructure(endIndex, type);
} if (start < end)
{
Marshal.StructureToPtr(endValue, startIndex, true);
Marshal.StructureToPtr(startValue, endIndex, true);
}
} return start;
}
public static void Sort(this UnmanagedArray array, bool descending) where T : struct, IComparable
虽然可用，但是用Marshal读写非托管数组效率比较低（使用了装箱拆箱操作）。于是我有了下面这个思路。
+BIT祝威+悄悄在此留下版了个权的信息说：
CodeProvider
我们知道C#现有的类库是支持动态生成和调用C#代码的。因此，我可以在调用 Sort<T>(this UnmanagedArray<T> array, bool descending) 时，临时为具体的T生成一个排序方法，然后去调用这个方法。这就不需要使用 Marshal 了。
具体步骤如下。
准备模板
为了便于编码、维护，我们先准备一个排序代码的模板。模板里的TemplateStructType纯属一个占位符，在使用的时候我们先用具体的类型把它替换掉，就成了我们需要的源代码。
using System;
using System.Collections.Generic;
using System.Runtime.InteropServices; namespace CSharpGL
{
/// <summary>
/// Helper class for sorting unmanaged array.
/// </summary>
public static partial class SortingHelper
{
///// <summary>
///// Sort unmanaged array specified with <paramref name="array"/> at specified area.
///// </summary>
///// <param name="array"></param>
///// <param name="descending">true for descending sort; otherwise false.</param>
//public static void Sort(this UnmanagedArray<TemplateStructType> array, bool descending)
//{
// QuickSort(array, 0, array.Length - 1, descending);
//} /// <summary>
/// Sort unmanaged array specified with <paramref name="array"/> at specified area.
/// </summary>
/// <param name="array"></param>
/// <param name="start">index of first value to be sorted.</param>
/// <param name="length">length of <paramref name="array"/> to bo sorted.</param>
/// <param name="descending">true for descending sort; otherwise false.</param>
public static void Sort(UnmanagedArray<TemplateStructType> array, int start, int length, bool descending)
{
QuickSort(array, start, start + length - , descending);
} private static void QuickSort(UnmanagedArray<TemplateStructType> array, int start, int end, bool descending)
{
if (start >= end) { return; } Stack<int> stack = new Stack<int>();
stack.Push(end);
stack.Push(start);
QuickSort(array, descending, stack);
} private static void QuickSort(UnmanagedArray<TemplateStructType> array, bool descending, Stack<int> stack)
{
while (stack.Count > )
{
int start = stack.Pop();
int end = stack.Pop();
int index = QuickSortPartion(array, start, end, descending);
if (start < index - )
{
stack.Push(index - ); stack.Push(start);
}
if (index + < end)
{
stack.Push(end); stack.Push(index + );
}
}
} private static unsafe int QuickSortPartion(UnmanagedArray<TemplateStructType> array, int start, int end, bool descending)
{
TemplateStructType* pointer = (TemplateStructType*)array.Header.ToPointer();
TemplateStructType pivot, startValue, endValue;
pivot = pointer[start];
while (start < end)
{
startValue = pointer[start];
while ((start < end)
&& ((descending && (startValue.CompareTo(pivot) > ))
|| (!descending) && (startValue.CompareTo(pivot) < )))
{
start++;
startValue = pointer[start];
} endValue = pointer[end];
while ((start < end)
&& ((descending && (endValue.CompareTo(pivot) < ))
|| (!descending) && (endValue.CompareTo(pivot) > )))
{
end--;
endValue = pointer[end];
} if (start < end)
{
pointer[end] = startValue;
pointer[start] = endValue;
}
} return start;
}
}
}
Teamplate method
嵌入的资源
然后把这个模板文件设置为嵌入的资源，以便于调用。
动态生成和调用代码
利用CSharpCodeProvider来把源代码编译为Assembly并调用。
public static void Sort<T>(this UnmanagedArray<T> array, bool descending) where T : struct, IComparable<T>
{
Type type = typeof(T);
string order = ManifestResourceLoader.LoadTextFile(@"Resources\SortingHelper.Order`1.cs");
order = order.Replace("TemplateStructType", type.FullName);
var codeProvider = new CSharpCodeProvider();
var option = new CompilerParameters();
option.GenerateInMemory = true;
option.CompilerOptions = "/unsafe";
option.ReferencedAssemblies.Add("System.dll");
option.ReferencedAssemblies.Add("CSharpGL.dll");
CompilerResults result = codeProvider.CompileAssemblyFromSource(option,
order);
Assembly asm = result.CompiledAssembly;
Type sortingHelper = asm.GetType("CSharpGL.SortingHelper");
Type unmanagedArrayGeneric = typeof(UnmanagedArray<>);
Type unmanagedArray = unmanagedArrayGeneric.MakeGenericType(type);
MethodInfo method = sortingHelper.GetMethod("Sort", new Type[] { unmanagedArray, typeof(int), typeof(int), typeof(bool) });
method.Invoke(null, new object[] { array, , array.Length, descending });
}
+BIT祝威+悄悄在此留下版了个权的信息说：
总结
还有一种利用emit的方法，我就暂时不研究了。