fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * CDDL HEADER START
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * The contents of this file are subject to the terms of the
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Common Development and Distribution License (the "License").
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * You may not use this file except in compliance with the License.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * See the License for the specific language governing permissions
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * and limitations under the License.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * When distributing Covered Code, include this CDDL HEADER in each
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * If applicable, add the following below this CDDL HEADER, with the
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * fields enclosed by brackets "[]" replaced with your own identifying
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * information: Portions Copyright [yyyy] [name of copyright owner]
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * CDDL HEADER END
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Initialize a bitset_t.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * After bitset_init(), the bitset will be zero sized.
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Initialize a bitset_t using a fanout. The fanout factor is platform
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * specific and passed in as a power of two.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Uninitialize a bitset_t.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * This will free the bitset's data, leaving it zero sized.
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Resize a bitset to where it can hold els number of elements.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * This can either grow or shrink the bitset holding capacity.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * In the case of shrinkage, elements that reside outside the new
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * holding capacity of the bitset are lost.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return; /* already properly sized */
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Allocate the new ulong_t array, and copy the old one, if there
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * was an old one.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe bset_new = kmem_zalloc(nwords * sizeof (ulong_t), KM_SLEEP);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /* swap out the old ulong_t array for new one */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /* free up the old array */
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe kmem_free(bset_tmp, b->bs_words * sizeof (ulong_t));
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Returns the current holding capacity of the bitset.
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Add (set) and delete (clear) bits in the bitset.
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Adding a bit that is already set, or removing a bit that's already clear
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * is legal.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Adding or deleting an element that falls outside the bitset's current
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * holding capacity is illegal.
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Set a bit in an atomically safe way.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Atomically test that a given bit isn't set, and set it.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Returns -1 if the bit was already set.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxebitset_atomic_test_and_add(bitset_t *b, uint_t elt)
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Clear a bit.
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Clear a bit in an atomically safe way.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Atomically test that a bit is set, and clear it.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Returns -1 if the bit was already clear.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxebitset_atomic_test_and_del(bitset_t *b, uint_t elt)
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Return non-zero if the bit is present in the set.
0f424180e3b253cef8b25600a32523677cd78cfaesaxe return (0);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Return non-zero if the bitset is empty.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe for (i = 0; i < b->bs_words; i++)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (b->bs_set[i] != 0)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (1);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Perform a non-victimizing search for a set bit in a word.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * A "seed" is passed to pseudo-randomize the search.
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Return -1 if no set bit was found.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe if (w == (ulong_t)0)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe rotated_word = (w >> rotate_bit) | (w << (BT_NBIPUL - rotate_bit));
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Select a bit that is set in the bitset in a non-victimizing fashion
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * (e.g. doesn't bias the low/high order bits/words).
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Return -1 if no set bit was found
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe if (++i == b->bs_words)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe } while (i != start);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * AND, OR, and XOR bitset computations, returns 1 if resulting bitset has any
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * set bits. Operands must have the same fanout, if any.
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh if ((res->bs_set[i] = (bs1->bs_set[i] & bs2->bs_set[i])) != 0)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh if ((res->bs_set[i] = (bs1->bs_set[i] | bs2->bs_set[i])) != 0)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh if ((res->bs_set[i] = (bs1->bs_set[i] ^ bs2->bs_set[i])) != 0)
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Return 1 if bitmaps are identical.
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh return (0);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh return (0);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh return (1);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Zero a bitset_t.
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Copy a bitset_t.