fs/xfs/libxfs/xfs_bit.c

   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 }