]>
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" | |
13 | ||
771ae456 PM |
14 | /** |
15 | * find_tree | |
16 | * @t: tree to search in | |
17 | * @val: value to find | |
18 | * | |
19 | * Search for given value in the tree. I relies on fact that sorted tree is populated | |
20 | * by &f_val structures (that can be compared by val_compare()). In each node of tree, | |
21 | * either single value (then t->from==t->to) or range is present. | |
8dcf2544 | 22 | * |
3e82b32d | 23 | * Both set matching and |switch() { }| construction is implemented using this function, |
8dcf2544 | 24 | * thus both are as fast as they can be. |
771ae456 | 25 | */ |
38506f71 PM |
26 | struct f_tree * |
27 | find_tree(struct f_tree *t, struct f_val val) | |
28 | { | |
29 | if (!t) | |
41be4444 | 30 | return NULL; |
38506f71 PM |
31 | if ((val_compare(t->from, val) != 1) && |
32 | (val_compare(t->to, val) != -1)) | |
33 | return t; | |
34 | if (val_compare(t->from, val) == -1) | |
35 | return find_tree(t->right, val); | |
36 | else | |
37 | return find_tree(t->left, val); | |
38 | } | |
39 | ||
dfd48621 OZ |
40 | static struct f_tree * |
41 | build_tree_rec(struct f_tree **buf, int l, int h) | |
42 | { | |
43 | struct f_tree *n; | |
44 | int pos; | |
45 | ||
46 | if (l >= h) | |
47 | return NULL; | |
48 | ||
49 | pos = (l+h)/2; | |
50 | n = buf[pos]; | |
51 | n->left = build_tree_rec(buf, l, pos); | |
52 | n->right = build_tree_rec(buf, pos+1, h); | |
53 | return n; | |
54 | } | |
55 | ||
28a10f84 OZ |
56 | static int |
57 | tree_compare(const void *p1, const void *p2) | |
58 | { | |
59 | return val_compare((* (struct f_tree **) p1)->from, (* (struct f_tree **) p2)->from); | |
60 | } | |
dfd48621 | 61 | |
771ae456 PM |
62 | /** |
63 | * build_tree | |
8dcf2544 | 64 | * @from: degenerated tree (linked by @tree->left) to be transformed into form suitable for find_tree() |
771ae456 PM |
65 | * |
66 | * Transforms denerated tree into balanced tree. | |
67 | */ | |
38506f71 PM |
68 | struct f_tree * |
69 | build_tree(struct f_tree *from) | |
70 | { | |
dfd48621 OZ |
71 | struct f_tree *tmp, *root; |
72 | struct f_tree **buf; | |
73 | int len, i; | |
38506f71 | 74 | |
dfd48621 | 75 | if (from == NULL) |
38506f71 PM |
76 | return NULL; |
77 | ||
dfd48621 OZ |
78 | len = 0; |
79 | for (tmp = from; tmp != NULL; tmp = tmp->left) | |
80 | len++; | |
81 | ||
82 | if (len <= 1024) | |
83 | buf = alloca(len * sizeof(struct f_tree *)); | |
84 | else | |
85 | buf = malloc(len * sizeof(struct f_tree *)); | |
86 | ||
87 | /* Convert a degenerated tree into an sorted array */ | |
88 | i = 0; | |
89 | for (tmp = from; tmp != NULL; tmp = tmp->left) | |
90 | buf[i++] = tmp; | |
91 | ||
92 | qsort(buf, len, sizeof(struct f_tree *), tree_compare); | |
93 | ||
94 | root = build_tree_rec(buf, 0, len); | |
95 | ||
96 | if (len > 1024) | |
97 | free(buf); | |
98 | ||
99 | return root; | |
38506f71 PM |
100 | } |
101 | ||
102 | struct f_tree * | |
103 | f_new_tree(void) | |
104 | { | |
105 | struct f_tree * ret; | |
106 | ret = cfg_alloc(sizeof(struct f_tree)); | |
107 | ret->left = ret->right = NULL; | |
108 | ret->from.type = ret->to.type = T_VOID; | |
109 | ret->from.val.i = ret->to.val.i = 0; | |
110 | ret->data = NULL; | |
111 | return ret; | |
112 | } | |
9a4037d4 | 113 | |
8dcf2544 PM |
114 | /** |
115 | * same_tree | |
116 | * @t1: first tree to be compared | |
117 | * @t2: second one | |
118 | * | |
119 | * Compares two trees and returns 1 if they are same | |
120 | */ | |
9a4037d4 PM |
121 | int |
122 | same_tree(struct f_tree *t1, struct f_tree *t2) | |
123 | { | |
124 | if ((!!t1) != (!!t2)) | |
125 | return 0; | |
126 | if (!t1) | |
127 | return 1; | |
128 | if (val_compare(t1->from, t2->from)) | |
129 | return 0; | |
130 | if (val_compare(t1->to, t2->to)) | |
131 | return 0; | |
132 | if (!same_tree(t1->left, t2->left)) | |
133 | return 0; | |
134 | if (!same_tree(t1->right, t2->right)) | |
135 | return 0; | |
136 | if (!i_same(t1->data, t2->data)) | |
137 | return 0; | |
138 | return 1; | |
139 | } |