]>
Commit | Line | Data |
---|---|---|
38506f71 PM |
1 | /* |
2 | * Filters: utility functions | |
3 | * | |
4 | * Copyright 1998 Pavel Machek <pavel@ucw.cz> | |
5 | * | |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | */ | |
8 | ||
dfd48621 | 9 | #include "lib/alloca.h" |
38506f71 | 10 | #include "nest/bird.h" |
38506f71 PM |
11 | #include "conf/conf.h" |
12 | #include "filter/filter.h" | |
4f082dfa | 13 | #include "filter/data.h" |
38506f71 | 14 | |
771ae456 PM |
15 | /** |
16 | * find_tree | |
17 | * @t: tree to search in | |
18 | * @val: value to find | |
19 | * | |
20 | * Search for given value in the tree. I relies on fact that sorted tree is populated | |
21 | * by &f_val structures (that can be compared by val_compare()). In each node of tree, | |
22 | * either single value (then t->from==t->to) or range is present. | |
8dcf2544 | 23 | * |
3e82b32d | 24 | * Both set matching and |switch() { }| construction is implemented using this function, |
8dcf2544 | 25 | * thus both are as fast as they can be. |
771ae456 | 26 | */ |
4c553c5a MM |
27 | const struct f_tree * |
28 | find_tree(const struct f_tree *t, const struct f_val *val) | |
38506f71 PM |
29 | { |
30 | if (!t) | |
41be4444 | 31 | return NULL; |
4c553c5a MM |
32 | if ((val_compare(&(t->from), val) != 1) && |
33 | (val_compare(&(t->to), val) != -1)) | |
38506f71 | 34 | return t; |
4c553c5a | 35 | if (val_compare(&(t->from), val) == -1) |
38506f71 PM |
36 | return find_tree(t->right, val); |
37 | else | |
38 | return find_tree(t->left, val); | |
39 | } | |
40 | ||
e20bef69 OZ |
41 | /** |
42 | * find_tree_linear | |
43 | * @t: tree to search in | |
44 | * @val: value to find | |
45 | * | |
46 | * Search for given value in the degenerated linear tree, which is generated by | |
47 | * parser before build_tree() is applied. The tree is not sorted and all nodes | |
48 | * are linked by left ptr. | |
49 | */ | |
50 | const struct f_tree * | |
51 | find_tree_linear(const struct f_tree *t, const struct f_val *val) | |
52 | { | |
53 | for (; t; t = t->left) | |
54 | if ((val_compare(&(t->from), val) != 1) && | |
55 | (val_compare(&(t->to), val) != -1)) | |
56 | return t; | |
57 | ||
58 | return NULL; | |
59 | } | |
60 | ||
dfd48621 OZ |
61 | static struct f_tree * |
62 | build_tree_rec(struct f_tree **buf, int l, int h) | |
63 | { | |
64 | struct f_tree *n; | |
65 | int pos; | |
66 | ||
67 | if (l >= h) | |
68 | return NULL; | |
69 | ||
70 | pos = (l+h)/2; | |
71 | n = buf[pos]; | |
72 | n->left = build_tree_rec(buf, l, pos); | |
73 | n->right = build_tree_rec(buf, pos+1, h); | |
74 | return n; | |
75 | } | |
76 | ||
28a10f84 OZ |
77 | static int |
78 | tree_compare(const void *p1, const void *p2) | |
79 | { | |
4c553c5a | 80 | return val_compare(&((* (struct f_tree **) p1)->from), &((* (struct f_tree **) p2)->from)); |
28a10f84 | 81 | } |
dfd48621 | 82 | |
771ae456 PM |
83 | /** |
84 | * build_tree | |
8dcf2544 | 85 | * @from: degenerated tree (linked by @tree->left) to be transformed into form suitable for find_tree() |
771ae456 | 86 | * |
c8cafc8e | 87 | * Transforms degenerated tree into balanced tree. |
771ae456 | 88 | */ |
38506f71 PM |
89 | struct f_tree * |
90 | build_tree(struct f_tree *from) | |
91 | { | |
dfd48621 OZ |
92 | struct f_tree *tmp, *root; |
93 | struct f_tree **buf; | |
94 | int len, i; | |
38506f71 | 95 | |
dfd48621 | 96 | if (from == NULL) |
38506f71 PM |
97 | return NULL; |
98 | ||
dfd48621 OZ |
99 | len = 0; |
100 | for (tmp = from; tmp != NULL; tmp = tmp->left) | |
101 | len++; | |
102 | ||
103 | if (len <= 1024) | |
104 | buf = alloca(len * sizeof(struct f_tree *)); | |
105 | else | |
bc00f058 | 106 | buf = xmalloc(len * sizeof(struct f_tree *)); |
dfd48621 OZ |
107 | |
108 | /* Convert a degenerated tree into an sorted array */ | |
109 | i = 0; | |
110 | for (tmp = from; tmp != NULL; tmp = tmp->left) | |
111 | buf[i++] = tmp; | |
112 | ||
113 | qsort(buf, len, sizeof(struct f_tree *), tree_compare); | |
114 | ||
115 | root = build_tree_rec(buf, 0, len); | |
116 | ||
117 | if (len > 1024) | |
bc00f058 | 118 | xfree(buf); |
dfd48621 OZ |
119 | |
120 | return root; | |
38506f71 PM |
121 | } |
122 | ||
123 | struct f_tree * | |
124 | f_new_tree(void) | |
125 | { | |
30b84682 | 126 | struct f_tree *ret = cfg_allocz(sizeof(struct f_tree)); |
38506f71 PM |
127 | return ret; |
128 | } | |
9a4037d4 | 129 | |
8dcf2544 PM |
130 | /** |
131 | * same_tree | |
132 | * @t1: first tree to be compared | |
133 | * @t2: second one | |
134 | * | |
135 | * Compares two trees and returns 1 if they are same | |
136 | */ | |
9a4037d4 | 137 | int |
4c553c5a | 138 | same_tree(const struct f_tree *t1, const struct f_tree *t2) |
9a4037d4 PM |
139 | { |
140 | if ((!!t1) != (!!t2)) | |
141 | return 0; | |
142 | if (!t1) | |
143 | return 1; | |
4c553c5a | 144 | if (val_compare(&(t1->from), &(t2->from))) |
9a4037d4 | 145 | return 0; |
4c553c5a | 146 | if (val_compare(&(t1->to), &(t2->to))) |
9a4037d4 PM |
147 | return 0; |
148 | if (!same_tree(t1->left, t2->left)) | |
149 | return 0; | |
150 | if (!same_tree(t1->right, t2->right)) | |
151 | return 0; | |
4c553c5a | 152 | if (!f_same(t1->data, t2->data)) |
9a4037d4 PM |
153 | return 0; |
154 | return 1; | |
155 | } | |
0e175f9f | 156 | |
92a85655 OZ |
157 | int |
158 | tree_node_count(const struct f_tree *t) | |
159 | { | |
160 | if (t == NULL) | |
161 | return 0; | |
162 | ||
163 | return 1 + tree_node_count(t->left) + tree_node_count(t->right); | |
164 | } | |
0e175f9f OZ |
165 | |
166 | static void | |
4c553c5a | 167 | tree_node_format(const struct f_tree *t, buffer *buf) |
0e175f9f OZ |
168 | { |
169 | if (t == NULL) | |
170 | return; | |
171 | ||
172 | tree_node_format(t->left, buf); | |
173 | ||
4c553c5a MM |
174 | val_format(&(t->from), buf); |
175 | if (val_compare(&(t->from), &(t->to)) != 0) | |
0e175f9f OZ |
176 | { |
177 | buffer_puts(buf, ".."); | |
4c553c5a | 178 | val_format(&(t->to), buf); |
0e175f9f OZ |
179 | } |
180 | buffer_puts(buf, ", "); | |
181 | ||
182 | tree_node_format(t->right, buf); | |
183 | } | |
184 | ||
185 | void | |
4c553c5a | 186 | tree_format(const struct f_tree *t, buffer *buf) |
0e175f9f OZ |
187 | { |
188 | buffer_puts(buf, "["); | |
c8cafc8e | 189 | |
33d22f0e | 190 | tree_node_format(t, buf); |
0e175f9f | 191 | |
c2564d34 PT |
192 | if (buf->pos == buf->end) |
193 | return; | |
194 | ||
33d22f0e | 195 | /* Undo last separator */ |
0e175f9f OZ |
196 | if (buf->pos[-1] != '[') |
197 | buf->pos -= 2; | |
c8cafc8e | 198 | |
0e175f9f OZ |
199 | buffer_puts(buf, "]"); |
200 | } | |
d06a875b OZ |
201 | |
202 | void | |
203 | tree_walk(const struct f_tree *t, void (*hook)(const struct f_tree *, void *), void *data) | |
204 | { | |
205 | if (!t) | |
206 | return; | |
207 | ||
208 | tree_walk(t->left, hook, data); | |
209 | hook(t, data); | |
210 | tree_walk(t->right, hook, data); | |
211 | } |