xfs_bit.c 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
  1. /*
  2. * Copyright (c) 2000-2005 Silicon Graphics, Inc.
  3. * All Rights Reserved.
  4. *
  5. * This program is free software; you can redistribute it and/or
  6. * modify it under the terms of the GNU General Public License as
  7. * published by the Free Software Foundation.
  8. *
  9. * This program is distributed in the hope that it would be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program; if not, write the Free Software Foundation,
  16. * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  17. */
  18. #include "xfs.h"
  19. #include "xfs_log_format.h"
  20. #include "xfs_bit.h"
  21. /*
  22. * XFS bit manipulation routines, used in non-realtime code.
  23. */
  24. /*
  25. * Return whether bitmap is empty.
  26. * Size is number of words in the bitmap, which is padded to word boundary
  27. * Returns 1 for empty, 0 for non-empty.
  28. */
  29. int
  30. xfs_bitmap_empty(uint *map, uint size)
  31. {
  32. uint i;
  33. uint ret = 0;
  34. for (i = 0; i < size; i++) {
  35. ret |= map[i];
  36. }
  37. return (ret == 0);
  38. }
  39. /*
  40. * Count the number of contiguous bits set in the bitmap starting with bit
  41. * start_bit. Size is the size of the bitmap in words.
  42. */
  43. int
  44. xfs_contig_bits(uint *map, uint size, uint start_bit)
  45. {
  46. uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
  47. uint result = 0;
  48. uint tmp;
  49. size <<= BIT_TO_WORD_SHIFT;
  50. ASSERT(start_bit < size);
  51. size -= start_bit & ~(NBWORD - 1);
  52. start_bit &= (NBWORD - 1);
  53. if (start_bit) {
  54. tmp = *p++;
  55. /* set to one first offset bits prior to start */
  56. tmp |= (~0U >> (NBWORD-start_bit));
  57. if (tmp != ~0U)
  58. goto found;
  59. result += NBWORD;
  60. size -= NBWORD;
  61. }
  62. while (size) {
  63. if ((tmp = *p++) != ~0U)
  64. goto found;
  65. result += NBWORD;
  66. size -= NBWORD;
  67. }
  68. return result - start_bit;
  69. found:
  70. return result + ffz(tmp) - start_bit;
  71. }
  72. /*
  73. * This takes the bit number to start looking from and
  74. * returns the next set bit from there. It returns -1
  75. * if there are no more bits set or the start bit is
  76. * beyond the end of the bitmap.
  77. *
  78. * Size is the number of words, not bytes, in the bitmap.
  79. */
  80. int xfs_next_bit(uint *map, uint size, uint start_bit)
  81. {
  82. uint * p = ((unsigned int *) map) + (start_bit >> BIT_TO_WORD_SHIFT);
  83. uint result = start_bit & ~(NBWORD - 1);
  84. uint tmp;
  85. size <<= BIT_TO_WORD_SHIFT;
  86. if (start_bit >= size)
  87. return -1;
  88. size -= result;
  89. start_bit &= (NBWORD - 1);
  90. if (start_bit) {
  91. tmp = *p++;
  92. /* set to zero first offset bits prior to start */
  93. tmp &= (~0U << start_bit);
  94. if (tmp != 0U)
  95. goto found;
  96. result += NBWORD;
  97. size -= NBWORD;
  98. }
  99. while (size) {
  100. if ((tmp = *p++) != 0U)
  101. goto found;
  102. result += NBWORD;
  103. size -= NBWORD;
  104. }
  105. return -1;
  106. found:
  107. return result + ffs(tmp) - 1;
  108. }