tree.h 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675
  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 (parent == RB_LEFT(gparent, field)) { \
  366. tmp = RB_RIGHT(gparent, field); \
  367. if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
  368. RB_COLOR(tmp, field) = RB_BLACK; \
  369. RB_SET_BLACKRED(parent, gparent, field);\
  370. elm = gparent; \
  371. continue; \
  372. } \
  373. if (RB_RIGHT(parent, field) == elm) { \
  374. RB_ROTATE_LEFT(head, parent, tmp, field);\
  375. tmp = parent; \
  376. parent = elm; \
  377. elm = tmp; \
  378. } \
  379. RB_SET_BLACKRED(parent, gparent, field); \
  380. RB_ROTATE_RIGHT(head, gparent, tmp, field); \
  381. } else { \
  382. tmp = RB_LEFT(gparent, field); \
  383. if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
  384. RB_COLOR(tmp, field) = RB_BLACK; \
  385. RB_SET_BLACKRED(parent, gparent, field);\
  386. elm = gparent; \
  387. continue; \
  388. } \
  389. if (RB_LEFT(parent, field) == elm) { \
  390. RB_ROTATE_RIGHT(head, parent, tmp, field);\
  391. tmp = parent; \
  392. parent = elm; \
  393. elm = tmp; \
  394. } \
  395. RB_SET_BLACKRED(parent, gparent, field); \
  396. RB_ROTATE_LEFT(head, gparent, tmp, field); \
  397. } \
  398. } \
  399. RB_COLOR(head->rbh_root, field) = RB_BLACK; \
  400. } \
  401. \
  402. void \
  403. name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
  404. { \
  405. struct type *tmp; \
  406. while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
  407. elm != RB_ROOT(head)) { \
  408. if (RB_LEFT(parent, field) == elm) { \
  409. tmp = RB_RIGHT(parent, field); \
  410. if (RB_COLOR(tmp, field) == RB_RED) { \
  411. RB_SET_BLACKRED(tmp, parent, field); \
  412. RB_ROTATE_LEFT(head, parent, tmp, field);\
  413. tmp = RB_RIGHT(parent, field); \
  414. } \
  415. if ((RB_LEFT(tmp, field) == NULL || \
  416. RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  417. (RB_RIGHT(tmp, field) == NULL || \
  418. RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  419. RB_COLOR(tmp, field) = RB_RED; \
  420. elm = parent; \
  421. parent = RB_PARENT(elm, field); \
  422. } else { \
  423. if (RB_RIGHT(tmp, field) == NULL || \
  424. RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
  425. struct type *oleft; \
  426. if ((oleft = RB_LEFT(tmp, field)))\
  427. RB_COLOR(oleft, field) = RB_BLACK;\
  428. RB_COLOR(tmp, field) = RB_RED; \
  429. RB_ROTATE_RIGHT(head, tmp, oleft, field);\
  430. tmp = RB_RIGHT(parent, field); \
  431. } \
  432. RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  433. RB_COLOR(parent, field) = RB_BLACK; \
  434. if (RB_RIGHT(tmp, field)) \
  435. RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
  436. RB_ROTATE_LEFT(head, parent, tmp, field);\
  437. elm = RB_ROOT(head); \
  438. break; \
  439. } \
  440. } else { \
  441. tmp = RB_LEFT(parent, field); \
  442. if (RB_COLOR(tmp, field) == RB_RED) { \
  443. RB_SET_BLACKRED(tmp, parent, field); \
  444. RB_ROTATE_RIGHT(head, parent, tmp, field);\
  445. tmp = RB_LEFT(parent, field); \
  446. } \
  447. if ((RB_LEFT(tmp, field) == NULL || \
  448. RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  449. (RB_RIGHT(tmp, field) == NULL || \
  450. RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  451. RB_COLOR(tmp, field) = RB_RED; \
  452. elm = parent; \
  453. parent = RB_PARENT(elm, field); \
  454. } else { \
  455. if (RB_LEFT(tmp, field) == NULL || \
  456. RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
  457. struct type *oright; \
  458. if ((oright = RB_RIGHT(tmp, field)))\
  459. RB_COLOR(oright, field) = RB_BLACK;\
  460. RB_COLOR(tmp, field) = RB_RED; \
  461. RB_ROTATE_LEFT(head, tmp, oright, field);\
  462. tmp = RB_LEFT(parent, field); \
  463. } \
  464. RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  465. RB_COLOR(parent, field) = RB_BLACK; \
  466. if (RB_LEFT(tmp, field)) \
  467. RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
  468. RB_ROTATE_RIGHT(head, parent, tmp, field);\
  469. elm = RB_ROOT(head); \
  470. break; \
  471. } \
  472. } \
  473. } \
  474. if (elm) \
  475. RB_COLOR(elm, field) = RB_BLACK; \
  476. } \
  477. \
  478. struct type * \
  479. name##_RB_REMOVE(struct name *head, struct type *elm) \
  480. { \
  481. struct type *child, *parent, *old = elm; \
  482. int color; \
  483. if (RB_LEFT(elm, field) == NULL) \
  484. child = RB_RIGHT(elm, field); \
  485. else if (RB_RIGHT(elm, field) == NULL) \
  486. child = RB_LEFT(elm, field); \
  487. else { \
  488. struct type *left; \
  489. elm = RB_RIGHT(elm, field); \
  490. while ((left = RB_LEFT(elm, field))) \
  491. elm = left; \
  492. child = RB_RIGHT(elm, field); \
  493. parent = RB_PARENT(elm, field); \
  494. color = RB_COLOR(elm, field); \
  495. if (child) \
  496. RB_PARENT(child, field) = parent; \
  497. if (parent) { \
  498. if (RB_LEFT(parent, field) == elm) \
  499. RB_LEFT(parent, field) = child; \
  500. else \
  501. RB_RIGHT(parent, field) = child; \
  502. RB_AUGMENT(parent); \
  503. } else \
  504. RB_ROOT(head) = child; \
  505. if (RB_PARENT(elm, field) == old) \
  506. parent = elm; \
  507. (elm)->field = (old)->field; \
  508. if (RB_PARENT(old, field)) { \
  509. if (RB_LEFT(RB_PARENT(old, field), field) == old)\
  510. RB_LEFT(RB_PARENT(old, field), field) = elm;\
  511. else \
  512. RB_RIGHT(RB_PARENT(old, field), field) = elm;\
  513. RB_AUGMENT(RB_PARENT(old, field)); \
  514. } else \
  515. RB_ROOT(head) = elm; \
  516. RB_PARENT(RB_LEFT(old, field), field) = elm; \
  517. if (RB_RIGHT(old, field)) \
  518. RB_PARENT(RB_RIGHT(old, field), field) = elm; \
  519. if (parent) { \
  520. left = parent; \
  521. do { \
  522. RB_AUGMENT(left); \
  523. } while ((left = RB_PARENT(left, field))); \
  524. } \
  525. goto color; \
  526. } \
  527. parent = RB_PARENT(elm, field); \
  528. color = RB_COLOR(elm, field); \
  529. if (child) \
  530. RB_PARENT(child, field) = parent; \
  531. if (parent) { \
  532. if (RB_LEFT(parent, field) == elm) \
  533. RB_LEFT(parent, field) = child; \
  534. else \
  535. RB_RIGHT(parent, field) = child; \
  536. RB_AUGMENT(parent); \
  537. } else \
  538. RB_ROOT(head) = child; \
  539. color: \
  540. if (color == RB_BLACK) \
  541. name##_RB_REMOVE_COLOR(head, parent, child); \
  542. return (old); \
  543. } \
  544. \
  545. /* Inserts a node into the RB tree */ \
  546. struct type * \
  547. name##_RB_INSERT(struct name *head, struct type *elm) \
  548. { \
  549. struct type *tmp; \
  550. struct type *parent = NULL; \
  551. int comp = 0; \
  552. tmp = RB_ROOT(head); \
  553. while (tmp) { \
  554. parent = tmp; \
  555. comp = (cmp)(elm, parent); \
  556. if (comp < 0) \
  557. tmp = RB_LEFT(tmp, field); \
  558. else if (comp > 0) \
  559. tmp = RB_RIGHT(tmp, field); \
  560. else \
  561. return (tmp); \
  562. } \
  563. RB_SET(elm, parent, field); \
  564. if (parent != NULL) { \
  565. if (comp < 0) \
  566. RB_LEFT(parent, field) = elm; \
  567. else \
  568. RB_RIGHT(parent, field) = elm; \
  569. RB_AUGMENT(parent); \
  570. } else \
  571. RB_ROOT(head) = elm; \
  572. name##_RB_INSERT_COLOR(head, elm); \
  573. return (NULL); \
  574. } \
  575. \
  576. /* Finds the node with the same key as elm */ \
  577. struct type * \
  578. name##_RB_FIND(struct name *head, struct type *elm) \
  579. { \
  580. struct type *tmp = RB_ROOT(head); \
  581. int comp; \
  582. while (tmp) { \
  583. comp = cmp(elm, tmp); \
  584. if (comp < 0) \
  585. tmp = RB_LEFT(tmp, field); \
  586. else if (comp > 0) \
  587. tmp = RB_RIGHT(tmp, field); \
  588. else \
  589. return (tmp); \
  590. } \
  591. return (NULL); \
  592. } \
  593. \
  594. struct type * \
  595. name##_RB_NEXT(_U_ struct name *head, struct type *elm) \
  596. { \
  597. if (RB_RIGHT(elm, field)) { \
  598. elm = RB_RIGHT(elm, field); \
  599. while (RB_LEFT(elm, field)) \
  600. elm = RB_LEFT(elm, field); \
  601. } else { \
  602. if (RB_PARENT(elm, field) && \
  603. (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
  604. elm = RB_PARENT(elm, field); \
  605. else { \
  606. while (RB_PARENT(elm, field) && \
  607. (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
  608. elm = RB_PARENT(elm, field); \
  609. elm = RB_PARENT(elm, field); \
  610. } \
  611. } \
  612. return (elm); \
  613. } \
  614. \
  615. struct type * \
  616. name##_RB_MINMAX(struct name *head, int val) \
  617. { \
  618. struct type *tmp = RB_ROOT(head); \
  619. struct type *parent = NULL; \
  620. while (tmp) { \
  621. parent = tmp; \
  622. if (val < 0) \
  623. tmp = RB_LEFT(tmp, field); \
  624. else \
  625. tmp = RB_RIGHT(tmp, field); \
  626. } \
  627. return (parent); \
  628. }
  629. #define RB_NEGINF -1
  630. #define RB_INF 1
  631. #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
  632. #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
  633. #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
  634. #define RB_NEXT(name, x, y) name##_RB_NEXT(x, y)
  635. #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
  636. #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
  637. #define RB_FOREACH(x, name, head) \
  638. for ((x) = RB_MIN(name, head); \
  639. (x) != NULL; \
  640. (x) = name##_RB_NEXT(head, x))
  641. #endif /* _SYS_TREE_H_ */