2 * Copyright (c) 2007-2008 Todd C. Miller <Todd.Miller@courtesan.com>
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.
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.
21 #include <sys/types.h>
30 #endif /* STDC_HEADERS */
35 __unused static const char rcsid[] = "$Sudo: list.c,v 1.6 2008/11/09 14:13:12 millert Exp $";
39 struct list_proto *prev;
40 struct list_proto *next;
43 struct list_head_proto {
44 struct list_proto *first;
45 struct list_proto *last;
49 * Pop the last element off the end of vh.
50 * Returns the popped element.
56 struct list_head_proto *h = (struct list_head_proto *)vh;
60 last = (void *)h->last;
61 if (h->first == h->last) {
65 h->last = h->last->prev;
73 * Convert from a semi-circle queue to normal doubly-linked list
81 struct list_head_proto *h = (struct list_head_proto *)vh;
82 struct list_proto *l = (struct list_proto *)vl;
86 if (l->prev == NULL) {
87 warningx("list2tq called with non-semicircular list");
92 h->last = l->prev; /* l->prev points to the last member of l */
93 l->prev = NULL; /* zero last ptr now that we have a head */
101 * Append one queue (or single entry) to another using the
102 * circular properties of the prev pointer to simplify the logic.
105 list_append(vl1, vl2)
109 struct list_proto *l1 = (struct list_proto *)vl1;
110 struct list_proto *l2 = (struct list_proto *)vl2;
111 void *tail = l2->prev;
119 * Append the list of entries to the head node and convert
120 * e from a semi-circle queue to normal doubly-linked list.
127 struct list_head_proto *h = (struct list_head_proto *)vh;
128 struct list_proto *l = (struct list_proto *)vl;
129 void *tail = l->prev;
131 if (h->first == NULL)