2022.04.18. push_swap - 정렬부 구현-3, a_stack 오름차순 정렬하기-1

지난 포스팅에서 pop_front 함수에서 lldb 디버거로 문제가 있음을 확인 했다. 28번째 줄에서 stack이 비어있을 경우에 stack이 비어있는데 head에 접근하려고 해서 생기는 sigfault라고 판단하고, stach에 head가 존재할 경우에만 작동하게 설정했다.

그 후 다시 컴파일 및 디버깅을 해보니,

이번엔 push_front 함수에서 문제가 발생함을 확인했다.

new_top에 NULL이 들어올 일이 없게끔 설계 했다고 생각했기 때문에 NULL 노드가 들어올 경우를 처리하지 않았는데, 그게 문제가 된것 같다. 17, 18줄을 추가했다.

그 후 다시 컴파일 하니 이번엔 push_back 함수이다.

push_front와 동일하게 32,33 줄을 추가했다.

 

이렇게 push/pop 관련 3개의 함수에 null인 new_node관련 처리를 해주었더니,

a_stack을 오름차순 정렬하는 함수인 sort_a_stack에서 sigfault가 발생했다. 그래도 이전보다 출력결과가 더 나와서 금방 원인을 알 수 있을 것 같다. k와 i 인덱스가 middle 값을 제일 앞으로 가져온 이후에 제대로 작동(증가)하지 않음을 알 수 있었다. -93 라고 출력된 부분이 원인음을 직관할 수 있었는데, sort_a_stack에 이런 출력문을 호출했기 때문이었는데, 위의 출력 결과를 낼 당시에는  "1 : " 뒤에는 인덱스 들의 합인 k +  i를 출력하게끔했었어서 2라고 나왔는데, 아래 89번째 line처럼 수정해서 돌려본 결과, 

위와 같은 결과를 얻게 되었다. stack -> count값에 문제가 있었다. 첫번째 middle값(a_stack내 최소값인 6)을 a_stack의 top으로 가져올 때는 잘 작동했었는데, "1. 정렬 도중에 count 값에 접근해서 변경한 적이 있는지", "2. stack의 주소가 올바르게 전달되었는지"를 살펴봐야겠다.

sort_a_stack에서 printf문 호출로 확인해 본 결과, n_times_pstack() 호출 이후 count 문에 문제가 생긴 것을 확인했다.

n_times_pstack()함수 내에 printf문을 호출해서 count를 봤더니

i가 의도한 값보다 커서 count가 과하게 감소 된것을 확인 할 수 있었다.

확인 결과,

sort_a_sort 함수 내에서 n_times_pstack 호출문

n_times_pstack 함수의 프로토타입(함수 선언부)

알고 보니 char 변수와 i 변수의 자리가 잘못들어가서 생긴 일이었다. 특히 char 형은 내부적으로는 ascii 코드인 Int형으로 다루어지므로 int형과 char 형이 서로 뒤바뀌어 넣어도 컴파일러에서 waring이나 error를 발생하지 않으므로 더욱 주의 해야겠다. 함수 호출 시 변수의 자리를 올바르게 수정하고 나서 다시 컴파일 해봤더니,  count가 음수여서 문제가 발생했던 부분에서 다시 프로세스가 멈춘것이 확인되었다. 

a_stack에서 첫번째 middle 값인 6이 a_stack의 top에 정렬되어있었다. 그러나, 정렬이후 +1 증가한 7로 변경했었어야했는데, 동일하게 middle이 될때까지 curr 노드를 이동 시켰으니, (k는 +1 되었다) a_stack의 입장에서는 9(index=7)부터 쭉 찾았는데도 middle에 도달하지 못했고, a_stack이 끝나버려 sigfault 가 발생한것이었다. 

middle을 수정 한 후 lldb를 실행하자,

동일한 부분에서 다시 프로세스가 중단되었고, curr->index 값이 현재 8이라는 것을 발견했다.

확인해 본 결과, unsorted의 초기 선언시 Index가 8인 노드를 가리키고 있었는데,(t_node *unsoted = a_stack->head;)

sort_a_stack이 파라미터로 넘겨받은 a_stack과 b_stack의 content와 [index]

a_stack의 최솟값인 6을 맨 앞으로 정렬한 후의 a_stack

unsorted가 index 7을 가리키기를 바라며 unsorted = unsorted->next로 했더니, 할당하는 시점에 inex 8을 가진 노드의 다음 노드였던 index 12값을 가진 노드가 unsorted로 지정이되었고, 해당 index 뒤에는 찾는 값(7)을 가진 노드가 없어서 sigfault가 발생한 것이었다.

이를 해결하기 위해서 직관적으로 딱 생각난 방법은 unsorted의 자료형을 바꾸는 것이었다. t_node가 아닌 t_stack으로, 연결 리스트를 가리킬수 있는 t_stack 포인터로서 선언하고, 한 노드씩(?) 다음으로 넘기려 했는데, 바로 이 방법이 잘못되었다는 것을 깨달았다. a_stack에는 next가 없기 때문이었다. 그래서 다시 t_node로 자료형을 바꾸고 while 문의 끝(103 line)에서 unsorted 값의 할당하는 방법을 바꾸었다.

 

의도한대로 unsorted node를 쓰기 위해서는 t_node *로서 정의하고, while문의 끝에서 매번 unsorted를 a_stack의 top을 가리키게 했다가 k만큼(k++를 한 다음에 while문을 돌리기 때문) unsorted의 다음 노드로 옮겨 주는 식으로 수정했다. unsorted 된 부분의 top을 알기위해서 선언해야하는 변수도 생겼고 관련 부분이 너무 길어졌으니, 후에 리팩토링 하면서 unsoted 된 노드의 top을 반환하는 함수로 따로 정의하는게 좋겠다.

다시 동일한 부분에서 index 접근에 문제가 생겼다. 최종적으로 남은 stack도 보니 정렬이 도중에 잘 되지 않았다. middle 값이 9일 때를 건너 뛴것 같아보이는데 확인이 필요하다. 현재 쓰고 있는 CLI 환경에서는 scroll up 기능이 지원되지 않아서, mac 기본 terminal로 환경을 잠시 옮겨서 확인해 보려 한다.( => terminal 환경에서 컴파일 및 디버깅 시엔 같은 input 값에 대해 sigfault가 발생하지 않았다. 컴파일러의 차이가 있을 것 같으니, 클러스터 환경에서도 한번 컴파일 및 디버깅 해보는 것이 좋을 것 같다.)

정렬의 최종 결과

printf문 호출로 확인 결과, k, i index 및 middle 값의 증가는 의도한 대로 이루어 졌으나, 정렬 알고리즘에 문제가 있어서 정상적으로 정렬이 되지 않은것으로 보였다.