diff options
| author | Davidlohr Bueso <dave@stgolabs.net> | 2018-12-06 11:18:16 -0800 |
|---|---|---|
| committer | Arnaldo Carvalho de Melo <acme@redhat.com> | 2019-01-25 15:12:10 +0100 |
| commit | ca2270292e6c3415102242bf9dc3d05f622b7b28 (patch) | |
| tree | 716a1cf2f73101e4d02569585fd26cb320f9a703 /tools/perf/util/intlist.h | |
| parent | 55ecd6310f9fe48cf7e435be408862da1e0e6baa (diff) | |
| download | lwn-ca2270292e6c3415102242bf9dc3d05f622b7b28.tar.gz lwn-ca2270292e6c3415102242bf9dc3d05f622b7b28.zip | |
perf util: Use cached rbtree for rblists
At the cost of an extra pointer, we can avoid the O(logN) cost of
finding the first element in the tree (smallest node), which is
something required for any of the strlist or intlist traversals
(XXX_for_each_entry()). There are a number of users in perf of these
(particularly strlists), including probes, and buildid.
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Tested-by: Arnaldo Carvalho de Melo <acme@redhat.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Namhyung Kim <namhyung@kernel.org>
Link: http://lkml.kernel.org/r/20181206191819.30182-5-dave@stgolabs.net
Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
Diffstat (limited to 'tools/perf/util/intlist.h')
| -rw-r--r-- | tools/perf/util/intlist.h | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/tools/perf/util/intlist.h b/tools/perf/util/intlist.h index 85bab8735fa9..5c19ee001299 100644 --- a/tools/perf/util/intlist.h +++ b/tools/perf/util/intlist.h @@ -45,7 +45,7 @@ static inline unsigned int intlist__nr_entries(const struct intlist *ilist) /* For intlist iteration */ static inline struct int_node *intlist__first(struct intlist *ilist) { - struct rb_node *rn = rb_first(&ilist->rblist.entries); + struct rb_node *rn = rb_first_cached(&ilist->rblist.entries); return rn ? rb_entry(rn, struct int_node, rb_node) : NULL; } static inline struct int_node *intlist__next(struct int_node *in) |