rbtree_augmented.h 6.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219
  1. /* SPDX-License-Identifier: GPL-2.0+ */
  2. /*
  3. Red Black Trees
  4. (C) 1999 Andrea Arcangeli <andrea@suse.de>
  5. (C) 2002 David Woodhouse <dwmw2@infradead.org>
  6. (C) 2012 Michel Lespinasse <walken@google.com>
  7. linux/include/linux/rbtree_augmented.h
  8. */
  9. #ifndef _LINUX_RBTREE_AUGMENTED_H
  10. #define _LINUX_RBTREE_AUGMENTED_H
  11. #include <linux/compiler.h>
  12. #include <linux/rbtree.h>
  13. /*
  14. * Please note - only struct rb_augment_callbacks and the prototypes for
  15. * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
  16. * The rest are implementation details you are not expected to depend on.
  17. *
  18. * See Documentation/rbtree.txt for documentation and samples.
  19. */
  20. struct rb_augment_callbacks {
  21. void (*propagate)(struct rb_node *node, struct rb_node *stop);
  22. void (*copy)(struct rb_node *old, struct rb_node *new);
  23. void (*rotate)(struct rb_node *old, struct rb_node *new);
  24. };
  25. extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
  26. void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
  27. static inline void
  28. rb_insert_augmented(struct rb_node *node, struct rb_root *root,
  29. const struct rb_augment_callbacks *augment)
  30. {
  31. __rb_insert_augmented(node, root, augment->rotate);
  32. }
  33. #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
  34. rbtype, rbaugmented, rbcompute) \
  35. static inline void \
  36. rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
  37. { \
  38. while (rb != stop) { \
  39. rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
  40. rbtype augmented = rbcompute(node); \
  41. if (node->rbaugmented == augmented) \
  42. break; \
  43. node->rbaugmented = augmented; \
  44. rb = rb_parent(&node->rbfield); \
  45. } \
  46. } \
  47. static inline void \
  48. rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
  49. { \
  50. rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
  51. rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
  52. new->rbaugmented = old->rbaugmented; \
  53. } \
  54. static void \
  55. rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
  56. { \
  57. rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
  58. rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
  59. new->rbaugmented = old->rbaugmented; \
  60. old->rbaugmented = rbcompute(old); \
  61. } \
  62. rbstatic const struct rb_augment_callbacks rbname = { \
  63. rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
  64. };
  65. #define RB_RED 0
  66. #define RB_BLACK 1
  67. #define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
  68. #define __rb_color(pc) ((pc) & 1)
  69. #define __rb_is_black(pc) __rb_color(pc)
  70. #define __rb_is_red(pc) (!__rb_color(pc))
  71. #define rb_color(rb) __rb_color((rb)->__rb_parent_color)
  72. #define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
  73. #define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
  74. static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
  75. {
  76. rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
  77. }
  78. static inline void rb_set_parent_color(struct rb_node *rb,
  79. struct rb_node *p, int color)
  80. {
  81. rb->__rb_parent_color = (unsigned long)p | color;
  82. }
  83. static inline void
  84. __rb_change_child(struct rb_node *old, struct rb_node *new,
  85. struct rb_node *parent, struct rb_root *root)
  86. {
  87. if (parent) {
  88. if (parent->rb_left == old)
  89. parent->rb_left = new;
  90. else
  91. parent->rb_right = new;
  92. } else
  93. root->rb_node = new;
  94. }
  95. extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
  96. void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
  97. static __always_inline struct rb_node *
  98. __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
  99. const struct rb_augment_callbacks *augment)
  100. {
  101. struct rb_node *child = node->rb_right, *tmp = node->rb_left;
  102. struct rb_node *parent, *rebalance;
  103. unsigned long pc;
  104. if (!tmp) {
  105. /*
  106. * Case 1: node to erase has no more than 1 child (easy!)
  107. *
  108. * Note that if there is one child it must be red due to 5)
  109. * and node must be black due to 4). We adjust colors locally
  110. * so as to bypass __rb_erase_color() later on.
  111. */
  112. pc = node->__rb_parent_color;
  113. parent = __rb_parent(pc);
  114. __rb_change_child(node, child, parent, root);
  115. if (child) {
  116. child->__rb_parent_color = pc;
  117. rebalance = NULL;
  118. } else
  119. rebalance = __rb_is_black(pc) ? parent : NULL;
  120. tmp = parent;
  121. } else if (!child) {
  122. /* Still case 1, but this time the child is node->rb_left */
  123. tmp->__rb_parent_color = pc = node->__rb_parent_color;
  124. parent = __rb_parent(pc);
  125. __rb_change_child(node, tmp, parent, root);
  126. rebalance = NULL;
  127. tmp = parent;
  128. } else {
  129. struct rb_node *successor = child, *child2;
  130. tmp = child->rb_left;
  131. if (!tmp) {
  132. /*
  133. * Case 2: node's successor is its right child
  134. *
  135. * (n) (s)
  136. * / \ / \
  137. * (x) (s) -> (x) (c)
  138. * \
  139. * (c)
  140. */
  141. parent = successor;
  142. child2 = successor->rb_right;
  143. augment->copy(node, successor);
  144. } else {
  145. /*
  146. * Case 3: node's successor is leftmost under
  147. * node's right child subtree
  148. *
  149. * (n) (s)
  150. * / \ / \
  151. * (x) (y) -> (x) (y)
  152. * / /
  153. * (p) (p)
  154. * / /
  155. * (s) (c)
  156. * \
  157. * (c)
  158. */
  159. do {
  160. parent = successor;
  161. successor = tmp;
  162. tmp = tmp->rb_left;
  163. } while (tmp);
  164. parent->rb_left = child2 = successor->rb_right;
  165. successor->rb_right = child;
  166. rb_set_parent(child, successor);
  167. augment->copy(node, successor);
  168. augment->propagate(parent, successor);
  169. }
  170. successor->rb_left = tmp = node->rb_left;
  171. rb_set_parent(tmp, successor);
  172. pc = node->__rb_parent_color;
  173. tmp = __rb_parent(pc);
  174. __rb_change_child(node, successor, tmp, root);
  175. if (child2) {
  176. successor->__rb_parent_color = pc;
  177. rb_set_parent_color(child2, parent, RB_BLACK);
  178. rebalance = NULL;
  179. } else {
  180. unsigned long pc2 = successor->__rb_parent_color;
  181. successor->__rb_parent_color = pc;
  182. rebalance = __rb_is_black(pc2) ? parent : NULL;
  183. }
  184. tmp = successor;
  185. }
  186. augment->propagate(tmp, NULL);
  187. return rebalance;
  188. }
  189. static __always_inline void
  190. rb_erase_augmented(struct rb_node *node, struct rb_root *root,
  191. const struct rb_augment_callbacks *augment)
  192. {
  193. struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
  194. if (rebalance)
  195. __rb_erase_color(rebalance, root, augment->rotate);
  196. }
  197. #endif /* _LINUX_RBTREE_AUGMENTED_H */