mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Arnaldo Carvalho de Melo <acme@infradead.org>
To: Ingo Molnar <mingo@kernel.org>
Cc: linux-kernel@vger.kernel.org, David Ahern <dsahern@gmail.com>,
	Frederic Weisbecker <fweisbec@gmail.com>,
	Jiri Olsa <jolsa@redhat.com>, Namhyung Kim <namhyung@kernel.org>,
	Peter Zijlstra <peterz@infradead.org>,
	Arnaldo Carvalho de Melo <acme@redhat.com>
Subject: [PATCH 14/18] perf tools: Introducing rblist
Date: Fri,  3 Aug 2012 11:01:06 -0300	[thread overview]
Message-ID: <1344002470-5965-15-git-send-email-acme@infradead.org> (raw)
In-Reply-To: <1344002470-5965-1-git-send-email-acme@infradead.org>

From: David Ahern <dsahern@gmail.com>

rblist is the rbtree based code from strlist. It will be the common code
for strlist and the to-be-introduced intlist.

Signed-off-by: David Ahern <dsahern@gmail.com>
Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Ingo Molnar <mingo@kernel.org>
Cc: Jiri Olsa <jolsa@redhat.com>
Cc: Namhyung Kim <namhyung@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1343709095-7089-2-git-send-email-dsahern@gmail.com
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
---
 tools/perf/Makefile      |    2 +
 tools/perf/util/rblist.c |  107 ++++++++++++++++++++++++++++++++++++++++++++++
 tools/perf/util/rblist.h |   47 ++++++++++++++++++++
 3 files changed, 156 insertions(+), 0 deletions(-)
 create mode 100644 tools/perf/util/rblist.c
 create mode 100644 tools/perf/util/rblist.h

diff --git a/tools/perf/Makefile b/tools/perf/Makefile
index 77f124f..285f700 100644
--- a/tools/perf/Makefile
+++ b/tools/perf/Makefile
@@ -319,6 +319,7 @@ LIB_H += $(ARCH_INCLUDE)
 LIB_H += util/cgroup.h
 LIB_H += $(TRACE_EVENT_DIR)event-parse.h
 LIB_H += util/target.h
+LIB_H += util/rblist.h
 
 LIB_OBJS += $(OUTPUT)util/abspath.o
 LIB_OBJS += $(OUTPUT)util/alias.o
@@ -383,6 +384,7 @@ LIB_OBJS += $(OUTPUT)util/xyarray.o
 LIB_OBJS += $(OUTPUT)util/cpumap.o
 LIB_OBJS += $(OUTPUT)util/cgroup.o
 LIB_OBJS += $(OUTPUT)util/target.o
+LIB_OBJS += $(OUTPUT)util/rblist.o
 
 BUILTIN_OBJS += $(OUTPUT)builtin-annotate.o
 
diff --git a/tools/perf/util/rblist.c b/tools/perf/util/rblist.c
new file mode 100644
index 0000000..0171fb6
--- /dev/null
+++ b/tools/perf/util/rblist.c
@@ -0,0 +1,107 @@
+/*
+ * Based on strlist.c by:
+ * (c) 2009 Arnaldo Carvalho de Melo <acme@redhat.com>
+ *
+ * Licensed under the GPLv2.
+ */
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "rblist.h"
+
+int rblist__add_node(struct rblist *rblist, const void *new_entry)
+{
+	struct rb_node **p = &rblist->entries.rb_node;
+	struct rb_node *parent = NULL, *new_node;
+
+	while (*p != NULL) {
+		int rc;
+
+		parent = *p;
+
+		rc = rblist->node_cmp(parent, new_entry);
+		if (rc > 0)
+			p = &(*p)->rb_left;
+		else if (rc < 0)
+			p = &(*p)->rb_right;
+		else
+			return -EEXIST;
+	}
+
+	new_node = rblist->node_new(rblist, new_entry);
+	if (new_node == NULL)
+		return -ENOMEM;
+
+	rb_link_node(new_node, parent, p);
+	rb_insert_color(new_node, &rblist->entries);
+	++rblist->nr_entries;
+
+	return 0;
+}
+
+void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node)
+{
+	rb_erase(rb_node, &rblist->entries);
+	rblist->node_delete(rblist, rb_node);
+}
+
+struct rb_node *rblist__find(struct rblist *rblist, const void *entry)
+{
+	struct rb_node **p = &rblist->entries.rb_node;
+	struct rb_node *parent = NULL;
+
+	while (*p != NULL) {
+		int rc;
+
+		parent = *p;
+
+		rc = rblist->node_cmp(parent, entry);
+		if (rc > 0)
+			p = &(*p)->rb_left;
+		else if (rc < 0)
+			p = &(*p)->rb_right;
+		else
+			return parent;
+	}
+
+	return NULL;
+}
+
+void rblist__init(struct rblist *rblist)
+{
+	if (rblist != NULL) {
+		rblist->entries	 = RB_ROOT;
+		rblist->nr_entries = 0;
+	}
+
+	return;
+}
+
+void rblist__delete(struct rblist *rblist)
+{
+	if (rblist != NULL) {
+		struct rb_node *pos, *next = rb_first(&rblist->entries);
+
+		while (next) {
+			pos = next;
+			next = rb_next(pos);
+			rb_erase(pos, &rblist->entries);
+			rblist->node_delete(rblist, pos);
+		}
+		free(rblist);
+	}
+}
+
+struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx)
+{
+	struct rb_node *node;
+
+	for (node = rb_first(&rblist->entries); node; node = rb_next(node)) {
+		if (!idx--)
+			return node;
+	}
+
+	return NULL;
+}
diff --git a/tools/perf/util/rblist.h b/tools/perf/util/rblist.h
new file mode 100644
index 0000000..6d0cae5
--- /dev/null
+++ b/tools/perf/util/rblist.h
@@ -0,0 +1,47 @@
+#ifndef __PERF_RBLIST_H
+#define __PERF_RBLIST_H
+
+#include <linux/rbtree.h>
+#include <stdbool.h>
+
+/*
+ * create node structs of the form:
+ * struct my_node {
+ *     struct rb_node rb_node;
+ *     ... my data ...
+ * };
+ *
+ * create list structs of the form:
+ * struct mylist {
+ *     struct rblist rblist;
+ *     ... my data ...
+ * };
+ */
+
+struct rblist {
+	struct rb_root entries;
+	unsigned int   nr_entries;
+
+	int (*node_cmp)(struct rb_node *rbn, const void *entry);
+	struct rb_node *(*node_new)(struct rblist *rlist, const void *new_entry);
+	void (*node_delete)(struct rblist *rblist, struct rb_node *rb_node);
+};
+
+void rblist__init(struct rblist *rblist);
+void rblist__delete(struct rblist *rblist);
+int rblist__add_node(struct rblist *rblist, const void *new_entry);
+void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node);
+struct rb_node *rblist__find(struct rblist *rblist, const void *entry);
+struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx);
+
+static inline bool rblist__empty(const struct rblist *rblist)
+{
+	return rblist->nr_entries == 0;
+}
+
+static inline unsigned int rblist__nr_entries(const struct rblist *rblist)
+{
+	return rblist->nr_entries;
+}
+
+#endif /* __PERF_RBLIST_H */
-- 
1.7.1


  parent reply	other threads:[~2012-08-03 14:01 UTC|newest]

Thread overview: 26+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2012-08-03 14:00 [GIT PULL 00/18] perf/core fixes and improvements Arnaldo Carvalho de Melo
2012-08-03 14:00 ` [PATCH 01/18] perf test: Fix parse events automated tests Arnaldo Carvalho de Melo
2012-08-03 14:00 ` [PATCH 02/18] perf symbols: Fix array sizes for binary types arrays Arnaldo Carvalho de Melo
2012-08-03 14:00 ` [PATCH 03/18] perf target: Fix check on buffer size Arnaldo Carvalho de Melo
2012-08-03 14:17   ` Kirill A. Shutemov
2012-08-06  3:53     ` Namhyung Kim
2012-08-06  4:14       ` David Ahern
2012-08-06  4:15         ` Namhyung Kim
2012-08-03 14:00 ` [PATCH 04/18] perf evsel: Precalculate the sample size Arnaldo Carvalho de Melo
2012-08-03 14:00 ` [PATCH 05/18] perf session: Use perf_evlist__sample_type more extensively Arnaldo Carvalho de Melo
2012-08-03 14:00 ` [PATCH 06/18] perf session: Use perf_evlist__sample_id_all " Arnaldo Carvalho de Melo
2012-08-03 14:00 ` [PATCH 07/18] perf session: Use perf_evlist__id_hdr_size " Arnaldo Carvalho de Melo
2012-08-03 14:01 ` [PATCH 08/18] perf evlist: Introduce perf_evlist__parse_sample Arnaldo Carvalho de Melo
2012-08-03 15:24   ` David Ahern
2012-08-03 17:28     ` Stephane Eranian
2012-08-03 14:01 ` [PATCH 09/18] perf evsel: Adopt parse_sample method from perf_event Arnaldo Carvalho de Melo
2012-08-03 14:01 ` [PATCH 10/18] perf session: Remove no longer used synthesize_sample method Arnaldo Carvalho de Melo
2012-08-03 14:01 ` [PATCH 11/18] perf top: Error handling for counter creation should parallel perf-record Arnaldo Carvalho de Melo
2012-08-03 14:01 ` [PATCH 12/18] perf tool: Save cmdline from user in file header vs what is passed to record Arnaldo Carvalho de Melo
2012-08-03 14:01 ` [PATCH 13/18] perf kvm: Use strtol for walking guestmount directory Arnaldo Carvalho de Melo
2012-08-03 14:01 ` Arnaldo Carvalho de Melo [this message]
2012-08-03 14:01 ` [PATCH 15/18] perf tools: Change strlist to use the new rblist Arnaldo Carvalho de Melo
2012-08-03 14:01 ` [PATCH 16/18] perf tools: Introduce intlist Arnaldo Carvalho de Melo
2012-08-03 14:01 ` [PATCH 17/18] perf kvm top: Limit guest kernel info message to once Arnaldo Carvalho de Melo
2012-08-03 14:01 ` [PATCH 18/18] perf tools: Remove brace expansion from clean target Arnaldo Carvalho de Melo
2012-08-05 10:40 ` [GIT PULL 00/18] perf/core fixes and improvements Ingo Molnar

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1344002470-5965-15-git-send-email-acme@infradead.org \
    --to=acme@infradead.org \
    --cc=acme@redhat.com \
    --cc=dsahern@gmail.com \
    --cc=fweisbec@gmail.com \
    --cc=jolsa@redhat.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@kernel.org \
    --cc=namhyung@kernel.org \
    --cc=peterz@infradead.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®