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
37
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
#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;
resort_rb__for_each_entry(nd, threads) {
struct thread *t = threads_entry;
printf("%s: %d\n", 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
#define resort_rb__for_each_entry(__nd, __name) \
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_ */
|
