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);
13 Feature Test Macro Requirements for glibc (see feature_test_macros(7)):
15 insque(), remque():
17 _XOPEN_SOURCE >= 500
18 || /* Glibc since 2.19: */ _DEFAULT_SOURCE
19 || /* Glibc <= 2.19: */ _SVID_SOURCE
20
22 The insque() and remque() functions manipulate doubly linked lists.
23 Each element in the list is a structure of which the first two elements
24 are a forward and a backward pointer. The linked list may be linear
25 (i.e., NULL forward pointer at the end of the list and NULL backward
26 pointer at the start of the list) or circular.
27 The insque() function inserts the element pointed to by elem immedi‐
29 ately after the element pointed to by prev.
30 If the list is linear, then the call insque(elem, NULL) can be used to
32 insert the initial list element, and the call sets the forward and
33 backward pointers of elem to NULL.
34 If the list is circular, the caller should ensure that the forward and
36 backward pointers of the first element are initialized to point to that
37 element, and the prev argument of the insque() call should also point
38 to the element.
39 The remque() function removes the element pointed to by elem from the
41 doubly linked list.
42
44 For an explanation of the terms used in this section, see at‐
45 tributes(7).
46 ┌────────────────────────────────────────────┬───────────────┬─────────┐
48 │Interface │ Attribute │ Value │
49 ├────────────────────────────────────────────┼───────────────┼─────────┤
50 │insque(), remque() │ Thread safety │ MT-Safe │
51 └────────────────────────────────────────────┴───────────────┴─────────┘
52
54 POSIX.1-2001, POSIX.1-2008.
55
57 On ancient systems, the arguments of these functions were of type
58 struct qelem *, defined as:
59 struct qelem {
61 struct qelem *q_forw;
62 struct qelem *q_back;
63 char q_data[1];
64 };
65 This is still what you will get if _GNU_SOURCE is defined before in‐
67 cluding <search.h>.
68 The location of the prototypes for these functions differs among sev‐
70 eral versions of UNIX. The above is the POSIX version. Some systems
71 place them in <string.h>.
72
74 In glibc 2.4 and earlier, it was not possible to specify prev as NULL.
75 Consequently, to build a linear list, the caller had to build a list
76 using an initial call that contained the first two elements of the
77 list, with the forward and backward pointers in each element suitably
78 initialized.
79
81 The program below demonstrates the use of insque(). Here is an example
82 run of the program:
83 $ ./a.out -c a b c
85 Traversing completed list:
86 a
87 b
88 c
89 That was a circular list
90 Program source
92 #include <stdio.h>
94 #include <stdlib.h>
95 #include <unistd.h>
96 #include <search.h>
97 struct element {
99 struct element *forward;
100 struct element *backward;
101 char *name;
102 };
103 static struct element *
105 new_element(void)
106 {
107 struct element *e = malloc(sizeof(*e));
108 if (e == NULL) {
109 fprintf(stderr, "malloc() failed\n");
110 exit(EXIT_FAILURE);
111 }
112 return e;
114 }
115 int
117 main(int argc, char *argv[])
118 {
119 struct element *first, *elem, *prev;
120 int circular, opt, errfnd;
121 /* The "-c" command-line option can be used to specify that the
123 list is circular. */
124 errfnd = 0;
126 circular = 0;
127 while ((opt = getopt(argc, argv, "c")) != -1) {
128 switch (opt) {
129 case 'c':
130 circular = 1;
131 break;
132 default:
133 errfnd = 1;
134 break;
135 }
136 }
137 if (errfnd || optind >= argc) {
139 fprintf(stderr, "Usage: %s [-c] string...\n", argv[0]);
140 exit(EXIT_FAILURE);
141 }
142 /* Create first element and place it in the linked list. */
144 elem = new_element();
146 first = elem;
147 elem->name = argv[optind];
149 if (circular) {
151 elem->forward = elem;
152 elem->backward = elem;
153 insque(elem, elem);
154 } else {
155 insque(elem, NULL);
156 }
157 /* Add remaining command-line arguments as list elements. */
159 while (++optind < argc) {
161 prev = elem;
162 elem = new_element();
164 elem->name = argv[optind];
165 insque(elem, prev);
166 }
167 /* Traverse the list from the start, printing element names. */
169 printf("Traversing completed list:\n");
171 elem = first;
172 do {
173 printf(" %s\n", elem->name);
174 elem = elem->forward;
175 } while (elem != NULL && elem != first);
176 if (elem == first)
178 printf("That was a circular list\n");
179 exit(EXIT_SUCCESS);
181 }
182
184 queue(7)
185
187 This page is part of release 5.13 of the Linux man-pages project. A
188 description of the project, information about reporting bugs, and the
189 latest version of this page, can be found at
190 https://www.kernel.org/doc/man-pages/.
191 2021-03-22 INSQUE(3)