common/os/bitset.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
 */

#include <sys/bitset.h>
#include <sys/kmem.h>
#include <sys/systm.h>
#include <sys/cpuvar.h>
#include <sys/cmn_err.h>
#include <sys/sysmacros.h>

/*
 * Initialize a bitset_t.
 * After bitset_init(), the bitset will be zero sized.
 */
void
bitset_init(bitset_t *b)
{
	bzero(b, sizeof (bitset_t));
}

/*
 * Initialize a bitset_t using a fanout. The fanout factor is platform
 * specific and passed in as a power of two.
 */
void
bitset_init_fanout(bitset_t *b, uint_t fanout)
{
	bzero(b, sizeof (bitset_t));
	b->bs_fanout = fanout;
}

/*
 * Uninitialize a bitset_t.
 * This will free the bitset's data, leaving it zero sized.
 */
void
bitset_fini(bitset_t *b)
{
	if (b->bs_words > 0)
		kmem_free(b->bs_set, b->bs_words * sizeof (ulong_t));
}

/*
 * Resize a bitset to where it can hold els number of elements.
 * This can either grow or shrink the bitset holding capacity.
 * In the case of shrinkage, elements that reside outside the new
 * holding capacity of the bitset are lost.
 */
void
bitset_resize(bitset_t *b, uint_t els)
{
	uint_t	nwords;
	ulong_t	*bset_new, *bset_tmp;

	nwords = BT_BITOUL(els << b->bs_fanout);
	if (b->bs_words == nwords)
		return;	/* already properly sized */

	/*
	 * Allocate the new ulong_t array, and copy the old one, if there
	 * was an old one.
	 */
	if (nwords > 0) {
		bset_new = kmem_zalloc(nwords * sizeof (ulong_t), KM_SLEEP);
		if (b->bs_words > 0)
			bcopy(b->bs_set, bset_new,
			    MIN(b->bs_words, nwords) * sizeof (ulong_t));
	} else {
		bset_new = NULL;
	}

	/* swap out the old ulong_t array for new one */
	bset_tmp = b->bs_set;
	b->bs_set = bset_new;

	/* free up the old array */
	if (b->bs_words > 0)
		kmem_free(bset_tmp, b->bs_words * sizeof (ulong_t));

	b->bs_words = nwords;
}

/*
 * Returns the current holding capacity of the bitset.
 */
uint_t
bitset_capacity(bitset_t *b)
{
	return (b->bs_words * BT_NBIPUL);
}

/*
 * Add (set) and delete (clear) bits in the bitset.
 *
 * Adding a bit that is already set, or removing a bit that's already clear
 * is legal.
 *
 * Adding or deleting an element that falls outside the bitset's current
 * holding capacity is illegal.
 */
void
bitset_add(bitset_t *b, uint_t elt)
{
	uint_t pos = (elt << b->bs_fanout);

	ASSERT(b->bs_words * BT_NBIPUL > pos);
	BT_SET(b->bs_set, pos);
}

/*
 * Set a bit in an atomically safe way.
 */
void
bitset_atomic_add(bitset_t *b, uint_t elt)
{
	uint_t pos = (elt << b->bs_fanout);

	ASSERT(b->bs_words * BT_NBIPUL > pos);
	BT_ATOMIC_SET(b->bs_set, pos);
}

/*
 * Atomically test that a given bit isn't set, and set it.
 * Returns -1 if the bit was already set.
 */
int
bitset_atomic_test_and_add(bitset_t *b, uint_t elt)
{
	uint_t pos = (elt << b->bs_fanout);
	int ret;

	ASSERT(b->bs_words * BT_NBIPUL > pos);
	BT_ATOMIC_SET_EXCL(b->bs_set, pos, ret);

	return (ret);
}

/*
 * Clear a bit.
 */
void
bitset_del(bitset_t *b, uint_t elt)
{
	uint_t pos = (elt << b->bs_fanout);

	ASSERT(b->bs_words * BT_NBIPUL > pos);
	BT_CLEAR(b->bs_set, pos);
}

/*
 * Clear a bit in an atomically safe way.
 */
void
bitset_atomic_del(bitset_t *b, uint_t elt)
{
	uint_t pos = (elt << b->bs_fanout);

	ASSERT(b->bs_words * BT_NBIPUL > pos);
	BT_ATOMIC_CLEAR(b->bs_set, pos);
}

/*
 * Atomically test that a bit is set, and clear it.
 * Returns -1 if the bit was already clear.
 */
int
bitset_atomic_test_and_del(bitset_t *b, uint_t elt)
{
	uint_t pos = (elt << b->bs_fanout);
	int ret;

	ASSERT(b->bs_words * BT_NBIPUL > pos);
	BT_ATOMIC_CLEAR_EXCL(b->bs_set, pos, ret);

	return (ret);
}

/*
 * Return non-zero if the bit is present in the set.
 */
int
bitset_in_set(bitset_t *b, uint_t elt)
{
	uint_t pos = (elt << b->bs_fanout);

	if (pos >= b->bs_words * BT_NBIPUL)
		return (0);

	return (BT_TEST(b->bs_set, pos));
}

/*
 * Return non-zero if the bitset is empty.
 */
int
bitset_is_null(bitset_t *b)
{
	int i;

	for (i = 0; i < b->bs_words; i++)
		if (b->bs_set[i] != 0)
			return (0);
	return (1);
}

/*
 * Perform a non-victimizing search for a set bit in a word.
 * A "seed" is passed to pseudo-randomize the search.
 * Return -1 if no set bit was found.
 */
static uint_t
bitset_find_in_word(ulong_t w, uint_t seed)
{
	uint_t rotate_bit, elt = (uint_t)-1;
	ulong_t rotated_word;

	if (w == (ulong_t)0)
		return (elt);

	rotate_bit = seed % BT_NBIPUL;
	rotated_word = (w >> rotate_bit) | (w << (BT_NBIPUL - rotate_bit));
	elt = (uint_t)(lowbit(rotated_word) - 1);
	if (elt != (uint_t)-1)
		elt = ((elt + rotate_bit) % BT_NBIPUL);

	return (elt);
}

/*
 * Select a bit that is set in the bitset in a non-victimizing fashion
 * (e.g. doesn't bias the low/high order bits/words).
 * Return -1 if no set bit was found
 */
uint_t
bitset_find(bitset_t *b)
{
	uint_t start, i;
	uint_t elt = (uint_t)-1;
	uint_t seed;

	seed = CPU_PSEUDO_RANDOM();

	ASSERT(b->bs_words > 0);
	start = seed % b->bs_words;

	i = start;
	do {
		elt = bitset_find_in_word(b->bs_set[i], seed);
		if (elt != (uint_t)-1) {
			elt += i * BT_NBIPUL;
			return (elt >> b->bs_fanout);
		}
		if (++i == b->bs_words)
			i = 0;
	} while (i != start);

	return (elt);
}

/*
 * AND, OR, and XOR bitset computations, returns 1 if resulting bitset has any
 * set bits. Operands must have the same fanout, if any.
 */
int
bitset_and(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
{
	int i, anyset;

	ASSERT(bs1->bs_fanout == bs2->bs_fanout);
	ASSERT(bs1->bs_fanout == res->bs_fanout);

	for (anyset = 0, i = 0; i < bs1->bs_words; i++) {
		if ((res->bs_set[i] = (bs1->bs_set[i] & bs2->bs_set[i])) != 0)
			anyset = 1;
	}
	return (anyset);
}

int
bitset_or(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
{
	int i, anyset;

	ASSERT(bs1->bs_fanout == bs2->bs_fanout);
	ASSERT(bs1->bs_fanout == res->bs_fanout);

	for (anyset = 0, i = 0; i < bs1->bs_words; i++) {
		if ((res->bs_set[i] = (bs1->bs_set[i] | bs2->bs_set[i])) != 0)
			anyset = 1;
	}
	return (anyset);
}

int
bitset_xor(bitset_t *bs1, bitset_t *bs2, bitset_t *res)
{
	int i, anyset = 0;

	ASSERT(bs1->bs_fanout == bs2->bs_fanout);
	ASSERT(bs1->bs_fanout == res->bs_fanout);

	for (i = 0; i < bs1->bs_words; i++) {
		if ((res->bs_set[i] = (bs1->bs_set[i] ^ bs2->bs_set[i])) != 0)
			anyset = 1;
	}
	return (anyset);
}

/*
 * Return 1 if bitmaps are identical.
 */
int
bitset_match(bitset_t *bs1, bitset_t *bs2)
{
	int i;

	if (bs1->bs_words != bs2->bs_words)
		return (0);

	for (i = 0; i < bs1->bs_words; i++)
		if (bs1->bs_set[i] != bs2->bs_set[i])
			return (0);
	return (1);
}

/*
 * Zero a bitset_t.
 */
void
bitset_zero(bitset_t *b)
{
	bzero(b->bs_set, sizeof (ulong_t) * b->bs_words);
}

/*
 * Copy a bitset_t.
 */
void
bitset_copy(bitset_t *src, bitset_t *dest)
{
	ASSERT(src->bs_fanout == dest->bs_fanout);
	bcopy(src->bs_set, dest->bs_set, sizeof (ulong_t) * src->bs_words);
}