visus
/
toolchain-gcc-arm-embedded
關註 1
收藏 0
複製 0
程式碼 問題管理 0 合併請求 0 版本發佈 0 Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2 Commit
1 分支
分支: main
分支列表 標籤列表
${ item.name }
Create branch ${ searchTerm }
from 'main'
${ noResults }
toolchain-gcc-arm-embedded/arm-none-eabi/include/sys/tree.h

804 line
27KB
原始文件 永久連結 Blame 文件歷史 

  1. /*	$NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $	*/

  2. /*	$OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $	*/

  3. /* $FreeBSD: head/sys/sys/tree.h 347360 2019-05-08 18:47:00Z trasz $ */

  4. 

  5. /*-

  6.  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD

  7.  *

  8.  * Copyright 2002 Niels Provos <provos@citi.umich.edu>

  9.  * All rights reserved.

  10.  *

  11.  * Redistribution and use in source and binary forms, with or without

  12.  * modification, are permitted provided that the following conditions

  13.  * are met:

  14.  * 1. Redistributions of source code must retain the above copyright

  15.  *    notice, this list of conditions and the following disclaimer.

  16.  * 2. Redistributions in binary form must reproduce the above copyright

  17.  *    notice, this list of conditions and the following disclaimer in the

  18.  *    documentation and/or other materials provided with the distribution.

  19.  *

  20.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR

  21.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

  22.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.

  23.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,

  24.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

  25.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

  26.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

  27.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

  28.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

  29.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

  30.  */

  31. 

  32. #ifndef	_SYS_TREE_H_

  33. #define	_SYS_TREE_H_

  34. 

  35. #include <sys/cdefs.h>

  36. 

  37. /*

  38.  * This file defines data structures for different types of trees:

  39.  * splay trees and red-black trees.

  40.  *

  41.  * A splay tree is a self-organizing data structure.  Every operation

  42.  * on the tree causes a splay to happen.  The splay moves the requested

  43.  * node to the root of the tree and partly rebalances it.

  44.  *

  45.  * This has the benefit that request locality causes faster lookups as

  46.  * the requested nodes move to the top of the tree.  On the other hand,

  47.  * every lookup causes memory writes.

  48.  *

  49.  * The Balance Theorem bounds the total access time for m operations

  50.  * and n inserts on an initially empty tree as O((m + n)lg n).  The

  51.  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);

  52.  *

  53.  * A red-black tree is a binary search tree with the node color as an

  54.  * extra attribute.  It fulfills a set of conditions:

  55.  *	- every search path from the root to a leaf consists of the

  56.  *	  same number of black nodes,

  57.  *	- each red node (except for the root) has a black parent,

  58.  *	- each leaf node is black.

  59.  *

  60.  * Every operation on a red-black tree is bounded as O(lg n).

  61.  * The maximum height of a red-black tree is 2lg (n+1).

  62.  */

  63. 

  64. #define SPLAY_HEAD(name, type)						\

  65. struct name {								\

  66. 	struct type *sph_root; /* root of the tree */			\

  67. }

  68. 

  69. #define SPLAY_INITIALIZER(root)						\

  70. 	{ NULL }

  71. 

  72. #define SPLAY_INIT(root) do {						\

  73. 	(root)->sph_root = NULL;					\

  74. } while (/*CONSTCOND*/ 0)

  75. 

  76. #define SPLAY_ENTRY(type)						\

  77. struct {								\

  78. 	struct type *spe_left; /* left element */			\

  79. 	struct type *spe_right; /* right element */			\

  80. }

  81. 

  82. #define SPLAY_LEFT(elm, field)		(elm)->field.spe_left

  83. #define SPLAY_RIGHT(elm, field)		(elm)->field.spe_right

  84. #define SPLAY_ROOT(head)		(head)->sph_root

  85. #define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)

  86. 

  87. /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */

  88. #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\

  89. 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\

  90. 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\

  91. 	(head)->sph_root = tmp;						\

  92. } while (/*CONSTCOND*/ 0)

  93. 	

  94. #define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\

  95. 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\

  96. 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\

  97. 	(head)->sph_root = tmp;						\

  98. } while (/*CONSTCOND*/ 0)

  99. 

  100. #define SPLAY_LINKLEFT(head, tmp, field) do {				\

  101. 	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\

  102. 	tmp = (head)->sph_root;						\

  103. 	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\

  104. } while (/*CONSTCOND*/ 0)

  105. 

  106. #define SPLAY_LINKRIGHT(head, tmp, field) do {				\

  107. 	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\

  108. 	tmp = (head)->sph_root;						\

  109. 	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\

  110. } while (/*CONSTCOND*/ 0)

  111. 

  112. #define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\

  113. 	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\

  114. 	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\

  115. 	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\

  116. 	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\

  117. } while (/*CONSTCOND*/ 0)

  118. 

  119. /* Generates prototypes and inline functions */

  120. 

  121. #define SPLAY_PROTOTYPE(name, type, field, cmp)				\

  122. void name##_SPLAY(struct name *, struct type *);			\

  123. void name##_SPLAY_MINMAX(struct name *, int);				\

  124. struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\

  125. struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\

  126. 									\

  127. /* Finds the node with the same key as elm */				\

  128. static __unused __inline struct type *					\

  129. name##_SPLAY_FIND(struct name *head, struct type *elm)			\

  130. {									\

  131. 	if (SPLAY_EMPTY(head))						\

  132. 		return(NULL);						\

  133. 	name##_SPLAY(head, elm);					\

  134. 	if ((cmp)(elm, (head)->sph_root) == 0)				\

  135. 		return (head->sph_root);				\

  136. 	return (NULL);							\

  137. }									\

  138. 									\

  139. static __unused __inline struct type *					\

  140. name##_SPLAY_NEXT(struct name *head, struct type *elm)			\

  141. {									\

  142. 	name##_SPLAY(head, elm);					\

  143. 	if (SPLAY_RIGHT(elm, field) != NULL) {				\

  144. 		elm = SPLAY_RIGHT(elm, field);				\

  145. 		while (SPLAY_LEFT(elm, field) != NULL) {		\

  146. 			elm = SPLAY_LEFT(elm, field);			\

  147. 		}							\

  148. 	} else								\

  149. 		elm = NULL;						\

  150. 	return (elm);							\

  151. }									\

  152. 									\

  153. static __unused __inline struct type *					\

  154. name##_SPLAY_MIN_MAX(struct name *head, int val)			\

  155. {									\

  156. 	name##_SPLAY_MINMAX(head, val);					\

  157.         return (SPLAY_ROOT(head));					\

  158. }

  159. 

  160. /* Main splay operation.

  161.  * Moves node close to the key of elm to top

  162.  */

  163. #define SPLAY_GENERATE(name, type, field, cmp)				\

  164. struct type *								\

  165. name##_SPLAY_INSERT(struct name *head, struct type *elm)		\

  166. {									\

  167.     if (SPLAY_EMPTY(head)) {						\

  168. 	    SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;	\

  169.     } else {								\

  170. 	    int __comp;							\

  171. 	    name##_SPLAY(head, elm);					\

  172. 	    __comp = (cmp)(elm, (head)->sph_root);			\

  173. 	    if(__comp < 0) {						\

  174. 		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\

  175. 		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\

  176. 		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\

  177. 	    } else if (__comp > 0) {					\

  178. 		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\

  179. 		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\

  180. 		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\

  181. 	    } else							\

  182. 		    return ((head)->sph_root);				\

  183.     }									\

  184.     (head)->sph_root = (elm);						\

  185.     return (NULL);							\

  186. }									\

  187. 									\

  188. struct type *								\

  189. name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\

  190. {									\

  191. 	struct type *__tmp;						\

  192. 	if (SPLAY_EMPTY(head))						\

  193. 		return (NULL);						\

  194. 	name##_SPLAY(head, elm);					\

  195. 	if ((cmp)(elm, (head)->sph_root) == 0) {			\

  196. 		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\

  197. 			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\

  198. 		} else {						\

  199. 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\

  200. 			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\

  201. 			name##_SPLAY(head, elm);			\

  202. 			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\

  203. 		}							\

  204. 		return (elm);						\

  205. 	}								\

  206. 	return (NULL);							\

  207. }									\

  208. 									\

  209. void									\

  210. name##_SPLAY(struct name *head, struct type *elm)			\

  211. {									\

  212. 	struct type __node, *__left, *__right, *__tmp;			\

  213. 	int __comp;							\

  214. \

  215. 	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\

  216. 	__left = __right = &__node;					\

  217. \

  218. 	while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {		\

  219. 		if (__comp < 0) {					\

  220. 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\

  221. 			if (__tmp == NULL)				\

  222. 				break;					\

  223. 			if ((cmp)(elm, __tmp) < 0){			\

  224. 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\

  225. 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\

  226. 					break;				\

  227. 			}						\

  228. 			SPLAY_LINKLEFT(head, __right, field);		\

  229. 		} else if (__comp > 0) {				\

  230. 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\

  231. 			if (__tmp == NULL)				\

  232. 				break;					\

  233. 			if ((cmp)(elm, __tmp) > 0){			\

  234. 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\

  235. 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\

  236. 					break;				\

  237. 			}						\

  238. 			SPLAY_LINKRIGHT(head, __left, field);		\

  239. 		}							\

  240. 	}								\

  241. 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\

  242. }									\

  243. 									\

  244. /* Splay with either the minimum or the maximum element			\

  245.  * Used to find minimum or maximum element in tree.			\

  246.  */									\

  247. void name##_SPLAY_MINMAX(struct name *head, int __comp) \

  248. {									\

  249. 	struct type __node, *__left, *__right, *__tmp;			\

  250. \

  251. 	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\

  252. 	__left = __right = &__node;					\

  253. \

  254. 	while (1) {							\

  255. 		if (__comp < 0) {					\

  256. 			__tmp = SPLAY_LEFT((head)->sph_root, field);	\

  257. 			if (__tmp == NULL)				\

  258. 				break;					\

  259. 			if (__comp < 0){				\

  260. 				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\

  261. 				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\

  262. 					break;				\

  263. 			}						\

  264. 			SPLAY_LINKLEFT(head, __right, field);		\

  265. 		} else if (__comp > 0) {				\

  266. 			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\

  267. 			if (__tmp == NULL)				\

  268. 				break;					\

  269. 			if (__comp > 0) {				\

  270. 				SPLAY_ROTATE_LEFT(head, __tmp, field);	\

  271. 				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\

  272. 					break;				\

  273. 			}						\

  274. 			SPLAY_LINKRIGHT(head, __left, field);		\

  275. 		}							\

  276. 	}								\

  277. 	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\

  278. }

  279. 

  280. #define SPLAY_NEGINF	-1

  281. #define SPLAY_INF	1

  282. 

  283. #define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)

  284. #define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)

  285. #define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)

  286. #define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)

  287. #define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\

  288. 					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))

  289. #define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\

  290. 					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))

  291. 

  292. #define SPLAY_FOREACH(x, name, head)					\

  293. 	for ((x) = SPLAY_MIN(name, head);				\

  294. 	     (x) != NULL;						\

  295. 	     (x) = SPLAY_NEXT(name, head, x))

  296. 

  297. /* Macros that define a red-black tree */

  298. #define RB_HEAD(name, type)						\

  299. struct name {								\

  300. 	struct type *rbh_root; /* root of the tree */			\

  301. }

  302. 

  303. #define RB_INITIALIZER(root)						\

  304. 	{ NULL }

  305. 

  306. #define RB_INIT(root) do {						\

  307. 	(root)->rbh_root = NULL;					\

  308. } while (/*CONSTCOND*/ 0)

  309. 

  310. #define RB_BLACK	0

  311. #define RB_RED		1

  312. #define RB_ENTRY(type)							\

  313. struct {								\

  314. 	struct type *rbe_left;		/* left element */		\

  315. 	struct type *rbe_right;		/* right element */		\

  316. 	struct type *rbe_parent;	/* parent element */		\

  317. 	int rbe_color;			/* node color */		\

  318. }

  319. 

  320. #define RB_LEFT(elm, field)		(elm)->field.rbe_left

  321. #define RB_RIGHT(elm, field)		(elm)->field.rbe_right

  322. #define RB_PARENT(elm, field)		(elm)->field.rbe_parent

  323. #define RB_COLOR(elm, field)		(elm)->field.rbe_color

  324. #define RB_ROOT(head)			(head)->rbh_root

  325. #define RB_EMPTY(head)			(RB_ROOT(head) == NULL)

  326. 

  327. #define RB_SET(elm, parent, field) do {					\

  328. 	RB_PARENT(elm, field) = parent;					\

  329. 	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\

  330. 	RB_COLOR(elm, field) = RB_RED;					\

  331. } while (/*CONSTCOND*/ 0)

  332. 

  333. #define RB_SET_BLACKRED(black, red, field) do {				\

  334. 	RB_COLOR(black, field) = RB_BLACK;				\

  335. 	RB_COLOR(red, field) = RB_RED;					\

  336. } while (/*CONSTCOND*/ 0)

  337. 

  338. #ifndef RB_AUGMENT

  339. #define RB_AUGMENT(x)	do {} while (0)

  340. #endif

  341. 

  342. #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\

  343. 	(tmp) = RB_RIGHT(elm, field);					\

  344. 	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\

  345. 		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\

  346. 	}								\

  347. 	RB_AUGMENT(elm);						\

  348. 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\

  349. 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\

  350. 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\

  351. 		else							\

  352. 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\

  353. 	} else								\

  354. 		(head)->rbh_root = (tmp);				\

  355. 	RB_LEFT(tmp, field) = (elm);					\

  356. 	RB_PARENT(elm, field) = (tmp);					\

  357. 	RB_AUGMENT(tmp);						\

  358. 	if ((RB_PARENT(tmp, field)))					\

  359. 		RB_AUGMENT(RB_PARENT(tmp, field));			\

  360. } while (/*CONSTCOND*/ 0)

  361. 

  362. #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\

  363. 	(tmp) = RB_LEFT(elm, field);					\

  364. 	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\

  365. 		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\

  366. 	}								\

  367. 	RB_AUGMENT(elm);						\

  368. 	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\

  369. 		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\

  370. 			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\

  371. 		else							\

  372. 			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\

  373. 	} else								\

  374. 		(head)->rbh_root = (tmp);				\

  375. 	RB_RIGHT(tmp, field) = (elm);					\

  376. 	RB_PARENT(elm, field) = (tmp);					\

  377. 	RB_AUGMENT(tmp);						\

  378. 	if ((RB_PARENT(tmp, field)))					\

  379. 		RB_AUGMENT(RB_PARENT(tmp, field));			\

  380. } while (/*CONSTCOND*/ 0)

  381. 

  382. /* Generates prototypes and inline functions */

  383. #define	RB_PROTOTYPE(name, type, field, cmp)				\

  384. 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)

  385. #define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\

  386. 	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)

  387. #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\

  388. 	RB_PROTOTYPE_INSERT_COLOR(name, type, attr);			\

  389. 	RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);			\

  390. 	RB_PROTOTYPE_INSERT(name, type, attr);				\

  391. 	RB_PROTOTYPE_REMOVE(name, type, attr);				\

  392. 	RB_PROTOTYPE_FIND(name, type, attr);				\

  393. 	RB_PROTOTYPE_NFIND(name, type, attr);				\

  394. 	RB_PROTOTYPE_NEXT(name, type, attr);				\

  395. 	RB_PROTOTYPE_PREV(name, type, attr);				\

  396. 	RB_PROTOTYPE_MINMAX(name, type, attr);

  397. #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)			\

  398. 	attr void name##_RB_INSERT_COLOR(struct name *, struct type *)

  399. #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)			\

  400. 	attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *)

  401. #define RB_PROTOTYPE_REMOVE(name, type, attr)				\

  402. 	attr struct type *name##_RB_REMOVE(struct name *, struct type *)

  403. #define RB_PROTOTYPE_INSERT(name, type, attr)				\

  404. 	attr struct type *name##_RB_INSERT(struct name *, struct type *)

  405. #define RB_PROTOTYPE_FIND(name, type, attr)				\

  406. 	attr struct type *name##_RB_FIND(struct name *, struct type *)

  407. #define RB_PROTOTYPE_NFIND(name, type, attr)				\

  408. 	attr struct type *name##_RB_NFIND(struct name *, struct type *)

  409. #define RB_PROTOTYPE_NEXT(name, type, attr)				\

  410. 	attr struct type *name##_RB_NEXT(struct type *)

  411. #define RB_PROTOTYPE_PREV(name, type, attr)				\

  412. 	attr struct type *name##_RB_PREV(struct type *)

  413. #define RB_PROTOTYPE_MINMAX(name, type, attr)				\

  414. 	attr struct type *name##_RB_MINMAX(struct name *, int)

  415. 

  416. /* Main rb operation.

  417.  * Moves node close to the key of elm to top

  418.  */

  419. #define	RB_GENERATE(name, type, field, cmp)				\

  420. 	RB_GENERATE_INTERNAL(name, type, field, cmp,)

  421. #define	RB_GENERATE_STATIC(name, type, field, cmp)			\

  422. 	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)

  423. #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\

  424. 	RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\

  425. 	RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\

  426. 	RB_GENERATE_INSERT(name, type, field, cmp, attr)		\

  427. 	RB_GENERATE_REMOVE(name, type, field, attr)			\

  428. 	RB_GENERATE_FIND(name, type, field, cmp, attr)			\

  429. 	RB_GENERATE_NFIND(name, type, field, cmp, attr)			\

  430. 	RB_GENERATE_NEXT(name, type, field, attr)			\

  431. 	RB_GENERATE_PREV(name, type, field, attr)			\

  432. 	RB_GENERATE_MINMAX(name, type, field, attr)

  433. 

  434. #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)		\

  435. attr void								\

  436. name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\

  437. {									\

  438. 	struct type *parent, *gparent, *tmp;				\

  439. 	while ((parent = RB_PARENT(elm, field)) != NULL &&		\

  440. 	    RB_COLOR(parent, field) == RB_RED) {			\

  441. 		gparent = RB_PARENT(parent, field);			\

  442. 		if (parent == RB_LEFT(gparent, field)) {		\

  443. 			tmp = RB_RIGHT(gparent, field);			\

  444. 			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\

  445. 				RB_COLOR(tmp, field) = RB_BLACK;	\

  446. 				RB_SET_BLACKRED(parent, gparent, field);\

  447. 				elm = gparent;				\

  448. 				continue;				\

  449. 			}						\

  450. 			if (RB_RIGHT(parent, field) == elm) {		\

  451. 				RB_ROTATE_LEFT(head, parent, tmp, field);\

  452. 				tmp = parent;				\

  453. 				parent = elm;				\

  454. 				elm = tmp;				\

  455. 			}						\

  456. 			RB_SET_BLACKRED(parent, gparent, field);	\

  457. 			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\

  458. 		} else {						\

  459. 			tmp = RB_LEFT(gparent, field);			\

  460. 			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\

  461. 				RB_COLOR(tmp, field) = RB_BLACK;	\

  462. 				RB_SET_BLACKRED(parent, gparent, field);\

  463. 				elm = gparent;				\

  464. 				continue;				\

  465. 			}						\

  466. 			if (RB_LEFT(parent, field) == elm) {		\

  467. 				RB_ROTATE_RIGHT(head, parent, tmp, field);\

  468. 				tmp = parent;				\

  469. 				parent = elm;				\

  470. 				elm = tmp;				\

  471. 			}						\

  472. 			RB_SET_BLACKRED(parent, gparent, field);	\

  473. 			RB_ROTATE_LEFT(head, gparent, tmp, field);	\

  474. 		}							\

  475. 	}								\

  476. 	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\

  477. }

  478. 

  479. #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)		\

  480. attr void								\

  481. name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \

  482. {									\

  483. 	struct type *tmp;						\

  484. 	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&	\

  485. 	    elm != RB_ROOT(head)) {					\

  486. 		if (RB_LEFT(parent, field) == elm) {			\

  487. 			tmp = RB_RIGHT(parent, field);			\

  488. 			if (RB_COLOR(tmp, field) == RB_RED) {		\

  489. 				RB_SET_BLACKRED(tmp, parent, field);	\

  490. 				RB_ROTATE_LEFT(head, parent, tmp, field);\

  491. 				tmp = RB_RIGHT(parent, field);		\

  492. 			}						\

  493. 			if ((RB_LEFT(tmp, field) == NULL ||		\

  494. 			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\

  495. 			    (RB_RIGHT(tmp, field) == NULL ||		\

  496. 			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\

  497. 				RB_COLOR(tmp, field) = RB_RED;		\

  498. 				elm = parent;				\

  499. 				parent = RB_PARENT(elm, field);		\

  500. 			} else {					\

  501. 				if (RB_RIGHT(tmp, field) == NULL ||	\

  502. 				    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\

  503. 					struct type *oleft;		\

  504. 					if ((oleft = RB_LEFT(tmp, field)) \

  505. 					    != NULL)			\

  506. 						RB_COLOR(oleft, field) = RB_BLACK;\

  507. 					RB_COLOR(tmp, field) = RB_RED;	\

  508. 					RB_ROTATE_RIGHT(head, tmp, oleft, field);\

  509. 					tmp = RB_RIGHT(parent, field);	\

  510. 				}					\

  511. 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\

  512. 				RB_COLOR(parent, field) = RB_BLACK;	\

  513. 				if (RB_RIGHT(tmp, field))		\

  514. 					RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\

  515. 				RB_ROTATE_LEFT(head, parent, tmp, field);\

  516. 				elm = RB_ROOT(head);			\

  517. 				break;					\

  518. 			}						\

  519. 		} else {						\

  520. 			tmp = RB_LEFT(parent, field);			\

  521. 			if (RB_COLOR(tmp, field) == RB_RED) {		\

  522. 				RB_SET_BLACKRED(tmp, parent, field);	\

  523. 				RB_ROTATE_RIGHT(head, parent, tmp, field);\

  524. 				tmp = RB_LEFT(parent, field);		\

  525. 			}						\

  526. 			if ((RB_LEFT(tmp, field) == NULL ||		\

  527. 			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\

  528. 			    (RB_RIGHT(tmp, field) == NULL ||		\

  529. 			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\

  530. 				RB_COLOR(tmp, field) = RB_RED;		\

  531. 				elm = parent;				\

  532. 				parent = RB_PARENT(elm, field);		\

  533. 			} else {					\

  534. 				if (RB_LEFT(tmp, field) == NULL ||	\

  535. 				    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\

  536. 					struct type *oright;		\

  537. 					if ((oright = RB_RIGHT(tmp, field)) \

  538. 					    != NULL)			\

  539. 						RB_COLOR(oright, field) = RB_BLACK;\

  540. 					RB_COLOR(tmp, field) = RB_RED;	\

  541. 					RB_ROTATE_LEFT(head, tmp, oright, field);\

  542. 					tmp = RB_LEFT(parent, field);	\

  543. 				}					\

  544. 				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\

  545. 				RB_COLOR(parent, field) = RB_BLACK;	\

  546. 				if (RB_LEFT(tmp, field))		\

  547. 					RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\

  548. 				RB_ROTATE_RIGHT(head, parent, tmp, field);\

  549. 				elm = RB_ROOT(head);			\

  550. 				break;					\

  551. 			}						\

  552. 		}							\

  553. 	}								\

  554. 	if (elm)							\

  555. 		RB_COLOR(elm, field) = RB_BLACK;			\

  556. }

  557. 

  558. #define RB_GENERATE_REMOVE(name, type, field, attr)			\

  559. attr struct type *							\

  560. name##_RB_REMOVE(struct name *head, struct type *elm)			\

  561. {									\

  562. 	struct type *child, *parent, *old = elm;			\

  563. 	int color;							\

  564. 	if (RB_LEFT(elm, field) == NULL)				\

  565. 		child = RB_RIGHT(elm, field);				\

  566. 	else if (RB_RIGHT(elm, field) == NULL)				\

  567. 		child = RB_LEFT(elm, field);				\

  568. 	else {								\

  569. 		struct type *left;					\

  570. 		elm = RB_RIGHT(elm, field);				\

  571. 		while ((left = RB_LEFT(elm, field)) != NULL)		\

  572. 			elm = left;					\

  573. 		child = RB_RIGHT(elm, field);				\

  574. 		parent = RB_PARENT(elm, field);				\

  575. 		color = RB_COLOR(elm, field);				\

  576. 		if (child)						\

  577. 			RB_PARENT(child, field) = parent;		\

  578. 		if (parent) {						\

  579. 			if (RB_LEFT(parent, field) == elm)		\

  580. 				RB_LEFT(parent, field) = child;		\

  581. 			else						\

  582. 				RB_RIGHT(parent, field) = child;	\

  583. 			RB_AUGMENT(parent);				\

  584. 		} else							\

  585. 			RB_ROOT(head) = child;				\

  586. 		if (RB_PARENT(elm, field) == old)			\

  587. 			parent = elm;					\

  588. 		(elm)->field = (old)->field;				\

  589. 		if (RB_PARENT(old, field)) {				\

  590. 			if (RB_LEFT(RB_PARENT(old, field), field) == old)\

  591. 				RB_LEFT(RB_PARENT(old, field), field) = elm;\

  592. 			else						\

  593. 				RB_RIGHT(RB_PARENT(old, field), field) = elm;\

  594. 			RB_AUGMENT(RB_PARENT(old, field));		\

  595. 		} else							\

  596. 			RB_ROOT(head) = elm;				\

  597. 		RB_PARENT(RB_LEFT(old, field), field) = elm;		\

  598. 		if (RB_RIGHT(old, field))				\

  599. 			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\

  600. 		if (parent) {						\

  601. 			left = parent;					\

  602. 			do {						\

  603. 				RB_AUGMENT(left);			\

  604. 			} while ((left = RB_PARENT(left, field)) != NULL); \

  605. 		}							\

  606. 		goto color;						\

  607. 	}								\

  608. 	parent = RB_PARENT(elm, field);					\

  609. 	color = RB_COLOR(elm, field);					\

  610. 	if (child)							\

  611. 		RB_PARENT(child, field) = parent;			\

  612. 	if (parent) {							\

  613. 		if (RB_LEFT(parent, field) == elm)			\

  614. 			RB_LEFT(parent, field) = child;			\

  615. 		else							\

  616. 			RB_RIGHT(parent, field) = child;		\

  617. 		RB_AUGMENT(parent);					\

  618. 	} else								\

  619. 		RB_ROOT(head) = child;					\

  620. color:									\

  621. 	if (color == RB_BLACK)						\

  622. 		name##_RB_REMOVE_COLOR(head, parent, child);		\

  623. 	return (old);							\

  624. }									\

  625. 

  626. #define RB_GENERATE_INSERT(name, type, field, cmp, attr)		\

  627. /* Inserts a node into the RB tree */					\

  628. attr struct type *							\

  629. name##_RB_INSERT(struct name *head, struct type *elm)			\

  630. {									\

  631. 	struct type *tmp;						\

  632. 	struct type *parent = NULL;					\

  633. 	int comp = 0;							\

  634. 	tmp = RB_ROOT(head);						\

  635. 	while (tmp) {							\

  636. 		parent = tmp;						\

  637. 		comp = (cmp)(elm, parent);				\

  638. 		if (comp < 0)						\

  639. 			tmp = RB_LEFT(tmp, field);			\

  640. 		else if (comp > 0)					\

  641. 			tmp = RB_RIGHT(tmp, field);			\

  642. 		else							\

  643. 			return (tmp);					\

  644. 	}								\

  645. 	RB_SET(elm, parent, field);					\

  646. 	if (parent != NULL) {						\

  647. 		if (comp < 0)						\

  648. 			RB_LEFT(parent, field) = elm;			\

  649. 		else							\

  650. 			RB_RIGHT(parent, field) = elm;			\

  651. 		RB_AUGMENT(parent);					\

  652. 	} else								\

  653. 		RB_ROOT(head) = elm;					\

  654. 	name##_RB_INSERT_COLOR(head, elm);				\

  655. 	return (NULL);							\

  656. }

  657. 

  658. #define RB_GENERATE_FIND(name, type, field, cmp, attr)			\

  659. /* Finds the node with the same key as elm */				\

  660. attr struct type *							\

  661. name##_RB_FIND(struct name *head, struct type *elm)			\

  662. {									\

  663. 	struct type *tmp = RB_ROOT(head);				\

  664. 	int comp;							\

  665. 	while (tmp) {							\

  666. 		comp = cmp(elm, tmp);					\

  667. 		if (comp < 0)						\

  668. 			tmp = RB_LEFT(tmp, field);			\

  669. 		else if (comp > 0)					\

  670. 			tmp = RB_RIGHT(tmp, field);			\

  671. 		else							\

  672. 			return (tmp);					\

  673. 	}								\

  674. 	return (NULL);							\

  675. }

  676. 

  677. #define RB_GENERATE_NFIND(name, type, field, cmp, attr)			\

  678. /* Finds the first node greater than or equal to the search key */	\

  679. attr struct type *							\

  680. name##_RB_NFIND(struct name *head, struct type *elm)			\

  681. {									\

  682. 	struct type *tmp = RB_ROOT(head);				\

  683. 	struct type *res = NULL;					\

  684. 	int comp;							\

  685. 	while (tmp) {							\

  686. 		comp = cmp(elm, tmp);					\

  687. 		if (comp < 0) {						\

  688. 			res = tmp;					\

  689. 			tmp = RB_LEFT(tmp, field);			\

  690. 		}							\

  691. 		else if (comp > 0)					\

  692. 			tmp = RB_RIGHT(tmp, field);			\

  693. 		else							\

  694. 			return (tmp);					\

  695. 	}								\

  696. 	return (res);							\

  697. }

  698. 

  699. #define RB_GENERATE_NEXT(name, type, field, attr)			\

  700. /* ARGSUSED */								\

  701. attr struct type *							\

  702. name##_RB_NEXT(struct type *elm)					\

  703. {									\

  704. 	if (RB_RIGHT(elm, field)) {					\

  705. 		elm = RB_RIGHT(elm, field);				\

  706. 		while (RB_LEFT(elm, field))				\

  707. 			elm = RB_LEFT(elm, field);			\

  708. 	} else {							\

  709. 		if (RB_PARENT(elm, field) &&				\

  710. 		    (elm == RB_LEFT(RB_PARENT(elm, field), field)))	\

  711. 			elm = RB_PARENT(elm, field);			\

  712. 		else {							\

  713. 			while (RB_PARENT(elm, field) &&			\

  714. 			    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\

  715. 				elm = RB_PARENT(elm, field);		\

  716. 			elm = RB_PARENT(elm, field);			\

  717. 		}							\

  718. 	}								\

  719. 	return (elm);							\

  720. }

  721. 

  722. #define RB_GENERATE_PREV(name, type, field, attr)			\

  723. /* ARGSUSED */								\

  724. attr struct type *							\

  725. name##_RB_PREV(struct type *elm)					\

  726. {									\

  727. 	if (RB_LEFT(elm, field)) {					\

  728. 		elm = RB_LEFT(elm, field);				\

  729. 		while (RB_RIGHT(elm, field))				\

  730. 			elm = RB_RIGHT(elm, field);			\

  731. 	} else {							\

  732. 		if (RB_PARENT(elm, field) &&				\

  733. 		    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))	\

  734. 			elm = RB_PARENT(elm, field);			\

  735. 		else {							\

  736. 			while (RB_PARENT(elm, field) &&			\

  737. 			    (elm == RB_LEFT(RB_PARENT(elm, field), field)))\

  738. 				elm = RB_PARENT(elm, field);		\

  739. 			elm = RB_PARENT(elm, field);			\

  740. 		}							\

  741. 	}								\

  742. 	return (elm);							\

  743. }

  744. 

  745. #define RB_GENERATE_MINMAX(name, type, field, attr)			\

  746. attr struct type *							\

  747. name##_RB_MINMAX(struct name *head, int val)				\

  748. {									\

  749. 	struct type *tmp = RB_ROOT(head);				\

  750. 	struct type *parent = NULL;					\

  751. 	while (tmp) {							\

  752. 		parent = tmp;						\

  753. 		if (val < 0)						\

  754. 			tmp = RB_LEFT(tmp, field);			\

  755. 		else							\

  756. 			tmp = RB_RIGHT(tmp, field);			\

  757. 	}								\

  758. 	return (parent);						\

  759. }

  760. 

  761. #define RB_NEGINF	-1

  762. #define RB_INF	1

  763. 

  764. #define RB_INSERT(name, x, y)	name##_RB_INSERT(x, y)

  765. #define RB_REMOVE(name, x, y)	name##_RB_REMOVE(x, y)

  766. #define RB_FIND(name, x, y)	name##_RB_FIND(x, y)

  767. #define RB_NFIND(name, x, y)	name##_RB_NFIND(x, y)

  768. #define RB_NEXT(name, x, y)	name##_RB_NEXT(y)

  769. #define RB_PREV(name, x, y)	name##_RB_PREV(y)

  770. #define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)

  771. #define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)

  772. 

  773. #define RB_FOREACH(x, name, head)					\

  774. 	for ((x) = RB_MIN(name, head);					\

  775. 	     (x) != NULL;						\

  776. 	     (x) = name##_RB_NEXT(x))

  777. 

  778. #define RB_FOREACH_FROM(x, name, y)					\

  779. 	for ((x) = (y);							\

  780. 	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\

  781. 	     (x) = (y))

  782. 

  783. #define RB_FOREACH_SAFE(x, name, head, y)				\

  784. 	for ((x) = RB_MIN(name, head);					\

  785. 	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\

  786. 	     (x) = (y))

  787. 

  788. #define RB_FOREACH_REVERSE(x, name, head)				\

  789. 	for ((x) = RB_MAX(name, head);					\

  790. 	     (x) != NULL;						\

  791. 	     (x) = name##_RB_PREV(x))

  792. 

  793. #define RB_FOREACH_REVERSE_FROM(x, name, y)				\

  794. 	for ((x) = (y);							\

  795. 	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\

  796. 	     (x) = (y))

  797. 

  798. #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\

  799. 	for ((x) = RB_MAX(name, head);					\

  800. 	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\

  801. 	     (x) = (y))

  802. 

  803. #endif	/* _SYS_TREE_H_ */