Sentinel?
프로그래밍에서 전형적인 반복이나 재귀 알고리즘에서 전형적인 반복이나 재귀 알고리즘에서 종료 조건으로 사용하기위한 특별한 값을 말한다. (flag value, trip value, rogue value, signal value, dummy data)라고 한다.
Sentinel Value는 명시적으로 데이터 표기가 되지 않은 경우 일반적인 데이터와 구별되는 값을 통해 유효한 데이터의 끝을 보장하기 위해 사용한다.
RB Tree에서는 nill 노드를 통해서 해당 노드의 끝을 확인한다.
nil 노드를 만드는 과정에서 알게된 것
rbtree *new_rbtree(void) {
rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
node_t nil = {
RBTREE_BLACK,
0,
NULL,
NULL,
NULL,
};
node_t *nil_p = &nil;
p->nil = nil;
p->root = NULL;
return p;
}RB Tree 구현 과정에서 위와 같이 트리에 사용될 NIL Node를 초기화하는 코드를 작성했다.
이런 식으로 작성하고, 해당 코드를 테스트하기 위해 트리를 만들고 printf해보았지만, 분명 nil 노드를 지났음에도 계속 반복을 계속하여 Segment Fault가 계속 나타났다.
애초에 노드를 만드는 방식 자체가 잘못되었고,
위와 같은 방식으로 만든 노드는 지역 변수로 만들어졌기 때문에, 함수가 실행 중에는 함수를 호출하는 stack frame에 nil 노드가 남아있지만, 이후 함수가 종료되었을때, 종료된 함수와 관련된 Stack Frame이 사라지기 때문에 nil 노드도 남아있지 않게 된 것이다.
👊 스택 프레임(Stack Frame)
함수가 호출 되었을 때, 그 함수만의 스택 영역을 구분하기 위해 생성되는 공간. 공간에는 관계있는 매개변수, 지역변수가 저장되며, 함수의 호출 시 할당되고, 함수가 종료되면 소멸된다.
의도한 대로 구현하기 위해서는 calloc / malloc을 활용해 메모리 동적 할당을 통해 node를 만들어주어야 한다.
메모리 동적 할당
CS에서 실행시간동안 사용할 메모리 공간을 할당하는 것을 말한다.
동적으로 할당된 공간은 명시적으로 메모리 공간을 해제하거나 Garbage Collection이 되기 전까지 유지된다. C에서는 메모리 해제(free())를 해주기 전까지 공간이 남아있다. 동적할 당은 프로세스의 힙 영역에 할당되는데 프로세스가 종료되면 운영체제에 메모리 리소스를 반납하면서 메모리 해제된다. 동적 할당 메모리 공간은 프로그램 실행시 정해진 힙 영역의 크기 이상으로는 사용이 불가능하기 때문에 사용하지 않는 경우 메모리 해제해주는 것이 바람직하다.
malloc / calloc
malloc
```c
// stdlib.h
void* malloc(size_t size);
```
실행과정에서 메모리를 인자로 받은 크기만 큼 메모리를 할당하고, 시작 주소값을 리턴한다.
malloc으로 선언한 후 받은 포인터의 타입이 void*이기 때문에 원하는 타입으로 캐스팅 하는 코드가 필요하다.
void를 리턴하는 이유는 포인터가 가리키는 값이 어떠한 데이터 타입도 가능하기 때문에 일반 포인터 타입으로 반환하기 때문이다.
그리고 프로그램이 종료되기 전까지 메모리가 사라지지 않기 때문에 할당한 메모리 공간의 사용이 끝나면`free()`로 메모리 해제 해주어야한다.calloc
```c
void* calloc(size_t count, size_t size);
```
malloc과 동작이 유사하지만 약간의 차이가 있다.
calloc은 인자를 하나 더 받아서 size 만큼의 공간을 count개에 할당하는 함수이다.
그리고 malloc과 달리 할당된 공간을 0으로 초기화해준다.
malloc과 마찬가지로 일반 포인터 타입을 반환하고 사용 후에는 `free()`를 통해 메모리를 해제 해주어야한다.malloc과 calloc으로 앞서 내가 실수했던 함수를 작성해보면 아래와 같이 작성해볼 수 있다.
// with malloc
rbtree *new_rbtree(void) {
rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
*node_t *nil = (node_t*)malloc(sizeof(node_t));
nil->color = RBTREE_BLACK;
nil->key = 0;
nil->left = NULL;
nil->right = NULL;
nil->parent = NULL;*
p->nil = nil;
p->root = NULL;
return p;
}// with calloc
rbtree *new_rbtree(void) {
rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
node_t *nil = (node_t*)calloc(1, sizeof(node_t));
nil->color = RBTREE_BLACK;
p->nil = nil;
p->root = NULL;
return p;
}malloc vs calloc 🤨
위 상황에 한해서 어떤 동적할당 방법을 사용할 것인지 고민해봤을 때, 개인적으로 내린 결론은 malloc을 사용하는 것이 더 적절하다고 판단했다. calloc이 malloc과 비교해서 제공해주는 추가적인 두가지 기능이 n개의 메모리 공간과, 0으로 초기화 해주는 것인데, node를 만드는 상황에서 2개 이상의 동적 메모리 공간이 필요하다고 생각되지 않았고, 구조체의 속성 타입이 calloc이 초기화 해주는 초기값 0과의 타입이 맞지 않기 때문에 calloc을 사용하는 것이 부자연스럽다고 생각했다.
