1: /*
2: * Copyright (c) 2007-2008, 2010-2011 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 "missing.h"
33: #include "list.h"
34: #ifdef DEBUG
35: # include "error.h"
36: #endif
37:
38: struct list_proto {
39: struct list_proto *prev;
40: struct list_proto *next;
41: };
42:
43: struct list_head_proto {
44: struct list_proto *first;
45: struct list_proto *last;
46: };
47:
48: /*
49: * Pop the last element off the end of vh.
50: * Returns the popped element.
51: */
52: void *
53: tq_pop(void *vh)
54: {
55: struct list_head_proto *h = (struct list_head_proto *)vh;
56: void *last = NULL;
57:
58: if (!tq_empty(h)) {
59: last = (void *)h->last;
60: if (h->first == h->last) {
61: h->first = NULL;
62: h->last = NULL;
63: } else {
64: h->last = h->last->prev;
65: h->last->next = NULL;
66: }
67: }
68: return last;
69: }
70:
71: /*
72: * Convert from a semi-circle queue to normal doubly-linked list
73: * with a head node.
74: */
75: void
76: list2tq(void *vh, void *vl)
77: {
78: struct list_head_proto *h = (struct list_head_proto *)vh;
79: struct list_proto *l = (struct list_proto *)vl;
80:
81: if (l != NULL) {
82: #ifdef DEBUG
83: if (l->prev == NULL) {
84: warningx("list2tq called with non-semicircular list");
85: abort();
86: }
87: #endif
88: h->first = l;
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 */
91: } else {
92: h->first = NULL;
93: h->last = NULL;
94: }
95: }
96:
97: /*
98: * Append one queue (or single entry) to another using the
99: * circular properties of the prev pointer to simplify the logic.
100: */
101: void
102: list_append(void *vl1, void *vl2)
103: {
104: struct list_proto *l1 = (struct list_proto *)vl1;
105: struct list_proto *l2 = (struct list_proto *)vl2;
106: void *tail = l2->prev;
107:
108: l1->prev->next = l2;
109: l2->prev = l1->prev;
110: l1->prev = tail;
111: }
112:
113: /*
114: * Append the list of entries to the head node and convert
115: * e from a semi-circle queue to normal doubly-linked list.
116: */
117: void
118: tq_append(void *vh, void *vl)
119: {
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;
123:
124: if (h->first == NULL)
125: h->first = l;
126: else
127: h->last->next = l;
128: l->prev = h->last;
129: h->last = tail;
130: }
131:
132: /*
133: * Remove element from the tail_queue
134: */
135: void
136: tq_remove(void *vh, void *vl)
137: {
138: struct list_head_proto *h = (struct list_head_proto *)vh;
139: struct list_proto *l = (struct list_proto *)vl;
140:
141: if (h->first == l && h->last == l) {
142: /* Single element in the list. */
143: h->first = NULL;
144: h->last = NULL;
145: } else {
146: /* At least two elements in the list. */
147: if (h->first == l) {
148: h->first = l->next;
149: h->first->prev = h->first;
150: } else if (h->last == l) {
151: h->last = l->prev;
152: h->last->next = NULL;
153: } else {
154: l->prev->next = l->next;
155: l->next->prev = l->prev;
156: }
157: }
158: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>