Return to list.c CVS log

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

Annotation of embedaddon/sudo/common/list.c, revision 1.1.1.2

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) {
1.1.1.2 ! misho      84:            warningx2("list2tq called with non-semicircular list");
1.1       misho      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: }