sysfs: use rb-tree for inode number lookup
sysfs: use rb-tree for inode number lookup
This patch makes sysfs use red-black tree for inode number lookup.
Together with a previous patch to use red-black tree for name lookup,
this patch makes all sysfs lookups to have O(log n) complexity.
Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
diff --git a/fs/sysfs/sysfs.h b/fs/sysfs/sysfs.h
index 3c26168..ce29e28 100644
--- a/fs/sysfs/sysfs.h
+++ b/fs/sysfs/sysfs.h
@@ -18,11 +18,10 @@
/* type-specific structures for sysfs_dirent->s_* union members */
struct sysfs_elem_dir {
struct kobject *kobj;
- /* children list starts here and goes through sd->s_sibling */
- struct sysfs_dirent *children;
unsigned long subdirs;
+ struct rb_root inode_tree;
struct rb_root name_tree;
};
@@ -61,9 +60,9 @@
struct lockdep_map dep_map;
#endif
struct sysfs_dirent *s_parent;
- struct sysfs_dirent *s_sibling;
const char *s_name;
+ struct rb_node inode_node;
struct rb_node name_node;
union {