A Multi-Field Single Pass Shell Sort Algorithm

by MacGregor K. Phillips





Listing One



// Journal Entry Index File Structure

typedef struct _DIARYENTRY

{

    BYTE                Date_Time[32];  // Date time as a string.

    BYTE                Year[6];        // Year as string.

    WORD                Type_Entry;     // 1 = date entry, 2 = keyword entry.

    BYTE                KeyWord[132];   // Keyword or "A" for date entry.

    DWORD               dwCreated[2];   // Date time created - msd to lsd.

    SYSTEMTIME          st;             // local time created.

    ULARGE_INTEGER      uliOffset;      // Offset of entry in file.

} DIARYENTRY, *LPDIARYENTRY;





Listing Two





// Shell Sort Template Structure

typedef struct _SORT_TEMPLATE

{

    DWORD   TYPE_SORT;      // Type of sort.

    DWORD   COMPARE_DIRECTION;  // FORWARD or BACKGROUND.

    DWORD   RECORD_SIZE;    // Record size.

    DWORD   COMPARE_SIZE;   // Sort field size.

    DWORD   COMPARE_OFFSET; // Offset of field in record to sort or -1 for end

    DWORD   TS;             // Start of 2nd sort or -1 for end marker.

    DWORD   CD;

    DWORD   RS;

    DWORD   CS;

    DWORD   CO;

    DWORD   TS1;                // Start of 3rd sort or -1 for end marker.

    DWORD   CD1;

    DWORD   RS1;

    DWORD   CS1;

    DWORD   CO1;

    DWORD   END_MARKER;         // Must be set to -1.

} SORT_TEMPLATE, *LPSORT_TEMPLATE;





Listing Three



// Diary Sort Template

SORT_TEMPLATE   DiarySort = {SORT_WORDS,FORWARD,sizeof(DIARYENTRY),1,38,

          SORT_STRINGS,FORWARD,sizeof(DIARYENTRY),130,40,

          SORT_DWORDS,FORWARD,sizeof(DIARYENTRY),2,172,SORT_END};





Listing Four



// Sort Algorithm Core.



while(TRUE)

{

    __asm

    {

        // Pointer to sort parameter structure.

        //.....................................

        mov     edx,dwTempEDX

        // Offset to current sort parameter in structure.

        //...............................................

        mov     ebx,dwTempEBX

        // Setup the records to compare.

        //..............................

        mov     esi,dwIndexB    // Bottom index.

        mov     edi,dwIndexC    // Center index.

        // Point to the part of the record to compare.

        //............................................

        add     esi,dword ptr [edx][ebx].COMPARE_OFFSET

        add     edi,dword ptr [edx][ebx].COMPARE_OFFSET

        mov     lpRecordB,esi

        mov     lpRecordC,edi

        // Size of the data to compare. If bytes, the number of bytes; if 

        // words, the number of words; if dwords, the number of dwords.

        //................................................

        mov     ecx,dword ptr [edx][ebx].COMPARE_SIZE

        // See if we are doing a signed comparison.

        //.........................................

        btr     dword ptr [edx][ebx].TYPE_SORT,7

        setc    Signed

        // Setup the direction for the comparision.

        //.........................................

        cmp     dword ptr [edx][ebx].COMPARE_DIRECTION,BACKWARD

        jne     L2

        // Comparision is performed backwards - high address to low.

        //..........................................................

        std

        // Compare bytes.

        //...............

    L2: cmp     dword ptr [edx][ebx].TYPE_SORT,SORT_BYTES

        jne     L3

        repe    cmpsb

        jmp     L5

        // Compare words.

        //...............

    L3: cmp     dword ptr [edx][ebx].TYPE_SORT,SORT_WORDS

        jne     L4

        rep     cmpsw

        jmp     L5

        // Compare dwords.

        //................

    L4: cmp     dword ptr [edx][ebx].TYPE_SORT,SORT_DWORDS

        jne     L7                  // Default to sort strings.

        repe    cmpsd

        // Make sure - reset direction flag to low to high address.

        //.........................................................

    L5: cld         

                        

        // Set the flags depending on if we sorted signed fields or not.

        //...............................................

        pushfd

        cmp     Signed,1

        je      L6

        popfd

        seta    Above

        setb    Below

        jmp     L8

    L6: popfd

        setg    Above

        setl    Below

        // Reset the signed field in the TYPE_SORT parameter for next record.

        //........................................

        bts     dword ptr [edx][ebx].TYPE_SORT,7

        jmp     L8



        // Save all of our registeres.

        //............................

    L7: pushad

    }

    // Compare strings using user default settings.

    //.............................................

    iCompareResult = CompareString(LOCALE_USER_DEFAULT,NORM_IGNORECASE,

                                   lpRecordB,-1,lpRecordC,-1);

    Above = 0;

    Below = 0;

    if (iCompareResult == CSTR_LESS_THAN)

    {

        Below = 1;

    }

    else if (iCompareResult == CSTR_GREATER_THAN)

    {

        Above = 1;

    }

    __asm

    {

        popad

        // Break if the fields are not equal.

        //...................................

        cmp     iCompareResult,CSTR_EQUAL

    L8: jne     CheckSwap

        // Break if the fields are equal and we have no more fields to sort 

        // on; else continue sorting the record on the next field.

        //...........................................

        add     ebx,20          // Size of 1 sort parameter.

        mov     dwTempEBX,ebx

        cmp     dword ptr [edx][ebx].TYPE_SORT,SORT_END

        je      CheckSwap

    }

}   // while TRUE













4



