xref: /titanic_53/usr/src/uts/common/os/bitset.c (revision fb2f18f820d90b001aea4fb27dd654bc1263c440)

/*
 * 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 2007 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

#include <sys/bitset.h>
#include <sys/kmem.h>
#include <sys/systm.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));
}

/*
 * 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 sz number of bits.
 * 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 sz)
{
	uint_t	nwords;
	ulong_t	*bset_new, *bset_tmp;

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

	/*
	 * Allocate the new ulong_t array, and copy the old one.
	 */
	if (nwords > 0) {
		bset_new = kmem_zalloc(nwords * sizeof (ulong_t), KM_SLEEP);
		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 */
	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 and delete bits in the bitset.
 *
 * Adding a bit that is already set, and clearing 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)
{
	ASSERT(b->bs_words * BT_NBIPUL > elt);

	BT_SET(b->bs_set, elt);
}

void
bitset_del(bitset_t *b, uint_t elt)
{
	ASSERT(b->bs_words * BT_NBIPUL > elt);

	BT_CLEAR(b->bs_set, elt);
}

/*
 * Return non-zero if the bit is present in the set
 */
int
bitset_in_set(bitset_t *b, uint_t elt)
{
	ASSERT(b->bs_words * BT_NBIPUL > elt);

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

/*
 * 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);
}

/*
 * Find the first set bit in the bitset
 * Return -1 if no bit was found
 */
uint_t
bitset_find(bitset_t *b)
{
	uint_t	i;
	uint_t	elt = (uint_t)-1;

	for (i = 0; i < b->bs_words; i++) {
		elt = (uint_t)(lowbit(b->bs_set[i]) - 1);
		if (elt != (uint_t)-1) {
			elt += i * BT_NBIPUL;
			break;
		}
	}
	return (elt);
}