[linux-2.6-block.git] / tools / perf / util / rb_resort.h

#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(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(__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_ */
Commit	Line	Data
f58c2535 ACM	1	#ifndef _PERF_RESORT_RB_H_
	2	#define _PERF_RESORT_RB_H_
	3	/*
	4	* Template for creating a class to resort an existing rb_tree according to
	5	* a new sort criteria, that must be present in the entries of the source
	6	* rb_tree.
	7	*
	8	* (c) 2016 Arnaldo Carvalho de Melo <acme@redhat.com>
	9	*
	10	* Quick example, resorting threads by its shortname:
	11	*
	12	* First define the prefix (threads) to be used for the functions and data
	13	* structures created, and provide an expression for the sorting, then the
	14	* fields to be present in each of the entries in the new, sorted, rb_tree.
	15	*
	16	* The body of the init function should collect the fields, maybe
	17	* pre-calculating them from multiple entries in the original 'entry' from
	18	* the rb_tree used as a source for the entries to be sorted:
	19
	20	DEFINE_RB_RESORT_RB(threads, strcmp(a->thread->shortname,
	21	b->thread->shortname) < 0,
	22	struct thread *thread;
	23	)
	24	{
	25	entry->thread = rb_entry(nd, struct thread, rb_node);
	26	}
	27
	28	* After this it is just a matter of instantiating it and iterating it,
	29	* for a few data structures with existing rb_trees, such as 'struct machine',
	30	* helpers are available to get the rb_root and the nr_entries:
	31
	32	DECLARE_RESORT_RB_MACHINE_THREADS(threads, machine_ptr);
	33
	34	* This will instantiate the new rb_tree and a cursor for it, that can be used as:
	35
	36	struct rb_node *nd;
	37
	38	resort_rb__for_each(nd, threads) {
	39	struct thread *t = threads_entry;
	40	printf("%s: %d\n", t->shortname, t->tid);
	41	}
	42
	43	* Then delete it:
	44
	45	resort_rb__delete(threads);
	46
	47	* The name of the data structures and functions will have a _sorted suffix
	48	* right before the method names, i.e. will look like:
	49	*
	50	* struct threads_sorted_entry {}
	51	* threads_sorted__insert()
	52	*/
	53
	54	#define DEFINE_RESORT_RB(__name, __comp, ...) \
	55	struct __name##_sorted_entry { \
	56	struct rb_node rb_node; \
	57	__VA_ARGS__ \
	58	}; \
	59	static void __name##_sorted__init_entry(struct rb_node *nd, \
	60	struct __name##_sorted_entry *entry); \
	61	\
	62	static int __name##_sorted__cmp(struct rb_node nda, struct rb_node ndb) \
	63	{ \
	64	struct __name##_sorted_entry a, b; \
65	a = rb_entry(nda, struct __name##_sorted_entry, rb_node); \
66	b = rb_entry(ndb, struct __name##_sorted_entry, rb_node); \
67	return __comp; \
68	} \
69	\
70	struct __name##_sorted { \
71	struct rb_root entries; \
72	struct __name##_sorted_entry nd[0]; \
73	}; \
74	\
75	static void __name##_sorted__insert(struct __name##_sorted *sorted, \
76	struct rb_node *sorted_nd) \
77	{ \
78	struct rb_node *p = &sorted->entries.rb_node, parent = NULL; \
79	while (*p != NULL) { \
80	parent = *p; \
81	if (__name##_sorted__cmp(sorted_nd, parent)) \
82	p = &(*p)->rb_left; \
83	else \
84	p = &(*p)->rb_right; \
85	} \
86	rb_link_node(sorted_nd, parent, p); \
87	rb_insert_color(sorted_nd, &sorted->entries); \
88	} \
89	\
90	static void __name##_sorted__sort(struct __name##_sorted *sorted, \
91	struct rb_root *entries) \
92	{ \
93	struct rb_node *nd; \
94	unsigned int i = 0; \
95	for (nd = rb_first(entries); nd; nd = rb_next(nd)) { \
96	struct __name##_sorted_entry *snd = &sorted->nd[i++]; \
97	__name##_sorted__init_entry(nd, snd); \
98	__name##_sorted__insert(sorted, &snd->rb_node); \
99	} \
100	} \
101	\
102	static struct __name##_sorted __name##_sorted__new(struct rb_root entries, \
103	int nr_entries) \
104	{ \
105	struct __name##_sorted *sorted; \
106	sorted = malloc(sizeof(sorted) + sizeof(sorted->nd[0]) nr_entries); \
107	if (sorted) { \
108	sorted->entries = RB_ROOT; \
109	__name##_sorted__sort(sorted, entries); \
110	} \
111	return sorted; \
112	} \
113	\
114	static void __name##_sorted__delete(struct __name##_sorted *sorted) \
115	{ \
116	free(sorted); \
117	} \
118	\
119	static void __name##_sorted__init_entry(struct rb_node *nd, \
120	struct __name##_sorted_entry *entry)
121
122	#define DECLARE_RESORT_RB(__name) \
123	struct __name##_sorted_entry *__name##_entry; \
124	struct __name##_sorted *__name = __name##_sorted__new
125
126	#define resort_rb__for_each(__nd, __name) \
127	for (__nd = rb_first(&__name->entries); \
128	__name##_entry = rb_entry(__nd, struct __name##_sorted_entry, \
129	rb_node), __nd; \
130	__nd = rb_next(__nd))
131
132	#define resort_rb__delete(__name) \
133	__name##_sorted__delete(__name), __name = NULL
134
135	/*
136	* Helpers for other classes that contains both an rbtree and the
137	* number of entries in it:
138	*/
139
140	/* For 'struct intlist' */
141	#define DECLARE_RESORT_RB_INTLIST(__name, __ilist) \
142	DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries, \
143	__ilist->rblist.nr_entries)
144
145	/* For 'struct machine->threads' */
146	#define DECLARE_RESORT_RB_MACHINE_THREADS(__name, __machine) \
147	DECLARE_RESORT_RB(__name)(&__machine->threads, __machine->nr_threads)
148
149	#endif /* _PERF_RESORT_RB_H_ */