From 56150213f54af9a37abf8a1a719d51eb4491087c Mon Sep 17 00:00:00 2001 From: Charles Date: Thu, 6 Feb 2020 23:45:04 +0100 Subject: Added ft_list_sort.s --- Makefile | 6 +-- ft_list_size.s | 2 +- ft_list_sort.s | 149 ++++++++++++++++++++++++++++++--------------------------- main.c | 130 ++++++++++++++++++++++++++++++++++++++++++++++++- 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 +#+ +:+ +#+ # # +#+#+#+#+#+ +#+ # # 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 +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* 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; } -- cgit