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
13       void remque(void *elem);
14
15   Feature Test Macro Requirements for glibc (see feature_test_macros(7)):
16
17       insque(), remque():
18           _SVID_SOURCE || _XOPEN_SOURCE >= 500 ||
19           _XOPEN_SOURCE && _XOPEN_SOURCE_EXTENDED
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

CONFORMING TO

44       POSIX.1-2001.
45

NOTES

47       Traditionally  (e.g., SunOS, Linux libc 4 and libc 5), the arguments of
48       these functions were of type struct qelem *, defined as:
49
50           struct qelem {
51               struct qelem *q_forw;
52               struct qelem *q_back;
53               char          q_data[1];
54           };
55
56       This is still what you  will  get  if  _GNU_SOURCE  is  defined  before
57       including <search.h>.
58
59       The  location  of the prototypes for these functions differs among sev‐
60       eral versions of UNIX.  The above is the POSIX version.   Some  systems
61       place  them  in  <string.h>.   Linux  libc4  and  libc 5 placed them in
62       <stdlib.h>.
63

BUGS

65       In glibc 2.4 and earlier, it was not possible to specify prev as  NULL.
66       Consequently,  to  build  a linear list, the caller had to build a list
67       using an initial call that contained the  first  two  elements  of  the
68       list,  with  the forward and backward pointers in each element suitably
69       initialized.
70

EXAMPLE

72       The program below demonstrates the use of insque().  Here is an example
73       run of the program:
74
75           $ ./a.out -c a b c
76           Traversing completed list:
77               a
78               b
79               c
80           That was a circular list
81
82   Program source
83
84       #include <stdio.h>
85       #include <stdlib.h>
86       #include <unistd.h>
87       #include <search.h>
88
89       struct element {
90           struct element *forward;
91           struct element *backward;
92           char *name;
93       };
94
95       static struct element *
96       new_element(void)
97       {
98           struct element *e;
99
100           e = malloc(sizeof(struct element));
101           if (e == NULL) {
102               fprintf(stderr, "malloc() failed\n");
103               exit(EXIT_FAILURE);
104           }
105
106           return e;
107       }
108
109       int
110       main(int argc, char *argv[])
111       {
112           struct element *first, *elem, *prev;
113           int circular, opt, errfnd;
114
115           /* The "-c" command-line option can be used to specify that the
116              list is circular */
117
118           errfnd = 0;
119           circular = 0;
120           while ((opt = getopt(argc, argv, "c")) != -1) {
121               switch (opt) {
122               case 'c':
123                   circular = 1;
124                   break;
125               default:
126                   errfnd = 1;
127                   break;
128               }
129           }
130
131           if (errfnd || optind >= argc) {
132               fprintf(stderr,  "Usage: %s [-c] string...\n", argv[0]);
133               exit(EXIT_FAILURE);
134           }
135
136           /* Create first element and place it in the linked list */
137
138           elem = new_element();
139           first = elem;
140
141           elem->name = argv[optind];
142
143           if (circular) {
144               elem->forward = elem;
145               elem->backward = elem;
146               insque(elem, elem);
147           } else {
148               insque(elem, NULL);
149           }
150
151           /* Add remaining command-line arguments as list elements */
152
153           while (++optind < argc) {
154               prev = elem;
155
156               elem = new_element();
157               elem->name = argv[optind];
158               insque(elem, prev);
159           }
160
161           /* Traverse the list from the start, printing element names */
162
163           printf("Traversing completed list:\n");
164           elem = first;
165           do {
166               printf("    %s\n", elem->name);
167               elem = elem->forward;
168           } while (elem != NULL && elem != first);
169
170           if (elem == first)
171               printf("That was a circular list\n");
172
173           exit(EXIT_SUCCESS);
174       }
175

COLOPHON

177       This  page  is  part of release 3.53 of the Linux man-pages project.  A
178       description of the project, and information about reporting  bugs,  can
179       be found at http://www.kernel.org/doc/man-pages/.
180
181
182
183                                  2010-09-09                         INSQUE(3)