File Coverage

bstree.h
Criterion Covered Total %
statement 83 100 83.0
branch 43 48 89.5
condition n/a
subroutine n/a
pod n/a
total 126 148 85.1


line stmt bran cond sub pod time code
1             /* Binary Search Tree implementation */
2             typedef struct bstree_node bstree_node;
3              
4             struct bstree_node {
5             int key;
6             void *val;
7             struct bstree_node *left;
8             struct bstree_node *right;
9             };
10              
11             typedef struct {
12             bstree_node *root;
13             int size;
14             } bstree;
15              
16             void bstree_put(bstree *tree, int key, void *val);
17             void* bstree_get(bstree *tree, int key);
18             void bstree_del(bstree *tree, int key);
19             int bstree_size(bstree *tree);
20             int* bstree_keys(bstree *tree);
21             void bstree_destroy(bstree *tree);
22             bstree_node* _bstree_new_node(int key, void *val);
23             int _bstree_put(bstree_node **node_ptr, int key, void *val);
24             void* _bstree_get(bstree_node *node, int key);
25             int _bstree_del(bstree *tree, bstree_node *parent, bstree_node *node, int key);
26             bstree_node* _bstree_most_left_node_parent(bstree_node *parent, bstree_node *node);
27             void _bstree_keys(bstree_node *node, int *rv, int i);
28             void _bstree_destroy(bstree_node *node);
29              
30             // PUBLIC API
31              
32 16           bstree* bstree_new() {
33 16           bstree *tree = malloc(sizeof(bstree));
34 16           tree->size = 0;
35 16           tree->root = NULL;
36            
37 16           return tree;
38             }
39              
40 314           void bstree_put(bstree *tree, int key, void *val) {
41 314           tree->size += _bstree_put(&tree->root, key, val);
42 314           }
43              
44 374           void* bstree_get(bstree *tree, int key) {
45 374           return _bstree_get(tree->root, key);
46             }
47              
48 326           void bstree_del(bstree *tree, int key) {
49 326           tree->size -= _bstree_del(tree, NULL, tree->root, key);
50 326           }
51              
52 16           int bstree_size(bstree *tree) {
53 16           return tree->size;
54             }
55              
56 0           int* bstree_keys(bstree *tree) {
57 0           int *rv = malloc(bstree_size(tree) * sizeof(int));
58 0           _bstree_keys(tree->root, rv, 0);
59            
60 0           return rv;
61             }
62              
63 16           void bstree_destroy(bstree *tree) {
64 16           _bstree_destroy(tree->root);
65 16           free(tree);
66 16           }
67              
68             // PRIVATE API
69              
70 314           bstree_node* _bstree_new_node(int key, void *val) {
71 314           bstree_node *node = malloc(sizeof(bstree_node));
72 314           node->left = node->right = NULL;
73 314           node->key = key;
74 314           node->val = val;
75            
76 314           return node;
77             }
78              
79 5170           int _bstree_put(bstree_node **node_ptr, int key, void *val) {
80 5170           bstree_node *node = *node_ptr;
81            
82 5170 100         if (node == NULL) {
83 314           *node_ptr = _bstree_new_node(key, val);
84 314           return 1;
85             }
86            
87 4856 100         if (key > node->key)
88 4772           return _bstree_put(&node->right, key, val);
89            
90 84 50         if (key < node->key)
91 84           return _bstree_put(&node->left, key, val);
92            
93 0           node->key = key;
94 0           node->val = val;
95 0           return 0;
96             }
97              
98 530           void* _bstree_get(bstree_node *node, int key) {
99 530 100         if (node == NULL)
100 12           return NULL;
101            
102 518 100         if (key > node->key)
103 105           return _bstree_get(node->right, key);
104            
105 413 100         if (key < node->key)
106 51           return _bstree_get(node->left, key);
107            
108 362           return node->val;
109             }
110              
111 561           int _bstree_del(bstree *tree, bstree_node *parent, bstree_node *node, int key) {
112 561 100         if (node == NULL)
113 12           return 0;
114            
115 549 100         if (key > node->key)
116 105           return _bstree_del(tree, node, node->right, key);
117            
118 444 100         if (key < node->key)
119 51           return _bstree_del(tree, node, node->left, key);
120            
121 393 100         if (node->left == NULL && node->right == NULL) {
    100          
122 117 100         if (parent == NULL) {
123 26           tree->root = NULL;
124             }
125 91 100         else if (parent->left == node) {
126 66           parent->left = NULL;
127             }
128             else {
129 25           parent->right = NULL;
130             }
131            
132 117           goto RET;
133             }
134            
135 276 100         if (node->left == NULL) {
136 191 100         if (parent == NULL) {
137 88           tree->root = node->right;
138             }
139 103 100         else if (parent->left == node) {
140 4           parent->left = node->right;
141             }
142             else {
143 99           parent->right = node->right;
144             }
145            
146 191           goto RET;
147             }
148            
149 85 100         if (node->right == NULL) {
150 6 100         if (parent == NULL) {
151 2           tree->root = node->left;
152             }
153 4 50         else if (parent->left == node) {
154 4           parent->left = node->left;
155             }
156             else {
157 0           parent->right = node->left;
158             }
159            
160 6           goto RET;
161             }
162            
163 79           bstree_node *next_node_parent = _bstree_most_left_node_parent(NULL, node->right);
164 79 100         bstree_node *next_node = next_node_parent == NULL ? node->right : next_node_parent->left;
165 79           node->key = next_node->key;
166 79           node->val = next_node->val;
167 79 100         return _bstree_del(tree, next_node_parent ? next_node_parent : node, next_node, next_node->key);
168            
169             RET:
170 314           free(node);
171 314           return 1;
172             }
173              
174 109           bstree_node* _bstree_most_left_node_parent(bstree_node *parent, bstree_node *node) {
175 109 100         if (node->left == NULL)
176 79           return parent;
177            
178 30           return _bstree_most_left_node_parent(node, node->left);
179             }
180              
181 0           void _bstree_keys(bstree_node *node, int *rv, int i) {
182 0 0         if (node == NULL)
183 0           return;
184            
185 0           rv[i++] = node->key;
186 0           _bstree_keys(node->left, rv, i);
187 0           _bstree_keys(node->right, rv, i);
188             }
189              
190 16           void _bstree_destroy(bstree_node *node) {
191 16 50         if (node == NULL)
192 16           return;
193            
194 0           _bstree_destroy(node->left);
195 0           _bstree_destroy(node->right);
196            
197 0           free(node);
198             }