diff options
| -rw-r--r-- | fs/sysfs/dir.c | 57 | ||||
| -rw-r--r-- | fs/sysfs/sysfs.h | 5 |
2 files changed, 55 insertions, 7 deletions
diff --git a/fs/sysfs/dir.c b/fs/sysfs/dir.c index 7d240e6b7176..3e937da224d4 100644 --- a/fs/sysfs/dir.c +++ b/fs/sysfs/dir.c @@ -45,6 +45,9 @@ static void sysfs_link_sibling(struct sysfs_dirent *sd) struct sysfs_dirent *parent_sd = sd->s_parent; struct sysfs_dirent **pos; + struct rb_node **p; + struct rb_node *parent; + BUG_ON(sd->s_sibling); if (sysfs_type(sd) == SYSFS_DIR) @@ -60,6 +63,23 @@ static void sysfs_link_sibling(struct sysfs_dirent *sd) } sd->s_sibling = *pos; *pos = sd; + + p = &parent_sd->s_dir.name_tree.rb_node; + parent = NULL; + while (*p) { + int c; + parent = *p; +#define node rb_entry(parent, struct sysfs_dirent, name_node) + c = strcmp(sd->s_name, node->s_name); + if (c < 0) { + p = &node->name_node.rb_left; + } else { + p = &node->name_node.rb_right; + } +#undef node + } + rb_link_node(&sd->name_node, parent, p); + rb_insert_color(&sd->name_node, &parent_sd->s_dir.name_tree); } /** @@ -87,6 +107,8 @@ static void sysfs_unlink_sibling(struct sysfs_dirent *sd) break; } } + + rb_erase(&sd->name_node, &sd->s_parent->s_dir.name_tree); } /** @@ -546,15 +568,36 @@ struct sysfs_dirent *sysfs_find_dirent(struct sysfs_dirent *parent_sd, const void *ns, const unsigned char *name) { - struct sysfs_dirent *sd; + struct rb_node *p = parent_sd->s_dir.name_tree.rb_node; + struct sysfs_dirent *found = NULL; + + while (p) { + int c; +#define node rb_entry(p, struct sysfs_dirent, name_node) + c = strcmp(name, node->s_name); + if (c < 0) { + p = node->name_node.rb_left; + } else if (c > 0) { + p = node->name_node.rb_right; + } else { + found = node; + p = node->name_node.rb_left; + } +#undef node + } - for (sd = parent_sd->s_dir.children; sd; sd = sd->s_sibling) { - if (ns && sd->s_ns && (sd->s_ns != ns)) - continue; - if (!strcmp(sd->s_name, name)) - return sd; + if (found && ns) { + while (found->s_ns && found->s_ns != ns) { + p = rb_next(&found->name_node); + if (!p) + return NULL; + found = rb_entry(p, struct sysfs_dirent, name_node); + if (strcmp(name, found->s_name)) + return NULL; + } } - return NULL; + + return found; } /** diff --git a/fs/sysfs/sysfs.h b/fs/sysfs/sysfs.h index 6348e2c753f6..fe1a9e8650bf 100644 --- a/fs/sysfs/sysfs.h +++ b/fs/sysfs/sysfs.h @@ -11,6 +11,7 @@ #include <linux/lockdep.h> #include <linux/kobject_ns.h> #include <linux/fs.h> +#include <linux/rbtree.h> struct sysfs_open_dirent; @@ -21,6 +22,8 @@ struct sysfs_elem_dir { struct sysfs_dirent *children; unsigned long subdirs; + + struct rb_root name_tree; }; struct sysfs_elem_symlink { @@ -61,6 +64,8 @@ struct sysfs_dirent { struct sysfs_dirent *s_sibling; const char *s_name; + struct rb_node name_node; + const void *s_ns; /* namespace tag */ union { struct sysfs_elem_dir s_dir; |