Linux Perf
rb_resort.h
Go to the documentation of this file.
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 
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 
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, ...) \
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 
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, \
144  __ilist->rblist.nr_entries)
145 
146 /* For 'struct machine->threads' */
147 #define DECLARE_RESORT_RB_MACHINE_THREADS(__name, __machine, hash_bucket) \
148  DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries, \
149  __machine->threads[hash_bucket].nr)
150 
151 #endif /* _PERF_RESORT_RB_H_ */