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