tools/perf/util/rb_resort.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 #ifndef _PERF_RESORT_RB_H_
   3 #define _PERF_RESORT_RB_H_
   4 /*
   5  * Template for creating a class to resort an existing rb_tree according to
   6  * a new sort criteria, that must be present in the entries of the source
   7  * rb_tree.
   8  *
   9  * (c) 2016 Arnaldo Carvalho de Melo <acme@redhat.com>
  10  *
  11  * Quick example, resorting threads by its shortname:
  12  *
  13  * First define the prefix (threads) to be used for the functions and data
  14  * structures created, and provide an expression for the sorting, then the
  15  * fields to be present in each of the entries in the new, sorted, rb_tree.
  16  *
  17  * The body of the init function should collect the fields, maybe
  18  * pre-calculating them from multiple entries in the original 'entry' from
  19  * the rb_tree used as a source for the entries to be sorted:
  20
  21 DEFINE_RB_RESORT_RB(threads, strcmp(a->thread->shortname,
  22                                     b->thread->shortname) < 0,
  23         struct thread *thread;
  24 )
  25 {
  26         entry->thread = rb_entry(nd, struct thread, rb_node);
  27 }
  28
  29  * After this it is just a matter of instantiating it and iterating it,
  30  * for a few data structures with existing rb_trees, such as 'struct machine',
  31  * helpers are available to get the rb_root and the nr_entries:
  32
  33         DECLARE_RESORT_RB_MACHINE_THREADS(threads, machine_ptr);
  34
  35  * This will instantiate the new rb_tree and a cursor for it, that can be used as:
  36
  37         struct rb_node *nd;
  38
  39         resort_rb__for_each_entry(nd, threads) {
  40                 struct thread *t = threads_entry;
  41                 printf("%s: %d\n", t->shortname, t->tid);
  42         }
  43
  44  * Then delete it:
  45
  46         resort_rb__delete(threads);
  47
  48  * The name of the data structures and functions will have a _sorted suffix
  49  * right before the method names, i.e. will look like:
  50  *
  51  *      struct threads_sorted_entry {}
  52  *      threads_sorted__insert()
  53  */
  54
  55 #define DEFINE_RESORT_RB(__name, __comp, ...)                                   \
  56 struct __name##_sorted_entry {                                                  \
  57         struct rb_node  rb_node;                                                \
  58         __VA_ARGS__                                                             \
  59 };                                                                              \
  60 static void __name##_sorted__init_entry(struct rb_node *nd,                     \
  61                                         struct __name##_sorted_entry *entry);   \
  62                                                                                 \
  63 static int __name##_sorted__cmp(struct rb_node *nda, struct rb_node *ndb)       \
  64 {                                                                               \
  65         struct __name##_sorted_entry *a, *b;                                    \
  66         a = rb_entry(nda, struct __name##_sorted_entry, rb_node);               \
  67         b = rb_entry(ndb, struct __name##_sorted_entry, rb_node);               \
  68         return __comp;                                                          \
  69 }                                                                               \
  70                                                                                 \
  71 struct __name##_sorted {                                                        \
  72        struct rb_root               entries;                                    \
  73        struct __name##_sorted_entry nd[0];                                      \
  74 };                                                                              \
  75                                                                                 \
  76 static void __name##_sorted__insert(struct __name##_sorted *sorted,             \
  77                                       struct rb_node *sorted_nd)                \
  78 {                                                                               \
  79         struct rb_node **p = &sorted->entries.rb_node, *parent = NULL;          \
  80         while (*p != NULL) {                                                    \
  81                 parent = *p;                                                    \
  82                 if (__name##_sorted__cmp(sorted_nd, parent))                    \
  83                         p = &(*p)->rb_left;                                     \
  84                 else                                                            \
  85                         p = &(*p)->rb_right;                                    \
  86         }                                                                       \
  87         rb_link_node(sorted_nd, parent, p);                                     \
  88         rb_insert_color(sorted_nd, &sorted->entries);                           \
  89 }                                                                               \
  90                                                                                 \
  91 static void __name##_sorted__sort(struct __name##_sorted *sorted,               \
  92                                     struct rb_root *entries)                    \
  93 {                                                                               \
  94         struct rb_node *nd;                                                     \
  95         unsigned int i = 0;                                                     \
  96         for (nd = rb_first(entries); nd; nd = rb_next(nd)) {                    \
  97                 struct __name##_sorted_entry *snd = &sorted->nd[i++];           \
  98                 __name##_sorted__init_entry(nd, snd);                           \
  99                 __name##_sorted__insert(sorted, &snd->rb_node);                 \
 100         }                                                                       \
 101 }                                                                               \
 102                                                                                 \
 103 static struct __name##_sorted *__name##_sorted__new(struct rb_root *entries,    \
 104                                                     int nr_entries)             \
 105 {                                                                               \
 106         struct __name##_sorted *sorted;                                         \
 107         sorted = malloc(sizeof(*sorted) + sizeof(sorted->nd[0]) * nr_entries);  \
 108         if (sorted) {                                                           \
 109                 sorted->entries = RB_ROOT;                                      \
 110                 __name##_sorted__sort(sorted, entries);                         \
 111         }                                                                       \
 112         return sorted;                                                          \
 113 }                                                                               \
 114                                                                                 \
 115 static void __name##_sorted__delete(struct __name##_sorted *sorted)             \
 116 {                                                                               \
 117         free(sorted);                                                           \
 118 }                                                                               \
 119                                                                                 \
 120 static void __name##_sorted__init_entry(struct rb_node *nd,                     \
 121                                         struct __name##_sorted_entry *entry)
 122
 123 #define DECLARE_RESORT_RB(__name)                                               \
 124 struct __name##_sorted_entry *__name##_entry;                                   \
 125 struct __name##_sorted *__name = __name##_sorted__new
 126
 127 #define resort_rb__for_each_entry(__nd, __name)                                 \
 128         for (__nd = rb_first(&__name->entries);                                 \
 129              __name##_entry = rb_entry(__nd, struct __name##_sorted_entry,      \
 130                                        rb_node), __nd;                          \
 131              __nd = rb_next(__nd))
 132
 133 #define resort_rb__delete(__name)                                               \
 134         __name##_sorted__delete(__name), __name = NULL
 135
 136 /*
 137  * Helpers for other classes that contains both an rbtree and the
 138  * number of entries in it:
 139  */
 140
 141 /* For 'struct intlist' */
 142 #define DECLARE_RESORT_RB_INTLIST(__name, __ilist)                              \
 143         DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries,                     \
 144                                   __ilist->rblist.nr_entries)
 145
 146 /* For 'struct machine->threads' */
 147 #define DECLARE_RESORT_RB_MACHINE_THREADS(__name, __machine, hash_bucket)       \
 148         DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries,     \
 149                                   __machine->threads[hash_bucket].nr)
 150
 151 #endif /* _PERF_RESORT_RB_H_ */