| @@ -1,532 +1,532 @@ | | | @@ -1,532 +1,532 @@ |
1 | .\" $NetBSD: gcq.3,v 1.2 2009/05/27 17:47:46 snj Exp $ | | 1 | .\" $NetBSD: gcq.3,v 1.3 2009/05/27 19:23:28 wiz Exp $ |
2 | .\" | | 2 | .\" |
3 | .\" Not (c) 2007 Matthew Orgass | | 3 | .\" Not (c) 2007 Matthew Orgass |
4 | .\" This file is public domain, meaning anyone can make any use of part or all | | 4 | .\" This file is public domain, meaning anyone can make any use of part or all |
5 | .\" of this file including copying into other works without credit. Any use, | | 5 | .\" of this file including copying into other works without credit. Any use, |
6 | .\" modified or not, is solely the responsibility of the user. If this file | | 6 | .\" modified or not, is solely the responsibility of the user. If this file |
7 | .\" is part of a collection then use in the collection is governed by the | | 7 | .\" is part of a collection then use in the collection is governed by the |
8 | .\" terms of the collection. | | 8 | .\" terms of the collection. |
9 | .\" | | 9 | .\" |
10 | .Dd May 1, 2007 | | 10 | .Dd May 1, 2007 |
11 | .Dt gcq 3 | | 11 | .Dt GCQ 3 |
12 | .Os | | 12 | .Os |
13 | .Sh NAME | | 13 | .Sh NAME |
14 | .Nm GCQ_INIT , | | 14 | .Nm GCQ_INIT , |
15 | .Nm GCQ_INIT_HEAD , | | 15 | .Nm GCQ_INIT_HEAD , |
16 | .Nm gcq_init , | | 16 | .Nm gcq_init , |
17 | .Nm gcq_init_head , | | 17 | .Nm gcq_init_head , |
18 | .Nm gcq_q , | | 18 | .Nm gcq_q , |
19 | .Nm gcq_hq , | | 19 | .Nm gcq_hq , |
20 | .Nm gcq_head , | | 20 | .Nm gcq_head , |
21 | .Nm gcq_remove , | | 21 | .Nm gcq_remove , |
22 | .Nm gcq_onlist , | | 22 | .Nm gcq_onlist , |
23 | .Nm gcq_empty , | | 23 | .Nm gcq_empty , |
24 | .Nm gcq_linked , | | 24 | .Nm gcq_linked , |
25 | .Nm gcq_insert_after , | | 25 | .Nm gcq_insert_after , |
26 | .Nm gcq_insert_before , | | 26 | .Nm gcq_insert_before , |
27 | .Nm gcq_insert_head , | | 27 | .Nm gcq_insert_head , |
28 | .Nm gcq_insert_tail , | | 28 | .Nm gcq_insert_tail , |
29 | .Nm gcq_tie , | | 29 | .Nm gcq_tie , |
30 | .Nm gcq_tie_after , | | 30 | .Nm gcq_tie_after , |
31 | .Nm gcq_tie_before , | | 31 | .Nm gcq_tie_before , |
32 | .Nm gcq_merge , | | 32 | .Nm gcq_merge , |
33 | .Nm gcq_merge_head , | | 33 | .Nm gcq_merge_head , |
34 | .Nm gcq_merge_tail , | | 34 | .Nm gcq_merge_tail , |
35 | .Nm gcq_clear , | | 35 | .Nm gcq_clear , |
36 | .Nm gcq_remove_all , | | 36 | .Nm gcq_remove_all , |
37 | .Nm GCQ_ITEM , | | 37 | .Nm GCQ_ITEM , |
38 | .Nm GCQ_GOT_FIRST , | | 38 | .Nm GCQ_GOT_FIRST , |
39 | .Nm GCQ_GOT_LAST , | | 39 | .Nm GCQ_GOT_LAST , |
40 | .Nm GCQ_GOT_NEXT , | | 40 | .Nm GCQ_GOT_NEXT , |
41 | .Nm GCQ_GOT_PREV , | | 41 | .Nm GCQ_GOT_PREV , |
42 | .Nm GCQ_DEQUEUED_FIRST , | | 42 | .Nm GCQ_DEQUEUED_FIRST , |
43 | .Nm GCQ_DEQUEUED_LAST , | | 43 | .Nm GCQ_DEQUEUED_LAST , |
44 | .Nm GCQ_DEQUEUED_NEXT , | | 44 | .Nm GCQ_DEQUEUED_NEXT , |
45 | .Nm GCQ_DEQUEUED_PREV , | | 45 | .Nm GCQ_DEQUEUED_PREV , |
46 | .Nm GCQ_GOT_FIRST_TYPED , | | 46 | .Nm GCQ_GOT_FIRST_TYPED , |
47 | .Nm GCQ_GOT_LAST_TYPED , | | 47 | .Nm GCQ_GOT_LAST_TYPED , |
48 | .Nm GCQ_GOT_NEXT_TYPED , | | 48 | .Nm GCQ_GOT_NEXT_TYPED , |
49 | .Nm GCQ_GOT_PREV_TYPED , | | 49 | .Nm GCQ_GOT_PREV_TYPED , |
50 | .Nm GCQ_DEQUEUED_FIRST_TYPED , | | 50 | .Nm GCQ_DEQUEUED_FIRST_TYPED , |
51 | .Nm GCQ_DEQUEUED_LAST_TYPED , | | 51 | .Nm GCQ_DEQUEUED_LAST_TYPED , |
52 | .Nm GCQ_DEQUEUED_NEXT_TYPED , | | 52 | .Nm GCQ_DEQUEUED_NEXT_TYPED , |
53 | .Nm GCQ_DEQUEUED_PREV_TYPED , | | 53 | .Nm GCQ_DEQUEUED_PREV_TYPED , |
54 | .Nm GCQ_GOT_FIRST_COND , | | 54 | .Nm GCQ_GOT_FIRST_COND , |
55 | .Nm GCQ_GOT_LAST_COND , | | 55 | .Nm GCQ_GOT_LAST_COND , |
56 | .Nm GCQ_GOT_NEXT_COND , | | 56 | .Nm GCQ_GOT_NEXT_COND , |
57 | .Nm GCQ_GOT_PREV_COND , | | 57 | .Nm GCQ_GOT_PREV_COND , |
58 | .Nm GCQ_DEQUEUED_FIRST_COND , | | 58 | .Nm GCQ_DEQUEUED_FIRST_COND , |
59 | .Nm GCQ_DEQUEUED_LAST_COND , | | 59 | .Nm GCQ_DEQUEUED_LAST_COND , |
60 | .Nm GCQ_DEQUEUED_NEXT_COND , | | 60 | .Nm GCQ_DEQUEUED_NEXT_COND , |
61 | .Nm GCQ_DEQUEUED_PREV_COND , | | 61 | .Nm GCQ_DEQUEUED_PREV_COND , |
62 | .Nm GCQ_GOT_FIRST_COND_TYPED , | | 62 | .Nm GCQ_GOT_FIRST_COND_TYPED , |
63 | .Nm GCQ_GOT_LAST_COND_TYPED , | | 63 | .Nm GCQ_GOT_LAST_COND_TYPED , |
64 | .Nm GCQ_GOT_NEXT_COND_TYPED , | | 64 | .Nm GCQ_GOT_NEXT_COND_TYPED , |
65 | .Nm GCQ_GOT_PREV_COND_TYPED , | | 65 | .Nm GCQ_GOT_PREV_COND_TYPED , |
66 | .Nm GCQ_DEQUEUED_FIRST_COND_TYPED , | | 66 | .Nm GCQ_DEQUEUED_FIRST_COND_TYPED , |
67 | .Nm GCQ_DEQUEUED_LAST_COND_TYPED , | | 67 | .Nm GCQ_DEQUEUED_LAST_COND_TYPED , |
68 | .Nm GCQ_DEQUEUED_NEXT_COND_TYPED , | | 68 | .Nm GCQ_DEQUEUED_NEXT_COND_TYPED , |
69 | .Nm GCQ_DEQUEUED_PREV_COND_TYPED , | | 69 | .Nm GCQ_DEQUEUED_PREV_COND_TYPED , |
70 | .Nm GCQ_FOREACH , | | 70 | .Nm GCQ_FOREACH , |
71 | .Nm GCQ_FOREACH_REV , | | 71 | .Nm GCQ_FOREACH_REV , |
72 | .Nm GCQ_FOREACH_NVAR , | | 72 | .Nm GCQ_FOREACH_NVAR , |
73 | .Nm GCQ_FOREACH_NVAR_REV , | | 73 | .Nm GCQ_FOREACH_NVAR_REV , |
74 | .Nm GCQ_FOREACH_RO , | | 74 | .Nm GCQ_FOREACH_RO , |
75 | .Nm GCQ_FOREACH_RO_REV , | | 75 | .Nm GCQ_FOREACH_RO_REV , |
76 | .Nm GCQ_FOREACH_DEQUEUED , | | 76 | .Nm GCQ_FOREACH_DEQUEUED , |
77 | .Nm GCQ_FOREACH_DEQUEUED_REV , | | 77 | .Nm GCQ_FOREACH_DEQUEUED_REV , |
78 | .Nm GCQ_FOREACH_TYPED , | | 78 | .Nm GCQ_FOREACH_TYPED , |
79 | .Nm GCQ_FOREACH_REV_TYPED , | | 79 | .Nm GCQ_FOREACH_REV_TYPED , |
80 | .Nm GCQ_FOREACH_NVAR_TYPED , | | 80 | .Nm GCQ_FOREACH_NVAR_TYPED , |
81 | .Nm GCQ_FOREACH_NVAR_REV_TYPED , | | 81 | .Nm GCQ_FOREACH_NVAR_REV_TYPED , |
82 | .Nm GCQ_FOREACH_RO_TYPED , | | 82 | .Nm GCQ_FOREACH_RO_TYPED , |
83 | .Nm GCQ_FOREACH_RO_REV_TYPED , | | 83 | .Nm GCQ_FOREACH_RO_REV_TYPED , |
84 | .Nm GCQ_FOREACH_DEQUEUED_TYPED , | | 84 | .Nm GCQ_FOREACH_DEQUEUED_TYPED , |
85 | .Nm GCQ_FOREACH_DEQUEUED_REV_TYPED , | | 85 | .Nm GCQ_FOREACH_DEQUEUED_REV_TYPED , |
86 | .Nm GCQ_FIND , | | 86 | .Nm GCQ_FIND , |
87 | .Nm GCQ_FIND_REV , | | 87 | .Nm GCQ_FIND_REV , |
88 | .Nm GCQ_FIND_TYPED , | | 88 | .Nm GCQ_FIND_TYPED , |
89 | .Nm GCQ_FIND_REV_TYPED | | 89 | .Nm GCQ_FIND_REV_TYPED |
90 | .Nd "Generic Circular Queues" | | 90 | .Nd "Generic Circular Queues" |
91 | .Sh SYNOPSIS | | 91 | .Sh SYNOPSIS |
92 | .In sys/gcq.h | | 92 | .In sys/gcq.h |
93 | .Pp | | 93 | .Pp |
94 | .Vt struct gcq ; | | 94 | .Vt struct gcq ; |
95 | .Vt struct gcq_head ; | | 95 | .Vt struct gcq_head ; |
96 | .Pp | | 96 | .Pp |
97 | .Fn GCQ_INIT name | | 97 | .Fn GCQ_INIT name |
98 | .Fn GCQ_INIT_HEAD name | | 98 | .Fn GCQ_INIT_HEAD name |
99 | .Pp | | 99 | .Pp |
100 | .Ft static inline void | | 100 | .Ft static inline void |
101 | .Fn gcq_init "struct gcq *q" | | 101 | .Fn gcq_init "struct gcq *q" |
102 | .Ft static inline void | | 102 | .Ft static inline void |
103 | .Fn gcq_init_head "struct gcq_head *head" | | 103 | .Fn gcq_init_head "struct gcq_head *head" |
104 | .Ft static inline struct gcq * | | 104 | .Ft static inline struct gcq * |
105 | .Fn gcq_q "struct gcq_head *head" | | 105 | .Fn gcq_q "struct gcq_head *head" |
106 | .Ft static inline struct gcq * | | 106 | .Ft static inline struct gcq * |
107 | .Fn gcq_hq "struct gcq_head *head" | | 107 | .Fn gcq_hq "struct gcq_head *head" |
108 | .Ft static inline struct gcq_head * | | 108 | .Ft static inline struct gcq_head * |
109 | .Fn gcq_head "struct gcq *q" | | 109 | .Fn gcq_head "struct gcq *q" |
110 | .Ft static inline struct gcq * | | 110 | .Ft static inline struct gcq * |
111 | .Fn gcq_remove "struct gcq *q" | | 111 | .Fn gcq_remove "struct gcq *q" |
112 | .Ft static inline bool | | 112 | .Ft static inline bool |
113 | .Fn gcq_onlist "struct gcq *q" | | 113 | .Fn gcq_onlist "struct gcq *q" |
114 | .Ft static inline bool | | 114 | .Ft static inline bool |
115 | .Fn gcq_empty "struct gcq_head *head" | | 115 | .Fn gcq_empty "struct gcq_head *head" |
116 | .Ft static inline bool | | 116 | .Ft static inline bool |
117 | .Fn gcq_linked "struct gcq *prev" "struct gcq *next" | | 117 | .Fn gcq_linked "struct gcq *prev" "struct gcq *next" |
118 | .Ft static inline void | | 118 | .Ft static inline void |
119 | .Fn gcq_insert_after "struct gcq *on" "struct gcq *off" | | 119 | .Fn gcq_insert_after "struct gcq *on" "struct gcq *off" |
120 | .Ft static inline void | | 120 | .Ft static inline void |
121 | .Fn gcq_insert_before "struct gcq *on" "struct gcq *off" | | 121 | .Fn gcq_insert_before "struct gcq *on" "struct gcq *off" |
122 | .Ft static inline void | | 122 | .Ft static inline void |
123 | .Fn gcq_insert_head "struct gcq_head *head" "struct gcq *q" | | 123 | .Fn gcq_insert_head "struct gcq_head *head" "struct gcq *q" |
124 | .Ft static inline void | | 124 | .Ft static inline void |
125 | .Fn gcq_insert_tail "struct gcq_head *head" "struct gcq *q" | | 125 | .Fn gcq_insert_tail "struct gcq_head *head" "struct gcq *q" |
126 | .Ft static inline void | | 126 | .Ft static inline void |
127 | .Fn gcq_tie "struct gcq *dst" "struct gcq *src" | | 127 | .Fn gcq_tie "struct gcq *dst" "struct gcq *src" |
128 | .Ft static inline void | | 128 | .Ft static inline void |
129 | .Fn gcq_tie_after "struct gcq *dst" "struct gcq *src" | | 129 | .Fn gcq_tie_after "struct gcq *dst" "struct gcq *src" |
130 | .Ft static inline void | | 130 | .Ft static inline void |
131 | .Fn gcq_tie_before "struct gcq *dst" "struct gcq *src" | | 131 | .Fn gcq_tie_before "struct gcq *dst" "struct gcq *src" |
132 | .Ft static inline void | | 132 | .Ft static inline void |
133 | .Fn gcq_merge "struct gcq *dst" "struct gcq *src" | | 133 | .Fn gcq_merge "struct gcq *dst" "struct gcq *src" |
134 | .Ft static inline void | | 134 | .Ft static inline void |
135 | .Fn gcq_merge_tail "struct gcq_head *dst" "struct gcq_head *src" | | 135 | .Fn gcq_merge_tail "struct gcq_head *dst" "struct gcq_head *src" |
136 | .Ft static inline void | | 136 | .Ft static inline void |
137 | .Fn gcq_merge_head "struct gcq_head *dst" "struct gcq_head *src" | | 137 | .Fn gcq_merge_head "struct gcq_head *dst" "struct gcq_head *src" |
138 | .Ft static inline void | | 138 | .Ft static inline void |
139 | .Fn gcq_clear "struct gcq *q" | | 139 | .Fn gcq_clear "struct gcq *q" |
140 | .Ft static inline void | | 140 | .Ft static inline void |
141 | .Fn gcq_remove_all "struct gcq_head *head" | | 141 | .Fn gcq_remove_all "struct gcq_head *head" |
142 | .Pp | | 142 | .Pp |
143 | .Ft type * | | 143 | .Ft type * |
144 | .Fn GCQ_ITEM q type name | | 144 | .Fn GCQ_ITEM q type name |
145 | .Ft bool | | 145 | .Ft bool |
146 | .Fn GCQ_GOT_FIRST var head | | 146 | .Fn GCQ_GOT_FIRST var head |
147 | .Ft bool | | 147 | .Ft bool |
148 | .Fn GCQ_GOT_LAST var head | | 148 | .Fn GCQ_GOT_LAST var head |
149 | .Ft bool | | 149 | .Ft bool |
150 | .Fn GCQ_GOT_NEXT var current head start | | 150 | .Fn GCQ_GOT_NEXT var current head start |
151 | .Ft bool | | 151 | .Ft bool |
152 | .Fn GCQ_GOT_PREV var current head start | | 152 | .Fn GCQ_GOT_PREV var current head start |
153 | .Ft bool | | 153 | .Ft bool |
154 | .Fn GCQ_DEQUEUED_FIRST var head | | 154 | .Fn GCQ_DEQUEUED_FIRST var head |
155 | .Ft bool | | 155 | .Ft bool |
156 | .Fn GCQ_DEQUEUED_LAST var head | | 156 | .Fn GCQ_DEQUEUED_LAST var head |
157 | .Ft bool | | 157 | .Ft bool |
158 | .Fn GCQ_DEQUEUED_NEXT var current head start | | 158 | .Fn GCQ_DEQUEUED_NEXT var current head start |
159 | .Ft bool | | 159 | .Ft bool |
160 | .Fn GCQ_DEQUEUED_PREV var current head start | | 160 | .Fn GCQ_DEQUEUED_PREV var current head start |
161 | .Ft bool | | 161 | .Ft bool |
162 | .Fn GCQ_GOT_FIRST_TYPED tvar head type name | | 162 | .Fn GCQ_GOT_FIRST_TYPED tvar head type name |
163 | .Ft bool | | 163 | .Ft bool |
164 | .Fn GCQ_GOT_LAST_TYPED tvar head type name | | 164 | .Fn GCQ_GOT_LAST_TYPED tvar head type name |
165 | .Ft bool | | 165 | .Ft bool |
166 | .Fn GCQ_GOT_NEXT_TYPED tvar current head start type name | | 166 | .Fn GCQ_GOT_NEXT_TYPED tvar current head start type name |
167 | .Ft bool | | 167 | .Ft bool |
168 | .Fn GCQ_GOT_PREV_TYPED tvar current head start type name | | 168 | .Fn GCQ_GOT_PREV_TYPED tvar current head start type name |
169 | .Ft bool | | 169 | .Ft bool |
170 | .Fn GCQ_DEQUEUED_FIRST_TYPED tvar head type name | | 170 | .Fn GCQ_DEQUEUED_FIRST_TYPED tvar head type name |
171 | .Ft bool | | 171 | .Ft bool |
172 | .Fn GCQ_DEQUEUED_LAST_TYPED tvar head type name | | 172 | .Fn GCQ_DEQUEUED_LAST_TYPED tvar head type name |
173 | .Ft bool | | 173 | .Ft bool |
174 | .Fn GCQ_DEQUEUED_NEXT_TYPED tvar current head start type name | | 174 | .Fn GCQ_DEQUEUED_NEXT_TYPED tvar current head start type name |
175 | .Ft bool | | 175 | .Ft bool |
176 | .Fn GCQ_DEQUEUED_PREV_TYPED tvar current head start type name | | 176 | .Fn GCQ_DEQUEUED_PREV_TYPED tvar current head start type name |
177 | .Ft bool | | 177 | .Ft bool |
178 | .Fn GCQ_GOT_FIRST_COND var head cond | | 178 | .Fn GCQ_GOT_FIRST_COND var head cond |
179 | .Ft bool | | 179 | .Ft bool |
180 | .Fn GCQ_GOT_LAST_COND var head cond | | 180 | .Fn GCQ_GOT_LAST_COND var head cond |
181 | .Ft bool | | 181 | .Ft bool |
182 | .Fn GCQ_GOT_NEXT_COND var current head start cond | | 182 | .Fn GCQ_GOT_NEXT_COND var current head start cond |
183 | .Ft bool | | 183 | .Ft bool |
184 | .Fn GCQ_GOT_PREV_COND var current head start cond | | 184 | .Fn GCQ_GOT_PREV_COND var current head start cond |
185 | .Ft bool | | 185 | .Ft bool |
186 | .Fn GCQ_DEQUEUED_FIRST_COND var head cond | | 186 | .Fn GCQ_DEQUEUED_FIRST_COND var head cond |
187 | .Ft bool | | 187 | .Ft bool |
188 | .Fn GCQ_DEQUEUED_LAST_COND var head cond | | 188 | .Fn GCQ_DEQUEUED_LAST_COND var head cond |
189 | .Ft bool | | 189 | .Ft bool |
190 | .Fn GCQ_DEQUEUED_NEXT_COND var current head start cond | | 190 | .Fn GCQ_DEQUEUED_NEXT_COND var current head start cond |
191 | .Ft bool | | 191 | .Ft bool |
192 | .Fn GCQ_DEQUEUED_PREV_COND var current head start cond | | 192 | .Fn GCQ_DEQUEUED_PREV_COND var current head start cond |
193 | .Ft bool | | 193 | .Ft bool |
194 | .Fn GCQ_GOT_FIRST_COND_TYPED tvar head type name cond | | 194 | .Fn GCQ_GOT_FIRST_COND_TYPED tvar head type name cond |
195 | .Ft bool | | 195 | .Ft bool |
196 | .Fn GCQ_GOT_LAST_COND_TYPED tvar head type name cond | | 196 | .Fn GCQ_GOT_LAST_COND_TYPED tvar head type name cond |
197 | .Ft bool | | 197 | .Ft bool |
198 | .Fn GCQ_GOT_NEXT_COND_TYPED tvar current head start type name cond | | 198 | .Fn GCQ_GOT_NEXT_COND_TYPED tvar current head start type name cond |
199 | .Ft bool | | 199 | .Ft bool |
200 | .Fn GCQ_GOT_PREV_COND_TYPED tvar current head start type name cond | | 200 | .Fn GCQ_GOT_PREV_COND_TYPED tvar current head start type name cond |
201 | .Ft bool | | 201 | .Ft bool |
202 | .Fn GCQ_DEQUEUED_FIRST_COND_TYPED tvar head type name cond | | 202 | .Fn GCQ_DEQUEUED_FIRST_COND_TYPED tvar head type name cond |
203 | .Ft bool | | 203 | .Ft bool |
204 | .Fn GCQ_DEQUEUED_LAST_COND_TYPED tvar head type name cond | | 204 | .Fn GCQ_DEQUEUED_LAST_COND_TYPED tvar head type name cond |
205 | .Ft bool | | 205 | .Ft bool |
206 | .Fn GCQ_DEQUEUED_NEXT_COND_TYPED tvar current head start type name cond | | 206 | .Fn GCQ_DEQUEUED_NEXT_COND_TYPED tvar current head start type name cond |
207 | .Ft bool | | 207 | .Ft bool |
208 | .Fn GCQ_DEQUEUED_PREV_COND_TYPED tvar current head start type name cond | | 208 | .Fn GCQ_DEQUEUED_PREV_COND_TYPED tvar current head start type name cond |
209 | .Fn GCQ_FOREACH var head | | 209 | .Fn GCQ_FOREACH var head |
210 | .Fn GCQ_FOREACH_REV var head | | 210 | .Fn GCQ_FOREACH_REV var head |
211 | .Fn GCQ_FOREACH_NVAR var nvar head | | 211 | .Fn GCQ_FOREACH_NVAR var nvar head |
212 | .Fn GCQ_FOREACH_NVAR_REV var nvar head | | 212 | .Fn GCQ_FOREACH_NVAR_REV var nvar head |
213 | .Fn GCQ_FOREACH_RO var nvar head | | 213 | .Fn GCQ_FOREACH_RO var nvar head |
214 | .Fn GCQ_FOREACH_RO_REV var nvar head | | 214 | .Fn GCQ_FOREACH_RO_REV var nvar head |
215 | .Fn GCQ_FOREACH_DEQUEUED var nvar head | | 215 | .Fn GCQ_FOREACH_DEQUEUED var nvar head |
216 | .Fn GCQ_FOREACH_DEQUEUED_REV var nvar head | | 216 | .Fn GCQ_FOREACH_DEQUEUED_REV var nvar head |
217 | .Fn GCQ_FOREACH_TYPED var head tvar type name | | 217 | .Fn GCQ_FOREACH_TYPED var head tvar type name |
218 | .Fn GCQ_FOREACH_REV_TYPED var head tvar type name | | 218 | .Fn GCQ_FOREACH_REV_TYPED var head tvar type name |
219 | .Fn GCQ_FOREACH_NVAR_TYPED var nvar head tvar type name | | 219 | .Fn GCQ_FOREACH_NVAR_TYPED var nvar head tvar type name |
220 | .Fn GCQ_FOREACH_NVAR_REV_TYPED var nvar head tvar type name | | 220 | .Fn GCQ_FOREACH_NVAR_REV_TYPED var nvar head tvar type name |
221 | .Fn GCQ_FOREACH_RO_TYPED var nvar head tvar type name | | 221 | .Fn GCQ_FOREACH_RO_TYPED var nvar head tvar type name |
222 | .Fn GCQ_FOREACH_RO_REV_TYPED var nvar head tvar type name | | 222 | .Fn GCQ_FOREACH_RO_REV_TYPED var nvar head tvar type name |
223 | .Fn GCQ_FOREACH_DEQUEUED_TYPED var nvar head tvar type name | | 223 | .Fn GCQ_FOREACH_DEQUEUED_TYPED var nvar head tvar type name |
224 | .Fn GCQ_FOREACH_DEQUEUED_REV_TYPED var nvar head tvar type name | | 224 | .Fn GCQ_FOREACH_DEQUEUED_REV_TYPED var nvar head tvar type name |
225 | .Fn GCQ_FIND var head cond | | 225 | .Fn GCQ_FIND var head cond |
226 | .Fn GCQ_FIND_REV var head cond | | 226 | .Fn GCQ_FIND_REV var head cond |
227 | .Fn GCQ_FIND_TYPED var head tvar type name cond | | 227 | .Fn GCQ_FIND_TYPED var head tvar type name cond |
228 | .Fn GCQ_FIND_REV_TYPED var head tvar type name cond | | 228 | .Fn GCQ_FIND_REV_TYPED var head tvar type name cond |
229 | .Fn GCQ_ASSERT cond | | 229 | .Fn GCQ_ASSERT cond |
230 | .Sh DESCRIPTION | | 230 | .Sh DESCRIPTION |
231 | The generic circular queue is a doubly linked list designed for efficient | | 231 | The generic circular queue is a doubly linked list designed for efficient |
232 | merge operations and unconditional removal. | | 232 | merge operations and unconditional removal. |
233 | All basic operations can be performed with or without use of a separate head, | | 233 | All basic operations can be performed with or without use of a separate head, |
234 | allowing easy replacement of any pointers where efficient removal is desired. | | 234 | allowing easy replacement of any pointers where efficient removal is desired. |
235 | The meaning of the data type will not change; direct use and defined | | 235 | The meaning of the data type will not change; direct use and defined |
236 | operations can be mixed when convenient. | | 236 | operations can be mixed when convenient. |
237 | The basic type is: | | 237 | The basic type is: |
238 | .Bd -literal -offset indent | | 238 | .Bd -literal -offset indent |
239 | struct gcq { | | 239 | struct gcq { |
240 | struct gcq *q_next; | | 240 | struct gcq *q_next; |
241 | struct gcq *q_prev; | | 241 | struct gcq *q_prev; |
242 | }; | | 242 | }; |
243 | .Ed | | 243 | .Ed |
244 | .Pp | | 244 | .Pp |
245 | The structure must first be initialized such that the | | 245 | The structure must first be initialized such that the |
246 | .Va q_next | | 246 | .Va q_next |
247 | and | | 247 | and |
248 | .Va q_prev | | 248 | .Va q_prev |
249 | members point to the beginning of the | | 249 | members point to the beginning of the |
250 | .Vt struct gcq . | | 250 | .Vt struct gcq . |
251 | This can be done with | | 251 | This can be done with |
252 | .Fn gcq_init | | 252 | .Fn gcq_init |
253 | and | | 253 | and |
254 | .Fn gcq_init_head | | 254 | .Fn gcq_init_head |
255 | or with constant initializers | | 255 | or with constant initializers |
256 | .Fn GCQ_INIT | | 256 | .Fn GCQ_INIT |
257 | and | | 257 | and |
258 | .Fn GCQ_INIT_HEAD . | | 258 | .Fn GCQ_INIT_HEAD . |
259 | A | | 259 | A |
260 | .Vt struct gcq | | 260 | .Vt struct gcq |
261 | should | | 261 | should |
262 | .Em never | | 262 | .Em never |
263 | be given | | 263 | be given |
264 | .Dv NULL | | 264 | .Dv NULL |
265 | values. | | 265 | values. |
266 | .Pp | | 266 | .Pp |
267 | The structure containing the | | 267 | The structure containing the |
268 | .Vt struct gcq | | 268 | .Vt struct gcq |
269 | can be retrieved by pointer arithmetic in the | | 269 | can be retrieved by pointer arithmetic in the |
270 | .Fn GCQ_ITEM | | 270 | .Fn GCQ_ITEM |
271 | macro. | | 271 | macro. |
272 | List traversal normally requires knowledge of the list head to safely | | 272 | List traversal normally requires knowledge of the list head to safely |
273 | retrieve list items. | | 273 | retrieve list items. |
274 | .Pp | | 274 | .Pp |
275 | Capitalized operation names are macros and should be assumed to cause multiple | | 275 | Capitalized operation names are macros and should be assumed to cause multiple |
276 | evaluation of arguments. | | 276 | evaluation of arguments. |
277 | .Li TYPED | | 277 | .Li TYPED |
278 | variants of macros set a typed pointer variable instead of or in addition to | | 278 | variants of macros set a typed pointer variable instead of or in addition to |
279 | .Vt struct gcq * | | 279 | .Vt struct gcq * |
280 | arguments. | | 280 | arguments. |
281 | Additional type specific inlines and macros around some GCQ operations can be | | 281 | Additional type specific inlines and macros around some GCQ operations can be |
282 | useful. | | 282 | useful. |
283 | .Pp | | 283 | .Pp |
284 | A few assertions are provided when | | 284 | A few assertions are provided when |
285 | .Dv DIAGNOSTIC | | 285 | .Dv DIAGNOSTIC |
286 | is defined in the kernel or | | 286 | is defined in the kernel or |
287 | .Dv _DIAGNOSTIC | | 287 | .Dv _DIAGNOSTIC |
288 | is defined in userland. | | 288 | is defined in userland. |
289 | If | | 289 | If |
290 | .Dv GCQ_USE_ASSERT | | 290 | .Dv GCQ_USE_ASSERT |
291 | is defined prior to header inclusions | | 291 | is defined prior to header inclusions |
292 | then | | 292 | then |
293 | .Fn assert | | 293 | .Fn assert |
294 | will be used for assertions and | | 294 | will be used for assertions and |
295 | .Dv NDEBUG | | 295 | .Dv NDEBUG |
296 | can be used to turn them off. | | 296 | can be used to turn them off. |
297 | .Fn GCQ_ASSERT | | 297 | .Fn GCQ_ASSERT |
298 | is a wrapper around the used assertion function. | | 298 | is a wrapper around the used assertion function. |
299 | None of the operations accept | | 299 | None of the operations accept |
300 | .Dv NULL | | 300 | .Dv NULL |
301 | arguments, however this is not tested by assertion. | | 301 | arguments, however this is not tested by assertion. |
302 | .Pp | | 302 | .Pp |
303 | The head is separately named for type checking but contains only a | | 303 | The head is separately named for type checking but contains only a |
304 | .Vt struct gcq , | | 304 | .Vt struct gcq , |
305 | a pointer to which can be retrieved via | | 305 | a pointer to which can be retrieved via |
306 | .Fn gcq_hq . | | 306 | .Fn gcq_hq . |
307 | The reverse operation is performed by | | 307 | The reverse operation is performed by |
308 | .Fn gcq_head , | | 308 | .Fn gcq_head , |
309 | turning the supplied | | 309 | turning the supplied |
310 | .Vt struct gcq * | | 310 | .Vt struct gcq * |
311 | into | | 311 | into |
312 | .Vt struct gcq_head * . | | 312 | .Vt struct gcq_head * . |
313 | .Fn gcq_q | | 313 | .Fn gcq_q |
314 | returns its | | 314 | returns its |
315 | .Vt struct gcq * | | 315 | .Vt struct gcq * |
316 | argument and is used for type checking in | | 316 | argument and is used for type checking in |
317 | .Fn GCQ_ITEM . | | 317 | .Fn GCQ_ITEM . |
318 | There are no functions for retrieving the raw | | 318 | There are no functions for retrieving the raw |
319 | .Va q_prev | | 319 | .Va q_prev |
320 | and | | 320 | and |
321 | .Va q_next | | 321 | .Va q_next |
322 | pointers as these are usually clearer when used directly (if at all). | | 322 | pointers as these are usually clearer when used directly (if at all). |
323 | .Pp | | 323 | .Pp |
324 | .Fn gcq_remove | | 324 | .Fn gcq_remove |
325 | returns the element removed and is always a valid operation after | | 325 | returns the element removed and is always a valid operation after |
326 | initialization. | | 326 | initialization. |
327 | .Fn gcq_onlist | | 327 | .Fn gcq_onlist |
328 | returns | | 328 | returns |
329 | .Dv false | | 329 | .Dv false |
330 | if the structure links to itself and | | 330 | if the structure links to itself and |
331 | .Dv true | | 331 | .Dv true |
332 | otherwise. | | 332 | otherwise. |
333 | .Fn gcq_empty | | 333 | .Fn gcq_empty |
334 | is the negation of this operation performed on a head. | | 334 | is the negation of this operation performed on a head. |
335 | .Fn gcq_linked | | 335 | .Fn gcq_linked |
336 | tests if | | 336 | tests if |
337 | .Li "prev->q_next == next && next->q_prev == prev" . | | 337 | .Li "prev-\*[Gt]q_next == next \*[Am]\*[Am] next-\*[Gt]q_prev == prev" . |
338 | .Pp | | 338 | .Pp |
339 | .Fn gcq_tie | | 339 | .Fn gcq_tie |
340 | ties | | 340 | ties |
341 | .Va src | | 341 | .Va src |
342 | after | | 342 | after |
343 | .Va dst | | 343 | .Va dst |
344 | such that that if the old lists are DST, DST2 and SRC, SRC2, the new list is | | 344 | such that that if the old lists are DST, DST2 and SRC, SRC2, the new list is |
345 | DST, SRC, SRC2, DST2. | | 345 | DST, SRC, SRC2, DST2. |
346 | If | | 346 | If |
347 | .Va dst | | 347 | .Va dst |
348 | and | | 348 | and |
349 | .Va src | | 349 | .Va src |
350 | are on the same list then any elements between but not including | | 350 | are on the same list then any elements between but not including |
351 | .Va dst | | 351 | .Va dst |
352 | and | | 352 | and |
353 | .Va src | | 353 | .Va src |
354 | are cut from the list. | | 354 | are cut from the list. |
355 | If | | 355 | If |
356 | .Li dst == src | | 356 | .Li dst == src |
357 | then the result is the same as | | 357 | then the result is the same as |
358 | .Fn gcq_remove . | | 358 | .Fn gcq_remove . |
359 | .Fn gcq_tie | | 359 | .Fn gcq_tie |
360 | is equivalent to | | 360 | is equivalent to |
361 | .Fn gcq_tie_after | | 361 | .Fn gcq_tie_after |
362 | except that the latter must only be used with arguments on separate lists or | | 362 | except that the latter must only be used with arguments on separate lists or |
363 | not on lists and asserts that | | 363 | not on lists and asserts that |
364 | .Li "src != dst && dst->q_prev != src" . | | 364 | .Li "src != dst \*[Am]\*[Am] dst-\*[Gt]q_prev != src" . |
365 | .Fn gcq_tie_before | | 365 | .Fn gcq_tie_before |
366 | performs the same operation on | | 366 | performs the same operation on |
367 | .Li dst->q_prev . | | 367 | .Li dst-\*[Gt]q_prev . |
368 | .Pp | | 368 | .Pp |
369 | .Fn gcq_merge | | 369 | .Fn gcq_merge |
370 | moves any elements on list | | 370 | moves any elements on list |
371 | .Va src | | 371 | .Va src |
372 | (but not | | 372 | (but not |
373 | .Va src | | 373 | .Va src |
374 | itself) to list | | 374 | itself) to list |
375 | .Va dst . | | 375 | .Va dst . |
376 | It is normally used with two heads via | | 376 | It is normally used with two heads via |
377 | .Fn gcq_merge_head | | 377 | .Fn gcq_merge_head |
378 | or | | 378 | or |
379 | .Fn gcq_merge_tail . | | 379 | .Fn gcq_merge_tail . |
380 | If | | 380 | If |
381 | .Dv GCQ_UNCONDITIONAL_MERGE | | 381 | .Dv GCQ_UNCONDITIONAL_MERGE |
382 | is defined prior to header inclusion then the merge operations will always | | 382 | is defined prior to header inclusion then the merge operations will always |
383 | perform a tie then remove | | 383 | perform a tie then remove |
384 | .Va src | | 384 | .Va src |
385 | from the new list, which may reduce code size slightly. | | 385 | from the new list, which may reduce code size slightly. |
386 | .Pp | | 386 | .Pp |
387 | .Fn gcq_clear | | 387 | .Fn gcq_clear |
388 | initializes all elements currently linked with | | 388 | initializes all elements currently linked with |
389 | .Va q | | 389 | .Va q |
390 | and is normally used with a head as | | 390 | and is normally used with a head as |
391 | .Fn gcq_remove_all . | | 391 | .Fn gcq_remove_all . |
392 | .Pp | | 392 | .Pp |
393 | .Fn gcq_insert_after | | 393 | .Fn gcq_insert_after |
394 | and | | 394 | and |
395 | .Fn gcq_insert_before | | 395 | .Fn gcq_insert_before |
396 | are slightly optimized versions of | | 396 | are slightly optimized versions of |
397 | .Fn gcq_tie | | 397 | .Fn gcq_tie |
398 | for the case where | | 398 | for the case where |
399 | .Va off | | 399 | .Va off |
400 | is not on a list and include assertions to this effect, which are also useful | | 400 | is not on a list and include assertions to this effect, which are also useful |
401 | to detect missing initialization. | | 401 | to detect missing initialization. |
402 | .Fn gcq_insert_head | | 402 | .Fn gcq_insert_head |
403 | and | | 403 | and |
404 | .Fn gcq_insert_tail | | 404 | .Fn gcq_insert_tail |
405 | are the same operations applied to a head. | | 405 | are the same operations applied to a head. |
406 | .Pp | | 406 | .Pp |
407 | .Fn GCQ_GOT_FIRST | | 407 | .Fn GCQ_GOT_FIRST |
408 | and | | 408 | and |
409 | .Fn GCQ_GOT_LAST | | 409 | .Fn GCQ_GOT_LAST |
410 | set | | 410 | set |
411 | .Va var | | 411 | .Va var |
412 | to a pointer to the first or last | | 412 | to a pointer to the first or last |
413 | .Vt struct gcq | | 413 | .Vt struct gcq |
414 | in the list | | 414 | in the list |
415 | or | | 415 | or |
416 | .Dv NULL | | 416 | .Dv NULL |
417 | if the list is empty and return | | 417 | if the list is empty and return |
418 | .Dv false | | 418 | .Dv false |
419 | if empty and | | 419 | if empty and |
420 | .Dv true | | 420 | .Dv true |
421 | otherwise. | | 421 | otherwise. |
422 | The boolean return is to emphasise that it is not normally safe and useful to | | 422 | The boolean return is to emphasise that it is not normally safe and useful to |
423 | directly pass the raw first/next/etc. pointer to another function. | | 423 | directly pass the raw first/next/etc. pointer to another function. |
424 | The macros are written such that the | | 424 | The macros are written such that the |
425 | .Dv NULL | | 425 | .Dv NULL |
426 | values will be optimized out if not otherwise used. | | 426 | values will be optimized out if not otherwise used. |
427 | .Li DEQUEUED | | 427 | .Li DEQUEUED |
428 | variants also remove the member from the list. | | 428 | variants also remove the member from the list. |
429 | .Li COND | | 429 | .Li COND |
430 | variants take an additional condition that is evaluated when the macro would | | 430 | variants take an additional condition that is evaluated when the macro would |
431 | otherwise return | | 431 | otherwise return |
432 | .Dv true . | | 432 | .Dv true . |
433 | If the condition is false | | 433 | If the condition is false |
434 | .Va var | | 434 | .Va var |
435 | or | | 435 | or |
436 | .Va tvar | | 436 | .Va tvar |
437 | is set to | | 437 | is set to |
438 | .Dv NULL | | 438 | .Dv NULL |
439 | and no dequeue is performed. | | 439 | and no dequeue is performed. |
440 | .Pp | | 440 | .Pp |
441 | .Fn GCQ_GOT_NEXT | | 441 | .Fn GCQ_GOT_NEXT |
442 | and variants take pointers to the current position, list head, and starting | | 442 | and variants take pointers to the current position, list head, and starting |
443 | point as arguments. | | 443 | point as arguments. |
444 | The list head will be skipped when it is reached unless it is equal to the | | 444 | The list head will be skipped when it is reached unless it is equal to the |
445 | starting point; upon reaching the starting point | | 445 | starting point; upon reaching the starting point |
446 | .Va var | | 446 | .Va var |
447 | will be set to | | 447 | will be set to |
448 | .Dv NULL | | 448 | .Dv NULL |
449 | and the macro will return | | 449 | and the macro will return |
450 | .Dv false . | | 450 | .Dv false . |
451 | The next and prev macros also assert that | | 451 | The next and prev macros also assert that |
452 | .Va current | | 452 | .Va current |
453 | is on the list unless it is equal to | | 453 | is on the list unless it is equal to |
454 | .Va start . | | 454 | .Va start . |
455 | These macros are the only provided method for iterating through the list from | | 455 | These macros are the only provided method for iterating through the list from |
456 | an arbitrary point. | | 456 | an arbitrary point. |
457 | Traversal macros are only provided for list heads, however | | 457 | Traversal macros are only provided for list heads, however |
458 | .Fn gcq_head | | 458 | .Fn gcq_head |
459 | can be used to treat any item as a head. | | 459 | can be used to treat any item as a head. |
460 | .Pp | | 460 | .Pp |
461 | Foreach variants contain an embedded | | 461 | Foreach variants contain an embedded |
462 | .Li for | | 462 | .Li for |
463 | statement for iterating over a list. | | 463 | statement for iterating over a list. |
464 | Those containing | | 464 | Those containing |
465 | .Li REV | | 465 | .Li REV |
466 | use the | | 466 | use the |
467 | .Va q_prev | | 467 | .Va q_prev |
468 | pointer for traversal, others use | | 468 | pointer for traversal, others use |
469 | .Va q_next . | | 469 | .Va q_next . |
470 | The plain | | 470 | The plain |
471 | .Fn GCQ_FOREACH | | 471 | .Fn GCQ_FOREACH |
472 | uses a single variable. | | 472 | uses a single variable. |
473 | .Li NVAR | | 473 | .Li NVAR |
474 | variants save the next pointer at the top of the loop so that the current | | 474 | variants save the next pointer at the top of the loop so that the current |
475 | element can be removed without adjusting | | 475 | element can be removed without adjusting |
476 | .Va var . | | 476 | .Va var . |
477 | This is useful when | | 477 | This is useful when |
478 | .Va var | | 478 | .Va var |
479 | is passed to a function that might remove it but will not otherwise modify | | 479 | is passed to a function that might remove it but will not otherwise modify |
480 | the list. | | 480 | the list. |
481 | When the head is reached both | | 481 | When the head is reached both |
482 | .Va var | | 482 | .Va var |
483 | and | | 483 | and |
484 | .Va nvar | | 484 | .Va nvar |
485 | elements are left pointing to the list head. | | 485 | elements are left pointing to the list head. |
486 | .Li FOREACH | | 486 | .Li FOREACH |
487 | asserts that | | 487 | asserts that |
488 | .Va var , | | 488 | .Va var , |
489 | and | | 489 | and |
490 | .Li NVAR | | 490 | .Li NVAR |
491 | asserts that | | 491 | asserts that |
492 | .Va nvar | | 492 | .Va nvar |
493 | does not point to itself when starting the next loop. | | 493 | does not point to itself when starting the next loop. |
494 | This assertion takes place after the variable is tested against the head so | | 494 | This assertion takes place after the variable is tested against the head so |
495 | it is safe to remove all elements from the list. | | 495 | it is safe to remove all elements from the list. |
496 | .Li RO | | 496 | .Li RO |
497 | variants also set | | 497 | variants also set |
498 | .Va nvar | | 498 | .Va nvar |
499 | but assert that the two variables are linked at the end of each iteration. | | 499 | but assert that the two variables are linked at the end of each iteration. |
500 | This is useful when calling a function that is not supposed to remove the | | 500 | This is useful when calling a function that is not supposed to remove the |
501 | element passed. | | 501 | element passed. |
502 | .Li DEQUEUED | | 502 | .Li DEQUEUED |
503 | variants are like | | 503 | variants are like |
504 | .Li NVAR | | 504 | .Li NVAR |
505 | but remove each element before the code block is executed. | | 505 | but remove each element before the code block is executed. |
506 | .Li TYPED | | 506 | .Li TYPED |
507 | variants are equivalent to the untyped versions except that they take three | | 507 | variants are equivalent to the untyped versions except that they take three |
508 | extra arguments: a typed pointer, the type name, and the member name of the | | 508 | extra arguments: a typed pointer, the type name, and the member name of the |
509 | .Vt struct gcq | | 509 | .Vt struct gcq |
510 | used in this list. | | 510 | used in this list. |
511 | .Va tvar | | 511 | .Va tvar |
512 | is set to | | 512 | is set to |
513 | .Dv NULL | | 513 | .Dv NULL |
514 | when the head is reached. | | 514 | when the head is reached. |
515 | .Pp | | 515 | .Pp |
516 | .Fn GCQ_FIND | | 516 | .Fn GCQ_FIND |
517 | is a foreach loop that does nothing except break when the supplied condition | | 517 | is a foreach loop that does nothing except break when the supplied condition |
518 | is true. | | 518 | is true. |
519 | .Li REV | | 519 | .Li REV |
520 | and | | 520 | and |
521 | .Li TYPED | | 521 | .Li TYPED |
522 | variants are available. | | 522 | variants are available. |
523 | .\" .Sh EXAMPLES | | 523 | .\" .Sh EXAMPLES |
524 | .Sh SEE ALSO | | 524 | .Sh SEE ALSO |
525 | .Xr gcc 1 , | | 525 | .Xr gcc 1 , |
526 | .Xr assert 3 , | | | |
527 | .Xr _DIAGASSERT 3 , | | 526 | .Xr _DIAGASSERT 3 , |
| | | 527 | .Xr assert 3 , |
528 | .Xr queue 3 , | | 528 | .Xr queue 3 , |
529 | .Xr KASSERT 9 | | 529 | .Xr KASSERT 9 |
530 | .Sh HISTORY | | 530 | .Sh HISTORY |
531 | GCQ appeared in | | 531 | GCQ appeared in |
532 | .Nx 5.0 . | | 532 | .Nx 5.0 . |