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