code:
/*	$NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $	*/
/*	$OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $	*/
/* $FreeBSD: release/9.0.0/sys/sys/tree.h 189204 2009-03-01 04:57:23Z bms $ */

/*-
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 * 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.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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_H_
#define	_SYS_TREE_H_

#include <sys/cdefs.h>

/*
 * This file defines data structures for different types of trees:
 * splay trees and red-black trees.
 *
 * A splay tree is a self-organizing data structure.  Every operation
 * on the tree causes a splay to happen.  The splay moves the requested
 * node to the root of the tree and partly rebalances it.
 *
 * This has the benefit that request locality causes faster lookups as
 * the requested nodes move to the top of the tree.  On the other hand,
 * every lookup causes memory writes.
 *
 * The Balance Theorem bounds the total access time for m operations
 * and n inserts on an initially empty tree as O((m + n)lg n).  The
 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
 *
 * A red-black tree is a binary search tree with the node color as an
 * extra attribute.  It fulfills a set of conditions:
 *	- every search path from the root to a leaf consists of the
 *	  same number of black nodes,
 *	- each red node (except for the root) has a black parent,
 *	- each leaf node is black.
 *
 * Every operation on a red-black tree is bounded as O(lg n).
 * The maximum height of a red-black tree is 2lg (n+1).
 */

#define SPLAY_HEAD(name, type)						\
struct name {								\
	struct type *sph_root; /* root of the tree */			\
}

#define SPLAY_INITIALIZER(root)						\
	{ NULL }

#define SPLAY_INIT(root) do {						\
	(root)->sph_root = NULL;					\
} while (/*CONSTCOND*/ 0)

#define SPLAY_ENTRY(type)						\
struct {								\
	struct type *spe_left; /* left element */			\
	struct type *spe_right; /* right element */			\
}

#define SPLAY_LEFT(elm, field)		(elm)->field.spe_left
#define SPLAY_RIGHT(elm, field)		(elm)->field.spe_right
#define SPLAY_ROOT(head)		(head)->sph_root
#define SPLAY_EMPTY(head)		(SPLAY_ROOT(head) == NULL)

/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {			\
	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);	\
	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
	(head)->sph_root = tmp;						\
} while (/*CONSTCOND*/ 0)

#define SPLAY_ROTATE_LEFT(head, tmp, field) do {			\
	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);	\
	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
	(head)->sph_root = tmp;						\
} while (/*CONSTCOND*/ 0)

#define SPLAY_LINKLEFT(head, tmp, field) do {				\
	SPLAY_LEFT(tmp, field) = (head)->sph_root;			\
	tmp = (head)->sph_root;						\
	(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);		\
} while (/*CONSTCOND*/ 0)

#define SPLAY_LINKRIGHT(head, tmp, field) do {				\
	SPLAY_RIGHT(tmp, field) = (head)->sph_root;			\
	tmp = (head)->sph_root;						\
	(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);	\
} while (/*CONSTCOND*/ 0)

#define SPLAY_ASSEMBLE(head, node, left, right, field) do {		\
	SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);	\
	SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
	SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);	\
	SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);	\
} while (/*CONSTCOND*/ 0)

/* Generates prototypes and inline functions */

#define SPLAY_PROTOTYPE(name, type, field, cmp)				\
void name##_SPLAY(struct name *, struct type *);			\
void name##_SPLAY_MINMAX(struct name *, int);				\
struct type *name##_SPLAY_INSERT(struct name *, struct type *);		\
struct type *name##_SPLAY_REMOVE(struct name *, struct type *);		\
									\
/* Finds the node with the same key as elm */				\
static __inline struct type *						\
name##_SPLAY_FIND(struct name *head, struct type *elm)			\
{									\
	if (SPLAY_EMPTY(head))						\
		return(NULL);						\
	name##_SPLAY(head, elm);					\
	if ((cmp)(elm, (head)->sph_root) == 0)				\
		return (head->sph_root);				\
	return (NULL);							\
}									\
									\
static __inline struct type *						\
name##_SPLAY_NEXT(struct name *head, struct type *elm)			\
{									\
	name##_SPLAY(head, elm);					\
	if (SPLAY_RIGHT(elm, field) != NULL) {				\
		elm = SPLAY_RIGHT(elm, field);				\
		while (SPLAY_LEFT(elm, field) != NULL) {		\
			elm = SPLAY_LEFT(elm, field);			\
		}							\
	} else								\
		elm = NULL;						\
	return (elm);							\
}									\
									\
static __inline struct type *						\
name##_SPLAY_MIN_MAX(struct name *head, int val)			\
{									\
	name##_SPLAY_MINMAX(head, val);					\
        return (SPLAY_ROOT(head));					\
}

/* Main splay operation.
 * Moves node close to the key of elm to top
 */
#define SPLAY_GENERATE(name, type, field, cmp)				\
struct type *								\
name##_SPLAY_INSERT(struct name *head, struct type *elm)		\
{									\
    if (SPLAY_EMPTY(head)) {						\
	    SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;	\
    } else {								\
	    int __comp;							\
	    name##_SPLAY(head, elm);					\
	    __comp = (cmp)(elm, (head)->sph_root);			\
	    if(__comp < 0) {						\
		    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
		    SPLAY_RIGHT(elm, field) = (head)->sph_root;		\
		    SPLAY_LEFT((head)->sph_root, field) = NULL;		\
	    } else if (__comp > 0) {					\
		    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
		    SPLAY_LEFT(elm, field) = (head)->sph_root;		\
		    SPLAY_RIGHT((head)->sph_root, field) = NULL;	\
	    } else							\
		    return ((head)->sph_root);				\
    }									\
    (head)->sph_root = (elm);						\
    return (NULL);							\
}									\
									\
struct type *								\
name##_SPLAY_REMOVE(struct name *head, struct type *elm)		\
{									\
	struct type *__tmp;						\
	if (SPLAY_EMPTY(head))						\
		return (NULL);						\
	name##_SPLAY(head, elm);					\
	if ((cmp)(elm, (head)->sph_root) == 0) {			\
		if (SPLAY_LEFT((head)->sph_root, field) == NULL) {	\
			(head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
		} else {						\
			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
			(head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
			name##_SPLAY(head, elm);			\
			SPLAY_RIGHT((head)->sph_root, field) = __tmp;	\
		}							\
		return (elm);						\
	}								\
	return (NULL);							\
}									\
									\
void									\
name##_SPLAY(struct name *head, struct type *elm)			\
{									\
	struct type __node, *__left, *__right, *__tmp;			\
	int __comp;							\
\
	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
	__left = __right = &__node;					\
\
	while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {		\
		if (__comp < 0) {					\
			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
			if (__tmp == NULL)				\
				break;					\
			if ((cmp)(elm, __tmp) < 0){			\
				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
					break;				\
			}						\
			SPLAY_LINKLEFT(head, __right, field);		\
		} else if (__comp > 0) {				\
			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
			if (__tmp == NULL)				\
				break;					\
			if ((cmp)(elm, __tmp) > 0){			\
				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
					break;				\
			}						\
			SPLAY_LINKRIGHT(head, __left, field);		\
		}							\
	}								\
	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
}									\
									\
/* Splay with either the minimum or the maximum element			\
 * Used to find minimum or maximum element in tree.			\
 */									\
void name##_SPLAY_MINMAX(struct name *head, int __comp) \
{									\
	struct type __node, *__left, *__right, *__tmp;			\
\
	SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
	__left = __right = &__node;					\
\
	while (1) {							\
		if (__comp < 0) {					\
			__tmp = SPLAY_LEFT((head)->sph_root, field);	\
			if (__tmp == NULL)				\
				break;					\
			if (__comp < 0){				\
				SPLAY_ROTATE_RIGHT(head, __tmp, field);	\
				if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
					break;				\
			}						\
			SPLAY_LINKLEFT(head, __right, field);		\
		} else if (__comp > 0) {				\
			__tmp = SPLAY_RIGHT((head)->sph_root, field);	\
			if (__tmp == NULL)				\
				break;					\
			if (__comp > 0) {				\
				SPLAY_ROTATE_LEFT(head, __tmp, field);	\
				if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
					break;				\
			}						\
			SPLAY_LINKRIGHT(head, __left, field);		\
		}							\
	}								\
	SPLAY_ASSEMBLE(head, &__node, __left, __right, field);		\
}

#define SPLAY_NEGINF	-1
#define SPLAY_INF	1

#define SPLAY_INSERT(name, x, y)	name##_SPLAY_INSERT(x, y)
#define SPLAY_REMOVE(name, x, y)	name##_SPLAY_REMOVE(x, y)
#define SPLAY_FIND(name, x, y)		name##_SPLAY_FIND(x, y)
#define SPLAY_NEXT(name, x, y)		name##_SPLAY_NEXT(x, y)
#define SPLAY_MIN(name, x)		(SPLAY_EMPTY(x) ? NULL	\
					: name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
#define SPLAY_MAX(name, x)		(SPLAY_EMPTY(x) ? NULL	\
					: name##_SPLAY_MIN_MAX(x, SPLAY_INF))

#define SPLAY_FOREACH(x, name, head)					\
	for ((x) = SPLAY_MIN(name, head);				\
	     (x) != NULL;						\
	     (x) = SPLAY_NEXT(name, head, x))

/* Macros that define a red-black tree */
#define RB_HEAD(name, type)						\
struct name {								\
	struct type *rbh_root; /* root of the tree */			\
}

#define RB_INITIALIZER(root)						\
	{ NULL }

#define RB_INIT(root) do {						\
	(root)->rbh_root = NULL;					\
} while (/*CONSTCOND*/ 0)

#define RB_BLACK	0
#define RB_RED		1
#define RB_ENTRY(type)							\
struct {								\
	struct type *rbe_left;		/* left element */		\
	struct type *rbe_right;		/* right element */		\
	struct type *rbe_parent;	/* parent element */		\
	int rbe_color;			/* node color */		\
}

#define RB_LEFT(elm, field)		(elm)->field.rbe_left
#define RB_RIGHT(elm, field)		(elm)->field.rbe_right
#define RB_PARENT(elm, field)		(elm)->field.rbe_parent
#define RB_COLOR(elm, field)		(elm)->field.rbe_color
#define RB_ROOT(head)			(head)->rbh_root
#define RB_EMPTY(head)			(RB_ROOT(head) == NULL)

#define RB_SET(elm, parent, field) do {					\
	RB_PARENT(elm, field) = parent;					\
	RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;		\
	RB_COLOR(elm, field) = RB_RED;					\
} while (/*CONSTCOND*/ 0)

#define RB_SET_BLACKRED(black, red, field) do {				\
	RB_COLOR(black, field) = RB_BLACK;				\
	RB_COLOR(red, field) = RB_RED;					\
} while (/*CONSTCOND*/ 0)

#ifndef RB_AUGMENT
#define RB_AUGMENT(x)	do {} while (0)
#endif

#define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
	(tmp) = RB_RIGHT(elm, field);					\
	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
		RB_PARENT(RB_LEFT(tmp, field), field) = (elm);		\
	}								\
	RB_AUGMENT(elm);						\
	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
		else							\
			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
	} else								\
		(head)->rbh_root = (tmp);				\
	RB_LEFT(tmp, field) = (elm);					\
	RB_PARENT(elm, field) = (tmp);					\
	RB_AUGMENT(tmp);						\
	if ((RB_PARENT(tmp, field)))					\
		RB_AUGMENT(RB_PARENT(tmp, field));			\
} while (/*CONSTCOND*/ 0)

#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
	(tmp) = RB_LEFT(elm, field);					\
	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\
		RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);		\
	}								\
	RB_AUGMENT(elm);						\
	if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {	\
		if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))	\
			RB_LEFT(RB_PARENT(elm, field), field) = (tmp);	\
		else							\
			RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);	\
	} else								\
		(head)->rbh_root = (tmp);				\
	RB_RIGHT(tmp, field) = (elm);					\
	RB_PARENT(elm, field) = (tmp);					\
	RB_AUGMENT(tmp);						\
	if ((RB_PARENT(tmp, field)))					\
		RB_AUGMENT(RB_PARENT(tmp, field));			\
} while (/*CONSTCOND*/ 0)

/* Generates prototypes and inline functions */
#define	RB_PROTOTYPE(name, type, field, cmp)				\
	RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
#define	RB_PROTOTYPE_STATIC(name, type, field, cmp)			\
	RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)		\
attr void name##_RB_INSERT_COLOR(struct name *, struct type *);		\
attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
attr struct type *name##_RB_REMOVE(struct name *, struct type *);	\
attr struct type *name##_RB_INSERT(struct name *, struct type *);	\
attr struct type *name##_RB_FIND(struct name *, struct type *);		\
attr struct type *name##_RB_NFIND(struct name *, struct type *);	\
attr struct type *name##_RB_NEXT(struct type *);			\
attr struct type *name##_RB_PREV(struct type *);			\
attr struct type *name##_RB_MINMAX(struct name *, int);			\
									\

/* Main rb operation.
 * Moves node close to the key of elm to top
 */
#define	RB_GENERATE(name, type, field, cmp)				\
	RB_GENERATE_INTERNAL(name, type, field, cmp,)
#define	RB_GENERATE_STATIC(name, type, field, cmp)			\
	RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)		\
attr void								\
name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
{									\
	struct type *parent, *gparent, *tmp;				\
	while ((parent = RB_PARENT(elm, field)) != NULL &&		\
	    RB_COLOR(parent, field) == RB_RED) {			\
		gparent = RB_PARENT(parent, field);			\
		if (parent == RB_LEFT(gparent, field)) {		\
			tmp = RB_RIGHT(gparent, field);			\
			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
				RB_COLOR(tmp, field) = RB_BLACK;	\
				RB_SET_BLACKRED(parent, gparent, field);\
				elm = gparent;				\
				continue;				\
			}						\
			if (RB_RIGHT(parent, field) == elm) {		\
				RB_ROTATE_LEFT(head, parent, tmp, field);\
				tmp = parent;				\
				parent = elm;				\
				elm = tmp;				\
			}						\
			RB_SET_BLACKRED(parent, gparent, field);	\
			RB_ROTATE_RIGHT(head, gparent, tmp, field);	\
		} else {						\
			tmp = RB_LEFT(gparent, field);			\
			if (tmp && RB_COLOR(tmp, field) == RB_RED) {	\
				RB_COLOR(tmp, field) = RB_BLACK;	\
				RB_SET_BLACKRED(parent, gparent, field);\
				elm = gparent;				\
				continue;				\
			}						\
			if (RB_LEFT(parent, field) == elm) {		\
				RB_ROTATE_RIGHT(head, parent, tmp, field);\
				tmp = parent;				\
				parent = elm;				\
				elm = tmp;				\
			}						\
			RB_SET_BLACKRED(parent, gparent, field);	\
			RB_ROTATE_LEFT(head, gparent, tmp, field);	\
		}							\
	}								\
	RB_COLOR(head->rbh_root, field) = RB_BLACK;			\
}									\
									\
attr void								\
name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
{									\
	struct type *tmp;						\
	while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&	\
	    elm != RB_ROOT(head)) {					\
		if (RB_LEFT(parent, field) == elm) {			\
			tmp = RB_RIGHT(parent, field);			\
			if (RB_COLOR(tmp, field) == RB_RED) {		\
				RB_SET_BLACKRED(tmp, parent, field);	\
				RB_ROTATE_LEFT(head, parent, tmp, field);\
				tmp = RB_RIGHT(parent, field);		\
			}						\
			if ((RB_LEFT(tmp, field) == NULL ||		\
			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
			    (RB_RIGHT(tmp, field) == NULL ||		\
			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
				RB_COLOR(tmp, field) = RB_RED;		\
				elm = parent;				\
				parent = RB_PARENT(elm, field);		\
			} else {					\
				if (RB_RIGHT(tmp, field) == NULL ||	\
				    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
					struct type *oleft;		\
					if ((oleft = RB_LEFT(tmp, field)) \
					    != NULL)			\
						RB_COLOR(oleft, field) = RB_BLACK;\
					RB_COLOR(tmp, field) = RB_RED;	\
					RB_ROTATE_RIGHT(head, tmp, oleft, field);\
					tmp = RB_RIGHT(parent, field);	\
				}					\
				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
				RB_COLOR(parent, field) = RB_BLACK;	\
				if (RB_RIGHT(tmp, field))		\
					RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
				RB_ROTATE_LEFT(head, parent, tmp, field);\
				elm = RB_ROOT(head);			\
				break;					\
			}						\
		} else {						\
			tmp = RB_LEFT(parent, field);			\
			if (RB_COLOR(tmp, field) == RB_RED) {		\
				RB_SET_BLACKRED(tmp, parent, field);	\
				RB_ROTATE_RIGHT(head, parent, tmp, field);\
				tmp = RB_LEFT(parent, field);		\
			}						\
			if ((RB_LEFT(tmp, field) == NULL ||		\
			    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
			    (RB_RIGHT(tmp, field) == NULL ||		\
			    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
				RB_COLOR(tmp, field) = RB_RED;		\
				elm = parent;				\
				parent = RB_PARENT(elm, field);		\
			} else {					\
				if (RB_LEFT(tmp, field) == NULL ||	\
				    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
					struct type *oright;		\
					if ((oright = RB_RIGHT(tmp, field)) \
					    != NULL)			\
						RB_COLOR(oright, field) = RB_BLACK;\
					RB_COLOR(tmp, field) = RB_RED;	\
					RB_ROTATE_LEFT(head, tmp, oright, field);\
					tmp = RB_LEFT(parent, field);	\
				}					\
				RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
				RB_COLOR(parent, field) = RB_BLACK;	\
				if (RB_LEFT(tmp, field))		\
					RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
				RB_ROTATE_RIGHT(head, parent, tmp, field);\
				elm = RB_ROOT(head);			\
				break;					\
			}						\
		}							\
	}								\
	if (elm)							\
		RB_COLOR(elm, field) = RB_BLACK;			\
}									\
									\
attr struct type *							\
name##_RB_REMOVE(struct name *head, struct type *elm)			\
{									\
	struct type *child, *parent, *old = elm;			\
	int color;							\
	if (RB_LEFT(elm, field) == NULL)				\
		child = RB_RIGHT(elm, field);				\
	else if (RB_RIGHT(elm, field) == NULL)				\
		child = RB_LEFT(elm, field);				\
	else {								\
		struct type *left;					\
		elm = RB_RIGHT(elm, field);				\
		while ((left = RB_LEFT(elm, field)) != NULL)		\
			elm = left;					\
		child = RB_RIGHT(elm, field);				\
		parent = RB_PARENT(elm, field);				\
		color = RB_COLOR(elm, field);				\
		if (child)						\
			RB_PARENT(child, field) = parent;		\
		if (parent) {						\
			if (RB_LEFT(parent, field) == elm)		\
				RB_LEFT(parent, field) = child;		\
			else						\
				RB_RIGHT(parent, field) = child;	\
			RB_AUGMENT(parent);				\
		} else							\
			RB_ROOT(head) = child;				\
		if (RB_PARENT(elm, field) == old)			\
			parent = elm;					\
		(elm)->field = (old)->field;				\
		if (RB_PARENT(old, field)) {				\
			if (RB_LEFT(RB_PARENT(old, field), field) == old)\
				RB_LEFT(RB_PARENT(old, field), field) = elm;\
			else						\
				RB_RIGHT(RB_PARENT(old, field), field) = elm;\
			RB_AUGMENT(RB_PARENT(old, field));		\
		} else							\
			RB_ROOT(head) = elm;				\
		RB_PARENT(RB_LEFT(old, field), field) = elm;		\
		if (RB_RIGHT(old, field))				\
			RB_PARENT(RB_RIGHT(old, field), field) = elm;	\
		if (parent) {						\
			left = parent;					\
			do {						\
				RB_AUGMENT(left);			\
			} while ((left = RB_PARENT(left, field)) != NULL); \
		}							\
		goto color;						\
	}								\
	parent = RB_PARENT(elm, field);					\
	color = RB_COLOR(elm, field);					\
	if (child)							\
		RB_PARENT(child, field) = parent;			\
	if (parent) {							\
		if (RB_LEFT(parent, field) == elm)			\
			RB_LEFT(parent, field) = child;			\
		else							\
			RB_RIGHT(parent, field) = child;		\
		RB_AUGMENT(parent);					\
	} else								\
		RB_ROOT(head) = child;					\
color:									\
	if (color == RB_BLACK)						\
		name##_RB_REMOVE_COLOR(head, parent, child);		\
	return (old);							\
}									\
									\
/* Inserts a node into the RB tree */					\
attr struct type *							\
name##_RB_INSERT(struct name *head, struct type *elm)			\
{									\
	struct type *tmp;						\
	struct type *parent = NULL;					\
	int comp = 0;							\
	tmp = RB_ROOT(head);						\
	while (tmp) {							\
		parent = tmp;						\
		comp = (cmp)(elm, parent);				\
		if (comp < 0)						\
			tmp = RB_LEFT(tmp, field);			\
		else if (comp > 0)					\
			tmp = RB_RIGHT(tmp, field);			\
		else							\
			return (tmp);					\
	}								\
	RB_SET(elm, parent, field);					\
	if (parent != NULL) {						\
		if (comp < 0)						\
			RB_LEFT(parent, field) = elm;			\
		else							\
			RB_RIGHT(parent, field) = elm;			\
		RB_AUGMENT(parent);					\
	} else								\
		RB_ROOT(head) = elm;					\
	name##_RB_INSERT_COLOR(head, elm);				\
	return (NULL);							\
}									\
									\
/* Finds the node with the same key as elm */				\
attr struct type *							\
name##_RB_FIND(struct name *head, struct type *elm)			\
{									\
	struct type *tmp = RB_ROOT(head);				\
	int comp;							\
	while (tmp) {							\
		comp = cmp(elm, tmp);					\
		if (comp < 0)						\
			tmp = RB_LEFT(tmp, field);			\
		else if (comp > 0)					\
			tmp = RB_RIGHT(tmp, field);			\
		else							\
			return (tmp);					\
	}								\
	return (NULL);							\
}									\
									\
/* Finds the first node greater than or equal to the search key */	\
attr struct type *							\
name##_RB_NFIND(struct name *head, struct type *elm)			\
{									\
	struct type *tmp = RB_ROOT(head);				\
	struct type *res = NULL;					\
	int comp;							\
	while (tmp) {							\
		comp = cmp(elm, tmp);					\
		if (comp < 0) {						\
			res = tmp;					\
			tmp = RB_LEFT(tmp, field);			\
		}							\
		else if (comp > 0)					\
			tmp = RB_RIGHT(tmp, field);			\
		else							\
			return (tmp);					\
	}								\
	return (res);							\
}									\
									\
/* ARGSUSED */								\
attr struct type *							\
name##_RB_NEXT(struct type *elm)					\
{									\
	if (RB_RIGHT(elm, field)) {					\
		elm = RB_RIGHT(elm, field);				\
		while (RB_LEFT(elm, field))				\
			elm = RB_LEFT(elm, field);			\
	} else {							\
		if (RB_PARENT(elm, field) &&				\
		    (elm == RB_LEFT(RB_PARENT(elm, field), field)))	\
			elm = RB_PARENT(elm, field);			\
		else {							\
			while (RB_PARENT(elm, field) &&			\
			    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
				elm = RB_PARENT(elm, field);		\
			elm = RB_PARENT(elm, field);			\
		}							\
	}								\
	return (elm);							\
}									\
									\
/* ARGSUSED */								\
attr struct type *							\
name##_RB_PREV(struct type *elm)					\
{									\
	if (RB_LEFT(elm, field)) {					\
		elm = RB_LEFT(elm, field);				\
		while (RB_RIGHT(elm, field))				\
			elm = RB_RIGHT(elm, field);			\
	} else {							\
		if (RB_PARENT(elm, field) &&				\
		    (elm == RB_RIGHT(RB_PARENT(elm, field), field)))	\
			elm = RB_PARENT(elm, field);			\
		else {							\
			while (RB_PARENT(elm, field) &&			\
			    (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
				elm = RB_PARENT(elm, field);		\
			elm = RB_PARENT(elm, field);			\
		}							\
	}								\
	return (elm);							\
}									\
									\
attr struct type *							\
name##_RB_MINMAX(struct name *head, int val)				\
{									\
	struct type *tmp = RB_ROOT(head);				\
	struct type *parent = NULL;					\
	while (tmp) {							\
		parent = tmp;						\
		if (val < 0)						\
			tmp = RB_LEFT(tmp, field);			\
		else							\
			tmp = RB_RIGHT(tmp, field);			\
	}								\
	return (parent);						\
}

#define RB_NEGINF	-1
#define RB_INF	1

#define RB_INSERT(name, x, y)	name##_RB_INSERT(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_NFIND(name, x, y)	name##_RB_NFIND(x, y)
#define RB_NEXT(name, x, y)	name##_RB_NEXT(y)
#define RB_PREV(name, x, y)	name##_RB_PREV(y)
#define RB_MIN(name, x)		name##_RB_MINMAX(x, RB_NEGINF)
#define RB_MAX(name, x)		name##_RB_MINMAX(x, RB_INF)

#define RB_FOREACH(x, name, head)					\
	for ((x) = RB_MIN(name, head);					\
	     (x) != NULL;						\
	     (x) = name##_RB_NEXT(x))

#define RB_FOREACH_FROM(x, name, y)					\
	for ((x) = (y);							\
	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
	     (x) = (y))

#define RB_FOREACH_SAFE(x, name, head, y)				\
	for ((x) = RB_MIN(name, head);					\
	    ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);	\
	     (x) = (y))

#define RB_FOREACH_REVERSE(x, name, head)				\
	for ((x) = RB_MAX(name, head);					\
	     (x) != NULL;						\
	     (x) = name##_RB_PREV(x))

#define RB_FOREACH_REVERSE_FROM(x, name, y)				\
	for ((x) = (y);							\
	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\
	     (x) = (y))

#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)			\
	for ((x) = RB_MAX(name, head);					\
	    ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);	\
	     (x) = (y))

#endif	/* _SYS_TREE_H_ */


code:
/*-
 * Copyright (c) 2008 Ed Schouten <ed@FreeBSD.org>
 * All rights reserved.
 *
 * Portions of this software were developed under sponsorship from Snow
 * B.V., the Netherlands.
 *
 * 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.
 *
 * 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.
 *
 * $FreeBSD: release/9.0.0/sys/sys/tty.h 223722 2011-07-02 13:54:20Z ed $
 */

#ifndef _SYS_TTY_H_
#define	_SYS_TTY_H_

#include <sys/param.h>
#include <sys/queue.h>
#include <sys/lock.h>
#include <sys/mutex.h>
#include <sys/condvar.h>
#include <sys/selinfo.h>
#include <sys/_termios.h>
#include <sys/ttycom.h>
#include <sys/ttyqueue.h>

struct cdev;
struct file;
struct pgrp;
struct session;
struct ucred;

struct ttydevsw;

/*
 * Per-TTY structure, containing buffers, etc.
 *
 * List of locks
 * (t)	locked by t_mtx
 * (l)	locked by tty_list_sx
 * (c)	const until freeing
 */
struct tty {
	struct mtx	*t_mtx;		/* TTY lock. */
	struct mtx	t_mtxobj;	/* Per-TTY lock (when not borrowing). */
	TAILQ_ENTRY(tty) t_list;	/* (l) TTY list entry. */
	unsigned int	t_flags;	/* (t) Terminal option flags. */
/* Keep flags in sync with db_show_tty and pstat(8). */
#define	TF_NOPREFIX	0x00001	/* Don't prepend "tty" to device name. */
#define	TF_INITLOCK	0x00002	/* Create init/lock state devices. */
#define	TF_CALLOUT	0x00004	/* Create "cua" devices. */
#define	TF_OPENED_IN	0x00008	/* "tty" node is in use. */
#define	TF_OPENED_OUT	0x00010	/* "cua" node is in use. */
#define	TF_OPENED_CONS	0x00020 /* Device in use as console. */
#define	TF_OPENED	(TF_OPENED_IN|TF_OPENED_OUT|TF_OPENED_CONS)
#define	TF_GONE		0x00040	/* Device node is gone. */
#define	TF_OPENCLOSE	0x00080	/* Device is in open()/close(). */
#define	TF_ASYNC	0x00100	/* Asynchronous I/O enabled. */
#define	TF_LITERAL	0x00200	/* Accept the next character literally. */
#define	TF_HIWAT_IN	0x00400	/* We've reached the input watermark. */
#define	TF_HIWAT_OUT	0x00800	/* We've reached the output watermark. */
#define	TF_HIWAT	(TF_HIWAT_IN|TF_HIWAT_OUT)
#define	TF_STOPPED	0x01000	/* Output flow control - stopped. */
#define	TF_EXCLUDE	0x02000	/* Exclusive access. */
#define	TF_BYPASS	0x04000	/* Optimized input path. */
#define	TF_ZOMBIE	0x08000	/* Modem disconnect received. */
#define	TF_HOOK		0x10000	/* TTY has hook attached. */
#define	TF_BUSY_IN	0x20000	/* Process busy in read() -- not supported. */
#define	TF_BUSY_OUT	0x40000	/* Process busy in write(). */
#define	TF_BUSY		(TF_BUSY_IN|TF_BUSY_OUT)
	unsigned int	t_revokecnt;	/* (t) revoke() count. */

	/* Buffering mechanisms. */
	struct ttyinq	t_inq;		/* (t) Input queue. */
	size_t		t_inlow;	/* (t) Input low watermark. */
	struct ttyoutq	t_outq;		/* (t) Output queue. */
	size_t		t_outlow;	/* (t) Output low watermark. */

	/* Sleeping mechanisms. */
	struct cv	t_inwait;	/* (t) Input wait queue. */
	struct cv	t_outwait;	/* (t) Output wait queue. */
	struct cv	t_outserwait;	/* (t) Serial output wait queue. */
	struct cv	t_bgwait;	/* (t) Background wait queue. */
	struct cv	t_dcdwait;	/* (t) Carrier Detect wait queue. */

	/* Polling mechanisms. */
	struct selinfo	t_inpoll;	/* (t) Input poll queue. */
	struct selinfo	t_outpoll;	/* (t) Output poll queue. */
	struct sigio	*t_sigio;	/* (t) Asynchronous I/O. */

	struct termios	t_termios;	/* (t) I/O processing flags. */
	struct winsize	t_winsize;	/* (t) Window size. */
	unsigned int	t_column;	/* (t) Current cursor position. */
	unsigned int	t_writepos;	/* (t) Where input was interrupted. */
	int		t_compatflags;	/* (t) COMPAT_43TTY flags. */

	/* Init/lock-state devices. */
	struct termios	t_termios_init_in;	/* tty%s.init. */
	struct termios	t_termios_lock_in;	/* tty%s.lock. */
	struct termios	t_termios_init_out;	/* cua%s.init. */
	struct termios	t_termios_lock_out;	/* cua%s.lock. */

	struct ttydevsw	*t_devsw;	/* (c) Driver hooks. */
	struct ttyhook	*t_hook;	/* (t) Capture/inject hook. */

	/* Process signal delivery. */
	struct pgrp	*t_pgrp;	/* (t) Foreground process group. */
	struct session	*t_session;	/* (t) Associated session. */
	unsigned int	t_sessioncnt;	/* (t) Backpointing sessions. */

	void		*t_devswsoftc;	/* (c) Soft config, for drivers. */
	void		*t_hooksoftc;	/* (t) Soft config, for hooks. */
	struct cdev	*t_dev;		/* (c) Primary character device. */
};

/*
 * Userland version of struct tty, for sysctl kern.ttys
 */
struct xtty {
	size_t	xt_size;	/* Structure size. */
	size_t	xt_insize;	/* Input queue size. */
	size_t	xt_incc;	/* Canonicalized characters. */
	size_t	xt_inlc;	/* Input line charaters. */
	size_t	xt_inlow;	/* Input low watermark. */
	size_t	xt_outsize;	/* Output queue size. */
	size_t	xt_outcc;	/* Output queue usage. */
	size_t	xt_outlow;	/* Output low watermark. */
	unsigned int xt_column;	/* Current column position. */
	pid_t	xt_pgid;	/* Foreground process group. */
	pid_t	xt_sid;		/* Session. */
	unsigned int xt_flags;	/* Terminal option flags. */
	dev_t	xt_dev;		/* Userland device. */
};

#ifdef _KERNEL

/* Used to distinguish between normal, callout, lock and init devices. */
#define	TTYUNIT_INIT		0x1
#define	TTYUNIT_LOCK		0x2
#define	TTYUNIT_CALLOUT		0x4

/* Allocation and deallocation. */
struct tty *tty_alloc(struct ttydevsw *tsw, void *softc);
struct tty *tty_alloc_mutex(struct ttydevsw *tsw, void *softc, struct mtx *mtx);
void	tty_rel_pgrp(struct tty *tp, struct pgrp *pgrp);
void	tty_rel_sess(struct tty *tp, struct session *sess);
void	tty_rel_gone(struct tty *tp);

#define	tty_lock(tp)		mtx_lock((tp)->t_mtx)
#define	tty_unlock(tp)		mtx_unlock((tp)->t_mtx)
#define	tty_lock_assert(tp,ma)	mtx_assert((tp)->t_mtx, (ma))
#define	tty_getlock(tp)		((tp)->t_mtx)

/* Device node creation. */
void	tty_makedev(struct tty *tp, struct ucred *cred, const char *fmt, ...)
    __printflike(3, 4);
#define	tty_makealias(tp,fmt,...) \
	make_dev_alias((tp)->t_dev, fmt, ## __VA_ARGS__)

/* Signalling processes. */
void	tty_signal_sessleader(struct tty *tp, int signal);
void	tty_signal_pgrp(struct tty *tp, int signal);
/* Waking up readers/writers. */
int	tty_wait(struct tty *tp, struct cv *cv);
int	tty_timedwait(struct tty *tp, struct cv *cv, int timo);
void	tty_wakeup(struct tty *tp, int flags);

/* System messages. */
int	tty_checkoutq(struct tty *tp);
int	tty_putchar(struct tty *tp, char c);

int	tty_ioctl(struct tty *tp, u_long cmd, void *data, int fflag,
    struct thread *td);
int	tty_ioctl_compat(struct tty *tp, u_long cmd, caddr_t data,
    int fflag, struct thread *td);
void	tty_init_console(struct tty *tp, speed_t speed);
void	tty_flush(struct tty *tp, int flags);
void	tty_hiwat_in_block(struct tty *tp);
void	tty_hiwat_in_unblock(struct tty *tp);
dev_t	tty_udev(struct tty *tp);
#define	tty_opened(tp)		((tp)->t_flags & TF_OPENED)
#define	tty_gone(tp)		((tp)->t_flags & TF_GONE)
#define	tty_softc(tp)		((tp)->t_devswsoftc)
#define	tty_devname(tp)		devtoname((tp)->t_dev)

/* Status line printing. */
void	tty_info(struct tty *tp);

/* /dev/console selection. */
void	ttyconsdev_select(const char *name);

/* Pseudo-terminal hooks. */
int	pts_alloc(int fflags, struct thread *td, struct file *fp);
int	pts_alloc_external(int fd, struct thread *td, struct file *fp,
    struct cdev *dev, const char *name);

/* Drivers and line disciplines also need to call these. */
#include <sys/ttydisc.h>
#include <sys/ttydevsw.h>
#include <sys/ttyhook.h>
#endif /* _KERNEL */

#endif /* !_SYS_TTY_H_ */

repo_name: veiledmerc/mira

license: mit


code:
/*-
 * Copyright (c) 1982, 1986, 1990, 1993, 1994
 *	The Regents of the University of California.  All rights reserved.
 * (c) UNIX System Laboratories, Inc.
 * All or some portions of this file are derived from material licensed
 * to the University of California by American Telephone and Telegraph
 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
 * the permission of UNIX System Laboratories, Inc.
 *
 * 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.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 *
 *	@(#)ttycom.h	8.1 (Berkeley) 3/28/94
 * $FreeBSD: release/9.0.0/sys/sys/ttycom.h 196884 2009-09-06 09:39:40Z ed $
 */

#ifndef	_SYS_TTYCOM_H_
#define	_SYS_TTYCOM_H_

#include <sys/ioccom.h>

/*
 * Tty ioctl's except for those supported only for backwards compatibility
 * with the old tty driver.
 */

/*
 * Window/terminal size structure.  This information is stored by the kernel
 * in order to provide a consistent interface, but is not used by the kernel.
 */
struct winsize {
	unsigned short	ws_row;		/* rows, in characters */
	unsigned short	ws_col;		/* columns, in characters */
	unsigned short	ws_xpixel;	/* horizontal size, pixels */
	unsigned short	ws_ypixel;	/* vertical size, pixels */
};

						/* 0-2 compat */
						/* 3-7 unused */
						/* 8-10 compat */
						/* 11-12 unused */
#define	TIOCEXCL	 _IO('t', 13)		/* set exclusive use of tty */
#define	TIOCNXCL	 _IO('t', 14)		/* reset exclusive use of tty */
#define	TIOCGPTN	_IOR('t', 15, int)	/* Get pts number. */
#define	TIOCFLUSH	_IOW('t', 16, int)	/* flush buffers */
						/* 17-18 compat */
#define	TIOCGETA	_IOR('t', 19, struct termios) /* get termios struct */
#define	TIOCSETA	_IOW('t', 20, struct termios) /* set termios struct */
#define	TIOCSETAW	_IOW('t', 21, struct termios) /* drain output, set */
#define	TIOCSETAF	_IOW('t', 22, struct termios) /* drn out, fls in, set */
						/* 23-25 unused */
#define	TIOCGETD	_IOR('t', 26, int)	/* get line discipline */
#define	TIOCSETD	_IOW('t', 27, int)	/* set line discipline */
#define	TIOCPTMASTER	 _IO('t', 28)		/* pts master validation */
						/* 29-85 unused */
#define	TIOCGDRAINWAIT	_IOR('t', 86, int)	/* get ttywait timeout */
#define	TIOCSDRAINWAIT	_IOW('t', 87, int)	/* set ttywait timeout */
						/* 88 unused */
						/* 89-91 conflicts: tun and tap */
#define	TIOCTIMESTAMP	_IOR('t', 89, struct timeval)	/* enable/get timestamp
						 * of last input event */
#define	TIOCMGDTRWAIT	_IOR('t', 90, int)	/* modem: get wait on close */
#define	TIOCMSDTRWAIT	_IOW('t', 91, int)	/* modem: set wait on close */
						/* 92-93 tun and tap */
						/* 94-97 conflicts: tun and tap */
#define	TIOCDRAIN	 _IO('t', 94)		/* wait till output drained */
#define	TIOCSIG		_IOWINT('t', 95)	/* pty: generate signal */
#define	TIOCEXT		_IOW('t', 96, int)	/* pty: external processing */
#define	TIOCSCTTY	 _IO('t', 97)		/* become controlling tty */
#define	TIOCCONS	_IOW('t', 98, int)	/* become virtual console */
#define	TIOCGSID	_IOR('t', 99, int)	/* get session id */
						/* 100 unused */
#define	TIOCSTAT	 _IO('t', 101)		/* simulate ^T status message */
#define	TIOCUCNTL	_IOW('t', 102, int)	/* pty: set/clr usr cntl mode */
#define		UIOCCMD(n)	_IO('u', n)	/* usr cntl op "n" */
#define	TIOCSWINSZ	_IOW('t', 103, struct winsize)	/* set window size */
#define	TIOCGWINSZ	_IOR('t', 104, struct winsize)	/* get window size */
						/* 105 unused */
#define	TIOCMGET	_IOR('t', 106, int)	/* get all modem bits */
#define		TIOCM_LE	0001		/* line enable */
#define		TIOCM_DTR	0002		/* data terminal ready */
#define		TIOCM_RTS	0004		/* request to send */
#define		TIOCM_ST	0010		/* secondary transmit */
#define		TIOCM_SR	0020		/* secondary receive */
#define		TIOCM_CTS	0040		/* clear to send */
#define		TIOCM_DCD	0100		/* data carrier detect */
#define		TIOCM_RI 	0200		/* ring indicate */
#define		TIOCM_DSR	0400		/* data set ready */
#define		TIOCM_CD	TIOCM_DCD
#define		TIOCM_CAR	TIOCM_DCD
#define		TIOCM_RNG	TIOCM_RI
#define	TIOCMBIC	_IOW('t', 107, int)	/* bic modem bits */
#define	TIOCMBIS	_IOW('t', 108, int)	/* bis modem bits */
#define	TIOCMSET	_IOW('t', 109, int)	/* set all modem bits */
#define	TIOCSTART	 _IO('t', 110)		/* start output, like ^Q */
#define	TIOCSTOP	 _IO('t', 111)		/* stop output, like ^S */
#define	TIOCPKT		_IOW('t', 112, int)	/* pty: set/clear packet mode */
#define		TIOCPKT_DATA		0x00	/* data packet */
#define		TIOCPKT_FLUSHREAD	0x01	/* flush packet */
#define		TIOCPKT_FLUSHWRITE	0x02	/* flush packet */
#define		TIOCPKT_STOP		0x04	/* stop output */
#define		TIOCPKT_START		0x08	/* start output */
#define		TIOCPKT_NOSTOP		0x10	/* no more ^S, ^Q */
#define		TIOCPKT_DOSTOP		0x20	/* now do ^S ^Q */
#define		TIOCPKT_IOCTL		0x40	/* state change of pty driver */
#define	TIOCNOTTY	 _IO('t', 113)		/* void tty association */
#define	TIOCSTI		_IOW('t', 114, char)	/* simulate terminal input */
#define	TIOCOUTQ	_IOR('t', 115, int)	/* output queue size */
						/* 116-117 compat */
#define	TIOCSPGRP	_IOW('t', 118, int)	/* set pgrp of tty */
#define	TIOCGPGRP	_IOR('t', 119, int)	/* get pgrp of tty */
#define	TIOCCDTR	 _IO('t', 120)		/* clear data terminal ready */
#define	TIOCSDTR	 _IO('t', 121)		/* set data terminal ready */
#define	TIOCCBRK	 _IO('t', 122)		/* clear break bit */
#define	TIOCSBRK	 _IO('t', 123)		/* set break bit */
						/* 124-127 compat */

#define	TTYDISC		0		/* termios tty line discipline */
#define	SLIPDISC	4		/* serial IP discipline */
#define	PPPDISC		5		/* PPP discipline */
#define	NETGRAPHDISC	6		/* Netgraph tty node discipline */
#define	H4DISC		7		/* Netgraph Bluetooth H4 discipline */

#endif /* !_SYS_TTYCOM_H_ */


code:
/*-
 * Copyright (c) 1982, 1986, 1993
 *	The Regents of the University of California.  All rights reserved.
 * (c) UNIX System Laboratories, Inc.
 * All or some portions of this file are derived from material licensed
 * to the University of California by American Telephone and Telegraph
 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
 * the permission of UNIX System Laboratories, Inc.
 *
 * 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.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 *
 *	@(#)ttydefaults.h	8.4 (Berkeley) 1/21/94
 * $FreeBSD: release/9.0.0/sys/sys/ttydefaults.h 184771 2008-11-08 20:40:39Z ed $
 */

/*
 * System wide defaults for terminal state.
 */
#ifndef _SYS_TTYDEFAULTS_H_
#define	_SYS_TTYDEFAULTS_H_

/*
 * Defaults on "first" open.
 */
#define	TTYDEF_IFLAG	(BRKINT	| ICRNL	| IMAXBEL | IXON | IXANY)
#define	TTYDEF_OFLAG	(OPOST | ONLCR)
#define	TTYDEF_LFLAG_NOECHO (ICANON | ISIG | IEXTEN)
#define	TTYDEF_LFLAG_ECHO (TTYDEF_LFLAG_NOECHO \
	| ECHO | ECHOE | ECHOKE | ECHOCTL)
#define	TTYDEF_LFLAG TTYDEF_LFLAG_ECHO
#define	TTYDEF_CFLAG	(CREAD | CS8 | HUPCL)
#define	TTYDEF_SPEED	(B9600)

/*
 * Control Character Defaults
 */
/*
 * XXX: A lot of code uses lowercase characters, but control-character
 * conversion is actually only valid when applied to uppercase
 * characters. We just treat lowercase characters as if they were
 * inserted as uppercase.
 */
#define	CTRL(x) ((x) >= 'a' && (x) <= 'z' ? \
	((x) - 'a' + 1) : (((x) - 'A' + 1) & 0x7f))
#define	CEOF		CTRL('D')
#define	CEOL		0xff		/* XXX avoid _POSIX_VDISABLE */
#define	CERASE		CTRL('?')
#define	CERASE2		CTRL('H')
#define	CINTR		CTRL('C')
#define	CSTATUS		CTRL('T')
#define	CKILL		CTRL('U')
#define	CMIN		1
#define	CQUIT		CTRL('\\')
#define	CSUSP		CTRL('Z')
#define	CTIME		0
#define	CDSUSP		CTRL('Y')
#define	CSTART		CTRL('Q')
#define	CSTOP		CTRL('S')
#define	CLNEXT		CTRL('V')
#define	CDISCARD 	CTRL('O')
#define	CWERASE 	CTRL('W')
#define	CREPRINT 	CTRL('R')
#define	CEOT		CEOF
/* compat */
#define	CBRK		CEOL
#define	CRPRNT		CREPRINT
#define	CFLUSH		CDISCARD

/* PROTECTED INCLUSION ENDS HERE */
#endif /* !_SYS_TTYDEFAULTS_H_ */

/*
 * #define TTYDEFCHARS to include an array of default control characters.
 */
#ifdef TTYDEFCHARS
static cc_t	ttydefchars[NCCS] = {
	CEOF,	CEOL,	CEOL,	CERASE, CWERASE, CKILL, CREPRINT,
	CERASE2, CINTR,	CQUIT,	CSUSP,	CDSUSP,	CSTART,	CSTOP,	CLNEXT,
	CDISCARD, CMIN,	CTIME,  CSTATUS, _POSIX_VDISABLE
};
#undef TTYDEFCHARS
#endif


code:
/*-
 * Copyright (c) 2008 Ed Schouten <ed@FreeBSD.org>
 * All rights reserved.
 *
 * Portions of this software were developed under sponsorship from Snow
 * B.V., the Netherlands.
 *
 * 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.
 *
 * 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.
 *
 * $FreeBSD: release/9.0.0/sys/sys/ttydevsw.h 223722 2011-07-02 13:54:20Z ed $
 */

#ifndef _SYS_TTYDEVSW_H_
#define	_SYS_TTYDEVSW_H_

#ifndef _SYS_TTY_H_
#error "can only be included through <sys/tty.h>"
#endif /* !_SYS_TTY_H_ */

/*
 * Driver routines that are called from the line discipline to adjust
 * hardware parameters and such.
 */
typedef int tsw_open_t(struct tty *tp);
typedef void tsw_close_t(struct tty *tp);
typedef void tsw_outwakeup_t(struct tty *tp);
typedef void tsw_inwakeup_t(struct tty *tp);
typedef int tsw_ioctl_t(struct tty *tp, u_long cmd, caddr_t data,
    struct thread *td);
typedef int tsw_cioctl_t(struct tty *tp, int unit, u_long cmd, caddr_t data,
    struct thread *td);
typedef int tsw_param_t(struct tty *tp, struct termios *t);
typedef int tsw_modem_t(struct tty *tp, int sigon, int sigoff);
typedef int tsw_mmap_t(struct tty *tp, vm_ooffset_t offset,
    vm_paddr_t * paddr, int nprot, vm_memattr_t *memattr);
typedef void tsw_pktnotify_t(struct tty *tp, char event);
typedef void tsw_free_t(void *softc);

struct ttydevsw {
	unsigned int	tsw_flags;	/* Default TTY flags. */

	tsw_open_t	*tsw_open;	/* Device opening. */
	tsw_close_t	*tsw_close;	/* Device closure. */

	tsw_outwakeup_t	*tsw_outwakeup;	/* Output available. */
	tsw_inwakeup_t	*tsw_inwakeup;	/* Input can be stored again. */

	tsw_ioctl_t	*tsw_ioctl;	/* ioctl() hooks. */
	tsw_cioctl_t	*tsw_cioctl;	/* ioctl() on control devices. */
	tsw_param_t	*tsw_param;	/* TIOCSETA device parameter setting. */
	tsw_modem_t	*tsw_modem;	/* Modem sigon/sigoff. */

	tsw_mmap_t	*tsw_mmap;	/* mmap() hooks. */
	tsw_pktnotify_t	*tsw_pktnotify;	/* TIOCPKT events. */

	tsw_free_t	*tsw_free;	/* Destructor. */

	void		*tsw_spare[4];	/* For future use. */
};

static __inline int
ttydevsw_open(struct tty *tp)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	return tp->t_devsw->tsw_open(tp);
}

static __inline void
ttydevsw_close(struct tty *tp)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	tp->t_devsw->tsw_close(tp);
}

static __inline void
ttydevsw_outwakeup(struct tty *tp)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	/* Prevent spurious wakeups. */
	if (ttydisc_getc_poll(tp) == 0)
		return;

	tp->t_devsw->tsw_outwakeup(tp);
}

static __inline void
ttydevsw_inwakeup(struct tty *tp)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	/* Prevent spurious wakeups. */
	if (tp->t_flags & TF_HIWAT_IN)
		return;

	tp->t_devsw->tsw_inwakeup(tp);
}

static __inline int
ttydevsw_ioctl(struct tty *tp, u_long cmd, caddr_t data, struct thread *td)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	return tp->t_devsw->tsw_ioctl(tp, cmd, data, td);
}

static __inline int
ttydevsw_cioctl(struct tty *tp, int unit, u_long cmd, caddr_t data, struct thread *td)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	return tp->t_devsw->tsw_cioctl(tp, unit, cmd, data, td);
}

static __inline int
ttydevsw_param(struct tty *tp, struct termios *t)
{
	MPASS(!tty_gone(tp));

	return tp->t_devsw->tsw_param(tp, t);
}

static __inline int
ttydevsw_modem(struct tty *tp, int sigon, int sigoff)
{
	MPASS(!tty_gone(tp));

	return tp->t_devsw->tsw_modem(tp, sigon, sigoff);
}

static __inline int
ttydevsw_mmap(struct tty *tp, vm_ooffset_t offset, vm_paddr_t *paddr,
    int nprot, vm_memattr_t *memattr)
{
	MPASS(!tty_gone(tp));

	return tp->t_devsw->tsw_mmap(tp, offset, paddr, nprot, memattr);
}

static __inline void
ttydevsw_pktnotify(struct tty *tp, char event)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	tp->t_devsw->tsw_pktnotify(tp, event);
}

static __inline void
ttydevsw_free(struct tty *tp)
{
	MPASS(tty_gone(tp));

	tp->t_devsw->tsw_free(tty_softc(tp));
}

#endif /* !_SYS_TTYDEVSW_H_ */


code:
/*-
 * Copyright (c) 2008 Ed Schouten <ed@FreeBSD.org>
 * All rights reserved.
 *
 * Portions of this software were developed under sponsorship from Snow
 * B.V., the Netherlands.
 *
 * 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.
 *
 * 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.
 *
 * $FreeBSD: release/9.0.0/sys/sys/ttydisc.h 196452 2009-08-23 08:04:40Z ed $
 */

#ifndef _SYS_TTYDISC_H_
#define	_SYS_TTYDISC_H_

#ifndef _SYS_TTY_H_
#error "can only be included through <sys/tty.h>"
#endif /* !_SYS_TTY_H_ */

struct cv;
struct thread;
struct tty;
struct uio;

/* Top half routines. */
void	ttydisc_open(struct tty *tp);
void	ttydisc_close(struct tty *tp);
int	ttydisc_read(struct tty *tp, struct uio *uio, int ioflag);
int	ttydisc_write(struct tty *tp, struct uio *uio, int ioflag);
void	ttydisc_optimize(struct tty *tp);

/* Bottom half routines. */
void	ttydisc_modem(struct tty *tp, int open);
#define ttydisc_can_bypass(tp) ((tp)->t_flags & TF_BYPASS)
int	ttydisc_rint(struct tty *tp, char c, int flags);
size_t	ttydisc_rint_simple(struct tty *tp, const void *buf, size_t len);
size_t	ttydisc_rint_bypass(struct tty *tp, const void *buf, size_t len);
void	ttydisc_rint_done(struct tty *tp);
size_t	ttydisc_rint_poll(struct tty *tp);
size_t	ttydisc_getc(struct tty *tp, void *buf, size_t len);
int	ttydisc_getc_uio(struct tty *tp, struct uio *uio);
size_t	ttydisc_getc_poll(struct tty *tp);

/* Error codes for ttydisc_rint(). */
#define	TRE_FRAMING	0x01
#define	TRE_PARITY	0x02
#define	TRE_OVERRUN	0x04
#define	TRE_BREAK	0x08

static __inline size_t
ttydisc_read_poll(struct tty *tp)
{

	tty_lock_assert(tp, MA_OWNED);

	return ttyinq_bytescanonicalized(&tp->t_inq);
}

static __inline size_t
ttydisc_write_poll(struct tty *tp)
{

	tty_lock_assert(tp, MA_OWNED);

	return ttyoutq_bytesleft(&tp->t_outq);
}

#endif /* !_SYS_TTYDISC_H_ */


code:
/*-
 * Copyright (c) 2008 Ed Schouten <ed@FreeBSD.org>
 * 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.
 *
 * 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.
 *
 * $FreeBSD: release/9.0.0/sys/sys/ttyhook.h 186056 2008-12-13 21:17:46Z mav $
 */

#ifndef _SYS_TTYHOOK_H_
#define	_SYS_TTYHOOK_H_

#ifndef _SYS_TTY_H_
#error "can only be included through <sys/tty.h>"
#endif /* !_SYS_TTY_H_ */

struct tty;

/*
 * Hooks interface, which allows to capture and inject traffic into the
 * input and output paths of a TTY.
 */

typedef int th_rint_t(struct tty *tp, char c, int flags);
typedef size_t th_rint_bypass_t(struct tty *tp, const void *buf, size_t len);
typedef void th_rint_done_t(struct tty *tp);
typedef size_t th_rint_poll_t(struct tty *tp);

typedef size_t th_getc_inject_t(struct tty *tp, void *buf, size_t len);
typedef void th_getc_capture_t(struct tty *tp, const void *buf, size_t len);
typedef size_t th_getc_poll_t(struct tty *tp);

typedef void th_close_t(struct tty *tp);

struct ttyhook {
	/* Character input. */
	th_rint_t		*th_rint;
	th_rint_bypass_t	*th_rint_bypass;
	th_rint_done_t		*th_rint_done;
	th_rint_poll_t		*th_rint_poll;

	/* Character output. */
	th_getc_inject_t	*th_getc_inject;
	th_getc_capture_t	*th_getc_capture;
	th_getc_poll_t		*th_getc_poll;

	th_close_t		*th_close;
};

int	ttyhook_register(struct tty **, struct proc *, int,
    struct ttyhook *, void *);
void	ttyhook_unregister(struct tty *);
#define	ttyhook_softc(tp)		((tp)->t_hooksoftc)
#define	ttyhook_hashook(tp,hook)	((tp)->t_hook != NULL && \
					(tp)->t_hook->th_ ## hook != NULL)

static __inline int
ttyhook_rint(struct tty *tp, char c, int flags)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	return tp->t_hook->th_rint(tp, c, flags);
}

static __inline size_t
ttyhook_rint_bypass(struct tty *tp, const void *buf, size_t len)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	return tp->t_hook->th_rint_bypass(tp, buf, len);
}

static __inline void
ttyhook_rint_done(struct tty *tp)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	tp->t_hook->th_rint_done(tp);
}

static __inline size_t
ttyhook_rint_poll(struct tty *tp)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	return tp->t_hook->th_rint_poll(tp);
}

static __inline size_t
ttyhook_getc_inject(struct tty *tp, void *buf, size_t len)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	return tp->t_hook->th_getc_inject(tp, buf, len);
}

static __inline void
ttyhook_getc_capture(struct tty *tp, const void *buf, size_t len)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	tp->t_hook->th_getc_capture(tp, buf, len);
}

static __inline size_t
ttyhook_getc_poll(struct tty *tp)
{
	tty_lock_assert(tp, MA_OWNED);
	MPASS(!tty_gone(tp));

	return tp->t_hook->th_getc_poll(tp);
}

static __inline void
ttyhook_close(struct tty *tp)
{
	tty_lock_assert(tp, MA_OWNED);

	tp->t_hook->th_close(tp);
}

#endif /* !_SYS_TTYHOOK_H_ */


code:
/*-
 * Copyright (c) 2008 Ed Schouten <ed@FreeBSD.org>
 * All rights reserved.
 *
 * Portions of this software were developed under sponsorship from Snow
 * B.V., the Netherlands.
 *
 * 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.
 *
 * 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.
 *
 * $FreeBSD: release/9.0.0/sys/sys/ttyqueue.h 198223 2009-10-19 07:17:37Z ed $
 */

#ifndef _SYS_TTYQUEUE_H_
#define	_SYS_TTYQUEUE_H_

#ifndef _SYS_TTY_H_
#error "can only be included through <sys/tty.h>"
#endif /* !_SYS_TTY_H_ */

struct tty;
struct ttyinq_block;
struct ttyoutq_block;
struct uio;

/* Data input queue. */
struct ttyinq {
	struct ttyinq_block	*ti_firstblock;
	struct ttyinq_block	*ti_startblock;
	struct ttyinq_block	*ti_reprintblock;
	struct ttyinq_block	*ti_lastblock;
	unsigned int		ti_begin;
	unsigned int		ti_linestart;
	unsigned int		ti_reprint;
	unsigned int		ti_end;
	unsigned int		ti_nblocks;
	unsigned int		ti_quota;
};
#define TTYINQ_DATASIZE 128

/* Data output queue. */
struct ttyoutq {
	struct ttyoutq_block	*to_firstblock;
	struct ttyoutq_block	*to_lastblock;
	unsigned int		to_begin;
	unsigned int		to_end;
	unsigned int		to_nblocks;
	unsigned int		to_quota;
};
#define TTYOUTQ_DATASIZE (256 - sizeof(struct ttyoutq_block *))

#ifdef _KERNEL
/* Input queue handling routines. */
void	ttyinq_setsize(struct ttyinq *ti, struct tty *tp, size_t len);
void	ttyinq_free(struct ttyinq *ti);
int	ttyinq_read_uio(struct ttyinq *ti, struct tty *tp, struct uio *uio,
    size_t readlen, size_t flushlen);
size_t	ttyinq_write(struct ttyinq *ti, const void *buf, size_t len,
    int quote);
int	ttyinq_write_nofrag(struct ttyinq *ti, const void *buf, size_t len,
    int quote);
void	ttyinq_canonicalize(struct ttyinq *ti);
size_t	ttyinq_findchar(struct ttyinq *ti, const char *breakc, size_t maxlen,
    char *lastc);
void	ttyinq_flush(struct ttyinq *ti);
int	ttyinq_peekchar(struct ttyinq *ti, char *c, int *quote);
void	ttyinq_unputchar(struct ttyinq *ti);
void	ttyinq_reprintpos_set(struct ttyinq *ti);
void	ttyinq_reprintpos_reset(struct ttyinq *ti);

static __inline size_t
ttyinq_getsize(struct ttyinq *ti)
{
	return (ti->ti_nblocks * TTYINQ_DATASIZE);
}

static __inline size_t
ttyinq_getallocatedsize(struct ttyinq *ti)
{

	return (ti->ti_quota * TTYINQ_DATASIZE);
}

static __inline size_t
ttyinq_bytesleft(struct ttyinq *ti)
{
	size_t len;

	/* Make sure the usage never exceeds the length. */
	len = ti->ti_nblocks * TTYINQ_DATASIZE;
	MPASS(len >= ti->ti_end);

	return (len - ti->ti_end);
}

static __inline size_t
ttyinq_bytescanonicalized(struct ttyinq *ti)
{
	MPASS(ti->ti_begin <= ti->ti_linestart);

	return (ti->ti_linestart - ti->ti_begin);
}

static __inline size_t
ttyinq_bytesline(struct ttyinq *ti)
{
	MPASS(ti->ti_linestart <= ti->ti_end);

	return (ti->ti_end - ti->ti_linestart);
}

/* Input buffer iteration. */
typedef void ttyinq_line_iterator_t(void *data, char c, int flags);
void	ttyinq_line_iterate_from_linestart(struct ttyinq *ti,
    ttyinq_line_iterator_t *iterator, void *data);
void	ttyinq_line_iterate_from_reprintpos(struct ttyinq *ti,
    ttyinq_line_iterator_t *iterator, void *data);

/* Output queue handling routines. */
void	ttyoutq_flush(struct ttyoutq *to);
void	ttyoutq_setsize(struct ttyoutq *to, struct tty *tp, size_t len);
void	ttyoutq_free(struct ttyoutq *to);
size_t	ttyoutq_read(struct ttyoutq *to, void *buf, size_t len);
int	ttyoutq_read_uio(struct ttyoutq *to, struct tty *tp, struct uio *uio);
size_t	ttyoutq_write(struct ttyoutq *to, const void *buf, size_t len);
int	ttyoutq_write_nofrag(struct ttyoutq *to, const void *buf, size_t len);

static __inline size_t
ttyoutq_getsize(struct ttyoutq *to)
{
	return (to->to_nblocks * TTYOUTQ_DATASIZE);
}

static __inline size_t
ttyoutq_getallocatedsize(struct ttyoutq *to)
{

	return (to->to_quota * TTYOUTQ_DATASIZE);
}

static __inline size_t
ttyoutq_bytesleft(struct ttyoutq *to)
{
	size_t len;

	/* Make sure the usage never exceeds the length. */
	len = to->to_nblocks * TTYOUTQ_DATASIZE;
	MPASS(len >= to->to_end);

	return (len - to->to_end);
}

static __inline size_t
ttyoutq_bytesused(struct ttyoutq *to)
{
	return (to->to_end - to->to_begin);
}
#endif /* _KERNEL */

#endif /* !_SYS_TTYQUEUE_H_ */


code:
/*-
 * Copyright (c) 2002 John Baldwin <jhb@FreeBSD.org>
 * 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. Neither the name of the author nor the names of any co-contributors
 *    may 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.
 *
 * $FreeBSD: release/9.0.0/sys/sys/turnstile.h 216421 2010-12-13 23:53:55Z mckusick $
 */

#ifndef _SYS_TURNSTILE_H_
#define _SYS_TURNSTILE_H_

/*
 * Turnstile interface.  Non-sleepable locks use a turnstile for the
 * queue of threads blocked on them when they are contested.  Each
 * turnstile contains two sub-queues: one for threads waiting for a
 * shared, or eread, lock, and one for threads waiting for an
 * exclusive, or write, lock.
 *
 * A thread calls turnstile_chain_lock() to lock the turnstile chain
 * associated with a given lock.  A thread calls turnstile_wait() when
 * the lock is contested to be put on the queue and block.  If a thread
 * calls turnstile_trywait() and decides to retry a lock operation instead
 * of blocking, it should call turnstile_cancel() to unlock the associated
 * turnstile chain lock.
 *
 * When a lock is released, the thread calls turnstile_lookup() to look
 * up the turnstile associated with the given lock in the hash table.  Then
 * it calls either turnstile_signal() or turnstile_broadcast() to mark
 * blocked threads for a pending wakeup.  turnstile_signal() marks the
 * highest priority blocked thread while turnstile_broadcast() marks all
 * blocked threads.  The turnstile_signal() function returns true if the
 * turnstile became empty as a result.  After the higher level code finishes
 * releasing the lock, turnstile_unpend() must be called to wake up the
 * pending thread(s) and give up ownership of the turnstile.
 *
 * Alternatively, if a thread wishes to relinquish ownership of a lock
 * without waking up any waiters, it may call turnstile_disown().
 *
 * When a lock is acquired that already has at least one thread contested
 * on it, the new owner of the lock must claim ownership of the turnstile
 * via turnstile_claim().
 *
 * Each thread allocates a turnstile at thread creation via turnstile_alloc()
 * and releases it at thread destruction via turnstile_free().  Note that
 * a turnstile is not tied to a specific thread and that the turnstile
 * released at thread destruction may not be the same turnstile that the
 * thread allocated when it was created.
 *
 * The highest priority thread blocked on a specified queue of a
 * turnstile can be obtained via turnstile_head().  A given queue can
 * also be queried to see if it is empty via turnstile_empty().
 */

struct lock_object;
struct thread;
struct turnstile;

#ifdef _KERNEL

/* Which queue to block on or which queue to wakeup one or more threads from. */
#define	TS_EXCLUSIVE_QUEUE	0
#define	TS_SHARED_QUEUE		1

/* The type of lock currently held. */
#define	TS_EXCLUSIVE_LOCK	TS_EXCLUSIVE_QUEUE
#define	TS_SHARED_LOCK		TS_SHARED_QUEUE

void	init_turnstiles(void);
void	turnstile_adjust(struct thread *, u_char);
struct turnstile *turnstile_alloc(void);
void	turnstile_broadcast(struct turnstile *, int);
void	turnstile_cancel(struct turnstile *);
void	turnstile_chain_lock(struct lock_object *);
void	turnstile_chain_unlock(struct lock_object *);
void	turnstile_claim(struct turnstile *);
void	turnstile_disown(struct turnstile *);
int	turnstile_empty(struct turnstile *ts, int queue);
void	turnstile_free(struct turnstile *);
struct thread *turnstile_head(struct turnstile *, int);
struct turnstile *turnstile_lookup(struct lock_object *);
int	turnstile_signal(struct turnstile *, int);
struct turnstile *turnstile_trywait(struct lock_object *);
void	turnstile_unpend(struct turnstile *, int);
void	turnstile_wait(struct turnstile *, struct thread *, int);

#endif	/* _KERNEL */
#endif	/* _SYS_TURNSTILE_H_ */


code:
/*-
 * Copyright (c) 1982, 1986, 1991, 1993, 1994
 *	The Regents of the University of California.  All rights reserved.
 * (c) UNIX System Laboratories, Inc.
 * All or some portions of this file are derived from material licensed
 * to the University of California by American Telephone and Telegraph
 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
 * the permission of UNIX System Laboratories, Inc.
 *
 * 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.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 *
 *	@(#)types.h	8.6 (Berkeley) 2/19/95
 * $FreeBSD: release/9.0.0/sys/sys/types.h 223710 2011-07-01 12:13:48Z jonathan $
 */

#ifndef _SYS_TYPES_H_
#define	_SYS_TYPES_H_

#include <sys/cdefs.h>

/* Machine type dependent parameters. */
#include <machine/endian.h>
#include <sys/_types.h>

#include <sys/_pthreadtypes.h>

#if __BSD_VISIBLE
typedef	unsigned char	u_char;
typedef	unsigned short	u_short;
typedef	unsigned int	u_int;
typedef	unsigned long	u_long;
#ifndef _KERNEL
typedef	unsigned short	ushort;		/* Sys V compatibility */
typedef	unsigned int	uint;		/* Sys V compatibility */
#endif
#endif

/*
 * XXX POSIX sized integrals that should appear only in <sys/stdint.h>.
 */
#include <sys/_stdint.h>

typedef __uint8_t	u_int8_t;	/* unsigned integrals (deprecated) */
typedef __uint16_t	u_int16_t;
typedef __uint32_t	u_int32_t;
typedef __uint64_t	u_int64_t;

typedef	__uint64_t	u_quad_t;	/* quads (deprecated) */
typedef	__int64_t	quad_t;
typedef	quad_t *	qaddr_t;

typedef	char *		caddr_t;	/* core address */
typedef	__const char *	c_caddr_t;	/* core address, pointer to const */
typedef	__volatile char *v_caddr_t;	/* core address, pointer to volatile */

#ifndef _BLKSIZE_T_DECLARED
typedef	__blksize_t	blksize_t;
#define	_BLKSIZE_T_DECLARED
#endif

typedef	__cpuwhich_t	cpuwhich_t;
typedef	__cpulevel_t	cpulevel_t;
typedef	__cpusetid_t	cpusetid_t;

#ifndef _BLKCNT_T_DECLARED
typedef	__blkcnt_t	blkcnt_t;
#define	_BLKCNT_T_DECLARED
#endif

typedef	__cap_rights_t	cap_rights_t;

#ifndef _CLOCK_T_DECLARED
typedef	__clock_t	clock_t;
#define	_CLOCK_T_DECLARED
#endif

#ifndef _CLOCKID_T_DECLARED
typedef	__clockid_t	clockid_t;
#define	_CLOCKID_T_DECLARED
#endif

typedef	__critical_t	critical_t;	/* Critical section value */
typedef	__int64_t	daddr_t;	/* disk address */

#ifndef _DEV_T_DECLARED
typedef	__dev_t		dev_t;		/* device number or struct cdev */
#define	_DEV_T_DECLARED
#endif

#ifndef _FFLAGS_T_DECLARED
typedef	__fflags_t	fflags_t;	/* file flags */
#define	_FFLAGS_T_DECLARED
#endif

typedef	__fixpt_t	fixpt_t;	/* fixed point number */

#ifndef _FSBLKCNT_T_DECLARED		/* for statvfs() */
typedef	__fsblkcnt_t	fsblkcnt_t;
typedef	__fsfilcnt_t	fsfilcnt_t;
#define	_FSBLKCNT_T_DECLARED
#endif

#ifndef _GID_T_DECLARED
typedef	__gid_t		gid_t;		/* group id */
#define	_GID_T_DECLARED
#endif

#ifndef _IN_ADDR_T_DECLARED
typedef	__uint32_t	in_addr_t;	/* base type for internet address */
#define	_IN_ADDR_T_DECLARED
#endif

#ifndef _IN_PORT_T_DECLARED
typedef	__uint16_t	in_port_t;
#define	_IN_PORT_T_DECLARED
#endif

#ifndef _ID_T_DECLARED
typedef	__id_t		id_t;		/* can hold a uid_t or pid_t */
#define	_ID_T_DECLARED
#endif

#ifndef _INO_T_DECLARED
typedef	__ino_t		ino_t;		/* inode number */
#define	_INO_T_DECLARED
#endif

#ifndef _KEY_T_DECLARED
typedef	__key_t		key_t;		/* IPC key (for Sys V IPC) */
#define	_KEY_T_DECLARED
#endif

#ifndef _LWPID_T_DECLARED
typedef	__lwpid_t	lwpid_t;	/* Thread ID (a.k.a. LWP) */
#define	_LWPID_T_DECLARED
#endif

#ifndef _MODE_T_DECLARED
typedef	__mode_t	mode_t;		/* permissions */
#define	_MODE_T_DECLARED
#endif

#ifndef _ACCMODE_T_DECLARED
typedef	__accmode_t	accmode_t;	/* access permissions */
#define	_ACCMODE_T_DECLARED
#endif

#ifndef _NLINK_T_DECLARED
typedef	__nlink_t	nlink_t;	/* link count */
#define	_NLINK_T_DECLARED
#endif

#ifndef _OFF_T_DECLARED
typedef	__off_t		off_t;		/* file offset */
#define	_OFF_T_DECLARED
#endif

#ifndef _PID_T_DECLARED
typedef	__pid_t		pid_t;		/* process id */
#define	_PID_T_DECLARED
#endif

typedef	__register_t	register_t;

#ifndef _RLIM_T_DECLARED
typedef	__rlim_t	rlim_t;		/* resource limit */
#define	_RLIM_T_DECLARED
#endif

typedef	__segsz_t	segsz_t;	/* segment size (in pages) */

#ifndef _SIZE_T_DECLARED
typedef	__size_t	size_t;
#define	_SIZE_T_DECLARED
#endif

#ifndef _SSIZE_T_DECLARED
typedef	__ssize_t	ssize_t;
#define	_SSIZE_T_DECLARED
#endif

#ifndef _SUSECONDS_T_DECLARED
typedef	__suseconds_t	suseconds_t;	/* microseconds (signed) */
#define	_SUSECONDS_T_DECLARED
#endif

#ifndef _TIME_T_DECLARED
typedef	__time_t	time_t;
#define	_TIME_T_DECLARED
#endif

#ifndef _TIMER_T_DECLARED
typedef	__timer_t	timer_t;
#define	_TIMER_T_DECLARED
#endif

#ifndef _MQD_T_DECLARED
typedef	__mqd_t	mqd_t;
#define	_MQD_T_DECLARED
#endif

typedef	__u_register_t	u_register_t;

#ifndef _UID_T_DECLARED
typedef	__uid_t		uid_t;		/* user id */
#define	_UID_T_DECLARED
#endif

#ifndef _USECONDS_T_DECLARED
typedef	__useconds_t	useconds_t;	/* microseconds (unsigned) */
#define	_USECONDS_T_DECLARED
#endif

typedef	__vm_offset_t	vm_offset_t;
typedef	__vm_ooffset_t	vm_ooffset_t;
typedef	__vm_paddr_t	vm_paddr_t;
typedef	__vm_pindex_t	vm_pindex_t;
typedef	__vm_size_t	vm_size_t;

#ifdef _KERNEL
typedef	int		boolean_t;
typedef	struct device	*device_t;
typedef	__intfptr_t	intfptr_t;

/*
 * XXX this is fixed width for historical reasons.  It should have had type
 * __int_fast32_t.  Fixed-width types should not be used unless binary
 * compatibility is essential.  Least-width types should be used even less
 * since they provide smaller benefits.
 *
 * XXX should be MD.
 *
 * XXX this is bogus in -current, but still used for spl*().
 */
typedef	__uint32_t	intrmask_t;	/* Interrupt mask (spl, xxx_imask...) */

typedef	__uintfptr_t	uintfptr_t;
typedef	__uint64_t	uoff_t;
typedef	char		vm_memattr_t;	/* memory attribute codes */
typedef	struct vm_page	*vm_page_t;

#ifndef offsetof
#define offsetof(type, field) __offsetof(type, field)
#endif

#endif /* !_KERNEL */

/*
 * The following are all things that really shouldn't exist in this header,
 * since its purpose is to provide typedefs, not miscellaneous doodads.
 */
#if __BSD_VISIBLE

#include <sys/select.h>

/*
 * minor() gives a cookie instead of an index since we don't want to
 * change the meanings of bits 0-15 or waste time and space shifting
 * bits 16-31 for devices that don't use them.
 */
#define	major(x)	((int)(((u_int)(x) >> 8)&0xff))	/* major number */
#define	minor(x)	((int)((x)&0xffff00ff))		/* minor number */
#define	makedev(x,y)	((dev_t)(((x) << 8) | (y)))	/* create dev_t */

/*
 * These declarations belong elsewhere, but are repeated here and in
 * <stdio.h> to give broken programs a better chance of working with
 * 64-bit off_t's.
 */
#ifndef _KERNEL
__BEGIN_DECLS
#ifndef _FTRUNCATE_DECLARED
#define	_FTRUNCATE_DECLARED
int	 ftruncate(int, off_t);
#endif
#ifndef _LSEEK_DECLARED
#define	_LSEEK_DECLARED
off_t	 lseek(int, off_t, int);
#endif
#ifndef _MMAP_DECLARED
#define	_MMAP_DECLARED
void *	 mmap(void *, size_t, int, int, int, off_t);
#endif
#ifndef _TRUNCATE_DECLARED
#define	_TRUNCATE_DECLARED
int	 truncate(const char *, off_t);
#endif
__END_DECLS
#endif /* !_KERNEL */

#endif /* __BSD_VISIBLE */

#endif /* !_SYS_TYPES_H_ */


code:
/*-
 * Copyright (c) 1999 Marcel Moolenaar
 * 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
 *    in this position and unchanged.
 * 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 ``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 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.
 *
 * $FreeBSD: release/9.0.0/sys/sys/ucontext.h 158471 2006-05-12 05:04:46Z jhb $
 */

#ifndef _SYS_UCONTEXT_H_
#define	_SYS_UCONTEXT_H_

#include <sys/signal.h>
#include <machine/ucontext.h>

typedef struct __ucontext {
	/*
	 * Keep the order of the first two fields. Also,
	 * keep them the first two fields in the structure.
	 * This way we can have a union with struct
	 * sigcontext and ucontext_t. This allows us to
	 * support them both at the same time.
	 * note: the union is not defined, though.
	 */
	sigset_t	uc_sigmask;
	mcontext_t	uc_mcontext;

	struct __ucontext *uc_link;
	stack_t		uc_stack;
	int		uc_flags;
#define	UCF_SWAPPED	0x00000001	/* Used by swapcontext(3). */
	int		__spare__[4];
} ucontext_t;

#if defined(_KERNEL) && defined(COMPAT_FREEBSD4)
#if defined(__i386__)
struct ucontext4 {
	sigset_t	uc_sigmask;
	struct mcontext4 uc_mcontext;
	struct ucontext4 *uc_link;
	stack_t		uc_stack;
	int		__spare__[8];
};
#else	/* __i386__ */
#define ucontext4 ucontext
#endif	/* __i386__ */
#endif	/* _KERNEL */

#ifndef _KERNEL

__BEGIN_DECLS

int	getcontext(ucontext_t *);
int	setcontext(const ucontext_t *);
void	makecontext(ucontext_t *, void (*)(void), int, ...);
int	signalcontext(ucontext_t *, int, __sighandler_t *);
int	swapcontext(ucontext_t *, const ucontext_t *);

__END_DECLS

#else /* _KERNEL */

struct thread;

/*
 * Flags for get_mcontext().  The low order 4 bits (i.e a mask of 0x0f) are
 * reserved for use by machine independent code.  All other bits are for use
 * by machine dependent code.
 */
#define	GET_MC_CLEAR_RET	1

/* Machine-dependent functions: */
int	get_mcontext(struct thread *, mcontext_t *, int);
int	set_mcontext(struct thread *, const mcontext_t *);

#endif /* !_KERNEL */

#endif /* !_SYS_UCONTEXT_H_ */


code:
/*-
 * Copyright (c) 1989, 1993
 *	The Regents of the University of California.  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.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 *
 *	@(#)ucred.h	8.4 (Berkeley) 1/9/95
 * $FreeBSD: release/9.0.0/sys/sys/ucred.h 219304 2011-03-05 12:40:35Z trasz $
 */

#ifndef _SYS_UCRED_H_
#define	_SYS_UCRED_H_

#include <bsm/audit.h>

struct loginclass;

/*
* Credentials.
*
* Please do not inspect cr_uid directly to determine superuserness.  The
* priv(9) interface should be used to check for privilege.
*/
#if defined(_KERNEL) || defined(_WANT_UCRED)
struct ucred {
	u_int	cr_ref;			/* reference count */
#define	cr_startcopy cr_uid
	uid_t	cr_uid;			/* effective user id */
	uid_t	cr_ruid;		/* real user id */
	uid_t	cr_svuid;		/* saved user id */
	int	cr_ngroups;		/* number of groups */
	gid_t	cr_rgid;		/* real group id */
	gid_t	cr_svgid;		/* saved group id */
	struct uidinfo	*cr_uidinfo;	/* per euid resource consumption */
	struct uidinfo	*cr_ruidinfo;	/* per ruid resource consumption */
	struct prison	*cr_prison;	/* jail(2) */
	struct loginclass	*cr_loginclass; /* login class */
	u_int		cr_flags;	/* credential flags */
	void 		*cr_pspare2[2];	/* general use 2 */
#define	cr_endcopy	cr_label

	uint64_t cr_sceAuthID;          /* sony app authorization id */
	uint64_t cr_sceCaps[0x04];	/* sony app capabilities */
	uint64_t cr_sceAttr[0x04];	/* sony app attributes */
	char     cr_unk0A0[0x48];

	struct auditinfo_addr	cr_audit;	/* Audit properties. */
	gid_t	*cr_groups;		/* groups */
	int	cr_agroups;		/* Available groups */
};
#define	NOCRED	((struct ucred *)0)	/* no credential available */
#define	FSCRED	((struct ucred *)-1)	/* filesystem credential */
#endif /* _KERNEL || _WANT_UCRED */

#define	XU_NGROUPS	16

/*
 * Flags for cr_flags.
 */
#define	CRED_FLAG_CAPMODE	0x00000001	/* In capability mode. */

/*
 * This is the external representation of struct ucred.
 */
struct xucred {
	u_int	cr_version;		/* structure layout version */
	uid_t	cr_uid;			/* effective user id */
	short	cr_ngroups;		/* number of groups */
	gid_t	cr_groups[XU_NGROUPS];	/* groups */
	void	*_cr_unused1;		/* compatibility with old ucred */
};
#define	XUCRED_VERSION	0

/* This can be used for both ucred and xucred structures. */
#define	cr_gid cr_groups[0]

#ifdef _KERNEL
struct proc;
struct thread;

void	change_egid(struct ucred *newcred, gid_t egid);
void	change_euid(struct ucred *newcred, struct uidinfo *euip);
void	change_rgid(struct ucred *newcred, gid_t rgid);
void	change_ruid(struct ucred *newcred, struct uidinfo *ruip);
void	change_svgid(struct ucred *newcred, gid_t svgid);
void	change_svuid(struct ucred *newcred, uid_t svuid);
void	crcopy(struct ucred *dest, struct ucred *src);
struct ucred	*crcopysafe(struct proc *p, struct ucred *cr);
struct ucred	*crdup(struct ucred *cr);
void	cred_update_thread(struct thread *td);
void	crfree(struct ucred *cr);
struct ucred	*crget(void);
struct ucred	*crhold(struct ucred *cr);
int	crshared(struct ucred *cr);
void	cru2x(struct ucred *cr, struct xucred *xcr);
void	crsetgroups(struct ucred *cr, int n, gid_t *groups);
int	groupmember(gid_t gid, struct ucred *cred);
#endif /* _KERNEL */

#endif /* !_SYS_UCRED_H_ */


code:
/*-
 * Copyright (c) 1982, 1986, 1993, 1994
 *	The Regents of the University of California.  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.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 *
 *	@(#)uio.h	8.5 (Berkeley) 2/22/94
 * $FreeBSD: release/9.0.0/sys/sys/uio.h 223889 2011-07-09 15:21:10Z kib $
 */

#ifndef _SYS_UIO_H_
#define	_SYS_UIO_H_

#include <sys/cdefs.h>
#include <sys/_types.h>
#include <sys/_iovec.h>

#ifndef _SSIZE_T_DECLARED
typedef	__ssize_t	ssize_t;
#define	_SSIZE_T_DECLARED
#endif

#ifndef _OFF_T_DECLARED
typedef	__off_t	off_t;
#define	_OFF_T_DECLARED
#endif

#if __BSD_VISIBLE
enum	uio_rw { UIO_READ, UIO_WRITE };

/* Segment flag values. */
enum uio_seg {
	UIO_USERSPACE,		/* from user data space */
	UIO_SYSSPACE,		/* from system space */
	UIO_NOCOPY		/* don't copy, already in object */
};
#endif

#ifdef _KERNEL

struct uio {
	struct	iovec *uio_iov;		/* scatter/gather list */
	int	uio_iovcnt;		/* length of scatter/gather list */
	off_t	uio_offset;		/* offset in target object */
	ssize_t	uio_resid;		/* remaining bytes to process */
	enum	uio_seg uio_segflg;	/* address space */
	enum	uio_rw uio_rw;		/* operation */
	struct	thread *uio_td;		/* owner */
};

/*
 * Limits
 *
 * N.B.: UIO_MAXIOV must be no less than IOV_MAX from <sys/syslimits.h>
 * which in turn must be no less than _XOPEN_IOV_MAX from <limits.h>.  If
 * we ever make this tunable (probably pointless), then IOV_MAX should be
 * removed from <sys/syslimits.h> and applications would be expected to use
 * sysconf(3) to find out the correct value, or else assume the worst
 * (_XOPEN_IOV_MAX).  Perhaps UIO_MAXIOV should be simply defined as
 * IOV_MAX.
 */
#define UIO_MAXIOV	1024		/* max 1K of iov's */

struct vm_object;
struct vm_page;

struct uio *cloneuio(struct uio *uiop);
int	copyinfrom(const void * __restrict src, void * __restrict dst,
	    size_t len, int seg);
int	copyiniov(struct iovec *iovp, u_int iovcnt, struct iovec **iov,
	    int error);
int	copyinstrfrom(const void * __restrict src, void * __restrict dst,
	    size_t len, size_t * __restrict copied, int seg);
int	copyinuio(struct iovec *iovp, u_int iovcnt, struct uio **uiop);
int	copyout_map(struct thread *td, vm_offset_t *addr, size_t sz);
int	copyout_unmap(struct thread *td, vm_offset_t addr, size_t sz);
int	uiomove(void *cp, int n, struct uio *uio);
int	uiomove_frombuf(void *buf, int buflen, struct uio *uio);
int	uiomove_fromphys(struct vm_page *ma[], vm_offset_t offset, int n,
	    struct uio *uio);
int	uiomove_nofault(void *cp, int n, struct uio *uio);
int	uiomoveco(void *cp, int n, struct uio *uio, int disposable);

#else /* !_KERNEL */

__BEGIN_DECLS
ssize_t	readv(int, const struct iovec *, int);
ssize_t	writev(int, const struct iovec *, int);
#if __BSD_VISIBLE
ssize_t	preadv(int, const struct iovec *, int, off_t);
ssize_t	pwritev(int, const struct iovec *, int, off_t);
#endif
__END_DECLS

#endif /* _KERNEL */

#endif /* !_SYS_UIO_H_ */


code:
/*-
 * Copyright (c) 2002, Jeffrey Roberson <jeff@freebsd.org>
 * 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 unmodified, 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.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 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.
 *
 * $FreeBSD: release/9.0.0/sys/sys/umtx.h 218970 2011-02-23 13:23:28Z jhb $
 *
 */

#ifndef _SYS_UMTX_H_
#define	_SYS_UMTX_H_

#include <sys/_umtx.h>
#include <sys/limits.h>

#define	UMTX_UNOWNED		0x0
#define	UMTX_CONTESTED		LONG_MIN

#define USYNC_PROCESS_SHARED	0x0001	/* Process shared sync objs */

#define	UMUTEX_UNOWNED		0x0
#define	UMUTEX_CONTESTED	0x80000000U

#define	UMUTEX_ERROR_CHECK	0x0002	/* Error-checking mutex */
#define	UMUTEX_PRIO_INHERIT	0x0004	/* Priority inherited mutex */
#define	UMUTEX_PRIO_PROTECT	0x0008	/* Priority protect mutex */

/* urwlock flags */
#define URWLOCK_PREFER_READER	0x0002

#define URWLOCK_WRITE_OWNER	0x80000000U
#define URWLOCK_WRITE_WAITERS	0x40000000U
#define URWLOCK_READ_WAITERS	0x20000000U
#define URWLOCK_MAX_READERS	0x1fffffffU
#define URWLOCK_READER_COUNT(c)	((c) & URWLOCK_MAX_READERS)

/* _usem flags */
#define SEM_NAMED	0x0002

/* op code for _umtx_op */
#define	UMTX_OP_LOCK		0
#define	UMTX_OP_UNLOCK		1
#define	UMTX_OP_WAIT		2
#define	UMTX_OP_WAKE		3
#define	UMTX_OP_MUTEX_TRYLOCK	4
#define	UMTX_OP_MUTEX_LOCK	5
#define	UMTX_OP_MUTEX_UNLOCK	6
#define	UMTX_OP_SET_CEILING	7
#define	UMTX_OP_CV_WAIT		8
#define	UMTX_OP_CV_SIGNAL	9
#define	UMTX_OP_CV_BROADCAST	10
#define	UMTX_OP_WAIT_UINT	11
#define	UMTX_OP_RW_RDLOCK	12
#define	UMTX_OP_RW_WRLOCK	13
#define	UMTX_OP_RW_UNLOCK	14
#define	UMTX_OP_WAIT_UINT_PRIVATE	15
#define	UMTX_OP_WAKE_PRIVATE	16
#define	UMTX_OP_MUTEX_WAIT	17
#define	UMTX_OP_MUTEX_WAKE	18
#define	UMTX_OP_SEM_WAIT	19
#define	UMTX_OP_SEM_WAKE	20
#define	UMTX_OP_NWAKE_PRIVATE   21
#define	UMTX_OP_MAX		22

/* Flags for UMTX_OP_CV_WAIT */
#define	CVWAIT_CHECK_UNPARKING	0x01
#define	CVWAIT_ABSTIME		0x02
#define	CVWAIT_CLOCKID		0x04

#define	UMTX_CHECK_UNPARKING	CVWAIT_CHECK_UNPARKING

#ifndef _KERNEL

int _umtx_op(void *obj, int op, u_long val, void *uaddr, void *uaddr2);

/*
 * Old (deprecated) userland mutex system calls.
 */
int _umtx_lock(struct umtx *mtx);
int _umtx_unlock(struct umtx *mtx);

/*
 * Standard api.  Try uncontested acquire/release and asks the
 * kernel to resolve failures.
 */
static __inline void
umtx_init(struct umtx *umtx)
{
	umtx->u_owner = UMTX_UNOWNED;
}

static __inline u_long
umtx_owner(struct umtx *umtx)
{
	return (umtx->u_owner & ~LONG_MIN);
}

static __inline int
umtx_lock(struct umtx *umtx, u_long id)
{
	if (atomic_cmpset_acq_long(&umtx->u_owner, UMTX_UNOWNED, id) == 0)
		if (_umtx_lock(umtx) == -1)
			return (errno);
	return (0);
}

static __inline int
umtx_trylock(struct umtx *umtx, u_long id)
{
	if (atomic_cmpset_acq_long(&umtx->u_owner, UMTX_UNOWNED, id) == 0)
		return (EBUSY);
	return (0);
}

static __inline int
umtx_timedlock(struct umtx *umtx, u_long id, const struct timespec *timeout)
{
	if (atomic_cmpset_acq_long(&umtx->u_owner, UMTX_UNOWNED, id) == 0)
		if (_umtx_op(umtx, UMTX_OP_LOCK, id, 0,
		    __DECONST(void *, timeout)) == -1)
			return (errno);
	return (0);
}

static __inline int
umtx_unlock(struct umtx *umtx, u_long id)
{
	if (atomic_cmpset_rel_long(&umtx->u_owner, id, UMTX_UNOWNED) == 0)
		if (_umtx_unlock(umtx) == -1)
			return (errno);
	return (0);
}

static __inline int
umtx_wait(u_long *p, long val, const struct timespec *timeout)
{
	if (_umtx_op(p, UMTX_OP_WAIT, val, 0,
	    __DECONST(void *, timeout)) == -1)
		return (errno);
	return (0);
}

/* Wake threads waiting on a user address. */
static __inline int
umtx_wake(u_long *p, int nr_wakeup)
{
	if (_umtx_op(p, UMTX_OP_WAKE, nr_wakeup, 0, 0) == -1)
		return (errno);
	return (0);
}

#else

/*
 * The umtx_key structure is used by both the Linux futex code and the
 * umtx implementation to map userland addresses to unique keys.
 */

enum {
	TYPE_SIMPLE_WAIT,
	TYPE_CV,
	TYPE_SEM,
	TYPE_SIMPLE_LOCK,
	TYPE_NORMAL_UMUTEX,
	TYPE_PI_UMUTEX,
	TYPE_PP_UMUTEX,
	TYPE_RWLOCK,
	TYPE_FUTEX
};

/* Key to represent a unique userland synchronous object */
struct umtx_key {
	int	hash;
	int	type;
	int	shared;
	union {
		struct {
			struct vm_object *object;
			uintptr_t	offset;
		} shared;
		struct {
			struct vmspace	*vs;
			uintptr_t	addr;
		} private;
		struct {
			void		*a;
			uintptr_t	b;
		} both;
	} info;
};

#define THREAD_SHARE		0
#define PROCESS_SHARE		1
#define AUTO_SHARE		2

struct thread;

static inline int
umtx_key_match(const struct umtx_key *k1, const struct umtx_key *k2)
{
	return (k1->type == k2->type &&
		k1->info.both.a == k2->info.both.a &&
	        k1->info.both.b == k2->info.both.b);
}

int umtx_key_get(void *, int, int, struct umtx_key *);
void umtx_key_release(struct umtx_key *);
struct umtx_q *umtxq_alloc(void);
void umtxq_free(struct umtx_q *);
int kern_umtx_wake(struct thread *, void *, int, int);
void umtx_pi_adjust(struct thread *, u_char);
void umtx_thread_init(struct thread *);
void umtx_thread_fini(struct thread *);
void umtx_thread_alloc(struct thread *);
void umtx_thread_exit(struct thread *);
#endif /* !_KERNEL */
#endif /* !_SYS_UMTX_H_ */


code:
/*-
 * Copyright (c) 1982, 1986, 1993
 *	The Regents of the University of California.  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.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 *
 *	@(#)un.h	8.3 (Berkeley) 2/19/95
 * $FreeBSD: release/9.0.0/sys/sys/un.h 183650 2008-10-06 18:43:11Z rwatson $
 */

#ifndef _SYS_UN_H_
#define _SYS_UN_H_

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

#ifndef _SA_FAMILY_T_DECLARED
typedef	__sa_family_t	sa_family_t;
#define	_SA_FAMILY_T_DECLARED
#endif

/*
 * Definitions for UNIX IPC domain.
 */
struct sockaddr_un {
	unsigned char	sun_len;	/* sockaddr len including null */
	sa_family_t	sun_family;	/* AF_UNIX */
	char	sun_path[104];		/* path name (gag) */
};

#if __BSD_VISIBLE

/* Socket options. */
#define	LOCAL_PEERCRED		0x001	/* retrieve peer credentials */
#define	LOCAL_CREDS		0x002	/* pass credentials to receiver */
#define	LOCAL_CONNWAIT		0x004	/* connects block until accepted */

#ifndef _KERNEL

/* actual length of an initialized sockaddr_un */
#define SUN_LEN(su) \
	(sizeof(*(su)) - sizeof((su)->sun_path) + strlen((su)->sun_path))

#endif /* !_KERNEL */

#endif /* __BSD_VISIBLE */

#endif /* !_SYS_UN_H_ */