STAILQ_INSERT_HEAD(3)

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

NAME

6       STAILQ_CONCAT,  STAILQ_EMPTY,  STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FORE‐
7       ACH,  STAILQ_HEAD,  STAILQ_HEAD_INITIALIZER,  STAILQ_INIT,   STAILQ_IN‐
8       SERT_AFTER,    STAILQ_INSERT_HEAD,   STAILQ_INSERT_TAIL,   STAILQ_NEXT,
9       STAILQ_REMOVE, STAILQ_REMOVE_HEAD, - implementation of a singly  linked
10       tail queue
11

SYNOPSIS

13       #include <sys/queue.h>
14
15       void STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);
16
17       int STAILQ_EMPTY(STAILQ_HEAD *head);
18
19       STAILQ_ENTRY(TYPE);
20
21       struct TYPE *STAILQ_FIRST(STAILQ_HEAD *head);
22
23       STAILQ_FOREACH(struct TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
24
25       STAILQ_HEAD(HEADNAME, TYPE);
26
27       STAILQ_HEAD STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
28
29       void STAILQ_INIT(STAILQ_HEAD *head);
30
31       void STAILQ_INSERT_AFTER(STAILQ_HEAD *head, struct TYPE *listelm,
32                       struct TYPE *elm, STAILQ_ENTRY NAME);
33
34       void STAILQ_INSERT_HEAD(STAILQ_HEAD *head, struct TYPE *elm,
35                       STAILQ_ENTRY NAME);
36
37       void STAILQ_INSERT_TAIL(STAILQ_HEAD *head, struct TYPE *elm,
38                       STAILQ_ENTRY NAME);
39
40       struct TYPE *STAILQ_NEXT(struct TYPE *elm, STAILQ_ENTRY NAME);
41
42       void STAILQ_REMOVE(STAILQ_HEAD *head, struct TYPE *elm, TYPE,
43                       STAILQ_ENTRY NAME);
44
45       void STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME);
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       A singly linked tail queue is headed by  a  structure  defined  by  the
56       STAILQ_HEAD()  macro.   This structure contains a pair of pointers, one
57       to the first element in the tail queue and the other to the  last  ele‐
58       ment  in  the  tail  queue.  The elements are singly linked for minimum
59       space and pointer manipulation overhead at the expense of O(n)  removal
60       for  arbitrary  elements.   New elements can be added to the tail queue
61       after an existing element, at the head of the tail queue, or at the end
62       of the tail queue.  A STAILQ_HEAD structure is declared as follows:
63
64           STAILQ_HEAD(HEADNAME, TYPE) head;
65
66       where  struct  HEADNAME is the structure to be defined, and struct TYPE
67       is the type of the elements to  be  linked  into  the  tail  queue.   A
68       pointer to the head of the tail queue can later be declared as:
69
70           struct HEADNAME *headp;
71
72       (The names head and headp are user selectable.)
73
74       The macro STAILQ_HEAD_INITIALIZER() evaluates to an initializer for the
75       tail queue head.
76
77       The macro STAILQ_CONCAT() concatenates the tail queue headed  by  head2
78       onto  the  end of the one headed by head1 removing all entries from the
79       former.
80
81       The macro STAILQ_EMPTY() evaluates to true if there are no items on the
82       tail queue.
83
84       The  macro  STAILQ_ENTRY()  declares a structure that connects the ele‐
85       ments in the tail queue.
86
87       The macro STAILQ_FIRST() returns the first item on the  tail  queue  or
88       NULL if the tail queue is empty.
89
90       The  macro STAILQ_FOREACH() traverses the tail queue referenced by head
91       in the forward direction, assigning each element in turn to var.
92
93       The macro STAILQ_INIT() initializes the tail queue referenced by head.
94
95       The macro STAILQ_INSERT_HEAD() inserts the new element elm at the  head
96       of the tail queue.
97
98       The  macro  STAILQ_INSERT_TAIL() inserts the new element elm at the end
99       of the tail queue.
100
101       The macro STAILQ_INSERT_AFTER() inserts the new element elm  after  the
102       element listelm.
103
104       The  macro  STAILQ_NEXT()  returns  the next item on the tail queue, or
105       NULL this item is the last.
106
107       The macro STAILQ_REMOVE_HEAD() removes the element at the head  of  the
108       tail  queue.   For  optimum efficiency, elements being removed from the
109       head of the tail queue should use this macro explicitly rather than the
110       generic STAILQ_REMOVE() macro.
111
112       The macro STAILQ_REMOVE() removes the element elm from the tail queue.
113

RETURN VALUE

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

CONFORMING TO

125       Not in POSIX.1, POSIX.1-2001 or  POSIX.1-2008.   Present  on  the  BSDs
126       (STAILQ macros first appeared in 4.4BSD).
127

BUGS

129       The  macro  STAILQ_FOREACH()  doesn't  allow var to be removed or freed
130       within the loop, as it would interfere with the traversal.   The  macro
131       STAILQ_FOREACH_SAFE(),  which is present on the BSDs but is not present
132       in glibc, fixes this limitation by allowing var to  safely  be  removed
133       from  the  list and freed from within the loop without interfering with
134       the traversal.
135

EXAMPLES

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

COLOPHON

200       This page is part of release 5.10 of the Linux  man-pages  project.   A
201       description  of  the project, information about reporting bugs, and the
202       latest    version    of    this    page,    can     be     found     at
203       https://www.kernel.org/doc/man-pages/.
204
205
206
207GNU                               2020-10-21                         STAILQ(3)