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 "%Z%%M% %I% %E% 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 ASSERT(b->bs_words * BT_NBIPUL > elt); 132 133 return (BT_TEST(b->bs_set, elt)); 134 } 135 136 /* 137 * Return non-zero if the bitset is empty 138 */ 139 int 140 bitset_is_null(bitset_t *b) 141 { 142 int i; 143 144 for (i = 0; i < b->bs_words; i++) 145 if (b->bs_set[i] != 0) 146 return (0); 147 return (1); 148 } 149 150 /* 151 * Find the first set bit in the bitset 152 * Return -1 if no bit was found 153 */ 154 uint_t 155 bitset_find(bitset_t *b) 156 { 157 uint_t i; 158 uint_t elt = (uint_t)-1; 159 160 for (i = 0; i < b->bs_words; i++) { 161 elt = (uint_t)(lowbit(b->bs_set[i]) - 1); 162 if (elt != (uint_t)-1) { 163 elt += i * BT_NBIPUL; 164 break; 165 } 166 } 167 return (elt); 168 } 169