From a406f75840e15afbabd98cb64ae36b51424a8033 Mon Sep 17 00:00:00 2001 From: Mikulas Patocka Date: Mon, 25 Jul 2011 17:57:03 -0400 Subject: 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 Signed-off-by: Greg Kroah-Hartman --- fs/sysfs/sysfs.h | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'fs/sysfs/sysfs.h') diff --git a/fs/sysfs/sysfs.h b/fs/sysfs/sysfs.h index 3c261681713b..ce29e28b766d 100644 --- a/fs/sysfs/sysfs.h +++ b/fs/sysfs/sysfs.h @@ -18,11 +18,10 @@ struct sysfs_open_dirent; /* 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 sysfs_dirent { 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 { -- cgit v1.2.3