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
46 attributes(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
68 including <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;
109 e = malloc(sizeof(struct element));
111 if (e == NULL) {
112 fprintf(stderr, "malloc() failed\n");
113 exit(EXIT_FAILURE);
114 }
115 return e;
117 }
118 int
120 main(int argc, char *argv[])
121 {
122 struct element *first, *elem, *prev;
123 int circular, opt, errfnd;
124 /* The "-c" command-line option can be used to specify that the
126 list is circular */
127 errfnd = 0;
129 circular = 0;
130 while ((opt = getopt(argc, argv, "c")) != -1) {
131 switch (opt) {
132 case 'c':
133 circular = 1;
134 break;
135 default:
136 errfnd = 1;
137 break;
138 }
139 }
140 if (errfnd || optind >= argc) {
142 fprintf(stderr, "Usage: %s [-c] string...\n", argv[0]);
143 exit(EXIT_FAILURE);
144 }
145 /* Create first element and place it in the linked list */
147 elem = new_element();
149 first = elem;
150 elem->name = argv[optind];
152 if (circular) {
154 elem->forward = elem;
155 elem->backward = elem;
156 insque(elem, elem);
157 } else {
158 insque(elem, NULL);
159 }
160 /* Add remaining command-line arguments as list elements */
162 while (++optind < argc) {
164 prev = elem;
165 elem = new_element();
167 elem->name = argv[optind];
168 insque(elem, prev);
169 }
170 /* Traverse the list from the start, printing element names */
172 printf("Traversing completed list:\n");
174 elem = first;
175 do {
176 printf(" %s\n", elem->name);
177 elem = elem->forward;
178 } while (elem != NULL && elem != first);
179 if (elem == first)
181 printf("That was a circular list\n");
182 exit(EXIT_SUCCESS);
184 }
185
187 queue(3)
188
190 This page is part of release 4.16 of the Linux man-pages project. A
191 description of the project, information about reporting bugs, and the
192 latest version of this page, can be found at
193 https://www.kernel.org/doc/man-pages/.
194 2017-09-15 INSQUE(3)