Home | History | Annotate | 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 2006 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 #include <unistd.h>
     30 #include <assert.h>
     31 
     32 #include <topo_list.h>
     33 #include <topo_tree.h>
     34 
     35 /*
     36  * Embedded Linked Lists
     37  *
     38  * Simple doubly-linked list implementation.  This implementation assumes that
     39  * each list element contains an embedded topo_list_t (previous and next
     40  * pointers), which is typically the first member of the element struct.
     41  * An additional topo_list_t is used to store the head (l_next) and tail
     42  * (l_prev) pointers.  The current head and tail list elements have their
     43  * previous and next pointers set to NULL, respectively.
     44  *
     45  * NOTE: The embeddable list code in this file intentionally provides no
     46  * locking of any kind.  The implementation of any list in topo must provide
     47  * an appropriate locking strategy to protect the list or to protect access
     48  * to the embedded topo_list_t inside of each list element to avoid corruption.
     49  * Refer to comments in the source files that use topo_list_t for lock details.
     50  */
     51 
     52 
     53 void
     54 topo_list_append(topo_list_t *lp, void *new)
     55 {
     56 	topo_list_t *p = lp->l_prev;	/* p = tail list element */
     57 	topo_list_t *q = new;		/* q = new list element */
     58 
     59 	lp->l_prev = q;
     60 	q->l_prev = p;
     61 	q->l_next = NULL;
     62 
     63 	if (p != NULL) {
     64 		assert(p->l_next == NULL);
     65 		p->l_next = q;
     66 	} else {
     67 		assert(lp->l_next == NULL);
     68 		lp->l_next = q;
     69 	}
     70 }
     71 
     72 void
     73 topo_list_prepend(topo_list_t *lp, void *new)
     74 {
     75 	topo_list_t *p = new;		/* p = new list element */
     76 	topo_list_t *q = lp->l_next;	/* q = head list element */
     77 
     78 	lp->l_next = p;
     79 	p->l_prev = NULL;
     80 	p->l_next = q;
     81 
     82 	if (q != NULL) {
     83 		assert(q->l_prev == NULL);
     84 		q->l_prev = p;
     85 	} else {
     86 		assert(lp->l_prev == NULL);
     87 		lp->l_prev = p;
     88 	}
     89 }
     90 
     91 void
     92 topo_list_insert_before(topo_list_t *lp, void *before_me, void *new)
     93 {
     94 	topo_list_t *p = before_me;
     95 	topo_list_t *q = new;
     96 
     97 	if (p == NULL || p->l_prev == NULL) {
     98 		topo_list_prepend(lp, new);
     99 		return;
    100 	}
    101 
    102 	q->l_prev = p->l_prev;
    103 	q->l_next = p;
    104 	p->l_prev = q;
    105 	q->l_prev->l_next = q;
    106 }
    107 
    108 void
    109 topo_list_insert_after(topo_list_t *lp, void *after_me, void *new)
    110 {
    111 	topo_list_t *p = after_me;
    112 	topo_list_t *q = new;
    113 
    114 	if (p == NULL || p->l_next == NULL) {
    115 		topo_list_append(lp, new);
    116 		return;
    117 	}
    118 
    119 	q->l_next = p->l_next;
    120 	q->l_prev = p;
    121 	p->l_next = q;
    122 	q->l_next->l_prev = q;
    123 }
    124 
    125 void
    126 topo_list_delete(topo_list_t *lp, void *existing)
    127 {
    128 	topo_list_t *p = existing;
    129 
    130 	if (p->l_prev != NULL)
    131 		p->l_prev->l_next = p->l_next;
    132 	else
    133 		lp->l_next = p->l_next;
    134 
    135 	if (p->l_next != NULL)
    136 		p->l_next->l_prev = p->l_prev;
    137 	else
    138 		lp->l_prev = p->l_prev;
    139 }
    140 
    141 tnode_t *
    142 topo_child_first(tnode_t *pnode)
    143 {
    144 	int i;
    145 	topo_nodehash_t *nhp;
    146 
    147 	for (nhp = topo_list_next(&pnode->tn_children); nhp != NULL;
    148 	    nhp = topo_list_next(nhp)) {
    149 		for (i = 0; i < nhp->th_arrlen; ++i) {
    150 			if (nhp->th_nodearr[i] != NULL)
    151 				return (nhp->th_nodearr[i]);
    152 		}
    153 	}
    154 
    155 	return (NULL);
    156 }
    157 
    158 tnode_t *
    159 topo_child_next(tnode_t *pnode, tnode_t *node)
    160 {
    161 	int i;
    162 	int index;
    163 	topo_nodehash_t *nhp;
    164 
    165 	if (node == NULL) {
    166 		return (topo_child_first(pnode));
    167 	}
    168 
    169 	/*
    170 	 * Begin search for next child in the current hash array
    171 	 * If none found or we are at the end of the array, move
    172 	 * on to the next array
    173 	 */
    174 	index = topo_node_hash(node->tn_phash, node->tn_instance) + 1;
    175 	for (nhp = node->tn_phash; nhp != NULL; nhp = topo_list_next(nhp)) {
    176 		for (i = index; i < nhp->th_arrlen; ++i) {
    177 			if (nhp->th_nodearr[i] != NULL) {
    178 				return (nhp->th_nodearr[i]);
    179 			}
    180 		}
    181 		index = 0;
    182 	}
    183 
    184 	return (NULL);
    185 }
    186