diff options
| -rw-r--r-- | filter/Doc | 3 | ||||
| -rw-r--r-- | filter/filter.c | 10 | ||||
| -rw-r--r-- | filter/tree.c | 24 |
3 files changed, 33 insertions, 4 deletions
@@ -1,2 +1,3 @@ H Filters -S filter.c
\ No newline at end of file +S filter.c +S tree.c
\ No newline at end of file diff --git a/filter/filter.c b/filter/filter.c index b4e0105..540ce13 100644 --- a/filter/filter.c +++ b/filter/filter.c @@ -260,6 +260,16 @@ rta_cow(void) * * Interpret given tree of filter instructions. This is core function * of filter system and does all the hard work. + * + * Each instruction has 4 fields: code (which is instruction code), + * aux (which is extension to instruction code, typically type), + * arg1 and arg2 - arguments. Depending on instruction, arguments + * are either integers, or pointers to instruction trees. Common + * instructions like +, that have two expressions as arguments use + * TWOARGS macro to get both of them evaluated. + * + * &f_val structures are copied around, so there are no problems with + * memory managment. */ static struct f_val interpret(struct f_inst *what) diff --git a/filter/tree.c b/filter/tree.c index 1d32969..56b3209 100644 --- a/filter/tree.c +++ b/filter/tree.c @@ -10,7 +10,9 @@ #include "conf/conf.h" #include "filter/filter.h" -/* Finds n-th item in list linked by right. Trashes pointers in right. */ +/* + * find_nth - finds n-th element in linked list. Don't be confused by tree structures. + */ static struct f_tree * find_nth(struct f_tree *from, int nth) { @@ -41,7 +43,9 @@ find_nth(struct f_tree *from, int nth) return find_nth(left, nth); } -/* Gets list linked by left, finds its median, trashes pointers in right */ +/* + * Gets list linked by left, finds its median, trashes pointers in right */ + */ static struct f_tree * find_median(struct f_tree *from) { @@ -57,6 +61,15 @@ find_median(struct f_tree *from) return find_nth(from, cnt/2); } +/** + * find_tree + * @t: tree to search in + * @val: value to find + * + * Search for given value in the tree. I relies on fact that sorted tree is populated + * by &f_val structures (that can be compared by val_compare()). In each node of tree, + * either single value (then t->from==t->to) or range is present. + */ struct f_tree * find_tree(struct f_tree *t, struct f_val val) { @@ -71,7 +84,12 @@ find_tree(struct f_tree *t, struct f_val val) return find_tree(t->left, val); } -/* Gets list linked by left */ +/** + * build_tree + * @from: degenerated tree (linked by tree->left) to be transformed into form suitable for find_tree() + * + * Transforms denerated tree into balanced tree. + */ struct f_tree * build_tree(struct f_tree *from) { |