The MASM Forum

General => The Laboratory => Topic started by: guga on October 09, 2020, 10:25:21 PM

Title: QSort issue
Post by: guga on October 09, 2020, 10:25:21 PM
Hi Guys

I´m having some trouble in using qsort (recursive as in msvcrt) to sort a array of structures on a certain order.

I´m trying to sort a array of structure containing 4 dwords each on a total size of 16 bytes. The array is displaced like this:

Format of the structure is:

[MemRecord.PtrMem: D$ 0
MemRecord.Chunck: D$ 0
MemRecord.PtrMotherMem: D$ 0
MemRecord.CommitedSize: D$ 0]

The equates representing the displacement of the structure is:

[MemRecord.PtrMemDis 0
MemRecord.ChunckSizeDis 4
MemRecord.PtrMotherMemDis 8
MemRecord.CommitedSizeDis 12]

[Size_Of_MemRecord 16]


Now..say i have filled this array with:

[MyArray:
MemRecord.Data1.PtrMem: D$ 123456
MemRecord.Data1.Chunck: D$ 0
MemRecord.Data1.PtrMotherMem: D$ 77898
MemRecord.Data1.CommitedSize: D$ 0

MemRecord.Data2.PtrMem: D$ 23456
MemRecord.Data2.Chunck: D$ 0
MemRecord.Data2.PtrMotherMem: D$ 77898
MemRecord.Data2.CommitedSize: D$ 0

MemRecord.Data3.PtrMem: D$ 1454
MemRecord.Data3.Chunck: D$ 0
MemRecord.Data3.PtrMotherMem: D$ 1258
MemRecord.Data3.CommitedSize: D$ 0

MemRecord.Data4.PtrMem: D$ 1457
MemRecord.Data4.Chunck: D$ 0
MemRecord.Data4.PtrMotherMem: D$ 125
MemRecord.Data4.CommitedSize: D$ 0]

I need to sort this array taking onto account the 3rd dword 1st (MemRecord.DataXXX.PtrMotherMem), followed by the 1st one MemRecord.DataXXXX.PtrMem) and also put the Arraay of MemRecord.DataXXX.PtrMem to the bottom when it is 0 and handle the situations when MemRecord.DataXXX.PtrMem = MemRecord.DataXXX.PtrMotherMem

So, the following array should become this (In red is what needs to be sorted 1st, i mean is what is necessary to take onto account to sort) and in Blue is what needs to be sorted after the red marks are identified and sorted:

[MyArray:

MemRecord.Data4.PtrMem: D$ 1454
MemRecord.Data4.Chunck: D$ 0
MemRecord.Data4.PtrMotherMem: D$ 125
MemRecord.Data4.CommitedSize: D$ 0

MemRecord.Data3.PtrMem: D$ 1457
MemRecord.Data3.Chunck: D$ 0
MemRecord.Data3.PtrMotherMem: D$ 1258
MemRecord.Data3.CommitedSize: D$ 0

MemRecord.Data2.PtrMem: D$ 23456
MemRecord.Data2.Chunck: D$ 0
MemRecord.Data2.PtrMotherMem: D$ 77898
MemRecord.Data2.CommitedSize: D$ 0

MemRecord.Data1.PtrMem: D$ 123456
MemRecord.Data1.Chunck: D$ 0
MemRecord.Data1.PtrMotherMem: D$ 77898
MemRecord.Data1.CommitedSize: D$ 0]


Or (Added a 5th element of array to make clear what is needed, ok ?

[MyArray:

MemRecord.Data4.PtrMem: D$ 1454
MemRecord.Data4.Chunck: D$ 0
MemRecord.Data4.PtrMotherMem: D$ 125
MemRecord.Data4.CommitedSize: D$ 0

MemRecord.Data3.PtrMem: D$ 1457
MemRecord.Data3.Chunck: D$ 0
MemRecord.Data3.PtrMotherMem: D$ 1258
MemRecord.Data3.CommitedSize: D$ 0

MemRecord.Data2.PtrMem: D$ 23456
MemRecord.Data2.Chunck: D$ 0
MemRecord.Data2.PtrMotherMem: D$ 77898
MemRecord.Data2.CommitedSize: D$ 0

MemRecord.Data1.PtrMem: D$ 123456
MemRecord.Data1.Chunck: D$ 0
MemRecord.Data1.PtrMotherMem: D$ 77898
MemRecord.Data1.CommitedSize: D$ 0

MemRecord.Data5.PtrMem: D$ 0 <; 0 ? Place it at the bottom of all
MemRecord.Data5.Chunck: D$ 0
MemRecord.Data5.PtrMotherMem: D$ 1 ; <---- Now, since MemRecord.Data5.PtrMem = 0, this structure will be placed at the bottom
MemRecord.Data5.CommitedSize: D$ 0
]


Or..when MemRecord.DataXXX.PtrMem = MemRecord.DataXXX.PtrMotherMem

[MyArray:

MemRecord.Data4.PtrMem: D$ 1
MemRecord.Data4.Chunck: D$ 0
MemRecord.Data4.PtrMotherMem: D$ 125
MemRecord.Data4.CommitedSize: D$ 0

MemRecord.Data3.PtrMem: D$ 1454
MemRecord.Data3.Chunck: D$ 0
MemRecord.Data3.PtrMotherMem: D$ 125
MemRecord.Data3.CommitedSize: D$ 0

MemRecord.Data2.PtrMem: D$ 23456
MemRecord.Data2.Chunck: D$ 0
MemRecord.Data2.PtrMotherMem: D$ 77898
MemRecord.Data2.CommitedSize: D$ 0

MemRecord.Data1.PtrMem: D$ 123456
MemRecord.Data1.Chunck: D$ 0
MemRecord.Data1.PtrMotherMem: D$ 77898
MemRecord.Data1.CommitedSize: D$ 0]


I created a callback function to handle this and placed That works fine only when i´m taking onto account the 1st Dword member of the structure.



; Equates used to sort
[SORT_ORDER_ASCENDING 0-1] ;  ascending order when they are arranged from the smallest to the largest number. E.g. 5, 9, 13, 17 and 21 are arranged in ascending order.
[SORT_ORDER_DESCENDING 1] ; descending order when they are arranged from the largest to the smallest number. E.g. 25, 21, 17, 13 and 9 are arranged in descending order.
[SORT_ORDER_EQUAL 0]

Proc StartMemSortOriginal:
    Arguments @PreviousElement, @NextElement
    Local @PreviousType, @NextType, @Return
    Uses ecx

    mov ecx D@NextElement | mov eax D$ecx+MemRecord.PtrMemDis | mov D@NextType eax
    mov ecx D@PreviousElement | mov eax D$ecx+MemRecord.PtrMemDis | mov D@PreviousType eax

    mov D@Return SORT_ORDER_EQUAL ; Assume 1st if they are equal
    mov eax D@PreviousType

    ; When the previous or next Element are 0, we will place it at the bottom of the list
    ; Since there´s no memory location starting with 0-1, i set this as a flag, in order
    ; to it guaranteed it will be placed at the bottom.
    If eax = 0
        mov eax 0-1 ; Dummy value to place 0 cases at the bottom.
    End_If
    If D@NextType = 0
        mov D@NextType 0-1 ; Dummy value to place 0 cases at the bottom.
    End_if

    .If eax < D@NextType ; If previous type is smaller then next type sort ascending
        mov D@Return SORT_ORDER_ASCENDING
    .Else_if eax > D@NextType ; If previous type is bigger then next type sort descending
        mov D@Return SORT_ORDER_DESCENDING
    .End_If
    mov eax D@Return

EndP



But, then, when i tried to do the same using the 1st and 3rd dword, it failed to organize and placed the cases where  MemRecord.DataXXX.PtrMotherMem = MemRecord.DataXXX.PtrMem


I did this:


; Sort uRsrcList Table by Type, then by name and then by lang:
[SORT_ORDER_ASCENDING 0-1] ;  ascending order when they are arranged from the smallest to the largest number. E.g. 5, 9, 13, 17 and 21 are arranged in ascending order.
[SORT_ORDER_DESCENDING 1] ; descending order when they are arranged from the largest to the smallest number. E.g. 25, 21, 17, 13 and 9 are arranged in descending order.
[SORT_ORDER_EQUAL 0]

Proc StartMemSort:
    Arguments @PreviousElement, @NextElement
    Local @PreviousMemType, @NextmemType, @Return, @PreviousMotherType, @NextMotherType
    Uses ecx, ebx

    mov ecx D@NextElement | mov eax D$ecx+MemRecord.PtrMemDis | mov D@NextMemType eax
    mov ecx D@PreviousElement | mov eax D$ecx+MemRecord.PtrMemDis | mov D@PreviousMemType eax
    mov ecx D@NextElement | mov eax D$ecx+MemRecord.PtrMotherMemDis | mov D@NextMotherType eax
    mov ecx D@PreviousElement | mov eax D$ecx+MemRecord.PtrMotherMemDis | mov D@PreviousMotherType eax

    mov D@Return SORT_ORDER_EQUAL ; Assume 1st if they are equal
    mov eax D@PreviousMemType
    mov ebx D@PreviousMotherType

    ; When the previous or next Element are 0, we will place it at the bottom of the list
    ; Since there´s no memory location starting with 0-1, i set this as a flag, in order
    ; to it guaranteed it will be placed at the bottom.
    If eax = 0
        mov eax 0-1
    End_If
    If D@NextMotherType = 0
        mov D@NextMotherType 0-1
    End_if

    ...If eax < D@NextMotherType ; If previous type is smaller then next type sort ascending
        ..If D@NextMotherType = 0-1
            mov D@Return SORT_ORDER_ASCENDING
        ..Else
            If ebx < D@NextMotherType
                mov D@Return SORT_ORDER_ASCENDING
            Else
                mov D@Return SORT_ORDER_DESCENDING
            End_If
        ..End_If
        ;mov D@Return SORT_ORDER_ASCENDING
    ...Else_if eax > D@NextMotherType ; If previous type is bigger then next type sort descending
        ..If eax = 0-1
            mov D@Return SORT_ORDER_DESCENDING
        ..Else
            If ebx < D@NextMotherType
                mov D@Return SORT_ORDER_ASCENDING
            Else
                mov D@Return SORT_ORDER_DESCENDING
            End_If
        ..End_If
        ;mov D@Return SORT_ORDER_DESCENDING
    ...End_If

    mov eax D@Return

EndP


Btw...the call to the callback function is the same as used in msvcrt., but i created a own library for it to behave the same.

D$MemTableCount = 4,5, 6,..XXX structures that fors the array
Size_Of_MemRecord = Always 16 bytes long

call 'FastCRT.qsort' MemTable, D$MemTableCount, Size_Of_MemRecord, StartMemSort


What i´m doing wrong ?