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_bit.h" 20#include "xfs_log.h" 21#include "xfs_trans.h" 22#include "xfs_buf_item.h" 23 24/* 25 * XFS bit manipulation routines, used in non-realtime code. 26 */ 27 28/* 29 * Return whether bitmap is empty. 30 * Size is number of words in the bitmap, which is padded to word boundary 31 * Returns 1 for empty, 0 for non-empty. 32 */ 33int 34xfs_bitmap_empty(uint *map, uint size) 35{ 36 uint i; 37 uint ret = 0; 38 39 for (i = 0; i < size; i++) { 40 ret |= map[i]; 41 } 42 43 return (ret == 0); 44} 45 46/* 47 * Count the number of contiguous bits set in the bitmap starting with bit 48 * start_bit. Size is the size of the bitmap in words. 49 */ 50int 51xfs_contig_bits(uint *map, uint size, uint start_bit) 52{ 53 uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT); 54 uint result = 0; 55 uint tmp; 56 57 size <<= BIT_TO_WORD_SHIFT; 58 59 ASSERT(start_bit < size); 60 size -= start_bit & ~(NBWORD - 1); 61 start_bit &= (NBWORD - 1); 62 if (start_bit) { 63 tmp = *p++; 64 /* set to one first offset bits prior to start */ 65 tmp |= (~0U >> (NBWORD-start_bit)); 66 if (tmp != ~0U) 67 goto found; 68 result += NBWORD; 69 size -= NBWORD; 70 } 71 while (size) { 72 if ((tmp = *p++) != ~0U) 73 goto found; 74 result += NBWORD; 75 size -= NBWORD; 76 } 77 return result - start_bit; 78found: 79 return result + ffz(tmp) - start_bit; 80} 81 82/* 83 * This takes the bit number to start looking from and 84 * returns the next set bit from there. It returns -1 85 * if there are no more bits set or the start bit is 86 * beyond the end of the bitmap. 87 * 88 * Size is the number of words, not bytes, in the bitmap. 89 */ 90int xfs_next_bit(uint *map, uint size, uint start_bit) 91{ 92 uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT); 93 uint result = start_bit & ~(NBWORD - 1); 94 uint tmp; 95 96 size <<= BIT_TO_WORD_SHIFT; 97 98 if (start_bit >= size) 99 return -1; 100 size -= result; 101 start_bit &= (NBWORD - 1); 102 if (start_bit) { 103 tmp = *p++; 104 /* set to zero first offset bits prior to start */ 105 tmp &= (~0U << start_bit); 106 if (tmp != 0U) 107 goto found; 108 result += NBWORD; 109 size -= NBWORD; 110 } 111 while (size) { 112 if ((tmp = *p++) != 0U) 113 goto found; 114 result += NBWORD; 115 size -= NBWORD; 116 } 117 return -1; 118found: 119 return result + ffs(tmp) - 1; 120} 121