perf/util/rb_resort.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 #ifndef _PERF_RESORT_RB_H_
0003 #define _PERF_RESORT_RB_H_
0004 /*
0005  * Template for creating a class to resort an existing rb_tree according to
0006  * a new sort criteria, that must be present in the entries of the source
0007  * rb_tree.
0008  *
0009  * (c) 2016 Arnaldo Carvalho de Melo <acme@redhat.com>
0010  *
0011  * Quick example, resorting threads by its shortname:
0012  *
0013  * First define the prefix (threads) to be used for the functions and data
0014  * structures created, and provide an expression for the sorting, then the
0015  * fields to be present in each of the entries in the new, sorted, rb_tree.
0016  *
0017  * The body of the init function should collect the fields, maybe
0018  * pre-calculating them from multiple entries in the original 'entry' from
0019  * the rb_tree used as a source for the entries to be sorted:
0020
0021 DEFINE_RB_RESORT_RB(threads, strcmp(a->thread->shortname,
0022                     b->thread->shortname) < 0,
0023     struct thread *thread;
0024 )
0025 {
0026     entry->thread = rb_entry(nd, struct thread, rb_node);
0027 }
0028
0029  * After this it is just a matter of instantiating it and iterating it,
0030  * for a few data structures with existing rb_trees, such as 'struct machine',
0031  * helpers are available to get the rb_root and the nr_entries:
0032
0033     DECLARE_RESORT_RB_MACHINE_THREADS(threads, machine_ptr);
0034
0035  * This will instantiate the new rb_tree and a cursor for it, that can be used as:
0036
0037     struct rb_node *nd;
0038
0039     resort_rb__for_each_entry(nd, threads) {
0040         struct thread *t = threads_entry;
0041         printf("%s: %d\n", t->shortname, t->tid);
0042     }
0043
0044  * Then delete it:
0045
0046     resort_rb__delete(threads);
0047
0048  * The name of the data structures and functions will have a _sorted suffix
0049  * right before the method names, i.e. will look like:
0050  *
0051  *  struct threads_sorted_entry {}
0052  *  threads_sorted__insert()
0053  */
0054
0055 #define DEFINE_RESORT_RB(__name, __comp, ...)                   \
0056 struct __name##_sorted_entry {                          \
0057     struct rb_node  rb_node;                        \
0058     __VA_ARGS__                             \
0059 };                                      \
0060 static void __name##_sorted__init_entry(struct rb_node *nd,         \
0061                     struct __name##_sorted_entry *entry);   \
0062                                         \
0063 static int __name##_sorted__cmp(struct rb_node *nda, struct rb_node *ndb)   \
0064 {                                       \
0065     struct __name##_sorted_entry *a, *b;                    \
0066     a = rb_entry(nda, struct __name##_sorted_entry, rb_node);       \
0067     b = rb_entry(ndb, struct __name##_sorted_entry, rb_node);       \
0068     return __comp;                              \
0069 }                                       \
0070                                         \
0071 struct __name##_sorted {                            \
0072        struct rb_root           entries;                    \
0073        struct __name##_sorted_entry nd[0];                  \
0074 };                                      \
0075                                         \
0076 static void __name##_sorted__insert(struct __name##_sorted *sorted,     \
0077                       struct rb_node *sorted_nd)        \
0078 {                                       \
0079     struct rb_node **p = &sorted->entries.rb_node, *parent = NULL;      \
0080     while (*p != NULL) {                            \
0081         parent = *p;                            \
0082         if (__name##_sorted__cmp(sorted_nd, parent))            \
0083             p = &(*p)->rb_left;                 \
0084         else                                \
0085             p = &(*p)->rb_right;                    \
0086     }                                   \
0087     rb_link_node(sorted_nd, parent, p);                 \
0088     rb_insert_color(sorted_nd, &sorted->entries);               \
0089 }                                       \
0090                                         \
0091 static void __name##_sorted__sort(struct __name##_sorted *sorted,       \
0092                     struct rb_root *entries)            \
0093 {                                       \
0094     struct rb_node *nd;                         \
0095     unsigned int i = 0;                         \
0096     for (nd = rb_first(entries); nd; nd = rb_next(nd)) {            \
0097         struct __name##_sorted_entry *snd = &sorted->nd[i++];       \
0098         __name##_sorted__init_entry(nd, snd);               \
0099         __name##_sorted__insert(sorted, &snd->rb_node);         \
0100     }                                   \
0101 }                                       \
0102                                         \
0103 static struct __name##_sorted *__name##_sorted__new(struct rb_root *entries,    \
0104                             int nr_entries)     \
0105 {                                       \
0106     struct __name##_sorted *sorted;                     \
0107     sorted = malloc(sizeof(*sorted) + sizeof(sorted->nd[0]) * nr_entries);  \
0108     if (sorted) {                               \
0109         sorted->entries = RB_ROOT;                  \
0110         __name##_sorted__sort(sorted, entries);             \
0111     }                                   \
0112     return sorted;                              \
0113 }                                       \
0114                                         \
0115 static void __name##_sorted__delete(struct __name##_sorted *sorted)     \
0116 {                                       \
0117     free(sorted);                               \
0118 }                                       \
0119                                         \
0120 static void __name##_sorted__init_entry(struct rb_node *nd,         \
0121                     struct __name##_sorted_entry *entry)
0122
0123 #define DECLARE_RESORT_RB(__name)                       \
0124 struct __name##_sorted_entry *__name##_entry;                   \
0125 struct __name##_sorted *__name = __name##_sorted__new
0126
0127 #define resort_rb__for_each_entry(__nd, __name)                 \
0128     for (__nd = rb_first(&__name->entries);                 \
0129          __name##_entry = rb_entry(__nd, struct __name##_sorted_entry,  \
0130                        rb_node), __nd;              \
0131          __nd = rb_next(__nd))
0132
0133 #define resort_rb__delete(__name)                       \
0134     __name##_sorted__delete(__name), __name = NULL
0135
0136 /*
0137  * Helpers for other classes that contains both an rbtree and the
0138  * number of entries in it:
0139  */
0140
0141 /* For 'struct intlist' */
0142 #define DECLARE_RESORT_RB_INTLIST(__name, __ilist)              \
0143     DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries.rb_root,     \
0144                   __ilist->rblist.nr_entries)
0145
0146 /* For 'struct machine->threads' */
0147 #define DECLARE_RESORT_RB_MACHINE_THREADS(__name, __machine, hash_bucket)    \
0148  DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries.rb_root, \
0149                __machine->threads[hash_bucket].nr)
0150
0151 #endif /* _PERF_RESORT_RB_H_ */