LXR linux/fs/xfs/libxfs/xfs

   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#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 boundary
  17 * Returns 1 for empty, 0 for non-empty.
  18 */
  19int
  20xfs_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 bit
  34 * start_bit.  Size is the size of the bitmap in words.
  35 */
  36int
  37xfs_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 and
  70 * returns the next set bit from there.  It returns -1
  71 * if there are no more bits set or the start bit is
  72 * 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