Post

[정글] rbtree 발표 자료

RBTree - find


rb트리 로직은 다른 사람들이 많이 할 거 같아서 특이하게 rbtree에서 key값과 일치하는 노드를 찾아 리턴하는 리턴 하는 rbtree_find()함수를 발표할 것이다.(핑계 아님)


rb트리의 키 값을 찾는 것은 간단하다.

일단 아래의 코드를 보자.

1
2
3
4
5
6
7
8
9
node_t *rbtree_find(const rbtree *t, const key_t key) {
    node_t *p = t->root;
    while (p != t->nil)
    {
      if (key == p->key) return p;
      if (key < p->key) p = p ->left; else p = p ->right;
    }
    return NULL;
  }

그림으로 보자.

rbtree_find

현재 노드와 키값의 크기 비교 후 작으면 왼쪽 자식, 크면 오른쪽 자식으로 포인터를 이동시킨다.


보았듯이 이진탐색트리의 키 값의 노드를 찾는 방법과 동일하다. 구현도 간단하다.

그럼 이 함수가 포함된 파일의 전체 소스코드를 보자

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include "rbtree.h"
#include <stdio.h>

node_t *rbtree_find(const rbtree *t, const key_t key) {
  // TODO: implement find
    node_t *p = t->root;
    while (p != t->nil)
    {
      if (key == p->key) return p;
      if (key < p->key) p = p ->left; else p = p ->right;
    }
    return NULL;
  }




// 없음
// 없음
// 없음
// 없음
// 없음
// 없음



?
?
?
?
?
?

rbtree_find

그렇다. 이 소스코드의 파일명은 find.c이다.

CSAPP를 공부하면서 직접만든 파일을 한 번 링킹해보고 싶었다.

지금까지 컴파일러가 자동으로 링킹해주는 것만 받아먹고 있었다.

링킹을 하려면 일단 .o의 확장자를 가진 재배치 가능 목적파일까지 어셈블이 되어있어야 한다.

obj

어??

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
.PHONY: test

CFLAGS=-I ../src -Wall -g -DSENTINEL

test: test-rbtree
	./test-rbtree
	valgrind ./test-rbtree

test-rbtree: test-rbtree.o ../src/rbtree.o

../src/rbtree.o:
	$(MAKE) -C ../src rbtree.o

clean:
	rm -f test-rbtree *.o

test/makefile을 보면 이미 rbtree.otest-rbtree.o를 링킹해주는 코드가 있다.

사실 makefile이 어떻게 동작하는 지는 잘 모른다.

그치만

딸깍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
.PHONY: test

CFLAGS=-I ../src -Wall -g -DSENTINEL

test: test-rbtree
	./test-rbtree
	valgrind ./test-rbtree

test-rbtree: test-rbtree.o ../src/rbtree.o ../src/find.o

../src/rbtree.o:
	$(MAKE) -C ../src rbtree.o

../src/find.o:
	$(MAKE) -C ../src find.o

clean:
	rm -f test-rbtree *.o

여기에 find.o만 추가해주면

1
2
3
4
5
6
7
8
make clean

make test


# 결과
Passed all tests!

성공이다.


처음 아래의 코드를 붙여넣으면 빨간줄이 마구 끄인다.

1
2
3
4
5
6
7
8
9
node_t *rbtree_find(const rbtree *t, const key_t key) {
    node_t *p = t->root;
    while (p != t->nil)
    {
      if (key == p->key) return p;
      if (key < p->key) p = p ->left; else p = p ->right;
    }
    return NULL;
  }

당연하다.

1
2
#include "rbtree.h"
#include <stdio.h>

헤더가 포함되지 않았기 때문이다.

포함시켜 준다.

그렇지만

1
gcc -E find.c -o find.i

find.c를 전처리 해서 열어보면

소스코드 상단에 헤더의 모든 텍스트가 복사돼서 붙여넣어져 있다.

가독성을 위해 stdio.h는 제외했다,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
# 0 "find.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "find.c"
# 1 "rbtree.h" 1



# 1 "/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h" 1 3 4
# 145 "/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h" 3 4

# 145 "/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h" 3 4
typedef long int ptrdiff_t;
# 214 "/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h" 3 4
typedef long unsigned int size_t;
# 329 "/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h" 3 4
typedef int wchar_t;
# 425 "/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h" 3 4
typedef struct {
  long long __max_align_ll __attribute__((__aligned__(__alignof__(long long))));
  long double __max_align_ld __attribute__((__aligned__(__alignof__(long double))));
# 436 "/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h" 3 4
} max_align_t;
# 5 "rbtree.h" 2


# 6 "rbtree.h"
typedef enum { RBTREE_RED, RBTREE_BLACK } color_t;

typedef int key_t;



typedef struct node_t {
  color_t color;
  key_t key;
  struct node_t *parent, *left, *right;
} node_t;




typedef struct {
  node_t *root;
  node_t *nil;
} rbtree;

rbtree *new_rbtree(void);
void delete_rbtree(rbtree *);

node_t *rbtree_insert(rbtree *, const key_t);
node_t *rbtree_find(const rbtree *, const key_t);
node_t *rbtree_min(const rbtree *);
node_t *rbtree_max(const rbtree *);
int rbtree_erase(rbtree *, node_t *);

int rbtree_to_array(const rbtree *, key_t *, const size_t);
# 2 "find.c" 2


node_t *rbtree_find(const rbtree *t, const key_t key) {

    node_t *p = t->root;
    while (p != t->nil)
    {
      if (key == p->key) return p;
      if (key < p->key) p = p ->left; else p = p ->right;
    }
    return 
# 12 "find.c" 3 4
          ((void *)0)
# 12 "find.c"
              ;
  }

두 파일에 이렇게 동일한 헤더가 들어가도 오류가 나지 않는 이유는 헤더에는 선언만 들어있기 때문이다.

1
objdump -d test-rbtree

임의로 실행파일을 만들어서 디스어셈블해보면

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
00000000000038b3 <rbtree_to_array>:
    38b3:       f3 0f 1e fa             endbr64
    38b7:       55                      push   %rbp
    38b8:       48 89 e5                mov    %rsp,%rbp
    38bb:       48 83 ec 20             sub    $0x20,%rsp
    38bf:       48 89 7d f8             mov    %rdi,-0x8(%rbp)
    38c3:       48 89 75 f0             mov    %rsi,-0x10(%rbp)
    38c7:       48 89 55 e8             mov    %rdx,-0x18(%rbp)
    38cb:       48 8b 45 f8             mov    -0x8(%rbp),%rax
    38cf:       48 8b 30                mov    (%rax),%rsi
    38d2:       48 8b 4d e8             mov    -0x18(%rbp),%rcx
    38d6:       48 8b 55 f0             mov    -0x10(%rbp),%rdx
    38da:       48 8b 45 f8             mov    -0x8(%rbp),%rax
    38de:       49 89 c8                mov    %rcx,%r8
    38e1:       b9 00 00 00 00          mov    $0x0,%ecx
    38e6:       48 89 c7                mov    %rax,%rdi
    38e9:       e8 02 ff ff ff          call   37f0 <inorder>
    38ee:       b8 00 00 00 00          mov    $0x0,%eax
    38f3:       c9                      leave
    38f4:       c3                      ret

00000000000038f5 <rbtree_find>:
    38f5:       f3 0f 1e fa             endbr64
    38f9:       55                      push   %rbp
    38fa:       48 89 e5                mov    %rsp,%rbp
    38fd:       48 89 7d e8             mov    %rdi,-0x18(%rbp)
    3901:       89 75 e4                mov    %esi,-0x1c(%rbp)
    3904:       48 8b 45 e8             mov    -0x18(%rbp),%rax
    3908:       48 8b 00                mov    (%rax),%rax
    390b:       48 89 45 f8             mov    %rax,-0x8(%rbp)
    390f:       eb 38                   jmp    3949 <rbtree_find+0x54>
    3911:       48 8b 45 f8             mov    -0x8(%rbp),%rax
    3915:       8b 40 04                mov    0x4(%rax),%eax
    3918:       39 45 e4                cmp    %eax,-0x1c(%rbp)
    391b:       75 06                   jne    3923 <rbtree_find+0x2e>
    391d:       48 8b 45 f8             mov    -0x8(%rbp),%rax
    3921:       eb 39                   jmp    395c <rbtree_find+0x67>
    3923:       48 8b 45 f8             mov    -0x8(%rbp),%rax
    3927:       8b 40 04                mov    0x4(%rax),%eax
    392a:       39 45 e4                cmp    %eax,-0x1c(%rbp)
    392d:       7d 0e                   jge    393d <rbtree_find+0x48>
    392f:       48 8b 45 f8             mov    -0x8(%rbp),%rax
    3933:       48 8b 40 10             mov    0x10(%rax),%rax
    3937:       48 89 45 f8             mov    %rax,-0x8(%rbp)
    393b:       eb 0c                   jmp    3949 <rbtree_find+0x54>
    393d:       48 8b 45 f8             mov    -0x8(%rbp),%rax
    3941:       48 8b 40 18             mov    0x18(%rax),%rax
    3945:       48 89 45 f8             mov    %rax,-0x8(%rbp)
    3949:       48 8b 45 e8             mov    -0x18(%rbp),%rax
    394d:       48 8b 40 08             mov    0x8(%rax),%rax
    3951:       48 39 45 f8             cmp    %rax,-0x8(%rbp)
    3955:       75 ba                   jne    3911 <rbtree_find+0x1c>
    3957:       b8 00 00 00 00          mov    $0x0,%eax
    395c:       5d                      pop    %rbp
    395d:       c3                      ret

소스 코드 가장 마지막 함수인 rbtree_to_array하단에 rbtree_find 프리시저가 있는 것을 볼 수 있다.

This post is licensed under CC BY 4.0 by the author.