algorithm/test_rbt.c at master · pacozhong/algorithm · GitHub

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include <stdio.h>
#include <stdlib.h>
#include "xl_util.h"
#include "xl_rbt.h"
#include "xl_visual.h"
/* test code */

typedef struct st {
	char * a;
	int key;
	char*  pad;
}st;

int compare_st(const void *a, const void *b){
//	printf("a:0x%016lx\tb:0x%016lx\n", (int64_t)a, (int64_t)b);
	return ((st*)a)->key - ((st*)b)->key;
}

void visit_st(const xl_rbt_node_t *node, void *data){
	char *a = (char*)malloc(sizeof(char) * 17);
	printf("visit:\t%s %d(%lu)%c\n", xl_print_addr(node, a), ((st*)(node->data))->key, node->cnt, node->color == 1 ? 'R' : 'B');
	free(a);
}
int get_key(const void *data){
	return ((st*)data)->key;
}
int
main(int argc, char* argv[]){
	xl_rbt_t *tree = xl_rbt_init(compare_st);

	int tmp;
	st *st_tmp;
	xl_rbt_node_t *st_ret;
	int insert_ret, find_ret, delete_ret, visual_ret;
	while(1){
		printf("insert loop:\n");
		while(scanf("%d", &tmp) != EOF){
			st_tmp = (st*)malloc(sizeof(st));
			st_tmp->a = "a";
			st_tmp->key = tmp;
			st_tmp->pad = "pad";
			printf("st_tmp:");
			xl_print_addr(st_tmp, NULL);
			printf("\n");
			printf("key:%d\n", st_tmp->key);
			insert_ret = xl_rbt_insert(tree, st_tmp);
			if(insert_ret != 0) {
				printf("insert error!\n");
			}
			xl_rbt_inorder_traverse(tree, visit_st, NULL);
			printf("////////////\n");
			xl_rbt_preorder_traverse(tree, visit_st, NULL);
			printf("////////////\n");
			xl_rbt_postorder_traverse(tree, visit_st, NULL);
			printf("\n");
		}
		visual_ret = xl_visual_rbt(tree, "/root/algo/visual/rbt.gv", get_key);
		if(visual_ret != 0)
			printf("visual error!\n");
		printf("find loop:\n");
		while(scanf("%d", &tmp) != EOF){
			st_tmp = (st*)malloc(sizeof(st));
			st_tmp->a = "a";
			st_tmp->key = tmp;
			st_tmp->pad = "pad";
			find_ret = xl_rbt_find(tree, st_tmp, &st_ret);
			if(find_ret != 0) {
				printf("find fail!\n");
			}
			free(st_tmp);
			xl_rbt_inorder_traverse(tree, visit_st, NULL);
			printf("////////////\n");
			xl_rbt_preorder_traverse(tree, visit_st, NULL);
			printf("////////////\n");
			xl_rbt_postorder_traverse(tree, visit_st, NULL);
			printf("\n");
		}
		printf("delete loop:\n");
		while(scanf("%d", &tmp) != EOF){
			st_tmp = (st*)malloc(sizeof(st));
			st_tmp->a = "a";
			st_tmp->key = tmp;
			st_tmp->pad = "pad";
			delete_ret = xl_rbt_delete(tree, st_tmp);
			printf("root:");
			xl_print_addr(tree->root, NULL);
			printf("\n");
			if(delete_ret != 0) {
				printf("delete fail!\n");
			}
			free(st_tmp);
			visual_ret = xl_visual_rbt(tree, "/root/algo/visual/rbt.gv", get_key);
			if(visual_ret != 0)
				printf("visual error!\n");
			xl_rbt_inorder_traverse(tree, visit_st, NULL);
			printf("////////////\n");
			xl_rbt_preorder_traverse(tree, visit_st, NULL);
			printf("////////////\n");
			xl_rbt_postorder_traverse(tree, visit_st, NULL);
			printf("\n");
		}
	}
}