queue.h for free bsd
1
/* $OpenBSD: queue.h,v 1.32 2007/04/30 18:42:34 pedro Exp $ */
2
/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
3
4
/*
5
* Copyright (c) 1991, 1993
6
* The Regents of the University of California.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
* 3. Neither the name of the University nor the names of its contributors
17
* may be used to endorse or promote products derived from this software
18
* without 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
* @(#)queue.h 8.5 (Berkeley) 8/20/94
33
*/
34
35
#ifndef
_SYS_QUEUE_H_
36
#define
_SYS_QUEUE_H_
37
38
/*
39
* This file defines five types of data structures: singly-linked lists,
40
* lists, simple queues, tail queues, and circular queues.
41
*
42
*
43
* A singly-linked list is headed by a single forward pointer. The elements
44
* are singly linked for minimum space and pointer manipulation overhead at
45
* the expense of O(n) removal for arbitrary elements. New elements can be
46
* added to the list after an existing element or at the head of the list.
47
* Elements being removed from the head of the list should use the explicit
48
* macro for this purpose for optimum efficiency. A singly-linked list may
49
* only be traversed in the forward direction.Singly-linked lists are ideal
50
* for applications with large datasets and few or no removals or for
51
* implementing a LIFO queue.
52
*
53
* A list is headed by a single forward pointer (or an array of forward
54
* pointers for a hash table header). The elements are doubly linked
55
* so that an arbitrary element can be removed without a need to
56
* traverse the list. New elements can be added to the list before
57
* or after an existing element or at the head of the list. A list
58
* may only be traversed in the forward direction.
59
*
60
* A simple queue is headed by a pair of pointers, one the head of the
61
* list and the other to the tail of the list. The elements are singly
62
* linked to save space, so elements can only be removed from the
63
* head of the list. New elements can be added to the list before or after（？？）
64
* an existing element, at the head of the list, or at the end of the
65
* list. A simple queue may only be traversed in the forward direction.
66
*
67
* A tail queue is headed by a pair of pointers, one to the head of the
68
* list and the other to the tail of the list. The elements are doubly
69
* linked so that an arbitrary element can be removed without a need to
70
* traverse the list. New elements can be added to the list before or
71
* after an existing element, at the head of the list, or at the end of
72
* the list. A tail queue may be traversed in either direction.
73
*
74
* A circle queue is headed by a pair of pointers, one to the head of the
75
* list and the other to the tail of the list. The elements are doubly
76
* linked so that an arbitrary element can be removed without a need to
77
* traverse the list. New elements can be added to the list before or after
78
* an existing element, at the head of the list, or at the end of the list.
79
* A circle queue may be traversed in either direction, but has a more
80
* complex end of list detection.
81
*
82
* For details on the use of these macros, see the queue(3) manual page.
83
*/
84
85
#if
defined
(QUEUE_MACRO_DEBUG) || (
defined
(
_KERNEL
) &&
defined
(DIAGNOSTIC))
86
#define
_Q_INVALIDATE
(
a
) (
a
) = ((void *)-1)
87
#else
88
#define
_Q_INVALIDATE
(
a
)
89
#endif
90
91
/*
92
* Singly-linked List definitions.
93
*/
94
#define
SLIST_HEAD
(
name
,
type
) \
95
struct
name
{ \
96
struct
type
*slh_first; /* first element */ \
97
}
98
99
#define
SLIST_HEAD_INITIALIZER
(
head
) \
100
{
NULL
}
101
102
#define
SLIST_ENTRY
(
type
) \
103
struct { \
104
struct
type
*sle_next;/* next element */ \
105
}
106
107
/*
108
* Singly-linked List access methods.
109
*/
110
#define
SLIST_FIRST
(
head
) ((
head
)->slh_first)
111
#define
SLIST_END
(
head
)
NULL
112
#define
SLIST_EMPTY
(
head
) (
SLIST_FIRST
(
head
) ==
SLIST_END
(
head
))
113
#define
SLIST_NEXT
(elm,
field
)((elm)->
field
.sle_next)
114
115
#define
SLIST_FOREACH
(var,
head
,
field
) \
116
for((var) =
SLIST_FIRST
(
head
); \
117
(var) !=
SLIST_END
(
head
); \
118
(var) =
SLIST_NEXT
(var,
field
))
119
120
#define
SLIST_FOREACH_PREVPTR
(var,
varp
,
head
,
field
) \
121
for ((
varp
) = &
SLIST_FIRST
((
head
)); \
122
((var) = *(
varp
)) !=
SLIST_END
(
head
); \
123
(
varp
) = &
SLIST_NEXT
((var),
field
))
124
125
/*
126
* Singly-linked List functions.
127
*/
128
#define
SLIST_INIT
(
head
) { \
129
SLIST_FIRST
(
head
) =
SLIST_END
(
head
); \
130
}
131
132
#define
SLIST_INSERT_AFTER
(slistelm, elm,
field
) do { \
133
(elm)->
field
.sle_next = (slistelm)->
field
.sle_next; \
134
(slistelm)->
field
.sle_next = (elm); \
135
} while (0)
136
137
#define
SLIST_INSERT_HEAD
(
head
, elm,
field
) do { \
138
(elm)->
field
.sle_next = (
head
)->slh_first; \
139
(
head
)->slh_first = (elm); \
140
} while (0)
141
142
#define
SLIST_REMOVE_NEXT
(
head
, elm,
field
) do { \
143
(elm)->
field
.sle_next = (elm)->
field
.sle_next->
field
.sle_next;\
144
} while (0)
145
146
#define
SLIST_REMOVE_HEAD
(
head
,
field
) do { \
147
(
head
)->slh_first = (
head
)->slh_first->
field
.sle_next; \
148
} while (0)
149
150
#define
SLIST_REMOVE
(
head
, elm,
type
,
field
) do { \
151
if ((
head
)->slh_first == (elm)) { \
152
SLIST_REMOVE_HEAD
((
head
),
field
); \
153
} else { \
154
struct
type
*curelm = (
head
)->slh_first; \
155
\
156
while (curelm->
field
.sle_next != (elm)) \
157
curelm = curelm->
field
.sle_next; \
158
curelm->
field
.sle_next = \
159
curelm->
field
.sle_next->
field
.sle_next; \
160
_Q_INVALIDATE
((elm)->
field
.sle_next); \
161
} \
162
} while (0)
本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/63316/showart_2017968.html
页:
[1]