107 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (c) 2000-2005 Silicon Graphics, Inc.4 * All Rights Reserved.5 */6#include "xfs.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 boundary17 * Returns 1 for empty, 0 for non-empty.18 */19int20xfs_bitmap_empty(uint *map, uint size)21{22 uint i;23 24 for (i = 0; i < size; i++) {25 if (map[i] != 0)26 return 0;27 }28 29 return 1;30}31 32/*33 * Count the number of contiguous bits set in the bitmap starting with bit34 * start_bit. Size is the size of the bitmap in words.35 */36int37xfs_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;64found:65 return result + ffz(tmp) - start_bit;66}67 68/*69 * This takes the bit number to start looking from and70 * returns the next set bit from there. It returns -171 * if there are no more bits set or the start bit is72 * beyond the end of the bitmap.73 *74 * Size is the number of words, not bytes, in the bitmap.75 */76int 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;104found:105 return result + ffs(tmp) - 1;106}107