git.gag.com Git - debian/sudo/blob - common/list.c

   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 }