rbtree.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480
  1. /*
  2. Red Black Trees
  3. (C) 1999 Andrea Arcangeli <andrea@suse.de>
  4. (C) 2002 David Woodhouse <dwmw2@infradead.org>
  5. This program is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 2 of the License, or
  8. (at your option) any later version.
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. GNU General Public License for more details.
  13. You should have received a copy of the GNU General Public License
  14. along with this program; if not, write to the Free Software
  15. Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  16. linux/lib/rbtree.c
  17. */
  18. #include <linux/rbtree.h>
  19. #include <linux/export.h>
  20. #define RB_RED 0
  21. #define RB_BLACK 1
  22. #define rb_color(r) ((r)->__rb_parent_color & 1)
  23. #define rb_is_red(r) (!rb_color(r))
  24. #define rb_is_black(r) rb_color(r)
  25. #define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0)
  26. #define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0)
  27. static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
  28. {
  29. rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
  30. }
  31. static inline void rb_set_color(struct rb_node *rb, int color)
  32. {
  33. rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color;
  34. }
  35. static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
  36. {
  37. struct rb_node *right = node->rb_right;
  38. struct rb_node *parent = rb_parent(node);
  39. if ((node->rb_right = right->rb_left))
  40. rb_set_parent(right->rb_left, node);
  41. right->rb_left = node;
  42. rb_set_parent(right, parent);
  43. if (parent)
  44. {
  45. if (node == parent->rb_left)
  46. parent->rb_left = right;
  47. else
  48. parent->rb_right = right;
  49. }
  50. else
  51. root->rb_node = right;
  52. rb_set_parent(node, right);
  53. }
  54. static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
  55. {
  56. struct rb_node *left = node->rb_left;
  57. struct rb_node *parent = rb_parent(node);
  58. if ((node->rb_left = left->rb_right))
  59. rb_set_parent(left->rb_right, node);
  60. left->rb_right = node;
  61. rb_set_parent(left, parent);
  62. if (parent)
  63. {
  64. if (node == parent->rb_right)
  65. parent->rb_right = left;
  66. else
  67. parent->rb_left = left;
  68. }
  69. else
  70. root->rb_node = left;
  71. rb_set_parent(node, left);
  72. }
  73. void rb_insert_color(struct rb_node *node, struct rb_root *root)
  74. {
  75. struct rb_node *parent, *gparent;
  76. while ((parent = rb_parent(node)) && rb_is_red(parent))
  77. {
  78. gparent = rb_parent(parent);
  79. if (parent == gparent->rb_left)
  80. {
  81. {
  82. register struct rb_node *uncle = gparent->rb_right;
  83. if (uncle && rb_is_red(uncle))
  84. {
  85. rb_set_black(uncle);
  86. rb_set_black(parent);
  87. rb_set_red(gparent);
  88. node = gparent;
  89. continue;
  90. }
  91. }
  92. if (parent->rb_right == node)
  93. {
  94. register struct rb_node *tmp;
  95. __rb_rotate_left(parent, root);
  96. tmp = parent;
  97. parent = node;
  98. node = tmp;
  99. }
  100. rb_set_black(parent);
  101. rb_set_red(gparent);
  102. __rb_rotate_right(gparent, root);
  103. } else {
  104. {
  105. register struct rb_node *uncle = gparent->rb_left;
  106. if (uncle && rb_is_red(uncle))
  107. {
  108. rb_set_black(uncle);
  109. rb_set_black(parent);
  110. rb_set_red(gparent);
  111. node = gparent;
  112. continue;
  113. }
  114. }
  115. if (parent->rb_left == node)
  116. {
  117. register struct rb_node *tmp;
  118. __rb_rotate_right(parent, root);
  119. tmp = parent;
  120. parent = node;
  121. node = tmp;
  122. }
  123. rb_set_black(parent);
  124. rb_set_red(gparent);
  125. __rb_rotate_left(gparent, root);
  126. }
  127. }
  128. rb_set_black(root->rb_node);
  129. }
  130. EXPORT_SYMBOL(rb_insert_color);
  131. static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
  132. struct rb_root *root)
  133. {
  134. struct rb_node *other;
  135. while ((!node || rb_is_black(node)) && node != root->rb_node)
  136. {
  137. if (parent->rb_left == node)
  138. {
  139. other = parent->rb_right;
  140. if (rb_is_red(other))
  141. {
  142. rb_set_black(other);
  143. rb_set_red(parent);
  144. __rb_rotate_left(parent, root);
  145. other = parent->rb_right;
  146. }
  147. if ((!other->rb_left || rb_is_black(other->rb_left)) &&
  148. (!other->rb_right || rb_is_black(other->rb_right)))
  149. {
  150. rb_set_red(other);
  151. node = parent;
  152. parent = rb_parent(node);
  153. }
  154. else
  155. {
  156. if (!other->rb_right || rb_is_black(other->rb_right))
  157. {
  158. rb_set_black(other->rb_left);
  159. rb_set_red(other);
  160. __rb_rotate_right(other, root);
  161. other = parent->rb_right;
  162. }
  163. rb_set_color(other, rb_color(parent));
  164. rb_set_black(parent);
  165. rb_set_black(other->rb_right);
  166. __rb_rotate_left(parent, root);
  167. node = root->rb_node;
  168. break;
  169. }
  170. }
  171. else
  172. {
  173. other = parent->rb_left;
  174. if (rb_is_red(other))
  175. {
  176. rb_set_black(other);
  177. rb_set_red(parent);
  178. __rb_rotate_right(parent, root);
  179. other = parent->rb_left;
  180. }
  181. if ((!other->rb_left || rb_is_black(other->rb_left)) &&
  182. (!other->rb_right || rb_is_black(other->rb_right)))
  183. {
  184. rb_set_red(other);
  185. node = parent;
  186. parent = rb_parent(node);
  187. }
  188. else
  189. {
  190. if (!other->rb_left || rb_is_black(other->rb_left))
  191. {
  192. rb_set_black(other->rb_right);
  193. rb_set_red(other);
  194. __rb_rotate_left(other, root);
  195. other = parent->rb_left;
  196. }
  197. rb_set_color(other, rb_color(parent));
  198. rb_set_black(parent);
  199. rb_set_black(other->rb_left);
  200. __rb_rotate_right(parent, root);
  201. node = root->rb_node;
  202. break;
  203. }
  204. }
  205. }
  206. if (node)
  207. rb_set_black(node);
  208. }
  209. void rb_erase(struct rb_node *node, struct rb_root *root)
  210. {
  211. struct rb_node *child, *parent;
  212. int color;
  213. if (!node->rb_left)
  214. child = node->rb_right;
  215. else if (!node->rb_right)
  216. child = node->rb_left;
  217. else
  218. {
  219. struct rb_node *old = node, *left;
  220. node = node->rb_right;
  221. while ((left = node->rb_left) != NULL)
  222. node = left;
  223. if (rb_parent(old)) {
  224. if (rb_parent(old)->rb_left == old)
  225. rb_parent(old)->rb_left = node;
  226. else
  227. rb_parent(old)->rb_right = node;
  228. } else
  229. root->rb_node = node;
  230. child = node->rb_right;
  231. parent = rb_parent(node);
  232. color = rb_color(node);
  233. if (parent == old) {
  234. parent = node;
  235. } else {
  236. if (child)
  237. rb_set_parent(child, parent);
  238. parent->rb_left = child;
  239. node->rb_right = old->rb_right;
  240. rb_set_parent(old->rb_right, node);
  241. }
  242. node->__rb_parent_color = old->__rb_parent_color;
  243. node->rb_left = old->rb_left;
  244. rb_set_parent(old->rb_left, node);
  245. goto color;
  246. }
  247. parent = rb_parent(node);
  248. color = rb_color(node);
  249. if (child)
  250. rb_set_parent(child, parent);
  251. if (parent)
  252. {
  253. if (parent->rb_left == node)
  254. parent->rb_left = child;
  255. else
  256. parent->rb_right = child;
  257. }
  258. else
  259. root->rb_node = child;
  260. color:
  261. if (color == RB_BLACK)
  262. __rb_erase_color(child, parent, root);
  263. }
  264. EXPORT_SYMBOL(rb_erase);
  265. static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
  266. {
  267. struct rb_node *parent;
  268. up:
  269. func(node, data);
  270. parent = rb_parent(node);
  271. if (!parent)
  272. return;
  273. if (node == parent->rb_left && parent->rb_right)
  274. func(parent->rb_right, data);
  275. else if (parent->rb_left)
  276. func(parent->rb_left, data);
  277. node = parent;
  278. goto up;
  279. }
  280. /*
  281. * after inserting @node into the tree, update the tree to account for
  282. * both the new entry and any damage done by rebalance
  283. */
  284. void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
  285. {
  286. if (node->rb_left)
  287. node = node->rb_left;
  288. else if (node->rb_right)
  289. node = node->rb_right;
  290. rb_augment_path(node, func, data);
  291. }
  292. EXPORT_SYMBOL(rb_augment_insert);
  293. /*
  294. * before removing the node, find the deepest node on the rebalance path
  295. * that will still be there after @node gets removed
  296. */
  297. struct rb_node *rb_augment_erase_begin(struct rb_node *node)
  298. {
  299. struct rb_node *deepest;
  300. if (!node->rb_right && !node->rb_left)
  301. deepest = rb_parent(node);
  302. else if (!node->rb_right)
  303. deepest = node->rb_left;
  304. else if (!node->rb_left)
  305. deepest = node->rb_right;
  306. else {
  307. deepest = rb_next(node);
  308. if (deepest->rb_right)
  309. deepest = deepest->rb_right;
  310. else if (rb_parent(deepest) != node)
  311. deepest = rb_parent(deepest);
  312. }
  313. return deepest;
  314. }
  315. EXPORT_SYMBOL(rb_augment_erase_begin);
  316. /*
  317. * after removal, update the tree to account for the removed entry
  318. * and any rebalance damage.
  319. */
  320. void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
  321. {
  322. if (node)
  323. rb_augment_path(node, func, data);
  324. }
  325. EXPORT_SYMBOL(rb_augment_erase_end);
  326. /*
  327. * This function returns the first node (in sort order) of the tree.
  328. */
  329. struct rb_node *rb_first(const struct rb_root *root)
  330. {
  331. struct rb_node *n;
  332. n = root->rb_node;
  333. if (!n)
  334. return NULL;
  335. while (n->rb_left)
  336. n = n->rb_left;
  337. return n;
  338. }
  339. EXPORT_SYMBOL(rb_first);
  340. struct rb_node *rb_last(const struct rb_root *root)
  341. {
  342. struct rb_node *n;
  343. n = root->rb_node;
  344. if (!n)
  345. return NULL;
  346. while (n->rb_right)
  347. n = n->rb_right;
  348. return n;
  349. }
  350. EXPORT_SYMBOL(rb_last);
  351. struct rb_node *rb_next(const struct rb_node *node)
  352. {
  353. struct rb_node *parent;
  354. if (RB_EMPTY_NODE(node))
  355. return NULL;
  356. /* If we have a right-hand child, go down and then left as far
  357. as we can. */
  358. if (node->rb_right) {
  359. node = node->rb_right;
  360. while (node->rb_left)
  361. node=node->rb_left;
  362. return (struct rb_node *)node;
  363. }
  364. /* No right-hand children. Everything down and left is
  365. smaller than us, so any 'next' node must be in the general
  366. direction of our parent. Go up the tree; any time the
  367. ancestor is a right-hand child of its parent, keep going
  368. up. First time it's a left-hand child of its parent, said
  369. parent is our 'next' node. */
  370. while ((parent = rb_parent(node)) && node == parent->rb_right)
  371. node = parent;
  372. return parent;
  373. }
  374. EXPORT_SYMBOL(rb_next);
  375. struct rb_node *rb_prev(const struct rb_node *node)
  376. {
  377. struct rb_node *parent;
  378. if (RB_EMPTY_NODE(node))
  379. return NULL;
  380. /* If we have a left-hand child, go down and then right as far
  381. as we can. */
  382. if (node->rb_left) {
  383. node = node->rb_left;
  384. while (node->rb_right)
  385. node=node->rb_right;
  386. return (struct rb_node *)node;
  387. }
  388. /* No left-hand children. Go up till we find an ancestor which
  389. is a right-hand child of its parent */
  390. while ((parent = rb_parent(node)) && node == parent->rb_left)
  391. node = parent;
  392. return parent;
  393. }
  394. EXPORT_SYMBOL(rb_prev);
  395. void rb_replace_node(struct rb_node *victim, struct rb_node *new,
  396. struct rb_root *root)
  397. {
  398. struct rb_node *parent = rb_parent(victim);
  399. /* Set the surrounding nodes to point to the replacement */
  400. if (parent) {
  401. if (victim == parent->rb_left)
  402. parent->rb_left = new;
  403. else
  404. parent->rb_right = new;
  405. } else {
  406. root->rb_node = new;
  407. }
  408. if (victim->rb_left)
  409. rb_set_parent(victim->rb_left, new);
  410. if (victim->rb_right)
  411. rb_set_parent(victim->rb_right, new);
  412. /* Copy the pointers/colour from the victim to the replacement */
  413. *new = *victim;
  414. }
  415. EXPORT_SYMBOL(rb_replace_node);