Skip to content

Latest commit

 

History

History
236 lines (198 loc) · 6.28 KB

swap.md

File metadata and controls

236 lines (198 loc) · 6.28 KB

swap 함수 구현하기

이 문서는 swap함수를 단계별로 단점을 극복해가며 작성한 것이다.

  • 모두가 아는 swap 함수
void swap(void *a, void *b);

int main() {
	int a = 10, b = 20;
	swap(&a, &b);
	printf("a = %d, b = %d", a, b);
	return 0;
}

void swap(void *a, void *b) {
        int t = *(int *)a;
	*(int *)a = *(int *)b;
	*(int *)b = t;
}

단점

  • 위 swap함수는 int형만 swap이 가능하다.
    따라서 다음에는 모든 타입에 대하여 swap이 가능하도록 해보자.
enum Type {  INT, DOUBLE };  //Type Code라 한다.
void swap(void *a, void *b, enum Type t) {
	switch (t) {
	case INT: {
		int tmp = *(int *)a;
		*(int *)a = *(int *)b;
		*(int *)b = tmp;
		break;
	}
	case DOUBLE: {
		double tmp = *(double *)a;
		*(double *)a = *(double *)b;
		*(double *)b = tmp;
		break;
	}
	}
}
int main() {
	int a = 10, b = 20;
   	swap(&a, &b, INT);
   	double c = 3.14, d = 5.14;
   	swap(&c, &d, DOUBLE);
}

C언어에는 Java의 Object처럼 모든 타입을 담을 수 있을 수 없기에
위와 같이 열거형으로 타입을 주었다.

단점들

  • (1) Type Code를 사용하면 항상 switch문을 이용하게 된다.
  • (2) 새로운 Type Code를 부여하면, case문을 그에 맞게 추가해야하는 번거로움이 있다.
이번에는 Type Code 대신 dataSize:size_t를 swap의 인수로 받아서 동적 할당을 통해 구현해보았다. 
void swap(void *a, void *b, size_t dataSize){
    void *t = malloc(dataSize);
    memcpy(t, a, dataSize);
    memcpy(a, b, dataSize);
    memcpy(b, t, dataSize);
    free(t);
}
int main() {
	int a = 10, b = 20;
	swap(&a, &b, sizeof(int));
	printf("a = %d, b = %d\n", a, b);
	double c = 3.14, d = 5.14;
	swap(&c, &d, sizeof(double));
	printf("c = %f, d = %f\n", c, d);
}

위와 같이 세번 째 인수로 바꾸려는 자료형의 크기를 전달하면, swap에서 void* t 를 해당 크기에 맞게 동적 할당하여 swap을 구현할 수 있었다.

단점들

  • (1) malloc()의 성공이 보장되지 않는다.
  • (2) 함수 호출의 오버헤드가 발생할 수 있다.
  • (3) OS측면에서 malloc()의 호출은 상당히 부담이 되는 작업이다.

따라서 다음에는 동적 할당을 하지 않고 하는 방법을 생각해보자. 
#define SWAP(x, y, t) \
    (t) = (x);
    (x) = (y);
    (y) = (t);
int main() {
	int a = 10, b = 20, t1;
	SWAP(a, b, t1);
	printf("a = %d, b = %d\n", a, b);
	double c = 3.14, d = 5.14, t2;
   	SWAP(c, d, t2);
   	printf("c = %f, d = %f\n", c, d);
}

이번에는 SWAP을 매크로 함수로 구현해보았다. SWAP의 세번 째 인수인 t는 사용자로부터 받는 인수이다.

단점

  • SWAP의 호출 회수만큼 해당 자료형의 메모리 변수를 선언해야 하므로 스택 메모리를 많이 차지하게 된다.
이번에는 위의 스택 메모리를 절약하기 위해 매크로 함수를 조금 바꿔보았다. 
#define SWAP(x, y, T) {\
	T t = (x);\
	(x) = (y);\
	(y) = t; }
int main() {
	int a = 10, b = 20;
   	SWAP(a, b, int);
   	printf("a = %d, b = %d\n", a, b);
   	double c = 3.14, d = 5.14;
   	SWAP(c, d, double);
   	printf("c = %f, d = %f\n", c, d);
}

위 코드에서는 SWAP의 세번 째 인자T에 swap할 자료형을 받게 했다.
그리고 { }블록을 두어 t를 그 안에서 선언하므로써, 불필요한 스택 메모리의 사용을 없앴다.

단점

  • Dangling-Else가 발생할 수 있다.
int a = 10, b = 20;
if(a > b){
	SWAP(a, b, int);	
}
else{
	;
}
//위와 같이 if문 안에 SWAP함수를 두면,
//전처리기에 의해 변환된 if절의 마지막이
// }; 로 끝나게 되는 문제점이 발생한다.
위 코드에서의 Dangling-else가 발생하는 현상을 막기 위해서는 SWAP함수의 정의부를 do-while 문으로 감싸주는 방법이 있다. 
#define SWAP(x, y, T) do{ \
    T t = (x);\
    (x) = (y);
    (y) = t; } while(0)

단점

  • 위 코드에서의 단점은 딱히 보이지 않았다.
  • 하지만 꼭 매크로 함수를 써야할까? 그리고, 일반 함수를 사용한다면 동적할당을 하지 않고 구현할 수는 없을까?
void swap(void *a, void *b, size_t dataSize) {
    char *pA = (char *)a;
    char *pB = (char *)b;
   for(size_t i = 0; i < dataSize; i++, pA++, pB++) {
        char t = *pA;
        *pA = *pB;
        *pB = t;
   }
}
int main(){
  	int a = 10, b = 20;
   	swap(&a, &b, sizeof(int));
   	printf("a = %d, b = %d\n", a, b);
   	double c = 3.14, d = 5.14, t2;
   	SWAP(c, d, t2);
   	printf("c = %f, d = %f\n", c, d);
}

위 swap함수에서는 바꿀 것을 1Byte 단위로 꺼내와서 복사한다. 그러기 위해 char* 와 char을 이용했다.

결과

  • 위 코드는 일반 함수를 이용해 완벽하게(?) 구현해낸 swap 함수이다.

생각해보기

다음은 리눅스 v2.6.39.4에 있는 sort.c의 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);
}

의문점

  • 위 코드는 GCC 컴파일러에서는 문제없이 작동하지만, Visual Studio C Compiler에서는 컴파일 타임에 오류가 발생한다. 이유가 뭘까..?

정답

  • GCC에서는 void* 에 대한 증감 연산이 가능하다. 하지만 Visual Studio C Compiler는 이를 허용하지 않는다.
  • *(char *)a++ = *(char *)b; 가 수행되는 순서
    • (1) a를 char*형으로 캐스팅한다.
    • (2) 역참조를 하여 우항의 값을 대입한다. (이때, 캐스팅효과는 역참조 후 풀리게 된다.)
    • (3) a(void*형)에 대하여 ++연산을 수행한다.
    • (4) void*에 대하여 ++ 연산을 하기에 Visual Studio C Compiler에서는 수행이 불가하지만, GCC에서는 수행이 가능한 것이다.
    • (5) Visual Studio C Comipler에서도 수행가능하게 하려면 코드를 다음과 같이 고쳐야 한다.

*((char *)a)++ = *(char *)b;
*((char *)b)++ = t;