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