xref: /illumos-gate/usr/src/uts/common/os/bitset.c (revision 0542eecf8a04bde577ee69151dfe367a36053e40)
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 (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
23  */
24 
25 #include <sys/bitset.h>
26 #include <sys/kmem.h>
27 #include <sys/systm.h>
28 #include <sys/cpuvar.h>
29 #include <sys/cmn_err.h>
30 #include <sys/sysmacros.h>
31 
32 /*
33  * Initialize a bitset_t.
34  * After bitset_init(), the bitset will be zero sized.
35  */
36 void
bitset_init(bitset_t * b)37 bitset_init(bitset_t *b)
38 {
39 	bzero(b, sizeof (bitset_t));
40 }
41 
42 /*
43  * Initialize a bitset_t using a fanout. The fanout factor is platform
44  * specific and passed in as a power of two.
45  */
46 void
bitset_init_fanout(bitset_t * b,uint_t fanout)47 bitset_init_fanout(bitset_t *b, uint_t fanout)
48 {
49 	bzero(b, sizeof (bitset_t));
50 	b->bs_fanout = fanout;
51 }
52 
53 /*
54  * Uninitialize a bitset_t.
55  * This will free the bitset's data, leaving it zero sized.
56  */
57 void
bitset_fini(bitset_t * b)58 bitset_fini(bitset_t *b)
59 {
60 	if (b->bs_words > 0)
61 		kmem_free(b->bs_set, b->bs_words * sizeof (ulong_t));
62 }
63 
64 /*
65  * Resize a bitset to where it can hold els number of elements.
66  * This can either grow or shrink the bitset holding capacity.
67  * In the case of shrinkage, elements that reside outside the new
68  * holding capacity of the bitset are lost.
69  */
70 void
bitset_resize(bitset_t * b,uint_t els)71 bitset_resize(bitset_t *b, uint_t els)
72 {
73 	uint_t	nwords;
74 	ulong_t	*bset_new, *bset_tmp;
75 
76 	nwords = BT_BITOUL(els << b->bs_fanout);
77 	if (b->bs_words == nwords)
78 		return;	/* already properly sized */
79 
80 	/*
81 	 * Allocate the new ulong_t array, and copy the old one, if there
82 	 * was an old one.
83 	 */
84 	if (nwords > 0) {
85 		bset_new = kmem_zalloc(nwords * sizeof (ulong_t), KM_SLEEP);
86 		if (b->bs_words > 0)
87 			bcopy(b->bs_set, bset_new,
88 			    MIN(b->bs_words, nwords) * sizeof (ulong_t));
89 	} else {
90 		bset_new = NULL;
91 	}
92 
93 	/* swap out the old ulong_t array for new one */
94 	bset_tmp = b->bs_set;
95 	b->bs_set = bset_new;
96 
97 	/* free up the old array */
98 	if (b->bs_words > 0)
99 		kmem_free(bset_tmp, b->bs_words * sizeof (ulong_t));
100 
101 	b->bs_words = nwords;
102 }
103 
104 /*
105  * Returns the current holding capacity of the bitset.
106  */
107 uint_t
bitset_capacity(bitset_t * b)108 bitset_capacity(bitset_t *b)
109 {
110 	return (b->bs_words * BT_NBIPUL);
111 }
112 
113 /*
114  * Add (set) and delete (clear) bits in the bitset.
115  *
116  * Adding a bit that is already set, or removing a bit that's already clear
117  * is legal.
118  *
119  * Adding or deleting an element that falls outside the bitset's current
120  * holding capacity is illegal.
121  */
122 void
bitset_add(bitset_t * b,uint_t elt)123 bitset_add(bitset_t *b, uint_t elt)
124 {
125 	uint_t pos = (elt << b->bs_fanout);
126 
127 	ASSERT(b->bs_words * BT_NBIPUL > pos);
128 	BT_SET(b->bs_set, pos);
129 }
130 
131 /*
132  * Set a bit in an atomically safe way.
133  */
134 void
bitset_atomic_add(bitset_t * b,uint_t elt)135 bitset_atomic_add(bitset_t *b, uint_t elt)
136 {
137 	uint_t pos = (elt << b->bs_fanout);
138 
139 	ASSERT(b->bs_words * BT_NBIPUL > pos);
140 	BT_ATOMIC_SET(b->bs_set, pos);
141 }
142 
143 /*
144  * Atomically test that a given bit isn't set, and set it.
145  * Returns -1 if the bit was already set.
146  */
147 int
bitset_atomic_test_and_add(bitset_t * b,uint_t elt)148 bitset_atomic_test_and_add(bitset_t *b, uint_t elt)
149 {
150 	uint_t pos = (elt << b->bs_fanout);
151 	int ret;
152 
153 	ASSERT(b->bs_words * BT_NBIPUL > pos);
154 	BT_ATOMIC_SET_EXCL(b->bs_set, pos, ret);
155 
156 	return (ret);
157 }
158 
159 /*
160  * Clear a bit.
161  */
162 void
bitset_del(bitset_t * b,uint_t elt)163 bitset_del(bitset_t *b, uint_t elt)
164 {
165 	uint_t pos = (elt << b->bs_fanout);
166 
167 	ASSERT(b->bs_words * BT_NBIPUL > pos);
168 	BT_CLEAR(b->bs_set, pos);
169 }
170 
171 /*
172  * Clear a bit in an atomically safe way.
173  */
174 void
bitset_atomic_del(bitset_t * b,uint_t elt)175 bitset_atomic_del(bitset_t *b, uint_t elt)
176 {
177 	uint_t pos = (elt << b->bs_fanout);
178 
179 	ASSERT(b->bs_words * BT_NBIPUL > pos);
180 	BT_ATOMIC_CLEAR(b->bs_set, pos);
181 }
182 
183 /*
184  * Atomically test that a bit is set, and clear it.
185  * Returns -1 if the bit was already clear.
186  */
187 int
bitset_atomic_test_and_del(bitset_t * b,uint_t elt)188 bitset_atomic_test_and_del(bitset_t *b, uint_t elt)
189 {
190 	uint_t pos = (elt << b->bs_fanout);
191 	int ret;
192 
193 	ASSERT(b->bs_words * BT_NBIPUL > pos);
194 	BT_ATOMIC_CLEAR_EXCL(b->bs_set, pos, ret);
195 
196 	return (ret);
197 }
198 
199 /*
200  * Return non-zero if the bit is present in the set.
201  */
202 int
bitset_in_set(bitset_t * b,uint_t elt)203 bitset_in_set(bitset_t *b, uint_t elt)
204 {
205 	uint_t pos = (elt << b->bs_fanout);
206 
207 	if (pos >= b->bs_words * BT_NBIPUL)
208 		return (0);
209 
210 	return (BT_TEST(b->bs_set, pos));
211 }
212 
213 /*
214  * Return non-zero if the bitset is empty.
215  */
216 int
bitset_is_null(bitset_t * b)217 bitset_is_null(bitset_t *b)
218 {
219 	int i;
220 
221 	for (i = 0; i < b->bs_words; i++)
222 		if (b->bs_set[i] != 0)
223 			return (0);
224 	return (1);
225 }
226 
227 /*
228  * Perform a non-victimizing search for a set bit in a word.
229  * A "seed" is passed to pseudo-randomize the search.
230  * Return -1 if no set bit was found.
231  */
232 static uint_t
bitset_find_in_word(ulong_t w,uint_t seed)233 bitset_find_in_word(ulong_t w, uint_t seed)
234 {
235 	uint_t rotate_bit, elt = (uint_t)-1;
236 	ulong_t rotated_word;
237 
238 	if (w == (ulong_t)0)
239 		return (elt);
240 
241 	rotate_bit = seed % BT_NBIPUL;
242 	rotated_word = (w >> rotate_bit) | (w << (BT_NBIPUL - rotate_bit));
243 	elt = (uint_t)(lowbit(rotated_word) - 1);
244 	if (elt != (uint_t)-1)
245 		elt = ((elt + rotate_bit) % BT_NBIPUL);
246 
247 	return (elt);
248 }
249 
250 /*
251  * Select a bit that is set in the bitset in a non-victimizing fashion
252  * (e.g. doesn't bias the low/high order bits/words).
253  * Return -1 if no set bit was found
254  */
255 uint_t
bitset_find(bitset_t * b)256 bitset_find(bitset_t *b)
257 {
258 	uint_t start, i;
259 	uint_t elt = (uint_t)-1;
260 	uint_t seed;
261 
262 	seed = CPU_PSEUDO_RANDOM();
263 
264 	ASSERT(b->bs_words > 0);
265 	start = seed % b->bs_words;
266 
267 	i = start;
268 	do {
269 		elt = bitset_find_in_word(b->bs_set[i], seed);
270 		if (elt != (uint_t)-1) {
271 			elt += i * BT_NBIPUL;
272 			return (elt >> b->bs_fanout);
273 		}
274 		if (++i == b->bs_words)
275 			i = 0;
276 	} while (i != start);
277 
278 	return (elt);
279 }
280 
281 /*
282  * AND, OR, and XOR bitset computations, returns 1 if resulting bitset has any
283  * set bits. Operands must have the same fanout, if any.
284  */
285 int
bitset_and(bitset_t * bs1,bitset_t * bs2,bitset_t * res)286 bitset_and(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
287 {
288 	int i, anyset;
289 
290 	ASSERT(bs1->bs_fanout == bs2->bs_fanout);
291 	ASSERT(bs1->bs_fanout == res->bs_fanout);
292 
293 	for (anyset = 0, i = 0; i < bs1->bs_words; i++) {
294 		if ((res->bs_set[i] = (bs1->bs_set[i] & bs2->bs_set[i])) != 0)
295 			anyset = 1;
296 	}
297 	return (anyset);
298 }
299 
300 int
bitset_or(bitset_t * bs1,bitset_t * bs2,bitset_t * res)301 bitset_or(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
302 {
303 	int i, anyset;
304 
305 	ASSERT(bs1->bs_fanout == bs2->bs_fanout);
306 	ASSERT(bs1->bs_fanout == res->bs_fanout);
307 
308 	for (anyset = 0, i = 0; i < bs1->bs_words; i++) {
309 		if ((res->bs_set[i] = (bs1->bs_set[i] | bs2->bs_set[i])) != 0)
310 			anyset = 1;
311 	}
312 	return (anyset);
313 }
314 
315 int
bitset_xor(bitset_t * bs1,bitset_t * bs2,bitset_t * res)316 bitset_xor(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
317 {
318 	int i, anyset = 0;
319 
320 	ASSERT(bs1->bs_fanout == bs2->bs_fanout);
321 	ASSERT(bs1->bs_fanout == res->bs_fanout);
322 
323 	for (i = 0; i < bs1->bs_words; i++) {
324 		if ((res->bs_set[i] = (bs1->bs_set[i] ^ bs2->bs_set[i])) != 0)
325 			anyset = 1;
326 	}
327 	return (anyset);
328 }
329 
330 /*
331  * Return 1 if bitmaps are identical.
332  */
333 int
bitset_match(bitset_t * bs1,bitset_t * bs2)334 bitset_match(bitset_t *bs1, bitset_t *bs2)
335 {
336 	int i;
337 
338 	if (bs1->bs_words != bs2->bs_words)
339 		return (0);
340 
341 	for (i = 0; i < bs1->bs_words; i++)
342 		if (bs1->bs_set[i] != bs2->bs_set[i])
343 			return (0);
344 	return (1);
345 }
346 
347 /*
348  * Zero a bitset_t.
349  */
350 void
bitset_zero(bitset_t * b)351 bitset_zero(bitset_t *b)
352 {
353 	bzero(b->bs_set, sizeof (ulong_t) * b->bs_words);
354 }
355 
356 /*
357  * Copy a bitset_t.
358  */
359 void
bitset_copy(bitset_t * src,bitset_t * dest)360 bitset_copy(bitset_t *src, bitset_t *dest)
361 {
362 	ASSERT(src->bs_fanout == dest->bs_fanout);
363 	bcopy(src->bs_set, dest->bs_set, sizeof (ulong_t) * src->bs_words);
364 }
365