libext2fs: make sure ismounted.c explicitly pulls in <sys/types.h>

[tools/e2fsprogs.git] / lib / ext2fs / blkmap64_ba.c

diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 395aba9..894293a 100644 (file)
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -9,6 +9,7 @@
  * %End-Header%
  */
 
+#include "config.h"
 #include <stdio.h>
 #include <string.h>
 #if HAVE_UNISTD_H
@@ -309,6 +310,161 @@ static void ba_clear_bmap(ext2fs_generic_bitmap bitmap)
               (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
 }
 
+static void ba_print_stats(ext2fs_generic_bitmap bitmap)
+{
+       fprintf(stderr, "%16llu Bytes used by bitarray\n",
+               ((bitmap->real_end - bitmap->start) >> 3) + 1 +
+               sizeof(struct ext2fs_ba_private_struct));
+}
+
+/* Find the first zero bit between start and end, inclusive. */
+static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
+                                   __u64 start, __u64 end, __u64 *out)
+{
+       ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
+       unsigned long bitpos = start - bitmap->start;
+       unsigned long count = end - start + 1;
+       int byte_found = 0; /* whether a != 0xff byte has been found */
+       const unsigned char *pos;
+       unsigned long max_loop_count, i;
+
+       /* scan bits until we hit a byte boundary */
+       while ((bitpos & 0x7) != 0 && count > 0) {
+               if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
+                       *out = bitpos + bitmap->start;
+                       return 0;
+               }
+               bitpos++;
+               count--;
+       }
+
+       if (!count)
+               return ENOENT;
+
+       pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
+       /* scan bytes until 8-byte (64-bit) aligned */
+       while (count >= 8 && (((unsigned long)pos) & 0x07)) {
+               if (*pos != 0xff) {
+                       byte_found = 1;
+                       break;
+               }
+               pos++;
+               count -= 8;
+               bitpos += 8;
+       }
+
+       if (!byte_found) {
+               max_loop_count = count >> 6; /* 8-byte blocks */
+               i = max_loop_count;
+               while (i) {
+                       if (*((const __u64 *)pos) != ((__u64)-1))
+                               break;
+                       pos += 8;
+                       i--;
+               }
+               count -= 64 * (max_loop_count - i);
+               bitpos += 64 * (max_loop_count - i);
+
+               max_loop_count = count >> 3;
+               i = max_loop_count;
+               while (i) {
+                       if (*pos != 0xff) {
+                               byte_found = 1;
+                               break;
+                       }
+                       pos++;
+                       i--;
+               }
+               count -= 8 * (max_loop_count - i);
+               bitpos += 8 * (max_loop_count - i);
+       }
+
+       /* Here either count < 8 or byte_found == 1. */
+       while (count-- > 0) {
+               if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
+                       *out = bitpos + bitmap->start;
+                       return 0;
+               }
+               bitpos++;
+       }
+
+       return ENOENT;
+}
+
+/* Find the first one bit between start and end, inclusive. */
+static errcode_t ba_find_first_set(ext2fs_generic_bitmap bitmap,
+                                   __u64 start, __u64 end, __u64 *out)
+{
+       ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
+       unsigned long bitpos = start - bitmap->start;
+       unsigned long count = end - start + 1;
+       int byte_found = 0; /* whether a != 0xff byte has been found */
+       const unsigned char *pos;
+       unsigned long max_loop_count, i;
+
+       /* scan bits until we hit a byte boundary */
+       while ((bitpos & 0x7) != 0 && count > 0) {
+               if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
+                       *out = bitpos + bitmap->start;
+                       return 0;
+               }
+               bitpos++;
+               count--;
+       }
+
+       if (!count)
+               return ENOENT;
+
+       pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
+       /* scan bytes until 8-byte (64-bit) aligned */
+       while (count >= 8 && (((unsigned long)pos) & 0x07)) {
+               if (*pos != 0) {
+                       byte_found = 1;
+                       break;
+               }
+               pos++;
+               count -= 8;
+               bitpos += 8;
+       }
+
+       if (!byte_found) {
+               max_loop_count = count >> 6; /* 8-byte blocks */
+               i = max_loop_count;
+               while (i) {
+                       if (*((const __u64 *)pos) != 0)
+                               break;
+                       pos += 8;
+                       i--;
+               }
+               count -= 64 * (max_loop_count - i);
+               bitpos += 64 * (max_loop_count - i);
+
+               max_loop_count = count >> 3;
+               i = max_loop_count;
+               while (i) {
+                       if (*pos != 0) {
+                               byte_found = 1;
+                               break;
+                       }
+                       pos++;
+                       i--;
+               }
+               count -= 8 * (max_loop_count - i);
+               bitpos += 8 * (max_loop_count - i);
+       }
+
+       /* Here either count < 8 or byte_found == 1. */
+       while (count-- > 0) {
+               if (ext2fs_test_bit64(bitpos, bp->bitarray)) {
+                       *out = bitpos + bitmap->start;
+                       return 0;
+               }
+               bitpos++;
+       }
+
+       return ENOENT;
+}
+
 struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
        .type = EXT2FS_BMAP64_BITARRAY,
        .new_bmap = ba_new_bmap,
@@ -324,4 +480,7 @@ struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
        .set_bmap_range = ba_set_bmap_range,
        .get_bmap_range = ba_get_bmap_range,
        .clear_bmap = ba_clear_bmap,
+       .print_stats = ba_print_stats,
+       .find_first_zero = ba_find_first_zero,
+       .find_first_set = ba_find_first_set
 };