summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--filter/Doc3
-rw-r--r--filter/filter.c10
-rw-r--r--filter/tree.c24
3 files changed, 33 insertions, 4 deletions
diff --git a/filter/Doc b/filter/Doc
index 407a44b..a21b6fa 100644
--- a/filter/Doc
+++ b/filter/Doc
@@ -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)
{