1/*
2 * Copyright (c) 2007-2008 Todd C. Miller <Todd.Miller@courtesan.com>
3 *
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
16 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
17 */
18
19#include <config.h>
20
21#include <sys/types.h>
22#include <stdio.h>
23#ifdef STDC_HEADERS
24# include <stdlib.h>
25# include <stddef.h>
26#else
27# ifdef HAVE_STDLIB_H
28#  include <stdlib.h>
29# endif
30#endif /* STDC_HEADERS */
31
32#include "sudo.h"
33
34struct list_proto {
35    struct list_proto *prev;
36    struct list_proto *next;
37};
38
39struct list_head_proto {
40    struct list_proto *first;
41    struct list_proto *last;
42};
43
44/*
45 * Pop the last element off the end of vh.
46 * Returns the popped element.
47 */
48void *
49tq_pop(vh)
50    void *vh;
51{
52    struct list_head_proto *h = (struct list_head_proto *)vh;
53    void *last = NULL;
54
55    if (!tq_empty(h)) {
56	last = (void *)h->last;
57	if (h->first == h->last) {
58	    h->first = NULL;
59	    h->last = NULL;
60	} else {
61	    h->last = h->last->prev;
62	    h->last->next = NULL;
63	}
64    }
65    return last;
66}
67
68/*
69 * Convert from a semi-circle queue to normal doubly-linked list
70 * with a head node.
71 */
72void
73list2tq(vh, vl)
74    void *vh;
75    void *vl;
76{
77    struct list_head_proto *h = (struct list_head_proto *)vh;
78    struct list_proto *l = (struct list_proto *)vl;
79
80    if (l != NULL) {
81#ifdef DEBUG
82	if (l->prev == NULL) {
83	    warningx("list2tq called with non-semicircular list");
84	    abort();
85	}
86#endif
87	h->first = l;
88	h->last = l->prev;	/* l->prev points to the last member of l */
89	l->prev = NULL;		/* zero last ptr now that we have a head */
90    } else {
91	h->first = NULL;
92	h->last = NULL;
93    }
94}
95
96/*
97 * Append one queue (or single entry) to another using the
98 * circular properties of the prev pointer to simplify the logic.
99 */
100void
101list_append(vl1, vl2)
102    void *vl1;
103    void *vl2;
104{
105    struct list_proto *l1 = (struct list_proto *)vl1;
106    struct list_proto *l2 = (struct list_proto *)vl2;
107    void *tail = l2->prev;
108
109    l1->prev->next = l2;
110    l2->prev = l1->prev;
111    l1->prev = tail;
112}
113
114/*
115 * Append the list of entries to the head node and convert
116 * e from a semi-circle queue to normal doubly-linked list.
117 */
118void
119tq_append(vh, vl)
120    void *vh;
121    void *vl;
122{
123    struct list_head_proto *h = (struct list_head_proto *)vh;
124    struct list_proto *l = (struct list_proto *)vl;
125    void *tail = l->prev;
126
127    if (h->first == NULL)
128	h->first = l;
129    else
130	h->last->next = l;
131    l->prev = h->last;
132    h->last = tail;
133}
134
135/*
136 * Remove element from the tail_queue
137 */
138void
139tq_remove(vh, vl)
140    void *vh;
141    void *vl;
142{
143    struct list_head_proto *h = (struct list_head_proto *)vh;
144    struct list_proto *l = (struct list_proto *)vl;
145
146    if (h->first == l && h->last == l) {
147	/* Single element in the list. */
148	h->first = NULL;
149	h->last = NULL;
150    } else {
151	/* At least two elements in the list. */
152	if (h->first == l) {
153	    h->first = l->next;
154	    h->first->prev = h->first;
155	} else if (h->last == l) {
156	    h->last = l->prev;
157	    h->last->next = NULL;
158	} else {
159	    l->prev->next = l->next;
160	    l->next->prev = l->prev;
161	}
162    }
163}
164