Home | History | Annotate | Download | only in os
      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 (the "License").
      6  * You may not use this file except in compliance with the License.
      7  *
      8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
      9  * or http://www.opensolaris.org/os/licensing.
     10  * See the License for the specific language governing permissions
     11  * and limitations under the License.
     12  *
     13  * When distributing Covered Code, include this CDDL HEADER in each
     14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
     15  * If applicable, add the following below this CDDL HEADER, with the
     16  * fields enclosed by brackets "[]" replaced with your own identifying
     17  * information: Portions Copyright [yyyy] [name of copyright owner]
     18  *
     19  * CDDL HEADER END
     20  */
     21 /*
     22  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
     23  * Use is subject to license terms.
     24  */
     25 
     26 #pragma ident	"@(#)bitset.c	1.2	07/02/21 SMI"
     27 
     28 #include <sys/bitset.h>
     29 #include <sys/kmem.h>
     30 #include <sys/systm.h>
     31 #include <sys/cmn_err.h>
     32 #include <sys/sysmacros.h>
     33 
     34 /*
     35  * Initialize a bitset_t.
     36  * After bitset_init(), the bitset will be zero sized.
     37  */
     38 void
     39 bitset_init(bitset_t *b)
     40 {
     41 	bzero(b, sizeof (bitset_t));
     42 }
     43 
     44 /*
     45  * Uninitialize a bitset_t.
     46  * This will free the bitset's data, leaving it zero sized.
     47  */
     48 void
     49 bitset_fini(bitset_t *b)
     50 {
     51 	if (b->bs_words > 0)
     52 		kmem_free(b->bs_set, b->bs_words * sizeof (ulong_t));
     53 }
     54 
     55 /*
     56  * Resize a bitset to where it can hold sz number of bits.
     57  * This can either grow or shrink the bitset holding capacity.
     58  * In the case of shrinkage, elements that reside outside the new
     59  * holding capacity of the bitset are lost.
     60  */
     61 void
     62 bitset_resize(bitset_t *b, uint_t sz)
     63 {
     64 	uint_t	nwords;
     65 	ulong_t	*bset_new, *bset_tmp;
     66 
     67 	nwords = BT_BITOUL(sz);
     68 	if (b->bs_words == nwords)
     69 		return;	/* already properly sized */
     70 
     71 	/*
     72 	 * Allocate the new ulong_t array, and copy the old one.
     73 	 */
     74 	if (nwords > 0) {
     75 		bset_new = kmem_zalloc(nwords * sizeof (ulong_t), KM_SLEEP);
     76 		bcopy(b->bs_set, bset_new,
     77 		    MIN(b->bs_words, nwords) * sizeof (ulong_t));
     78 	} else {
     79 		bset_new = NULL;
     80 	}
     81 
     82 	/* swap out the old ulong_t array for new one */
     83 	bset_tmp = b->bs_set;
     84 	b->bs_set = bset_new;
     85 
     86 	/* free up the old array */
     87 	kmem_free(bset_tmp, b->bs_words * sizeof (ulong_t));
     88 	b->bs_words = nwords;
     89 }
     90 
     91 /*
     92  * Returns the current holding capacity of the bitset
     93  */
     94 uint_t
     95 bitset_capacity(bitset_t *b)
     96 {
     97 	return (b->bs_words * BT_NBIPUL);
     98 }
     99 
    100 /*
    101  * Add and delete bits in the bitset.
    102  *
    103  * Adding a bit that is already set, and clearing a bit that's already clear
    104  * is legal.
    105  *
    106  * Adding or deleting an element that falls outside the bitset's current
    107  * holding capacity is illegal.
    108  */
    109 void
    110 bitset_add(bitset_t *b, uint_t elt)
    111 {
    112 	ASSERT(b->bs_words * BT_NBIPUL > elt);
    113 
    114 	BT_SET(b->bs_set, elt);
    115 }
    116 
    117 void
    118 bitset_del(bitset_t *b, uint_t elt)
    119 {
    120 	ASSERT(b->bs_words * BT_NBIPUL > elt);
    121 
    122 	BT_CLEAR(b->bs_set, elt);
    123 }
    124 
    125 /*
    126  * Return non-zero if the bit is present in the set
    127  */
    128 int
    129 bitset_in_set(bitset_t *b, uint_t elt)
    130 {
    131 	if (elt >= b->bs_words * BT_NBIPUL)
    132 		return (0);
    133 
    134 	return (BT_TEST(b->bs_set, elt));
    135 }
    136 
    137 /*
    138  * Return non-zero if the bitset is empty
    139  */
    140 int
    141 bitset_is_null(bitset_t *b)
    142 {
    143 	int	i;
    144 
    145 	for (i = 0; i < b->bs_words; i++)
    146 		if (b->bs_set[i] != 0)
    147 			return (0);
    148 	return (1);
    149 }
    150 
    151 /*
    152  * Find the first set bit in the bitset
    153  * Return -1 if no bit was found
    154  */
    155 uint_t
    156 bitset_find(bitset_t *b)
    157 {
    158 	uint_t	i;
    159 	uint_t	elt = (uint_t)-1;
    160 
    161 	for (i = 0; i < b->bs_words; i++) {
    162 		elt = (uint_t)(lowbit(b->bs_set[i]) - 1);
    163 		if (elt != (uint_t)-1) {
    164 			elt += i * BT_NBIPUL;
    165 			break;
    166 		}
    167 	}
    168 	return (elt);
    169 }
    170