tree.h 52 KB

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