Line data    Source code

       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             :  */
      19             : int
      20  4811649256 : xfs_bitmap_empty(uint *map, uint size)
      21             : {
      22  4811649256 :         uint i;
      23             : 
      24  4928489874 :         for (i = 0; i < size; i++) {
      25  4841886964 :                 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             :  */
      36             : int
      37 13276803581 : xfs_contig_bits(uint *map, uint size, uint start_bit)
      38             : {
      39 13276803581 :         uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
      40 13276803581 :         uint result = 0;
      41 13276803581 :         uint tmp;
      42             : 
      43 13276803581 :         size <<= BIT_TO_WORD_SHIFT;
      44             : 
      45 13276803581 :         ASSERT(start_bit < size);
      46 13276803581 :         size -= start_bit & ~(NBWORD - 1);
      47 13276803581 :         start_bit &= (NBWORD - 1);
      48 13276803581 :         if (start_bit) {
      49  5037178669 :                 tmp = *p++;
      50             :                 /* set to one first offset bits prior to start */
      51  5037178669 :                 tmp |= (~0U >> (NBWORD-start_bit));
      52  5037178669 :                 if (tmp != ~0U)
      53  4493137590 :                         goto found;
      54   544041079 :                 result += NBWORD;
      55   544041079 :                 size -= NBWORD;
      56             :         }
      57 11471623282 :         while (size) {
      58  8259174876 :                 if ((tmp = *p++) != ~0U)
      59  5571217585 :                         goto found;
      60  2687957291 :                 result += NBWORD;
      61  2687957291 :                 size -= NBWORD;
      62             :         }
      63  3212448406 :         return result - start_bit;
      64 10064355175 : found:
      65 10064355175 :         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             :  */
      76 >11527*10^7 : int xfs_next_bit(uint *map, uint size, uint start_bit)
      77             : {
      78 >11527*10^7 :         uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
      79 >11527*10^7 :         uint result = start_bit & ~(NBWORD - 1);
      80 >11527*10^7 :         uint tmp;
      81             : 
      82 >11527*10^7 :         size <<= BIT_TO_WORD_SHIFT;
      83             : 
      84 >11527*10^7 :         if (start_bit >= size)
      85             :                 return -1;
      86 >11175*10^7 :         size -= result;
      87 >11175*10^7 :         start_bit &= (NBWORD - 1);
      88 >11175*10^7 :         if (start_bit) {
      89 92952987749 :                 tmp = *p++;
      90             :                 /* set to zero first offset bits prior to start */
      91 92952987749 :                 tmp &= (~0U << start_bit);
      92 92952987749 :                 if (tmp != 0U)
      93 77400085670 :                         goto found;
      94 15552902079 :                 result += NBWORD;
      95 15552902079 :                 size -= NBWORD;
      96             :         }
      97 34505804452 :         while (size) {
      98 19108799681 :                 if ((tmp = *p++) != 0U)
      99 18958320300 :                         goto found;
     100   150479381 :                 result += NBWORD;
     101   150479381 :                 size -= NBWORD;
     102             :         }
     103             :         return -1;
     104 96358405970 : found:
     105 96358405970 :         return result + ffs(tmp) - 1;
     106             : }