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