[linux-2.6-block.git] / fs / xfs / libxfs / xfs_bit.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
 * All Rights Reserved.
 */
#include "xfs.h"
#include "xfs_log_format.h"
#include "xfs_bit.h"

/*
 * XFS bit manipulation routines, used in non-realtime code.
 */

/*
 * Return whether bitmap is empty.
 * Size is number of words in the bitmap, which is padded to word boundary
 * Returns 1 for empty, 0 for non-empty.
 */
int
xfs_bitmap_empty(uint *map, uint size)
{
	uint i;

	for (i = 0; i < size; i++) {
		if (map[i] != 0)
			return 0;
	}

	return 1;
}

/*
 * Count the number of contiguous bits set in the bitmap starting with bit
 * start_bit.  Size is the size of the bitmap in words.
 */
int
xfs_contig_bits(uint *map, uint	size, uint start_bit)
{
	uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
	uint result = 0;
	uint tmp;

	size <<= BIT_TO_WORD_SHIFT;

	ASSERT(start_bit < size);
	size -= start_bit & ~(NBWORD - 1);
	start_bit &= (NBWORD - 1);
	if (start_bit) {
		tmp = *p++;
		/* set to one first offset bits prior to start */
		tmp |= (~0U >> (NBWORD-start_bit));
		if (tmp != ~0U)
			goto found;
		result += NBWORD;
		size -= NBWORD;
	}
	while (size) {
		if ((tmp = *p++) != ~0U)
			goto found;
		result += NBWORD;
		size -= NBWORD;
	}
	return result - start_bit;
found:
	return result + ffz(tmp) - start_bit;
}

/*
 * This takes the bit number to start looking from and
 * returns the next set bit from there.  It returns -1
 * if there are no more bits set or the start bit is
 * beyond the end of the bitmap.
 *
 * Size is the number of words, not bytes, in the bitmap.
 */
int xfs_next_bit(uint *map, uint size, uint start_bit)
{
	uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
	uint result = start_bit & ~(NBWORD - 1);
	uint tmp;

	size <<= BIT_TO_WORD_SHIFT;

	if (start_bit >= size)
		return -1;
	size -= result;
	start_bit &= (NBWORD - 1);
	if (start_bit) {
		tmp = *p++;
		/* set to zero first offset bits prior to start */
		tmp &= (~0U << start_bit);
		if (tmp != 0U)
			goto found;
		result += NBWORD;
		size -= NBWORD;
	}
	while (size) {
		if ((tmp = *p++) != 0U)
			goto found;
		result += NBWORD;
		size -= NBWORD;
	}
	return -1;
found:
	return result + ffs(tmp) - 1;
}
Commit	Line	Data
0b61f8a4	1	// SPDX-License-Identifier: GPL-2.0
1da177e4	2	/*
7b718769 NS	3	* Copyright (c) 2000-2005 Silicon Graphics, Inc.
7b718769 NS	4	* All Rights Reserved.
1da177e4	5	*/
1da177e4	6	#include "xfs.h"
239880ef	7	#include "xfs_log_format.h"
5f213ddb	8	#include "xfs_bit.h"
1da177e4	9
7b718769 NS	10	/*
	11	* XFS bit manipulation routines, used in non-realtime code.
	12	*/
1da177e4	13
1da177e4	14	/*
24ad33ff ES	15	* Return whether bitmap is empty.
	16	* Size is number of words in the bitmap, which is padded to word boundary
	17	* Returns 1 for empty, 0 for non-empty.
1da177e4 LT	18	*/
1da177e4 LT	19	int
24ad33ff	20	xfs_bitmap_empty(uint *map, uint size)
1da177e4	21	{
24ad33ff	22	uint i;
1da177e4	23
24ad33ff	24	for (i = 0; i < size; i++) {
1d4292bf JH	25	if (map[i] != 0)
1d4292bf JH	26	return 0;
1da177e4 LT	27	}
1da177e4 LT	28
1d4292bf	29	return 1;
1da177e4 LT	30	}
	31
	32	/*
	33	* Count the number of contiguous bits set in the bitmap starting with bit
	34	* start_bit. Size is the size of the bitmap in words.
	35	*/
	36	int
	37	xfs_contig_bits(uint *map, uint size, uint start_bit)
	38	{
	39	uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
	40	uint result = 0;
	41	uint tmp;
	42
	43	size <<= BIT_TO_WORD_SHIFT;
	44
	45	ASSERT(start_bit < size);
	46	size -= start_bit & ~(NBWORD - 1);
	47	start_bit &= (NBWORD - 1);
	48	if (start_bit) {
	49	tmp = *p++;
	50	/* set to one first offset bits prior to start */
	51	tmp \|= (~0U >> (NBWORD-start_bit));
	52	if (tmp != ~0U)
	53	goto found;
	54	result += NBWORD;
	55	size -= NBWORD;
	56	}
	57	while (size) {
	58	if ((tmp = *p++) != ~0U)
	59	goto found;
	60	result += NBWORD;
	61	size -= NBWORD;
	62	}
	63	return result - start_bit;
	64	found:
	65	return result + ffz(tmp) - start_bit;
	66	}
	67
	68	/*
	69	* This takes the bit number to start looking from and
	70	* returns the next set bit from there. It returns -1
	71	* if there are no more bits set or the start bit is
	72	* beyond the end of the bitmap.
	73	*
	74	* Size is the number of words, not bytes, in the bitmap.
	75	*/
	76	int xfs_next_bit(uint *map, uint size, uint start_bit)
	77	{
	78	uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
	79	uint result = start_bit & ~(NBWORD - 1);
	80	uint tmp;
	81
	82	size <<= BIT_TO_WORD_SHIFT;
	83
	84	if (start_bit >= size)
	85	return -1;
	86	size -= result;
	87	start_bit &= (NBWORD - 1);
	88	if (start_bit) {
	89	tmp = *p++;
	90	/* set to zero first offset bits prior to start */
	91	tmp &= (~0U << start_bit);
	92	if (tmp != 0U)
	93	goto found;
94	result += NBWORD;
95	size -= NBWORD;
96	}
97	while (size) {
98	if ((tmp = *p++) != 0U)
99	goto found;
100	result += NBWORD;
101	size -= NBWORD;
102	}
103	return -1;
104	found:
105	return result + ffs(tmp) - 1;
106	}