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