WebSVN – Kolibri OS – Diff – /drivers/ddk/linux/bitmap.c

  * endian architectures.  See the big-endian headers
  * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
  * for the best explanations of this ordering.
  */
-int __bitmap_empty(const unsigned long *bitmap, unsigned int bits)
-{
-	unsigned int k, lim = bits/BITS_PER_LONG;
-	for (k = 0; k < lim; ++k)
-		if (bitmap[k])
-			return 0;
-	if (bits % BITS_PER_LONG)
-		if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
-			return 0;
-	return 1;
-}
-EXPORT_SYMBOL(__bitmap_empty);
-int __bitmap_full(const unsigned long *bitmap, unsigned int bits)
-{
-	unsigned int k, lim = bits/BITS_PER_LONG;
-	for (k = 0; k < lim; ++k)
-		if (~bitmap[k])
-			return 0;
-	if (bits % BITS_PER_LONG)
-		if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
-			return 0;
-	return 1;
-}
-EXPORT_SYMBOL(__bitmap_full);
 int __bitmap_equal(const unsigned long *bitmap1,
 		const unsigned long *bitmap2, unsigned int bits)
+{
 	unsigned int k, lim = bits/BITS_PER_LONG;
 /**
  * __bitmap_shift_right - logical right shift of the bits in a bitmap
  *   @dst : destination bitmap
  *   @src : source bitmap
  *   @shift : shift by this many bits
- *   @bits : bitmap size, in bits
+ *   @nbits : bitmap size, in bits
+ *
  * Shifting right (dividing) means moving bits in the MS -> LS bit
  * direction.  Zeros are fed into the vacated MS positions and the
  * LS bits shifted off the bottom are lost.
  */
-void __bitmap_shift_right(unsigned long *dst,
+void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
-			const unsigned long *src, int shift, int bits)
+			unsigned shift, unsigned nbits)
+{
-	int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
+	unsigned k, lim = BITS_TO_LONGS(nbits);
-	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+	unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
-	unsigned long mask = (1UL << left) - 1;
+	unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
 	for (k = 0; off + k < lim; ++k) {
 		unsigned long upper, lower;
 		/*
 		 */
 		if (!rem || off + k + 1 >= lim)
 			upper = 0;
 		else {
 			upper = src[off + k + 1];
-			if (off + k + 1 == lim - 1 && left)
+			if (off + k + 1 == lim - 1)
 				upper &= mask;
+			upper <<= (BITS_PER_LONG - rem);
+		}
 		lower = src[off + k];
-		if (left && off + k == lim - 1)
+		if (off + k == lim - 1)
 			lower &= mask;
-		dst[k] = lower >> rem;
+		lower >>= rem;
-		if (rem)
-			dst[k] |= upper << (BITS_PER_LONG - rem);
-		if (left && k == lim - 1)
-			dst[k] &= mask;
+		dst[k] = lower | upper;
+	}
 	if (off)
 		memset(&dst[lim - off], 0, off*sizeof(unsigned long));
+}
 EXPORT_SYMBOL(__bitmap_shift_right);
 /**
  * __bitmap_shift_left - logical left shift of the bits in a bitmap
  *   @dst : destination bitmap
  *   @src : source bitmap
  *   @shift : shift by this many bits
- *   @bits : bitmap size, in bits
+ *   @nbits : bitmap size, in bits
+ *
  * Shifting left (multiplying) means moving bits in the LS -> MS
  * direction.  Zeros are fed into the vacated LS bit positions
  * and those MS bits shifted off the top are lost.
  */
-void __bitmap_shift_left(unsigned long *dst,
+void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
-			const unsigned long *src, int shift, int bits)
+			unsigned int shift, unsigned int nbits)
+{
-{
+	int k;
-	int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
+	unsigned int lim = BITS_TO_LONGS(nbits);
-	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+	unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
 	for (k = lim - off - 1; k >= 0; --k) {
 		unsigned long upper, lower;
 		/*
 		 * If shift is not word aligned, take upper rem bits of
 		 * word below and make them the bottom rem bits of result.
 		 */
 		if (rem && k > 0)
-			lower = src[k - 1];
+			lower = src[k - 1] >> (BITS_PER_LONG - rem);
 		else
-			lower = 0;
-		upper = src[k];
-		if (left && k == lim - 1)
+			lower = 0;
-			upper &= (1UL << left) - 1;
-		dst[k + off] = upper << rem;
-		if (rem)
-			dst[k + off] |= lower >> (BITS_PER_LONG - rem);
-		if (left && k + off == lim - 1)
+		upper = src[k] << rem;
-			dst[k + off] &= (1UL << left) - 1;
+		dst[k + off] = lower | upper;
+	}
 	if (off)
 		memset(dst, 0, off*sizeof(unsigned long));
 /**
  * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
  *	@buf: pointer to a bitmap
- *	@pos: a bit position in @buf (0 <= @pos < @bits)
+ *	@pos: a bit position in @buf (0 <= @pos < @nbits)
- *	@bits: number of valid bit positions in @buf
+ *	@nbits: number of valid bit positions in @buf
+ *
- * Map the bit at position @pos in @buf (of length @bits) to the
+ * Map the bit at position @pos in @buf (of length @nbits) to the
  * ordinal of which set bit it is.  If it is not set or if @pos
  * is not a valid bit position, map to -1.
+ *
  * gets mapped to (returns) @ord value 3 in this example, that means
  * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
+ *
  * The bit positions 0 through @bits are valid positions in @buf.
  */
-static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
+static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
+{
-	int i, ord;
-	if (pos < 0 || pos >= bits || !test_bit(pos, buf))
+	if (pos >= nbits || !test_bit(pos, buf))
 		return -1;
-	i = find_first_bit(buf, bits);
-	ord = 0;
-	while (i < pos) {
-		i = find_next_bit(buf, bits, i + 1);
-	     	ord++;
-	}
-	BUG_ON(i != pos);
-	return ord;
+	return __bitmap_weight(buf, pos);
+}
 /**
  * bitmap_ord_to_pos - find position of n-th set bit in bitmap
  *	@buf: pointer to bitmap
  *	@ord: ordinal bit position (n-th set bit, n >= 0)
- *	@bits: number of valid bit positions in @buf
+ *	@nbits: number of valid bit positions in @buf
  *
  * Map the ordinal offset of bit @ord in @buf to its position in @buf.
- * Value of @ord should be in range 0 <= @ord < weight(buf), else
+ * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord
- * results are undefined.
+ * >= weight(buf), returns @nbits.
+ *
  * If for example, just bits 4 through 7 are set in @buf, then @ord
  * values 0 through 3 will get mapped to 4 through 7, respectively,
- * and all other @ord values return undefined values.  When @ord value 3
+ * and all other @ord values returns @nbits.  When @ord value 3
  * gets mapped to (returns) @pos value 7 in this example, that means
  * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
+ *
- * The bit positions 0 through @bits are valid positions in @buf.
+ * The bit positions 0 through @nbits-1 are valid positions in @buf.
  */
-int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits)
+unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
-{
-	int pos = 0;
-	if (ord >= 0 && ord < bits) {
+{
-		int i;
+	unsigned int pos;
-		for (i = find_first_bit(buf, bits);
+	for (pos = find_first_bit(buf, nbits);
-		     i < bits && ord > 0;
-		     i = find_next_bit(buf, bits, i + 1))
-	     		ord--;
-		if (i < bits && ord == 0)
+	     pos < nbits && ord;
-			pos = i;
+	     pos = find_next_bit(buf, nbits, pos + 1))
 	     		ord--;
 	return pos;
+}
 /**
  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
  *	@dst: remapped result
  *	@src: subset to be remapped
  *	@old: defines domain of map
  *	@new: defines range of map
- *	@bits: number of bits in each of these bitmaps
+ *	@nbits: number of bits in each of these bitmaps
  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
  * 13 and 15 set.
  */
 void bitmap_remap(unsigned long *dst, const unsigned long *src,
 		const unsigned long *old, const unsigned long *new,
-		int bits)
+		unsigned int nbits)
+{
-	int oldbit, w;
+	unsigned int oldbit, w;
 	if (dst == src)		/* following doesn't handle inplace remaps */
 		return;
-	bitmap_zero(dst, bits);
+	bitmap_zero(dst, nbits);
-	w = bitmap_weight(new, bits);
+	w = bitmap_weight(new, nbits);
-	for_each_set_bit(oldbit, src, bits) {
+	for_each_set_bit(oldbit, src, nbits) {
-	     	int n = bitmap_pos_to_ord(old, oldbit, bits);
+		int n = bitmap_pos_to_ord(old, oldbit, nbits);
 		if (n < 0 || w == 0)
 			set_bit(oldbit, dst);	/* identity map */
 		else
-			set_bit(bitmap_ord_to_pos(new, n % w, bits), dst);
+			set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
+	}
  * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
  * (If you understood the previous sentence the first time your
  * read it, you're overqualified for your current job.)
+ *
  * In other words, @orig is mapped onto (surjectively) @dst,
- * using the the map {  | the n-th bit of @relmap is the
+ * using the map {  | the n-th bit of @relmap is the
  * m-th set bit of @relmap }.
+ *
  * Any set bits in @orig above bit number W, where W is the
  * weight of (number of set bits in) @relmap are mapped nowhere.
  * In particular, if for all bits m set in @orig, m >= W, then
  * once again be returned empty.
+ *
  * All bits in @dst not set by the above rule are cleared.
  */
 void bitmap_onto(unsigned long *dst, const unsigned long *orig,
-			const unsigned long *relmap, int bits)
+			const unsigned long *relmap, unsigned int bits)
+{
-	int n, m;       	/* same meaning as in above comment */
+	unsigned int n, m;	/* same meaning as in above comment */
 	if (dst == orig)	/* following doesn't handle inplace mappings */
 		return;
 /**
  * bitmap_fold - fold larger bitmap into smaller, modulo specified size
  *	@dst: resulting smaller bitmap
  *	@orig: original larger bitmap
  *	@sz: specified size
- *	@bits: number of bits in each of these bitmaps
+ *	@nbits: number of bits in each of these bitmaps
+ *
  * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
  * Clear all other bits in @dst.  See further the comment and
  * Example [2] for bitmap_onto() for why and how to use this.
  */
 void bitmap_fold(unsigned long *dst, const unsigned long *orig,
-			int sz, int bits)
+			unsigned int sz, unsigned int nbits)
+{
-	int oldbit;
+	unsigned int oldbit;
 	if (dst == orig)	/* following doesn't handle inplace mappings */
 		return;
-	bitmap_zero(dst, bits);
+	bitmap_zero(dst, nbits);
-	for_each_set_bit(oldbit, orig, bits)
+	for_each_set_bit(oldbit, orig, nbits)
 		set_bit(oldbit % sz, dst);
+}
  * @src:   bitmap to copy
  * @nbits: number of bits in the bitmap
+ *
  * Require nbits % BITS_PER_LONG == 0.
  */
+#ifdef __BIG_ENDIAN
-void bitmap_copy_le(void *dst, const unsigned long *src, int nbits)
+void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits)
+{
-	unsigned long *d = dst;
+	unsigned int i;
-	int i;
 	for (i = 0; i < nbits/BITS_PER_LONG; i++) {
 		if (BITS_PER_LONG == 64)
-			d[i] = cpu_to_le64(src[i]);
+			dst[i] = cpu_to_le64(src[i]);
 		else
-			d[i] = cpu_to_le32(src[i]);
+			dst[i] = cpu_to_le32(src[i]);
+	}
+}
+EXPORT_SYMBOL(bitmap_copy_le);

Subversion Repositories Kolibri OS

(root)/drivers/ddk/linux/bitmap.c – Rev 5270 → 6082