lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:   Fri,  6 Aug 2021 11:58:17 +0200
From:   Lukas Czerner <lczerner@...hat.com>
To:     tytso@....edu
Cc:     linux-ext4@...r.kernel.org
Subject: [PATCH 4/7] e2fsprogs: remove augmented rbtree functionality

Rbtree code was originally taken from linux kernel. This includes the
augmented rbtree functionality, however this was never intended to be
used and is not used still. Just remove it.

Signed-off-by: Lukas Czerner <lczerner@...hat.com>
---
 lib/ext2fs/rbtree.c | 68 ---------------------------------------------
 lib/ext2fs/rbtree.h |  8 ------
 2 files changed, 76 deletions(-)

diff --git a/lib/ext2fs/rbtree.c b/lib/ext2fs/rbtree.c
index 5b92099d..74426fa6 100644
--- a/lib/ext2fs/rbtree.c
+++ b/lib/ext2fs/rbtree.c
@@ -280,74 +280,6 @@ void ext2fs_rb_erase(struct rb_node *node, struct rb_root *root)
 		__rb_erase_color(child, parent, root);
 }
 
-static void ext2fs_rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
-{
-	struct rb_node *parent;
-
-up:
-	func(node, data);
-	parent = ext2fs_rb_parent(node);
-	if (!parent)
-		return;
-
-	if (node == parent->rb_left && parent->rb_right)
-		func(parent->rb_right, data);
-	else if (parent->rb_left)
-		func(parent->rb_left, data);
-
-	node = parent;
-	goto up;
-}
-
-/*
- * after inserting @node into the tree, update the tree to account for
- * both the new entry and any damage done by rebalance
- */
-void ext2fs_rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
-{
-	if (node->rb_left)
-		node = node->rb_left;
-	else if (node->rb_right)
-		node = node->rb_right;
-
-	ext2fs_rb_augment_path(node, func, data);
-}
-
-/*
- * before removing the node, find the deepest node on the rebalance path
- * that will still be there after @node gets removed
- */
-struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node)
-{
-	struct rb_node *deepest;
-
-	if (!node->rb_right && !node->rb_left)
-		deepest = ext2fs_rb_parent(node);
-	else if (!node->rb_right)
-		deepest = node->rb_left;
-	else if (!node->rb_left)
-		deepest = node->rb_right;
-	else {
-		deepest = ext2fs_rb_next(node);
-		if (deepest->rb_right)
-			deepest = deepest->rb_right;
-		else if (ext2fs_rb_parent(deepest) != node)
-			deepest = ext2fs_rb_parent(deepest);
-	}
-
-	return deepest;
-}
-
-/*
- * after removal, update the tree to account for the removed entry
- * and any rebalance damage.
- */
-void ext2fs_rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
-{
-	if (node)
-		ext2fs_rb_augment_path(node, func, data);
-}
-
 /*
  * This function returns the first node (in sort order) of the tree.
  */
diff --git a/lib/ext2fs/rbtree.h b/lib/ext2fs/rbtree.h
index dfeeb234..f718ad24 100644
--- a/lib/ext2fs/rbtree.h
+++ b/lib/ext2fs/rbtree.h
@@ -151,14 +151,6 @@ static inline void ext2fs_rb_clear_node(struct rb_node *node)
 extern void ext2fs_rb_insert_color(struct rb_node *, struct rb_root *);
 extern void ext2fs_rb_erase(struct rb_node *, struct rb_root *);
 
-typedef void (*rb_augment_f)(struct rb_node *node, void *data);
-
-extern void ext2fs_rb_augment_insert(struct rb_node *node,
-			      rb_augment_f func, void *data);
-extern struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node);
-extern void ext2fs_rb_augment_erase_end(struct rb_node *node,
-				 rb_augment_f func, void *data);
-
 /* Find logical next and previous nodes in a tree */
 extern struct rb_node *ext2fs_rb_next(struct rb_node *);
 extern struct rb_node *ext2fs_rb_prev(struct rb_node *);
-- 
2.31.1

Powered by blists - more mailing lists