24.02.05 CSAPP 8.55, RB트리 구현

CSAPP

8.5.5 시그널 핸들러 작성하기

• 핸들러는 이해하기 어렵게 만드는 몇 가지 특성을 가진다.
  1. 핸들러는 메인프로그램과 동시적으로 돌아가고, 같은 전역변수를 공유하며, 그래서 메인 프로그램과 다른 핸들러들과 뒤섞일 수 있다.
  2. 어떻게 그리고 언제 시그널들이 수신 될 수 있는지는 종종 직관적이지 않다.
  3. 다른 시스템들은 다른 시그널 처리 방식을 갖는다.

안전한 시그널 처리

• G0
  • 핸들러는 가능한 한 간단하게 유지하라. 문제를 피하는 최상의 방법은 핸들러를 작고 단순하게 유지하는 것이다.
• G1
  • 핸들러에서 비동시성-시그널-안전한 함수만 호출하라. 비동기성-시그널-안전한 또는 단순히 안전한 함수는 그것이 재진입 가능하거나 어떤 시그널 핸들러에 의해 중단 될 수 없기 때문에 어떤 시그널 핸들러로 부터 안전하게 호출될 수 있는 특성을 가진다
• G2
  • errno를 저장하고 복원하라
• G3
  • 모든 시그널을 블록 시켜서 공유된 전역 자료구조들로의 접근을 보호하라
• G4
  • 전역변수들을 volatile로 선언하라
• G5
  • sig_atomic_t로 플래그들을 선언하라

RB트리 구현

예림님과 재희님의 도움을 받아, 구현을 마쳤다. 내가 한 건 약간 이론같은 영역이 많아서 구현에는 큰 힘을 못썼는데, 예림님과 재희님이 하드캐리 해버리셨다. 특히 예림님이 크게 역할을 해 주셔서 편하게 할 수 있었다.

• 나는 ARRAY부분을 맡았다.

void inorder(const rbtree *t, node_t *x, key_t *arr, int *idx, const size_t n)
{
    if (x == t->nil)
    {
        return;
    }
    inorder(t, x->left, arr, idx, n);
    if (*idx < n)
    {
        arr[(*idx)++] = x->key;
    }
    else
    {
        return;
    }
    inorder(t, x->right, arr, idx, n);
}

int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n)
{
    node_t *x = t->root;
    if (x == t->nil)
        return 0;
    int cnt = 0;
    int *idx = &cnt;
    inorder(t, x, arr, idx, n);
    return 0;
}

• 인터넷의 도움을 받았다.
• 중위순회를 사용했고, 어레이의 인덱스에서 어떻게 해야할지 고민에 빠졌었는데, 한 블로거분이 인트 주소를 받아서 인덱스로 사용하고, 포인터 연산을 통해 인덱스를 조절하는 것을 보고 이마를 탁하고 쳤다! 유ㅠㅠㅠㅠ레ㅔㅔㅔㅔ카ㅏㅏㅏ