Differential D35516 Diff 111258 sys/sys/tree.h

Changeset View

Standalone View

sys/sys/tree.h

Show First 20 Lines • Show All 408 Lines • ▼ Show 20 Lines
#define RB_PROTOTYPE(name, type, field, cmp) \		#define RB_PROTOTYPE(name, type, field, cmp) \
RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)		RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \		#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)		RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \		#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
RB_PROTOTYPE_RANK(name, type, attr) \		RB_PROTOTYPE_RANK(name, type, attr) \
RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \		RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \		RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
		RB_PROTOTYPE_INSERT_FINISH(name, type, attr); \
RB_PROTOTYPE_INSERT(name, type, attr); \		RB_PROTOTYPE_INSERT(name, type, attr); \
RB_PROTOTYPE_REMOVE(name, type, attr); \		RB_PROTOTYPE_REMOVE(name, type, attr); \
RB_PROTOTYPE_FIND(name, type, attr); \		RB_PROTOTYPE_FIND(name, type, attr); \
RB_PROTOTYPE_NFIND(name, type, attr); \		RB_PROTOTYPE_NFIND(name, type, attr); \
RB_PROTOTYPE_NEXT(name, type, attr); \		RB_PROTOTYPE_NEXT(name, type, attr); \
		RB_PROTOTYPE_INSERT_NEXT(name, type, attr); \
RB_PROTOTYPE_PREV(name, type, attr); \		RB_PROTOTYPE_PREV(name, type, attr); \
		RB_PROTOTYPE_INSERT_PREV(name, type, attr); \
RB_PROTOTYPE_MINMAX(name, type, attr); \		RB_PROTOTYPE_MINMAX(name, type, attr); \
RB_PROTOTYPE_REINSERT(name, type, attr);		RB_PROTOTYPE_REINSERT(name, type, attr);
#ifdef _RB_DIAGNOSTIC		#ifdef _RB_DIAGNOSTIC
#define RB_PROTOTYPE_RANK(name, type, attr) \		#define RB_PROTOTYPE_RANK(name, type, attr) \
attr int name##_RB_RANK(struct type *);		attr int name##_RB_RANK(struct type *);
#else		#else
#define RB_PROTOTYPE_RANK(name, type, attr)		#define RB_PROTOTYPE_RANK(name, type, attr)
#endif		#endif
#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \		#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
attr struct type name##_RB_INSERT_COLOR(struct name , \		attr struct type name##_RB_INSERT_COLOR(struct name , \
struct type , struct type )		struct type , struct type )
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \		#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
attr struct type name##_RB_REMOVE_COLOR(struct name , \		attr struct type name##_RB_REMOVE_COLOR(struct name , \
struct type , struct type )		struct type , struct type )
#define RB_PROTOTYPE_REMOVE(name, type, attr) \		#define RB_PROTOTYPE_REMOVE(name, type, attr) \
attr struct type name##_RB_REMOVE(struct name , struct type *)		attr struct type name##_RB_REMOVE(struct name , struct type *)
		#define RB_PROTOTYPE_INSERT_FINISH(name, type, attr) \
		attr struct type name##_RB_INSERT_FINISH(struct name , \
		struct type , struct type , struct type )
#define RB_PROTOTYPE_INSERT(name, type, attr) \		#define RB_PROTOTYPE_INSERT(name, type, attr) \
attr struct type name##_RB_INSERT(struct name , struct type *)		attr struct type name##_RB_INSERT(struct name , struct type *)
#define RB_PROTOTYPE_FIND(name, type, attr) \		#define RB_PROTOTYPE_FIND(name, type, attr) \
attr struct type name##_RB_FIND(struct name , struct type *)		attr struct type name##_RB_FIND(struct name , struct type *)
#define RB_PROTOTYPE_NFIND(name, type, attr) \		#define RB_PROTOTYPE_NFIND(name, type, attr) \
attr struct type name##_RB_NFIND(struct name , struct type *)		attr struct type name##_RB_NFIND(struct name , struct type *)
#define RB_PROTOTYPE_NEXT(name, type, attr) \		#define RB_PROTOTYPE_NEXT(name, type, attr) \
attr struct type name##_RB_NEXT(struct type )		attr struct type name##_RB_NEXT(struct type )
		#define RB_PROTOTYPE_INSERT_NEXT(name, type, attr) \
		attr struct type name##_RB_INSERT_NEXT(struct name , \
		struct type , struct type )
#define RB_PROTOTYPE_PREV(name, type, attr) \		#define RB_PROTOTYPE_PREV(name, type, attr) \
attr struct type name##_RB_PREV(struct type )		attr struct type name##_RB_PREV(struct type )
		#define RB_PROTOTYPE_INSERT_PREV(name, type, attr) \
		attr struct type name##_RB_INSERT_PREV(struct name , \
		struct type , struct type )
#define RB_PROTOTYPE_MINMAX(name, type, attr) \		#define RB_PROTOTYPE_MINMAX(name, type, attr) \
attr struct type name##_RB_MINMAX(struct name , int)		attr struct type name##_RB_MINMAX(struct name , int)
#define RB_PROTOTYPE_REINSERT(name, type, attr) \		#define RB_PROTOTYPE_REINSERT(name, type, attr) \
attr struct type name##_RB_REINSERT(struct name , struct type *)		attr struct type name##_RB_REINSERT(struct name , struct type *)

/* Main rb operation.		/* Main rb operation.
* Moves node close to the key of elm to top		* Moves node close to the key of elm to top
*/		*/
#define RB_GENERATE(name, type, field, cmp) \		#define RB_GENERATE(name, type, field, cmp) \
RB_GENERATE_INTERNAL(name, type, field, cmp,)		RB_GENERATE_INTERNAL(name, type, field, cmp,)
#define RB_GENERATE_STATIC(name, type, field, cmp) \		#define RB_GENERATE_STATIC(name, type, field, cmp) \
RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)		RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \		#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
RB_GENERATE_RANK(name, type, field, attr) \		RB_GENERATE_RANK(name, type, field, attr) \
RB_GENERATE_INSERT_COLOR(name, type, field, attr) \		RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \		RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
		RB_GENERATE_INSERT_FINISH(name, type, field, attr) \
RB_GENERATE_INSERT(name, type, field, cmp, attr) \		RB_GENERATE_INSERT(name, type, field, cmp, attr) \
RB_GENERATE_REMOVE(name, type, field, attr) \		RB_GENERATE_REMOVE(name, type, field, attr) \
RB_GENERATE_FIND(name, type, field, cmp, attr) \		RB_GENERATE_FIND(name, type, field, cmp, attr) \
RB_GENERATE_NFIND(name, type, field, cmp, attr) \		RB_GENERATE_NFIND(name, type, field, cmp, attr) \
RB_GENERATE_NEXT(name, type, field, attr) \		RB_GENERATE_NEXT(name, type, field, attr) \
		RB_GENERATE_INSERT_NEXT(name, type, field, attr) \
RB_GENERATE_PREV(name, type, field, attr) \		RB_GENERATE_PREV(name, type, field, attr) \
		RB_GENERATE_INSERT_PREV(name, type, field, attr) \
RB_GENERATE_MINMAX(name, type, field, attr) \		RB_GENERATE_MINMAX(name, type, field, attr) \
RB_GENERATE_REINSERT(name, type, field, cmp, attr)		RB_GENERATE_REINSERT(name, type, field, cmp, attr)

#ifdef _RB_DIAGNOSTIC		#ifdef _RB_DIAGNOSTIC
#ifndef RB_AUGMENT		#ifndef RB_AUGMENT
#define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x)		#define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x)
#else		#else
#define _RB_AUGMENT_VERIFY(x) 0		#define _RB_AUGMENT_VERIFY(x) 0
▲ Show 20 Lines • Show All 316 Lines • ▼ Show 20 Lines	if (opar != NULL) { \
*/ \		*/ \
(void)RB_AUGMENT_CHECK(opar); \		(void)RB_AUGMENT_CHECK(opar); \
(void)RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \		(void)RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \
} \		} \
} \		} \
return (out); \		return (out); \
}		}

		#define RB_GENERATE_INSERT_FINISH(name, type, field, attr) \
		/* Inserts a node into the RB tree */ \
		attr struct type * \
		name##_RB_INSERT_FINISH(struct name head, struct type parent, \
		struct type *pptr, struct type elm) \
		{ \
		struct type *tmp = NULL; \
		\
		RB_SET(elm, parent, field); \
		*pptr = elm; \
		if (parent != NULL) \
		tmp = name##_RB_INSERT_COLOR(head, parent, elm); \
		_RB_AUGMENT_WALK(elm, tmp, field); \
		if (tmp != NULL) \
		/* \
		* An element rotated into the search path has a \
		* changed subtree, so update augmentation for it if \
		* AUGMENT_WALK didn't. \
		*/ \
		(void)RB_AUGMENT_CHECK(tmp); \
		return (NULL); \
		}

#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \		#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \
/* Inserts a node into the RB tree */ \		/* Inserts a node into the RB tree */ \
attr struct type * \		attr struct type * \
name##_RB_INSERT(struct name head, struct type elm) \		name##_RB_INSERT(struct name head, struct type elm) \
{ \		{ \
struct type *tmp; \		struct type *tmp; \
struct type **tmpp = &RB_ROOT(head); \		struct type **tmpp = &RB_ROOT(head); \
struct type *parent = NULL; \		struct type *parent = NULL; \
\		\
while ((tmp = *tmpp) != NULL) { \		while ((tmp = *tmpp) != NULL) { \
parent = tmp; \		parent = tmp; \
__typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \		__typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \
if (comp < 0) \		if (comp < 0) \
tmpp = &RB_LEFT(parent, field); \		tmpp = &RB_LEFT(parent, field); \
else if (comp > 0) \		else if (comp > 0) \
tmpp = &RB_RIGHT(parent, field); \		tmpp = &RB_RIGHT(parent, field); \
else \		else \
return (parent); \		return (parent); \
} \		} \
RB_SET(elm, parent, field); \		return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm)); \
*tmpp = elm; \
if (parent != NULL) \
tmp = name##_RB_INSERT_COLOR(head, parent, elm); \
_RB_AUGMENT_WALK(elm, tmp, field); \
if (tmp != NULL) \
/* \
* An element rotated into the search path has a \
* changed subtree, so update augmentation for it if \
* AUGMENT_WALK didn't. \
*/ \
(void)RB_AUGMENT_CHECK(tmp); \
return (NULL); \
}		}

#define RB_GENERATE_FIND(name, type, field, cmp, attr) \		#define RB_GENERATE_FIND(name, type, field, cmp, attr) \
/* Finds the node with the same key as elm */ \		/* Finds the node with the same key as elm */ \
attr struct type * \		attr struct type * \
name##_RB_FIND(struct name head, struct type elm) \		name##_RB_FIND(struct name head, struct type elm) \
{ \		{ \
struct type *tmp = RB_ROOT(head); \		struct type *tmp = RB_ROOT(head); \
▲ Show 20 Lines • Show All 45 Lines • ▼ Show 20 Lines	if (RB_RIGHT(elm, field)) { \
while (RB_PARENT(elm, field) && \		while (RB_PARENT(elm, field) && \
(elm == RB_RIGHT(RB_PARENT(elm, field), field))) \		(elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
elm = RB_PARENT(elm, field); \		elm = RB_PARENT(elm, field); \
elm = RB_PARENT(elm, field); \		elm = RB_PARENT(elm, field); \
} \		} \
return (elm); \		return (elm); \
}		}

		#define RB_GENERATE_INSERT_NEXT(name, type, field, attr) \
		kibUnsubmitted Not Done Inline Actions #if defined(_KERNEL) && defined(DIAGNOSTIC) kib: ``` #if defined(_KERNEL) && defined(DIAGNOSTIC) ```
		/* Inserts a node into the next position in the RB tree */ \
		attr struct type * \
		name##_RB_INSERT_NEXT(struct name *head, \
		struct type elm, struct type next) \
		{ \
		struct type *tmp; \
		struct type **tmpp = &RB_RIGHT(elm, field); \
		\
		while ((tmp = *tmpp) != NULL) { \
		elm = tmp; \
		tmpp = &RB_LEFT(elm, field); \
		} \
		return (name##_RB_INSERT_FINISH(head, elm, tmpp, next)); \
		}

#define RB_GENERATE_PREV(name, type, field, attr) \		#define RB_GENERATE_PREV(name, type, field, attr) \
/* ARGSUSED */ \		/* ARGSUSED */ \
attr struct type * \		attr struct type * \
name##_RB_PREV(struct type *elm) \		name##_RB_PREV(struct type *elm) \
{ \		{ \
if (RB_LEFT(elm, field)) { \		if (RB_LEFT(elm, field)) { \
elm = RB_LEFT(elm, field); \		elm = RB_LEFT(elm, field); \
while (RB_RIGHT(elm, field)) \		while (RB_RIGHT(elm, field)) \
elm = RB_RIGHT(elm, field); \		elm = RB_RIGHT(elm, field); \
} else { \		} else { \
while (RB_PARENT(elm, field) && \		while (RB_PARENT(elm, field) && \
(elm == RB_LEFT(RB_PARENT(elm, field), field))) \		(elm == RB_LEFT(RB_PARENT(elm, field), field))) \
elm = RB_PARENT(elm, field); \		elm = RB_PARENT(elm, field); \
elm = RB_PARENT(elm, field); \		elm = RB_PARENT(elm, field); \
} \		} \
return (elm); \		return (elm); \
}		}

		#define RB_GENERATE_INSERT_PREV(name, type, field, attr) \
		/* Inserts a node into the prev position in the RB tree */ \
		attr struct type * \
		name##_RB_INSERT_PREV(struct name *head, \
		struct type elm, struct type prev) \
		{ \
		struct type *tmp; \
		struct type **tmpp = &RB_LEFT(elm, field); \
		\
		while ((tmp = *tmpp) != NULL) { \
		elm = tmp; \
		tmpp = &RB_RIGHT(elm, field); \
		} \
		return (name##_RB_INSERT_FINISH(head, elm, tmpp, prev)); \
		}

#define RB_GENERATE_MINMAX(name, type, field, attr) \		#define RB_GENERATE_MINMAX(name, type, field, attr) \
attr struct type * \		attr struct type * \
name##_RB_MINMAX(struct name *head, int val) \		name##_RB_MINMAX(struct name *head, int val) \
{ \		{ \
struct type *tmp = RB_ROOT(head); \		struct type *tmp = RB_ROOT(head); \
struct type *parent = NULL; \		struct type *parent = NULL; \
while (tmp) { \		while (tmp) { \
parent = tmp; \		parent = tmp; \
Show All 20 Lines	name##_RB_REINSERT(struct name head, struct type elm) \
} \		} \
return (NULL); \		return (NULL); \
} \		} \

#define RB_NEGINF -1		#define RB_NEGINF -1
#define RB_INF 1		#define RB_INF 1

#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)		#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
		#define RB_INSERT_NEXT(name, x, y, z) name##_RB_INSERT_NEXT(x, y, z)
		#define RB_INSERT_PREV(name, x, y, z) name##_RB_INSERT_PREV(x, y, z)
#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)		#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
#define RB_FIND(name, x, y) name##_RB_FIND(x, y)		#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)		#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
#define RB_NEXT(name, x, y) name##_RB_NEXT(y)		#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
#define RB_PREV(name, x, y) name##_RB_PREV(y)		#define RB_PREV(name, x, y) name##_RB_PREV(y)
#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)		#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)		#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
#define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y)		#define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y)
Show All 32 Lines