1/*	$KAME: altq_classq.h,v 1.6 2003/01/07 07:33:38 kjc Exp $	*/
2
3/*
4 * Copyright (c) 1991-1997 Regents of the University of California.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 * 3. All advertising materials mentioning features or use of this software
16 *    must display the following acknowledgement:
17 *	This product includes software developed by the Network Research
18 *	Group at Lawrence Berkeley Laboratory.
19 * 4. Neither the name of the University nor of the Laboratory may be used
20 *    to endorse or promote products derived from this software without
21 *    specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35/*
36 * class queue definitions extracted from rm_class.h.
37 */
38#ifndef _ALTQ_ALTQ_CLASSQ_H_
39#define	_ALTQ_ALTQ_CLASSQ_H_
40
41#ifdef __cplusplus
42extern "C" {
43#endif
44
45/*
46 * Packet Queue types: RED or DROPHEAD.
47 */
48#define	Q_DROPHEAD	0x00
49#define	Q_RED		0x01
50#define	Q_RIO		0x02
51#define	Q_DROPTAIL	0x03
52
53#ifdef _KERNEL
54
55/*
56 * Packet Queue structures and macros to manipulate them.
57 */
58struct _class_queue_ {
59	struct mbuf	*tail_;	/* Tail of packet queue */
60	int	qlen_;		/* Queue length (in number of packets) */
61	int	qlim_;		/* Queue limit (in number of packets*) */
62	int	qtype_;		/* Queue type */
63};
64
65typedef struct _class_queue_	class_queue_t;
66
67#define	qtype(q)	(q)->qtype_		/* Get queue type */
68#define	qlimit(q)	(q)->qlim_		/* Max packets to be queued */
69#define	qlen(q)		(q)->qlen_		/* Current queue length. */
70#define	qtail(q)	(q)->tail_		/* Tail of the queue */
71#define	qhead(q)	((q)->tail_ ? (q)->tail_->m_nextpkt : NULL)
72
73#define	qempty(q)	((q)->qlen_ == 0)	/* Is the queue empty?? */
74#define	q_is_red(q)	((q)->qtype_ == Q_RED)	/* Is the queue a red queue */
75#define	q_is_rio(q)	((q)->qtype_ == Q_RIO)	/* Is the queue a rio queue */
76#define	q_is_red_or_rio(q)	((q)->qtype_ == Q_RED || (q)->qtype_ == Q_RIO)
77
78#if !defined(__GNUC__) || defined(ALTQ_DEBUG)
79
80extern void		_addq(class_queue_t *, struct mbuf *);
81extern struct mbuf	*_getq(class_queue_t *);
82extern struct mbuf	*_getq_tail(class_queue_t *);
83extern struct mbuf	*_getq_random(class_queue_t *);
84extern void		_removeq(class_queue_t *, struct mbuf *);
85extern void		_flushq(class_queue_t *);
86
87#else /* __GNUC__ && !ALTQ_DEBUG */
88/*
89 * inlined versions
90 */
91static __inline void
92_addq(class_queue_t *q, struct mbuf *m)
93{
94        struct mbuf *m0;
95
96	if ((m0 = qtail(q)) != NULL)
97		m->m_nextpkt = m0->m_nextpkt;
98	else
99		m0 = m;
100	m0->m_nextpkt = m;
101	qtail(q) = m;
102	qlen(q)++;
103}
104
105static __inline struct mbuf *
106_getq(class_queue_t *q)
107{
108	struct mbuf  *m, *m0;
109
110	if ((m = qtail(q)) == NULL)
111		return (NULL);
112	if ((m0 = m->m_nextpkt) != m)
113		m->m_nextpkt = m0->m_nextpkt;
114	else
115		qtail(q) = NULL;
116	qlen(q)--;
117	m0->m_nextpkt = NULL;
118	return (m0);
119}
120
121/* drop a packet at the tail of the queue */
122static __inline struct mbuf *
123_getq_tail(class_queue_t *q)
124{
125	struct mbuf *m, *m0, *prev;
126
127	if ((m = m0 = qtail(q)) == NULL)
128		return NULL;
129	do {
130		prev = m0;
131		m0 = m0->m_nextpkt;
132	} while (m0 != m);
133	prev->m_nextpkt = m->m_nextpkt;
134	if (prev == m)
135		qtail(q) = NULL;
136	else
137		qtail(q) = prev;
138	qlen(q)--;
139	m->m_nextpkt = NULL;
140	return (m);
141}
142
143/* randomly select a packet in the queue */
144static __inline struct mbuf *
145_getq_random(class_queue_t *q)
146{
147	struct mbuf *m;
148	int i, n;
149
150	if ((m = qtail(q)) == NULL)
151		return NULL;
152	if (m->m_nextpkt == m)
153		qtail(q) = NULL;
154	else {
155		struct mbuf *prev = NULL;
156
157		n = random() % qlen(q) + 1;
158		for (i = 0; i < n; i++) {
159			prev = m;
160			m = m->m_nextpkt;
161		}
162		prev->m_nextpkt = m->m_nextpkt;
163		if (m == qtail(q))
164			qtail(q) = prev;
165	}
166	qlen(q)--;
167	m->m_nextpkt = NULL;
168	return (m);
169}
170
171static __inline void
172_removeq(class_queue_t *q, struct mbuf *m)
173{
174	struct mbuf *m0, *prev;
175
176	m0 = qtail(q);
177	do {
178		prev = m0;
179		m0 = m0->m_nextpkt;
180	} while (m0 != m);
181	prev->m_nextpkt = m->m_nextpkt;
182	if (prev == m)
183		qtail(q) = NULL;
184	else if (qtail(q) == m)
185		qtail(q) = prev;
186	qlen(q)--;
187}
188
189static __inline void
190_flushq(class_queue_t *q)
191{
192	struct mbuf *m;
193
194	while ((m = _getq(q)) != NULL)
195		m_freem(m);
196}
197
198#endif /* __GNUC__ && !ALTQ_DEBUG */
199
200#endif /* _KERNEL */
201
202#ifdef __cplusplus
203}
204#endif
205
206#endif /* _ALTQ_ALTQ_CLASSQ_H_ */
207