1 files changed, 244 insertions, 0 deletions
diff --git a/usr/src/uts/common/os/bitmap.c b/usr/src/uts/common/os/bitmap.c
new file mode 100644
index 0000000000..46fae44adb
--- /dev/null
+++ b/usr/src/uts/common/os/bitmap.c
@@ -0,0 +1,244 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License, Version 1.0 only
+ * (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) 1984, 1986, 1987, 1988, 1989 AT&T	*/
+/*	  All Rights Reserved  	*/
+
+
+/*
+ * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#pragma ident	"%Z%%M%	%I%	%E% SMI"
+
+/*
+ * Operations on bitmaps of arbitrary size
+ * A bitmap is a vector of 1 or more ulongs.
+ * The user of the package is responsible for range checks and keeping
+ * track of sizes.
+ */
+
+#include <sys/types.h>
+#include <sys/bitmap.h>
+#include <sys/debug.h>		/* ASSERT */
+
+/*
+ * Return index of first available bit in denoted bitmap, or -1 for
+ * failure.  Size is the cardinality of the bitmap; that is, the
+ * number of bits.
+ * No side-effects.  In particular, does not update bitmap.
+ * Caller is responsible for range checks.
+ */
+index_t
+bt_availbit(ulong_t *bitmap, size_t nbits)
+{
+	index_t	maxword;	/* index of last in map */
+	index_t	wx;		/* word index in map */
+
+	/*
+	 * Look for a word with a bit off.
+	 * Subtract one from nbits because we're converting it to a
+	 * a range of indices.
+	 */
+	nbits -= 1;
+	maxword = nbits >> BT_ULSHIFT;
+	for (wx = 0; wx <= maxword; wx++)
+		if (bitmap[wx] != ~0)
+			break;
+
+	if (wx <= maxword) {
+		/*
+		 * Found a word with a bit off.  Now find the bit in the word.
+		 */
+		index_t	bx;	/* bit index in word */
+		index_t	maxbit; /* last bit to look at */
+		ulong_t		word;
+		ulong_t		bit;
+
+		maxbit = wx == maxword ? nbits & BT_ULMASK : BT_NBIPUL - 1;
+		word = bitmap[wx];
+		bit = 1;
+		for (bx = 0; bx <= maxbit; bx++, bit <<= 1) {
+			if (!(word & bit)) {
+				return (wx << BT_ULSHIFT | bx);
+			}
+		}
+	}
+	return (-1);
+}
+
+
+/*
+ * Find highest order bit that is on, and is within or below
+ * the word specified by wx.
+ */
+int
+bt_gethighbit(ulong_t *mapp, int wx)
+{
+	ulong_t word;
+
+	while ((word = mapp[wx]) == 0) {
+		wx--;
+		if (wx < 0) {
+			return (-1);
+		}
+	}
+	return (wx << BT_ULSHIFT | (highbit(word) - 1));
+}
+
+
+/*
+ * Search the bitmap for a consecutive pattern of 1's.
+ * Search starts at position pos1.
+ * Returns 1 on success and 0 on failure.
+ * Side effects.
+ * Returns indices to the first bit (pos1)
+ * and one past the last bit (pos2) in the pattern.
+ */
+int
+bt_range(ulong_t *bitmap, size_t *pos1, size_t *pos2, size_t end_pos)
+{
+	size_t pos;
+
+	for (pos = *pos1; pos < end_pos; pos++)
+		if (BT_TEST(bitmap, pos))
+			break;
+
+	if (pos == end_pos)
+		return (0);
+
+	*pos1 = pos;
+
+	for (; pos < end_pos; pos++)
+		if (!BT_TEST(bitmap, pos))
+			break;
+	*pos2 = pos;
+
+	return (1);
+}
+
+
+/*
+ * return the parity of the supplied long
+ *
+ * this works by successively partitioning the argument in half, and
+ * setting the parity of the result to the parity of the 2 halfs, until
+ * only one bit is left
+ */
+int
+odd_parity(ulong_t i)
+{
+#ifdef _LP64
+	i ^= i >> 32;
+#endif
+	i ^= i >> 16;
+	i ^= i >> 8;
+	i ^= i >> 4;
+	i ^= i >> 2;
+	i ^= i >> 1;
+
+	return (i & 0x01);
+}
+
+
+/*
+ * get the lowest bit in the range of 'start' and 'stop', inclusive.
+ * I.e., if caller calls bt_getlowbit(map, X, Y), any value between X and Y,
+ * including X and Y can be returned.
+ * Neither start nor stop is required to align with word boundaries.
+ * If a bit is set in the range, the bit position is returned; otherwise,
+ * a -1 is returned.
+ */
+int
+bt_getlowbit(ulong_t *map, size_t start, size_t stop)
+{
+	ulong_t		word;
+	int		counter = start >> BT_ULSHIFT;
+	int		limit = stop >> BT_ULSHIFT;
+	index_t		partial_start = start & BT_ULMASK;
+	index_t		partial_stop = stop & BT_ULMASK;
+
+	if (start > stop) {
+		return (-1);
+	}
+
+	/*
+	 * The range between 'start' and 'stop' can be very large, and the
+	 * '1' bits in this range can be sparse.
+	 * For performance reason, the underlying implementation operates
+	 * on words, not on bits.
+	 */
+	word = map[counter];
+
+	if (partial_start) {
+		/*
+		 * Since the start is not aligned on word boundary, we
+		 * need to patch the unwanted low order bits with 0's before
+		 * operating on the first bitmap word.
+		 */
+		word = word & (BT_ULMAXMASK << partial_start);
+	}
+
+	/*
+	 * Locate a word from the map array with one of the bits set.
+	 */
+
+	while ((word == 0) && (counter < limit)) {
+		word = map[++counter];
+	}
+
+	/*
+	 * The end of range has similar problems if it is not aligned.
+	 * Taking care of the end which is not aligned.
+	 */
+
+	if ((counter == limit) && (partial_stop != BT_ULMASK)) {
+		/*
+		 * Take care the partial word by patch the high order
+		 * bits with 0's. Here we dealing with the case that
+		 * the last word of the bitmap is not aligned.
+		 */
+
+		ASSERT(partial_stop < BT_ULMASK);
+		word = word & (~(BT_ULMAXMASK << partial_stop + 1));
+	}
+
+	/*
+	 * Examine the word.
+	 */
+	if (word == 0) {
+		return (-1);
+	} else {
+		return ((counter << BT_ULSHIFT) | (lowbit(word) - 1));
+	}
+}
+
+/*
+ * Copy the bitmap.
+ */
+void
+bt_copy(ulong_t *from, ulong_t *to, ulong_t size)
+{
+	ulong_t i;
+	for (i = 0; i < size; i++)
+		*to++ = *from++;
+}