/* $FreeBSD$ */

/*-
 * Copyright (c) 2007 Bruce M. Simpson.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef	_SYS_TREE_SET_H_
#define	_SYS_TREE_SET_H_

#include <sys/cdefs.h>
#include <sys/tree.h>

/*
 * Macros to generate prototypes for building ordered sets on RB-trees.
 */
#define RB_SET_PROTOTYPE(name, type, field, cmp, clone)			\
	RB_SET_PROTOTYPE_INTERNAL(name, type, field, cmp, clone,)
#define RB_SET_PROTOTYPE_STATIC(name, type, field, cmp, clone)		\
	RB_SET_PROTOTYPE_INTERNAL(name, type, field, cmp, clone,	\
	__unused static)
#define RB_SET_PROTOTYPE_INTERNAL(name, type, field, cmp, clone, attr)	\
attr int name##_RB_SET_DIFF(struct name *, struct name *, struct name *); \
attr int name##_RB_SET_INCLUDES(struct name *, struct name *);		\
attr int name##_RB_SET_INTERSECT(struct name *, struct name *, struct name *);\
attr int name##_RB_SET_SYMDIFF(struct name *, struct name *, struct name *); \
attr int name##_RB_SET_UNION(struct name *, struct name *, struct name *); \
attr int name##_RB_SET_UNION_BOUND(struct name *, struct name *,	\
	struct name *, size_t);

#define RB_SET_GENERATE(name, type, field, cmp, clone)			\
	RB_SET_GENERATE_INTERNAL(name, type, field, cmp, clone, )
#define RB_SET_GENERATE_STATIC(name, type, field, cmp, clone)		\
	RB_SET_GENERATE_INTERNAL(name, type, field, cmp, clone,		\
	    __unused static)
#define RB_SET_GENERATE_INTERNAL(name, type, field, cmp, clone, attr)	\
attr int name##_RB_SET_INCLUDES(struct name *x, struct name *y)		\
{									\
	struct type *px, *py;						\
	int comp;							\
	px = name##_RB_MINMAX(x, RB_NEGINF);				\
	py = name##_RB_MINMAX(y, RB_NEGINF);				\
	while (px != NULL && py != NULL) {				\
		comp = cmp(px, py);					\
		if (comp > 0)						\
			return (0);					\
		else if (comp < 0)					\
			px = name##_RB_NEXT(px);			\
		else {							\
			px = name##_RB_NEXT(px);			\
			py = name##_RB_NEXT(py);			\
		}							\
	}								\
	return (py == NULL);						\
}									\
attr int name##_RB_SET_DIFF(struct name *n, struct name *x,		\
    struct name *y)							\
{									\
	struct type *px, *py, *pn;					\
	int comp;							\
	size_t nelems = 0;						\
	px = name##_RB_MINMAX(x, RB_NEGINF);				\
	py = name##_RB_MINMAX(y, RB_NEGINF);				\
	while (px != NULL && py != NULL) {				\
		comp = cmp(px, py);					\
		if (comp < 0) {						\
			pn = clone(px);					\
			name##_RB_INSERT(n, pn);			\
			px = name##_RB_NEXT(px);			\
			++nelems;					\
		} else if (comp > 0) {					\
			py = name##_RB_NEXT(py);			\
		} else {						\
			px = name##_RB_NEXT(px);			\
			py = name##_RB_NEXT(py);			\
		}							\
	}								\
	while (px != NULL) {						\
		pn = clone(px);						\
		name##_RB_INSERT(n, pn);				\
		px = name##_RB_NEXT(px);				\
		++nelems;						\
	}								\
	return (nelems);						\
}									\
attr int name##_RB_SET_SYMDIFF(struct name *n, struct name *x,		\
    struct name *y)							\
{									\
	struct type *px, *py, *pn;					\
	int comp;							\
	size_t nelems = 0;						\
	px = name##_RB_MINMAX(x, RB_NEGINF);				\
	py = name##_RB_MINMAX(y, RB_NEGINF);				\
	while (px != NULL && py != NULL) {				\
		comp = cmp(px, py);					\
		if (comp < 0) {						\
			pn = clone(px);					\
			name##_RB_INSERT(n, pn);			\
			px = name##_RB_NEXT(px);			\
			++nelems;					\
		} else if (comp > 0) {					\
			pn = clone(py);					\
			name##_RB_INSERT(n, pn);			\
			py = name##_RB_NEXT(py);			\
			++nelems;					\
		} else {						\
			px = name##_RB_NEXT(px);			\
			py = name##_RB_NEXT(py);			\
		}							\
	}								\
	while (px != NULL) {						\
		pn = clone(px);						\
		name##_RB_INSERT(n, pn);				\
		px = name##_RB_NEXT(px);				\
		++nelems;						\
	}								\
	return (nelems);						\
}									\
attr int name##_RB_SET_UNION(struct name *n, struct name *x,		\
    struct name *y)							\
{									\
	struct type *px, *py, *pn;					\
	int comp;							\
	size_t nelems = 0;						\
	px = name##_RB_MINMAX(x, RB_NEGINF);				\
	py = name##_RB_MINMAX(y, RB_NEGINF);				\
	while (px != NULL && py != NULL) {				\
		comp = cmp(px, py);					\
		if (comp < 0) {						\
			pn = clone(px);					\
			name##_RB_INSERT(n, pn);			\
			px = name##_RB_NEXT(px);			\
			++nelems;					\
		} else if (comp > 0) {					\
			pn = clone(py);					\
			name##_RB_INSERT(n, pn);			\
			py = name##_RB_NEXT(py);			\
			++nelems;					\
		} else {						\
			pn = clone(px);					\
			name##_RB_INSERT(n, pn);			\
			px = name##_RB_NEXT(px);			\
			py = name##_RB_NEXT(py);			\
			++nelems;					\
		}							\
	}								\
	while (py != NULL) {						\
		pn = clone(py);						\
		name##_RB_INSERT(n, pn);				\
		py = name##_RB_NEXT(py);				\
		++nelems;						\
	}								\
	return (nelems);						\
}									\
attr int name##_RB_SET_UNION_BOUND(struct name *n, struct name *x,	\
    struct name *y, size_t bound)					\
{									\
	struct type *px, *py, *pn;					\
	int comp;							\
	size_t nelems = 0;						\
	px = name##_RB_MINMAX(x, RB_NEGINF);				\
	py = name##_RB_MINMAX(y, RB_NEGINF);				\
	while (px != NULL && py != NULL && nelems < bound) {		\
		comp = cmp(px, py);					\
		if (comp < 0) {						\
			pn = clone(px);					\
			name##_RB_INSERT(n, pn);			\
			px = name##_RB_NEXT(px);			\
			++nelems;					\
		} else if (comp > 0) {					\
			pn = clone(py);					\
			name##_RB_INSERT(n, pn);			\
			py = name##_RB_NEXT(py);			\
			++nelems;					\
		} else {						\
			pn = clone(px);					\
			name##_RB_INSERT(n, pn);			\
			px = name##_RB_NEXT(px);			\
			py = name##_RB_NEXT(py);			\
			++nelems;					\
		}							\
	}								\
	while (py != NULL && nelems < bound) {				\
		pn = clone(py);						\
		name##_RB_INSERT(n, pn);				\
		py = name##_RB_NEXT(py);				\
		++nelems;						\
	}								\
	return (nelems);						\
}									\
attr int name##_RB_SET_INTERSECT(struct name *n, struct name *x,	\
    struct name *y)							\
{									\
	struct type *px, *py, *pn;					\
	int comp;							\
	size_t nelems = 0;						\
	px = name##_RB_MINMAX(x, RB_NEGINF); 				\
	py = name##_RB_MINMAX(y, RB_NEGINF);				\
	while (px != NULL && py != NULL) {				\
		comp = cmp(px, py);					\
		if (comp < 0) {						\
			px = name##_RB_NEXT(px);			\
		} else if (comp > 0) {					\
			py = name##_RB_NEXT(py);			\
		} else {						\
			pn = clone(px);					\
			name##_RB_INSERT(n, pn);			\
			px = name##_RB_NEXT(px);			\
			py = name##_RB_NEXT(py);			\
			++nelems;					\
		}							\
	}								\
	return (nelems);						\
}

#define RB_SET_DIFF(name, x, y, r)					\
	name##_RB_SET_DIFF(x, y, r)
#define RB_SET_INCLUDES(name, x, y)					\
	name##_RB_SET_INCLUDES(x, y)
#define RB_SET_INTERSECT(name, x, y, r)					\
	name##_RB_SET_INTERSECT(x,, y, r)
#define RB_SET_SYMDIFF(name, x, y, r)					\
	name##_RB_SET_SYMDIFF(x,, y, r)
#define RB_SET_UNION(name, x, y, r)					\
	name##_RB_SET_UNION(x,, y, r)
#define RB_SET_UNION_BOUND(name, x, y, r, n)				\
	name##_RB_SET_UNION_BOUND(x,, y, r, n)

#endif	/* _SYS_TREE_SET_H_ */