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_ */ 152