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_entry(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_entry(__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_ */ 150