[thirdparty/xfsprogs-dev.git] / libxfs / xfs_bit.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
 * All Rights Reserved.
 */
#include "libxfs_priv.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
37b3b4d6	1	// SPDX-License-Identifier: GPL-2.0
4071f725 DC	2	/*
	3	* Copyright (c) 2000-2005 Silicon Graphics, Inc.
	4	* All Rights Reserved.
4071f725 DC	5	*/
	6	#include "libxfs_priv.h"
	7	#include "xfs_log_format.h"
	8	#include "xfs_bit.h"
	9
	10	/*
	11	* XFS bit manipulation routines, used in non-realtime code.
	12	*/
	13
	14	/*
	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.
	18	*/
	19	int
	20	xfs_bitmap_empty(uint *map, uint size)
	21	{
	22	uint i;
4071f725 DC	23
4071f725 DC	24	for (i = 0; i < size; i++) {
c5c9f532 JH	25	if (map[i] != 0)
c5c9f532 JH	26	return 0;
4071f725 DC	27	}
4071f725 DC	28
c5c9f532	29	return 1;
4071f725 DC	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	}