tools/perf/util/rb_resort.h

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