[RFC net-next mlxsw v7] lib: Introduce manager for priority base pruning lookups between tables

[Tal Bar]

An object (e.g. packet) needs to be evaluated against a data base of
prune items (represented by {key, mask, priority}), so that the matching
item with the highest priority is selected to continue process the object.
Usually these items are spread across different tables for better
utilization of the H.W resources.

One way to find this item is to perform multiple (on all the tables) exact
match lookups, each with a different mask. It is possible to reduce the
number of lookups by pruning tables where we know that an higher priority
match does not exist.

The prune library aim: reduce number of lookups (by prune) between tables
within same prune items set (The prune object). As mentioned above pruning
save time complexity by doing lookups only on the relevant tables, this
eliminate the need to search for exact match in other tables based on item
priority and mask.

In order to establish this aim the prune library:
1. Maintain a prune vector for each item.
2. Calculate the prune vector of an inserted item i to table x and the
prune vector of an affected items by this rule. If there is a matching
item j in other table z with lower priority item, item i set to prune
table z (e.g. no need for further lookups). Since item j was pruning
table x the prune library also calculate item j prune vector not to prune
table x.

For further details please check: Documentation/prune.txt

Alongside this, a testing module is introduced as well.

Signed-off-by: Tal Bar <talb at mellanox.com>
---
v6 -> v7:
* revisit the library APIs and update prune library internal implementation.
* Update commit message
* Fix static checks found by smatch and C=2
* Adjust prune_test to use new APIs
v5 -> v6:
* Add notification aggregation capability
* Adjust prune_test to handle notification aggregation
* Add getters for prune_item_nofity and prune_vector_item
* Fix many comments from v5 review
v1 -> v5:
* Fix style issues
---
 Documentation/prune.txt |   56 ++
 MAINTAINERS             |    8 +
 include/linux/prune.h   |   81 +++
 lib/Kconfig             |    6 +
 lib/Kconfig.debug       |   10 +
 lib/Makefile            |    3 +
 lib/prune.c             | 1380 +++++++++++++++++++++++++++++++++++++++++++++++
 lib/test_prune.c        | 1193 ++++++++++++++++++++++++++++++++++++++++
 8 files changed, 2737 insertions(+)
 create mode 100644 Documentation/prune.txt
 create mode 100644 include/linux/prune.h
 create mode 100644 lib/prune.c
 create mode 100644 lib/test_prune.c

diff --git a/Documentation/prune.txt b/Documentation/prune.txt
new file mode 100644
index 0000000..3707508
--- /dev/null
+++ b/Documentation/prune.txt
@@ -0,0 +1,56 @@
+Prune
+=====
+
+Prune is a library which solves how to select which table needs to be searched.
+User can create tables with specific masks. The tables contains masked items
+with priority. Since similar item can be inserted to different tables, there is
+a need to prune between the tables.
+Pruning saves time complexity so that there won't be any need to search in
+other tables.
+
+Requirements
+============
+        * Each item has its own prune-vector.
+	* Prune-vector can be effected by add/remove an item.
+	* User has the ability to determine if items can be compared for pruning.
+
+Database
+========
+Each prune object has a list of tables with mask.
+Each table consist:
+	* hash table for items
+	* list of the corresponding intersection tables (with other tables)
+Each intersection table consists of:
+	* hash table for intersects items
+		* each item contain two lists:
+			1. items of the table owner
+			2. items of other tables (neighbor) in the prune object.
+
+
+Flows
+=====
+Direction of prune calculation:
+-------------------------------
+A*->A: Calculate my own prune vector
+A->A*: Calculate other items prune vector in the prune object
+
+Insert item 'R'
+---------------
+	* A*->A: Insert an item 'R' to a table, calculate its own prune-vector.
+	* A->A*: 'R' was inserted to a table, and we have to calculate the
+		 prune-vectors of other compatible items (in different tables).
+
+Remove item 'R'
+---------------
+	* A->*A: 'R' was removed from a table, this might impact the prune-vectors of
+		 other compatible items (in different tables).
+
+Add table 'T'
+-------------
+	By adding table 'T' to the prune object, prune vector item should be added to the
+	prune-vector of all the items in the prune object.
+
+Remove table 'T'
+----------------
+	By removing table 'T' from the prune object, prune vector item should be removed
+	from the prune-vector of all the items in the prune object.
diff --git a/MAINTAINERS b/MAINTAINERS
index 7ed37c0..2703ae7 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -11489,6 +11489,14 @@ F:	include/linux/sysctl.h
 F:	kernel/sysctl.c
 F:	tools/testing/selftests/sysctl/
 
+PRUNE
+M:	Tal Bar <talb at mellanox.com>
+L:	netdev at vger.kernel.org
+S:	Supported
+F:	lib/prune.c
+F:	lib/test_prune.c
+F:	include/linux/prune.h
+
 PS3 NETWORK SUPPORT
 M:	Geoff Levand <geoff at infradead.org>
 L:	netdev at vger.kernel.org
diff --git a/include/linux/prune.h b/include/linux/prune.h
new file mode 100644
index 0000000..fb24722
--- /dev/null
+++ b/include/linux/prune.h
@@ -0,0 +1,81 @@
+/* SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause */
+/*
+ * include/linux/prune.h - Manager for priority base pruning lookups
+ * between tables.
+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
+ * Copyright (c) 2018 Tal Bar <talb at mellanox.com>
+ */
+
+#ifndef _PRUNE_H
+#define _PRUNE_H
+
+struct prune_item_notification;
+struct prune_table;
+struct prune;
+
+struct prune_item {
+	unsigned long priority; /* Lower number means higher priority  */
+	unsigned long *key; /* Pointer to bitmap */
+	void *priv; /* User item id */
+	struct prune_table *table; /* Table which the item belongs to */
+};
+
+struct prune_vector_item_data {
+	struct prune_table *table; /* The table which should be pruned */
+	bool pruned; /* True if the item is pruning this table */
+};
+
+struct prune_vector_item {
+	struct prune_vector_item_data prune_data;
+	struct list_head list; /* node in table_prune_vector */
+};
+
+struct prune_vector {
+	/* list of prune_vector_items */
+	const struct list_head *table_prune_vector;
+};
+
+struct prune_item_notify {
+	struct prune_item item; /* The item which his prune vector changed */
+	struct prune_vector *prune_vector; /* vector of prune vector item */
+	struct list_head list; /* Node of prune_item_notify */
+};
+
+/**
+ * This structure defines the management hooks for prune object.
+ * The following hooks can be defined; unless noted otherwise, they are
+ * optional and can be filled with a null pointer.
+ *
+ * prune_item_notify:
+ *	Called if there is a change in a the prune vector of an item or items,
+ *	the notification can be sent on one item or more.
+ *
+ * @notification:	An iterable notification object.
+ * @prune_data:		The changed prune_date (equal to all items in the
+ *			notification object
+ */
+struct prune_ops {
+	void (*prune_item_notify)(struct prune_item_notification *notification,
+				  struct prune_vector_item_data *prune_data);
+};
+struct prune *prune_create(unsigned int mask_len, const struct prune_ops *ops,
+			   void *priv);
+void prune_destroy(struct prune *prune);
+struct prune_table *prune_table_create(struct prune *prune, unsigned long *mask,
+				       unsigned int mask_len, void *priv);
+int prune_table_destroy(struct prune_table *table);
+struct prune_item *prune_item_create(struct prune *prune,
+				     struct prune_table *table,
+				     unsigned long priority,
+				     unsigned long *key,
+				     void *priv,
+				     struct prune_vector *prune_vector);
+int prune_item_destroy(struct prune_item *item);
+struct prune_vector_item
+*prune_vector_item_get_next(struct prune_vector *prune_vector,
+			    struct prune_vector_item *vector_item_prev);
+struct prune_item_notify
+*prune_item_notify_get_next(struct prune_item_notification *notification,
+			    struct prune_item_notify *item_notify_prev);
+void *prune_table_priv_get(struct prune_table *table);
+#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index 706836e..997093b 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -592,6 +592,12 @@ config PARMAN
 config PRIME_NUMBERS
 	tristate
 
+config PRUNE
+	tristate "prune"
+	help
+	  This option enables the use of prune manager library for priority
+	  base pruning lookups between tables.
+
 config STRING_SELFTEST
 	tristate "Test string functions"
 
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 8838d11..1e8564a 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1837,6 +1837,16 @@ config TEST_PARMAN
 
 	  If unsure, say N.
 
+config TEST_PRUNE
+	tristate "Perform selftest on pruning tables manager"
+        default n
+        depends on PRUNE
+        help
+          Enable this option to test pruning tables manager
+          (or module load).
+
+          If unsure, say N.
+
 config TEST_LKM
 	tristate "Test module loading with 'hello world' module"
 	default n
diff --git a/lib/Makefile b/lib/Makefile
index 90dc552..84c1cbb 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -69,6 +69,7 @@ obj-$(CONFIG_TEST_UUID) += test_uuid.o
 obj-$(CONFIG_TEST_PARMAN) += test_parman.o
 obj-$(CONFIG_TEST_KMOD) += test_kmod.o
 obj-$(CONFIG_TEST_DEBUG_VIRTUAL) += test_debug_virtual.o
+obj-$(CONFIG_TEST_PRUNE) += test_prune.o
 
 ifeq ($(CONFIG_DEBUG_KOBJECT),y)
 CFLAGS_kobject.o += -DDEBUG
@@ -250,6 +251,8 @@ obj-$(CONFIG_SBITMAP) += sbitmap.o
 
 obj-$(CONFIG_PARMAN) += parman.o
 
+obj-$(CONFIG_PRUNE) += prune.o
+
 # GCC library routines
 obj-$(CONFIG_GENERIC_LIB_ASHLDI3) += ashldi3.o
 obj-$(CONFIG_GENERIC_LIB_ASHRDI3) += ashrdi3.o
diff --git a/lib/prune.c b/lib/prune.c
new file mode 100644
index 0000000..7912dcf
--- /dev/null
+++ b/lib/prune.c
@@ -0,0 +1,1380 @@
+// SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause
+/*
+ * lib/prune.c - Manager for priority base pruning lookups between tables.
+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
+ * Copyright (c) 2018 Tal Bar <talb at mellanox.com>
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/slab.h>
+#include <linux/export.h>
+#include <linux/list.h>
+#include <linux/rhashtable.h>
+#include <linux/prune.h>
+#include <linux/jhash.h>
+#include <linux/bitmap.h>
+
+struct prune_item_notification {
+	/* list of prune_item_notify */
+	struct list_head item_notify_list;
+};
+
+struct prune_table_item_entry {
+	struct prune_item item;
+	/* List of struct prune_vector_item */
+	struct list_head table_prune_vector;
+	struct list_head list; /* Node of item_entry_list (in prune_table) */
+};
+
+struct prune_neighbor_table_items {
+	const struct prune_table_item_entry *entry;
+	struct list_head list;
+};
+
+struct prune_intersec_table_item {
+	const struct prune_table_item_entry *entry;
+	struct list_head list;
+};
+
+struct intersec_item {
+	unsigned long *key;
+};
+
+struct prune_intersec_table_item_entry {
+	struct rhash_head ht_node; /* Member of tablset HT */
+	struct intersec_item ht_key;
+	unsigned int key_len;
+	struct list_head intersec_table_items;
+	struct list_head neighbor_table_items; /* Can be enhanced to rbtree */
+};
+
+struct prune_intersec_table {
+	unsigned long *mask;
+	struct rhashtable items_ht;
+	struct prune_table *neigh_table;
+	struct list_head list; /* Node of intersec_table_list (in prune_table)*/
+};
+
+struct prune_table {
+	struct prune *prune; /* Prune which the table belongs to */
+	unsigned long *mask;
+	struct list_head item_entry_list; /* A list of prune_table_item_entry */
+	/* A list of table structs that contains intersection of the current
+	 * table with the other tables in the prune object.
+	 */
+	struct list_head intersec_table_list;
+	struct list_head list; /* Node of table_list in struct prune */
+	void *priv;
+};
+
+struct prune {
+	const struct prune_ops *ops;
+	unsigned int mask_len;
+	struct list_head table_list;	/* A list of struct prune_table */
+	unsigned int table_cnt;		/* Number of tables in the list */
+	void *priv;
+};
+
+static inline size_t prune_mask_size(unsigned int nbits)
+{
+	return BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+}
+
+static u32 prune_intersec_ht_hash(const void *data, u32 len, u32 seed)
+{
+	u32 jash_len = prune_mask_size(len);
+	const struct intersec_item * const ht_key = data;
+
+	return jhash(ht_key->key, jash_len, seed);
+}
+
+static int prune_intersec_ht_cmp(struct rhashtable_compare_arg *arg,
+				 const void *obj)
+{
+	const struct prune_intersec_table_item_entry *intersec_entry = obj;
+	const struct intersec_item *ht_key = arg->key;
+
+	return !(bitmap_equal(ht_key->key, intersec_entry->ht_key.key,
+			      intersec_entry->key_len));
+}
+
+static struct rhashtable_params intersec_tables_ht_params = {
+	.key_offset = offsetof(struct prune_intersec_table_item_entry, ht_key),
+	.head_offset = offsetof(struct prune_intersec_table_item_entry, ht_node),
+	.obj_cmpfn = prune_intersec_ht_cmp,
+	.hashfn = prune_intersec_ht_hash,
+	.automatic_shrinking = true,
+};
+
+static void prune_table_prune_vector_fini(struct prune_table_item_entry *entry)
+{
+	struct prune_vector_item *vector_item;
+	struct list_head *pos, *tmp;
+
+	list_for_each_safe(pos, tmp, &entry->table_prune_vector) {
+		vector_item = list_entry(pos, typeof(*vector_item), list);
+		list_del(&vector_item->list);
+		kfree(vector_item);
+	}
+}
+
+static int prune_table_prune_vector_init(struct prune *prune,
+				       struct prune_table_item_entry *entry)
+{
+	struct prune_vector_item *vector_item;
+	struct prune_table *table;
+
+	INIT_LIST_HEAD(&entry->table_prune_vector);
+
+	list_for_each_entry(table, &prune->table_list, list) {
+		vector_item = kzalloc(sizeof(*vector_item), GFP_KERNEL);
+		if (!vector_item) {
+			prune_table_prune_vector_fini(entry);
+			return -ENOMEM;
+		}
+		vector_item->prune_data.pruned = true;
+		vector_item->prune_data.table = table;
+		list_add_tail(&vector_item->list,
+			      &entry->table_prune_vector);
+	}
+	return 0;
+}
+
+static struct prune_table_item_entry *
+prune_item_entry_create(struct prune *prune, unsigned long *key,
+			unsigned long priority, void *priv)
+{
+	struct prune_table_item_entry *entry;
+	int err;
+
+	entry = kzalloc(sizeof(*entry), GFP_KERNEL);
+	if (!entry)
+		goto err_entry_alloc;
+
+	entry->item.key = key;
+	entry->item.priority = priority;
+	entry->item.priv = priv;
+
+	err = prune_table_prune_vector_init(prune, entry);
+	if (err)
+		goto err_vector_init;
+
+	return entry;
+
+err_vector_init:
+	kfree(entry);
+err_entry_alloc:
+	return NULL;
+}
+
+static void prune_entry_destroy(struct prune_table_item_entry *entry)
+{
+	prune_table_prune_vector_fini(entry);
+	list_del(&entry->list);
+	kfree(entry);
+}
+
+static bool prune_vector_item_update(const struct list_head *table_prune_list,
+				     struct prune_table *corresponding_table,
+				     bool is_prune)
+{
+	struct prune_vector_item *vector_item;
+
+	list_for_each_entry(vector_item, table_prune_list, list) {
+		/* Find the corresponding prune item and set it */
+		if (vector_item->prune_data.table == corresponding_table &&
+		    vector_item->prune_data.pruned != is_prune) {
+			vector_item->prune_data.pruned = is_prune;
+			return true;
+		}
+	}
+	return false;
+}
+
+static bool prune_vector_set(struct prune_table *table,
+			     struct prune_table *neigh_table,
+			     const struct prune_table_item_entry *entry,
+			     struct prune_neighbor_table_items *neigh_item,
+			     struct prune_intersec_table_item *intersec_item,
+			     bool neigh_items)
+{
+	const struct list_head *prune_list;
+	bool not_prune;
+
+	if (neigh_items) {
+		/* Should not continue pruning in case neighbor priority is
+		 * lower (more important) then the new item
+		 */
+		not_prune = neigh_item->entry->item.priority < entry->item.priority;
+
+	} else {
+		/* Should not continue pruning in case my priority is higher
+		 * (less important) then the new item
+		 */
+		not_prune = intersec_item->entry->item.priority > entry->item.priority;
+	}
+	prune_list = neigh_items ? &entry->table_prune_vector : &intersec_item->entry->table_prune_vector;
+	if (not_prune)
+		return prune_vector_item_update(prune_list, neigh_table, false);
+
+	return false;
+}
+
+static void
+prune_item_entry_to_item_notify(struct prune_item_notify *item_notify,
+				struct prune_intersec_table_item *intersec_item)
+{
+	const struct prune_table_item_entry *entry = intersec_item->entry;
+
+	item_notify->item.priority = entry->item.priority;
+	item_notify->item.key = entry->item.key;
+	item_notify->prune_vector->table_prune_vector = &entry->table_prune_vector;
+}
+
+static void
+prune_item_notify_list_fini(struct prune_item_notification *notify_list)
+{
+	struct prune_item_notify *item_notify;
+	struct list_head *pos, *tmp;
+
+	list_for_each_safe(pos, tmp, &notify_list->item_notify_list) {
+		item_notify = list_entry(pos, typeof(*item_notify), list);
+		list_del(&item_notify->list);
+		kfree(item_notify->prune_vector);
+		kfree(item_notify);
+	}
+}
+
+static int
+prune_item_notify_list_add(struct prune_intersec_table_item *intersec_item,
+			   struct prune_item_notification *notify_list)
+{
+	struct prune_item_notify *item_notify;
+
+	item_notify = kzalloc(sizeof(*item_notify), GFP_KERNEL);
+	if (!item_notify) {
+		if (!list_empty(&notify_list->item_notify_list))
+			prune_item_notify_list_fini(notify_list);
+		return -ENOMEM;
+	}
+	item_notify->prune_vector = kzalloc(sizeof(*item_notify->prune_vector),
+					    GFP_KERNEL);
+	if (!item_notify->prune_vector) {
+		kfree(item_notify);
+		if (!list_empty(&notify_list->item_notify_list))
+			prune_item_notify_list_fini(notify_list);
+		return -ENOMEM;
+	}
+	prune_item_entry_to_item_notify(item_notify, intersec_item);
+	list_add_tail(&item_notify->list, &notify_list->item_notify_list);
+
+	return 0;
+}
+
+/*
+ * prune_item_add_prune_vector_calc - Calculate the prune vector due to a new
+ *				      item add flow
+ * @table:	    The table which the new item belongs to
+ * @intersec_table: The intersection table of the table above
+ * @ht_key:	    A key to store the current masked key
+ * @entry:	    The entry which is being added
+ * @neigh:	    If true search the neighbor_table_items
+ * @notify_list:    The notification list which will returned due to changes in
+ *		    other items in the prune object
+ */
+static bool
+prune_item_add_prune_vector_calc(struct prune_table *table,
+				 struct prune_intersec_table *intersec_table,
+				 struct intersec_item *ht_key,
+				 const struct prune_table_item_entry *entry,
+				 bool neigh,
+				 struct prune_item_notification *notify_list)
+{
+	struct prune_neighbor_table_items *neigh_item;
+	struct prune_intersec_table_item_entry *intersec_entry;
+	struct prune_intersec_table_item *intersec_item;
+	bool prune_vector_chng = false;
+
+	bitmap_clear(ht_key->key, 0, table->prune->mask_len);
+	bitmap_and(ht_key->key, entry->item.key, intersec_table->mask,
+		   table->prune->mask_len);
+
+	intersec_entry = rhashtable_lookup_fast(&intersec_table->items_ht,
+						ht_key,
+						intersec_tables_ht_params);
+	if (!intersec_entry)
+		return false;
+
+	if (neigh) {
+		/* Iterate on neighbor_table_items. In case there is a entry
+		 * with higher priority we should not prune the neighbor table.
+		 */
+		list_for_each_entry(neigh_item,
+				    &intersec_entry->neighbor_table_items,
+				    list) {
+			prune_vector_chng |= prune_vector_set(table,
+					     intersec_table->neigh_table,
+					     entry,
+					     neigh_item,
+					     NULL,
+					     neigh);
+		}
+	} else {
+		/* For my items need to update to prune vector
+		 * corresponding to the new item
+		 */
+		list_for_each_entry(intersec_item,
+				    &intersec_entry->intersec_table_items,
+				    list) {
+			if (prune_vector_set(table,
+					     intersec_table->neigh_table,
+					     entry,
+					     NULL,
+					     intersec_item,
+					     neigh)) {
+				prune_item_notify_list_add(intersec_item,
+							   notify_list);
+			}
+		}
+	}
+	return prune_vector_chng;
+}
+
+static bool
+prune_neigh_item_prio_lower(struct prune_table *table,
+			     const struct prune_table_item_entry *neigh_entry,
+			     const struct prune_table_item_entry *entry)
+{
+	if (neigh_entry->item.priority < entry->item.priority)
+		return true;
+	else
+		return false;
+}
+
+static bool prune_neighbor_list_item_lower_prio(struct prune_table *table,
+						struct prune_intersec_table_item *intersec_item,
+						struct prune_intersec_table_item_entry *intersec_entry)
+{
+	struct prune_neighbor_table_items *neigh_item;
+
+	list_for_each_entry(neigh_item, &intersec_entry->neighbor_table_items,
+			    list) {
+		if (prune_neigh_item_prio_lower(table, neigh_item->entry,
+						 intersec_item->entry))
+			return true;
+	}
+	return false;
+}
+
+/*
+ * prune_item_del_prune_vector_calc - Calculate the prune vector due to an item
+ *				      delete flow
+ * @table:	    The table which the new item belongs to
+ * @intersec_table: The intersection table of the table above
+ * @ht_key:	    A key to store the current masked key
+ * @deleted_entry:  The entry which is being deleted
+ * @notify_list:    The notification list which will returned due to changes in
+ *		    other items in the prune object
+ */
+static void
+prune_item_del_prune_vector_calc(struct prune_table *table,
+				 struct prune_intersec_table *intersec_table,
+				 struct intersec_item *ht_key,
+				 const struct prune_table_item_entry *deleted_entry,
+				 struct prune_item_notification *notify_list)
+{
+	struct prune_intersec_table_item_entry *intersec_entry;
+	struct prune_intersec_table_item *intersec_item;
+	const struct list_head *prune_list;
+	bool to_prune, notify;
+
+	bitmap_clear(ht_key->key, 0, table->prune->mask_len);
+	bitmap_and(ht_key->key, deleted_entry->item.key, intersec_table->mask,
+		   table->prune->mask_len);
+
+	intersec_entry = rhashtable_lookup_fast(&intersec_table->items_ht,
+						ht_key,
+						intersec_tables_ht_params);
+	if (!intersec_entry)
+		return;
+
+	/* Check if one of the items in the neighbor list have higher prio if so
+	 * don't prune
+	 */
+	list_for_each_entry(intersec_item,
+			    &intersec_entry->intersec_table_items, list) {
+		/* Check if there is an item in my neighbor list with higher
+		 * (less important) priority if so --> don't prune
+		 */
+		to_prune = true;
+
+		notify = false;
+		if (!prune_neighbor_list_item_lower_prio(table,
+							  intersec_item,
+							  intersec_entry)) {
+			/* Update intersec_item prune vector for the
+			 * corresponding table to prune due to delete flow
+			 */
+			prune_list = &intersec_item->entry->table_prune_vector;
+			notify = prune_vector_item_update(prune_list, table,
+							  true);
+		}
+		if (notify) {
+			prune_item_notify_list_add(intersec_item,
+						   notify_list);
+		}
+	}
+}
+
+static int
+prune_item_add_prune_vector_set(struct prune_table *table,
+				struct prune_table_item_entry *entry,
+				bool *notify)
+{
+	struct prune_intersec_table *intersec_table;
+	struct intersec_item ht_key;
+	unsigned int mask_len = table->prune->mask_len;
+
+	ht_key.key = kcalloc(1, prune_mask_size(mask_len), GFP_KERNEL);
+	if (!ht_key.key)
+		return -ENOMEM;
+
+	*notify = false;
+	list_for_each_entry(intersec_table, &table->intersec_table_list, list) {
+		*notify |= prune_item_add_prune_vector_calc(table,
+							    intersec_table,
+							    &ht_key, entry,
+							    true,
+							    NULL);
+
+
+	}
+	kfree(ht_key.key);
+	return 0;
+}
+
+static void
+prune_neigh_prune_vector_calc(struct prune_table *table,
+			      struct prune_table *curr_table,
+			      struct intersec_item *ht_key,
+			      const struct prune_table_item_entry *entry,
+			      bool add_item,
+			      struct prune_item_notification *notify_list)
+{
+	struct prune_intersec_table *intersec_table;
+
+	/* Search the corresponding intersection table with
+	 * this table and update the prune vector of items in
+	 * the intersection table if there is no higher
+	 * priority items in their neighbor table.
+	 */
+	list_for_each_entry(intersec_table, &curr_table->intersec_table_list,
+			    list) {
+		if (intersec_table->neigh_table == table) {
+			/* This is the corresponding table */
+			if (add_item)
+				prune_item_add_prune_vector_calc(table,
+								 intersec_table,
+								 ht_key,
+								 entry,
+								 false,
+								 notify_list);
+			else
+				prune_item_del_prune_vector_calc(table,
+								 intersec_table,
+								 ht_key,
+								 entry,
+								 notify_list);
+		}
+	}
+}
+
+static int
+prune_neigh_table_prune_vector_set(struct prune_table *table,
+				   const struct prune_table_item_entry *entry,
+				   bool add_item)
+{
+	struct intersec_item ht_key;
+	struct prune_table *curr_table;
+	struct prune_item_notification notification_list;
+	struct prune_vector_item_data prune_data;
+
+	ht_key.key = kcalloc(1, prune_mask_size(table->prune->mask_len),
+			     GFP_KERNEL);
+	if (!ht_key.key)
+		return -ENOMEM;
+
+	INIT_LIST_HEAD(&notification_list.item_notify_list);
+
+	list_for_each_entry(curr_table, &table->prune->table_list, list) {
+		if (curr_table != table)
+			prune_neigh_prune_vector_calc(table, curr_table,
+						      &ht_key, entry, add_item,
+						      &notification_list);
+	}
+	if (!list_empty(&notification_list.item_notify_list)) {
+		prune_data.pruned = add_item ? false : true;
+		prune_data.table = entry->item.table;
+		table->prune->ops->prune_item_notify(&notification_list,
+						     &prune_data);
+		prune_item_notify_list_fini(&notification_list);
+	}
+	kfree(ht_key.key);
+	return 0;
+}
+
+static struct prune_table_item_entry *
+prune_table_entry_create(struct prune *prune, struct prune_table *table,
+			 unsigned long *key, unsigned long priority, void *priv,
+			 bool *notify)
+{
+	struct prune_table_item_entry *entry;
+	int err;
+
+	if (bitmap_subset(key, table->mask, prune->mask_len) != 1)
+		return ERR_PTR(-EPERM);
+
+	entry = prune_item_entry_create(prune, key, priority, priv);
+	if (!entry)
+		return ERR_PTR(-ENOMEM);
+
+	err = prune_item_add_prune_vector_set(table, entry, notify);
+	if (err) {
+		prune_entry_destroy(entry);
+		return ERR_PTR(err);
+	}
+	list_add_tail(&entry->list, &table->item_entry_list);
+	entry->item.table = table;
+
+	return entry;
+}
+
+void prune_intersec_entry_destroy(struct prune_intersec_table_item_entry *intersec_entry)
+{
+	if (!list_empty(&intersec_entry->intersec_table_items) ||
+	    !list_empty(&intersec_entry->neighbor_table_items))
+		WARN_ON(1); /* Try to free a non empty intersection entry */
+
+	kfree(intersec_entry->ht_key.key);
+	kfree(intersec_entry);
+}
+
+struct prune_intersec_table_item_entry
+*prune_intersec_entry_create(unsigned long *intersec_table_mask,
+			     unsigned long *item_key,
+			     unsigned int mask_len)
+{
+	struct prune_intersec_table_item_entry *intersec_entry;
+
+	intersec_entry = kzalloc(sizeof(*intersec_entry), GFP_KERNEL);
+	if (!intersec_entry)
+		goto err_entry_alloc;
+
+	intersec_entry->ht_key.key = kcalloc(1, prune_mask_size(mask_len),
+					     GFP_KERNEL);
+	if (!intersec_entry->ht_key.key)
+		goto err_key_alloc;
+
+	intersec_entry->key_len = mask_len;
+
+	bitmap_and(intersec_entry->ht_key.key, intersec_table_mask, item_key,
+		   mask_len);
+
+	INIT_LIST_HEAD(&intersec_entry->intersec_table_items);
+	INIT_LIST_HEAD(&intersec_entry->neighbor_table_items);
+
+	return intersec_entry;
+err_key_alloc:
+	kfree(intersec_entry);
+err_entry_alloc:
+	return ERR_PTR(-ENOMEM);
+}
+
+static int prune_intersec_item_add(struct prune_intersec_table *intersec_table,
+				   const struct prune_table_item_entry *entry,
+				   bool neigh)
+{
+	struct prune_neighbor_table_items *neigh_item = NULL;
+	struct prune_intersec_table_item_entry *intersec_entry;
+	struct prune_intersec_table_item *intersec_item = NULL;
+	struct intersec_item ht_key;
+	unsigned int mask_len = entry->item.table->prune->mask_len;
+	bool found = true;
+	int err = 0;
+
+	ht_key.key = kcalloc(1, prune_mask_size(mask_len), GFP_KERNEL);
+	if (!ht_key.key)
+		return -ENOMEM;
+
+	bitmap_and(ht_key.key, intersec_table->mask, entry->item.key, mask_len);
+
+	intersec_entry = rhashtable_lookup_fast(&intersec_table->items_ht,
+						&ht_key,
+						intersec_tables_ht_params);
+	kfree(ht_key.key);
+
+	if (!intersec_entry) {
+		/* create new intersec entry since there ins't already one */
+		intersec_entry = prune_intersec_entry_create(intersec_table->mask,
+							     entry->item.key,
+							     mask_len);
+		if (IS_ERR(intersec_entry)) {
+			err = PTR_ERR(intersec_entry);
+			goto err_entry_alloc;
+		}
+		found = false;
+	}
+
+	if (!neigh) {
+		intersec_item = kzalloc(sizeof(*intersec_item), GFP_KERNEL);
+		if (!intersec_item)
+			goto err_list_item_alloc;
+
+		intersec_item->entry = entry;
+		list_add_tail(&intersec_item->list,
+			      &intersec_entry->intersec_table_items);
+	} else {
+		neigh_item = kzalloc(sizeof(*neigh_item), GFP_KERNEL);
+		if (!neigh_item)
+			goto err_nigh_list_item_alloc;
+
+		neigh_item->entry = entry;
+		list_add_tail(&neigh_item->list,
+			      &intersec_entry->neighbor_table_items);
+	}
+	if (!found) {
+		err = rhashtable_insert_fast(&intersec_table->items_ht,
+					     &intersec_entry->ht_node,
+					     intersec_tables_ht_params);
+		if (err)
+			goto err_rhashtable_insert;
+	}
+	return 0;
+
+err_rhashtable_insert:
+	if (!neigh) {
+		list_del(&intersec_item->list);
+		kfree(intersec_item);
+	} else {
+		list_del(&neigh_item->list);
+		kfree(neigh_item);
+	}
+err_nigh_list_item_alloc:
+err_list_item_alloc:
+	if (!found)
+		prune_intersec_entry_destroy(intersec_entry);
+err_entry_alloc:
+	return err;
+}
+
+static int
+prune_intersec_item_remove(struct prune_intersec_table *intersec_table,
+			   struct prune_table_item_entry *remove_entry,
+			   bool neigh)
+{
+	struct prune_intersec_table_item_entry *intersec_entry;
+	struct prune_neighbor_table_items *neigh_item;
+	struct prune_intersec_table_item *intersec_item;
+	struct intersec_item ht_key;
+	unsigned int mask_len = remove_entry->item.table->prune->mask_len;
+	struct list_head *pos, *tmp;
+
+	ht_key.key = kcalloc(1, prune_mask_size(mask_len), GFP_KERNEL);
+	if (!ht_key.key)
+		return -ENOMEM;
+
+	bitmap_and(ht_key.key, intersec_table->mask, remove_entry->item.key,
+		   mask_len);
+
+	intersec_entry = rhashtable_lookup_fast(&intersec_table->items_ht,
+						&ht_key,
+						intersec_tables_ht_params);
+	if (!intersec_entry) {
+		kfree(ht_key.key);
+		return -EPERM;
+	}
+	if (!neigh) {
+		list_for_each_safe(pos, tmp,
+				   &intersec_entry->intersec_table_items) {
+			intersec_item = list_entry(pos, typeof(*intersec_item),
+						   list);
+			if (intersec_item->entry == remove_entry) {
+				list_del(&intersec_item->list);
+				kfree(intersec_item);
+				break;
+			}
+		}
+	} else {
+		list_for_each_safe(pos, tmp,
+				   &intersec_entry->neighbor_table_items) {
+			neigh_item = list_entry(pos, typeof(*neigh_item), list);
+			if (remove_entry == neigh_item->entry) {
+				list_del(&neigh_item->list);
+				kfree(neigh_item);
+				break;
+			}
+		}
+	}
+	if (list_empty(&intersec_entry->intersec_table_items) &&
+	    list_empty(&intersec_entry->neighbor_table_items)) {
+		rhashtable_remove_fast(&intersec_table->items_ht,
+				       &intersec_entry->ht_node,
+				       intersec_tables_ht_params);
+		prune_intersec_entry_destroy(intersec_entry);
+	}
+	kfree(ht_key.key);
+	return 0;
+}
+
+static struct prune_intersec_table *
+prune_intrsc_table_create(unsigned int mask_len)
+{
+	struct prune_intersec_table *intersec_table;
+
+	intersec_table = kzalloc(sizeof(*intersec_table), GFP_KERNEL);
+	if (!intersec_table)
+		goto err_intersec_table_alloc;
+
+	intersec_table->mask = kcalloc(1, prune_mask_size(mask_len),
+				       GFP_KERNEL);
+	if (!intersec_table->mask)
+		goto err_intersec_table_mask_alloc;
+
+	return intersec_table;
+
+err_intersec_table_mask_alloc:
+	kfree(intersec_table);
+err_intersec_table_alloc:
+	return NULL;
+}
+
+/*
+ * prune_intersec_table_items_update - Update the item of the current table to
+ *				       the nighbor items in the intersection
+ *				       table
+ * @curr_table:	    The table which her items needs to be updated in the
+ *		    intersection table
+ * @intersec_table: The intersection table which needs to be updated
+ * @add_to_neighbor_items: True if items need to be add to neighbor_table_items
+ */
+static void prune_intersec_table_items_update(struct prune_table *curr_table,
+					      struct prune_intersec_table *intersec_table,
+					      bool add_to_neighbor_items)
+{
+	struct prune_table_item_entry *entry;
+
+	list_for_each_entry(entry, &curr_table->item_entry_list, list) {
+		prune_intersec_item_add(intersec_table, entry,
+					add_to_neighbor_items);
+	}
+}
+
+static int prune_intersec_table_add(struct prune *prune,
+				    struct prune_table *new_table,
+				    struct prune_table *curr_table)
+{
+	struct prune_intersec_table *intersec_table1;
+	struct prune_intersec_table *intersec_table2;
+	int err;
+
+	intersec_table1 = prune_intrsc_table_create(prune->mask_len);
+	if (!intersec_table1)
+		goto err_allocate_intersec_table1;
+
+	intersec_table2 = prune_intrsc_table_create(prune->mask_len);
+	if (!intersec_table2)
+		goto err_allocate_intersec_table2;
+
+	bitmap_and(intersec_table1->mask, new_table->mask, curr_table->mask,
+		   prune->mask_len);
+
+	bitmap_and(intersec_table2->mask, new_table->mask, curr_table->mask,
+		   prune->mask_len);
+
+	err = rhashtable_init(&intersec_table1->items_ht,
+			      &intersec_tables_ht_params);
+	if (err)
+		goto err_rhashtable_init_1;
+
+	err = rhashtable_init(&intersec_table2->items_ht,
+			      &intersec_tables_ht_params);
+	if (err)
+		goto err_rhashtable_init_2;
+
+	/* Add new intersection table to the old table */
+	intersec_table1->neigh_table = new_table;
+	prune_intersec_table_items_update(curr_table, intersec_table1, false);
+	list_add(&intersec_table1->list, &curr_table->intersec_table_list);
+	/* Add new intersection table to new table */
+	intersec_table2->neigh_table = curr_table;
+	prune_intersec_table_items_update(curr_table, intersec_table2, true);
+	list_add(&intersec_table2->list, &new_table->intersec_table_list);
+
+	return 0;
+
+err_rhashtable_init_2:
+	rhashtable_destroy(&intersec_table2->items_ht);
+err_rhashtable_init_1:
+err_allocate_intersec_table2:
+	kfree(intersec_table1->mask);
+	kfree(intersec_table1);
+err_allocate_intersec_table1:
+	return -ENOMEM;
+}
+
+/* Add new intersection table to all tables */
+static int prune_intersec_table_build(struct prune *prune,
+				      struct prune_table *new_table)
+{
+	struct prune_table *curr_table;
+	int err;
+
+	list_for_each_entry(curr_table, &prune->table_list, list) {
+		err = prune_intersec_table_add(prune, new_table, curr_table);
+		if (err) {
+			/* TODO: Need to free memory of new intersec tables,
+			 * that have been created.
+			 */
+			return err;
+		}
+	}
+	return 0;
+}
+
+static void prune_intersec_rht_free(void *ptr, void *arg)
+{
+	struct prune_intersec_table_item_entry *rht_node = ptr;
+	struct prune_intersec_table_item *intersec_item;
+	struct prune_neighbor_table_items *neigh_item;
+	struct list_head *pos, *tmp;
+
+	list_for_each_safe(pos, tmp, &rht_node->intersec_table_items) {
+		intersec_item = list_entry(pos, typeof(*intersec_item), list);
+		list_del(&intersec_item->list);
+		kfree(intersec_item);
+	}
+	list_for_each_safe(pos, tmp, &rht_node->neighbor_table_items) {
+		neigh_item = list_entry(pos, typeof(*neigh_item), list);
+		list_del(&neigh_item->list);
+		kfree(neigh_item);
+	}
+	kfree(rht_node->ht_key.key);
+	kfree(rht_node);
+}
+
+static int prune_instersec_table_remove(unsigned int mask_len,
+					struct prune_table *table,
+					struct prune_table *table_removed)
+{
+	struct prune_intersec_table *curr_intersec_table;
+	struct list_head *intersec_pos, *tmp;
+	struct rhashtable *items_rht;
+	unsigned long *curr_mask;
+	int err;
+
+	curr_mask = kcalloc(1, prune_mask_size(mask_len), GFP_KERNEL);
+	if (!curr_mask)
+		return -ENOMEM;
+
+	bitmap_and(curr_mask, table->mask, table_removed->mask, mask_len);
+
+	list_for_each_safe(intersec_pos, tmp, &table->intersec_table_list) {
+		curr_intersec_table = list_entry(intersec_pos,
+						 typeof(*curr_intersec_table),
+						 list);
+		if (bitmap_equal(curr_mask, curr_intersec_table->mask,
+				 mask_len)) {
+			list_del(&curr_intersec_table->list);
+			items_rht = &curr_intersec_table->items_ht;
+			rhashtable_free_and_destroy(items_rht,
+						    prune_intersec_rht_free,
+						    NULL);
+			kfree(curr_intersec_table->mask);
+			kfree(curr_intersec_table);
+			err = 0;
+			goto end;
+		}
+	}
+	goto err_flow;
+
+err_flow:
+	err = -EPERM;
+	WARN_ON(1); /* Didn't found the wanted intersection table */
+end:
+	kfree(curr_mask);
+	return err;
+}
+
+static int
+prune_intersec_list_item_add(struct prune_table *item_added_table,
+			     struct prune_table *table,
+			     const struct prune_table_item_entry *entry,
+			     bool neigh_item)
+{
+	struct prune_intersec_table *curr_intersec_table;
+	int err;
+
+	list_for_each_entry(curr_intersec_table, &table->intersec_table_list,
+			    list) {
+		/* Add the item only to the corresponding tables */
+		if (!neigh_item ||
+		    curr_intersec_table->neigh_table == item_added_table) {
+			err = prune_intersec_item_add(curr_intersec_table,
+						      entry,
+						      neigh_item);
+			if (err)
+				return err;
+		}
+	}
+	return 0;
+}
+
+static int
+prune_intersec_list_item_remove(struct prune_table *remove_item_table,
+				struct prune_table *table,
+				struct prune_table_item_entry *remove_entry,
+				bool neigh_item)
+{
+	struct prune_intersec_table *curr_intersec_table;
+	int err;
+
+	list_for_each_entry(curr_intersec_table, &table->intersec_table_list,
+			    list) {
+		if (curr_intersec_table->neigh_table == remove_item_table ||
+		    !neigh_item) {
+			err = prune_intersec_item_remove(curr_intersec_table,
+							 remove_entry,
+							 neigh_item);
+			if (err)
+				return err;
+		}
+	}
+	return 0;
+}
+
+static void prune_table_item_vector_remove(struct prune_table *table,
+					struct prune_table *del_table)
+{
+	struct prune_vector_item *vector_item;
+	struct prune_table_item_entry *entry;
+	struct list_head *pos, *tmp;
+
+	list_for_each_entry(entry, &table->item_entry_list, list) {
+		list_for_each_safe(pos, tmp, &entry->table_prune_vector) {
+			vector_item = list_entry(pos,
+					    typeof(*vector_item),
+					    list);
+			if (vector_item->prune_data.table == del_table) {
+				list_del(&vector_item->list);
+				kfree(vector_item);
+				break;
+			}
+		}
+	}
+}
+
+static int prune_table_item_vector_add(struct prune_table *table,
+				       struct prune_table *new_table)
+{
+	struct prune_vector_item *vector_item;
+	struct prune_table_item_entry *entry;
+
+	list_for_each_entry(entry, &table->item_entry_list, list) {
+		vector_item = kzalloc(sizeof(*vector_item), GFP_KERNEL);
+		if (!vector_item) {
+			prune_table_item_vector_remove(table, new_table);
+			return -ENOMEM;
+		}
+		vector_item->prune_data.pruned = true;
+		vector_item->prune_data.table = new_table;
+		list_add_tail(&vector_item->list,
+			      &entry->table_prune_vector);
+	}
+	return 0;
+}
+
+/*
+ * prune_item_prune_table_add - Add new vector_item to each item in each table
+ * @prune: The prune object which contains all tables
+ * @new_table: The new table which needs to be pointed by the vector_item
+ */
+static int prune_item_prune_table_add(struct prune *prune,
+				       struct prune_table *new_table)
+{
+	struct prune_table *table;
+	int err;
+
+	list_for_each_entry(table, &prune->table_list, list) {
+		err = prune_table_item_vector_add(table, new_table);
+		if (err)
+			return err;
+	}
+	return 0;
+}
+
+static void prune_item_prune_table_remove(struct prune *prune,
+					  struct prune_table *del_table)
+{
+	struct prune_table *table;
+
+	list_for_each_entry(table, &prune->table_list, list) {
+		if (del_table != table)
+			prune_table_item_vector_remove(table, del_table);
+	}
+}
+
+/**
+ * prune_create - Creates a prune object which manage the pruning vector
+ *		  between tables
+ * @mask_len:	Sets the mask len (nbits) for all tables in the prune
+ *		object.
+ * @ops:	caller-specific callbacks
+ * @priv:	Pointer to a private user data.
+ *
+ * Returns a pointer to newly created prune instance in case of success,
+ * otherwise it returns NULL.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+struct prune *prune_create(unsigned int mask_len, const struct prune_ops *ops,
+			   void *priv)
+{
+	struct prune *prune;
+
+	if (!ops)
+		return NULL;
+
+	prune = kzalloc(sizeof(*prune), GFP_KERNEL);
+	if (!prune)
+		return NULL;
+
+	prune->table_cnt = 0;
+	prune->priv = priv;
+	prune->mask_len = mask_len;
+	INIT_LIST_HEAD(&prune->table_list);
+	prune->ops = ops;
+	intersec_tables_ht_params.key_len = mask_len;
+
+	return prune;
+}
+EXPORT_SYMBOL(prune_create);
+
+/**
+ * prune_destroy - Destroys the prune object
+ * @prune: Prune object
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+void prune_destroy(struct prune *prune)
+{
+	WARN_ON(prune->table_cnt > 0 || !list_empty(&prune->table_list));
+
+	kfree(prune);
+}
+EXPORT_SYMBOL(prune_destroy);
+
+/**
+ * prune_table_create - Creates new table with specific mask and adds it to the
+ *			prune object
+ * @prune:	Prune object
+ * @mask:	Table mask - all items key should match this mask
+ * @mask_len:	The leangth of mask - number of bits
+ * @priv:	user data
+ *
+ * Returns a pointer to newly created prune table instance in case of success,
+ * otherwise it returns negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ * This function may sleep so you must not call it from interrupt
+ * context or with spin locks held.
+ */
+
+struct prune_table *prune_table_create(struct prune *prune, unsigned long *mask,
+				       unsigned int mask_len, void *priv)
+{
+	int err;
+	struct prune_table *table;
+
+	if (prune->mask_len != mask_len)
+		return ERR_PTR(-EPERM);
+
+	table = kzalloc(sizeof(*table), GFP_KERNEL);
+	if (!table)
+		return ERR_PTR(-ENOMEM);
+
+	table->mask = kcalloc(1, prune_mask_size(prune->mask_len), GFP_KERNEL);
+	if (!table->mask) {
+		err = -ENOMEM;
+		goto err_mask_alloc_fail;
+	}
+	bitmap_copy(table->mask, mask, prune->mask_len);
+	table->priv = priv;
+	INIT_LIST_HEAD(&table->item_entry_list);
+	INIT_LIST_HEAD(&table->intersec_table_list);
+
+	/* Enlarge the prune vector of all item with the new table */
+	err = prune_item_prune_table_add(prune, table);
+	if (err)
+		goto err_free_mask;
+
+	err = prune_intersec_table_build(prune, table);
+	if (err)
+		goto err_free_mask;
+
+	list_add_tail(&table->list, &prune->table_list);
+	table->prune = prune;
+	prune->table_cnt++;
+
+	return table;
+
+err_free_mask:
+	kfree(table->mask);
+err_mask_alloc_fail:
+	kfree(table);
+	return ERR_PTR(err);
+}
+EXPORT_SYMBOL(prune_table_create);
+
+/**
+ * prune_table_destroy - Removes a table from the prune object and destroys it.
+ * @prune:	Prune object
+ * @table:	Table to be removed.
+ *
+ * Returns 0 in case of success, negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ * This function may sleep so you must not call it from interrupt
+ * context or with spin locks held.
+ */
+int prune_table_destroy(struct prune_table *table)
+{
+	struct prune_intersec_table *curr_intersec_table;
+	struct prune_table *curr_table;
+	struct rhashtable *items_rht;
+	struct list_head *pos, *tmp;
+	struct prune *prune;
+	int err;
+
+	prune = table->prune;
+
+	if (prune->table_cnt == 0 || !list_empty(&table->item_entry_list)) {
+		return -EPERM;
+	}
+
+	else if (prune->table_cnt > 1) {
+		/* Remove the intersection table from neighbor tables */
+		list_for_each_entry(curr_table, &prune->table_list, list) {
+			if (curr_table != table) {
+				err = prune_instersec_table_remove
+						(prune->mask_len,
+						 curr_table,
+						 table);
+				if (err)
+					return err;
+			}
+		}
+		/* Remove all intersection tables from this table */
+		list_for_each_safe(pos, tmp, &table->intersec_table_list) {
+			curr_intersec_table =
+					list_entry(pos,
+						   typeof(*curr_intersec_table),
+						   list);
+			list_del(&curr_intersec_table->list);
+			items_rht = &curr_intersec_table->items_ht;
+			rhashtable_free_and_destroy(items_rht,
+						    prune_intersec_rht_free,
+						    NULL);
+			kfree(curr_intersec_table->mask);
+			kfree(curr_intersec_table);
+		}
+	}
+	WARN_ON_ONCE(!list_empty(&table->intersec_table_list));
+
+	prune_item_prune_table_remove(prune, table);
+
+	list_del(&table->list);
+	kfree(table->mask);
+	kfree(table);
+
+	prune->table_cnt--;
+
+	return 0;
+}
+EXPORT_SYMBOL(prune_table_destroy);
+
+/**
+ * prune_item_add - Adds an item to a table.
+ * @prune:		Prune object
+ * @table:		Add the item to this table.
+ * @key:		Item key (bit array) - must be corresponding to
+ *			table mask and length (not copied by thE library)
+ * @priority:		Item priority
+ * @priv:		User data (item id)
+ * @prune_vector:	Contains the data on which tables should not be pruned.
+ *			all others pruned (default)
+ *
+ * Returns a pointer to newly created prune item instance in case of success,
+ * otherwise it returns negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+struct prune_item *prune_item_create(struct prune *prune,
+				     struct prune_table *table,
+				     unsigned long priority,
+				     unsigned long *key,
+				     void *priv,
+				     struct prune_vector *prune_vector)
+{
+	struct prune_table_item_entry *entry;
+	struct prune_table *curr_table;
+	bool notify;
+	int err;
+
+	entry = prune_table_entry_create(prune, table, key, priority, priv,
+					 &notify);
+	if (IS_ERR(entry)) {
+		err = PTR_ERR(entry);
+		return ERR_PTR(err);
+	}
+	if (notify)
+		prune_vector->table_prune_vector = &entry->table_prune_vector;
+	else
+		prune_vector->table_prune_vector = NULL;
+
+	/* Add the item to the intersection tables of all tables*/
+	list_for_each_entry(curr_table, &prune->table_list, list) {
+		err = prune_intersec_list_item_add(table, curr_table, entry,
+						   curr_table != table ?
+								  true : false);
+		if (err) {
+			prune_entry_destroy(entry);
+			return ERR_PTR(err);
+		}
+	}
+	/* Update prune vector of the corresponding items of the neighbor
+	 * tables
+	 */
+	err = prune_neigh_table_prune_vector_set(table, entry, true);
+	if (err) {
+		prune_item_destroy(&entry->item);
+		return ERR_PTR(err);
+	}
+	return &entry->item;
+}
+EXPORT_SYMBOL(prune_item_create);
+
+/**
+ * prune_item_destroy - removes an item from a table
+ * @prune:	prune object
+ * @table:	Remove the item from this table.
+ * @item:	the item to remove.
+ *
+ * Returns 0 in case of success, negative number to indicate an error.
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+int prune_item_destroy(struct prune_item *item)
+{
+	struct prune_table_item_entry *entry;
+	struct prune_table *curr_table;
+	struct prune_table *table;
+	struct prune *prune;
+	int err;
+
+	table = item->table;
+	prune = table->prune;
+
+	entry = container_of(item, struct prune_table_item_entry, item);
+	/* Remove the item from tables in the intersect tables */
+	list_for_each_entry(curr_table, &prune->table_list, list) {
+		err = prune_intersec_list_item_remove(table, curr_table, entry,
+						      curr_table != table ?
+								  true : false);
+		if (err)
+			return err;
+	}
+
+	/* Update prune vector of the corresponding items of the neighbor
+	 * prune_table
+	 */
+	err = prune_neigh_table_prune_vector_set(table, entry, false);
+	if (err)
+		return err;
+
+	prune_entry_destroy(entry);
+
+	return 0;
+}
+EXPORT_SYMBOL(prune_item_destroy);
+
+/**
+ * prune_vector_item_get_next - gets the next vector item
+ * @item_notify:	item_notify object
+ * @vector_item_prev:	NULL for the first item otherwise the next one.
+ *
+ * Returns a pointer to a vector item in case of success,
+ * NULL if there is no more items
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+struct prune_vector_item
+*prune_vector_item_get_next(struct prune_vector *prune_vector,
+			    struct prune_vector_item *vector_item_prev)
+{
+	struct prune_vector_item *vector_item;
+
+	if (prune_vector->table_prune_vector == NULL)
+		return NULL;
+
+	if (!vector_item_prev) {
+		return list_first_entry(prune_vector->table_prune_vector,
+					typeof(*vector_item), list);
+	} else {
+		vector_item = list_next_entry(vector_item_prev, list);
+		if (&vector_item->list == prune_vector->table_prune_vector)
+			return NULL;
+		else
+			return vector_item;
+	}
+}
+EXPORT_SYMBOL(prune_vector_item_get_next);
+
+/**
+ * prune_item_notify_get_next - gets the next item notify
+ * @notification:	notification object
+ * @item_notify_prev:	NULL for the first item otherwise the next one.
+ *
+ * Returns a pointer to an item notify in case of success,
+ * NULL if there is no more items
+ *
+ * Note: It's the user responsibility to care for synchronization.
+ */
+struct prune_item_notify
+*prune_item_notify_get_next(struct prune_item_notification *notification,
+			    struct prune_item_notify *item_notify_prev)
+{
+	struct prune_item_notify *item_notify;
+
+	if (!item_notify_prev) {
+		return list_first_entry(&notification->item_notify_list,
+					typeof(*item_notify), list);
+	} else {
+		item_notify = list_next_entry(item_notify_prev, list);
+		if (&item_notify->list == &notification->item_notify_list)
+			return NULL;
+		else
+			return item_notify;
+	}
+}
+EXPORT_SYMBOL(prune_item_notify_get_next);
+
+void *prune_table_priv_get(struct prune_table *table)
+{
+	return table->priv;
+}
+EXPORT_SYMBOL(prune_table_priv_get);
+
+MODULE_LICENSE("Dual BSD/GPL");
+MODULE_AUTHOR("Tal Bar<talb at mellanox.com>");
+MODULE_DESCRIPTION("Prune lookup table manager");
diff --git a/lib/test_prune.c b/lib/test_prune.c
new file mode 100644
index 0000000..07a7af0
--- /dev/null
+++ b/lib/test_prune.c
@@ -0,0 +1,1193 @@
+// SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause
+/*
+ * lib/test_prune.c - Test module for prune
+ * Copyright (c) 2018 Mellanox Technologies. All rights reserved.
+ * Copyright (c) 2018 Tal Bar <talb at mellanox.com>
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/err.h>
+#include <linux/prune.h>
+#include <linux/bitmap.h>
+#include <linux/slab.h>
+
+#define TABLES_2 (2)
+#define TABLES_3 (3)
+#define TABLES_4 (4)
+#define ITEMS_3 (3)
+#define ITEMS_6 (6)
+#define ITEMS_8 (8)
+
+struct test_prune_table_attr {
+	unsigned long *mask;
+	unsigned int mask_len; /* Number of bits */
+	unsigned int table_id;
+};
+
+struct test_prune_item {
+	unsigned long priority; /* Lower number means higher priority  */
+	unsigned long *key;
+	void *priv; /* user item id */
+	struct prune_vector prune_vector;
+};
+
+struct test_prune_vector_item {
+	unsigned int table_id;
+	bool is_pruned; /* True if the item is pruning this table */
+};
+
+static inline size_t prune_mask_size(unsigned int nbits)
+{
+	return BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+}
+
+static void test_prune_notification_print(struct prune_item_notify *item_notify,
+					  bool print)
+{
+	struct prune_vector_item *vector_item = NULL;
+	void *priv;
+	int i;
+
+
+	if (print) {
+		i = 0;
+		pr_info("item prio: %lu\n", item_notify->item.priority);
+		pr_info("item mask: %lu\n", *item_notify->item.key);
+		pr_info("item from table *: %p\n", item_notify->item.table);
+
+		while ((vector_item =
+			prune_vector_item_get_next(item_notify->prune_vector,
+						   vector_item))) {
+			priv = prune_table_priv_get(vector_item->prune_data.table);
+			pr_info("i = [%d], table priv: %lu\t is prune: %s\t pruned table *: %p\n",
+				i,
+				(uintptr_t)priv,
+				vector_item->prune_data.pruned ? "Yes" : "No",
+				vector_item->prune_data.table);
+			i++;
+		}
+	}
+}
+
+static bool test_prune_check_prune_vector(struct prune_vector *prune_vector,
+					  bool *prune_val_arr,
+					  int arr_len)
+{
+	struct prune_vector_item *vector_item = NULL;
+	bool case_passed = true;
+	int table_id = 0;
+	void *priv;
+	#define MAX_CASE (5)
+
+	while ((vector_item =
+		prune_vector_item_get_next(prune_vector, vector_item))) {
+		if (table_id == arr_len || table_id > MAX_CASE) {
+			WARN(1, "test didn't pass too many items in prune vector");
+			return false;
+		}
+
+		priv = prune_table_priv_get(vector_item->prune_data.table);
+		switch (table_id) {
+		case MAX_CASE - 5:
+			case_passed =
+				(uintptr_t)priv == table_id &&
+				vector_item->prune_data.pruned == prune_val_arr[0];
+			break;
+		case MAX_CASE - 4:
+			case_passed =
+				(uintptr_t)priv == table_id &&
+				vector_item->prune_data.pruned == prune_val_arr[1];
+			break;
+		case MAX_CASE - 3:
+			case_passed =
+				(uintptr_t)priv == table_id &&
+				vector_item->prune_data.pruned == prune_val_arr[2];
+			break;
+		case MAX_CASE - 2:
+			case_passed =
+				(uintptr_t)priv == table_id &&
+				vector_item->prune_data.pruned == prune_val_arr[3];
+			break;
+		case MAX_CASE - 1:
+			case_passed =
+				(uintptr_t)priv == table_id &&
+				vector_item->prune_data.pruned == prune_val_arr[4];
+			break;
+		case MAX_CASE:
+			case_passed =
+				(uintptr_t)priv == table_id &&
+				vector_item->prune_data.pruned == prune_val_arr[5];
+			break;
+		default:
+			case_passed = false;
+			break;
+		}
+		table_id++;
+
+		if (!case_passed) {
+			WARN(1, "test didn't pass for table [%d]", table_id);
+			return case_passed;
+		}
+	}
+	return case_passed;
+}
+
+static bool test_prune_check_case(struct prune_item_notify *item_notify,
+				  unsigned int prio,
+				  bool *prune_val_arr,
+				  int arr_len,
+				  int test_case)
+{
+	bool case_passed = true;
+
+	if (item_notify->item.priority != prio) {
+		WARN(1, "test case [%d] didn't pass. Incorrect priority [%lu]",
+		     test_case,
+		     item_notify->item.priority);
+		return false;
+	}
+
+	case_passed = test_prune_check_prune_vector(item_notify->prune_vector,
+						    prune_val_arr, arr_len);
+
+	if (!case_passed)
+		WARN(1, "test case [%d] didn't pass", test_case);
+
+	return case_passed;
+}
+
+static void
+test_prune_subsequent_notify(struct prune_item_notification *notification,
+			     struct prune_vector_item_data *prune_data)
+{
+	bool prune_value_case0[2] = {true, false};
+	bool prune_value_case1[3] = {true, false, false};
+	bool prune_value_case2[3] = {true, true, false};
+	bool prune_value_case3[3] = {true, true, true};
+	struct prune_item_notify *item_notify = NULL;
+	static int test_case;
+
+	while ((item_notify =
+		prune_item_notify_get_next(notification, item_notify))) {
+		test_prune_notification_print(item_notify, false);
+
+		switch (test_case) {
+		case 0:
+			test_prune_check_case(item_notify, 10,
+					      prune_value_case0,
+					      ARRAY_SIZE(prune_value_case0),
+					      test_case);
+			break;
+		case 1:
+			test_prune_check_case(item_notify, 10,
+					      prune_value_case1,
+					      ARRAY_SIZE(prune_value_case1),
+					      test_case);
+			break;
+		case 2:
+			test_prune_check_case(item_notify, 5,
+					      prune_value_case2,
+					      ARRAY_SIZE(prune_value_case2),
+					      test_case);
+			break;
+		case 3:
+			test_prune_check_case(item_notify, 8,
+					      prune_value_case3,
+					      ARRAY_SIZE(prune_value_case3),
+					      test_case);
+			break;
+		default:
+			WARN(1, "unexpected test case %d", test_case);
+			break;
+		}
+		test_case++;
+	}
+}
+
+static void
+test_prune_flows_1_notify(struct prune_item_notification *notification,
+			  struct prune_vector_item_data *prune_data)
+{
+	bool prune_value_arr_case0[2] = {false, true};
+	bool prune_value_arr_case1[2] = {true, true};
+	bool prune_value_arr_case2[2] = {true, true};
+	struct prune_item_notify *item_notify = NULL;
+	static int test_case;
+
+	while ((item_notify =
+		prune_item_notify_get_next(notification, item_notify))) {
+		test_prune_notification_print(item_notify, false);
+
+		switch (test_case) {
+		case 0:
+			test_prune_check_case(item_notify, 10,
+					      prune_value_arr_case0,
+					      ARRAY_SIZE(prune_value_arr_case0),
+					      test_case);
+			break;
+		case 1:
+			test_prune_check_case(item_notify, 7,
+					      prune_value_arr_case1,
+					      ARRAY_SIZE(prune_value_arr_case1),
+					      test_case);
+			break;
+		case 2:
+			test_prune_check_case(item_notify, 10,
+					      prune_value_arr_case2,
+					      ARRAY_SIZE(prune_value_arr_case2),
+					      test_case);
+			break;
+		default:
+			WARN(1, "unexpected test case %d", test_case);
+			break;
+		}
+		test_case++;
+	}
+}
+
+static void
+test_prune_flows_2_notify(struct prune_item_notification *notification,
+			  struct prune_vector_item_data *prune_data)
+{
+	struct prune_item_notify *item_notify = NULL;
+	bool prune_value_arr_case0[2] = {false, true};
+	bool prune_value_arr_case1[3] = {true, false, true};
+	bool prune_value_arr_case2[3] = {true, true, true};
+	static int test_case;
+
+	while ((item_notify =
+		prune_item_notify_get_next(notification, item_notify))) {
+		test_prune_notification_print(item_notify, false);
+
+		switch (test_case) {
+		case 0:
+			test_prune_check_case(item_notify, 7,
+					      prune_value_arr_case0,
+					      ARRAY_SIZE(prune_value_arr_case0),
+					      test_case);
+			break;
+		case 1:
+			test_prune_check_case(item_notify, 7,
+					      prune_value_arr_case1,
+					      ARRAY_SIZE(prune_value_arr_case1),
+					      test_case);
+			break;
+		case 2:
+			test_prune_check_case(item_notify, 5,
+					      prune_value_arr_case2,
+					      ARRAY_SIZE(prune_value_arr_case2),
+					      test_case);
+			break;
+		default:
+			WARN(1, "unexpected test case %d", test_case);
+			break;
+		}
+		test_case++;
+	}
+}
+
+static void
+test_prune_basic_notify(struct prune_item_notification *notification,
+			struct prune_vector_item_data *prune_data)
+{
+	bool prune_value_arr_case0[3] = {true, false, true};
+	bool prune_value_arr_case1[3] = {true, false, false};
+	bool prune_value_arr_case2[3] = {true, true, false};
+	bool prune_value_arr_case3[3] = {true, false, true};
+	bool prune_value_arr_case4[3] = {true, true, true};
+	struct prune_item_notify *item_notify = NULL;
+	static int test_case;
+
+	while ((item_notify =
+		prune_item_notify_get_next(notification, item_notify))) {
+		test_prune_notification_print(item_notify, false);
+
+		switch (test_case) {
+		case 0:
+			test_prune_check_case(item_notify, 3,
+					      prune_value_arr_case0,
+					      ARRAY_SIZE(prune_value_arr_case0),
+					      test_case);
+			break;
+		case 1:
+			test_prune_check_case(item_notify, 3,
+					      prune_value_arr_case1,
+					      ARRAY_SIZE(prune_value_arr_case1),
+					      test_case);
+			break;
+		case 2:
+			test_prune_check_case(item_notify, 2,
+					      prune_value_arr_case2,
+					      ARRAY_SIZE(prune_value_arr_case2),
+					      test_case);
+			break;
+		case 3:
+			test_prune_check_case(item_notify, 3,
+					      prune_value_arr_case3,
+					      ARRAY_SIZE(prune_value_arr_case3),
+					      test_case);
+			break;
+		case 4:
+			test_prune_check_case(item_notify, 2,
+					      prune_value_arr_case4,
+					      ARRAY_SIZE(prune_value_arr_case4),
+					      test_case);
+			break;
+		default:
+			WARN(1, "unexpected test case %d", test_case);
+			break;
+		}
+		test_case++;
+	}
+}
+
+static const struct prune_ops test_prune_add_new_table_subsequent_ops = {
+	.prune_item_notify = test_prune_subsequent_notify
+};
+
+static const struct prune_ops test_prune_flows_add_delete_items_1_ops = {
+	.prune_item_notify = test_prune_flows_1_notify
+};
+
+static const struct prune_ops test_prune_flows_add_delete_items_2_ops = {
+	.prune_item_notify = test_prune_flows_2_notify
+};
+
+static const struct prune_ops test_prune_basic_ops = {
+	.prune_item_notify = test_prune_basic_notify
+};
+
+static int table_attr_create(struct test_prune_table_attr *table_attr,
+			     unsigned int mask_len,
+			     unsigned int table_cnt)
+{
+	unsigned long i, j;
+
+	for (i = 0; i < table_cnt; i++) {
+		table_attr[i].mask = kcalloc(1, prune_mask_size(mask_len),
+					     GFP_KERNEL);
+		if (!table_attr[i].mask) {
+			if (i > 0) {
+				for (j = i - 1; j == 0; j--)
+					kfree(table_attr[j].mask);
+			}
+			return -ENOMEM;
+		}
+		table_attr[i].mask_len = mask_len;
+		table_attr[i].table_id = i;
+	}
+	return 0;
+}
+
+static void table_attr_destroy(struct test_prune_table_attr *table_attr,
+			       unsigned int table_cnt)
+{
+	int i;
+
+	for (i = 0; i < table_cnt; i++)
+		kfree(table_attr[i].mask);
+}
+
+static void prune_item_arr_destroy(struct test_prune_item *pi_arr,
+				   unsigned int pi_cnt)
+{
+	int i;
+
+	for (i = 0; i < pi_cnt; i++)
+		kfree(pi_arr[i].key);
+}
+
+static int test_prune_item_arr_create(struct test_prune_item *tpi_arr,
+				      unsigned int pi_cnt,
+				      unsigned int pi_nbits)
+{
+	int i, j = 0;
+
+	for (i = 0; i < pi_cnt; i++) {
+		tpi_arr[i].key = kcalloc(1, prune_mask_size(pi_nbits),
+					 GFP_KERNEL);
+		if (!tpi_arr[i].key) {
+			if (i > 0)
+				for (j = i - 1; j > -1; j--)
+					kfree(tpi_arr[j].key);
+			return -ENOMEM;
+		}
+		bitmap_clear(tpi_arr[i].key, 0, pi_nbits);
+	}
+	return 0;
+}
+
+/*
+ * Basic test: test add / remove table and item without checking their prune
+ * vector
+ */
+static int test_prune_basic(void)
+{
+	struct test_prune_table_attr table_attr[TABLES_3];
+	struct prune_table *table_arr[TABLES_3];
+	struct test_prune_item tpi_arr[ITEMS_3];
+	struct prune_item *item_arr[ITEMS_3];
+	unsigned int nbits = 40;
+	struct prune *prune;
+	int err;
+
+	prune = prune_create(nbits, &test_prune_basic_ops, NULL);
+	if (IS_ERR(prune))
+		return PTR_ERR(prune);
+
+	err = table_attr_create(table_attr, nbits, TABLES_3);
+	if (err)
+		return err;
+
+	err = test_prune_item_arr_create(tpi_arr, ITEMS_3, nbits);
+	if (err)
+		return err;
+
+	bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len);
+	bitmap_set(table_attr[0].mask, 0, 2);
+	table_arr[0] = prune_table_create(prune, table_attr[0].mask,
+					  table_attr[0].mask_len,
+					  (int *)(uintptr_t)table_attr[0].table_id);
+	if (IS_ERR(table_arr[0]))
+		return PTR_ERR(table_arr[0]);
+
+	bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len);
+	bitmap_set(table_attr[1].mask, 1, 2);
+	table_arr[1] = prune_table_create(prune, table_attr[1].mask,
+					  table_attr[1].mask_len,
+					  (int *)(uintptr_t)table_attr[1].table_id);
+	if (IS_ERR(table_arr[1]))
+		return PTR_ERR(table_arr[1]);
+
+	bitmap_clear(table_attr[2].mask, 0, table_attr[2].mask_len);
+	bitmap_set(table_attr[2].mask, 2, 2);
+	table_arr[2] = prune_table_create(prune, table_attr[2].mask,
+					  table_attr[2].mask_len,
+					  (int *)(uintptr_t)table_attr[2].table_id);
+	if (IS_ERR(table_arr[2]))
+		return PTR_ERR(table_arr[2]);
+
+	tpi_arr[0].priority = 3;
+	tpi_arr[0].priv = NULL;
+	bitmap_set(tpi_arr[0].key, 0, 2);
+	item_arr[0] = prune_item_create(prune, table_arr[0],
+					tpi_arr[0].priority, tpi_arr[0].key,
+					tpi_arr[0].priv,
+					&tpi_arr[0].prune_vector);
+	if (IS_ERR(item_arr[0]))
+		return -EBADE;
+
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[0].prune_vector, NULL, 0))
+		return -EBADE;
+
+	tpi_arr[1].priority = 2;
+	tpi_arr[1].priv = NULL;
+	bitmap_set(tpi_arr[1].key, 1, 2);
+	item_arr[1] = prune_item_create(prune, table_arr[1],
+					tpi_arr[1].priority,
+					tpi_arr[1].key, tpi_arr[1].priv,
+					&tpi_arr[1].prune_vector);
+	if (IS_ERR(item_arr[1]))
+		return -EBADE;
+
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[1].prune_vector, NULL, 0))
+		return -EBADE;
+
+	tpi_arr[2].priority = 1;
+	tpi_arr[2].priv = NULL;
+	bitmap_set(tpi_arr[2].key, 2, 2);
+
+	item_arr[2] = prune_item_create(prune, table_arr[2],
+					tpi_arr[2].priority,
+					tpi_arr[2].key, tpi_arr[2].priv,
+					&tpi_arr[2].prune_vector);
+	if (IS_ERR(item_arr[1]))
+		return -EBADE;
+
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[2].prune_vector, NULL, 0))
+		return -EBADE;
+
+	err = prune_item_destroy(item_arr[2]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[0]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[1]);
+	if (err)
+		return err;
+
+	prune_table_destroy(table_arr[0]);
+
+	prune_table_destroy(table_arr[1]);
+
+	prune_table_destroy(table_arr[2]);
+
+	prune_destroy(prune);
+
+	prune_item_arr_destroy(tpi_arr, ITEMS_3);
+	table_attr_destroy(table_attr, TABLES_3);
+
+	return 0;
+}
+
+static int test_prune_flows_add_delete_items_1(void)
+{
+	struct test_prune_table_attr table_attr[TABLES_2];
+	struct prune_table *table_arr[TABLES_2];
+	struct test_prune_item tpi_arr[ITEMS_3];
+	struct prune_item *item_arr[ITEMS_3];
+	bool prune_val_arr_2[2] =  {true, false};
+	unsigned int nbits = 40;
+	struct prune *prune;
+	int err;
+
+	prune = prune_create(nbits, &test_prune_flows_add_delete_items_1_ops,
+			     NULL);
+
+	if (IS_ERR(prune))
+		return PTR_ERR(prune);
+
+	err = table_attr_create(table_attr, nbits, TABLES_2);
+	if (err)
+		return err;
+
+	err = test_prune_item_arr_create(tpi_arr, ITEMS_3, nbits);
+	if (err)
+		return err;
+
+	/* Create table with mask u.u.u.x.x - table 0*/
+	bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len);
+	bitmap_set(table_attr[0].mask, 0, 24); /* Set care on #1-3 byte*/
+	table_arr[0] = prune_table_create(prune, table_attr[0].mask,
+					  table_attr[0].mask_len,
+					  (int *)(uintptr_t)table_attr[0].table_id);
+	if (IS_ERR(table_arr[0]))
+		return PTR_ERR(table_arr[0]);
+
+	/* Create table with mask x.u.u.u.x */
+	bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len);
+	bitmap_set(table_attr[1].mask, 8, 24); /* Set care on #2-4 byte*/
+	table_arr[1] = prune_table_create(prune, table_attr[1].mask,
+					  table_attr[1].mask_len,
+					  (int *)(uintptr_t)table_attr[1].table_id);
+	if (IS_ERR(table_arr[0]))
+		return PTR_ERR(table_arr[0]);
+
+	/* Create item0 x.2.3.4.x prio 5 */
+	tpi_arr[0].priority = 5;
+	tpi_arr[0].priv = NULL;
+	bitmap_set(tpi_arr[0].key, 14, 1); /* Set 2 on #2 byte*/
+	bitmap_set(tpi_arr[0].key, 22, 2); /* Set 3 on #3 byte*/
+	bitmap_set(tpi_arr[0].key, 29, 1); /* Set 4 on #4 byte*/
+
+	/* Create item1 x.2.3.5.x prio 10*/
+	tpi_arr[1].priority = 10;
+	tpi_arr[1].priv = NULL;
+	bitmap_set(tpi_arr[1].key, 14, 1); /* Set 2 on #2 byte*/
+	bitmap_set(tpi_arr[1].key, 22, 2); /* Set 3 on #3 byte*/
+	bitmap_set(tpi_arr[1].key, 29, 1); /* Set 5 on #4 byte*/
+	bitmap_set(tpi_arr[1].key, 31, 1); /* Set 5 on #4 byte*/
+
+	/* Add item0: x.2.3.4.x to table 1 */
+	item_arr[0] = prune_item_create(prune, table_arr[1],
+					tpi_arr[0].priority,
+					tpi_arr[0].key, tpi_arr[0].priv,
+					&tpi_arr[0].prune_vector);
+	if (IS_ERR(item_arr[0]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[0].prune_vector, NULL, 0))
+		return -EBADE;
+
+	/* Expected prune vector for item1 and item2
+	 * table 0 prune
+	 * table 1 prune
+	 * --> Shoudn't not get notification
+	 */
+
+	/* Add item1: x.2.3.5.x to table 1 */
+	item_arr[1] = prune_item_create(prune, table_arr[1],
+					tpi_arr[1].priority,
+					tpi_arr[1].key, tpi_arr[1].priv,
+					&tpi_arr[1].prune_vector);
+	if (IS_ERR(item_arr[1]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[1].prune_vector, NULL, 0))
+		return -EBADE;
+
+	/* Expected prune vector for both item
+	 * table 0 prune
+	 * table 1 prune
+	 * --> Shoudn't not get notification
+	 */
+
+	/* Create item2 1.2.3.x.x prio 7 */
+	tpi_arr[2].priority = 7;
+	tpi_arr[2].priv = NULL;
+	bitmap_set(tpi_arr[2].key, 7, 1); /* Set 1 on #1 byte*/
+	bitmap_set(tpi_arr[2].key, 14, 1); /* Set 2 on #2 byte*/
+	bitmap_set(tpi_arr[2].key, 22, 2); /* Set 3 on #3 byte*/
+
+	/* Add item2: 1.2.3.x.x prio 7 to table 0 */
+	item_arr[2] = prune_item_create(prune, table_arr[0],
+					tpi_arr[2].priority,
+					tpi_arr[2].key, tpi_arr[2].priv,
+					&tpi_arr[2].prune_vector);
+	if (IS_ERR(item_arr[2]))
+		return -EBADE;
+
+	if (!test_prune_check_prune_vector(&tpi_arr[2].prune_vector,
+					   prune_val_arr_2, 2))
+		return -EBADE;
+
+	/* Expected prune vector per item
+	 * item0 in table 1 (x.2.3.4.x prio 10):
+	 *	table 0 prune (no change)
+	 *	table 1 prune (no change)
+	 * --> shoudn't not get notification
+	 * item1 in table 1 (x.2.3.5.x prio 5):
+	 *	table 0 don't prune (changed)
+	 *	table 1 prune (changed)
+	 * --> Should get notification
+	 * item2 in table 0 (1.2.3.x.x prio 7):
+	 *	table 0 prune (no change)
+	 *	table 1 don't prune (no change)
+	 * --> Should get notification
+	 */
+
+	/* Delete item: 0: (x.2.3.4.x prio 10 from table 1 */
+	err = prune_item_destroy(item_arr[0]);
+	if (err)
+		return err;
+
+	/* Expected prune vector
+	 * item0: item is deleted
+	 * item1 table 1 (x.2.3.5.x prio 5):
+	 *	table 0 don't prune
+	 *	table 1 prune
+	 * item2 table 0 (1.2.3.x.x prio 7):
+	 *	table 0 prune
+	 *	table 1 prune (changed)
+	 */
+
+	/* Delete item: 2: (1.2.3.x.x prio 7) from table 0 */
+	err = prune_item_destroy(item_arr[2]);
+	if (err)
+		return err;
+
+	/* Expected prune vector
+	 * item0: item is deleted
+	 * item1 table 1 (x.2.3.5.x prio 5):
+	 *	table 0 prune (changed)
+	 *	table 1 prune
+	 * item2 item is deleted
+	 *
+	 */
+
+	/* Delete item: 1: (x.2.3.5.x prio 5) from table 1 */
+	err = prune_item_destroy(item_arr[1]);
+	if (err)
+		return err;
+
+	err = prune_table_destroy(table_arr[0]);
+	if (err)
+		return err;
+
+	err = prune_table_destroy(table_arr[1]);
+	if (err)
+		return err;
+
+	prune_destroy(prune);
+
+	prune_item_arr_destroy(tpi_arr, ITEMS_3);
+	table_attr_destroy(table_attr, TABLES_2);
+
+	return 0;
+}
+
+static int test_prune_flows_add_delete_item_2(void)
+{
+	bool prune_val_arr_3[3] = {false, false, true};
+	bool prune_val_arr_5[3] = {false, true, true};
+	struct test_prune_table_attr table_attr[TABLES_3];
+	struct prune_table *table_arr[TABLES_3];
+	struct test_prune_item tpi_arr[ITEMS_6];
+	struct prune_item *item_arr[ITEMS_6];
+	unsigned int nbits = 40;
+	struct prune *prune;
+	int err;
+
+	prune = prune_create(nbits, &test_prune_flows_add_delete_items_2_ops,
+			     NULL);
+	if (IS_ERR(prune))
+		return PTR_ERR(prune);
+
+	err = table_attr_create(table_attr, nbits, TABLES_3);
+	if (err)
+		return err;
+
+	err = test_prune_item_arr_create(tpi_arr, ITEMS_6, nbits);
+	if (err)
+		return err;
+
+	/* Tables:
+	 *	table 0: x.x.u.u.u
+	 *	table 1: u.u.u.x.x
+	 *	table 2: x.u.x.x.x
+	 */
+
+	/* Create table with mask x.x.u.u.u - table 0 */
+	bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len);
+	bitmap_set(table_attr[0].mask, 16, 24); /* Set care on #3-5 byte*/
+
+	/* Create table with mask u.u.u.x.x - table 1 */
+	bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len);
+	bitmap_set(table_attr[1].mask, 0, 24); /* Set care on #1-3 byte*/
+
+	/* Create table with mask x.u.x.x.x - table 2 */
+	bitmap_clear(table_attr[2].mask, 2, table_attr[2].mask_len);
+	bitmap_set(table_attr[2].mask, 8, 8); /* Set care on #2 byte*/
+
+	/* Create rules */
+	/* Create item0 x.x.3.5.5 prio 7 */
+	tpi_arr[0].priority = 7;
+	tpi_arr[0].priv = NULL;
+	bitmap_set(tpi_arr[0].key, 22, 2); /* Set 3 on #3 byte */
+	bitmap_set(tpi_arr[0].key, 29, 1); /* Set 5 on #4 byte */
+	bitmap_set(tpi_arr[0].key, 31, 1); /* Set 5 on #4 byte */
+	bitmap_set(tpi_arr[0].key, 37, 1); /* Set 5 on #5 byte */
+	bitmap_set(tpi_arr[0].key, 39, 1); /* Set 5 on #5 byte */
+
+	/* Create item1 1.2.3.x.x  prio 7 */
+	tpi_arr[1].priority = 7;
+	tpi_arr[1].priv = NULL;
+	bitmap_set(tpi_arr[1].key, 7, 1); /* Set 1 on #1 byte */
+	bitmap_set(tpi_arr[1].key, 14, 1); /* Set 2 on #2 byte */
+	bitmap_set(tpi_arr[1].key, 22, 2); /* Set 3 on #3 byte */
+
+	/* Create item2 x.x.3.5.x prio 3 */
+	tpi_arr[2].priority = 3;
+	tpi_arr[2].priv = NULL;
+	bitmap_set(tpi_arr[2].key, 22, 2); /* Set 3 on #3 byte */
+	bitmap_set(tpi_arr[2].key, 29, 1); /* Set 5 on #4 byte */
+	bitmap_set(tpi_arr[2].key, 31, 1); /* Set 5 on #4 byte */
+
+	/* Create item3 x.2.x.x.x prio 10 */
+	tpi_arr[3].priority = 10;
+	tpi_arr[3].priv = NULL;
+	bitmap_set(tpi_arr[3].key, 14, 1); /* Set 2 on #2 byte */
+
+	/* Create item4 x.x.x.x.6 prio 7 */
+	tpi_arr[4].priority = 7;
+	tpi_arr[4].priv = NULL;
+	bitmap_set(tpi_arr[4].key, 37, 2); /* Set 6 on #5 byte */
+
+	/* Create item5 2.2.3.x.x prio 5 */
+	tpi_arr[5].priority = 5;
+	tpi_arr[5].priv = NULL;
+	bitmap_set(tpi_arr[5].key, 7, 1); /* Set 2 on #1 byte */
+	bitmap_set(tpi_arr[5].key, 14, 1); /* Set 2 on #2 byte */
+	bitmap_set(tpi_arr[5].key, 22, 2); /* Set 3 on #3 byte */
+
+	table_arr[0] = prune_table_create(prune, table_attr[0].mask,
+					  table_attr[0].mask_len,
+					  (int *)(uintptr_t)table_attr[0].table_id);
+	if (IS_ERR(table_arr[0]))
+		return PTR_ERR(table_arr[0]);
+
+	item_arr[0] = prune_item_create(prune, table_arr[0],
+					tpi_arr[0].priority,
+					tpi_arr[0].key, tpi_arr[0].priv,
+					&tpi_arr[0].prune_vector);
+	if (IS_ERR(item_arr[0]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[0].prune_vector, NULL, 0))
+		return -EBADE;
+
+	table_arr[1] = prune_table_create(prune, table_attr[1].mask,
+					  table_attr[1].mask_len,
+					  (int *)(uintptr_t)table_attr[1].table_id);
+	if (IS_ERR(table_arr[1]))
+		return PTR_ERR(table_arr[1]);
+
+	item_arr[1] = prune_item_create(prune, table_arr[1],
+					tpi_arr[1].priority,
+					tpi_arr[1].key, tpi_arr[1].priv,
+					&tpi_arr[1].prune_vector);
+	if (IS_ERR(item_arr[1]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[1].prune_vector, NULL, 0))
+		return -EBADE;
+
+	item_arr[2] = prune_item_create(prune, table_arr[0],
+					tpi_arr[2].priority,
+					tpi_arr[2].key, tpi_arr[2].priv,
+					&tpi_arr[2].prune_vector);
+	if (IS_ERR(item_arr[2]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[2].prune_vector, NULL, 0))
+		return -EBADE;
+
+	table_arr[2] = prune_table_create(prune, table_attr[2].mask,
+					  table_attr[2].mask_len,
+					  (int *)(uintptr_t)table_attr[2].table_id);
+	if (IS_ERR(table_arr[2]))
+		return PTR_ERR(table_arr[2]);
+
+	item_arr[3] = prune_item_create(prune, table_arr[2],
+					tpi_arr[3].priority,
+					tpi_arr[3].key, tpi_arr[3].priv,
+					&tpi_arr[3].prune_vector);
+	if (IS_ERR(item_arr[3]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[3].prune_vector,
+					   prune_val_arr_3, 3))
+		return -EBADE;
+
+	item_arr[4] = prune_item_create(prune, table_arr[0],
+					tpi_arr[4].priority,
+					tpi_arr[4].key, tpi_arr[4].priv,
+					&tpi_arr[4].prune_vector);
+	if (IS_ERR(item_arr[4]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[4].prune_vector, NULL, 0))
+		return -EBADE;
+
+	item_arr[5] = prune_item_create(prune, table_arr[1],
+					tpi_arr[5].priority,
+					tpi_arr[5].key, tpi_arr[5].priv,
+					&tpi_arr[5].prune_vector);
+	if (IS_ERR(item_arr[5]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[5].prune_vector,
+					   prune_val_arr_5, 3)) {
+		return -EBADE;
+	}
+
+	/* Free resources */
+	err = prune_item_destroy(item_arr[0]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[1]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[2]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[3]);
+	if (err)
+		return err;
+
+	err = prune_table_destroy(table_arr[2]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[4]);
+	if (err)
+		return err;
+
+	err = prune_table_destroy(table_arr[0]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[5]);
+	if (err)
+		return err;
+
+	err = prune_table_destroy(table_arr[1]);
+	if (err)
+		return err;
+
+	prune_destroy(prune);
+
+	prune_item_arr_destroy(tpi_arr, ITEMS_6);
+	table_attr_destroy(table_attr, TABLES_3);
+
+	return 0;
+}
+
+static int test_prune_add_new_table_with_item_subsequent_to_curr_tables(void)
+{
+	struct test_prune_table_attr table_attr[TABLES_3];
+	struct prune_table *table_arr[TABLES_3];
+	struct test_prune_item tpi_arr[ITEMS_8];
+	struct prune_item *item_arr[ITEMS_8];
+	bool prune_val_arr_5[2] = {false, true};
+	unsigned int nbits = 40;
+	struct prune *prune;
+	int err;
+
+	prune = prune_create(nbits, &test_prune_add_new_table_subsequent_ops,
+			     NULL);
+	if (IS_ERR(prune))
+		return PTR_ERR(prune);
+
+	err = table_attr_create(table_attr, nbits, TABLES_3);
+	if (err)
+		return err;
+
+	err = test_prune_item_arr_create(tpi_arr, ITEMS_8, nbits);
+	if (err)
+		return err;
+
+	/* Tables:
+	 *      table 0: u.u.u.x.x
+	 *      table 1: x.u.u.u.x
+	 *      table 2: x.x.u.u.u
+	 */
+
+	/* Create table with mask u.u.u.x.x - table 0 */
+	bitmap_clear(table_attr[0].mask, 0, table_attr[0].mask_len);
+	bitmap_set(table_attr[0].mask, 0, 24); /* Set care on #1-3 byte*/
+	table_arr[0] = prune_table_create(prune, table_attr[0].mask,
+					  table_attr[0].mask_len,
+					  (int *)(uintptr_t)table_attr[0].table_id);
+	if (IS_ERR(table_arr[0]))
+		return PTR_ERR(table_arr[0]);
+
+	/* Create table with mask x.u.u.u.x table 1 */
+	bitmap_clear(table_attr[1].mask, 0, table_attr[1].mask_len);
+	bitmap_set(table_attr[1].mask, 8, 24); /* Set care on #2-4 byte*/
+	table_arr[1] = prune_table_create(prune, table_attr[1].mask,
+					  table_attr[1].mask_len,
+					  (int *)(uintptr_t)table_attr[1].table_id);
+	if (IS_ERR(table_arr[1]))
+		return PTR_ERR(table_arr[1]);
+
+	/* Create rules */
+	/* Create item0 1.2.3.x.x prio 10 */
+	tpi_arr[0].priority = 10;
+	tpi_arr[0].priv = NULL;
+	bitmap_set(tpi_arr[0].key, 7, 1); /* Set 1 on #1 byte */
+	bitmap_set(tpi_arr[0].key, 14, 1); /* Set 2 on #2 byte */
+	bitmap_set(tpi_arr[0].key, 22, 2); /* Set 3 on #3 byte */
+
+	/* Create item1 x.2.3.4.x prio 3 */
+	tpi_arr[1].priority = 3;
+	tpi_arr[1].priv = NULL;
+	bitmap_set(tpi_arr[1].key, 14, 1); /* Set 2 on #2 byte */
+	bitmap_set(tpi_arr[1].key, 22, 2); /* Set 3 on #3 byte */
+	bitmap_set(tpi_arr[1].key, 29, 1); /* Set 4 on #4 byte */
+
+	/* Create item2 x.x.3.9.9 prio 1 */
+	tpi_arr[2].priority = 1;
+	tpi_arr[2].priv = NULL;
+	bitmap_set(tpi_arr[2].key, 22, 2); /* Set 3 on #3 byte */
+	bitmap_set(tpi_arr[2].key, 28, 1); /* Set 9 on #4 byte */
+	bitmap_set(tpi_arr[2].key, 31, 1); /* Set 9 on #4 byte */
+	bitmap_set(tpi_arr[2].key, 36, 1); /* Set 9 on #5 byte */
+	bitmap_set(tpi_arr[2].key, 39, 1); /* Set 9 on #5 byte */
+
+	/* Create item3 2.2.4.x.x prio 5 */
+	tpi_arr[3].priority = 5;
+	tpi_arr[3].priv = NULL;
+	bitmap_set(tpi_arr[3].key, 6, 1); /* Set 2 on #1 byte */
+	bitmap_set(tpi_arr[3].key, 14, 1); /* Set 2 on #2 byte */
+	bitmap_set(tpi_arr[3].key, 21, 1); /* Set 4 on #3 byte */
+
+	/* Create item4 x.x.4.5.x prio 2 */
+	tpi_arr[4].priority = 2;
+	tpi_arr[4].priv = NULL;
+	bitmap_set(tpi_arr[4].key, 21, 1); /* Set 4 on #3 byte */
+	bitmap_set(tpi_arr[4].key, 29, 1); /* Set 5 on #4 byte */
+	bitmap_set(tpi_arr[4].key, 31, 1); /* Set 5 on #4 byte */
+
+	/* Create item5 x.2.4.7.x prio 8 */
+	tpi_arr[5].priority = 8;
+	tpi_arr[5].priv = NULL;
+	bitmap_set(tpi_arr[5].key, 14, 1); /* Set 2 on #2 byte */
+	bitmap_set(tpi_arr[5].key, 21, 1); /* Set 4 on #3 byte */
+	bitmap_set(tpi_arr[5].key, 29, 3); /* Set 7 on #4 byte */
+
+	/* Create item6 x.2.x.9.x prio 8 */
+	tpi_arr[6].priority = 8;
+	tpi_arr[6].priv = NULL;
+	bitmap_set(tpi_arr[6].key, 14, 1); /* Set 2 on #2 byte */
+	bitmap_set(tpi_arr[6].key, 28, 1); /* Set 9 on #4 byte */
+	bitmap_set(tpi_arr[6].key, 31, 1); /* Set 9 on #4 byte */
+
+	item_arr[0] = prune_item_create(prune, table_arr[0],
+					tpi_arr[0].priority,
+					tpi_arr[0].key, tpi_arr[0].priv,
+					&tpi_arr[0].prune_vector);
+	if (IS_ERR(item_arr[0]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[0].prune_vector, NULL, 0))
+		return -EBADE;
+
+	item_arr[1] = prune_item_create(prune, table_arr[1],
+					tpi_arr[1].priority,
+					tpi_arr[1].key, tpi_arr[1].priv,
+					&tpi_arr[1].prune_vector);
+	if (IS_ERR(item_arr[1]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[1].prune_vector, NULL, 0))
+		return -EBADE;
+
+	item_arr[3] = prune_item_create(prune, table_arr[0],
+					tpi_arr[3].priority,
+					tpi_arr[3].key, tpi_arr[3].priv,
+					&tpi_arr[3].prune_vector);
+	if (IS_ERR(item_arr[3]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[3].prune_vector, NULL, 0))
+		return -EBADE;
+
+	item_arr[5] = prune_item_create(prune, table_arr[1],
+					tpi_arr[5].priority,
+					tpi_arr[5].key, tpi_arr[5].priv,
+					&tpi_arr[5].prune_vector);
+	if (IS_ERR(item_arr[5]))
+		return -EBADE;
+
+	if (!test_prune_check_prune_vector(&tpi_arr[5].prune_vector,
+					   prune_val_arr_5, 2))
+		return -EBADE;
+
+	item_arr[6] = prune_item_create(prune, table_arr[1],
+					tpi_arr[6].priority,
+					tpi_arr[6].key, tpi_arr[6].priv,
+					&tpi_arr[6].prune_vector);
+	if (IS_ERR(item_arr[6]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[6].prune_vector, NULL, 0))
+		return -EBADE;
+
+	/* Create table with mask x.x.u.u.u table 2 */
+	bitmap_clear(table_attr[2].mask, 0, table_attr[2].mask_len);
+	bitmap_set(table_attr[2].mask, 16, 24); /* Set care on #2-5 byte*/
+	table_arr[2] = prune_table_create(prune, table_attr[2].mask,
+					  table_attr[2].mask_len,
+					  (int *)(uintptr_t)table_attr[2].table_id);
+	if (IS_ERR(table_arr[2]))
+		return PTR_ERR(table_arr[2]);
+
+	item_arr[2] = prune_item_create(prune, table_arr[2],
+					tpi_arr[2].priority,
+					tpi_arr[2].key, tpi_arr[2].priv,
+					&tpi_arr[2].prune_vector);
+	if (IS_ERR(item_arr[2]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[2].prune_vector, NULL, 0))
+		return -EBADE;
+
+	item_arr[4] = prune_item_create(prune, table_arr[2],
+					tpi_arr[4].priority,
+					tpi_arr[4].key, tpi_arr[4].priv,
+					&tpi_arr[4].prune_vector);
+	if (IS_ERR(item_arr[4]))
+		return -EBADE;
+	/* default prune vector */
+	if (!test_prune_check_prune_vector(&tpi_arr[4].prune_vector, NULL, 0))
+		return -EBADE;
+
+	err = prune_item_destroy(item_arr[0]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[1]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[2]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[3]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[4]);
+	if (err)
+		return err;
+
+	err = prune_table_destroy(table_arr[2]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[5]);
+	if (err)
+		return err;
+
+	err = prune_item_destroy(item_arr[6]);
+	if (err)
+		return err;
+
+	err = prune_table_destroy(table_arr[0]);
+	if (err)
+		return err;
+
+	err = prune_table_destroy(table_arr[1]);
+	if (err)
+		return err;
+
+	prune_destroy(prune);
+
+	prune_item_arr_destroy(tpi_arr, ITEMS_8);
+	table_attr_destroy(table_attr, TABLES_3);
+
+	return 0;
+}
+
+static int test_prune(void)
+{
+	int err;
+
+	err = test_prune_basic();
+	if (err)
+		return err;
+
+	err = test_prune_flows_add_delete_items_1();
+	if (err)
+		return err;
+
+	err = test_prune_add_new_table_with_item_subsequent_to_curr_tables();
+	if (err)
+		return err;
+
+	err = test_prune_flows_add_delete_item_2();
+	if (err)
+		return err;
+
+	return 0;
+}
+
+static int __init test_prune_init(void)
+{
+		return test_prune();
+}
+
+static void __exit test_prune_exit(void)
+{
+}
+
+module_init(test_prune_init);
+module_exit(test_prune_exit);
+
+MODULE_LICENSE("Dual BSD/GPL");
+MODULE_AUTHOR("Tal Bar <talb at mellanox.com>");
+MODULE_DESCRIPTION("Test module for prune");
-- 
2.8.0