rb_resort.h 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151
  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. 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. * After this it is just a matter of instantiating it and iterating it,
  28. * for a few data structures with existing rb_trees, such as 'struct machine',
  29. * helpers are available to get the rb_root and the nr_entries:
  30. DECLARE_RESORT_RB_MACHINE_THREADS(threads, machine_ptr);
  31. * This will instantiate the new rb_tree and a cursor for it, that can be used as:
  32. struct rb_node *nd;
  33. resort_rb__for_each_entry(nd, threads) {
  34. struct thread *t = threads_entry;
  35. printf("%s: %d\n", t->shortname, t->tid);
  36. }
  37. * Then delete it:
  38. resort_rb__delete(threads);
  39. * The name of the data structures and functions will have a _sorted suffix
  40. * right before the method names, i.e. will look like:
  41. *
  42. * struct threads_sorted_entry {}
  43. * threads_sorted__insert()
  44. */
  45. #define DEFINE_RESORT_RB(__name, __comp, ...) \
  46. struct __name##_sorted_entry { \
  47. struct rb_node rb_node; \
  48. __VA_ARGS__ \
  49. }; \
  50. static void __name##_sorted__init_entry(struct rb_node *nd, \
  51. struct __name##_sorted_entry *entry); \
  52. \
  53. static int __name##_sorted__cmp(struct rb_node *nda, struct rb_node *ndb) \
  54. { \
  55. struct __name##_sorted_entry *a, *b; \
  56. a = rb_entry(nda, struct __name##_sorted_entry, rb_node); \
  57. b = rb_entry(ndb, struct __name##_sorted_entry, rb_node); \
  58. return __comp; \
  59. } \
  60. \
  61. struct __name##_sorted { \
  62. struct rb_root entries; \
  63. struct __name##_sorted_entry nd[0]; \
  64. }; \
  65. \
  66. static void __name##_sorted__insert(struct __name##_sorted *sorted, \
  67. struct rb_node *sorted_nd) \
  68. { \
  69. struct rb_node **p = &sorted->entries.rb_node, *parent = NULL; \
  70. while (*p != NULL) { \
  71. parent = *p; \
  72. if (__name##_sorted__cmp(sorted_nd, parent)) \
  73. p = &(*p)->rb_left; \
  74. else \
  75. p = &(*p)->rb_right; \
  76. } \
  77. rb_link_node(sorted_nd, parent, p); \
  78. rb_insert_color(sorted_nd, &sorted->entries); \
  79. } \
  80. \
  81. static void __name##_sorted__sort(struct __name##_sorted *sorted, \
  82. struct rb_root *entries) \
  83. { \
  84. struct rb_node *nd; \
  85. unsigned int i = 0; \
  86. for (nd = rb_first(entries); nd; nd = rb_next(nd)) { \
  87. struct __name##_sorted_entry *snd = &sorted->nd[i++]; \
  88. __name##_sorted__init_entry(nd, snd); \
  89. __name##_sorted__insert(sorted, &snd->rb_node); \
  90. } \
  91. } \
  92. \
  93. static struct __name##_sorted *__name##_sorted__new(struct rb_root *entries, \
  94. int nr_entries) \
  95. { \
  96. struct __name##_sorted *sorted; \
  97. sorted = malloc(sizeof(*sorted) + sizeof(sorted->nd[0]) * nr_entries); \
  98. if (sorted) { \
  99. sorted->entries = RB_ROOT; \
  100. __name##_sorted__sort(sorted, entries); \
  101. } \
  102. return sorted; \
  103. } \
  104. \
  105. static void __name##_sorted__delete(struct __name##_sorted *sorted) \
  106. { \
  107. free(sorted); \
  108. } \
  109. \
  110. static void __name##_sorted__init_entry(struct rb_node *nd, \
  111. struct __name##_sorted_entry *entry)
  112. #define DECLARE_RESORT_RB(__name) \
  113. struct __name##_sorted_entry *__name##_entry; \
  114. struct __name##_sorted *__name = __name##_sorted__new
  115. #define resort_rb__for_each_entry(__nd, __name) \
  116. for (__nd = rb_first(&__name->entries); \
  117. __name##_entry = rb_entry(__nd, struct __name##_sorted_entry, \
  118. rb_node), __nd; \
  119. __nd = rb_next(__nd))
  120. #define resort_rb__delete(__name) \
  121. __name##_sorted__delete(__name), __name = NULL
  122. /*
  123. * Helpers for other classes that contains both an rbtree and the
  124. * number of entries in it:
  125. */
  126. /* For 'struct intlist' */
  127. #define DECLARE_RESORT_RB_INTLIST(__name, __ilist) \
  128. DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries.rb_root, \
  129. __ilist->rblist.nr_entries)
  130. /* For 'struct machine->threads' */
  131. #define DECLARE_RESORT_RB_MACHINE_THREADS(__name, __machine, hash_bucket) \
  132. DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries.rb_root, \
  133. __machine->threads[hash_bucket].nr)
  134. #endif /* _PERF_RESORT_RB_H_ */