diff options
author | Mikulas Patocka <mpatocka@redhat.com> | 2011-07-25 17:55:57 -0400 |
---|---|---|
committer | Greg Kroah-Hartman <gregkh@suse.de> | 2011-08-22 17:43:52 -0700 |
commit | 4f72c0cab40536a0be501d85ea4918467ab82ad5 (patch) | |
tree | f5f0cc385fed9a32f7fc4451f8618c3b4120bc3d /fs/sysfs/dir.c | |
parent | 7f9838fd01833ffb30177d964983076924344c9e (diff) |
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 <mpatocka@redhat.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
Diffstat (limited to 'fs/sysfs/dir.c')
-rw-r--r-- | fs/sysfs/dir.c | 57 |
1 files changed, 50 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; } /** |