xfs/libxfs/xfs_bit.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (c) 2000-2005 Silicon Graphics, Inc.
0004  * All Rights Reserved.
0005  */
0006 #include "xfs.h"
0007 #include "xfs_log_format.h"
0008 #include "xfs_bit.h"
0009
0010 /*
0011  * XFS bit manipulation routines, used in non-realtime code.
0012  */
0013
0014 /*
0015  * Return whether bitmap is empty.
0016  * Size is number of words in the bitmap, which is padded to word boundary
0017  * Returns 1 for empty, 0 for non-empty.
0018  */
0019 int
0020 xfs_bitmap_empty(uint *map, uint size)
0021 {
0022     uint i;
0023
0024     for (i = 0; i < size; i++) {
0025         if (map[i] != 0)
0026             return 0;
0027     }
0028
0029     return 1;
0030 }
0031
0032 /*
0033  * Count the number of contiguous bits set in the bitmap starting with bit
0034  * start_bit.  Size is the size of the bitmap in words.
0035  */
0036 int
0037 xfs_contig_bits(uint *map, uint size, uint start_bit)
0038 {
0039     uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
0040     uint result = 0;
0041     uint tmp;
0042
0043     size <<= BIT_TO_WORD_SHIFT;
0044
0045     ASSERT(start_bit < size);
0046     size -= start_bit & ~(NBWORD - 1);
0047     start_bit &= (NBWORD - 1);
0048     if (start_bit) {
0049         tmp = *p++;
0050         /* set to one first offset bits prior to start */
0051         tmp |= (~0U >> (NBWORD-start_bit));
0052         if (tmp != ~0U)
0053             goto found;
0054         result += NBWORD;
0055         size -= NBWORD;
0056     }
0057     while (size) {
0058         if ((tmp = *p++) != ~0U)
0059             goto found;
0060         result += NBWORD;
0061         size -= NBWORD;
0062     }
0063     return result - start_bit;
0064 found:
0065     return result + ffz(tmp) - start_bit;
0066 }
0067
0068 /*
0069  * This takes the bit number to start looking from and
0070  * returns the next set bit from there.  It returns -1
0071  * if there are no more bits set or the start bit is
0072  * beyond the end of the bitmap.
0073  *
0074  * Size is the number of words, not bytes, in the bitmap.
0075  */
0076 int xfs_next_bit(uint *map, uint size, uint start_bit)
0077 {
0078     uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
0079     uint result = start_bit & ~(NBWORD - 1);
0080     uint tmp;
0081
0082     size <<= BIT_TO_WORD_SHIFT;
0083
0084     if (start_bit >= size)
0085         return -1;
0086     size -= result;
0087     start_bit &= (NBWORD - 1);
0088     if (start_bit) {
0089         tmp = *p++;
0090         /* set to zero first offset bits prior to start */
0091         tmp &= (~0U << start_bit);
0092         if (tmp != 0U)
0093             goto found;
0094         result += NBWORD;
0095         size -= NBWORD;
0096     }
0097     while (size) {
0098         if ((tmp = *p++) != 0U)
0099             goto found;
0100         result += NBWORD;
0101         size -= NBWORD;
0102     }
0103     return -1;
0104 found:
0105     return result + ffs(tmp) - 1;
0106 }