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
21DEFINE_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, ...)					\
56struct __name##_sorted_entry {							\
57	struct rb_node	rb_node;						\
58	__VA_ARGS__								\
59};										\
60static void __name##_sorted__init_entry(struct rb_node *nd,			\
61					struct __name##_sorted_entry *entry);	\
62										\
63static 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										\
71struct __name##_sorted {							\
72       struct rb_root		    entries;					\
73       struct __name##_sorted_entry nd[0];					\
74};										\
75										\
76static 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										\
91static 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										\
103static 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										\
115static void __name##_sorted__delete(struct __name##_sorted *sorted)		\
116{										\
117	free(sorted);								\
118}										\
119										\
120static void __name##_sorted__init_entry(struct rb_node *nd,			\
121					struct __name##_sorted_entry *entry)
122
123#define DECLARE_RESORT_RB(__name)						\
124struct __name##_sorted_entry *__name##_entry;					\
125struct __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.rb_root,		\
144				  __ilist->rblist.nr_entries)
145
146#endif /* _PERF_RESORT_RB_H_ */
147