2021 05 31(월)

20210531(월)

1. 학습 날짜 : 20210531(월)

2. 학습 시간 : 12:40 ~

3. 학습 주제 : push_swap

4. 동료 학습 방법 : 개인..?

5. 학습 목표 :

push_swap 코드 완성

​ 작동 할 지 안할지는 모름, 프로그램의 완성 후, 작동되나 봐야함.

​ 작동하지 않는다면...? 멘탈 관리하고 사람들한테 물어보던가, 코드를 참고하던가...

• sort_a_less_n_equal_3
• 아래 함수들 검증, 고쳐보기
• void sort_a_132(t_ll **ab_array) void sort_a_321(t_ll **ab_array) void sort_a_312(t_ll **ab_array) void sort_a_213(t_ll **ab_array) void sort_a_231(t_ll **ab_array)
• 아래 함수들의 작성, 검증
• void sort_b_(t_ll **ab_array) void sort_b_(t_ll **ab_array) void sort_b_(t_ll **ab_array) void sort_b_(t_ll **ab_array) void sort_b_(t_ll **ab_array)
• sorting 함수 전체의 검증
  • sort_a
  • sort_b
• 검증이 끝나면, 프로그램 돌려보기
  • 돌아간다면, 에러잡기
  • 안돌아간다면, 멘탈잡고 타인의 코드를 돌아보던지, 물어보던지... 해서 화요일 안에 끝낼 수 있도록 해보기.

6. 학습 내용 :

sort 함수들의 검증이 끝난 후, 프로그램의 실행 시에 sort_a()에서 문제가 발생했다.

==93893==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000010 (pc 0x00010a1a5593 bp 0x7ffee5a5e590 sp 0x7ffee5a5e4a0 T0)
==93893==The signal is caused by a WRITE memory access.
==93893==Hint: address points to the zero page.
    #0 0x10a1a5593 in linked_list_push linked_list.c:66
    #1 0x10a1a6eaf in push_ab inst.c:26
    #2 0x10a1a9046 in sort_a sort_a.c:74
    #3 0x10a1a63be in main main.c:37
    #4 0x7fff6cb2ecc8 in start+0x0 (libdyld.dylib:x86_64+0x1acc8)

문제를 보면, linked_list_push 에서 문제가 발생한 것으로 보인다.

1. 연결리스트 함수를 제대로 짜지 못했거나,
2. push_ab를 제대로 하지 못했거나 둘 중 하나의 가능성이 있는데

아마 연결리스트 자료구조를 제대로 짜지 못한 것으로 보인다.

고쳐야 할 리스트 함수 목록:

int        init_linked_list(t_ll ***ab_arr)
int        linked_list_push(t_ll **ab_arr, int    num_stack, int data
int        linked_list_pop(t_ll **ab_arr, int num_stack, int *data)

int        linked_list_push(t_ll **ab_arr, int    num_stack, int data)
{
    t_node    *new_node;
    t_ll    *l_list;

    l_list = ab_arr[num_stack];
    new_node = (t_node *)malloc(sizeof(t_node));
    if (!new_node)
        return (ft_print_error());
        //malloc 에러 시 t_ll, 안의 모든 노드들 삭제하고 프로그램 종료.
    new_node->data = data;
    if (l_list->size == 0)
        l_list->head = new_node;
    else
    {
        l_list->tail->next = new_node;
        l_list->head->prev = new_node;
    }
    new_node->next = l_list->head;
    new_node->prev = l_list->tail;
    l_list->tail = new_node;
    l_list->size++;
    return (1);
}

    if (l_list->size == 0)
        l_list->head = new_node;
    new_node->next = l_list->head;
    new_node->prev = l_list->tail;    //문제 발생 구간
        l_list->tail = new_node;    //문제 발생 구간
    l_list->size++;
return (1);

이 경우에 문제가 발생할 것으로 보인다.

해당 문제 발생 구간을 수정한 뒤 잘 돌아갔다.

//TYPORA

수정했음.

연결리스트 자료구조의. 수정

sort_a 함수에서 발생하는 문제

traverse_list_A
3    2    1    8
traverse_list_B
4    5    6    7
sort_num : 1

traverse_list_A                    ## 8이 B로 넘어가야하는 상황임에도 A에서 rotate되는 상황. 이 역시 연결리스트의 문제일 수 있음.
8    3    2    1
traverse_list_B
4    5    6    7
sort_num : 0

문제 해결 : 노드의 시작을 node->head에서 시작했기 때문에, push() 하고자 하는 원소와 반대 원소가 push() 된 상황.
노드의 시작을 node->tail 로 바꾸어주어 마치 스택의 _top_을 조작해주듯이 바꾸어주었다.

SEGFAULT

STACK_A :        8    7    6    5    4    3    2    1    9
STACK_B :        empty stack
SORT_A
REV_AB
STACK_A :        7    6    5    4    3    2    1    9    8
STACK_B :        empty stack
REV_AB
STACK_A :        6    5    4    3    2    1    9    8
STACK_B :        7
REV_AB
STACK_A :        5    4    3    2    1    9    8
STACK_B :        7    6
REV_AB
STACK_A :        4    3    2    1    9    8
STACK_B :        7    6    5
STACK_A :        3    2    1    9    8
STACK_B :        4    7    6    5
STACK_A :        2    1    9    8
STACK_B :        3    4    7    6    5
STACK_A :        1    9    8
STACK_B :        2    3    4    7    6    5
STACK_A :        9    8
STACK_B :        1    2    3    4    7    6    5
REV_AB
STACK_A :        8    9
STACK_B :        1    2    3    4    7    6    5
RREV_AB
RREV_AB
RREV_AB
RREV_AB
RREV_AB
STACK_A :        8    9
STACK_B :        7    6    5    1    2    3    4
SORT_A
SORT_NUM < = 3
SORT_A_LESS_N_EQUAL_3
sort_num == 2
STACK_A :        8    9
STACK_B :        7    6    5    1    2    3    4
SORT_B
SORT_B_LESS_N_EQUAL_3
STACK_A :        5    6    7    8    9
STACK_B :        1    2    3    4
SORT_B
REV_AB
STACK_A :        5    6    7    8    9
STACK_B :        2    3    4    1
REV_AB
STACK_A :        5    6    7    8    9
STACK_B :        3    4    1    2
REV_AB
STACK_A :        5    6    7    8    9    3
STACK_B :        4    1    2

SEGFAULT

#에러 로그 : 
==11806==ERROR: AddressSanitizer: heap-use-after-free on address 0x6030000019f8 at pc 0x00010edf33ee bp 0x7ffee0e15450 sp 0x7ffee0e15448
READ of size 8 at 0x6030000019f8 thread T0
    #0 0x10edf33ed in sort_b sort_b.c:87
    #1 0x10edf1a1f in sort_a sort_a.c:99
    #2 0x10edee561 in main main.c:41
    #3 0x7fff71859cc8 in start+0x0 (libdyld.dylib:x86_64+0x1acc8)

0x6030000019f8 is located 8 bytes inside of 24-byte region [0x6030000019f0,0x603000001a08)
freed by thread T0 here:
    #0 0x10ee502c6 in wrap_free+0xa6 (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x492c6)
    #1 0x10edee0a7 in linked_list_pop linked_list.c:101
    #2 0x10edef023 in push_ab inst.c:25
    #3 0x10edf31f5 in sort_b sort_b.c:78
    #4 0x10edf1a1f in sort_a sort_a.c:99
    #5 0x10edee561 in main main.c:41
    #6 0x7fff71859cc8 in start+0x0 (libdyld.dylib:x86_64+0x1acc8)

previously allocated by thread T0 here:
    #0 0x10ee5017d in wrap_malloc+0x9d (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x4917d)
    #1 0x10eded4e4 in linked_list_push linked_list.c:57
    #2 0x10edef08f in push_ab inst.c:26
    #3 0x10edf14af in sort_a sort_a.c:80
    #4 0x10edee561 in main main.c:41
    #5 0x7fff71859cc8 in start+0x0 (libdyld.dylib:x86_64+0x1acc8)

SUMMARY: AddressSanitizer: heap-use-after-free sort_b.c:87 in sort_b

int        **sort_b(t_ll **ab_array, int **piv_arr, int sort_num)
{
    t_freq    freq;
    t_node    *node;
    int        **piv_arr_cpy;
    int        node_data;

    printf("SORT_B\n");
    if (sort_num <= 3)
    {
        sort_b_less_n_equal_3(ab_array, sort_num); 
        return (piv_arr - 1);
    }
    init_freq(&freq);
    node = ab_array[STACK_B]->tail;                            
    while (sort_num-- > 0)
    {
        node_data = node->data;
        printf("B Node_Data %d\n", node->data);
        if ((*piv_arr)[0] >= node_data)
        {
            rev_ab(ab_array, STACK_B);
            freq.rotate_this++;
        }
        else
        {
            push_ab(ab_array, STACK_A);
            freq.push_opp++;
            if ((*piv_arr)[1] >= node_data)
            {
                rev_ab(ab_array, STACK_A);
                freq.rotate_opp++;
            }
        }
        traverse_ab(ab_array);
        node = ab_array[STACK_B]->tail;            //이 부분에서 문제가 생겼다. 
    }

문제 해결 :

        traverse_ab(ab_array);        node = ab_array[STACK_B]->tail;            //이 부분에서 문제가 생겼다.     }

문제가 생긴 부분은 위의 node = ab_array[STACK_B]->tail; 부분으로,

원래는 node = node->prev; 였다. 문제가 생긴 이유는, Doubly - Circular LinkedList 로 이루어진 연결리스트의 node가 push/pop과정을 거치면서 노드가 삭제되는데,

이 때, 삭제된 노드를 참조하려다 보니까 (node->prev) heap-use-after-free on address 에러가 생겼다.

적절하게 push/pop() 으로 재구성된 연결리스트의 Tail/Top을 참조하고 할당하도록 고쳐주었다.

인자가 11개 이상 들어오면 에러가 나는 문제

./push_swap 1 2 3 4 5 6 7 8 9 10 11 : 과 같이 인자가 11개 이상 들어왔을 경우 segmentation fault가 난다.

문제 분석 : pivot_array 가 4 7 2 3 9 10와 같이, 본 sort 함수에서 사용되는 pivot의 순서와 달라서 문제가 생긴 듯 하다.

원래대로라면, pivot_array 안의 pivot의 순서가, 4,7 9,10 2,3 의 순서로 되어있어야 하지만 4 7 2 3 9 10 과 같은 순서로 할당이 되어있다.

pivot_array를 만들고, 할당 할 때 생기는 문제를 해결하면 segfault를 해결할 수 있지 않을까.

지금 생각난건데, pivot_array를 만들고 값을 sort의 순서에 따라 할당할 때, 현재 pivot_array를 구현한 방법으로는 pivot_array안의 pivot의 사용순서와 sorting의 pivot사용 순서가 적절히 대응되지 못할 것 같다.

이를 해결하기 위해서는, pivot_array를 만들 때, 완전히 sorting의 순서를 모방해야하지 않나...

원래대로 pivot이 사용되는 순서는 다음과 같다. ./push_swap 의 인자가 1, 2, 3, ...., 29, 30 과 같이 들어왔을 때, (11,21), (23, 24), (15, 18), (13, 14), (4, 7), (9, 10), (2, 3) 의 순서로 사용이 되어야한다.

현재 프로그램의 pivot_array의 pivot순서는 위와 완전히 다르다.

따라서, pivot_array의 pivot 순서를 수정해야하고, 그러기 위해서는 pivot_array에 값을 할당할 때, sort_a 와 sort_b 를 모방해야한다.

)

sequence of numbers를 자르는데 있어 문제

위와 같이 22~30 수준에서 pivot을 뽑아내려다 보면, 균등하게 나눠지지 않는다. 22 ~ 25, 26 ~ 28, 29 ~ 30으로, 각각 4개, 3개, 2개다.

명령어의 개수가 균등하게 나누었을 때보다 증가할지, 감소할지는 모르지만,

추후 명령어의 개수에 문제가 생겼을 경우, 이 부분에서 최적화가 필요할 것 같아 적는다.

---

pivot_array를 수정하고 다시 잡아야한다.

학습에 도움된 사이트 :

오늘 발견한 문제와 해결방안:

• 상기에 적었으며, 설계는괜찮았으나, 구현부에서 예상 외로 에러를 많이 띄웠고, 디버깅하는데 시간을 많이 잡아먹었다.

고쳐야 할 점

1. 연결리스트 함수를 제대로 짜지 못했기 때문에 에러가 발생했고, 에러 발생 지점을 체크하는데 약 2시간 가량 걸렸다.자료구조에 대한 이해
2. 구현 알고리즘에 대한 피드백
3. 자료구조에 대한 이해와 구현에 어려움이 있었기 때문에 발생한 문제라고 생각한다.

2. sort_a 함수에서 발생하는 문제 : 구현부에서 실수가 있었으며, 디버깅하는데 약 2시간 가량 소요되었다.
   설계단에서 문제가 있었고, 따라서 설계할 때 심혈을 기울여야 한다.
   만약, 설계단에서 문제를 잡지 못했다면, 함수를 한번 더 훑으며 검증하는 과정이 필요해보인다.
3. 설계할 때 심혈을 기울여야 한다 /
4. 설계단에서 문제를 잡지 못했다면, 함수를 한번 더 훑으며 검증하는 과정이 필요해보인다.

3. SEGFAULT : 2와 동일.

4. 프로그램 기한 :문제는, 분할정복 알고리즘에 대한 이해가 없었고, 알고리즘에 익숙치 않기 때문에
   타인의 알고리즘 설명을 보고, 듣는데 약 3~4일 가량을 소요했다.알고리즘에 대한 이해가 많이 필요해보인다.
5. 알고리즘
6. 근본적인 원인은 알고리즘의 구현부를 생각하지 못했기 때문이라고 생각한다.
7. 프로그램 기한을 일주일로 잡았으나, 프로그램에 문제가 없다면 약 하루~이틀가량 더 소요될 것으로 보인다.

7. 학습 총평 :

• 내일 끝내야하는데 기한 내로 못끝낸게 좀 아쉽다...

8. 다음 학습 계획 :

• push_swap : pivot_array고치기
• 아마 pivot_array를 고치면 전체적으로 작동은 잘 할것으로 예상되나,
• 명령어의 사용 개수를 고려하여 프로그램을 최적화해야하지 않을까 싶다...