Return to list.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sudo / common

Initial revision

    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: }