1 /* 2 * Copyright (c) 2000-2005 Silicon Graphics, Inc. 3 * All Rights Reserved. 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU General Public License as 7 * published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it would be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 #include "xfs.h" 19 #include "xfs_log_format.h" 20 #include "xfs_bit.h" 21 22 /* 23 * XFS bit manipulation routines, used in non-realtime code. 24 */ 25 26 /* 27 * Return whether bitmap is empty. 28 * Size is number of words in the bitmap, which is padded to word boundary 29 * Returns 1 for empty, 0 for non-empty. 30 */ 31 int 32 xfs_bitmap_empty(uint *map, uint size) 33 { 34 uint i; 35 uint ret = 0; 36 37 for (i = 0; i < size; i++) { 38 ret |= map[i]; 39 } 40 41 return (ret == 0); 42 } 43 44 /* 45 * Count the number of contiguous bits set in the bitmap starting with bit 46 * start_bit. Size is the size of the bitmap in words. 47 */ 48 int 49 xfs_contig_bits(uint *map, uint size, uint start_bit) 50 { 51 uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT); 52 uint result = 0; 53 uint tmp; 54 55 size <<= BIT_TO_WORD_SHIFT; 56 57 ASSERT(start_bit < size); 58 size -= start_bit & ~(NBWORD - 1); 59 start_bit &= (NBWORD - 1); 60 if (start_bit) { 61 tmp = *p++; 62 /* set to one first offset bits prior to start */ 63 tmp |= (~0U >> (NBWORD-start_bit)); 64 if (tmp != ~0U) 65 goto found; 66 result += NBWORD; 67 size -= NBWORD; 68 } 69 while (size) { 70 if ((tmp = *p++) != ~0U) 71 goto found; 72 result += NBWORD; 73 size -= NBWORD; 74 } 75 return result - start_bit; 76 found: 77 return result + ffz(tmp) - start_bit; 78 } 79 80 /* 81 * This takes the bit number to start looking from and 82 * returns the next set bit from there. It returns -1 83 * if there are no more bits set or the start bit is 84 * beyond the end of the bitmap. 85 * 86 * Size is the number of words, not bytes, in the bitmap. 87 */ 88 int xfs_next_bit(uint *map, uint size, uint start_bit) 89 { 90 uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT); 91 uint result = start_bit & ~(NBWORD - 1); 92 uint tmp; 93 94 size <<= BIT_TO_WORD_SHIFT; 95 96 if (start_bit >= size) 97 return -1; 98 size -= result; 99 start_bit &= (NBWORD - 1); 100 if (start_bit) { 101 tmp = *p++; 102 /* set to zero first offset bits prior to start */ 103 tmp &= (~0U << start_bit); 104 if (tmp != 0U) 105 goto found; 106 result += NBWORD; 107 size -= NBWORD; 108 } 109 while (size) { 110 if ((tmp = *p++) != 0U) 111 goto found; 112 result += NBWORD; 113 size -= NBWORD; 114 } 115 return -1; 116 found: 117 return result + ffs(tmp) - 1; 118 } 119