[정글] rbtree 발표 자료
![["gcc썸네일 이미지"]](/assets/img/posts/발표/thumb.jpg)
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;
}
그림으로 보자.
현재 노드와 키값의 크기 비교 후 작으면 왼쪽 자식, 크면 오른쪽 자식으로 포인터를 이동시킨다.
보았듯이 이진탐색트리의 키 값의 노드를 찾는 방법과 동일하다. 구현도 간단하다.
그럼 이 함수가 포함된 파일의 전체 소스코드를 보자
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;
}
// 없음
// 없음
// 없음
// 없음
// 없음
// 없음
?
?
?
?
?
?
그렇다. 이 소스코드의 파일명은 find.c이다.
CSAPP를 공부하면서 직접만든 파일을 한 번 링킹해보고 싶었다.
지금까지 컴파일러가 자동으로 링킹해주는 것만 받아먹고 있었다.
링킹을 하려면 일단 .o의 확장자를 가진 재배치 가능 목적파일까지 어셈블이 되어있어야 한다.
어??
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.o 와 test-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.