Added ft_list_sort.s

4 files changed, 211 insertions, 76 deletions

diff --git a/Makefile b/Makefile
index 9f45ddc..2925114 100644
--- a/Makefile
+++ b/Makefile
@@ -6,7 +6,7 @@
 #    By: cacharle <marvin@42.fr>                    +#+  +:+       +#+         #
 #                                                 +#+#+#+#+#+   +#+            #
 #    Created: 2019/11/22 02:56:22 by cacharle          #+#    #+#              #
-#    Updated: 2020/02/05 21:15:19 by cacharle         ###   ########.fr        #
+#    Updated: 2020/02/08 00:14:34 by cacharle         ###   ########.fr        #
 #                                                                              #
 # **************************************************************************** #
 
@@ -14,7 +14,7 @@ RM = rm -f
 LIB = ar rcs
 
 CC = gcc
-CCFLAGS = -Wall -Wextra -fomit-frame-pointer
+CCFLAGS = -g -Wall -Wextra -fomit-frame-pointer
 
 NASM = nasm
 NASMFLAGS = -f macho64
@@ -22,7 +22,7 @@ NASMFLAGS = -f macho64
 NAME = libasm.a
 ASMSRC = ft_strlen.s ft_strcpy.s ft_strcmp.s ft_write.s ft_read.s \
 		 ft_strdup.s ft_atoi_base.s ft_list_push_front.s \
-		 ft_list_size.s #ft_list_sort.s ft_list_remove_if.s
+		 ft_list_size.s ft_list_sort.s #ft_list_remove_if.s
 ASMOBJ = $(ASMSRC:.s=.o)
 
 all: $(NAME)
diff --git a/ft_list_size.s b/ft_list_size.s
index ad89999..b41cfb4 100644
--- a/ft_list_size.s
+++ b/ft_list_size.s
@@ -21,5 +21,5 @@ FT_LIST_SIZE_LOOP:
 	inc eax
 	mov rdi, [rdi + 8]
 	jmp FT_LIST_SIZE_LOOP
-FT_LIST_SIZE_END
+FT_LIST_SIZE_END:
 	ret
diff --git a/ft_list_sort.s b/ft_list_sort.s
index 23924e1..a541bd8 100644
--- a/ft_list_sort.s
+++ b/ft_list_sort.s
@@ -12,106 +12,115 @@
 
 global _ft_list_sort
 
-; void ft_list_sort(t_list **begin_list, int (*cmp)());
+%define NULL 0x0
+
+; void ft_list_sort(t_list **begin_list, int (*cmp)(void*, void*));
 _ft_list_sort:
-	; t_list *fast
-	; t_list *slow
-	; t_list *middle
-	sub  rsp, 24
-
-	cmp  rdi, 0x0
-	je   FT_LIST_SORT_END
-	cmp  [rdi], 0x0
-	je   FT_LIST_SORT_END
-	cmp  [[rdi] + 8], 0x0  ; use tmp register
-	je   FT_LIST_SORT_END
-
-	mov  [rsp], [[rdi] + 8]
-	mov  [rsp + 8], [rdi]
-FT_GET_MIDDLE_LOOP: 
-	mov  [rsp], [rsp + 8]
-	cmp  [rsp], 0x0
-	je   FT_GET_MIDDLE_LOOP_END
-	mov  [rsp], [rsp + 8]
-	mov  [rsp + 8], [[rsp + 8] + 8] ; i want c pointers back plz
-FT_GET_MIDDLE_LOOP_END:
-	mov  [rsp + 16], [[rsp + 8] + 8]
-	mov  [[rsp + 8] + 8], 0x0
+	; 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
 
-	push rdi
-	call _ft_list_sort
-	pop  rdi
+	; 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
-	mov  rdi, [rsp + 16]
-	call _ft_list_sort
+	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  rdx, rsi
-	mov  rdi, [rdi]
-	mov  rsi, [rsp + 16]
-	call _merge_sorted_list
+	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(...);
 
-	mov  [rdi], rax
-
-	add rsp, 24
+	; restoring stack frame
+	mov  rsp, rbp
+	pop  rbp
 FT_LIST_SORT_END:
 	ret
 
 
-
-; t_list *merge_sorted_list(t_list* l1, t_list* l2, int (*cmp)())
-_merge_sorted_list:
-	sub  rsp, 8
-
-	cmp  rdi, 0x0
-	je   MERGE_SORTED_LIST_RETURN_L2
-	cmp  rsi, 0x0
-	je   MERGE_SORTED_LIST_RETURN_L1
+; 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
-	mov  rdi, [rdi]
-	mov  rsi, [rsi]
-	call rdx        ; cmp
+	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  rax, 0x0
-	jl   L1_LT_L2
+	cmp  eax, 0
+	jl   MERGE_SORTED_LIST_L1_LT_L2
 
-; L1_GE_L2
-	mov  rsp, rsi
+	; 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
-	push rsi
 	mov  rdi, [rdi + 8]
-	call _merge_sorted_list
-	pop  rsi
+	call _st_merge_sorted_list         ; merge_sort_list(l1->next, l2, cmp)
 	pop  rdi
-	mov  [rsp + 8], rax
+	mov  [rdi + 8], rax
+	mov  rax, rdi
 	jmp  MERGE_SORTED_LIST_END
 
-L1_LT_L2:
-	mov  rsp, rdi
-	push rdi
-	push rsi
-	mov  rsi, [rsi + 8]
-	call _merge_sorted_list
-	pop  rsi
-	pop  rdi
-	mov  [rsp + 8], rax
-
-MERGE_SORTED_LIST_END:
-	mov  rax, [rsp]
-	add  rsp, 8
-	ret
 MERGE_SORTED_LIST_RETURN_L1:
 	mov  rax, rdi
 	ret
 MERGE_SORTED_LIST_RETURN_L2:
 	mov  rax, rsi
+MERGE_SORTED_LIST_END:
 	ret
diff --git a/main.c b/main.c
index 333d2a2..9c28aef 100644
--- a/main.c
+++ b/main.c
@@ -6,7 +6,7 @@
 /*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
 /*                                                +#+#+#+#+#+   +#+           */
 /*   Created: 2019/11/22 02:02:24 by cacharle          #+#    #+#             */
-/*   Updated: 2019/11/25 03:29:53 by cacharle         ###   ########.fr       */
+/*   Updated: 2020/02/08 02:58:50 by cacharle         ###   ########.fr       */
 /*                                                                            */
 /* ************************************************************************** */
 
@@ -20,6 +20,116 @@ typedef struct		s_list
 	struct s_list	*next;
 }					t_list;
 
+
+int*
+create_data_elem(int data)
+{
+	int *data_ptr = malloc(sizeof(int));
+	if (data_ptr == NULL)
+		return (NULL);
+	*data_ptr = data;
+	return data_ptr;
+}
+
+t_list*
+create_elem(int data)
+{
+	t_list *new = malloc(sizeof(t_list));
+	if (new == NULL)
+		return NULL;
+	if ((new->data = create_data_elem(data)) == NULL)
+		return (NULL);
+	new->next = NULL;
+	return new;
+}
+
+static void
+push_front(t_list **lst_ptr, t_list *new_front)
+{
+	if (lst_ptr == NULL || new_front == NULL)
+		return ;
+	new_front->next = *lst_ptr;
+	*lst_ptr = new_front;
+}
+
+static t_list*
+reverse(t_list *list)
+{
+	if (list == NULL || list->next == NULL)
+		return list;
+	t_list *tmp = reverse(list->next);
+	list->next->next = list;
+	list->next = NULL;
+	return tmp;
+}
+
+t_list*
+list_from_format(char *fmt)
+{
+	t_list *head = NULL;
+
+	while (fmt != NULL && *fmt)
+	{
+		int n = (int)strtol(fmt, &fmt, 10);
+		t_list *elem = create_elem(n);
+		push_front(&head, elem);
+	}
+	return reverse(head);
+}
+
+t_list*
+list_dup(t_list *list)
+{
+	t_list *dup_head = NULL;
+
+	while (list != NULL)
+	{
+		t_list *tmp = create_elem(*(int*)list->data);
+		push_front(&dup_head, tmp);
+	}
+	return reverse(dup_head);
+}
+
+int
+list_cmp(t_list *l1, t_list *l2)
+{
+	if (l1 == NULL && l2 == NULL)
+		return 0;
+	if (l1 == NULL)
+		return -1;
+	if (l2 == NULL)
+		return 1;
+	if (l1->data == NULL)
+		return -1;
+	if (l2->data == NULL)
+		return 1;
+	if (*(int*)l1->data != *(int*)l2->data)
+		return *(int*)l1->data - *(int*)l2->data;
+	return list_cmp(l1->next, l2->next);
+}
+
+void
+list_print(t_list *list)
+{
+	while (list != NULL)
+	{
+		printf("[%d] -> ", *(int*)list->data);
+		list = list->next;
+	}
+	printf("(null)");
+}
+
+void
+list_destroy(t_list *list)
+{
+	if (list == NULL)
+		return ;
+	list_destroy(list->next);
+	if (list->data != NULL)
+		free(list->data);
+	free(list);
+}
+
 int ft_strlen(char *);
 char *ft_strcpy(char *dst, const char *src);
 int ft_strcmp(const char *s1, const char *s2);
@@ -32,6 +142,14 @@ void ft_list_push_front(t_list **begin_list, void *data);
 int ft_list_size(t_list *begin_list);
 void ft_list_sort(t_list **begin_list, int (*cmp)());
 
+int compar(void *a, void *b)
+{
+	printf("---\n");
+	printf("a = %p, b = %p\n", a, b);
+	printf("*a = %d, *b = %d\n", *(int*)a, *(int*)b);
+	return *(int*)a - *(int*)b;
+}
+
 int main()
 {
 	/* char *a = ""; */
@@ -71,6 +189,14 @@ int main()
 	/* printf("%d\n", check_base("01")); */
 
 	/* printf("%d\n", ft_atoi_base(" \t\n\r\v\f\r 10\t0101001", "01")); */
-	printf("_%d_\n", ft_atoi_base(" 755x+", "01234567"));
+	/* printf("_%d_\n", ft_atoi_base(" 755x+", "01234567")); */
+
+	/* system("vmmap a.out"); */
+	/* t_list *a = list_from_format("-1 2 3 98 1234 12 123 4 123 -123 2 5 6 0 1 3 4"); */
+	/* t_list *a = list_from_format("1"); */
+	t_list *a = NULL;
+	printf("%d: ", ft_list_size(a)); list_print(a); putchar('\n');
+	ft_list_sort(&a, compar);
+	printf("%d: ", ft_list_size(a)); list_print(a); putchar('\n');
 	return 0;
 }