diff options
| -rw-r--r-- | filter/Doc | 2 | ||||
| -rw-r--r-- | filter/filter.c | 21 | ||||
| -rw-r--r-- | filter/tree.c | 16 |
3 files changed, 30 insertions, 9 deletions
@@ -1,3 +1,3 @@ H Filters S filter.c -S tree.c
\ No newline at end of file +S tree.c diff --git a/filter/filter.c b/filter/filter.c index 540ce132..d580b55d 100644 --- a/filter/filter.c +++ b/filter/filter.c @@ -25,7 +25,7 @@ * * Filters use structure &f_val for its variables. Each &f_val * contains type and value. Types are constants prefixed with %T_. Few - * of types are special; %T_RETURN can be or-ed with type to indicate + * of types are special; %T_RETURN can be or--ed with type to indicate * that return from function/from whole filter should be * forced. Important thing about &f_val s is that they may be copied * with simple =. That's fine for all currently defined types: strings @@ -71,8 +71,14 @@ pm_path_compare(struct f_path_mask *m1, struct f_path_mask *m2) } } -/* - * val_compare - compare two values, returns -1, 0, 1 on <, =, > and 999 on error +/** + * val_compare + * @v1: first value + * @v2: second value + * + * Compares two values and returns -1, 0, 1 on <, =, > or 999 on error. + * Tree module relies on this giving consistent results so that it can + * build balanced trees. */ int val_compare(struct f_val v1, struct f_val v2) @@ -140,8 +146,13 @@ val_simple_in_range(struct f_val v1, struct f_val v2) return CMP_ERROR; } -/* - * val_in_range - check if @v1 ~ @v2 +/** + * val_in_range + * @v1: element + * @v2: set + * + * Checks if @v1 is element (|~| operator) of @v2. Sets are internally represented as balanced trees, see + * tree.c module (this is not limited to sets, but for non-set cases, val_simple_in_range() is called early). */ int val_in_range(struct f_val v1, struct f_val v2) diff --git a/filter/tree.c b/filter/tree.c index 6bbf1fd8..cd8eef09 100644 --- a/filter/tree.c +++ b/filter/tree.c @@ -11,7 +11,7 @@ #include "filter/filter.h" /* - * find_nth - finds n-th element in linked list. Don't be confused by tree structures. + * find_nth - finds n-th element in linked list. Don't be confused by types, it is really a linked list. */ static struct f_tree * find_nth(struct f_tree *from, int nth) @@ -44,7 +44,7 @@ find_nth(struct f_tree *from, int nth) } /* - * find_median - Gets list linked by left, finds its median, trashes pointers in right + * find_median - Gets list linked by @left, finds its median, trashes pointers in @right. */ static struct f_tree * find_median(struct f_tree *from) @@ -69,6 +69,9 @@ find_median(struct f_tree *from) * 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. + * + * Both set matching and switch() { } construction is implemented using this function, + * thus both are as fast as they can be. */ struct f_tree * find_tree(struct f_tree *t, struct f_val val) @@ -86,7 +89,7 @@ find_tree(struct f_tree *t, struct f_val val) /** * build_tree - * @from: degenerated tree (linked by tree->left) to be transformed into form suitable for find_tree() + * @from: degenerated tree (linked by @tree->left) to be transformed into form suitable for find_tree() * * Transforms denerated tree into balanced tree. */ @@ -130,6 +133,13 @@ f_new_tree(void) return ret; } +/** + * same_tree + * @t1: first tree to be compared + * @t2: second one + * + * Compares two trees and returns 1 if they are same + */ int same_tree(struct f_tree *t1, struct f_tree *t2) { |