Annotation of embedaddon/sudo/common/list.c, revision 1.1
1.1 ! misho 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>