X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=lib%2Fext2fs%2Fblkmap64_rb.c;h=0df58dc738aee97f32252ada03daabe2683b2bc3;hb=2a2edef1c38d1fa55f83f5d33b1ad158113dff13;hp=a0752747008ae207ccb424cd895121b0380c5081;hpb=3a4fd4c84d5bab959c85a6ccbfcb9715c3d9fd5e;p=tools%2Fe2fsprogs.git diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c index a075274..0df58dc 100644 --- a/lib/ext2fs/blkmap64_rb.c +++ b/lib/ext2fs/blkmap64_rb.c @@ -9,6 +9,7 @@ * %End-Header% */ +#include "config.h" #include #include #if HAVE_UNISTD_H @@ -22,6 +23,9 @@ #if HAVE_SYS_TYPES_H #include #endif +#if HAVE_LINUX_TYPES_H +#include +#endif #include "ext2_fs.h" #include "ext2fsP.h" @@ -47,6 +51,17 @@ struct ext2fs_rb_private { #endif }; +inline static struct bmap_rb_extent *node_to_extent(struct rb_node *node) +{ + /* + * This depends on the fact the struct rb_node is at the + * beginning of the bmap_rb_extent structure. We use this + * instead of the ext2fs_rb_entry macro because it causes gcc + * -Wall to generate a huge amount of noise. + */ + return (struct bmap_rb_extent *) node; +} + static int rb_insert_extent(__u64 start, __u64 count, struct ext2fs_rb_private *); static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64); @@ -59,72 +74,85 @@ static void print_tree(struct rb_root *root) struct rb_node *node = NULL; struct bmap_rb_extent *ext; - printf("\t\t\t=================================\n"); + fprintf(stderr, "\t\t\t=================================\n"); node = ext2fs_rb_first(root); for (node = ext2fs_rb_first(root); node != NULL; node = ext2fs_rb_next(node)) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); - printf("\t\t\t--> (%llu -> %llu)\n", - ext->start, ext->start + ext->count); + ext = node_to_extent(node); + fprintf(stderr, "\t\t\t--> (%llu -> %llu)\n", + (unsigned long long) ext->start, + (unsigned long long) ext->start + ext->count); } - printf("\t\t\t=================================\n"); + fprintf(stderr, "\t\t\t=================================\n"); } -static int check_tree(struct rb_root *root, const char *msg) +static void check_tree(struct rb_root *root, const char *msg) { - struct rb_node *new_node, *node, *next; + struct rb_node *node; struct bmap_rb_extent *ext, *old = NULL; for (node = ext2fs_rb_first(root); node; node = ext2fs_rb_next(node)) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); - if (ext->count <= 0) { - printf("Tree Error: count is crazy\n"); - printf("extent: %llu -> %llu (%u)\n", ext->start, - ext->start + ext->count, ext->count); + ext = node_to_extent(node); + if (ext->count == 0) { + fprintf(stderr, "Tree Error: count is zero\n"); + fprintf(stderr, "extent: %llu -> %llu (%llu)\n", + (unsigned long long) ext->start, + (unsigned long long) ext->start + ext->count, + (unsigned long long) ext->count); goto err_out; } - if (ext->start < 0) { - printf("Tree Error: start is crazy\n"); - printf("extent: %llu -> %llu (%u)\n", ext->start, - ext->start + ext->count, ext->count); + if (ext->start + ext->count < ext->start) { + fprintf(stderr, + "Tree Error: start or count is crazy\n"); + fprintf(stderr, "extent: %llu -> %llu (%llu)\n", + (unsigned long long) ext->start, + (unsigned long long) ext->start + ext->count, + (unsigned long long) ext->count); goto err_out; } if (old) { if (old->start > ext->start) { - printf("Tree Error: start is crazy\n"); - printf("extent: %llu -> %llu (%u)\n", - old->start, old->start + old->count, - old->count); - printf("extent next: %llu -> %llu (%u)\n", - ext->start, ext->start + ext->count, - ext->count); + fprintf(stderr, "Tree Error: start is crazy\n"); + fprintf(stderr, "extent: %llu -> %llu (%llu)\n", + (unsigned long long) old->start, + (unsigned long long) old->start + old->count, + (unsigned long long) old->count); + fprintf(stderr, + "extent next: %llu -> %llu (%llu)\n", + (unsigned long long) ext->start, + (unsigned long long) ext->start + ext->count, + (unsigned long long) ext->count); goto err_out; } if ((old->start + old->count) >= ext->start) { - printf("Tree Error: extent is crazy\n"); - printf("extent: %llu -> %llu (%u)\n", - old->start, old->start + old->count, - old->count); - printf("extent next: %llu -> %llu (%u)\n", - ext->start, ext->start + ext->count, - ext->count); + fprintf(stderr, + "Tree Error: extent is crazy\n"); + fprintf(stderr, "extent: %llu -> %llu (%llu)\n", + (unsigned long long) old->start, + (unsigned long long) old->start + old->count, + (unsigned long long) old->count); + fprintf(stderr, + "extent next: %llu -> %llu (%llu)\n", + (unsigned long long) ext->start, + (unsigned long long) ext->start + ext->count, + (unsigned long long) ext->count); goto err_out; } } old = ext; } - return 0; + return; err_out: - printf("%s\n", msg); + fprintf(stderr, "%s\n", msg); print_tree(root); exit(1); } #else -#define check_tree(root, msg) 0 -#define print_tree(root, msg) 0 +#define check_tree(root, msg) do {} while (0) +#define print_tree(root) do {} while (0) #endif static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start, @@ -156,7 +184,7 @@ static void rb_free_extent(struct ext2fs_rb_private *bp, ext2fs_free_mem(&ext); } -static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap) +static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap_64 bitmap) { struct ext2fs_rb_private *bp; errcode_t retval; @@ -180,7 +208,7 @@ static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap) } static errcode_t rb_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)), - ext2fs_generic_bitmap bitmap) + ext2fs_generic_bitmap_64 bitmap) { errcode_t retval; @@ -198,13 +226,13 @@ static void rb_free_tree(struct rb_root *root) for (node = ext2fs_rb_first(root); node; node = next) { next = ext2fs_rb_next(node); - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); ext2fs_rb_erase(node, root); ext2fs_free_mem(&ext); } } -static void rb_free_bmap(ext2fs_generic_bitmap bitmap) +static void rb_free_bmap(ext2fs_generic_bitmap_64 bitmap) { struct ext2fs_rb_private *bp; @@ -215,8 +243,8 @@ static void rb_free_bmap(ext2fs_generic_bitmap bitmap) bp = 0; } -static errcode_t rb_copy_bmap(ext2fs_generic_bitmap src, - ext2fs_generic_bitmap dest) +static errcode_t rb_copy_bmap(ext2fs_generic_bitmap_64 src, + ext2fs_generic_bitmap_64 dest) { struct ext2fs_rb_private *src_bp, *dest_bp; struct bmap_rb_extent *src_ext, *dest_ext; @@ -234,7 +262,7 @@ static errcode_t rb_copy_bmap(ext2fs_generic_bitmap src, src_node = ext2fs_rb_first(&src_bp->root); while (src_node) { - src_ext = ext2fs_rb_entry(src_node, struct bmap_rb_extent, node); + src_ext = node_to_extent(src_node); retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent), &dest_ext); if (retval) @@ -267,7 +295,7 @@ static void rb_truncate(__u64 new_max, struct rb_root *root) node = ext2fs_rb_last(root); while (node) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); if ((ext->start + ext->count - 1) <= new_max) break; @@ -281,26 +309,24 @@ static void rb_truncate(__u64 new_max, struct rb_root *root) } } -static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap, +static errcode_t rb_resize_bmap(ext2fs_generic_bitmap_64 bmap, __u64 new_end, __u64 new_real_end) { struct ext2fs_rb_private *bp; - if (new_real_end >= bmap->real_end) { - bmap->end = new_end; - bmap->real_end = new_real_end; - return 0; - } - bp = (struct ext2fs_rb_private *) bmap->private; bp->rcursor = NULL; bp->wcursor = NULL; - /* truncate tree to new_real_end size */ - rb_truncate(new_real_end, &bp->root); + rb_truncate(((new_end < bmap->end) ? new_end : bmap->end) - bmap->start, + &bp->root); bmap->end = new_end; bmap->real_end = new_real_end; + + if (bmap->end < bmap->real_end) + rb_insert_extent(bmap->end + 1 - bmap->start, + bmap->real_end - bmap->end, bp); return 0; } @@ -328,8 +354,7 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit) if (!next_ext) { next = ext2fs_rb_next(&rcursor->node); if (next) - next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, - node); + next_ext = node_to_extent(next); bp->rcursor_next = next_ext; } if (next_ext) { @@ -355,7 +380,7 @@ search_tree: while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (bit < ext->start) n = &(*n)->rb_left; else if (bit >= (ext->start + ext->count)) @@ -379,6 +404,9 @@ static int rb_insert_extent(__u64 start, __u64 count, struct bmap_rb_extent *ext; int retval = 0; + if (count == 0) + return 0; + bp->rcursor_next = NULL; ext = bp->wcursor; if (ext) { @@ -393,7 +421,7 @@ static int rb_insert_extent(__u64 start, __u64 count, while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (start < ext->start) { n = &(*n)->rb_left; @@ -427,7 +455,7 @@ got_extent: node = ext2fs_rb_prev(new_node); if (node) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); if ((ext->start + ext->count) == start) { start = ext->start; count += ext->count; @@ -440,7 +468,7 @@ skip_insert: /* See if we can merge extent to the right */ for (node = ext2fs_rb_next(new_node); node != NULL; node = next) { next = ext2fs_rb_next(node); - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); if ((ext->start + ext->count) <= start) continue; @@ -480,12 +508,12 @@ static int rb_remove_extent(__u64 start, __u64 count, __u64 new_start, new_count; int retval = 0; - if (EXT2FS_RB_EMPTY_ROOT(root)) + if (ext2fs_rb_empty_root(root)) return 0; while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (start < ext->start) { n = &(*n)->rb_left; continue; @@ -528,7 +556,7 @@ static int rb_remove_extent(__u64 start, __u64 count, /* See if we should delete or truncate extent on the right */ for (; parent != NULL; parent = node) { node = ext2fs_rb_next(parent); - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if ((ext->start + ext->count) <= start) continue; @@ -543,7 +571,7 @@ static int rb_remove_extent(__u64 start, __u64 count, retval = 1; continue; } else { - /* modify the last extent in reigon to be removed */ + /* modify the last extent in region to be removed */ ext->count -= ((start + count) - ext->start); ext->start = start + count; retval = 1; @@ -554,17 +582,20 @@ static int rb_remove_extent(__u64 start, __u64 count, return retval; } -static int rb_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) +static int rb_mark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) { struct ext2fs_rb_private *bp; + int retval; bp = (struct ext2fs_rb_private *) bitmap->private; arg -= bitmap->start; - return rb_insert_extent(arg, 1, bp); + retval = rb_insert_extent(arg, 1, bp); + check_tree(&bp->root, __func__); + return retval; } -static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) +static int rb_unmark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) { struct ext2fs_rb_private *bp; int retval; @@ -579,7 +610,7 @@ static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) } inline -static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) +static int rb_test_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) { struct ext2fs_rb_private *bp; @@ -589,7 +620,7 @@ static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) return rb_test_bit(bp, arg); } -static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, +static void rb_mark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg, unsigned int num) { struct ext2fs_rb_private *bp; @@ -598,9 +629,10 @@ static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, arg -= bitmap->start; rb_insert_extent(arg, num, bp); + check_tree(&bp->root, __func__); } -static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, +static void rb_unmark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg, unsigned int num) { struct ext2fs_rb_private *bp; @@ -612,7 +644,7 @@ static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, check_tree(&bp->root, __func__); } -static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, +static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 start, unsigned int len) { struct rb_node *parent = NULL, **n; @@ -625,7 +657,7 @@ static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, n = &bp->root.rb_node; start -= bitmap->start; - if ((len == 0) || EXT2FS_RB_EMPTY_ROOT(&bp->root)) + if (len == 0 || ext2fs_rb_empty_root(&bp->root)) return 1; /* @@ -635,7 +667,7 @@ static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, */ while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (start < ext->start) { n = &(*n)->rb_left; } else if (start >= (ext->start + ext->count)) { @@ -652,7 +684,7 @@ static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, node = parent; while (node) { next = ext2fs_rb_next(node); - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); node = next; if ((ext->start + ext->count) <= start) @@ -668,43 +700,71 @@ static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, return retval; } -static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap, +static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap_64 bitmap, __u64 start, size_t num, void *in) { struct ext2fs_rb_private *bp; + unsigned char *cp = in; size_t i; - int ret; + int first_set = -1; bp = (struct ext2fs_rb_private *) bitmap->private; for (i = 0; i < num; i++) { - ret = ext2fs_test_bit(i, in); - if (ret) - rb_insert_extent(start + i - bitmap->start, 1, bp); + if ((i & 7) == 0) { + unsigned char c = cp[i/8]; + if (c == 0xFF) { + if (first_set == -1) + first_set = i; + i += 7; + continue; + } + if ((c == 0x00) && (first_set == -1)) { + i += 7; + continue; + } + } + if (ext2fs_test_bit(i, in)) { + if (first_set == -1) + first_set = i; + continue; + } + if (first_set == -1) + continue; + + rb_insert_extent(start + first_set - bitmap->start, + i - first_set, bp); + check_tree(&bp->root, __func__); + first_set = -1; + } + if (first_set != -1) { + rb_insert_extent(start + first_set - bitmap->start, + num - first_set, bp); + check_tree(&bp->root, __func__); } return 0; } -static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap, +static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap_64 bitmap, __u64 start, size_t num, void *out) { struct rb_node *parent = NULL, *next, **n; struct ext2fs_rb_private *bp; struct bmap_rb_extent *ext; - __u64 pos; + __u64 count, pos; bp = (struct ext2fs_rb_private *) bitmap->private; n = &bp->root.rb_node; start -= bitmap->start; - if (EXT2FS_RB_EMPTY_ROOT(&bp->root)) + if (ext2fs_rb_empty_root(&bp->root)) return 0; while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (start < ext->start) { n = &(*n)->rb_left; } else if (start >= (ext->start + ext->count)) { @@ -713,36 +773,45 @@ static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap, break; } - pos = start; + memset(out, 0, (num + 7) >> 3); + for (; parent != NULL; parent = next) { next = ext2fs_rb_next(parent); - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); - while (((pos - start) < num) && - (pos < ext->start)) { - ext2fs_fast_clear_bit64((pos - start), out); - pos++; + pos = ext->start; + count = ext->count; + if (pos >= start + num) + break; + if (pos < start) { + if (pos + count < start) + continue; + count -= start - pos; + pos = start; } - - if ((pos - start) >= num) - return 0; - - while (((pos - start) < num) && - (pos < (ext->start + ext->count))) { + if (pos + count > start + num) + count = start + num - pos; + + while (count > 0) { + if ((count >= 8) && + ((pos - start) % 8) == 0) { + int nbytes = count >> 3; + int offset = (pos - start) >> 3; + + memset(((char *) out) + offset, 0xFF, nbytes); + pos += nbytes << 3; + count -= nbytes << 3; + continue; + } ext2fs_fast_set_bit64((pos - start), out); pos++; + count--; } } - - while ((pos - start) < num) { - ext2fs_fast_clear_bit64((pos - start), out); - pos++; - } - return 0; } -static void rb_clear_bmap(ext2fs_generic_bitmap bitmap) +static void rb_clear_bmap(ext2fs_generic_bitmap_64 bitmap) { struct ext2fs_rb_private *bp; @@ -752,10 +821,95 @@ static void rb_clear_bmap(ext2fs_generic_bitmap bitmap) bp->rcursor = NULL; bp->rcursor_next = NULL; bp->wcursor = NULL; + check_tree(&bp->root, __func__); +} + +static errcode_t rb_find_first_zero(ext2fs_generic_bitmap_64 bitmap, + __u64 start, __u64 end, __u64 *out) +{ + struct rb_node *parent = NULL, **n; + struct ext2fs_rb_private *bp; + struct bmap_rb_extent *ext; + + bp = (struct ext2fs_rb_private *) bitmap->private; + n = &bp->root.rb_node; + start -= bitmap->start; + end -= bitmap->start; + + 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 if (ext->start + ext->count <= end) { + *out = ext->start + ext->count + bitmap->start; + return 0; + } else + return ENOENT; + } + + *out = start + bitmap->start; + return 0; +} + +static errcode_t rb_find_first_set(ext2fs_generic_bitmap_64 bitmap, + __u64 start, __u64 end, __u64 *out) +{ + struct rb_node *parent = NULL, **n; + struct rb_node *node; + struct ext2fs_rb_private *bp; + struct bmap_rb_extent *ext; + + bp = (struct ext2fs_rb_private *) bitmap->private; + n = &bp->root.rb_node; + start -= bitmap->start; + end -= bitmap->start; + + 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 ENABLE_BMAP_STATS -static void rb_print_stats(ext2fs_generic_bitmap bitmap) +static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap) { struct ext2fs_rb_private *bp; struct rb_node *node = NULL; @@ -772,10 +926,9 @@ static void rb_print_stats(ext2fs_generic_bitmap bitmap) bp = (struct ext2fs_rb_private *) bitmap->private; - node = ext2fs_rb_first(&bp->root); for (node = ext2fs_rb_first(&bp->root); node != NULL; node = ext2fs_rb_next(node)) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); count++; if (ext->count > max_size) max_size = ext->count; @@ -803,21 +956,25 @@ static void rb_print_stats(ext2fs_generic_bitmap bitmap) 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))); + (unsigned long long) count, (unsigned long long) + ((count * sizeof(struct bmap_rb_extent)) + + sizeof(struct ext2fs_rb_private))); fprintf(stderr, "%16llu bits minimum size\n", - min_size); + (unsigned long long) 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); + (unsigned long long) max_size, (unsigned long long) avg_size); + fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", + (unsigned long long) size, + (unsigned long long) bitmap->real_end - bitmap->start); fprintf(stderr, "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n", eff); } #else -static void rb_print_stats(ext2fs_generic_bitmap bitmap){} +static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap EXT2FS_ATTR((unused))) +{ +} #endif struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = { @@ -836,4 +993,6 @@ struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = { .get_bmap_range = rb_get_bmap_range, .clear_bmap = rb_clear_bmap, .print_stats = rb_print_stats, + .find_first_zero = rb_find_first_zero, + .find_first_set = rb_find_first_set, };