segmentation fault / linked list

• LinkedList.h

1     #ifndef __LINKED_LIST_H_
2     #define __LINKED_LIST_H_
3
4     #define TRUE    1
5     #define FALSE    0
6
7     #define DUMMY_DATA    -1374165384
8
9     typedef int Data;
10
11   typedef struct _node {
12       Data data;
13       struct _node* next;
14   } Node;
15
16   typedef struct _linked_list {
17       Node* head;
18       Node* cur;
19       Node* before;
20       int size;
21       int (*comp)(Data data1, Data data2);
22   } LinkedList;
23
24   typedef LinkedList List;
25
26   void listInit(List* list);
27
28   int listFirst(List* list, Data* data);
29   int listNext(List* list, Data* data);
30
31   void listAdd(List* list, Data data);
32   Data listRemove(List* list);
33   Data listGet(List* list);
34
35   int listSize(List* list);
36
37   void setSortRule(List* list, int (*comp)(Data data1, Data data2));
38
39   #endif

---

2. LinkedList.c

1     #include <stdio.h>
2     #include <stdlib.h>
3     #include "LinkedList.h"
4
5     void listInit(List* list) {
6         Node* dummy = (Node*)malloc(sizeof(Node));
7         dummy->next = NULL;
8         list->head = dummy;
9         list->before = dummy;
10       list->cur = dummy;
11       list->size = 0;
12       list->comp = NULL;
13   }
14
15   int listFirst(List* list, Data* data) {
16       if (list->size == 0) { return FALSE; }
17
18       list->cur = list->head->next;
19       list->before = list->head;
20       *data = list->cur->data;
21
22      return TRUE;
23   }
24
25   Data listNext(List* list, Data* data) {
26       if (list->size == 0 || list->cur->next == NULL) { return FALSE; }
27
28      list->before = list->cur;
29       list->cur = list->cur->next;
30      *data = list->cur->data;
31
32      return TRUE;
33   }
34
35   void listAddFirst(List* list, Data data);
36   void listAddBySortRule(List* list, Data data);
37   void listAddAt(List* list, Data data, Node* frontLandmark, Node* backLandmark);
38
39   void listAdd(List* list, Data data) {
40       if (list->comp == NULL) {
41          listAddFirst(list, data);
42      } else {
43           listAddBySortRule(list, data);
44       }
45
46      list->size++;
47   }
48
49   void listAddFirst(List* list, Data data) {
50       listAddAt(list, data, list->head, list->head->next);
51   }
52
53   void listAddBySortRule(List* list, Data data) {
54       Node* currentNode = list->head->next;
55       Node* before = list->head;
56
57       if (currentNode == NULL) { listAddFirst(list, data); return; }
58
59       while (currentNode != NULL || list->comp(data, currentNode->data) != FALSE) {
60           before = currentNode;
61           currentNode = currentNode->next;
62       }
63
64       listAddAt(list, data, before, currentNode);
65   }
66
67   void listAddAt(List* list, Data data, Node* beforeNode, Node* nextNode) {
68       Node* newNode = (Node*)malloc(sizeof(Node));
69       newNode->data = data;
70       newNode->next = beforeNode;
71       nextNode->next = newNode;
72   }
73
74   Data listRemove(List* list) {
75       Node* removedNode = list->cur;
76       Data dataOfRemovedNode = removedNode->data;
77
78        list->before->next = removedNode->next;
79       list->cur = list->before;
80
81       free(removedNode);
82       list->size--;
83
84       return dataOfRemovedNode;
85   }
86
87   Data listGet(List* list) {
88       Data curData = list->cur->data;
89
90       return curData;
91   }
92
93   int listSize(List* list) { return list->size; }
94
95   void setSortRule(List* list, int (*comp)(Data data1, Data data2)) {
96       list->comp = comp;
97   }

---

• main.c

1     #include <stdio.h>
2     #include "LinkedList.h"
3
4     int compare(Data d1, Data d2) {
5         if (d1 > d2) {
6             return TRUE;
7         } else {
8             return FALSE;
9         }
10   }
11
12   int main() {
13       List llist;
14       List* list = &llist;
15   
16       listInit(list);
17
18       setSortRule(list, compare);
19
20       listAdd(list, 13); listAdd(list, 15); listAdd(list, 9);
21       listAdd(list, 221); listAdd(list, 90); listAdd(list, 11);
22
23       int data;
24       if (listFirst(list, &data)) {
25           printf("%d\n", data);
26
27           while (listNext(list, &data)) {
28               printf("%d\n", data);
29           }
30      }
31
32       listFirst(list, &data);
33       listNext(list, &data);
34       listNext(list, &data);
35       listNext(list, &data);
36
37       int removedData = listRemove(list);
38
39       printf("RemovedData: %d\n", removedData);
40
41       if (listFirst(list, &data)) {
42           printf("%d\n", data);
43
44          while (listNext(list, &data)) {
45             printf("%d\n", data);
46          }
47       }
48
49       return 0;
50   }

위 코드를 돌릴 경우, 세그먼테이션 오류 (core dumped)라는 메시지가 나타난다.

그런데 main 함수 내

setSortRule(list, compare);

을 주석처리하면 오류가 발생하지 않는다.

즉, void listAddBySortRule(List* list, Data data) 함수에서 세그먼테이션 오류가 발생하는 것이다.

https://ko.wikipedia.org/wiki/%EC%84%B8%EA%B7%B8%EB%A9%98%ED%85%8C%EC%9D%B4%EC%85%98_%EC%98%A4%EB%A5%98

ko.wikipedia.org
위키피디아 세그먼테이션 오류 페이지

그러나 위의 글만 읽고는 앞서 제시된 코드를 실행하면 세그먼테이션 오류가 발생하는 원인을 알 수 없다.

우선 void listAddBySortRule(List* list, Data data) 함수 내부의 코드들을 모두 주석처리해 보았다.

실행 결과, 세그먼테이션 오류가 발생했다.

LinkedList.c에서 59~64행, main.c에서 23~47행을 주석처리하여 실행해 보았다.

실행 결과, 세그먼테이션 오류가 발생했다.

LinkedList.c 57행에서 listAddFirst(list, data) 함수 호출 시 오류가 발생한 것이다.

그런데 void listAddAt(List* list, Data data, Node* beforeNode, Node* nextNode) 함수가 이상하다.

세 번째, 네 번째 파라미터의 이름을 변경할 때 실수가 발생했다.

void listAddAt(List* list, Data data, Node* beforeNode, Node* nextNode) {

    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = nextNode;
    beforeNode->next = newNode;

}

이와 같이 변경하니 listAddFirst 함수는 오류 없이 호출된다.

main.c의 18행, setSortRule(list, compare); 를 주석처리 한 경우 실행 결과

11
90
221
9
15
13
RemovedData: 9
11
90
221
15
13

즉, 세그먼테이션 오류 (core dump)는 java의 NullPointerException과 같은 조건에서 발생한다고 볼 수 있다.

Node* nextNode 변수에 NULL 값이 들어 있는데 nextNode->next와 같은 식의 참조를 시도하려고 하니 세그먼테이션 오류가 발생한 것이다.

LinkedList.c 의 59행을 보면 while문 조건이 currentNode != NULL || list->comp(data, currentNode->data) != FALSE 라고 돼 있는데, 코드 작성자가 착각하여 AND 연산을 해야 할 부분을 OR 연산을 한 부분이다.

1. currentNode 가 NULL 값이 아니다

2. list->comp 함수포인터가 가리키는 함수의 리턴 값이 FALSE 가 아니다.

OR 연산의 경우 A || B 가 있다고 가정할 때, A가 true면 조건문을 탈출하여 B가 실행되지 않지만, A가 false면 B가 실행된다. 이 사실을 currentNode != NULL || list->comp(data, currentNode->data) != FALSE 에 대입해 보자.

currentNode != NULL 이 false라는 것은 currentNode에 NULL 값이 저장돼 있다는 것이다. 이 상태에서 currentNode != NULL가 false이기 때문에 list->comp(data, currentNode->data) != FALSE 가 실행되는데, 이때 currentNode는 NULL 값이기 때문에 currentNode->data 는 올바르지 않은 접근이다.

LinkedList.c 59행을 다음과 같이 변경했다.

currentNode != NULL && list->comp(data, currentNode->data) != FALSE

OR 연산을 AND 연산으로 바꿨다. 변경사항은 그뿐이다.

그리고 코드를 실행했다. 더 이상 세그먼테이션 오류가 발생하지 않았다. 실행 결과는 다음과 같다.

9
11
13
15
90
221
RemovedData: 15
9
11
13
90
221

데이터가 List에 정렬되어 저장됐다.

'세그먼테이션 오류 (core dump)'의 발생 원인으로 위키피디아에 기술된 바는 다음과 같다.

"세그멘테이션 오류는 프로그램이 허용되지 않은 메모리 영역에 접근을 시도하거나, 허용되지 않은 방법으로 메모리 영역에 접근을 시도할 경우 발생한다. (예를 들어, 읽기 전용 영역에 어떤 내용을 쓰려고 시도하거나, 운영 체제에서 사용하는 영역에 다른 내용을 덮어쓰려 하는 경우)"

그리고 NULL 값이 저장된 구조체 포인터 변수로 구조체 멤버를 참조하려 할 경우 세그먼테이션 오류가 발생했다. 이 경우 세그먼테이션 오류 발생 원인은 Java에서 NullPointerException이 발생하는 원인과 같다. NULL 값이 저장된 포인터 변수로 그 포인터 변수가 가리키는 주소(NULL 값이 저장됐다는 것을 인지하지 못하고 해당 포인터 변수에 특정한 주소 값이 저장됐다고 믿는 프로그래머가 생각하는 주소)에 저장된 데이터를 참조하려 한다면, 이는 허용되지 않은 방법으로 메모리 영역에 접근을 시도한 것이다. 그렇기 때문에 세그먼테이션 오류가 발생한 것이다.

물론 세그먼테이션 오류 == NullPointerException 이라고 말할 순 없다. 세그먼테이션 오류가 상기된 상황에서만 발생하는 것이 아니라 다른 여러 경우에도 발생하는 것이고, 또한 세그먼테이션 오류의 원인을 본질적으로 해명하려면 메모리 구조에 대한 논의가 필요하다. (세그먼트)

다만 세그먼테이션 오류의 발생이 NullPointerException과 동일한 조건에서도 발생한다는 점을 알면 코드 오류 수정에 큰 도움이 될 것이다.