]>
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 PM |
13 | /* |
14 | * find_nth - finds n-th element in linked list. Don't be confused by tree structures. | |
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 | /* |
907503ad | 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. | |
72 | */ | |
38506f71 PM |
73 | struct f_tree * |
74 | find_tree(struct f_tree *t, struct f_val val) | |
75 | { | |
76 | if (!t) | |
41be4444 | 77 | return NULL; |
38506f71 PM |
78 | if ((val_compare(t->from, val) != 1) && |
79 | (val_compare(t->to, val) != -1)) | |
80 | return t; | |
81 | if (val_compare(t->from, val) == -1) | |
82 | return find_tree(t->right, val); | |
83 | else | |
84 | return find_tree(t->left, val); | |
85 | } | |
86 | ||
771ae456 PM |
87 | /** |
88 | * build_tree | |
89 | * @from: degenerated tree (linked by tree->left) to be transformed into form suitable for find_tree() | |
90 | * | |
91 | * Transforms denerated tree into balanced tree. | |
92 | */ | |
38506f71 PM |
93 | struct f_tree * |
94 | build_tree(struct f_tree *from) | |
95 | { | |
96 | struct f_tree *median, *t = from, *next, *left = NULL, *right = NULL; | |
97 | ||
98 | median = find_median(from); | |
99 | if (!median) | |
100 | return NULL; | |
101 | ||
102 | do { | |
103 | next = t->left; | |
104 | if (t == median) | |
105 | continue; | |
106 | ||
107 | if (val_compare(median->from, t->from)==1) { | |
108 | t->left = left; | |
109 | left = t; | |
110 | } else { | |
111 | t->left = right; | |
112 | right = t; | |
113 | } | |
114 | } while(t = next); | |
115 | ||
116 | median->left = build_tree(left); | |
117 | median->right = build_tree(right); | |
118 | return median; | |
119 | } | |
120 | ||
121 | struct f_tree * | |
122 | f_new_tree(void) | |
123 | { | |
124 | struct f_tree * ret; | |
125 | ret = cfg_alloc(sizeof(struct f_tree)); | |
126 | ret->left = ret->right = NULL; | |
127 | ret->from.type = ret->to.type = T_VOID; | |
128 | ret->from.val.i = ret->to.val.i = 0; | |
129 | ret->data = NULL; | |
130 | return ret; | |
131 | } | |
9a4037d4 PM |
132 | |
133 | int | |
134 | same_tree(struct f_tree *t1, struct f_tree *t2) | |
135 | { | |
136 | if ((!!t1) != (!!t2)) | |
137 | return 0; | |
138 | if (!t1) | |
139 | return 1; | |
140 | if (val_compare(t1->from, t2->from)) | |
141 | return 0; | |
142 | if (val_compare(t1->to, t2->to)) | |
143 | return 0; | |
144 | if (!same_tree(t1->left, t2->left)) | |
145 | return 0; | |
146 | if (!same_tree(t1->right, t2->right)) | |
147 | return 0; | |
148 | if (!i_same(t1->data, t2->data)) | |
149 | return 0; | |
150 | return 1; | |
151 | } |