/
tree.h
133 lines (121 loc) · 3.64 KB
/
tree.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
122
123
124
125
126
127
128
129
130
131
132
133
struct tree_node {
struct tree_node* zero;
struct tree_node* one;
unsigned char* value;
};
struct tree_value {
int mask;
int addr[];
};
struct tree_head {
int reclen;
struct tree_node* root;
};
int bitVals[] = {
0x80000000, 0x40000000, 0x20000000, 0x10000000,
0x8000000, 0x4000000, 0x2000000, 0x1000000,
0x800000, 0x400000, 0x200000, 0x100000,
0x80000, 0x40000, 0x20000, 0x10000,
0x8000, 0x4000, 0x2000, 0x1000,
0x800, 0x400, 0x200, 0x100,
0x80, 0x40, 0x20, 0x10,
0x8, 0x4, 0x2, 0x1
};
void tree_init(struct tree_head *tab, int reclen) {
tab->reclen = reclen;
tab->root = malloc(sizeof(struct tree_node));
if (tab->root == NULL) err("error allocating memory");
memset(tab->root, 0, sizeof(struct tree_node));
}
void tree_deinit(struct tree_head *tab) {
tab->reclen = 0;
free(tab->root);
tab->root = NULL;
}
#define tree_bit(p) (val->addr[p / 32] & bitVals[p % 32])
void* tree_lpm(struct tree_head *tab, void *ntry) {
struct tree_node* cur = tab->root;
struct tree_value* val = ntry;
int vlmsk = val->mask;
void* lst = NULL;
for (int p = 0;; p++) {
if (cur->value != NULL) lst = cur->value;
if (p >= vlmsk) return lst;
if (tree_bit(p) != 0) {
cur = cur->one;
} else {
cur = cur->zero;
}
if (cur == NULL) return lst;
}
}
void tree_add(struct tree_head *tab, void *ntry) {
struct tree_node* cur = tab->root;
struct tree_value* val = ntry;
int vlmsk = val->mask;
for (int p = 0;; p++) {
if (p >= vlmsk) {
if (cur->value != NULL) {
memcpy(cur->value, ntry, tab->reclen);
return;
}
void* nxt = malloc(tab->reclen);
if (nxt == NULL) err("error allocating memory");
memcpy(nxt, ntry, tab->reclen);
cur->value = nxt;
return;
}
if (tree_bit(p) != 0) {
if (cur->one != NULL) {
cur = cur->one;
continue;
}
struct tree_node* nxt = malloc(sizeof(struct tree_node));
if (nxt == NULL) err("error allocating memory");
memset(nxt, 0, sizeof(struct tree_node));
cur->one = nxt;
cur = nxt;
} else {
if (cur->zero != NULL) {
cur = cur->zero;
continue;
}
struct tree_node* nxt = malloc(sizeof(struct tree_node));
if (nxt == NULL) err("error allocating memory");
memset(nxt, 0, sizeof(struct tree_node));
cur->zero = nxt;
cur = nxt;
}
}
}
void tree_del(struct tree_head *tab, void *ntry) {
struct tree_node* cur = tab->root;
struct tree_value* val = ntry;
int vlmsk = val->mask;
for (int p = 0;; p++) {
if (p >= vlmsk) {
void* old = cur->value;
if (old == NULL) return;
cur->value = NULL;
free(old);
return;
}
if (tree_bit(p) != 0) {
cur = cur->one;
} else {
cur = cur->zero;
}
if (cur == NULL) return;
}
}
void tree_walkNode(struct tree_node *cur, void doer(void *, int, void *), int fixed, void* param) {
if (cur == NULL) return;
tree_walkNode(cur->zero, doer, fixed, param);
tree_walkNode(cur->one, doer, fixed, param);
if (cur->value == NULL) return;
doer(cur->value, fixed, param);
}
void tree_walk(struct tree_head *tab, void doer(void *, int, void *), int fixed, void* param) {
struct tree_node* cur = tab->root;
tree_walkNode(cur, doer, fixed, param);
}