LXR linux/fs/xfs/xfs

   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