1STAILQ(3)                  Linux Programmer's Manual                 STAILQ(3)
2
3
4

NAME

6       SIMPLEQ_EMPTY,   SIMPLEQ_ENTRY,  SIMPLEQ_FIRST,  SIMPLEQ_FOREACH,  SIM‐
7       PLEQ_HEAD, SIMPLEQ_HEAD_INITIALIZER,  SIMPLEQ_INIT,  SIMPLEQ_INSERT_AF‐
8       TER,   SIMPLEQ_INSERT_HEAD,   SIMPLEQ_INSERT_TAIL,  SIMPLEQ_NEXT,  SIM‐
9       PLEQ_REMOVE,    SIMPLEQ_REMOVE_HEAD,    STAILQ_CONCAT,    STAILQ_EMPTY,
10       STAILQ_ENTRY,      STAILQ_FIRST,      STAILQ_FOREACH,      STAILQ_HEAD,
11       STAILQ_HEAD_INITIALIZER, STAILQ_INIT,  STAILQ_INSERT_AFTER,  STAILQ_IN‐
12       SERT_HEAD,  STAILQ_INSERT_TAIL,  STAILQ_NEXT, STAILQ_REMOVE, STAILQ_RE‐
13       MOVE_HEAD, - implementation of a singly linked tail queue
14

SYNOPSIS

16       #include <sys/queue.h>
17
18       STAILQ_ENTRY(TYPE);
19
20       STAILQ_HEAD(HEADNAME, TYPE);
21       STAILQ_HEAD STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
22       void STAILQ_INIT(STAILQ_HEAD *head);
23
24       int STAILQ_EMPTY(STAILQ_HEAD *head);
25
26       void STAILQ_INSERT_HEAD(STAILQ_HEAD *head,
27                                struct TYPE *elm, STAILQ_ENTRY NAME);
28       void STAILQ_INSERT_TAIL(STAILQ_HEAD *head,
29                                struct TYPE *elm, STAILQ_ENTRY NAME);
30       void STAILQ_INSERT_AFTER(STAILQ_HEAD *head, struct TYPE *listelm,
31                                struct TYPE *elm, STAILQ_ENTRY NAME);
32
33       struct TYPE *STAILQ_FIRST(STAILQ_HEAD *head);
34       struct TYPE *STAILQ_NEXT(struct TYPE *elm, STAILQ_ENTRY NAME);
35
36       STAILQ_FOREACH(struct TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
37
38       void STAILQ_REMOVE(STAILQ_HEAD *head, struct TYPE *elm, TYPE,
39                                STAILQ_ENTRY NAME);
40       void STAILQ_REMOVE_HEAD(STAILQ_HEAD *head,
41                                STAILQ_ENTRY NAME);
42
43       void STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);
44       Note: Identical macros prefixed with SIMPLEQ instead of  STAILQ  exist;
45       see NOTES.
46

DESCRIPTION

48       These macros define and operate on singly linked tail queues.
49
50       In the macro definitions, TYPE is the name of a user-defined structure,
51       that must contain a field of type STAILQ_ENTRY, named NAME.  The  argu‐
52       ment  HEADNAME is the name of a user-defined structure that must be de‐
53       clared using the macro STAILQ_HEAD().
54
55   Creation
56       A singly linked tail queue is headed by  a  structure  defined  by  the
57       STAILQ_HEAD()  macro.   This structure contains a pair of pointers, one
58       to the first element in the tail queue and the other to the  last  ele‐
59       ment  in  the  tail  queue.  The elements are singly linked for minimum
60       space and pointer manipulation overhead at the expense of O(n)  removal
61       for  arbitrary  elements.   New elements can be added to the tail queue
62       after an existing element, at the head of the tail queue, or at the end
63       of the tail queue.  A STAILQ_HEAD structure is declared as follows:
64
65           STAILQ_HEAD(HEADNAME, TYPE) head;
66
67       where  struct  HEADNAME is the structure to be defined, and struct TYPE
68       is the type of the elements to  be  linked  into  the  tail  queue.   A
69       pointer to the head of the tail queue can later be declared as:
70
71           struct HEADNAME *headp;
72
73       (The names head and headp are user selectable.)
74
75       STAILQ_ENTRY()  declares  a structure that connects the elements in the
76       tail queue.
77
78       STAILQ_HEAD_INITIALIZER() evaluates to  an  initializer  for  the  tail
79       queue head.
80
81       STAILQ_INIT() initializes the tail queue referenced by head.
82
83       STAILQ_EMPTY()  evaluates  to  true  if  there are no items on the tail
84       queue.
85
86   Insertion
87       STAILQ_INSERT_HEAD() inserts the new element elm at  the  head  of  the
88       tail queue.
89
90       STAILQ_INSERT_TAIL() inserts the new element elm at the end of the tail
91       queue.
92
93       STAILQ_INSERT_AFTER() inserts the new element  elm  after  the  element
94       listelm.
95
96   Traversal
97       STAILQ_FIRST()  returns the first item on the tail queue or NULL if the
98       tail queue is empty.
99
100       STAILQ_NEXT() returns the next item on the tail  queue,  or  NULL  this
101       item is the last.
102
103       STAILQ_FOREACH()  traverses  the  tail  queue referenced by head in the
104       forward direction, assigning each element in turn to var.
105
106   Removal
107       STAILQ_REMOVE() removes the element elm from the tail queue.
108
109       STAILQ_REMOVE_HEAD() removes the element at the head of the tail queue.
110       For  optimum  efficiency,  elements  being removed from the head of the
111       tail queue should use this macro explicitly  rather  than  the  generic
112       STAILQ_REMOVE() macro.
113
114   Other features
115       STAILQ_CONCAT()  concatenates  the  tail queue headed by head2 onto the
116       end of the one headed by head1 removing all entries from the former.
117

RETURN VALUE

119       STAILQ_EMPTY() returns nonzero if the queue is empty, and zero  if  the
120       queue contains at least one entry.
121
122       STAILQ_FIRST(), and STAILQ_NEXT() return a pointer to the first or next
123       TYPE structure, respectively.
124
125       STAILQ_HEAD_INITIALIZER() returns an initializer that can  be  assigned
126       to the queue head.
127

CONFORMING TO

129       Not  in  POSIX.1,  POSIX.1-2001,  or POSIX.1-2008.  Present on the BSDs
130       (STAILQ macros first appeared in 4.4BSD).
131

NOTES

133       Some BSDs provide SIMPLEQ instead of STAILQ.  They are  identical,  but
134       for  historical  reasons they were named differently on different BSDs.
135       STAILQ originated on FreeBSD, and SIMPLEQ originated  on  NetBSD.   For
136       compatibility reasons, some systems provide both sets of macros.  Glibc
137       provides both STAILQ and SIMPLEQ, which  are  identical  except  for  a
138       missing SIMPLEQ equivalent to STAILQ_CONCAT().
139

BUGS

141       STAILQ_FOREACH()  doesn't  allow  var to be removed or freed within the
142       loop, as it would interfere with the traversal.  STAILQ_FOREACH_SAFE(),
143       which  is  present  on the BSDs but is not present in glibc, fixes this
144       limitation by allowing var to safely be removed from the list and freed
145       from within the loop without interfering with the traversal.
146

EXAMPLES

148       #include <stddef.h>
149       #include <stdio.h>
150       #include <stdlib.h>
151       #include <sys/queue.h>
152
153       struct entry {
154           int data;
155           STAILQ_ENTRY(entry) entries;        /* Singly linked tail queue */
156       };
157
158       STAILQ_HEAD(stailhead, entry);
159
160       int
161       main(void)
162       {
163           struct entry *n1, *n2, *n3, *np;
164           struct stailhead head;                  /* Singly linked tail queue
165                                                      head */
166
167           STAILQ_INIT(&head);                     /* Initialize the queue */
168
169           n1 = malloc(sizeof(struct entry));      /* Insert at the head */
170           STAILQ_INSERT_HEAD(&head, n1, entries);
171
172           n1 = malloc(sizeof(struct entry));      /* Insert at the tail */
173           STAILQ_INSERT_TAIL(&head, n1, entries);
174
175           n2 = malloc(sizeof(struct entry));      /* Insert after */
176           STAILQ_INSERT_AFTER(&head, n1, n2, entries);
177
178           STAILQ_REMOVE(&head, n2, entry, entries); /* Deletion */
179           free(n2);
180
181           n3 = STAILQ_FIRST(&head);
182           STAILQ_REMOVE_HEAD(&head, entries);     /* Deletion from the head */
183           free(n3);
184
185           n1 = STAILQ_FIRST(&head);
186           n1->data = 0;
187           for (int i = 1; i < 5; i++) {
188               n1 = malloc(sizeof(struct entry));
189               STAILQ_INSERT_HEAD(&head, n1, entries);
190               n1->data = i;
191           }
192                                                   /* Forward traversal */
193           STAILQ_FOREACH(np, &head, entries)
194               printf("%i\n", np->data);
195                                                   /* TailQ deletion */
196           n1 = STAILQ_FIRST(&head);
197           while (n1 != NULL) {
198               n2 = STAILQ_NEXT(n1, entries);
199               free(n1);
200               n1 = n2;
201           }
202           STAILQ_INIT(&head);
203
204           exit(EXIT_SUCCESS);
205       }
206

SEE ALSO

208       insque(3), queue(7)
209

COLOPHON

211       This  page  is  part of release 5.13 of the Linux man-pages project.  A
212       description of the project, information about reporting bugs,  and  the
213       latest     version     of     this    page,    can    be    found    at
214       https://www.kernel.org/doc/man-pages/.
215
216
217
218GNU                               2021-08-27                         STAILQ(3)
Impressum