From 4f72c0cab40536a0be501d85ea4918467ab82ad5 Mon Sep 17 00:00:00 2001 From: Mikulas Patocka Date: Mon, 25 Jul 2011 17:55:57 -0400 Subject: sysfs: use rb-tree for name lookups sysfs: use rb-tree for name lookups Use red-black tree for name lookups. Signed-off-by: Mikulas Patocka Signed-off-by: Greg Kroah-Hartman --- fs/sysfs/dir.c | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 50 insertions(+), 7 deletions(-) (limited to 'fs/sysfs/dir.c') 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; } /** -- cgit v1.2.3-59-g8ed1b