^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Copyright (c) 2000-2005 Silicon Graphics, Inc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * All Rights Reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #include "xfs.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include "xfs_log_format.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #include "xfs_bit.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * XFS bit manipulation routines, used in non-realtime code.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * Return whether bitmap is empty.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * Size is number of words in the bitmap, which is padded to word boundary
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * Returns 1 for empty, 0 for non-empty.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) xfs_bitmap_empty(uint *map, uint size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) uint i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) for (i = 0; i < size; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) if (map[i] != 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) * Count the number of contiguous bits set in the bitmap starting with bit
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) * start_bit. Size is the size of the bitmap in words.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) int
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) xfs_contig_bits(uint *map, uint size, uint start_bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) uint result = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) uint tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) size <<= BIT_TO_WORD_SHIFT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) ASSERT(start_bit < size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) size -= start_bit & ~(NBWORD - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) start_bit &= (NBWORD - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) if (start_bit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) tmp = *p++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) /* set to one first offset bits prior to start */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) tmp |= (~0U >> (NBWORD-start_bit));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) if (tmp != ~0U)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) goto found;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) result += NBWORD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) size -= NBWORD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) while (size) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) if ((tmp = *p++) != ~0U)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) goto found;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) result += NBWORD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) size -= NBWORD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) return result - start_bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) found:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) return result + ffz(tmp) - start_bit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) * This takes the bit number to start looking from and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) * returns the next set bit from there. It returns -1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) * if there are no more bits set or the start bit is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) * beyond the end of the bitmap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) * Size is the number of words, not bytes, in the bitmap.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) int xfs_next_bit(uint *map, uint size, uint start_bit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) uint result = start_bit & ~(NBWORD - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) uint tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) size <<= BIT_TO_WORD_SHIFT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) if (start_bit >= size)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) size -= result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) start_bit &= (NBWORD - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) if (start_bit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) tmp = *p++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) /* set to zero first offset bits prior to start */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) tmp &= (~0U << start_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) if (tmp != 0U)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) goto found;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) result += NBWORD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) size -= NBWORD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) while (size) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) if ((tmp = *p++) != 0U)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) goto found;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) result += NBWORD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) size -= NBWORD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) found:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) return result + ffs(tmp) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags