]>
git.ipfire.org Git - thirdparty/bird.git/blob - filter/tree.c
2 * Filters: utility functions
4 * Copyright 1998 Pavel Machek <pavel@ucw.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
9 #include "lib/alloca.h"
10 #include "nest/bird.h"
11 #include "conf/conf.h"
12 #include "filter/filter.h"
16 * @t: tree to search in
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.
23 * Both set matching and |switch() { }| construction is implemented using this function,
24 * thus both are as fast as they can be.
27 find_tree(struct f_tree
*t
, struct f_val val
)
31 if ((val_compare(t
->from
, val
) != 1) &&
32 (val_compare(t
->to
, val
) != -1))
34 if (val_compare(t
->from
, val
) == -1)
35 return find_tree(t
->right
, val
);
37 return find_tree(t
->left
, val
);
40 static struct f_tree
*
41 build_tree_rec(struct f_tree
**buf
, int l
, int h
)
51 n
->left
= build_tree_rec(buf
, l
, pos
);
52 n
->right
= build_tree_rec(buf
, pos
+1, h
);
57 tree_compare(const void *p1
, const void *p2
)
59 return val_compare((* (struct f_tree
**) p1
)->from
, (* (struct f_tree
**) p2
)->from
);
64 * @from: degenerated tree (linked by @tree->left) to be transformed into form suitable for find_tree()
66 * Transforms denerated tree into balanced tree.
69 build_tree(struct f_tree
*from
)
71 struct f_tree
*tmp
, *root
;
79 for (tmp
= from
; tmp
!= NULL
; tmp
= tmp
->left
)
83 buf
= alloca(len
* sizeof(struct f_tree
*));
85 buf
= xmalloc(len
* sizeof(struct f_tree
*));
87 /* Convert a degenerated tree into an sorted array */
89 for (tmp
= from
; tmp
!= NULL
; tmp
= tmp
->left
)
92 qsort(buf
, len
, sizeof(struct f_tree
*), tree_compare
);
94 root
= build_tree_rec(buf
, 0, len
);
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;
116 * @t1: first tree to be compared
119 * Compares two trees and returns 1 if they are same
122 same_tree(struct f_tree
*t1
, struct f_tree
*t2
)
124 if ((!!t1
) != (!!t2
))
128 if (val_compare(t1
->from
, t2
->from
))
130 if (val_compare(t1
->to
, t2
->to
))
132 if (!same_tree(t1
->left
, t2
->left
))
134 if (!same_tree(t1
->right
, t2
->right
))
136 if (!i_same(t1
->data
, t2
->data
))
143 tree_node_format(struct f_tree
*t
, buffer
*buf
)
148 tree_node_format(t
->left
, buf
);
150 val_format(t
->from
, buf
);
151 if (val_compare(t
->from
, t
->to
) != 0)
153 buffer_puts(buf
, "..");
154 val_format(t
->to
, buf
);
156 buffer_puts(buf
, ", ");
158 tree_node_format(t
->right
, buf
);
162 tree_format(struct f_tree
*t
, buffer
*buf
)
164 buffer_puts(buf
, "[");
166 tree_node_format(t
, buf
);
168 /* Undo last separator */
169 if (buf
->pos
[-1] != '[')
172 buffer_puts(buf
, "]");