forked from bangoc/cgen
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbns.h
121 lines (105 loc) · 2.73 KB
/
bns.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
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/*
(C) 2021 Nguyen Ba Ngoc (bangoc)
*/
#ifndef BNS_H_
#define BNS_H_
#include "bn.h"
// ========== Khai báo hàm ===============
static bn_node_t bns_search(bn_node_t root, const void *query,
bn_compare_t cmp);
// gte = greater than or equal, lte = less than or equal
static bn_node_t bns_search_gte(bn_node_t root, const void *query,
bn_compare_t cmp);
static bn_node_t bns_search_lte(bn_node_t root, const void *query,
bn_compare_t cmp);
// ========== Macro viết nhanh ===========
#define bns_child(n, order) (order < 0? n->left: n->right)
#define bns_child_ref(n, order) (order < 0? &n->left: &n->right)
#define bns_set_child(n, order, child) \
if (order < 0) n->left = child; else n->right = child
#define bns_find_insert_location(loc, root, data, cmp, same, parent) \
do { \
bn_node_t x = root; \
int order; \
while (x) { \
parent = x; \
order = cmp(data, x); \
if (!order) { \
same = x; \
} \
x = bns_child(x, order); \
} \
loc = parent? bns_child_ref(parent, order): &root; \
} while (0)
#define bns_search_inline(out, root, query, cmp) \
do { \
int order; \
bn_node_t x = root; \
out = NULL_PTR; \
while (x) { \
order = cmp(query, x); \
if (!order) { \
out = x; \
break; \
} \
x = bns_child(x, order); \
} \
} while (0)
#define bns_search_gte_inline(out, root, query, cmp) \
do {\
int order; \
bn_node_t x = root; \
out = NULL_PTR; \
while (x) { \
order = cmp(query, x); \
if (!order) { \
out = x; \
break; \
} \
if (order < 0) { \
out = x; \
x = x->left; \
continue; \
} \
x = x->right; \
} \
} while (0)
#define bns_search_lte_inline(out, root, query, cmp) \
do { \
int order; \
bn_node_t x = root; \
out = NULL_PTR; \
while (x) { \
order = cmp(query, x); \
if (!order) { \
out = x; \
break; \
} \
if (order > 0) { \
out = x; \
x = x->right; \
continue; \
} \
x = x->left; \
} \
} while (0)
// ========== Định nghĩa hàm =============
static bn_node_t bns_search(bn_node_t root, const void *query,
bn_compare_t cmp) {
bn_node_t result;
bns_search_inline(result, root, query, cmp);
return result;
}
static bn_node_t bns_search_gte(bn_node_t root, const void *query,
bn_compare_t cmp) {
bn_node_t out;
bns_search_gte_inline(out, root, query, cmp);
return out;
}
static bn_node_t bns_search_lte(bn_node_t root, const void *query,
bn_compare_t cmp) {
bn_node_t out;
bns_search_lte_inline(out, root, query, cmp);
return out;
}
#endif // BSNT_H_