1INSQUE(3) Linux Programmer's Manual INSQUE(3)
2
6 insque, remque - insert/remove an item from a queue
7
9 #include <search.h>
10 void insque(void *elem, void *prev);
12 void remque(void *elem);
14 Feature Test Macro Requirements for glibc (see feature_test_macros(7)):
16 insque(), remque():
18 _XOPEN_SOURCE >= 500
19 || /* Glibc since 2.19: */ _DEFAULT_SOURCE
20 || /* Glibc versions <= 2.19: */ _SVID_SOURCE
21
23 The insque() and remque() functions manipulate doubly linked lists.
24 Each element in the list is a structure of which the first two elements
25 are a forward and a backward pointer. The linked list may be linear
26 (i.e., NULL forward pointer at the end of the list and NULL backward
27 pointer at the start of the list) or circular.
28 The insque() function inserts the element pointed to by elem immedi‐
30 ately after the element pointed to by prev.
31 If the list is linear, then the call insque(elem, NULL) can be used to
33 insert the initial list element, and the call sets the forward and
34 backward pointers of elem to NULL.
35 If the list is circular, the caller should ensure that the forward and
37 backward pointers of the first element are initialized to point to that
38 element, and the prev argument of the insque() call should also point
39 to the element.
40 The remque() function removes the element pointed to by elem from the
42 doubly linked list.
43
45 For an explanation of the terms used in this section, see at‐
46 tributes(7).
47 ┌───────────────────┬───────────────┬─────────┐
49 │Interface │ Attribute │ Value │
50 ├───────────────────┼───────────────┼─────────┤
51 │insque(), remque() │ Thread safety │ MT-Safe │
52 └───────────────────┴───────────────┴─────────┘
53
55 POSIX.1-2001, POSIX.1-2008.
56
58 On ancient systems, the arguments of these functions were of type
59 struct qelem *, defined as:
60 struct qelem {
62 struct qelem *q_forw;
63 struct qelem *q_back;
64 char q_data[1];
65 };
66 This is still what you will get if _GNU_SOURCE is defined before in‐
68 cluding <search.h>.
69 The location of the prototypes for these functions differs among sev‐
71 eral versions of UNIX. The above is the POSIX version. Some systems
72 place them in <string.h>.
73
75 In glibc 2.4 and earlier, it was not possible to specify prev as NULL.
76 Consequently, to build a linear list, the caller had to build a list
77 using an initial call that contained the first two elements of the
78 list, with the forward and backward pointers in each element suitably
79 initialized.
80
82 The program below demonstrates the use of insque(). Here is an example
83 run of the program:
84 $ ./a.out -c a b c
86 Traversing completed list:
87 a
88 b
89 c
90 That was a circular list
91 Program source
93 #include <stdio.h>
95 #include <stdlib.h>
96 #include <unistd.h>
97 #include <search.h>
98 struct element {
100 struct element *forward;
101 struct element *backward;
102 char *name;
103 };
104 static struct element *
106 new_element(void)
107 {
108 struct element *e = malloc(sizeof(*e));
109 if (e == NULL) {
110 fprintf(stderr, "malloc() failed\n");
111 exit(EXIT_FAILURE);
112 }
113 return e;
115 }
116 int
118 main(int argc, char *argv[])
119 {
120 struct element *first, *elem, *prev;
121 int circular, opt, errfnd;
122 /* The "-c" command-line option can be used to specify that the
124 list is circular */
125 errfnd = 0;
127 circular = 0;
128 while ((opt = getopt(argc, argv, "c")) != -1) {
129 switch (opt) {
130 case 'c':
131 circular = 1;
132 break;
133 default:
134 errfnd = 1;
135 break;
136 }
137 }
138 if (errfnd || optind >= argc) {
140 fprintf(stderr, "Usage: %s [-c] string...\n", argv[0]);
141 exit(EXIT_FAILURE);
142 }
143 /* Create first element and place it in the linked list */
145 elem = new_element();
147 first = elem;
148 elem->name = argv[optind];
150 if (circular) {
152 elem->forward = elem;
153 elem->backward = elem;
154 insque(elem, elem);
155 } else {
156 insque(elem, NULL);
157 }
158 /* Add remaining command-line arguments as list elements */
160 while (++optind < argc) {
162 prev = elem;
163 elem = new_element();
165 elem->name = argv[optind];
166 insque(elem, prev);
167 }
168 /* Traverse the list from the start, printing element names */
170 printf("Traversing completed list:\n");
172 elem = first;
173 do {
174 printf(" %s\n", elem->name);
175 elem = elem->forward;
176 } while (elem != NULL && elem != first);
177 if (elem == first)
179 printf("That was a circular list\n");
180 exit(EXIT_SUCCESS);
182 }
183
185 queue(7)
186
188 This page is part of release 5.10 of the Linux man-pages project. A
189 description of the project, information about reporting bugs, and the
190 latest version of this page, can be found at
191 https://www.kernel.org/doc/man-pages/.
192 2020-11-01 INSQUE(3)