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