자료구조

struct Table의 멤버는 size다. destroy()는 zsize를 읽는다. 오타 하나지만 결과는 절대적이다 — 이 파일은 어떤 C 컴파일러로도 빌드되지 않는다. 즉 저자는 이 소스를 마지막으로 고친 뒤 단 한 번도 빌드하지 않고 커밋했다. 커밋 메시지가 Update struct type C89인 것으로 보아 구조체 선언을 손보다가 멤버명을 건드렸고, 그대로 push한 것으로 보인다.

zsize를 size로 고쳐 컴파일되게 만들어도 destroy()는 각 버킷의 헤드 센티널 하나만 해제한다. insert()가 list->next에 이어붙인 실제 데이터 노드는 한 개도 해제되지 않는다. 분리 연쇄법 해시 테이블에서 해제해야 할 것의 대부분이 곧 체인인데, 그 체인을 순회하는 루프가 아예 없다.

같은 함수 안에 버킷 배열 할당 버그도 있다. t->lists는 node*(포인터 배열)인데 sizeof(struct Node)로 크기를 잡았다 — 64비트에서 포인터당 8바이트면 되는 자리에 16바이트씩 잡는다. 크래시는 안 나지만 타입을 이해하지 못한 채 쓴 sizeof다.

oper(e, pop(number), pop(number))는 C 표준에서 인자 평가 순서가 미지정(unspecified)이다. 두 pop 중 어느 쪽이 먼저 실행될지 컴파일러가 정한다. clang에서 실행한 결과 first에 스택 최상단(= 후위식의 오른쪽 피연산자)이 들어가, 프로그램은 right OP left를 계산한다. -, /, %처럼 교환법칙이 성립하지 않는 연산자 전부가 반대로 계산된다.

저자의 gcc 5.2.1에서는 반대 순서로 평가되어 우연히 맞는 답이 나왔을 수도 있다. 그것이 더 나쁘다 — 컴파일러가 버그를 가려준 것이지 코드가 맞은 게 아니기 때문이다.

변환된 후위식 4736%+*42/-9+23*-는 정확하다. 즉 Lab04 과제의 절반(중위→후위 변환)은 제대로 구현했고, 나머지 절반(평가)만 틀렸다. 그런데 출력 한 줄만 검산했으면 즉시 드러났을 오류다.

토크나이저가 >= 대신 >를 썼다. '0'은 조건을 통과하지 못하고 else의 switch로 떨어지는데 거기에도 case '0'이 없다. 결과적으로 입력에서 조용히 사라진다.

루프가 tmp를 한 칸 뒤처져 따라가며 해제하는데, 종료 시점에 tmp는 마지막 실제 노드를 가리키고 ptr은 NULL이다. 그리고 루프 밖에서 해제하는 것은 tmp가 아니라 ptr — 즉 free(NULL)이다. 저자가 꼬리 노드를 해제하려 한 의도는 명확하지만 변수를 잘못 골랐다. 호출할 때마다 노드 하나씩 누수된다.

여기에 더해 calc()가 내부에 만드는 number 리스트는 어디에서도 해제되지 않는다.

back()(:58)과 pop_back()(:74)은 정의만 되고 호출되지 않는다. 둘 다 빈 리스트에서 널 역참조하는 버그를 품고 있으나 호출되지 않아 드러나지 않는다. getOper()(:10–26)는 switch의 모든 case를 벗어나면 반환값 없이 함수를 이탈한다 — -Wreturn-type이 잡는다. main의 op(:164), calc의 first/second(:105)는 선언만 되고 쓰이지 않는다.

main은 읽은 문자가 13(캐리지 리턴)일 때 삭제 모드로 전환한다. 그런데 함께 커밋된 lab10/input은 LF(0x0a)로 개행된 순수 Unix 텍스트다 — 파일 어디에도 0x0d가 없다. README는 "compile@Linux Ubuntu Gnome 15.10"이라고 적혀 있으니, 저자가 명시한 바로 그 환경에서도 이 조건은 영원히 거짓이다.

결과: 두 번째 줄의 21 3 5 11 23은 삭제 대상이 아니라 추가 삽입된다. 삭제 단계 진입을 알리는 printf("start delete\n")는 출력에 나타나지 않는다.

루프가 fscanf의 반환값 chk를 검사하기 전에 insertNode를 호출한다. EOF에 도달하면 두 fscanf가 모두 실패하고 ch는 직전 값을 그대로 유지하는데, 그 값이 다시 삽입된 뒤에야 루프 조건이 평가된다.

이 버그는 입력 파일이 개행으로 끝나느냐에 따라 나타났다 사라진다. lab09/input은 개행 없이 끝나 Lab09에서는 증상이 없고, lab10/input은 개행으로 끝나 증상이 나타난다. Lab08·Lab09는 if (chk < 0) break;를 작업 앞에 두는 올바른 패턴을 쓴다. Lab10에서 오히려 퇴행했다.

lab10/p10-test.c는 p10.c와 아무 관계가 없는 완전히 독립적인 R-B 트리 구현이다. 전역 root, struct rbNode { int data, color; struct rbNode *link[2]; }의 배열형 자식 포인터, stack[98]/dir[98] 고정 배열을 쓴 반복적 삽입, 그리고 ASCII 아트로 회전을 그려 놓은 /* */ 주석 스타일 — 이 네 가지 특징은 레포의 나머지 22개 소스 어디에도 나타나지 않는다. 저자 본인의 코드는 일관되게 typedef한 포인터, left/right 명명, #if defined(_WIN32) && defined(_MSC_VER) 가드를 쓴다.

이 파일의 3행은 그 가드 없이 #pragma warning (disable :4996)를 노출한 채 시작한다 — 저자가 모든 파일에 붙이던 가드를 유독 여기만 빠뜨렸다. 외부에서 가져온 코드로 강하게 추정된다(단정은 하지 않는다 — 원출처를 확인하지 못했다). 어느 쪽이든 빌드에도, 보고서에도 쓰이지 않는 파일이 master에 남아 있다. Lab12에서는 같은 성격의 p12-test.c를 삭제하는 커밋(b294387)을 남겼으면서 이건 정리하지 않았다.

List는 struct Node *의 typedef다. 따라서 sizeof(List)는 포인터 크기(8바이트)이지 struct Node의 크기(16바이트)가 아니다. makeList()와 Create() 모두 이 값으로 malloc하므로, 리스트에 들어가는 모든 노드가 필요한 크기의 절반만 할당된다. next 필드(오프셋 8)에 쓰는 순간 힙 경계를 넘는다.

연결 리스트 과제에서 노드 할당 크기를 틀렸다는 것은, 자료구조의 가장 기본이 되는 한 줄이 틀렸다는 뜻이다. 32비트에서도 마찬가지로 절반만 잡힌다 — 우연히 맞을 플랫폼이 없다.

DelList()(:151–160)는 리스트 전체를 순회하며 해제하도록 올바르게 작성되어 있다. 그런데 main에서 호출하지 않는다. makeEmpty()(:102–106)는 더 나쁘다 — 파라미터 list에 새 할당을 대입하는데, C는 값 전달이므로 호출자에게는 아무 효과가 없고 원래 리스트만 유실된다. 정의만 되고 호출되지 않는 것이 오히려 다행인 함수다. isEmpty(), isLast()도 호출부가 없다.

입력 파싱도 취약하다. :46–48의 do–while은 fscanf의 반환값을 확인하지 않는다. 입력이 p로 끝나지 않으면 command가 갱신되지 않은 채 무한 루프에 들어간다. 커밋된 입력이 마침 p로 끝나서 드러나지 않을 뿐이다. :42의 fopen 결과도 NULL 검사가 없다 — 다른 랩들은 대부분 검사한다.

배열 기반 이진 힙을 1번 인덱스부터 쓰려면 capacity + 1칸이 필요하다(0번은 센티널). 여기서는 정확히 capacity칸만 잡는다. 동시에 isFull()은 size >= capacity로 판정하므로 capacity개까지 삽입을 허용한다. 마지막 삽입에서 i가 capacity가 되어 배열 바로 뒤에 쓴다.

같은 코드가 lab13/p13.c:184, :215에 복사되어 있다. 거기서는 그 힙을 아무도 호출하지 않아 터지지 않는다.

g->vertex는 list(포인터) size개를 담을 배열인데 sizeof(list), 즉 포인터 하나 분량만 할당한다. 바로 다음 줄의 루프가 size개를 채워 넣는다.

커밋 이력이 흥미롭다. b294387 "Crash Fix"(2016-05-26)에서 저자는 이 크래시를 만나 int mat[100][100]이라는 고정 인접 행렬을 구조체에 추가하는 것으로 우회했다. 원인인 malloc 크기는 손대지 않았고, 대신 정점 100개라는 하드코딩 상한과 graphAppend의 경계 검사 부재를 새로 들여왔다.

함수는 pGraph를 반환한다고 선언되어 있고, 내부에서 구조체를 할당해 초기화까지 한다. 그리고 그것을 반환하지 않는다. 호출자가 받는 값은 미정의다 — 실제로는 레지스터에 남은 쓰레기값이다. 그 쓰레기 포인터의 size 필드를 읽어 graph_realloc에 넘기고, malloc이 0xffffffffbcc60608바이트를 요구하며 죽는다.

-Wall이 정확히 이 줄을 짚는다. 경고를 한 번도 켜지 않았다는 증거다.

&&는 왼쪽부터 평가한다. 따라서 graph->vertex[now_index]->first->value를 먼저 읽고 그 다음에 now_index < graph->size를 확인한다. 찾는 정점이 없으면 배열 끝을 넘어 읽는다. 두 조건의 순서만 바꾸면 되는 문제다.

같은 함수에서 visited[now]는 배열 인덱스가 아니라 정점 값으로 접근한다(:220, :222). 정점 번호가 배열 크기 이상이면 그대로 경계 밖이다. graph_append_edge의 if (start > graph->size)(:207)도 값과 개수를 비교하는 같은 종류의 혼동이다. 그리고 graph_find_dfs_rec_util은 int를 반환한다면서 루프를 다 돌고 나면 반환 없이 끝난다(:232).

구조체에는 index 하나뿐이다. pop()은 0번을 꺼낸 뒤 나머지 전체를 앞으로 복사한다 — O(n)이다. 이건 원형 큐가 아니라 배열 기반 리스트다. 게다가 capacity만큼 채운 뒤 dequeue하면 뒤쪽 공간이 재사용되긴 하지만, 그것은 원형 인덱싱 덕분이 아니라 매번 전체를 시프트하기 때문이다. 과제가 가르치려던 개념이 구현에 하나도 없다.

그리고 ret는 빈 큐 검사보다 먼저 대입된다. 큐가 비어 있으면 초기화되지 않은 메모리를 읽는다 — 값은 버려지지만 읽기 자체가 일어난다.

lab05/input 16–21행에 해결되지 않은 Git 충돌 마커가 남아 있다. dfe0f97 "Update Directory" 커밋으로 들어왔고 2016년 이후 지금까지 master에 그대로 있다. 프로그램은 <, =, >, 16진 해시 문자를 명령으로 해석하지 못해 조용히 무시한다 — 그래서 아무도 눈치채지 못했다.

충돌을 해결하지 않고 커밋했다는 것 자체보다, 그 뒤로 이 파일로 프로그램을 한 번도 눈여겨 돌려보지 않았다는 사실이 더 문제다. 참고로 저자는 3e22981 "remove unmerged file"이라는 커밋도 남겼다 — 충돌 상황을 인지하고 있었지만 이 파일은 놓쳤다.

main은 Node를 하나 할당하는데 value, capacity, index 어느 것도 초기화하지 않는다. 입력의 n 5 명령이 init(5)로 덮어쓰면서 이 할당은 누수된다. 반대로 입력에 n이 없으면 모든 연산이 초기화되지 않은 capacity와 널 아닌 쓰레기 value 포인터를 쓰게 된다.

해제 함수 empty()(:72–76)와 출력 함수 view()(:64–71)는 정의만 되고 호출되지 않는다. init()의 malloc(sizeof(int) * cap + 1)(:14)은 연산자 우선순위상 int 한 칸이 아니라 1바이트를 더 잡는다 — 의도가 무엇이었든 그대로 이루어지지 않았다.

파서가 입력의 "첫 줄=정점 목록, 둘째 줄=간선 목록" 구조를 줄바꿈 바이트를 직접 비교해서 판별한다. __linux__도 _MSC_VER도 아닌 환경(macOS·BSD)에서는 LINE_CHAR가 13이 되고, LF로 끝나는 입력 파일에서 조건이 영원히 거짓이 된다. Lab12는 빈 줄 하나만 출력하고 끝나고, Lab13은 모든 토큰을 정점으로 오인해 비용이 전부 0 또는 INF인 쓰레기를 출력한다. lab15/p15_1.c, p15_2.c도 같은 매크로를 공유한다.

검증을 위해 #define LINE_CHAR 13을 10으로 바꾼 사본을 만들어 돌렸다. 그러자 두 과제 모두 정답을 냈다. 알고리즘은 맞았고 이식성만 틀린 것이다. 그러나 3분기 #if를 직접 작성해 놓고 마지막 분기를 검증하지 않은 것 자체가 결함이다 — 애초에 c == '\n' || c == '\r'이면 끝날 일이었다.

p13.c는 :173–251에 완전한 이진 최대 힙(heap_create, heap_push, heap_pop, heap_free, 약 80행)을 구현해 놓았다. 그런데 grep으로 확인한 결과 이 네 함수의 호출부가 파일 전체에 하나도 없다. dijkstra()는 pList heap = list_create(), 즉 평범한 연결 리스트를 쓰면서 변수 이름만 heap이다.

그래서 "최소 비용 정점 추출" 루프가 힙 연산이 아니다. 더 나쁜 것은 그 루프의 비교문이다. k는 파일 상단의 전역 int i, j, k; 중 하나로, main의 :375에서 마지막으로 읽은 간선 가중치가 들어 있다. 그 값으로 list_index(heap, k)를 계산해 인덱싱한다 — 의미 없는 비교다. 결국 최소값 선택이 성립하지 않는다.

그럼에도 정답이 나오는 이유는 :295의 list_push(heap, next)가 거리가 갱신될 때마다 정점을 다시 넣기 때문이다. 즉 이것은 Dijkstra가 아니라 큐 기반 반복 완화(Bellman–Ford/SPFA 계열)이고, 최악 복잡도는 O(E log V)가 아니라 O(V·E)다. 제출물이 Shortest Path라는 결과는 내지만, Dijkstra라는 자료구조 수업의 학습 목표는 달성하지 못했다.

graphFree()는 본문이 주석 처리된 free(g) 한 줄뿐인 빈 함수다. 호출은 되지만 아무것도 하지 않는다. 정점 리스트, 노드, 그래프 구조체 전부가 누수된다. p13.c의 dijkstra()가 할당하는 dist 배열(:268)도 해제되지 않는다.

부수적으로, 두 파일 모두 int i, j, k;를 전역으로 두고 서로 다른 함수에서 루프 카운터로 재사용한다. 지금은 중첩 호출이 없어 터지지 않지만, graphInit이 i를 쓰는 동안 i로 도는 루프에서 그것을 호출하면 즉시 무한 루프가 된다.

세 개의 off-by-one이 겹쳐 있다. merge_sort_merge는 last를 포함(inclusive) 인덱스로 쓰는데(n2 = last - mid, ary[mid+1..last]를 복사), merge_sort_iterative_util은 right를 배타적 끝으로 계산해 넘긴다. 게다가 호출부는 원소 개수 i가 아니라 i - 1을 넘기는데, 받는 쪽은 start < n으로 개수처럼 쓴다.

블록 크기가 커지면 mid가 last를 넘어서고 n2가 음수가 된다. malloc(sizeof(int) * -2)는 size_t로 승격되어 0xfffffffffffffff8이 된다 — ASan이 정확히 그 값을 보고한다.

두 함수가 같은 merge_sort_merge를 공유한다. 재귀판이 맞는다는 것은 병합 로직 자체는 옳고 반복판의 구간 계산만 틀렸다는 뜻이다. 그리고 두 결과를 나란히 출력해 놓고도 한쪽이 정렬되지 않았다는 것을 알아채지 못했다.

a ^= b ^= (a ^= b)는 하나의 시퀀스 포인트 사이에서 같은 객체를 여러 번 수정한다. C에서 미정의 동작이며, 컴파일러가 바꾸면 결과가 바뀔 수 있다. i == j일 때 원소를 0으로 만들어 버리는 성질도 있다(:185의 if (i != j) 가드 덕에 여기서는 피해 간다). 같은 관용구가 lab02/p2_1.c:78에도 있는데, 거기엔 그 가드가 없다 — i < j가 보장되어 우연히 안전할 뿐이다.

세 줄 임시변수 교환이 더 짧고 빠르고 정의된 동작이다. 이 관용구는 2016년 기준으로도 이미 20년 묵은 안티패턴이었다.

:182의 while (ary[j] > ary[pivot]) --j;는 j >= first를 확인하지 않는다. 지금은 ary[pivot] 자신이 자기보다 크지 않아 멈추지만, :188–189에서 pivot이 이동한 뒤에는 그 보장이 약해진다. :181의 while (ary[i] <= ary[pivot] && i < last)는 Lab14와 같은 "역참조 후 경계 검사" 순서다.

:253의 char input_string[100]에 :259의 fscanf(fp, "%s", input_string)로 읽는다 — 길이 제한이 없다. 100자 넘는 토큰이 들어오면 스택을 넘어 쓴다. %99s 한 번이면 끝날 문제이고, 같은 패턴이 lab02/p2_1.c:67에도 있다.

AVL 트리의 삽입과 회전은 정상 동작한다(실행 로그에 Single Rotate Left/Right, Double Rotate Left가 올바른 시점에 찍힌다). 그런데 deleteValue(:131–183)는 호출부가 없다. 그 안에서 preright = mom으로 읽는 전역 Tree * mom;(:18)은 어디서도 대입되지 않아 항상 NULL이다 — 죽은 코드 안의 죽은 분기다.

더 심각한 것은 :150이다. 중위 후속자 ret를 끌어올린 뒤 제거해야 하는데, 해제하는 것은 rret->right다. while 루프가 한 번이라도 돌았다면 ret는 rret->left에 있고, rret->right는 트리에 여전히 연결된 다른 노드다. 살아 있는 노드를 해제하고, 그 자리를 NULL로 끊어 서브트리를 통째로 유실시킨다. 똑같은 코드가 lab07/p7_1.c:141에도 있다 — Lab08이 Lab07을 복사했고, 두 과제의 입력 모두 삭제 명령을 포함하지 않아 아무도 이 경로를 밟지 않았다.

lab02/TestCase/에는 세 문제 각각의 input1/input2와 기대 출력 output1/output2가 들어 있다. 레포 전체에서 기대 출력이 존재하는 유일한 곳이다. 그래서 실제로 돌려 diff를 떠 봤다.

p2_1은 두 입력 모두 완전 일치한다. 그런데 p2_2와 p2_3은 네 케이스 전부 불일치한다. 숫자 값은 맞고, 틀리는 것은 라벨과 공백이다 — p2_3은 progAvg/examAvg여야 할 자리에 HwAvg/ExamAvg를 쓰고 탭 대신 공백을 넣는다. p2_2는 첫 열 머리글 앞 들여쓰기가 없고 줄 끝에 불필요한 탭이 붙는다.

출력 형식이 명세의 일부인 자동 채점 과제에서 이건 감점 사유다. 그러나 등급보다 중요한 것은 이것이다 — 정답 파일을 손에 쥐고도 diff를 한 번 돌리지 않았다. 명령 한 줄이면 끝났을 대조를, 정답을 커밋까지 해 놓고 하지 않았다. 이후 13개 랩에서 반복될 모든 결함의 원형이 여기 있다.

집합 {a,b,c} 형태를 읽어 부분집합/순열을 만드는 과제다. fscanf(fin, "%s", ret)는 SIZE 버퍼에 길이 제한 없이 쓴다. 이어지는 while (ret[++ptr] != '}')는 종료 조건을 닫는 중괄호의 존재에만 의존한다 — 입력에 '}'가 없으면 힙 버퍼를 벗어나 우연히 0x7D 바이트를 만날 때까지 읽고, 그 사이의 모든 바이트를 string에 쓴다. 시작 인덱스가 ++ptr이라 여는 중괄호를 건너뛰는 건 의도적이지만, 그 의도를 문서화한 검사는 없다.

함수 포인터 배열로 연산자를 디스패치하는 계산기다. 구조는 깔끔한데, 인접한 두 함수의 방어 수준이 다르다. division은 second가 0이면 0을 반환하는데, 바로 아래 modulus는 그대로 %를 수행한다 — x % 0은 x86에서 SIGFPE다. 같은 화면에 보이는 두 함수 사이의 불일치라 더 눈에 띈다.

또한 printf(__FUNCTION__)(:13, 19, 25, 35, 41)은 사용자 입력이 아니라 컴파일 타임 리터럴이므로 실제 위험은 없지만, 포맷 문자열 자리에 변수를 놓는 습관 그 자체다(-Wformat-security 대상). printf("%s", __FUNCTION__)가 맞다.

lab06/lab06.zip은 p6.c, input, lab6.docx를 담고 있는데 셋 다 이미 같은 디렉터리에 개별 파일로 커밋되어 있다. 제출용으로 압축한 것을 지우지 않고 함께 올린 것이다. 나머지 14개 랩에는 zip이 없으니 실수로 보인다.

과제 명세 PDF/DOCX 30개가 함께 커밋되어 있다(lab15.pdf 278KB 등, 팩 전체 2.65MB). 학부 레포에서 명세를 같이 두는 것은 납득할 만하지만, .gitignore에는 *.out, log/, test/만 있고 바이너리 문서에 대한 정책은 없다. lab10/p10-test.c가 남은 것도 같은 맥락이다 — lab12/p12-test.c는 지웠으면서.