1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
; **************************************************************************** ;
; ;
; ::: :::::::: ;
; ft_list_sort.s :+: :+: :+: ;
; +:+ +:+ +:+ ;
; By: cacharle <marvin@42.fr> +#+ +:+ +#+ ;
; +#+#+#+#+#+ +#+ ;
; Created: 2019/11/22 21:03:52 by cacharle #+# #+# ;
; Updated: 2019/11/22 21:27:27 by cacharle ### ########.fr ;
; ;
; **************************************************************************** ;
global ft_list_sort
%define NULL 0x0
; void ft_list_sort(t_list **begin_list, int (*cmp)(void*, void*));
ft_list_sort:
; t_list *slow : rax = *begin_list
; t_list *fast : rbx = (*begin_list)->next
; t_list *middle : rsp + 0
; === base condition ===
cmp rdi, NULL
je FT_LIST_SORT_END ; if begin_list == NULL return
mov rax, [rdi]
cmp rax, NULL
je FT_LIST_SORT_END ; if *begin_list == NULL return
mov rbx, [rax + 8]
cmp rbx, NULL
je FT_LIST_SORT_END ; if (*begin_list)->next == NULL return
; === find list middle loop ===
FT_LIST_SORT_MIDDLE_LOOP: ; do {
mov rbx, [rbx + 8] ; fast = fast->next
cmp rbx, NULL
je FT_LIST_SORT_MIDDLE_LOOP_END ; if fast == NULL break
mov rbx, [rbx + 8] ; fast = fast->next
mov rax, [rax + 8] ; slow = slow->next
cmp rbx, NULL
jne FT_LIST_SORT_MIDDLE_LOOP ; } while (fast != NULL)
FT_LIST_SORT_MIDDLE_LOOP_END:
; create a stack frame for local variable to store middle address
push rbp
mov rbp, rsp
sub rsp, 8
; store middle in [rbp - 8]
mov rcx, [rax + 8]
mov [rbp - 8], rcx
mov qword [rax + 8], NULL ; slow->next = NULL
; === sorting both child list ===
push rdi
push rsi
call ft_list_sort ; ft_list_sort(begin_list, cmp)
lea rdi, [rbp - 8]
call ft_list_sort ; ft_list_sort(&middle, cmp)
pop rsi
pop rdi
; === merging sorted child ===
push rdi
push rsi
mov rdi, [rdi] ; arg_1 = *begin_list
mov rdx, rsi ; arg_3 = cmp
mov rsi, [rbp - 8] ; arg_2 = middle
call _st_merge_sorted_list
pop rsi
pop rdi
mov [rdi], rax ; *begin_list = st_merge_sorted_list(...);
; restoring stack frame
mov rsp, rbp
pop rbp
FT_LIST_SORT_END:
ret
; t_list *st_merge_sorted_list(t_list* l1, t_list* l2, int (*cmp)(void*, void*))
_st_merge_sorted_list:
cmp rdi, NULL
je MERGE_SORTED_LIST_RETURN_L2 ; if l1 == NULL return l2
cmp rsi, NULL
je MERGE_SORTED_LIST_RETURN_L1 ; if l2 == NULL return l1
push rdi
push rsi
push rdx
mov rdi, [rdi + 0] ; l1->data
mov rsi, [rsi + 0] ; l2->data
xor rax, rax
call rdx ; cmp
pop rdx
pop rsi
pop rdi
cmp eax, 0
jl MERGE_SORTED_LIST_L1_LT_L2
; if l1 >= l2
push rsi ; save l2
mov rsi, [rsi + 8] ; l2 = l2->next
call _st_merge_sorted_list ; merge_sorted_list(l1, l2->next, cmp)
pop rsi ; restore rsi
mov [rsi + 8], rax
mov rax, rsi
jmp MERGE_SORTED_LIST_END
; else
MERGE_SORTED_LIST_L1_LT_L2:
push rdi
mov rdi, [rdi + 8]
call _st_merge_sorted_list ; merge_sort_list(l1->next, l2, cmp)
pop rdi
mov [rdi + 8], rax
mov rax, rdi
jmp MERGE_SORTED_LIST_END
MERGE_SORTED_LIST_RETURN_L1:
mov rax, rdi
ret
MERGE_SORTED_LIST_RETURN_L2:
mov rax, rsi
MERGE_SORTED_LIST_END:
ret
|
