하루 요약

✏️오늘의 한 일

• RB 로직 수정
• CSAPP 링커

🌈오늘의 성장?

RB 트리 로직 수정

삽입 로직 수정

• 발생 에러
  34를 넣으면 재조정 통해 루트가 바뀌는데 이 과정에서 기존 루트였던 10이 사라졌던 에러 발생

Root set to: 1024
Insert: 1024 at 0xaaaad3b18340, color : 0
Root set to: 512
Insert: 512 at 0xaaaad3b187d0, color : 0
Root set to: 128
Insert: 128 at 0xaaaad3b18850, color : 0
Transplant: replacing 128 with NIL
Root set to: 10
Insert: 10 at 0xaaaad3b188d0, color : 0
Insert: 5 at 0xaaaad3b18900, color : 0
Insert: 8 at 0xaaaad3b18930, color : 0
Root set to: 34
Insert: 34 at 0xaaaad3b18960, color : 0
Insert: 67 at 0xaaaad3b18990, color : 0
Insert: 23 at 0xaaaad3b189c0, color : 0
Insert: 156 at 0xaaaad3b189f0, color : 0
Insert: 24 at 0xaaaad3b18a20, color : 0
Insert: 2 at 0xaaaad3b18a50, color : 0
Insert: 12 at 0xaaaad3b18a80, color : 0
Insert: 24 at 0xaaaad3b18ab0, color : 0
Insert: 36 at 0xaaaad3b18ae0, color : 0
Insert: 990 at 0xaaaad3b18b10, color : 0
Insert: 25 at 0xaaaad3b18b40, color : 0

• 기존 로직

} else{ // (부모 RED + 삼촌 BLACK)
  // CASE 3 (일직선)
    if(is_straight_left){ // 왼쪽 일직선
      // 1. 부모와 조부모 색 교환
      color_t temp = parent->color;
      parent->color = grand_parent->color;
      grand_parent->color = temp;
      // 2. 회전
      right_rotate(t, grand_parent);
    } else if(is_straight_right){
      // 1. 부모와 조부모 색 교환
      color_t temp = parent->color;
      parent->color = grand_parent->color;
      grand_parent->color = temp;

      left_rotate(t, grand_parent);
    } else {
      // CASE 2 (꺾인 선)
      if(parent->left == z){
        // 왼쪽 삽입인 경우
        right_rotate(t, parent);
        z = z->left;
      }
      else
      { // 오른쪽 삽입
        left_rotate(t, parent);
        z = z->right;
      }
      // CASE 3 적용
      parent = z->parent;
      grand_parent = parent->parent;
      
      color_t temp = parent->color;
      parent->color = grand_parent->color;
      grand_parent->color = temp;
      
      if (z == parent->left) {
        right_rotate(t, grand_parent);
      } else {
        left_rotate(t, grand_parent);
      }
    }
  }

  t->root->color = RBTREE_BLACK;
}

• 수정 후

void rbtree_fix_up(rbtree *t, node_t *z) {
  while (z->parent->color == RBTREE_RED) {
    node_t *parent = z->parent;
    node_t *grand_parent = parent->parent;

    node_t *uncle = (grand_parent->left == parent) ? grand_parent->right : grand_parent->left;

    if (uncle->color == RBTREE_RED) {
      // CASE 1: 부모와 삼촌이 모두 RED
      parent->color = RBTREE_BLACK;
      uncle->color = RBTREE_BLACK;
      grand_parent->color = RBTREE_RED;
      z = grand_parent;
    } else {
      // CASE 2 & 3
      if (parent == grand_parent->left) {
        if (z == parent->right) {
          // CASE 2: 좌-우 (꺾인 선)
          z = parent;
          left_rotate(t, z);
        }
        // CASE 3: 좌-좌 (일직선)
        parent = z->parent;
        grand_parent = parent->parent;
        parent->color = RBTREE_BLACK;
        grand_parent->color = RBTREE_RED;
        right_rotate(t, grand_parent);
      } else {
        if (z == parent->left) {
          // CASE 2: 우-좌 (꺾인 선)
          z = parent;
          right_rotate(t, z);
        }
        // CASE 3: 우-우 (일직선)
        parent = z->parent;
        grand_parent = parent->parent;
        parent->color = RBTREE_BLACK;
        grand_parent->color = RBTREE_RED;
        left_rotate(t, grand_parent);
      }
    }
  }
  t->root->color = RBTREE_BLACK;
}

기존에 분기처리를 통해 CASE 2 -> CASE 3 가는 로직 하나, CASE 3 검사 로직 하나로 중복으로 검사하다보니
로직이 꼬일 수 있다고 판단.
CASE 2 에 if문을 걸어 먼저 검사하고 무조건 CASE 3로 가도록 수정하니 트리 자체는 문제 없이 동작.
단 이제 calloc에서 에러 뜨는...ㅠ

CSAPP 07. 링커

1️⃣ 링커란?

• 여러 개의 목적 파일(.o)을 연결하여
• 실행 가능한 파일(executable) 또는 라이브러리(.so, .a)를 만드는 도구

---

2️⃣ 링킹의 종류

시점	설명
정적 링크	컴파일 시 모든 참조를 해결해 하나의 실행파일 생성
동적 링크	실행 중에 필요한 라이브러리를 메모리에 로드하고 연결

---

3️⃣ 목적 파일의 종류

종류	설명
.o	재배치 가능 목적 파일 (Relocatable Object)
.out, .exe	실행 가능한 목적 파일 (Executable)
.so	공유 라이브러리 (Shared Object)

---

4️⃣ 링커의 핵심 작업

🧩 1. 심볼 해석 (Symbol Resolution)

• 함수나 변수 참조를 정의된 위치로 연결
• 외부에서 참조하는 심볼(함수, 변수)을 찾아 정확한 심볼로 연결

🔧 2. 재배치 (Relocation)

• 각각의 심볼에 실제 주소 할당
• 코드 내 참조 위치를 해당 주소로 수정(patching)

---

5️⃣ ELF 구조 핵심

구성 요소	역할
ELF Header	ELF 파일 정보(포맷, 타입 등)
섹션 헤더 테이블	각 섹션의 위치, 크기, 타입 정보
.text	기계어 코드
.data / .bss	전역 변수 (초기화 여부에 따라 구분)
.symtab / .strtab	심볼 테이블, 문자열 테이블
.rel.text / .rel.data	재배치 정보

---

6️⃣ 심볼의 종류

종류	설명
정의된 전역 심볼	함수나 초기화된 전역 변수 (강한 심볼)
외부 참조 심볼	extern으로 선언된 참조 대상 (링커가 연결)
정적(Local) 심볼	static으로 선언된 변수/함수 (자기 파일 내 전용)

• 🔹 중복 시 규칙
  • 강한 심볼은 단 하나
  • 강한 + 약한 ⇒ 강한만 사용
  • 약한만 여러 개 ⇒ 하나만 선택

---

7️⃣ 정적 라이브러리 vs 공유 라이브러리

항목	정적 라이브러리 (.a)	공유 라이브러리 (.so)
연결 시점	컴파일 시	실행 시
메모리 사용	중복 포함됨	메모리에 단 1개만
유지 보수	재컴파일 필요	교체만 하면 됨
코드 공유	X	O (메모리 절약)
위치 독립성	필요 없음	필요 (PIC 사용)

---

8️⃣ PIC (Position-Independent Code)

• 어떤 주소에 로드되어도 잘 작동하는 코드
• 공유 라이브러리에서 필수
• PC-relative 방식 or GOT 사용으로 구현

---

9️⃣ 라이브러리 삽입 (Interposition)

시점	방법	예
컴파일 시	#define malloc mymalloc	간단 디버깅
링크 시	gcc mymalloc.o main.o	빌드 시간 제어
런타임 시	LD_PRELOAD=myhook.so ./prog	디버깅, 추적

---

🔟 도구 정리

도구	설명
nm	심볼 테이블 조회
readelf	ELF 구조 분석
objdump	어셈블리/섹션/재배치 보기
ar	정적 라이브러리(.a) 내부 보기

⛏오늘의 삽질

• RB트리 로직 확인 삽질
  

삽입하고 바로 프린트문 찍어서 레드만 들어가는 줄 알고 삽입 로직 3시간 수정.