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

   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
  34 struct list_proto {
  35     struct list_proto *prev;
  36     struct list_proto *next;
  37 };
  38
  39 struct 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  */
  48 void *
  49 tq_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  */
  72 void
  73 list2tq(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  */
 100 void
 101 list_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  */
 118 void
 119 tq_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 }