Home | History | Annotate | Line # | Download | only in common 
      1 /*
      2  * CDDL HEADER START
      3  *
      4  * The contents of this file are subject to the terms of the
      5  * Common Development and Distribution License, Version 1.0 only
      6  * (the "License").  You may not use this file except in compliance
      7  * with the License.
      8  *
      9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
     10  * or http://www.opensolaris.org/os/licensing.
     11  * See the License for the specific language governing permissions
     12  * and limitations under the License.
     13  *
     14  * When distributing Covered Code, include this CDDL HEADER in each
     15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
     16  * If applicable, add the following below this CDDL HEADER, with the
     17  * fields enclosed by brackets "[]" replaced with your own identifying
     18  * information: Portions Copyright [yyyy] [name of copyright owner]
     19  *
     20  * CDDL HEADER END
     21  */
     22 /*
     23  * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
     24  * Use is subject to license terms.
     25  */
     26 
     27 #pragma ident	"%Z%%M%	%I%	%E% SMI"
     28 
     29 /*
     30  * Simple doubly-linked list implementation.  This implementation assumes that
     31  * each list element contains an embedded dt_list_t (previous and next
     32  * pointers), which is typically the first member of the element struct.
     33  * An additional dt_list_t is used to store the head (dl_next) and tail
     34  * (dl_prev) pointers.  The current head and tail list elements have their
     35  * previous and next pointers set to NULL, respectively.
     36  */
     37 
     38 #include <unistd.h>
     39 #include <assert.h>
     40 #include <dt_list.h>
     41 
     42 void
     43 dt_list_append(dt_list_t *dlp, void *new)
     44 {
     45 	dt_list_t *p = dlp->dl_prev;	/* p = tail list element */
     46 	dt_list_t *q = new;		/* q = new list element */
     47 
     48 	dlp->dl_prev = q;
     49 	q->dl_prev = p;
     50 	q->dl_next = NULL;
     51 
     52 	if (p != NULL) {
     53 		assert(p->dl_next == NULL);
     54 		p->dl_next = q;
     55 	} else {
     56 		assert(dlp->dl_next == NULL);
     57 		dlp->dl_next = q;
     58 	}
     59 }
     60 
     61 void
     62 dt_list_prepend(dt_list_t *dlp, void *new)
     63 {
     64 	dt_list_t *p = new;		/* p = new list element */
     65 	dt_list_t *q = dlp->dl_next;	/* q = head list element */
     66 
     67 	dlp->dl_next = p;
     68 	p->dl_prev = NULL;
     69 	p->dl_next = q;
     70 
     71 	if (q != NULL) {
     72 		assert(q->dl_prev == NULL);
     73 		q->dl_prev = p;
     74 	} else {
     75 		assert(dlp->dl_prev == NULL);
     76 		dlp->dl_prev = p;
     77 	}
     78 }
     79 
     80 void
     81 dt_list_insert(dt_list_t *dlp, void *after_me, void *new)
     82 {
     83 	dt_list_t *p = after_me;
     84 	dt_list_t *q = new;
     85 
     86 	if (p == NULL || p->dl_next == NULL) {
     87 		dt_list_append(dlp, new);
     88 		return;
     89 	}
     90 
     91 	q->dl_next = p->dl_next;
     92 	q->dl_prev = p;
     93 	p->dl_next = q;
     94 	q->dl_next->dl_prev = q;
     95 }
     96 
     97 void
     98 dt_list_delete(dt_list_t *dlp, void *existing)
     99 {
    100 	dt_list_t *p = existing;
    101 
    102 	if (p->dl_prev != NULL)
    103 		p->dl_prev->dl_next = p->dl_next;
    104 	else
    105 		dlp->dl_next = p->dl_next;
    106 
    107 	if (p->dl_next != NULL)
    108 		p->dl_next->dl_prev = p->dl_prev;
    109 	else
    110 		dlp->dl_prev = p->dl_prev;
    111 }
    112