Commit | Line | Data |
---|---|---|
b2441318 | 1 | /* SPDX-License-Identifier: GPL-2.0 */ |
f58c2535 ACM |
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 | ||
98a91837 | 39 | resort_rb__for_each_entry(nd, threads) { |
f58c2535 ACM |
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 | ||
98a91837 | 127 | #define resort_rb__for_each_entry(__nd, __name) \ |
f58c2535 ACM |
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) \ | |
148 | DECLARE_RESORT_RB(__name)(&__machine->threads, __machine->nr_threads) | |
149 | ||
150 | #endif /* _PERF_RESORT_RB_H_ */ |