2 * Copyright (c) 2007-2008, 2010-2011 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 */
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.
55 struct list_head_proto *h = (struct list_head_proto *)vh;
59 last = (void *)h->last;
60 if (h->first == h->last) {
64 h->last = h->last->prev;
72 * Convert from a semi-circle queue to normal doubly-linked list
76 list2tq(void *vh, void *vl)
78 struct list_head_proto *h = (struct list_head_proto *)vh;
79 struct list_proto *l = (struct list_proto *)vl;
83 if (l->prev == NULL) {
84 warningx2("list2tq called with non-semicircular list");
89 h->last = l->prev; /* l->prev points to the last member of l */
90 l->prev = NULL; /* zero last ptr now that we have a head */
98 * Append one queue (or single entry) to another using the
99 * circular properties of the prev pointer to simplify the logic.
102 list_append(void *vl1, void *vl2)
104 struct list_proto *l1 = (struct list_proto *)vl1;
105 struct list_proto *l2 = (struct list_proto *)vl2;
106 void *tail = l2->prev;
114 * Append the list of entries to the head node and convert
115 * e from a semi-circle queue to normal doubly-linked list.
118 tq_append(void *vh, void *vl)
120 struct list_head_proto *h = (struct list_head_proto *)vh;
121 struct list_proto *l = (struct list_proto *)vl;
122 void *tail = l->prev;
124 if (h->first == NULL)
133 * Remove element from the tail_queue
136 tq_remove(void *vh, void *vl)
138 struct list_head_proto *h = (struct list_head_proto *)vh;
139 struct list_proto *l = (struct list_proto *)vl;
141 if (h->first == l && h->last == l) {
142 /* Single element in the list. */
146 /* At least two elements in the list. */
149 h->first->prev = h->first;
150 } else if (h->last == l) {
152 h->last->next = NULL;
154 l->prev->next = l->next;
155 l->next->prev = l->prev;