]>
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 | ||
38506f71 | 9 | #include "nest/bird.h" |
38506f71 PM |
10 | #include "conf/conf.h" |
11 | #include "filter/filter.h" | |
12 | ||
771ae456 | 13 | /* |
8dcf2544 | 14 | * find_nth - finds n-th element in linked list. Don't be confused by types, it is really a linked list. |
771ae456 | 15 | */ |
38506f71 PM |
16 | static struct f_tree * |
17 | find_nth(struct f_tree *from, int nth) | |
18 | { | |
19 | struct f_tree *pivot; | |
20 | int lcount = 0, rcount = 0; | |
21 | struct f_tree *left, *right, *next; | |
22 | ||
23 | pivot = from; | |
24 | ||
25 | left = right = NULL; | |
26 | next = from->right; | |
27 | while (from = next) { | |
28 | next = from->right; | |
29 | if (val_compare(pivot->from, from->from)==1) { | |
30 | from->right = left; | |
31 | left = from; | |
32 | lcount++; | |
33 | } else { | |
34 | from->right = right; | |
35 | right = from; | |
36 | rcount++; | |
37 | } | |
38 | } | |
39 | if (lcount == nth) | |
40 | return pivot; | |
41 | if (lcount < nth) | |
42 | return find_nth(right, nth-lcount-1); | |
43 | return find_nth(left, nth); | |
44 | } | |
45 | ||
771ae456 | 46 | /* |
8dcf2544 | 47 | * find_median - Gets list linked by @left, finds its median, trashes pointers in @right. |
771ae456 | 48 | */ |
38506f71 PM |
49 | static struct f_tree * |
50 | find_median(struct f_tree *from) | |
51 | { | |
52 | struct f_tree *t = from; | |
53 | int cnt = 0; | |
54 | ||
55 | if (!from) | |
56 | return NULL; | |
57 | do { | |
58 | t->right = t->left; | |
59 | cnt++; | |
60 | } while (t = t->left); | |
61 | return find_nth(from, cnt/2); | |
62 | } | |
63 | ||
771ae456 PM |
64 | /** |
65 | * find_tree | |
66 | * @t: tree to search in | |
67 | * @val: value to find | |
68 | * | |
69 | * Search for given value in the tree. I relies on fact that sorted tree is populated | |
70 | * by &f_val structures (that can be compared by val_compare()). In each node of tree, | |
71 | * either single value (then t->from==t->to) or range is present. | |
8dcf2544 PM |
72 | * |
73 | * Both set matching and switch() { } construction is implemented using this function, | |
74 | * thus both are as fast as they can be. | |
771ae456 | 75 | */ |
38506f71 PM |
76 | struct f_tree * |
77 | find_tree(struct f_tree *t, struct f_val val) | |
78 | { | |
79 | if (!t) | |
41be4444 | 80 | return NULL; |
38506f71 PM |
81 | if ((val_compare(t->from, val) != 1) && |
82 | (val_compare(t->to, val) != -1)) | |
83 | return t; | |
84 | if (val_compare(t->from, val) == -1) | |
85 | return find_tree(t->right, val); | |
86 | else | |
87 | return find_tree(t->left, val); | |
88 | } | |
89 | ||
771ae456 PM |
90 | /** |
91 | * build_tree | |
8dcf2544 | 92 | * @from: degenerated tree (linked by @tree->left) to be transformed into form suitable for find_tree() |
771ae456 PM |
93 | * |
94 | * Transforms denerated tree into balanced tree. | |
95 | */ | |
38506f71 PM |
96 | struct f_tree * |
97 | build_tree(struct f_tree *from) | |
98 | { | |
99 | struct f_tree *median, *t = from, *next, *left = NULL, *right = NULL; | |
100 | ||
101 | median = find_median(from); | |
102 | if (!median) | |
103 | return NULL; | |
104 | ||
105 | do { | |
106 | next = t->left; | |
107 | if (t == median) | |
108 | continue; | |
109 | ||
110 | if (val_compare(median->from, t->from)==1) { | |
111 | t->left = left; | |
112 | left = t; | |
113 | } else { | |
114 | t->left = right; | |
115 | right = t; | |
116 | } | |
117 | } while(t = next); | |
118 | ||
119 | median->left = build_tree(left); | |
120 | median->right = build_tree(right); | |
121 | return median; | |
122 | } | |
123 | ||
124 | struct f_tree * | |
125 | f_new_tree(void) | |
126 | { | |
127 | struct f_tree * ret; | |
128 | ret = cfg_alloc(sizeof(struct f_tree)); | |
129 | ret->left = ret->right = NULL; | |
130 | ret->from.type = ret->to.type = T_VOID; | |
131 | ret->from.val.i = ret->to.val.i = 0; | |
132 | ret->data = NULL; | |
133 | return ret; | |
134 | } | |
9a4037d4 | 135 | |
8dcf2544 PM |
136 | /** |
137 | * same_tree | |
138 | * @t1: first tree to be compared | |
139 | * @t2: second one | |
140 | * | |
141 | * Compares two trees and returns 1 if they are same | |
142 | */ | |
9a4037d4 PM |
143 | int |
144 | same_tree(struct f_tree *t1, struct f_tree *t2) | |
145 | { | |
146 | if ((!!t1) != (!!t2)) | |
147 | return 0; | |
148 | if (!t1) | |
149 | return 1; | |
150 | if (val_compare(t1->from, t2->from)) | |
151 | return 0; | |
152 | if (val_compare(t1->to, t2->to)) | |
153 | return 0; | |
154 | if (!same_tree(t1->left, t2->left)) | |
155 | return 0; | |
156 | if (!same_tree(t1->right, t2->right)) | |
157 | return 0; | |
158 | if (!i_same(t1->data, t2->data)) | |
159 | return 0; | |
160 | return 1; | |
161 | } |