db: optimize matching argument chain sub-trees and fix a few related bugs

This patch adds sub-tree optimization code to the filter DB; it
isn't the most elegant solution - it is fairly ham-fisted in a number
of ways - but it appears to work: identifying sub-tree matches both
in the existing argument chain tree and the new chain being inserted.

CHANGELOG:
 * v3: March 22, 2012
   - Added additional tests from Ashley.
   - Fixed the db_chain_one_nxt() macro.
   - Handle the case where we can't remove a node because it has
     multiple results, but we can remove an action.
 * v2: March 20, 2012
   - Extraced some of the fixes into separate patches to submit
     independently.
   - Leveraged the util_getopt() function in the sub-tree test.
 * v1: March 16, 2012
   - Initial draft.

CC: Ashley Lai <adlai@linux.vnet.ibm.com>
Signed-off-by: Paul Moore <pmoore@redhat.com>

1 files changed, 24 insertions, 0 deletions

diff --git a/src/db.h b/src/db.h
index 4b86e0e..26e40b6 100644
--- a/src/db.h
+++ b/src/db.h
@@ -64,8 +64,32 @@ struct db_arg_chain_tree {
 #define db_chain_eq(x,y) \
 	(((x)->arg == (y)->arg) && \
 	 ((x)->op == (y)->op) && ((x)->datum == (y)->datum))
+#define db_chain_gt(x,y) \
+	(((x)->arg > (y)->arg) || \
+	 (((x)->arg == (y)->arg) && ((x)->op > (y)->op)))
 #define db_chain_leaf(x) \
 	(((x)->act_t_flg != 0) || ((x)->act_f_flg != 0))
+#define db_chain_zombie(x) \
+	(((x)->nxt_t == NULL) && ((x)->nxt_f == NULL) && \
+	 ((x)->act_t_flg == 0) && ((x)->act_f_flg == 0))
+#define db_chain_one_nxt(x) \
+	(((x)->nxt_t != NULL && (x)->nxt_f == NULL) || \
+	 ((x)->nxt_t == NULL && (x)->nxt_f != NULL))
+#define db_chain_one_action(x) \
+	((x)->act_t_flg != (x)->act_f_flg)
+#define db_chain_one_result(x) \
+	(db_chain_one_nxt(x) != db_chain_one_action(x))
+#define db_chain_eq_result(x,y) \
+	((((x)->nxt_t != NULL && (y)->nxt_t != NULL) || \
+	  ((x)->nxt_t == NULL && (y)->nxt_t == NULL)) && \
+	 (((x)->nxt_f != NULL && (y)->nxt_f != NULL) || \
+	  ((x)->nxt_f == NULL && (y)->nxt_f == NULL)) && \
+	 ((x)->act_t_flg == (y)->act_t_flg) && \
+	 ((x)->act_f_flg == (y)->act_f_flg) && \
+	 (((x)->act_t_flg && (x)->act_t == (y)->act_t) || \
+	  (!((x)->act_t_flg))) && \
+	 (((x)->act_f_flg && (x)->act_f == (y)->act_f) || \
+	  (!((x)->act_f_flg))))
 
 struct db_sys_list {
 	/* native syscall number */