]>
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 | ||
dfd48621 OZ |
41 | static struct f_tree * |
42 | build_tree_rec(struct f_tree **buf, int l, int h) | |
43 | { | |
44 | struct f_tree *n; | |
45 | int pos; | |
46 | ||
47 | if (l >= h) | |
48 | return NULL; | |
49 | ||
50 | pos = (l+h)/2; | |
51 | n = buf[pos]; | |
52 | n->left = build_tree_rec(buf, l, pos); | |
53 | n->right = build_tree_rec(buf, pos+1, h); | |
54 | return n; | |
55 | } | |
56 | ||
28a10f84 OZ |
57 | static int |
58 | tree_compare(const void *p1, const void *p2) | |
59 | { | |
4c553c5a | 60 | return val_compare(&((* (struct f_tree **) p1)->from), &((* (struct f_tree **) p2)->from)); |
28a10f84 | 61 | } |
dfd48621 | 62 | |
771ae456 PM |
63 | /** |
64 | * build_tree | |
8dcf2544 | 65 | * @from: degenerated tree (linked by @tree->left) to be transformed into form suitable for find_tree() |
771ae456 | 66 | * |
c8cafc8e | 67 | * Transforms degenerated tree into balanced tree. |
771ae456 | 68 | */ |
38506f71 PM |
69 | struct f_tree * |
70 | build_tree(struct f_tree *from) | |
71 | { | |
dfd48621 OZ |
72 | struct f_tree *tmp, *root; |
73 | struct f_tree **buf; | |
74 | int len, i; | |
38506f71 | 75 | |
dfd48621 | 76 | if (from == NULL) |
38506f71 PM |
77 | return NULL; |
78 | ||
dfd48621 OZ |
79 | len = 0; |
80 | for (tmp = from; tmp != NULL; tmp = tmp->left) | |
81 | len++; | |
82 | ||
83 | if (len <= 1024) | |
84 | buf = alloca(len * sizeof(struct f_tree *)); | |
85 | else | |
bc00f058 | 86 | buf = xmalloc(len * sizeof(struct f_tree *)); |
dfd48621 OZ |
87 | |
88 | /* Convert a degenerated tree into an sorted array */ | |
89 | i = 0; | |
90 | for (tmp = from; tmp != NULL; tmp = tmp->left) | |
91 | buf[i++] = tmp; | |
92 | ||
93 | qsort(buf, len, sizeof(struct f_tree *), tree_compare); | |
94 | ||
95 | root = build_tree_rec(buf, 0, len); | |
96 | ||
97 | if (len > 1024) | |
bc00f058 | 98 | xfree(buf); |
dfd48621 OZ |
99 | |
100 | return root; | |
38506f71 PM |
101 | } |
102 | ||
103 | struct f_tree * | |
104 | f_new_tree(void) | |
105 | { | |
30b84682 | 106 | struct f_tree *ret = cfg_allocz(sizeof(struct f_tree)); |
38506f71 PM |
107 | return ret; |
108 | } | |
9a4037d4 | 109 | |
8dcf2544 PM |
110 | /** |
111 | * same_tree | |
112 | * @t1: first tree to be compared | |
113 | * @t2: second one | |
114 | * | |
115 | * Compares two trees and returns 1 if they are same | |
116 | */ | |
9a4037d4 | 117 | int |
4c553c5a | 118 | same_tree(const struct f_tree *t1, const struct f_tree *t2) |
9a4037d4 PM |
119 | { |
120 | if ((!!t1) != (!!t2)) | |
121 | return 0; | |
122 | if (!t1) | |
123 | return 1; | |
4c553c5a | 124 | if (val_compare(&(t1->from), &(t2->from))) |
9a4037d4 | 125 | return 0; |
4c553c5a | 126 | if (val_compare(&(t1->to), &(t2->to))) |
9a4037d4 PM |
127 | return 0; |
128 | if (!same_tree(t1->left, t2->left)) | |
129 | return 0; | |
130 | if (!same_tree(t1->right, t2->right)) | |
131 | return 0; | |
4c553c5a | 132 | if (!f_same(t1->data, t2->data)) |
9a4037d4 PM |
133 | return 0; |
134 | return 1; | |
135 | } | |
0e175f9f OZ |
136 | |
137 | ||
138 | static void | |
4c553c5a | 139 | tree_node_format(const struct f_tree *t, buffer *buf) |
0e175f9f OZ |
140 | { |
141 | if (t == NULL) | |
142 | return; | |
143 | ||
144 | tree_node_format(t->left, buf); | |
145 | ||
4c553c5a MM |
146 | val_format(&(t->from), buf); |
147 | if (val_compare(&(t->from), &(t->to)) != 0) | |
0e175f9f OZ |
148 | { |
149 | buffer_puts(buf, ".."); | |
4c553c5a | 150 | val_format(&(t->to), buf); |
0e175f9f OZ |
151 | } |
152 | buffer_puts(buf, ", "); | |
153 | ||
154 | tree_node_format(t->right, buf); | |
155 | } | |
156 | ||
157 | void | |
4c553c5a | 158 | tree_format(const struct f_tree *t, buffer *buf) |
0e175f9f OZ |
159 | { |
160 | buffer_puts(buf, "["); | |
c8cafc8e | 161 | |
33d22f0e | 162 | tree_node_format(t, buf); |
0e175f9f | 163 | |
c2564d34 PT |
164 | if (buf->pos == buf->end) |
165 | return; | |
166 | ||
33d22f0e | 167 | /* Undo last separator */ |
0e175f9f OZ |
168 | if (buf->pos[-1] != '[') |
169 | buf->pos -= 2; | |
c8cafc8e | 170 | |
0e175f9f OZ |
171 | buffer_puts(buf, "]"); |
172 | } | |
d06a875b OZ |
173 | |
174 | void | |
175 | tree_walk(const struct f_tree *t, void (*hook)(const struct f_tree *, void *), void *data) | |
176 | { | |
177 | if (!t) | |
178 | return; | |
179 | ||
180 | tree_walk(t->left, hook, data); | |
181 | hook(t, data); | |
182 | tree_walk(t->right, hook, data); | |
183 | } |