Author Topic: QSort issue  (Read 311 times)

guga

  • Member
  • *****
  • Posts: 1357
  • Assembly is a state of art.
    • RosAsm
QSort issue
« 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.

Code: [Select]

; 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:

Code: [Select]
; 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 ?
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com