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

NAME

6       insque, remque - insert/remove an item from a queue
7

SYNOPSIS

9       #include <search.h>
10
11       void insque(void *elem, void *prev);
12       void remque(void *elem);
13
14   Feature Test Macro Requirements for glibc (see feature_test_macros(7)):
15
16       insque(), remque():
17           _XOPEN_SOURCE >= 500
18               || /* Glibc since 2.19: */ _DEFAULT_SOURCE
19               || /* Glibc <= 2.19: */ _SVID_SOURCE
20

DESCRIPTION

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
28       The  insque()  function  inserts the element pointed to by elem immedi‐
29       ately after the element pointed to by prev.
30
31       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
35       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
40       The  remque()  function removes the element pointed to by elem from the
41       doubly linked list.
42

ATTRIBUTES

44       For an  explanation  of  the  terms  used  in  this  section,  see  at‐
45       tributes(7).
46
47       ┌────────────────────────────────────────────┬───────────────┬─────────┐
48Interface                                   Attribute     Value   
49       ├────────────────────────────────────────────┼───────────────┼─────────┤
50insque(), remque()                          │ Thread safety │ MT-Safe │
51       └────────────────────────────────────────────┴───────────────┴─────────┘
52

CONFORMING TO

54       POSIX.1-2001, POSIX.1-2008.
55

NOTES

57       On  ancient  systems,  the  arguments  of  these functions were of type
58       struct qelem *, defined as:
59
60           struct qelem {
61               struct qelem *q_forw;
62               struct qelem *q_back;
63               char          q_data[1];
64           };
65
66       This is still what you will get if _GNU_SOURCE is  defined  before  in‐
67       cluding <search.h>.
68
69       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

BUGS

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

EXAMPLES

81       The program below demonstrates the use of insque().  Here is an example
82       run of the program:
83
84           $ ./a.out -c a b c
85           Traversing completed list:
86               a
87               b
88               c
89           That was a circular list
90
91   Program source
92
93       #include <stdio.h>
94       #include <stdlib.h>
95       #include <unistd.h>
96       #include <search.h>
97
98       struct element {
99           struct element *forward;
100           struct element *backward;
101           char *name;
102       };
103
104       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
113           return e;
114       }
115
116       int
117       main(int argc, char *argv[])
118       {
119           struct element *first, *elem, *prev;
120           int circular, opt, errfnd;
121
122           /* The "-c" command-line option can be used to specify that the
123              list is circular. */
124
125           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
138           if (errfnd || optind >= argc) {
139               fprintf(stderr,  "Usage: %s [-c] string...\n", argv[0]);
140               exit(EXIT_FAILURE);
141           }
142
143           /* Create first element and place it in the linked list. */
144
145           elem = new_element();
146           first = elem;
147
148           elem->name = argv[optind];
149
150           if (circular) {
151               elem->forward = elem;
152               elem->backward = elem;
153               insque(elem, elem);
154           } else {
155               insque(elem, NULL);
156           }
157
158           /* Add remaining command-line arguments as list elements. */
159
160           while (++optind < argc) {
161               prev = elem;
162
163               elem = new_element();
164               elem->name = argv[optind];
165               insque(elem, prev);
166           }
167
168           /* Traverse the list from the start, printing element names. */
169
170           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
177           if (elem == first)
178               printf("That was a circular list\n");
179
180           exit(EXIT_SUCCESS);
181       }
182

SEE ALSO

184       queue(7)
185

COLOPHON

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
192
193
194                                  2021-03-22                         INSQUE(3)
Impressum