/*++ Copyright (c) 1998, Microsoft Corporation Module Name: sort.c Abstract: This module contains routines used for efficiently sorting information. Author: Abolade Gbadegesin (aboladeg) 18-Feb-1998 Based on version written for user-mode RAS user-interface. (net\routing\ras\ui\common\nouiutil\noui.c). Revision History: --*/ #include "precomp.h" #pragma hdrstop NTSTATUS ShellSort( VOID* pItemTable, ULONG dwItemSize, ULONG dwItemCount, PCOMPARE_CALLBACK CompareCallback, VOID* pDestinationTable OPTIONAL ) /* Sort an array of items in-place using shell-sort. ** This function calls ShellSortIndirect to sort a table of pointers ** to table items. We then move the items into place by copying. ** This algorithm allows us to guarantee that the number ** of copies necessary in the worst case is N + 1. ** ** Note that if the caller merely needs to know the sorted order ** of the array, ShellSortIndirect should be called since that function ** avoids moving items altogether, and instead fills an array with pointers ** to the array items in the correct order. The array items can then ** be accessed through the array of pointers. */ { VOID** ppItemTable; LONG N; LONG i; UCHAR *a, **p, *t = NULL; if (!dwItemCount) { return STATUS_SUCCESS; } /* allocate space for the table of pointers. */ ppItemTable = ExAllocatePoolWithTag( NonPagedPool, dwItemCount * sizeof(VOID*), NAT_TAG_SORT ); if (!ppItemTable) { return STATUS_NO_MEMORY; } /* call ShellSortIndirect to fill our table of pointers ** with the sorted positions for each table element. */ ShellSortIndirect( pItemTable, ppItemTable, dwItemSize, dwItemCount, CompareCallback ); /* now that we know the sort order, move each table item into place. ** This is easy if we are sorting to a different array. */ if (pDestinationTable) { for (i = 0; i < (LONG)dwItemCount; i++) { RtlCopyMemory( (PUCHAR)pDestinationTable + i * dwItemSize, ppItemTable[i], dwItemSize ); } ExFreePool(ppItemTable); return STATUS_SUCCESS; } /* We are sorting in-place, which is a little more involved. ** This involves going through the table of pointers making sure ** that the item which should be in 'i' is in fact in 'i', moving ** things around if necessary to achieve this condition. */ a = (UCHAR*)pItemTable; p = (UCHAR**)ppItemTable; N = (LONG)dwItemCount; for (i = 0; i < N; i++) { LONG j, k; UCHAR* ai = (a + i * dwItemSize), *ak, *aj; /* see if item 'i' is not in-place */ if (p[i] != ai) { /* item 'i' isn't in-place, so we'll have to move it. ** if we've delayed allocating a temporary buffer so far, ** we'll need one now. */ if (!t) { t = ExAllocatePoolWithTag( NonPagedPool, dwItemSize, NAT_TAG_SORT ); if (!t) { ExFreePool(ppItemTable); return STATUS_NO_MEMORY; } } /* save a copy of the item to be overwritten */ RtlCopyMemory(t, ai, dwItemSize); k = i; ak = ai; /* Now move whatever item is occupying the space where it should be. ** This may involve moving the item occupying the space where ** it should be, etc. */ do { /* copy the item which should be in position 'j' ** over the item which is currently in position 'j'. */ j = k; aj = ak; RtlCopyMemory(aj, p[j], dwItemSize); /* set 'k' to the position from which we copied ** into position 'j'; this is where we will copy ** the next out-of-place item in the array. */ ak = p[j]; k = (ULONG)(ak - a) / dwItemSize; /* keep the array of position pointers up-to-date; ** the contents of 'aj' are now in their sorted position. */ p[j] = aj; } while (ak != ai); /* now write the item which we first overwrote. */ RtlCopyMemory(aj, t, dwItemSize); } } if (t) { ExFreePool(t); } ExFreePool(ppItemTable); return STATUS_SUCCESS; } VOID ShellSortIndirect( VOID* pItemTable, VOID** ppItemTable, ULONG dwItemSize, ULONG dwItemCount, PCOMPARE_CALLBACK CompareCallback ) /* Sorts an array of items indirectly using shell-sort. ** 'pItemTable' points to the table of items, 'dwItemCount' is the number ** of items in the table, and 'CompareCallback' is a function called ** to compare items. ** ** Rather than sort the items by moving them around, ** we sort them by initializing the table of pointers 'ppItemTable' ** with pointers such that 'ppItemTable[i]' contains a pointer ** into 'pItemTable' for the item which would be in position 'i' ** if 'pItemTable' were sorted. ** ** For instance, given an array pItemTable of 5 strings as follows ** ** pItemTable[0]: "xyz" ** pItemTable[1]: "abc" ** pItemTable[2]: "mno" ** pItemTable[3]: "qrs" ** pItemTable[4]: "def" ** ** on output ppItemTable contains the following pointers ** ** ppItemTable[0]: &pItemTable[1] ("abc") ** ppItemTable[1]: &pItemTable[4] ("def") ** ppItemTable[2]: &pItemTable[2] ("mno") ** ppItemTable[3]: &pItemTable[3] ("qrs") ** ppItemTable[4]: &pItemTable[0] ("xyz") ** ** and the contents of pItemTable are untouched. ** And the caller can print out the array in sorted order using ** for (i = 0; i < 4; i++) { ** printf("%s\n", (char *)*ppItemTable[i]); ** } */ { /* The following algorithm is derived from Sedgewick's Shellsort, ** as given in "Algorithms in C++". ** ** The Shellsort algorithm sorts the table by viewing it as ** a number of interleaved arrays, each of whose elements are 'h' ** spaces apart for some 'h'. Each array is sorted separately, ** starting with the array whose elements are farthest apart and ** ending with the array whose elements are closest together. ** Since the 'last' such array always has elements next to each other, ** this degenerates to Insertion sort, but by the time we get down ** to the 'last' array, the table is pretty much sorted. ** ** The sequence of values chosen below for 'h' is 1, 4, 13, 40, 121, ... ** and the worst-case running time for the sequence is N^(3/2), where ** the running time is measured in number of comparisons. */ ULONG dwErr; LONG i, j, h, N; UCHAR* a, *v, **p; a = (UCHAR*)pItemTable; p = (UCHAR**)ppItemTable; N = (LONG)dwItemCount; /* Initialize the table of position pointers. */ for (i = 0; i < N; i++) { p[i] = (a + i * dwItemSize); } /* Move 'h' to the largest increment in our series */ for (h = 1; h < N/9; h = 3 * h + 1) { } /* For each increment in our series, sort the 'array' for that increment */ for ( ; h > 0; h /= 3) { /* For each element in the 'array', get the pointer to its ** sorted position. */ for (i = h; i < N; i++) { /* save the pointer to be inserted */ v = p[i]; j = i; /* Move all the larger elements to the right */ while (j >= h && CompareCallback(p[j - h], v) > 0) { p[j] = p[j - h]; j -= h; } /* put the saved pointer in the position where we stopped. */ p[j] = v; } } }