147 lines · c
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 to6 * a new sort criteria, that must be present in the entries of the source7 * 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 data14 * structures created, and provide an expression for the sorting, then the15 * 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, maybe18 * pre-calculating them from multiple entries in the original 'entry' from19 * the rb_tree used as a source for the entries to be sorted:20 21DEFINE_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 suffix49 * 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, ...) \56struct __name##_sorted_entry { \57 struct rb_node rb_node; \58 __VA_ARGS__ \59}; \60static void __name##_sorted__init_entry(struct rb_node *nd, \61 struct __name##_sorted_entry *entry); \62 \63static 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 \71struct __name##_sorted { \72 struct rb_root entries; \73 struct __name##_sorted_entry nd[0]; \74}; \75 \76static 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 \91static 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 \103static 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 \115static void __name##_sorted__delete(struct __name##_sorted *sorted) \116{ \117 free(sorted); \118} \119 \120static void __name##_sorted__init_entry(struct rb_node *nd, \121 struct __name##_sorted_entry *entry)122 123#define DECLARE_RESORT_RB(__name) \124struct __name##_sorted_entry *__name##_entry; \125struct __name##_sorted *__name = __name##_sorted__new126 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 = NULL135 136/*137 * Helpers for other classes that contains both an rbtree and the138 * 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.rb_root, \144 __ilist->rblist.nr_entries)145 146#endif /* _PERF_RESORT_RB_H_ */147