summaryrefslogtreecommitdiff
path: root/fs/sysfs
diff options
context:
space:
mode:
authorMikulas Patocka <mpatocka@redhat.com>2011-07-25 17:55:57 -0400
committerGreg Kroah-Hartman <gregkh@suse.de>2011-08-22 17:43:52 -0700
commit4f72c0cab40536a0be501d85ea4918467ab82ad5 (patch)
treef5f0cc385fed9a32f7fc4451f8618c3b4120bc3d /fs/sysfs
parent7f9838fd01833ffb30177d964983076924344c9e (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')
-rw-r--r--fs/sysfs/dir.c57
-rw-r--r--fs/sysfs/sysfs.h5
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;