+ if (start > end)
+ return EINVAL;
+
+ if (EXT2FS_RB_EMPTY_ROOT(&bp->root))
+ return ENOENT;
+
+ while (*n) {
+ parent = *n;
+ ext = node_to_extent(parent);
+ if (start < ext->start) {
+ n = &(*n)->rb_left;
+ } else if (start >= (ext->start + ext->count)) {
+ n = &(*n)->rb_right;
+ } else {
+ /* The start bit is set */
+ *out = start + bitmap->start;
+ return 0;
+ }
+ }
+
+ node = parent;
+ ext = node_to_extent(node);
+ if (ext->start < start) {
+ node = ext2fs_rb_next(node);
+ if (node == NULL)
+ return ENOENT;
+ ext = node_to_extent(node);
+ }
+ if (ext->start <= end) {
+ *out = ext->start + bitmap->start;
+ return 0;
+ }
+ return ENOENT;
+}
+
+#ifdef BMAP_STATS
+static void rb_print_stats(ext2fs_generic_bitmap bitmap)
+{
+ struct ext2fs_rb_private *bp;
+ struct rb_node *node = NULL;
+ struct bmap_rb_extent *ext;
+ __u64 count = 0;
+ __u64 max_size = 0;
+ __u64 min_size = ULONG_MAX;
+ __u64 size = 0, avg_size = 0;
+ double eff;
+#ifdef BMAP_STATS_OPS
+ __u64 mark_all, test_all;
+ double m_hit = 0.0, t_hit = 0.0;
+#endif
+
+ bp = (struct ext2fs_rb_private *) bitmap->private;
+
+ for (node = ext2fs_rb_first(&bp->root); node != NULL;
+ node = ext2fs_rb_next(node)) {
+ ext = node_to_extent(node);
+ count++;
+ if (ext->count > max_size)
+ max_size = ext->count;
+ if (ext->count < min_size)
+ min_size = ext->count;
+ size += ext->count;
+ }
+
+ if (count)
+ avg_size = size / count;
+ if (min_size == ULONG_MAX)
+ min_size = 0;
+ eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) /
+ (bitmap->real_end - bitmap->start);
+#ifdef BMAP_STATS_OPS
+ mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count;
+ test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count;
+ if (mark_all)
+ m_hit = ((double)bp->mark_hit / mark_all) * 100;
+ if (test_all)
+ t_hit = ((double)bp->test_hit / test_all) * 100;
+
+ fprintf(stderr, "%16llu cache hits on test (%.2f%%)\n"
+ "%16llu cache hits on mark (%.2f%%)\n",
+ bp->test_hit, t_hit, bp->mark_hit, m_hit);
+#endif
+ fprintf(stderr, "%16llu extents (%llu bytes)\n",
+ count, ((count * sizeof(struct bmap_rb_extent)) +
+ sizeof(struct ext2fs_rb_private)));
+ fprintf(stderr, "%16llu bits minimum size\n",
+ min_size);
+ fprintf(stderr, "%16llu bits maximum size\n"
+ "%16llu bits average size\n",
+ max_size, avg_size);
+ fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", size,
+ bitmap->real_end - bitmap->start);
+ fprintf(stderr,
+ "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
+ eff);