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