Deleted Added
sdiff udiff text old ( 1639 ) new ( 13698 )
full compact
queue.3 (1639) queue.3 (13698)
1.\" Copyright (c) 1993
2.\" The Regents of the University of California. All rights reserved.
3.\"
4.\" Redistribution and use in source and binary forms, with or without
5.\" modification, are permitted provided that the following conditions
6.\" are met:
7.\" 1. Redistributions of source code must retain the above copyright
8.\" notice, this list of conditions and the following disclaimer.

--- 25 unchanged lines hidden (view full) ---

34.Dd "January 24, 1994"
35.Dt QUEUE 3
36.Os BSD 4
37.Sh NAME
38.Nm LIST_ENTRY ,
39.Nm LIST_HEAD ,
40.Nm LIST_INIT ,
41.Nm LIST_INSERT_AFTER ,
1.\" Copyright (c) 1993
2.\" The Regents of the University of California. All rights reserved.
3.\"
4.\" Redistribution and use in source and binary forms, with or without
5.\" modification, are permitted provided that the following conditions
6.\" are met:
7.\" 1. Redistributions of source code must retain the above copyright
8.\" notice, this list of conditions and the following disclaimer.

--- 25 unchanged lines hidden (view full) ---

34.Dd "January 24, 1994"
35.Dt QUEUE 3
36.Os BSD 4
37.Sh NAME
38.Nm LIST_ENTRY ,
39.Nm LIST_HEAD ,
40.Nm LIST_INIT ,
41.Nm LIST_INSERT_AFTER ,
42.Nm LIST_INSERT_BEFORE ,
42.Nm LIST_INSERT_HEAD ,
43.Nm LIST_REMOVE ,
44.Nm TAILQ_ENTRY ,
45.Nm TAILQ_HEAD ,
46.Nm TAILQ_INIT ,
47.Nm TAILQ_INSERT_AFTER ,
43.Nm LIST_INSERT_HEAD ,
44.Nm LIST_REMOVE ,
45.Nm TAILQ_ENTRY ,
46.Nm TAILQ_HEAD ,
47.Nm TAILQ_INIT ,
48.Nm TAILQ_INSERT_AFTER ,
49.Nm TAILQ_INSERT_BEFORE ,
48.Nm TAILQ_INSERT_HEAD ,
49.Nm TAILQ_INSERT_TAIL ,
50.Nm TAILQ_REMOVE ,
51.Nm CIRCLEQ_ENTRY ,
52.Nm CIRCLEQ_HEAD ,
53.Nm CIRCLEQ_INIT ,
54.Nm CIRCLEQ_INSERT_AFTER ,
55.Nm CIRCLEQ_INSERT_BEFORE ,
56.Nm CIRCLEQ_INSERT_HEAD ,
57.Nm CIRCLEQ_INSERT_TAIL ,
58.Nm CIRCLEQ_REMOVE
59.Nd implementations of lists, tail queues, and circular queues
60.Sh SYNOPSIS
61.Fd #include <sys/queue.h>
62.sp
63.Fn LIST_ENTRY "TYPE"
64.Fn LIST_HEAD "HEADNAME" "TYPE"
65.Fn LIST_INIT "LIST_HEAD *head"
66.Fn LIST_INSERT_AFTER "LIST_ENTRY *listelm" "TYPE *elm" "LIST_ENTRY NAME"
50.Nm TAILQ_INSERT_HEAD ,
51.Nm TAILQ_INSERT_TAIL ,
52.Nm TAILQ_REMOVE ,
53.Nm CIRCLEQ_ENTRY ,
54.Nm CIRCLEQ_HEAD ,
55.Nm CIRCLEQ_INIT ,
56.Nm CIRCLEQ_INSERT_AFTER ,
57.Nm CIRCLEQ_INSERT_BEFORE ,
58.Nm CIRCLEQ_INSERT_HEAD ,
59.Nm CIRCLEQ_INSERT_TAIL ,
60.Nm CIRCLEQ_REMOVE
61.Nd implementations of lists, tail queues, and circular queues
62.Sh SYNOPSIS
63.Fd #include <sys/queue.h>
64.sp
65.Fn LIST_ENTRY "TYPE"
66.Fn LIST_HEAD "HEADNAME" "TYPE"
67.Fn LIST_INIT "LIST_HEAD *head"
68.Fn LIST_INSERT_AFTER "LIST_ENTRY *listelm" "TYPE *elm" "LIST_ENTRY NAME"
69.Fn LIST_INSERT_BEFORE "LIST_ENTRY *listelm" "TYPE *elm" "LIST_ENTRY NAME"
67.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
68.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
69.sp
70.Fn TAILQ_ENTRY "TYPE"
71.Fn TAILQ_HEAD "HEADNAME" "TYPE"
72.Fn TAILQ_INIT "TAILQ_HEAD *head"
73.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
70.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
71.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
72.sp
73.Fn TAILQ_ENTRY "TYPE"
74.Fn TAILQ_HEAD "HEADNAME" "TYPE"
75.Fn TAILQ_INIT "TAILQ_HEAD *head"
76.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
77.Fn TAILQ_INSERT_BEFORE "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
74.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
75.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
76.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
77.sp
78.Fn CIRCLEQ_ENTRY "TYPE"
79.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
80.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
81.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"

--- 6 unchanged lines hidden (view full) ---

88lists, tail queues, and circular queues.
89All three structures support the following functionality:
90.Bl -enum -compact -offset indent
91.It
92Insertion of a new entry at the head of the list.
93.It
94Insertion of a new entry after any element in the list.
95.It
78.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
79.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
80.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
81.sp
82.Fn CIRCLEQ_ENTRY "TYPE"
83.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
84.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
85.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"

--- 6 unchanged lines hidden (view full) ---

92lists, tail queues, and circular queues.
93All three structures support the following functionality:
94.Bl -enum -compact -offset indent
95.It
96Insertion of a new entry at the head of the list.
97.It
98Insertion of a new entry after any element in the list.
99.It
100Insertion of a new entry before any element in the list.
101.It
96Removal of any entry in the list.
97.It
98Forward traversal through the list.
99.El
100.Pp
101Lists are the simplest of the three data structures and support
102only the above functionality.
103.Pp

--- 13 unchanged lines hidden (view full) ---

117than lists.
118.El
119.Pp
120Circular queues add the following functionality:
121.Bl -enum -compact -offset indent
122.It
123Entries can be added at the end of a list.
124.It
102Removal of any entry in the list.
103.It
104Forward traversal through the list.
105.El
106.Pp
107Lists are the simplest of the three data structures and support
108only the above functionality.
109.Pp

--- 13 unchanged lines hidden (view full) ---

123than lists.
124.El
125.Pp
126Circular queues add the following functionality:
127.Bl -enum -compact -offset indent
128.It
129Entries can be added at the end of a list.
130.It
125Entries can be added before another entry.
126.It
127They may be traversed backwards, from tail to head.
128.El
129However:
130.Bl -enum -compact -offset indent
131.It
132All list insertions and removals must specify the head of the list.
133.It
134Each head entry requires two pointers rather than one.

--- 76 unchanged lines hidden (view full) ---

211The macro
212.Nm LIST_INSERT_AFTER
213inserts the new element
214.Fa elm
215after the element
216.Fa listelm .
217.Pp
218The macro
131They may be traversed backwards, from tail to head.
132.El
133However:
134.Bl -enum -compact -offset indent
135.It
136All list insertions and removals must specify the head of the list.
137.It
138Each head entry requires two pointers rather than one.

--- 76 unchanged lines hidden (view full) ---

215The macro
216.Nm LIST_INSERT_AFTER
217inserts the new element
218.Fa elm
219after the element
220.Fa listelm .
221.Pp
222The macro
223.Nm LIST_INSERT_BEFORE
224inserts the new element
225.Fa elm
226before the element
227.Fa listelm .
228.Pp
229The macro
219.Nm LIST_REMOVE
220removes the element
221.Fa elm
222from the list.
223.Sh LIST EXAMPLE
224.Bd -literal
225LIST_HEAD(listhead, entry) head;
226struct listhead *headp; /* List head. */
227struct entry {
228 ...
229 LIST_ENTRY(entry) entries; /* List. */
230 ...
230.Nm LIST_REMOVE
231removes the element
232.Fa elm
233from the list.
234.Sh LIST EXAMPLE
235.Bd -literal
236LIST_HEAD(listhead, entry) head;
237struct listhead *headp; /* List head. */
238struct entry {
239 ...
240 LIST_ENTRY(entry) entries; /* List. */
241 ...
231} *n1, *n2, *np;
242} *n1, *n2, *n3, *np;
232
233LIST_INIT(&head); /* Initialize the list. */
234
235n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
236LIST_INSERT_HEAD(&head, n1, entries);
237
238n2 = malloc(sizeof(struct entry)); /* Insert after. */
239LIST_INSERT_AFTER(n1, n2, entries);
243
244LIST_INIT(&head); /* Initialize the list. */
245
246n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
247LIST_INSERT_HEAD(&head, n1, entries);
248
249n2 = malloc(sizeof(struct entry)); /* Insert after. */
250LIST_INSERT_AFTER(n1, n2, entries);
251
252n3 = malloc(sizeof(struct entry)); /* Insert before. */
253LIST_INSERT_BEFORE(n2, n3, entries);
254
255LIST_REMOVE(n2, entries); /* Deletion. */
256free(n2);
257
240 /* Forward traversal. */
241for (np = head.lh_first; np != NULL; np = np->entries.le_next)
242 np-> ...
243
258 /* Forward traversal. */
259for (np = head.lh_first; np != NULL; np = np->entries.le_next)
260 np-> ...
261
244while (head.lh_first != NULL) /* Delete. */
245 LIST_REMOVE(head.lh_first, entries);
262while (head.lh_first != NULL) { /* List Deletion. */
263 n1 = head.lh_first;
264 LIST_REMOVE(n1, entries);
265 free(n1);
266}
267
268n1 = head.lh_first; /* Faster List Delete. */
269while (n1 != NULL) {
270 n2 = n1->entires.le_next;
271 free(n1);
272 n1 = n2;
273}
274LIST_INIT(&head);
275
246.Ed
247.Sh TAIL QUEUES
248A tail queue is headed by a structure defined by the
249.Nm TAILQ_HEAD
250macro.
251This structure contains a pair of pointers,
252one to the first element in the tail queue and the other to
253the last element in the tail queue.

--- 49 unchanged lines hidden (view full) ---

303The macro
304.Nm TAILQ_INSERT_AFTER
305inserts the new element
306.Fa elm
307after the element
308.Fa listelm .
309.Pp
310The macro
276.Ed
277.Sh TAIL QUEUES
278A tail queue is headed by a structure defined by the
279.Nm TAILQ_HEAD
280macro.
281This structure contains a pair of pointers,
282one to the first element in the tail queue and the other to
283the last element in the tail queue.

--- 49 unchanged lines hidden (view full) ---

333The macro
334.Nm TAILQ_INSERT_AFTER
335inserts the new element
336.Fa elm
337after the element
338.Fa listelm .
339.Pp
340The macro
341.Nm TAILQ_INSERT_BEFORE
342inserts the new element
343.Fa elm
344before the element
345.Fa listelm .
346.Pp
347The macro
311.Nm TAILQ_REMOVE
312removes the element
313.Fa elm
314from the tail queue.
315.Sh TAIL QUEUE EXAMPLE
316.Bd -literal
317TAILQ_HEAD(tailhead, entry) head;
318struct tailhead *headp; /* Tail queue head. */
319struct entry {
320 ...
321 TAILQ_ENTRY(entry) entries; /* Tail queue. */
322 ...
348.Nm TAILQ_REMOVE
349removes the element
350.Fa elm
351from the tail queue.
352.Sh TAIL QUEUE EXAMPLE
353.Bd -literal
354TAILQ_HEAD(tailhead, entry) head;
355struct tailhead *headp; /* Tail queue head. */
356struct entry {
357 ...
358 TAILQ_ENTRY(entry) entries; /* Tail queue. */
359 ...
323} *n1, *n2, *np;
360} *n1, *n2, *n3, *np;
324
325TAILQ_INIT(&head); /* Initialize the queue. */
326
327n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
328TAILQ_INSERT_HEAD(&head, n1, entries);
329
330n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
331TAILQ_INSERT_TAIL(&head, n1, entries);
332
333n2 = malloc(sizeof(struct entry)); /* Insert after. */
334TAILQ_INSERT_AFTER(&head, n1, n2, entries);
361
362TAILQ_INIT(&head); /* Initialize the queue. */
363
364n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
365TAILQ_INSERT_HEAD(&head, n1, entries);
366
367n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
368TAILQ_INSERT_TAIL(&head, n1, entries);
369
370n2 = malloc(sizeof(struct entry)); /* Insert after. */
371TAILQ_INSERT_AFTER(&head, n1, n2, entries);
372
373n3 = malloc(sizeof(struct entry)); /* Insert before. */
374TAILQ_INSERT_BEFORE(&head, n2, n3, entries);
375
376TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
377free(n2);
335 /* Forward traversal. */
336for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
337 np-> ...
378 /* Forward traversal. */
379for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
380 np-> ...
338 /* Delete. */
339while (head.tqh_first != NULL)
381 /* TailQ Deletion. */
382while (head.tqh_first != NULL) {
383 n1 = head.tqh_first;
340 TAILQ_REMOVE(&head, head.tqh_first, entries);
384 TAILQ_REMOVE(&head, head.tqh_first, entries);
385 free(n1);
386}
387 /* Faster TailQ Deletion. */
388n1 = head.tqh_first;
389while (n1 != NULL) {
390 n2 = n1->entries.tqe_next;
391 free(n1);
392 n1 = n2;
393}
394TAILQ_INIT(&head);
341.Ed
342.Sh CIRCULAR QUEUES
343A circular queue is headed by a structure defined by the
344.Nm CIRCLEQ_HEAD
345macro.
346This structure contains a pair of pointers,
347one to the first element in the circular queue and the other to the
348last element in the circular queue.

--- 84 unchanged lines hidden (view full) ---

433n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
434CIRCLEQ_INSERT_TAIL(&head, n1, entries);
435
436n2 = malloc(sizeof(struct entry)); /* Insert after. */
437CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
438
439n2 = malloc(sizeof(struct entry)); /* Insert before. */
440CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
395.Ed
396.Sh CIRCULAR QUEUES
397A circular queue is headed by a structure defined by the
398.Nm CIRCLEQ_HEAD
399macro.
400This structure contains a pair of pointers,
401one to the first element in the circular queue and the other to the
402last element in the circular queue.

--- 84 unchanged lines hidden (view full) ---

487n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
488CIRCLEQ_INSERT_TAIL(&head, n1, entries);
489
490n2 = malloc(sizeof(struct entry)); /* Insert after. */
491CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
492
493n2 = malloc(sizeof(struct entry)); /* Insert before. */
494CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
495
496CIRCLEQ_REMOVE(&head, n1, entries); /* Deletion. */
497free(n1);
441 /* Forward traversal. */
442for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
443 np-> ...
444 /* Reverse traversal. */
445for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
446 np-> ...
498 /* Forward traversal. */
499for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
500 np-> ...
501 /* Reverse traversal. */
502for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
503 np-> ...
447 /* Delete. */
448while (head.cqh_first != (void *)&head)
504 /* CircleQ Deletion. */
505while (head.cqh_first != (void *)&head) {
506 n1 = head.cqh_first;
449 CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
507 CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
508 free(n1);
509}
510 /* Faster CircleQ Deletion. */
511n1 = head.cqh_first;
512while (n1 != (void *)&head) {
513 n2 = n1->entries.cqh_next;
514 free(n1);
515 n1 = n2;
516}
517CIRCLEQ_INIT(&head);
450.Ed
451.Sh HISTORY
452The
453.Nm queue
454functions first appeared in 4.4BSD.
518.Ed
519.Sh HISTORY
520The
521.Nm queue
522functions first appeared in 4.4BSD.