1
2 #ifndef _PERF_RESORT_RB_H_
3 #define _PERF_RESORT_RB_H_
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 #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
138
139
140
141
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
147 #define DECLARE_RESORT_RB_MACHINE_THREADS(__name, __machine, hash_bucket) \
148 DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries.rb_root, \
149 __machine->threads[hash_bucket].nr)
150
151 #endif