fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * CDDL HEADER START
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
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 *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * or http://www.opensolaris.org/os/licensing.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * See the License for the specific language governing permissions
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * and limitations under the License.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
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 *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * CDDL HEADER END
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/bitset.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/kmem.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/systm.h>
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe#include <sys/cpuvar.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/cmn_err.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe#include <sys/sysmacros.h>
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Initialize a bitset_t.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * After bitset_init(), the bitset will be zero sized.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxebitset_init(bitset_t *b)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe bzero(b, sizeof (bitset_t));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni/*
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.
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni */
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanonivoid
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanonibitset_init_fanout(bitset_t *b, uint_t fanout)
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni bzero(b, sizeof (bitset_t));
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni b->bs_fanout = fanout;
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni}
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Uninitialize a bitset_t.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * This will free the bitset's data, leaving it zero sized.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxebitset_fini(bitset_t *b)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (b->bs_words > 0)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe kmem_free(b->bs_set, b->bs_words * sizeof (ulong_t));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
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 */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanonibitset_resize(bitset_t *b, uint_t els)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe uint_t nwords;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe ulong_t *bset_new, *bset_tmp;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni nwords = BT_BITOUL(els << b->bs_fanout);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (b->bs_words == nwords)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return; /* already properly sized */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /*
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Allocate the new ulong_t array, and copy the old one, if there
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * was an old one.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (nwords > 0) {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe bset_new = kmem_zalloc(nwords * sizeof (ulong_t), KM_SLEEP);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe if (b->bs_words > 0)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe bcopy(b->bs_set, bset_new,
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe MIN(b->bs_words, nwords) * sizeof (ulong_t));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe } else {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe bset_new = NULL;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe }
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /* swap out the old ulong_t array for new one */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe bset_tmp = b->bs_set;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe b->bs_set = bset_new;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe /* free up the old array */
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe if (b->bs_words > 0)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe kmem_free(bset_tmp, b->bs_words * sizeof (ulong_t));
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe b->bs_words = nwords;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Returns the current holding capacity of the bitset.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxeuint_t
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxebitset_capacity(bitset_t *b)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (b->bs_words * BT_NBIPUL);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Add (set) and delete (clear) bits in the bitset.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Adding a bit that is already set, or removing a bit that's already clear
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * is legal.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe *
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * Adding or deleting an element that falls outside the bitset's current
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe * holding capacity is illegal.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxebitset_add(bitset_t *b, uint_t elt)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni uint_t pos = (elt << b->bs_fanout);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(b->bs_words * BT_NBIPUL > pos);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni BT_SET(b->bs_set, pos);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Set a bit in an atomically safe way.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe */
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxevoid
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxebitset_atomic_add(bitset_t *b, uint_t elt)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni uint_t pos = (elt << b->bs_fanout);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(b->bs_words * BT_NBIPUL > pos);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni BT_ATOMIC_SET(b->bs_set, pos);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe}
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe/*
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 Saxe */
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxeint
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxebitset_atomic_test_and_add(bitset_t *b, uint_t elt)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni uint_t pos = (elt << b->bs_fanout);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni int ret;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(b->bs_words * BT_NBIPUL > pos);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni BT_ATOMIC_SET_EXCL(b->bs_set, pos, ret);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni return (ret);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe}
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Clear a bit.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxevoid
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxebitset_del(bitset_t *b, uint_t elt)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni uint_t pos = (elt << b->bs_fanout);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(b->bs_words * BT_NBIPUL > pos);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni BT_CLEAR(b->bs_set, pos);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Clear a bit in an atomically safe way.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe */
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxevoid
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxebitset_atomic_del(bitset_t *b, uint_t elt)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni uint_t pos = (elt << b->bs_fanout);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(b->bs_words * BT_NBIPUL > pos);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni BT_ATOMIC_CLEAR(b->bs_set, pos);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe}
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe/*
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Atomically test that a bit is set, and clear it.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe * Returns -1 if the bit was already clear.
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe */
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxeint
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxebitset_atomic_test_and_del(bitset_t *b, uint_t elt)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni uint_t pos = (elt << b->bs_fanout);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni int ret;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(b->bs_words * BT_NBIPUL > pos);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni BT_ATOMIC_CLEAR_EXCL(b->bs_set, pos, ret);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni return (ret);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe}
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Return non-zero if the bit is present in the set.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxeint
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxebitset_in_set(bitset_t *b, uint_t elt)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni uint_t pos = (elt << b->bs_fanout);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni if (pos >= b->bs_words * BT_NBIPUL)
0f424180e3b253cef8b25600a32523677cd78cfaesaxe return (0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni return (BT_TEST(b->bs_set, pos));
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Return non-zero if the bitset is empty.
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxeint
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxebitset_is_null(bitset_t *b)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni int i;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe for (i = 0; i < b->bs_words; i++)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (b->bs_set[i] != 0)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (0);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (1);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe/*
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 */
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxestatic uint_t
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxebitset_find_in_word(ulong_t w, uint_t seed)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe{
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe uint_t rotate_bit, elt = (uint_t)-1;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe ulong_t rotated_word;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe if (w == (ulong_t)0)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe return (elt);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe rotate_bit = seed % BT_NBIPUL;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe rotated_word = (w >> rotate_bit) | (w << (BT_NBIPUL - rotate_bit));
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe elt = (uint_t)(lowbit(rotated_word) - 1);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe if (elt != (uint_t)-1)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe elt = ((elt + rotate_bit) % BT_NBIPUL);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe return (elt);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe}
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe/*
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
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe */
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxeuint_t
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxebitset_find(bitset_t *b)
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe{
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe uint_t start, i;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe uint_t elt = (uint_t)-1;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe uint_t seed;
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe seed = CPU_PSEUDO_RANDOM();
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(b->bs_words > 0);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe start = seed % b->bs_words;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe i = start;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe do {
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe elt = bitset_find_in_word(b->bs_set[i], seed);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe if (elt != (uint_t)-1) {
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe elt += i * BT_NBIPUL;
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni return (elt >> b->bs_fanout);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe }
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe if (++i == b->bs_words)
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe i = 0;
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe } while (i != start);
6890d023cce317bfcb74d7e43a813d060ebd2e47Eric Saxe
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe return (elt);
fb2f18f820d90b001aea4fb27dd654bc1263c440esaxe}
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh/*
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 */
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhint
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhbitset_and(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh{
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh int i, anyset;
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(bs1->bs_fanout == bs2->bs_fanout);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(bs1->bs_fanout == res->bs_fanout);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh for (anyset = 0, i = 0; i < bs1->bs_words; i++) {
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh if ((res->bs_set[i] = (bs1->bs_set[i] & bs2->bs_set[i])) != 0)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh anyset = 1;
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh }
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh return (anyset);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh}
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhint
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhbitset_or(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh{
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh int i, anyset;
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(bs1->bs_fanout == bs2->bs_fanout);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(bs1->bs_fanout == res->bs_fanout);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh for (anyset = 0, i = 0; i < bs1->bs_words; i++) {
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh if ((res->bs_set[i] = (bs1->bs_set[i] | bs2->bs_set[i])) != 0)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh anyset = 1;
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh }
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh return (anyset);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh}
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhint
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhbitset_xor(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni int i, anyset = 0;
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(bs1->bs_fanout == bs2->bs_fanout);
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(bs1->bs_fanout == res->bs_fanout);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh for (i = 0; i < bs1->bs_words; i++) {
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh if ((res->bs_set[i] = (bs1->bs_set[i] ^ bs2->bs_set[i])) != 0)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh anyset = 1;
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh }
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh return (anyset);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh}
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Return 1 if bitmaps are identical.
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh */
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhint
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhbitset_match(bitset_t *bs1, bitset_t *bs2)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh{
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh int i;
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh if (bs1->bs_words != bs2->bs_words)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh return (0);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh for (i = 0; i < bs1->bs_words; i++)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh if (bs1->bs_set[i] != bs2->bs_set[i])
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh return (0);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh return (1);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh}
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Zero a bitset_t.
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh */
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhvoid
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhbitset_zero(bitset_t *b)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh{
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh bzero(b->bs_set, sizeof (ulong_t) * b->bs_words);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh}
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh/*
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni * Copy a bitset_t.
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh */
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhvoid
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dhbitset_copy(bitset_t *src, bitset_t *dest)
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh{
0542eecf8a04bde577ee69151dfe367a36053e40Rafael Vanoni ASSERT(src->bs_fanout == dest->bs_fanout);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh bcopy(src->bs_set, dest->bs_set, sizeof (ulong_t) * src->bs_words);
4c06356b0f0fffb4fc1b6eccc8e5d8e2254a84d6dh}