Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

tree.h @ 444

Last change on this file since 444 was 444, checked in by satin@…, 6 years ago
add newlib,libalmos-mkh, restructure shared_syscalls.h and mini-libc
File size: 26.8 KB

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

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: trunk/libs/newlib/src/newlib/libc/include/sys/tree.h @ 444

Download in other formats: