tree.h 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685
  1. /* $OpenBSD: tree.h,v 1.6 2002/06/11 22:09:52 provos Exp $ */
  2. /*
  3. * Copyright 2002 Niels Provos <provos@citi.umich.edu>
  4. * All rights reserved.
  5. *
  6. * Redistribution and use in source and binary forms, with or without
  7. * modification, are permitted provided that the following conditions
  8. * are met:
  9. * 1. Redistributions of source code must retain the above copyright
  10. * notice, this list of conditions and the following disclaimer.
  11. * 2. Redistributions in binary form must reproduce the above copyright
  12. * notice, this list of conditions and the following disclaimer in the
  13. * documentation and/or other materials provided with the distribution.
  14. *
  15. * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16. * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17. * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19. * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20. * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21. * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22. * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24. * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25. */
  26. #ifndef _SYS_TREE_H_
  27. #define _SYS_TREE_H_
  28. /*
  29. * This file defines data structures for different types of trees:
  30. * splay trees and red-black trees.
  31. *
  32. * A splay tree is a self-organizing data structure. Every operation
  33. * on the tree causes a splay to happen. The splay moves the requested
  34. * node to the root of the tree and partly rebalances it.
  35. *
  36. * This has the benefit that request locality causes faster lookups as
  37. * the requested nodes move to the top of the tree. On the other hand,
  38. * every lookup causes memory writes.
  39. *
  40. * The Balance Theorem bounds the total access time for m operations
  41. * and n inserts on an initially empty tree as O((m + n)lg n). The
  42. * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
  43. *
  44. * A red-black tree is a binary search tree with the node color as an
  45. * extra attribute. It fulfills a set of conditions:
  46. * - every search path from the root to a leaf consists of the
  47. * same number of black nodes,
  48. * - each red node (except for the root) has a black parent,
  49. * - each leaf node is black.
  50. *
  51. * Every operation on a red-black tree is bounded as O(lg n).
  52. * The maximum height of a red-black tree is 2lg (n+1).
  53. */
  54. #define SPLAY_HEAD(name, type) \
  55. struct name { \
  56. struct type *sph_root; /* root of the tree */ \
  57. }
  58. #define SPLAY_INITIALIZER(root) \
  59. { NULL }
  60. #define SPLAY_INIT(root) do { \
  61. (root)->sph_root = NULL; \
  62. } while (0)
  63. #define SPLAY_ENTRY(type) \
  64. struct { \
  65. struct type *spe_left; /* left element */ \
  66. struct type *spe_right; /* right element */ \
  67. }
  68. #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
  69. #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
  70. #define SPLAY_ROOT(head) (head)->sph_root
  71. #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
  72. /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
  73. #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
  74. SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
  75. SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
  76. (head)->sph_root = tmp; \
  77. } while (0)
  78. #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
  79. SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
  80. SPLAY_LEFT(tmp, field) = (head)->sph_root; \
  81. (head)->sph_root = tmp; \
  82. } while (0)
  83. #define SPLAY_LINKLEFT(head, tmp, field) do { \
  84. SPLAY_LEFT(tmp, field) = (head)->sph_root; \
  85. tmp = (head)->sph_root; \
  86. (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
  87. } while (0)
  88. #define SPLAY_LINKRIGHT(head, tmp, field) do { \
  89. SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
  90. tmp = (head)->sph_root; \
  91. (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
  92. } while (0)
  93. #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
  94. SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
  95. SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
  96. SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
  97. SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
  98. } while (0)
  99. /* Generates prototypes and inline functions */
  100. #define SPLAY_PROTOTYPE(name, type, field, cmp) \
  101. void name##_SPLAY(struct name *, struct type *); \
  102. void name##_SPLAY_MINMAX(struct name *, int); \
  103. struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
  104. struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
  105. \
  106. /* Finds the node with the same key as elm */ \
  107. static __inline struct type * \
  108. name##_SPLAY_FIND(struct name *head, struct type *elm) \
  109. { \
  110. if (SPLAY_EMPTY(head)) \
  111. return(NULL); \
  112. name##_SPLAY(head, elm); \
  113. if ((cmp)(elm, (head)->sph_root) == 0) \
  114. return (head->sph_root); \
  115. return (NULL); \
  116. } \
  117. \
  118. static __inline struct type * \
  119. name##_SPLAY_NEXT(struct name *head, struct type *elm) \
  120. { \
  121. name##_SPLAY(head, elm); \
  122. if (SPLAY_RIGHT(elm, field) != NULL) { \
  123. elm = SPLAY_RIGHT(elm, field); \
  124. while (SPLAY_LEFT(elm, field) != NULL) { \
  125. elm = SPLAY_LEFT(elm, field); \
  126. } \
  127. } else \
  128. elm = NULL; \
  129. return (elm); \
  130. } \
  131. \
  132. static __inline struct type * \
  133. name##_SPLAY_MIN_MAX(struct name *head, int val) \
  134. { \
  135. name##_SPLAY_MINMAX(head, val); \
  136. return (SPLAY_ROOT(head)); \
  137. }
  138. /* Main splay operation.
  139. * Moves node close to the key of elm to top
  140. */
  141. #define SPLAY_GENERATE(name, type, field, cmp) \
  142. struct type * \
  143. name##_SPLAY_INSERT(struct name *head, struct type *elm) \
  144. { \
  145. if (SPLAY_EMPTY(head)) { \
  146. SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
  147. } else { \
  148. int __comp; \
  149. name##_SPLAY(head, elm); \
  150. __comp = (cmp)(elm, (head)->sph_root); \
  151. if(__comp < 0) { \
  152. SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
  153. SPLAY_RIGHT(elm, field) = (head)->sph_root; \
  154. SPLAY_LEFT((head)->sph_root, field) = NULL; \
  155. } else if (__comp > 0) { \
  156. SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
  157. SPLAY_LEFT(elm, field) = (head)->sph_root; \
  158. SPLAY_RIGHT((head)->sph_root, field) = NULL; \
  159. } else \
  160. return ((head)->sph_root); \
  161. } \
  162. (head)->sph_root = (elm); \
  163. return (NULL); \
  164. } \
  165. \
  166. struct type * \
  167. name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
  168. { \
  169. struct type *__tmp; \
  170. if (SPLAY_EMPTY(head)) \
  171. return (NULL); \
  172. name##_SPLAY(head, elm); \
  173. if ((cmp)(elm, (head)->sph_root) == 0) { \
  174. if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
  175. (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
  176. } else { \
  177. __tmp = SPLAY_RIGHT((head)->sph_root, field); \
  178. (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
  179. name##_SPLAY(head, elm); \
  180. SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
  181. } \
  182. return (elm); \
  183. } \
  184. return (NULL); \
  185. } \
  186. \
  187. void \
  188. name##_SPLAY(struct name *head, struct type *elm) \
  189. { \
  190. struct type __node, *__left, *__right, *__tmp; \
  191. int __comp; \
  192. \
  193. SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
  194. __left = __right = &__node; \
  195. \
  196. while ((__comp = (cmp)(elm, (head)->sph_root))) { \
  197. if (__comp < 0) { \
  198. __tmp = SPLAY_LEFT((head)->sph_root, field); \
  199. if (__tmp == NULL) \
  200. break; \
  201. if ((cmp)(elm, __tmp) < 0){ \
  202. SPLAY_ROTATE_RIGHT(head, __tmp, field); \
  203. if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
  204. break; \
  205. } \
  206. SPLAY_LINKLEFT(head, __right, field); \
  207. } else if (__comp > 0) { \
  208. __tmp = SPLAY_RIGHT((head)->sph_root, field); \
  209. if (__tmp == NULL) \
  210. break; \
  211. if ((cmp)(elm, __tmp) > 0){ \
  212. SPLAY_ROTATE_LEFT(head, __tmp, field); \
  213. if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
  214. break; \
  215. } \
  216. SPLAY_LINKRIGHT(head, __left, field); \
  217. } \
  218. } \
  219. SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
  220. } \
  221. \
  222. /* Splay with either the minimum or the maximum element \
  223. * Used to find minimum or maximum element in tree. \
  224. */ \
  225. void name##_SPLAY_MINMAX(struct name *head, int __comp) \
  226. { \
  227. struct type __node, *__left, *__right, *__tmp; \
  228. \
  229. SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
  230. __left = __right = &__node; \
  231. \
  232. while (1) { \
  233. if (__comp < 0) { \
  234. __tmp = SPLAY_LEFT((head)->sph_root, field); \
  235. if (__tmp == NULL) \
  236. break; \
  237. if (__comp < 0){ \
  238. SPLAY_ROTATE_RIGHT(head, __tmp, field); \
  239. if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
  240. break; \
  241. } \
  242. SPLAY_LINKLEFT(head, __right, field); \
  243. } else if (__comp > 0) { \
  244. __tmp = SPLAY_RIGHT((head)->sph_root, field); \
  245. if (__tmp == NULL) \
  246. break; \
  247. if (__comp > 0) { \
  248. SPLAY_ROTATE_LEFT(head, __tmp, field); \
  249. if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
  250. break; \
  251. } \
  252. SPLAY_LINKRIGHT(head, __left, field); \
  253. } \
  254. } \
  255. SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
  256. }
  257. #define SPLAY_NEGINF -1
  258. #define SPLAY_INF 1
  259. #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
  260. #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
  261. #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
  262. #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
  263. #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
  264. : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
  265. #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
  266. : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
  267. #define SPLAY_FOREACH(x, name, head) \
  268. for ((x) = SPLAY_MIN(name, head); \
  269. (x) != NULL; \
  270. (x) = SPLAY_NEXT(name, head, x))
  271. /* Macros that define a red-back tree */
  272. #define RB_HEAD(name, type) \
  273. struct name { \
  274. struct type *rbh_root; /* root of the tree */ \
  275. }
  276. #define RB_INITIALIZER(root) \
  277. { NULL }
  278. #define RB_INIT(root) do { \
  279. (root)->rbh_root = NULL; \
  280. } while (0)
  281. #define RB_BLACK 0
  282. #define RB_RED 1
  283. #define RB_ENTRY(type) \
  284. struct { \
  285. struct type *rbe_left; /* left element */ \
  286. struct type *rbe_right; /* right element */ \
  287. struct type *rbe_parent; /* parent element */ \
  288. int rbe_color; /* node color */ \
  289. }
  290. #define RB_LEFT(elm, field) (elm)->field.rbe_left
  291. #define RB_RIGHT(elm, field) (elm)->field.rbe_right
  292. #define RB_PARENT(elm, field) (elm)->field.rbe_parent
  293. #define RB_COLOR(elm, field) (elm)->field.rbe_color
  294. #define RB_ROOT(head) (head)->rbh_root
  295. #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
  296. #define RB_SET(elm, parent, field) do { \
  297. RB_PARENT(elm, field) = parent; \
  298. RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
  299. RB_COLOR(elm, field) = RB_RED; \
  300. } while (0)
  301. #define RB_SET_BLACKRED(black, red, field) do { \
  302. RB_COLOR(black, field) = RB_BLACK; \
  303. RB_COLOR(red, field) = RB_RED; \
  304. } while (0)
  305. #ifndef RB_AUGMENT
  306. #define RB_AUGMENT(x)
  307. #endif
  308. #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
  309. (tmp) = RB_RIGHT(elm, field); \
  310. if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
  311. RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
  312. } \
  313. RB_AUGMENT(elm); \
  314. if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
  315. if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
  316. RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
  317. else \
  318. RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
  319. RB_AUGMENT(RB_PARENT(elm, field)); \
  320. } else \
  321. (head)->rbh_root = (tmp); \
  322. RB_LEFT(tmp, field) = (elm); \
  323. RB_PARENT(elm, field) = (tmp); \
  324. RB_AUGMENT(tmp); \
  325. } while (0)
  326. #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
  327. (tmp) = RB_LEFT(elm, field); \
  328. if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
  329. RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
  330. } \
  331. RB_AUGMENT(elm); \
  332. if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
  333. if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
  334. RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
  335. else \
  336. RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
  337. RB_AUGMENT(RB_PARENT(elm, field)); \
  338. } else \
  339. (head)->rbh_root = (tmp); \
  340. RB_RIGHT(tmp, field) = (elm); \
  341. RB_PARENT(elm, field) = (tmp); \
  342. RB_AUGMENT(tmp); \
  343. } while (0)
  344. /* Generates prototypes and inline functions */
  345. #define RB_PROTOTYPE(name, type, field, cmp) \
  346. void name##_RB_INSERT_COLOR(struct name *, struct type *); \
  347. void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
  348. struct type *name##_RB_REMOVE(struct name *, struct type *); \
  349. struct type *name##_RB_INSERT(struct name *, struct type *); \
  350. struct type *name##_RB_FIND(struct name *, struct type *); \
  351. struct type *name##_RB_NEXT(struct name *, struct type *); \
  352. struct type *name##_RB_MINMAX(struct name *, int); \
  353. \
  354. /* Main rb operation.
  355. * Moves node close to the key of elm to top
  356. */
  357. #define RB_GENERATE(name, type, field, cmp) \
  358. void \
  359. name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
  360. { \
  361. struct type *parent, *gparent, *tmp; \
  362. while ((parent = RB_PARENT(elm, field)) && \
  363. RB_COLOR(parent, field) == RB_RED) { \
  364. gparent = RB_PARENT(parent, field); \
  365. if (!gparent) \
  366. continue; \
  367. if (parent == RB_LEFT(gparent, field)) { \
  368. tmp = RB_RIGHT(gparent, field); \
  369. if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
  370. RB_COLOR(tmp, field) = RB_BLACK; \
  371. RB_SET_BLACKRED(parent, gparent, field);\
  372. elm = gparent; \
  373. continue; \
  374. } \
  375. if (RB_RIGHT(parent, field) == elm) { \
  376. RB_ROTATE_LEFT(head, parent, tmp, field);\
  377. tmp = parent; \
  378. parent = elm; \
  379. elm = tmp; \
  380. } \
  381. RB_SET_BLACKRED(parent, gparent, field); \
  382. RB_ROTATE_RIGHT(head, gparent, tmp, field); \
  383. } else { \
  384. tmp = RB_LEFT(gparent, field); \
  385. if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
  386. RB_COLOR(tmp, field) = RB_BLACK; \
  387. RB_SET_BLACKRED(parent, gparent, field);\
  388. elm = gparent; \
  389. continue; \
  390. } \
  391. if (RB_LEFT(parent, field) == elm) { \
  392. RB_ROTATE_RIGHT(head, parent, tmp, field);\
  393. tmp = parent; \
  394. parent = elm; \
  395. elm = tmp; \
  396. } \
  397. RB_SET_BLACKRED(parent, gparent, field); \
  398. RB_ROTATE_LEFT(head, gparent, tmp, field); \
  399. } \
  400. } \
  401. RB_COLOR(head->rbh_root, field) = RB_BLACK; \
  402. } \
  403. \
  404. void \
  405. name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
  406. { \
  407. struct type *tmp; \
  408. while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
  409. elm != RB_ROOT(head)) { \
  410. if (RB_LEFT(parent, field) == elm) { \
  411. tmp = RB_RIGHT(parent, field); \
  412. if (!tmp) \
  413. continue; \
  414. if (RB_COLOR(tmp, field) == RB_RED) { \
  415. RB_SET_BLACKRED(tmp, parent, field); \
  416. RB_ROTATE_LEFT(head, parent, tmp, field);\
  417. tmp = RB_RIGHT(parent, field); \
  418. } \
  419. if (!tmp) \
  420. continue; \
  421. if ((RB_LEFT(tmp, field) == NULL || \
  422. RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  423. (RB_RIGHT(tmp, field) == NULL || \
  424. RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  425. RB_COLOR(tmp, field) = RB_RED; \
  426. elm = parent; \
  427. parent = RB_PARENT(elm, field); \
  428. } else { \
  429. if (RB_RIGHT(tmp, field) == NULL || \
  430. RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
  431. struct type *oleft; \
  432. if ((oleft = RB_LEFT(tmp, field)))\
  433. RB_COLOR(oleft, field) = RB_BLACK;\
  434. RB_COLOR(tmp, field) = RB_RED; \
  435. RB_ROTATE_RIGHT(head, tmp, oleft, field);\
  436. tmp = RB_RIGHT(parent, field); \
  437. } \
  438. RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  439. RB_COLOR(parent, field) = RB_BLACK; \
  440. if (RB_RIGHT(tmp, field)) \
  441. RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
  442. RB_ROTATE_LEFT(head, parent, tmp, field);\
  443. elm = RB_ROOT(head); \
  444. break; \
  445. } \
  446. } else { \
  447. tmp = RB_LEFT(parent, field); \
  448. if (!tmp) \
  449. continue; \
  450. if (RB_COLOR(tmp, field) == RB_RED) { \
  451. RB_SET_BLACKRED(tmp, parent, field); \
  452. RB_ROTATE_RIGHT(head, parent, tmp, field);\
  453. tmp = RB_LEFT(parent, field); \
  454. } \
  455. if (!tmp) \
  456. continue; \
  457. if ((RB_LEFT(tmp, field) == NULL || \
  458. RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  459. (RB_RIGHT(tmp, field) == NULL || \
  460. RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  461. RB_COLOR(tmp, field) = RB_RED; \
  462. elm = parent; \
  463. parent = RB_PARENT(elm, field); \
  464. } else { \
  465. if (RB_LEFT(tmp, field) == NULL || \
  466. RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
  467. struct type *oright; \
  468. if ((oright = RB_RIGHT(tmp, field)))\
  469. RB_COLOR(oright, field) = RB_BLACK;\
  470. RB_COLOR(tmp, field) = RB_RED; \
  471. RB_ROTATE_LEFT(head, tmp, oright, field);\
  472. tmp = RB_LEFT(parent, field); \
  473. } \
  474. RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  475. RB_COLOR(parent, field) = RB_BLACK; \
  476. if (RB_LEFT(tmp, field)) \
  477. RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
  478. RB_ROTATE_RIGHT(head, parent, tmp, field);\
  479. elm = RB_ROOT(head); \
  480. break; \
  481. } \
  482. } \
  483. } \
  484. if (elm) \
  485. RB_COLOR(elm, field) = RB_BLACK; \
  486. } \
  487. \
  488. struct type * \
  489. name##_RB_REMOVE(struct name *head, struct type *elm) \
  490. { \
  491. struct type *child, *parent, *old = elm; \
  492. int color; \
  493. if (RB_LEFT(elm, field) == NULL) \
  494. child = RB_RIGHT(elm, field); \
  495. else if (RB_RIGHT(elm, field) == NULL) \
  496. child = RB_LEFT(elm, field); \
  497. else { \
  498. struct type *left; \
  499. elm = RB_RIGHT(elm, field); \
  500. while ((left = RB_LEFT(elm, field))) \
  501. elm = left; \
  502. child = RB_RIGHT(elm, field); \
  503. parent = RB_PARENT(elm, field); \
  504. color = RB_COLOR(elm, field); \
  505. if (child) \
  506. RB_PARENT(child, field) = parent; \
  507. if (parent) { \
  508. if (RB_LEFT(parent, field) == elm) \
  509. RB_LEFT(parent, field) = child; \
  510. else \
  511. RB_RIGHT(parent, field) = child; \
  512. RB_AUGMENT(parent); \
  513. } else \
  514. RB_ROOT(head) = child; \
  515. if (RB_PARENT(elm, field) == old) \
  516. parent = elm; \
  517. (elm)->field = (old)->field; \
  518. if (RB_PARENT(old, field)) { \
  519. if (RB_LEFT(RB_PARENT(old, field), field) == old)\
  520. RB_LEFT(RB_PARENT(old, field), field) = elm;\
  521. else \
  522. RB_RIGHT(RB_PARENT(old, field), field) = elm;\
  523. RB_AUGMENT(RB_PARENT(old, field)); \
  524. } else \
  525. RB_ROOT(head) = elm; \
  526. RB_PARENT(RB_LEFT(old, field), field) = elm; \
  527. if (RB_RIGHT(old, field)) \
  528. RB_PARENT(RB_RIGHT(old, field), field) = elm; \
  529. if (parent) { \
  530. left = parent; \
  531. do { \
  532. RB_AUGMENT(left); \
  533. } while ((left = RB_PARENT(left, field))); \
  534. } \
  535. goto color; \
  536. } \
  537. parent = RB_PARENT(elm, field); \
  538. color = RB_COLOR(elm, field); \
  539. if (child) \
  540. RB_PARENT(child, field) = parent; \
  541. if (parent) { \
  542. if (RB_LEFT(parent, field) == elm) \
  543. RB_LEFT(parent, field) = child; \
  544. else \
  545. RB_RIGHT(parent, field) = child; \
  546. RB_AUGMENT(parent); \
  547. } else \
  548. RB_ROOT(head) = child; \
  549. color: \
  550. if (color == RB_BLACK) \
  551. name##_RB_REMOVE_COLOR(head, parent, child); \
  552. return (old); \
  553. } \
  554. \
  555. /* Inserts a node into the RB tree */ \
  556. struct type * \
  557. name##_RB_INSERT(struct name *head, struct type *elm) \
  558. { \
  559. struct type *tmp; \
  560. struct type *parent = NULL; \
  561. int comp = 0; \
  562. tmp = RB_ROOT(head); \
  563. while (tmp) { \
  564. parent = tmp; \
  565. comp = (cmp)(elm, parent); \
  566. if (comp < 0) \
  567. tmp = RB_LEFT(tmp, field); \
  568. else if (comp > 0) \
  569. tmp = RB_RIGHT(tmp, field); \
  570. else \
  571. return (tmp); \
  572. } \
  573. RB_SET(elm, parent, field); \
  574. if (parent != NULL) { \
  575. if (comp < 0) \
  576. RB_LEFT(parent, field) = elm; \
  577. else \
  578. RB_RIGHT(parent, field) = elm; \
  579. RB_AUGMENT(parent); \
  580. } else \
  581. RB_ROOT(head) = elm; \
  582. name##_RB_INSERT_COLOR(head, elm); \
  583. return (NULL); \
  584. } \
  585. \
  586. /* Finds the node with the same key as elm */ \
  587. struct type * \
  588. name##_RB_FIND(struct name *head, struct type *elm) \
  589. { \
  590. struct type *tmp = RB_ROOT(head); \
  591. int comp; \
  592. while (tmp) { \
  593. comp = cmp(elm, tmp); \
  594. if (comp < 0) \
  595. tmp = RB_LEFT(tmp, field); \
  596. else if (comp > 0) \
  597. tmp = RB_RIGHT(tmp, field); \
  598. else \
  599. return (tmp); \
  600. } \
  601. return (NULL); \
  602. } \
  603. \
  604. struct type * \
  605. name##_RB_NEXT(_U_ struct name *head, struct type *elm) \
  606. { \
  607. if (RB_RIGHT(elm, field)) { \
  608. elm = RB_RIGHT(elm, field); \
  609. while (RB_LEFT(elm, field)) \
  610. elm = RB_LEFT(elm, field); \
  611. } else { \
  612. if (RB_PARENT(elm, field) && \
  613. (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
  614. elm = RB_PARENT(elm, field); \
  615. else { \
  616. while (RB_PARENT(elm, field) && \
  617. (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
  618. elm = RB_PARENT(elm, field); \
  619. elm = RB_PARENT(elm, field); \
  620. } \
  621. } \
  622. return (elm); \
  623. } \
  624. \
  625. struct type * \
  626. name##_RB_MINMAX(struct name *head, int val) \
  627. { \
  628. struct type *tmp = RB_ROOT(head); \
  629. struct type *parent = NULL; \
  630. while (tmp) { \
  631. parent = tmp; \
  632. if (val < 0) \
  633. tmp = RB_LEFT(tmp, field); \
  634. else \
  635. tmp = RB_RIGHT(tmp, field); \
  636. } \
  637. return (parent); \
  638. }
  639. #define RB_NEGINF -1
  640. #define RB_INF 1
  641. #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
  642. #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
  643. #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
  644. #define RB_NEXT(name, x, y) name##_RB_NEXT(x, y)
  645. #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
  646. #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
  647. #define RB_FOREACH(x, name, head) \
  648. for ((x) = RB_MIN(name, head); \
  649. (x) != NULL; \
  650. (x) = name##_RB_NEXT(head, x))
  651. #endif /* _SYS_TREE_H_ */