Step to UEFI (159）UEFI 下的排序

大多数情况下，2层循环的冒泡排序对于一般用户已经足够，但是如果对于速度有要求，那就需要考虑效率更高的排序算法了。最近偶然看到 MdeModulePkg\Include\Library\SortLib.h 提供的排序功能，研究之后编写如下的例子。
这个库的核心是PerformQuickSort() 函数，调用者给出需要排序的 buffer，然后给出其中每一个元素的大小和数量，然后这个函数还会调用作为参数指定的CompareFunction函数。通过这个函数，不但可以比较数字或者字符串，还可以比较自动定义的规则，比方说设定书记>厂长>科长之类的……

示例代码如下：

/**
  Function to perform a Quick Sort on a buffer of comparable elements.

  Each element must be equally sized.

  If BufferToSort is NULL, then ASSERT.
  If CompareFunction is NULL, then ASSERT.

  If Count is < 2 , then perform no action.
  If Size is < 1 , then perform no action.

  @param[in, out] BufferToSort   On call, a Buffer of (possibly sorted) elements;
                                 on return, a buffer of sorted elements.
  @param[in]  Count              The number of elements in the buffer to sort.
  @param[in]  ElementSize        The size of an element in bytes.
  @param[in]  CompareFunction    The function to call to perform the comparison
                                 of any two elements.
**/
VOID
EFIAPI
PerformQuickSort (
  IN OUT VOID                   *BufferToSort,
  IN CONST UINTN                Count,
  IN CONST UINTN                ElementSize,
  IN       SORT_COMPARE         CompareFunction
  );
代码如下：
#include <stdlib.h>
#include <stdio.h>
#include <Uefi.h>
#include <Library/UefiLib.h>
#include <Library/ShellCEntryLib.h>
#include <Library/MemoryAllocationLib.h>
#include <Library/BaseMemoryLib.h>
#include <Library/SortLib.h>

#define TOTAL           100
#define NAMELENGTH        4

/** Expands to an integer constant expression that is the maximum value
    returned by the rand function.
**/
#define RAND_MAX  0x7fffffff
static UINT32 next = 1;

typedef struct {
            char Name[NAMELENGTH+1];
            int  Score;
} TScoreRecord;

/** Compute a pseudo-random number.
  *
  * Compute x = (7^5 * x) mod (2^31 - 1)
  * without overflowing 31 bits:
  *      (2^31 - 1) = 127773 * (7^5) + 2836
  * From "Random number generators: good ones are hard to find",
  * Park and Miller, Communications of the ACM, vol. 31, no. 10,
  * October 1988, p. 1195.
**/
int
rand()
{
  INT32 hi, lo, x;

  /* Can't be initialized with 0, so use another value. */
  if (next == 0)
    next = 123459876;
  hi = next / 127773;
  lo = next % 127773;
  x = 16807 * lo - 2836 * hi;
  if (x < 0)
    x += 0x7fffffff;
  return ((next = x) % ((UINT32)RAND_MAX + 1));
}

/**
  Test comparator.

  @param[in] b1   The first INTN
  @param[in] b2   The other INTN

  @retval 0       They are the same.
  @retval -1      b1 is less than b2
  @retval 1       b1 is greater then b2
**/
INTN
EFIAPI
Compare (CONST TScoreRecord *b1, CONST TScoreRecord *b2)
{
  if ((b1->Score)<(b2->Score)) {
          return -1;
  }
  if ((b1->Score)>(b2->Score)) {
          return 1;
  }
  return (0);
}

int main()
{       
        TScoreRecord   *SR;
        int             Index,NameIndex;
        
        SR = AllocatePool (sizeof(TScoreRecord)*TOTAL);
        
        for (Index=0;Index<TOTAL;Index++) {
            //Generate a name
            for (NameIndex=0;NameIndex<NAMELENGTH;NameIndex++) {
                        SR[Index].Name[NameIndex]=(rand()%26)+'A';
                }
            SR[Index].Name[NAMELENGTH]=0;
            //Generate a score
            SR[Index].Score=rand()%150;
            //Output
            printf("[%d] %s %d\n",Index,SR[Index].Name,SR[Index].Score);
        }

        //Sort
        PerformQuickSort (SR,TOTAL,sizeof(TScoreRecord),Compare);

        //Show the sort result
        for (Index=0;Index<TOTAL;Index++) {
            printf("[%d] %s %d\n",Index,SR[Index].Name,SR[Index].Score);
        }        
        
        FreePool(SR);
        
        return 0;
}

运行结果：

完整代码和EFI 下载：

SortTest

此外，还有一个有意思的问题：如果Compare (CONST TScoreRecord *b1, CONST TScoreRecord *b2) 这里定义为Compare (TScoreRecord *b1, TScoreRecord *b2)，那么在编译时，会在PerformQuickSort (SR,TOTAL,sizeof(TScoreRecord),Compare); 报告C4090错误。因为编译器报告错误位置和实际位置着实不同，为了找到原因着实让我花费了不少时间。