sys-tree.h 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677
  1. /* $OpenBSD: tree.h,v 1.9 2004/11/24 18:10:42 tdeval 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-black 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. } else \
  320. (head)->rbh_root = (tmp); \
  321. RB_LEFT(tmp, field) = (elm); \
  322. RB_PARENT(elm, field) = (tmp); \
  323. RB_AUGMENT(tmp); \
  324. if ((RB_PARENT(tmp, field))) \
  325. RB_AUGMENT(RB_PARENT(tmp, field)); \
  326. } while (0)
  327. #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
  328. (tmp) = RB_LEFT(elm, field); \
  329. if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
  330. RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
  331. } \
  332. RB_AUGMENT(elm); \
  333. if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
  334. if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
  335. RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
  336. else \
  337. RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
  338. } else \
  339. (head)->rbh_root = (tmp); \
  340. RB_RIGHT(tmp, field) = (elm); \
  341. RB_PARENT(elm, field) = (tmp); \
  342. RB_AUGMENT(tmp); \
  343. if ((RB_PARENT(tmp, field))) \
  344. RB_AUGMENT(RB_PARENT(tmp, field)); \
  345. } while (0)
  346. /* Generates prototypes and inline functions */
  347. #define RB_PROTOTYPE(name, type, field, cmp) \
  348. void name##_RB_INSERT_COLOR(struct name *, struct type *); \
  349. void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
  350. struct type *name##_RB_REMOVE(struct name *, struct type *); \
  351. struct type *name##_RB_INSERT(struct name *, struct type *); \
  352. struct type *name##_RB_FIND(struct name *, struct type *); \
  353. struct type *name##_RB_NEXT(struct type *); \
  354. struct type *name##_RB_MINMAX(struct name *, int); \
  355. \
  356. /* Main rb operation.
  357. * Moves node close to the key of elm to top
  358. */
  359. #define RB_GENERATE(name, type, field, cmp) \
  360. void \
  361. name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
  362. { \
  363. struct type *parent, *gparent, *tmp; \
  364. while ((parent = RB_PARENT(elm, field)) && \
  365. RB_COLOR(parent, field) == RB_RED) { \
  366. gparent = RB_PARENT(parent, field); \
  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 (RB_COLOR(tmp, field) == RB_RED) { \
  413. RB_SET_BLACKRED(tmp, parent, field); \
  414. RB_ROTATE_LEFT(head, parent, tmp, field);\
  415. tmp = RB_RIGHT(parent, field); \
  416. } \
  417. if ((RB_LEFT(tmp, field) == NULL || \
  418. RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  419. (RB_RIGHT(tmp, field) == NULL || \
  420. RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  421. RB_COLOR(tmp, field) = RB_RED; \
  422. elm = parent; \
  423. parent = RB_PARENT(elm, field); \
  424. } else { \
  425. if (RB_RIGHT(tmp, field) == NULL || \
  426. RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
  427. struct type *oleft; \
  428. if ((oleft = RB_LEFT(tmp, field)))\
  429. RB_COLOR(oleft, field) = RB_BLACK;\
  430. RB_COLOR(tmp, field) = RB_RED; \
  431. RB_ROTATE_RIGHT(head, tmp, oleft, field);\
  432. tmp = RB_RIGHT(parent, field); \
  433. } \
  434. RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  435. RB_COLOR(parent, field) = RB_BLACK; \
  436. if (RB_RIGHT(tmp, field)) \
  437. RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
  438. RB_ROTATE_LEFT(head, parent, tmp, field);\
  439. elm = RB_ROOT(head); \
  440. break; \
  441. } \
  442. } else { \
  443. tmp = RB_LEFT(parent, field); \
  444. if (RB_COLOR(tmp, field) == RB_RED) { \
  445. RB_SET_BLACKRED(tmp, parent, field); \
  446. RB_ROTATE_RIGHT(head, parent, tmp, field);\
  447. tmp = RB_LEFT(parent, field); \
  448. } \
  449. if ((RB_LEFT(tmp, field) == NULL || \
  450. RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  451. (RB_RIGHT(tmp, field) == NULL || \
  452. RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  453. RB_COLOR(tmp, field) = RB_RED; \
  454. elm = parent; \
  455. parent = RB_PARENT(elm, field); \
  456. } else { \
  457. if (RB_LEFT(tmp, field) == NULL || \
  458. RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
  459. struct type *oright; \
  460. if ((oright = RB_RIGHT(tmp, field)))\
  461. RB_COLOR(oright, field) = RB_BLACK;\
  462. RB_COLOR(tmp, field) = RB_RED; \
  463. RB_ROTATE_LEFT(head, tmp, oright, field);\
  464. tmp = RB_LEFT(parent, field); \
  465. } \
  466. RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  467. RB_COLOR(parent, field) = RB_BLACK; \
  468. if (RB_LEFT(tmp, field)) \
  469. RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
  470. RB_ROTATE_RIGHT(head, parent, tmp, field);\
  471. elm = RB_ROOT(head); \
  472. break; \
  473. } \
  474. } \
  475. } \
  476. if (elm) \
  477. RB_COLOR(elm, field) = RB_BLACK; \
  478. } \
  479. \
  480. struct type * \
  481. name##_RB_REMOVE(struct name *head, struct type *elm) \
  482. { \
  483. struct type *child, *parent, *old = elm; \
  484. int color; \
  485. if (RB_LEFT(elm, field) == NULL) \
  486. child = RB_RIGHT(elm, field); \
  487. else if (RB_RIGHT(elm, field) == NULL) \
  488. child = RB_LEFT(elm, field); \
  489. else { \
  490. struct type *left; \
  491. elm = RB_RIGHT(elm, field); \
  492. while ((left = RB_LEFT(elm, field))) \
  493. elm = left; \
  494. child = RB_RIGHT(elm, field); \
  495. parent = RB_PARENT(elm, field); \
  496. color = RB_COLOR(elm, field); \
  497. if (child) \
  498. RB_PARENT(child, field) = parent; \
  499. if (parent) { \
  500. if (RB_LEFT(parent, field) == elm) \
  501. RB_LEFT(parent, field) = child; \
  502. else \
  503. RB_RIGHT(parent, field) = child; \
  504. RB_AUGMENT(parent); \
  505. } else \
  506. RB_ROOT(head) = child; \
  507. if (RB_PARENT(elm, field) == old) \
  508. parent = elm; \
  509. (elm)->field = (old)->field; \
  510. if (RB_PARENT(old, field)) { \
  511. if (RB_LEFT(RB_PARENT(old, field), field) == old)\
  512. RB_LEFT(RB_PARENT(old, field), field) = elm;\
  513. else \
  514. RB_RIGHT(RB_PARENT(old, field), field) = elm;\
  515. RB_AUGMENT(RB_PARENT(old, field)); \
  516. } else \
  517. RB_ROOT(head) = elm; \
  518. RB_PARENT(RB_LEFT(old, field), field) = elm; \
  519. if (RB_RIGHT(old, field)) \
  520. RB_PARENT(RB_RIGHT(old, field), field) = elm; \
  521. if (parent) { \
  522. left = parent; \
  523. do { \
  524. RB_AUGMENT(left); \
  525. } while ((left = RB_PARENT(left, field))); \
  526. } \
  527. goto color; \
  528. } \
  529. parent = RB_PARENT(elm, field); \
  530. color = RB_COLOR(elm, field); \
  531. if (child) \
  532. RB_PARENT(child, field) = parent; \
  533. if (parent) { \
  534. if (RB_LEFT(parent, field) == elm) \
  535. RB_LEFT(parent, field) = child; \
  536. else \
  537. RB_RIGHT(parent, field) = child; \
  538. RB_AUGMENT(parent); \
  539. } else \
  540. RB_ROOT(head) = child; \
  541. color: \
  542. if (color == RB_BLACK) \
  543. name##_RB_REMOVE_COLOR(head, parent, child); \
  544. return (old); \
  545. } \
  546. \
  547. /* Inserts a node into the RB tree */ \
  548. struct type * \
  549. name##_RB_INSERT(struct name *head, struct type *elm) \
  550. { \
  551. struct type *tmp; \
  552. struct type *parent = NULL; \
  553. int comp = 0; \
  554. tmp = RB_ROOT(head); \
  555. while (tmp) { \
  556. parent = tmp; \
  557. comp = (cmp)(elm, parent); \
  558. if (comp < 0) \
  559. tmp = RB_LEFT(tmp, field); \
  560. else if (comp > 0) \
  561. tmp = RB_RIGHT(tmp, field); \
  562. else \
  563. return (tmp); \
  564. } \
  565. RB_SET(elm, parent, field); \
  566. if (parent != NULL) { \
  567. if (comp < 0) \
  568. RB_LEFT(parent, field) = elm; \
  569. else \
  570. RB_RIGHT(parent, field) = elm; \
  571. RB_AUGMENT(parent); \
  572. } else \
  573. RB_ROOT(head) = elm; \
  574. name##_RB_INSERT_COLOR(head, elm); \
  575. return (NULL); \
  576. } \
  577. \
  578. /* Finds the node with the same key as elm */ \
  579. struct type * \
  580. name##_RB_FIND(struct name *head, struct type *elm) \
  581. { \
  582. struct type *tmp = RB_ROOT(head); \
  583. int comp; \
  584. while (tmp) { \
  585. comp = cmp(elm, tmp); \
  586. if (comp < 0) \
  587. tmp = RB_LEFT(tmp, field); \
  588. else if (comp > 0) \
  589. tmp = RB_RIGHT(tmp, field); \
  590. else \
  591. return (tmp); \
  592. } \
  593. return (NULL); \
  594. } \
  595. \
  596. struct type * \
  597. name##_RB_NEXT(struct type *elm) \
  598. { \
  599. if (RB_RIGHT(elm, field)) { \
  600. elm = RB_RIGHT(elm, field); \
  601. while (RB_LEFT(elm, field)) \
  602. elm = RB_LEFT(elm, field); \
  603. } else { \
  604. if (RB_PARENT(elm, field) && \
  605. (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
  606. elm = RB_PARENT(elm, field); \
  607. else { \
  608. while (RB_PARENT(elm, field) && \
  609. (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
  610. elm = RB_PARENT(elm, field); \
  611. elm = RB_PARENT(elm, field); \
  612. } \
  613. } \
  614. return (elm); \
  615. } \
  616. \
  617. struct type * \
  618. name##_RB_MINMAX(struct name *head, int val) \
  619. { \
  620. struct type *tmp = RB_ROOT(head); \
  621. struct type *parent = NULL; \
  622. while (tmp) { \
  623. parent = tmp; \
  624. if (val < 0) \
  625. tmp = RB_LEFT(tmp, field); \
  626. else \
  627. tmp = RB_RIGHT(tmp, field); \
  628. } \
  629. return (parent); \
  630. }
  631. #define RB_NEGINF -1
  632. #define RB_INF 1
  633. #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
  634. #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
  635. #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
  636. #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
  637. #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
  638. #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
  639. #define RB_FOREACH(x, name, head) \
  640. for ((x) = RB_MIN(name, head); \
  641. (x) != NULL; \
  642. (x) = name##_RB_NEXT(x))
  643. #endif /* _SYS_TREE_H_ */