일반적으로 사용하는 Swap 함수
#include <stdio.h>
void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main(void)
{
int x = 1;
int y = 2;
swap(&x, &y);
printf("x(%d), y(%d)\n", x, y);
}일반적으로 swap() 함수는 위의 코드와 같이 포인터를 사용해서 두 숫자를 바꿔줄 때 사용된다.
일반적인 swap 함수의 문제점
만약 그냥 swap 함수를 사용하게 된다면, 데이터 타입의 변경이 발생했을 때 각각의 타입에 맞춰서 함수를 구현해야하는 치명적인 문제점이 있다.
#include <stdio.h>
void swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void swap(double* a, double* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int main(void)
{
int x = 1, y = 2;
double dx = 1.1, dy = 2.1;
swap(&x, &y);
printf("x(%d), y(%d)\n", x, y);
swap(&dx, &dy);
printf("dx(%lf), dy(%lf)\n", dx, dy);
}예를 들어, 위의 코드처럼 int 타입의 swap 함수와 double 타입의 swap함수를 동시에 구현하였을 때, 함수 이름을 다르게 하지 않으면 C++에서는 오버로딩을 지원하므로 가능하지만, C언어에서는 전부 에러이다. 따라서 네임 맹글링(name mangling)과 같은 방법을 통해 함수 이름도 각각 지원해야하는 불편함이 있다.
#include <stdio.h>
void swap(char* a, char* b, int size)
{
char tmp;
int i = 0;
for (i = 0; i < size; i++) {
tmp = a[i];
a[i] = b[i];
b[i] = tmp;
}
}
int main(void)
{
int x = 1, y = 2;
double dx = 1.1, dy = 2.1;
swap((char *)&x, (char*)&y, sizeof(x));
printf("x(%d), y(%d)\n", x, y);
swap((char*)&dx, (char*)&dy, sizeof(dx));
printf("dx(%lf), dy(%lf)\n", dx, dy);
}만약 위의 코드처럼 swap 함수의 네임 맹글링 없이 char *와 size를 사용하여 넘긴다면 warning도 없고, 값도 잘 변경된다. 하지만 위 코드에서의 최대 문제점은 사용자가 swap 함수를 호출할 때마다 필요한 만큼 사이즈를 캐스팅 하는 것인데 이것은 올바르지 않다.
구현된 swap 함수는 이미 char로 받아서 편리하게 프로그래밍 했지만 caller는 매번 casting이 필요한 것은 상당히 불편하기 때문에 이렇게 코딩하면 안 된다. 따라서 swap 함수를 제네릭하게 변경해야 한다.
Generic Swap 함수
void swap(void* a, void* b, int size)
{
char tmp;
int i = 0;
for (i = 0; i < size; i++) {
tmp = a[i];
a[i] = b[i];
b[i] = tmp;
}
}따라서 swap 함수의 일반화가 필요하다. 그리고 이 때 사용되는 테크닉이 만능 열쇠인 void pointer이다. void pointer는 캐스팅 없이 받아주는 포인터이다. 그러면 에러가 발생하지도 않고 유저가 쓰기 편하다. 하지만 void pointer를 진짜로 사용하는 것은 문법상 허용되지 않기 때문에 전부 error가 발생한다.
void swap(void* a, void* b, int size)
{
char tmp;
int i = 0;
char* p = (char*)a;
char* q = (char*)b;
for (i = 0; i < size; i++) {
tmp = p[i];
p[i] = q[i];
q[i] = tmp;
}
}
int main(void)
{
int x = 1, y = 2;
double dx = 1.1, dy = 2.1;
swap(&x, &y, sizeof(x));
printf("x(%d), y(%d)\n", x, y);
swap(&dx, &dy, sizeof(dx));
printf("dx(%lf), dy(%lf)\n", dx, dy);
}void pointer를 사용해도 문법 상 에러가 발생하지 않게 하려면 당연히 char pointer로 캐스팅해서 void pointer의 움직이는 거리를 compiler에게 알려줘야 한다. 이럴 때 구현하는 swap 함수는 복잡해지더라도 호출하는 사용자가 쓰기 편하므로 전체 생산성을 증가시킬 수 있다.
그리고 위의 코드처럼 swap 함수를 사용한다면, 데이터 타입에 대한 에러도 당연히 없고 swap 함수도 문제 없이 수행되므로 모든 타입을 swap 가능한 generic swap 함수가 된다. 그리고 실제로 이 코드는 오픈 소스에서 지원하는 코드이다.
static void generic_swap(void *a, void *b, int size)
{
char t;
do {
t = *(char *)a;
*(char *)a++ = *(char *)b;
*(char *)b++ = t;
} while (--size > 0);
}Linux Kernel에서 제공하는 lib/sort.c 코드를 보면, 매개변수로 받은 size를 사용하여 do while문을 사용하였다. 연산 퍼포먼스는 Linux Kernel 코드가 조금 더 빠르다.
그 이유는 커널의 size는 감소하면서 0과 비교하는 것이기 때문에 어셈블리 코드 상 flag가 적기 때문이다. 반면에 i가 증가하면서 size가 되는지 조건을 비교하는 것은 연산 측면에서 조금 더 불리하고, 실제로 변수 i는 Linux Kernel 코드에서는 사용하지 않기 때문에 자원을 아낀 측면도 있다. 하지만 Clean code 관점에서 보자면 Linux Kernel 코드는 가독성이 조금 떨어진다.
void sort(void *base, size_t num, size_t size,
int (*cmp_func)(const void *, const void *),
void (*swap_func)(void *, void *, int size))
{
/* pre-scale counters for performance */
int i = (num/2 - 1) * size, n = num * size, c, r;
if (!swap_func) {
if (size == 4 && alignment_ok(base, 4))
swap_func = u32_swap;
else if (size == 8 && alignment_ok(base, 8))
swap_func = u64_swap;
else
swap_func = generic_swap;
}
......
}결국 핵심은 데이터 타입에 무관한 만능 열쇠인 void pointer를 넘겨 받고 필요한 변수 사이즈를 하나 넘겨서 루프를 돌며 char 별로 데이터들을 각각 swap하는 것이 핵심 테크닉이다. 그리고 이러한 generic swap 함수는 보통 위의 Linux Kernel의 sort 함수처럼 sorting의 내부 알고리즘으로 사용된다.
'자료구조' 카테고리의 다른 글
| [자료구조] Select sort (선택 정렬) (0) | 2020.02.05 |
|---|---|
| [자료구조] Bubble sort (버블 정렬) (0) | 2020.02.05 |
