| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Mon, 30 Jul 2012 22:31:33 -0600
From: David Ahern <dsahern@...il.com>
To: acme@...stprotocols.net, linux-kernel@...r.kernel.org
Cc: David Ahern <dsahern@...il.com>, Ingo Molnar <mingo@...nel.org>,
Jiri Olsa <jolsa@...hat.com>,
Namhyung Kim <namhyung@...nel.org>,
Frederic Weisbecker <fweisbec@...il.com>,
Peter Zijlstra <peterz@...radead.org>
Subject: [PATCH 2/4] perf tool: change strlist to use the new rblist
Replaces the direct use of rbtree code with the rblist API. In the end
the patch is a no-op on strlist functionality; the API for strlist is
not changed, only its implementaton.
Signed-off-by: David Ahern <dsahern@...il.com>
Cc: Arnaldo Carvalho de Melo <acme@...stprotocols.net>
Cc: Ingo Molnar <mingo@...nel.org>
Cc: Jiri Olsa <jolsa@...hat.com>
Cc: Namhyung Kim <namhyung@...nel.org>
Cc: Frederic Weisbecker <fweisbec@...il.com>
Cc: Peter Zijlstra <peterz@...radead.org>
---
tools/perf/util/strlist.c | 130 ++++++++++++++++++---------------------------
tools/perf/util/strlist.h | 11 ++--
2 files changed, 57 insertions(+), 84 deletions(-)
diff --git a/tools/perf/util/strlist.c b/tools/perf/util/strlist.c
index 6783a20..95856ff 100644
--- a/tools/perf/util/strlist.c
+++ b/tools/perf/util/strlist.c
@@ -10,23 +10,28 @@
#include <stdlib.h>
#include <string.h>
-static struct str_node *str_node__new(const char *s, bool dupstr)
+static
+struct rb_node *strlist__node_new(struct rblist *rblist, const void *entry)
{
- struct str_node *self = malloc(sizeof(*self));
+ const char *s = entry;
+ struct rb_node *rc = NULL;
+ struct strlist *strlist = container_of(rblist, struct strlist, rblist);
+ struct str_node *snode = malloc(sizeof(*snode));
- if (self != NULL) {
- if (dupstr) {
+ if (snode != NULL) {
+ if (strlist->dupstr) {
s = strdup(s);
if (s == NULL)
goto out_delete;
}
- self->s = s;
+ snode->s = s;
+ rc = &snode->rb_node;
}
- return self;
+ return rc;
out_delete:
- free(self);
+ free(snode);
return NULL;
}
@@ -37,36 +42,26 @@ static void str_node__delete(struct str_node *self, bool dupstr)
free(self);
}
-int strlist__add(struct strlist *self, const char *new_entry)
+static
+void strlist__node_delete(struct rblist *rblist, struct rb_node *rb_node)
{
- struct rb_node **p = &self->entries.rb_node;
- struct rb_node *parent = NULL;
- struct str_node *sn;
-
- while (*p != NULL) {
- int rc;
-
- parent = *p;
- sn = rb_entry(parent, struct str_node, rb_node);
- rc = strcmp(sn->s, new_entry);
-
- if (rc > 0)
- p = &(*p)->rb_left;
- else if (rc < 0)
- p = &(*p)->rb_right;
- else
- return -EEXIST;
- }
+ struct strlist *slist = container_of(rblist, struct strlist, rblist);
+ struct str_node *snode = container_of(rb_node, struct str_node, rb_node);
- sn = str_node__new(new_entry, self->dupstr);
- if (sn == NULL)
- return -ENOMEM;
+ str_node__delete(snode, slist->dupstr);
+}
- rb_link_node(&sn->rb_node, parent, p);
- rb_insert_color(&sn->rb_node, &self->entries);
- ++self->nr_entries;
+static int strlist__node_cmp(struct rb_node *rb_node, const void *entry)
+{
+ const char *str = entry;
+ struct str_node *snode = container_of(rb_node, struct str_node, rb_node);
+
+ return strcmp(snode->s, str);
+}
- return 0;
+int strlist__add(struct strlist *self, const char *new_entry)
+{
+ return rblist__add_node(&self->rblist, new_entry);
}
int strlist__load(struct strlist *self, const char *filename)
@@ -96,34 +91,20 @@ out:
return err;
}
-void strlist__remove(struct strlist *self, struct str_node *sn)
+void strlist__remove(struct strlist *slist, struct str_node *snode)
{
- rb_erase(&sn->rb_node, &self->entries);
- str_node__delete(sn, self->dupstr);
+ str_node__delete(snode, slist->dupstr);
}
-struct str_node *strlist__find(struct strlist *self, const char *entry)
+struct str_node *strlist__find(struct strlist *slist, const char *entry)
{
- struct rb_node **p = &self->entries.rb_node;
- struct rb_node *parent = NULL;
-
- while (*p != NULL) {
- struct str_node *sn;
- int rc;
-
- parent = *p;
- sn = rb_entry(parent, struct str_node, rb_node);
- rc = strcmp(sn->s, entry);
-
- if (rc > 0)
- p = &(*p)->rb_left;
- else if (rc < 0)
- p = &(*p)->rb_right;
- else
- return sn;
- }
+ struct str_node *snode = NULL;
+ struct rb_node *rb_node = rblist__find(&slist->rblist, entry);
- return NULL;
+ if (rb_node)
+ snode = container_of(rb_node, struct str_node, rb_node);
+
+ return snode;
}
static int strlist__parse_list_entry(struct strlist *self, const char *s)
@@ -156,9 +137,12 @@ struct strlist *strlist__new(bool dupstr, const char *slist)
struct strlist *self = malloc(sizeof(*self));
if (self != NULL) {
- self->entries = RB_ROOT;
+ rblist__init(&self->rblist);
+ self->rblist.node_cmp = strlist__node_cmp;
+ self->rblist.node_new = strlist__node_new;
+ self->rblist.node_delete = strlist__node_delete;
+
self->dupstr = dupstr;
- self->nr_entries = 0;
if (slist && strlist__parse_list(self, slist) != 0)
goto out_error;
}
@@ -171,30 +155,18 @@ out_error:
void strlist__delete(struct strlist *self)
{
- if (self != NULL) {
- struct str_node *pos;
- struct rb_node *next = rb_first(&self->entries);
-
- while (next) {
- pos = rb_entry(next, struct str_node, rb_node);
- next = rb_next(&pos->rb_node);
- strlist__remove(self, pos);
- }
- self->entries = RB_ROOT;
- free(self);
- }
+ if (self != NULL)
+ rblist__delete(&self->rblist);
}
-struct str_node *strlist__entry(const struct strlist *self, unsigned int idx)
+struct str_node *strlist__entry(const struct strlist *slist, unsigned int idx)
{
- struct rb_node *nd;
+ struct str_node *snode = NULL;
+ struct rb_node *rb_node;
- for (nd = rb_first(&self->entries); nd; nd = rb_next(nd)) {
- struct str_node *pos = rb_entry(nd, struct str_node, rb_node);
+ rb_node = rblist__entry(&slist->rblist, idx);
+ if (rb_node)
+ snode = container_of(rb_node, struct str_node, rb_node);
- if (!idx--)
- return pos;
- }
-
- return NULL;
+ return snode;
}
diff --git a/tools/perf/util/strlist.h b/tools/perf/util/strlist.h
index 3ba8390..dd9f922 100644
--- a/tools/perf/util/strlist.h
+++ b/tools/perf/util/strlist.h
@@ -4,14 +4,15 @@
#include <linux/rbtree.h>
#include <stdbool.h>
+#include "rblist.h"
+
struct str_node {
struct rb_node rb_node;
const char *s;
};
struct strlist {
- struct rb_root entries;
- unsigned int nr_entries;
+ struct rblist rblist;
bool dupstr;
};
@@ -32,18 +33,18 @@ static inline bool strlist__has_entry(struct strlist *self, const char *entry)
static inline bool strlist__empty(const struct strlist *self)
{
- return self->nr_entries == 0;
+ return rblist__empty(&self->rblist);
}
static inline unsigned int strlist__nr_entries(const struct strlist *self)
{
- return self->nr_entries;
+ return rblist__nr_entries(&self->rblist);
}
/* For strlist iteration */
static inline struct str_node *strlist__first(struct strlist *self)
{
- struct rb_node *rn = rb_first(&self->entries);
+ struct rb_node *rn = rb_first(&self->rblist.entries);
return rn ? rb_entry(rn, struct str_node, rb_node) : NULL;
}
static inline struct str_node *strlist__next(struct str_node *sn)
--
1.7.10.1
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists