diff options
Diffstat (limited to 'set.c')
| -rw-r--r-- | set.c | 458 |
1 files changed, 276 insertions, 182 deletions
@@ -7,6 +7,7 @@ #include "id.h" #include "internal.h" #include "internal/bits.h" +#include "internal/error.h" #include "internal/hash.h" #include "internal/proc.h" #include "internal/sanitizers.h" @@ -101,6 +102,8 @@ static ID id_any_p; static ID id_new; static ID id_i_hash; static ID id_set_iter_lev; +static ID id_subclass_compatible; +static ID id_class_methods; #define RSET_INITIALIZED FL_USER1 #define RSET_LEV_MASK (FL_USER13 | FL_USER14 | FL_USER15 | /* FL 13..19 */ \ @@ -113,7 +116,7 @@ static ID id_set_iter_lev; #define RSET_SIZE(set) set_table_size(RSET_TABLE(set)) #define RSET_EMPTY(set) (RSET_SIZE(set) == 0) #define RSET_SIZE_NUM(set) SIZET2NUM(RSET_SIZE(set)) -#define RSET_IS_MEMBER(sobj, item) set_lookup(RSET_TABLE(set), (st_data_t)(item)) +#define RSET_IS_MEMBER(set, item) set_table_lookup(RSET_TABLE(set), (st_data_t)(item)) #define RSET_COMPARE_BY_IDENTITY(set) (RSET_TABLE(set)->type == &identhash) struct set_object { @@ -132,13 +135,12 @@ static void set_mark(void *ptr) { struct set_object *sobj = ptr; - if (sobj->table.entries) set_foreach(&sobj->table, mark_key, 0); + if (sobj->table.entries) set_table_foreach(&sobj->table, mark_key, 0); } static void set_free_embedded(struct set_object *sobj) { - free((&sobj->table)->bins); free((&sobj->table)->entries); } @@ -171,9 +173,7 @@ set_foreach_replace(st_data_t key, st_data_t argp, int error) static int set_replace_ref(st_data_t *key, st_data_t argp, int existing) { - if (rb_gc_location((VALUE)*key) != (VALUE)*key) { - *key = rb_gc_location((VALUE)*key); - } + rb_gc_mark_and_move((VALUE *)key); return ST_CONTINUE; } @@ -405,6 +405,13 @@ set_s_alloc(VALUE klass) return set_alloc_with_size(klass, 0); } +/* + * call-seq: + * Set[*objects] -> new_set + * + * Returns a new Set object populated with the given objects, + * See Set::new. + */ static VALUE set_s_create(int argc, VALUE *argv, VALUE klass) { @@ -419,6 +426,19 @@ set_s_create(int argc, VALUE *argv, VALUE klass) return set; } +static VALUE +set_s_inherited(VALUE klass, VALUE subclass) +{ + if (klass == rb_cSet) { + // When subclassing directly from Set, include the compatibility layer + rb_require("set/subclass_compatible.rb"); + VALUE subclass_compatible = rb_const_get(klass, id_subclass_compatible); + rb_include_module(subclass, subclass_compatible); + rb_extend_object(subclass, rb_const_get(subclass_compatible, id_class_methods)); + } + return Qnil; +} + static void check_set(VALUE arg) { @@ -475,11 +495,11 @@ set_initialize_with_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, set)) * If a block is given, the elements of enum are preprocessed by the * given block. * - * Set.new([1, 2]) #=> #<Set: {1, 2}> - * Set.new([1, 2, 1]) #=> #<Set: {1, 2}> - * Set.new([1, 'c', :s]) #=> #<Set: {1, "c", :s}> - * Set.new(1..5) #=> #<Set: {1, 2, 3, 4, 5}> - * Set.new([1, 2, 3]) { |x| x * x } #=> #<Set: {1, 4, 9}> + * Set.new([1, 2]) #=> Set[1, 2] + * Set.new([1, 2, 1]) #=> Set[1, 2] + * Set.new([1, 'c', :s]) #=> Set[1, "c", :s] + * Set.new(1..5) #=> Set[1, 2, 3, 4, 5] + * Set.new([1, 2, 3]) { |x| x * x } #=> Set[1, 4, 9] */ static VALUE set_i_initialize(int argc, VALUE *argv, VALUE set) @@ -513,6 +533,7 @@ set_i_initialize(int argc, VALUE *argv, VALUE set) return set; } +/* :nodoc: */ static VALUE set_i_initialize_copy(VALUE set, VALUE other) { @@ -527,6 +548,7 @@ set_i_initialize_copy(VALUE set, VALUE other) set_free_embedded(sobj); set_copy(&sobj->table, RSET_TABLE(other)); + rb_gc_writebarrier_remember(set); return set; } @@ -534,10 +556,14 @@ set_i_initialize_copy(VALUE set, VALUE other) static int set_inspect_i(st_data_t key, st_data_t arg) { - VALUE str = (VALUE)arg; - if (RSTRING_LEN(str) > 8) { + VALUE *args = (VALUE*)arg; + VALUE str = args[0]; + if (args[1] == Qtrue) { rb_str_buf_cat_ascii(str, ", "); } + else { + args[1] = Qtrue; + } rb_str_buf_append(str, rb_inspect((VALUE)key)); return ST_CONTINUE; @@ -547,11 +573,17 @@ static VALUE set_inspect(VALUE set, VALUE dummy, int recur) { VALUE str; + VALUE klass_name = rb_class_path(CLASS_OF(set)); - if (recur) return rb_usascii_str_new2("#<Set: {...}>"); - str = rb_str_buf_new2("#<Set: {"); - set_iter(set, set_inspect_i, str); - rb_str_buf_cat2(str, "}>"); + if (recur) { + str = rb_sprintf("%"PRIsVALUE"[...]", klass_name); + return rb_str_export_to_enc(str, rb_usascii_encoding()); + } + + str = rb_sprintf("%"PRIsVALUE"[", klass_name); + VALUE args[2] = {str, Qfalse}; + set_iter(set, set_inspect_i, (st_data_t)args); + rb_str_buf_cat2(str, "]"); return str; } @@ -563,11 +595,11 @@ set_inspect(VALUE set, VALUE dummy, int recur) * Returns a new string containing the set entries: * * s = Set.new - * s.inspect # => "#<Set: {}>" + * s.inspect # => "Set[]" * s.add(1) - * s.inspect # => "#<Set: {1}>" + * s.inspect # => "Set[1]" * s.add(2) - * s.inspect # => "#<Set: {1, 2}>" + * s.inspect # => "Set[1, 2]" * * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting]. */ @@ -616,35 +648,22 @@ set_i_to_a(VALUE set) /* * call-seq: - * to_set(klass = Set, *args, &block) -> self or new_set + * to_set(&block) -> self or new_set * - * Returns self if receiver is an instance of +Set+ and no arguments or - * block are given. Otherwise, converts the set to another with - * <tt>klass.new(self, *args, &block)</tt>. + * Without a block, if +self+ is an instance of +Set+, returns +self+. + * Otherwise, calls <tt>Set.new(self, &block)</tt>. * - * In subclasses, returns `klass.new(self, *args, &block)` unless overridden. + * A form with arguments is _deprecated_. It converts the set to another + * with <tt>klass.new(self, *args, &block)</tt>. */ static VALUE -set_i_to_set(int argc, VALUE *argv, VALUE set) +set_i_to_set(VALUE set) { - VALUE klass; - - if (argc == 0) { - klass = rb_cSet; - argv = &set; - argc = 1; - } - else { - klass = argv[0]; - argv[0] = set; - } - - if (klass == rb_cSet && rb_obj_is_instance_of(set, rb_cSet) && - argc == 1 && !rb_block_given_p()) { + if (rb_obj_is_instance_of(set, rb_cSet) && !rb_block_given_p()) { return set; } - return rb_funcall_passing_block(klass, id_new, argc, argv); + return rb_funcall_passing_block(rb_cSet, id_new, 0, NULL); } /* @@ -664,19 +683,19 @@ set_i_join(int argc, VALUE *argv, VALUE set) * call-seq: * add(obj) -> self * - * Adds the given object to the set and returns self. Use `merge` to + * Adds the given object to the set and returns self. Use Set#merge to * add many elements at once. * - * Set[1, 2].add(3) #=> #<Set: {1, 2, 3}> - * Set[1, 2].add([3, 4]) #=> #<Set: {1, 2, [3, 4]}> - * Set[1, 2].add(2) #=> #<Set: {1, 2}> + * Set[1, 2].add(3) #=> Set[1, 2, 3] + * Set[1, 2].add([3, 4]) #=> Set[1, 2, [3, 4]] + * Set[1, 2].add(2) #=> Set[1, 2] */ static VALUE set_i_add(VALUE set, VALUE item) { rb_check_frozen(set); if (set_iterating_p(set)) { - if (!set_lookup(RSET_TABLE(set), (st_data_t)item)) { + if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) { no_new_item(); } } @@ -693,8 +712,8 @@ set_i_add(VALUE set, VALUE item) * Adds the given object to the set and returns self. If the object is * already in the set, returns nil. * - * Set[1, 2].add?(3) #=> #<Set: {1, 2, 3}> - * Set[1, 2].add?([3, 4]) #=> #<Set: {1, 2, [3, 4]}> + * Set[1, 2].add?(3) #=> Set[1, 2, 3] + * Set[1, 2].add?([3, 4]) #=> Set[1, 2, [3, 4]] * Set[1, 2].add?(2) #=> nil */ static VALUE @@ -702,7 +721,7 @@ set_i_add_p(VALUE set, VALUE item) { rb_check_frozen(set); if (set_iterating_p(set)) { - if (!set_lookup(RSET_TABLE(set), (st_data_t)item)) { + if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) { no_new_item(); } return Qnil; @@ -723,7 +742,7 @@ static VALUE set_i_delete(VALUE set, VALUE item) { rb_check_frozen(set); - if (set_delete(RSET_TABLE(set), (st_data_t *)&item)) { + if (set_table_delete(RSET_TABLE(set), (st_data_t *)&item)) { set_compact_after_delete(set); } return set; @@ -740,7 +759,7 @@ static VALUE set_i_delete_p(VALUE set, VALUE item) { rb_check_frozen(set); - if (set_delete(RSET_TABLE(set), (st_data_t *)&item)) { + if (set_table_delete(RSET_TABLE(set), (st_data_t *)&item)) { set_compact_after_delete(set); return set; } @@ -823,9 +842,9 @@ set_classify_i(st_data_t key, st_data_t tmp) * * files = Set.new(Dir.glob("*.rb")) * hash = files.classify { |f| File.mtime(f).year } - * hash #=> {2000 => #<Set: {"a.rb", "b.rb"}>, - * # 2001 => #<Set: {"c.rb", "d.rb", "e.rb"}>, - * # 2002 => #<Set: {"f.rb"}>} + * hash #=> {2000 => Set["a.rb", "b.rb"], + * # 2001 => Set["c.rb", "d.rb", "e.rb"], + * # 2002 => Set["f.rb"]} * * Returns an enumerator if no block is given. */ @@ -840,66 +859,72 @@ set_i_classify(VALUE set) return args[0]; } -struct set_divide_args { - VALUE self; - VALUE set_class; - VALUE final_set; - VALUE hash; - VALUE current_set; - VALUE current_item; - unsigned long ni; - unsigned long nj; -}; +// Union-find with path compression +static long +set_divide_union_find_root(long *uf_parents, long index, long *tmp_array) +{ + long root = uf_parents[index]; + long update_size = 0; + while (root != index) { + tmp_array[update_size++] = index; + index = root; + root = uf_parents[index]; + } + for (long j = 0; j < update_size; j++) { + long idx = tmp_array[j]; + uf_parents[idx] = root; + } + return root; +} -static VALUE -set_divide_block0(RB_BLOCK_CALL_FUNC_ARGLIST(j, arg)) -{ - struct set_divide_args *args = (struct set_divide_args *)arg; - if (args->nj > args->ni) { - VALUE i = args->current_item; - if (RTEST(rb_yield_values(2, i, j)) && RTEST(rb_yield_values(2, j, i))) { - VALUE hash = args->hash; - if (args->current_set == Qnil) { - VALUE set = rb_hash_aref(hash, j); - if (set == Qnil) { - VALUE both[2] = {i, j}; - set = set_s_create(2, both, args->set_class); - rb_hash_aset(hash, i, set); - rb_hash_aset(hash, j, set); - set_i_add(args->final_set, set); - } - else { - set_i_add(set, i); - rb_hash_aset(hash, i, set); - } - args->current_set = set; - } - else { - set_i_add(args->current_set, j); - rb_hash_aset(hash, j, args->current_set); +static void +set_divide_union_find_merge(long *uf_parents, long i, long j, long *tmp_array) +{ + long root_i = set_divide_union_find_root(uf_parents, i, tmp_array); + long root_j = set_divide_union_find_root(uf_parents, j, tmp_array); + if (root_i != root_j) uf_parents[root_j] = root_i; +} + +static VALUE +set_divide_arity2(VALUE set) +{ + VALUE tmp, uf; + long size, *uf_parents, *tmp_array; + VALUE set_class = rb_obj_class(set); + VALUE items = set_i_to_a(set); + rb_ary_freeze(items); + size = RARRAY_LEN(items); + tmp_array = ALLOCV_N(long, tmp, size); + uf_parents = ALLOCV_N(long, uf, size); + for (long i = 0; i < size; i++) { + uf_parents[i] = i; + } + for (long i = 0; i < size - 1; i++) { + VALUE item1 = RARRAY_AREF(items, i); + for (long j = i + 1; j < size; j++) { + VALUE item2 = RARRAY_AREF(items, j); + if (RTEST(rb_yield_values(2, item1, item2)) && + RTEST(rb_yield_values(2, item2, item1))) { + set_divide_union_find_merge(uf_parents, i, j, tmp_array); } } } - args->nj++; - return j; -} - -static VALUE -set_divide_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, arg)) -{ - struct set_divide_args *args = (struct set_divide_args *)arg; - VALUE hash = args->hash; - args->current_set = rb_hash_aref(hash, i); - args->current_item = i; - args->nj = 0; - rb_block_call(args->self, id_each, 0, 0, set_divide_block0, arg); - if (args->current_set == Qnil) { - VALUE set = set_s_create(1, &i, args->set_class); - rb_hash_aset(hash, i, set); - set_i_add(args->final_set, set); + VALUE final_set = set_s_create(0, 0, rb_cSet); + VALUE hash = rb_hash_new(); + for (long i = 0; i < size; i++) { + VALUE v = RARRAY_AREF(items, i); + long root = set_divide_union_find_root(uf_parents, i, tmp_array); + VALUE set = rb_hash_aref(hash, LONG2FIX(root)); + if (set == Qnil) { + set = set_s_create(0, 0, set_class); + rb_hash_aset(hash, LONG2FIX(root), set); + set_i_add(final_set, set); + } + set_i_add(set, v); } - args->ni++; - return i; + ALLOCV_END(tmp); + ALLOCV_END(uf); + return final_set; } static void set_merge_enum_into(VALUE set, VALUE arg); @@ -920,10 +945,10 @@ static void set_merge_enum_into(VALUE set, VALUE arg); * * numbers = Set[1, 3, 4, 6, 9, 10, 11] * set = numbers.divide { |i,j| (i - j).abs == 1 } - * set #=> #<Set: {#<Set: {1}>, - * # #<Set: {3, 4}>, - * # #<Set: {6}>}> - * # #<Set: {9, 10, 11}>, + * set #=> Set[Set[1], + * # Set[3, 4], + * # Set[6], + * # Set[9, 10, 11]] * * Returns an enumerator if no block is given. */ @@ -933,19 +958,7 @@ set_i_divide(VALUE set) RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size); if (rb_block_arity() == 2) { - VALUE final_set = set_s_create(0, 0, rb_cSet); - struct set_divide_args args = { - .self = set, - .set_class = rb_obj_class(set), - .final_set = final_set, - .hash = rb_hash_new(), - .current_set = 0, - .current_item = 0, - .ni = 0, - .nj = 0 - }; - rb_block_call(set, id_each, 0, 0, set_divide_block, (VALUE)&args); - return final_set; + return set_divide_arity2(set); } VALUE values = rb_hash_values(set_i_classify(set)); @@ -966,9 +979,9 @@ set_clear_i(st_data_t key, st_data_t dummy) * * Removes all elements and returns self. * - * set = Set[1, 'c', :s] #=> #<Set: {1, "c", :s}> - * set.clear #=> #<Set: {}> - * set #=> #<Set: {}> + * set = Set[1, 'c', :s] #=> Set[1, "c", :s] + * set.clear #=> Set[] + * set #=> Set[] */ static VALUE set_i_clear(VALUE set) @@ -979,7 +992,7 @@ set_i_clear(VALUE set) set_iter(set, set_clear_i, 0); } else { - set_clear(RSET_TABLE(set)); + set_table_clear(RSET_TABLE(set)); set_compact_after_delete(set); } return set; @@ -995,7 +1008,7 @@ static int set_intersection_i(st_data_t key, st_data_t tmp) { struct set_intersection_data *data = (struct set_intersection_data *)tmp; - if (set_lookup(data->other, key)) { + if (set_table_lookup(data->other, key)) { set_table_insert_wb(data->into, data->set, key, NULL); } @@ -1016,8 +1029,8 @@ set_intersection_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, data)) * Returns a new set containing elements common to the set and the given * enumerable object. * - * Set[1, 3, 5] & Set[3, 2, 1] #=> #<Set: {3, 1}> - * Set['a', 'b', 'z'] & ['a', 'b', 'c'] #=> #<Set: {"a", "b"}> + * Set[1, 3, 5] & Set[3, 2, 1] #=> Set[3, 1] + * Set['a', 'b', 'z'] & ['a', 'b', 'c'] #=> Set["a", "b"] */ static VALUE set_i_intersection(VALUE set, VALUE other) @@ -1245,7 +1258,7 @@ set_xor_i(st_data_t key, st_data_t data) VALUE set = (VALUE)data; set_table *table = RSET_TABLE(set); if (set_table_insert_wb(table, set, element, &element)) { - set_delete(table, &element); + set_table_delete(table, &element); } return ST_CONTINUE; } @@ -1258,21 +1271,23 @@ set_xor_i(st_data_t key, st_data_t data) * given enumerable object. <tt>(set ^ enum)</tt> is equivalent to * <tt>((set | enum) - (set & enum))</tt>. * - * Set[1, 2] ^ Set[2, 3] #=> #<Set: {3, 1}> - * Set[1, 'b', 'c'] ^ ['b', 'd'] #=> #<Set: {"d", 1, "c"}> + * Set[1, 2] ^ Set[2, 3] #=> Set[3, 1] + * Set[1, 'b', 'c'] ^ ['b', 'd'] #=> Set["d", 1, "c"] */ static VALUE set_i_xor(VALUE set, VALUE other) { - VALUE new_set; + VALUE new_set = rb_obj_dup(set); + if (rb_obj_is_kind_of(other, rb_cSet)) { - new_set = other; + set_iter(other, set_xor_i, (st_data_t)new_set); } else { - new_set = set_s_alloc(rb_obj_class(set)); - set_merge_enum_into(new_set, other); + VALUE tmp = set_s_alloc(rb_cSet); + set_merge_enum_into(tmp, other); + set_iter(tmp, set_xor_i, (st_data_t)new_set); } - set_iter(set, set_xor_i, (st_data_t)new_set); + return new_set; } @@ -1283,8 +1298,8 @@ set_i_xor(VALUE set, VALUE other) * Returns a new set built by merging the set and the elements of the * given enumerable object. * - * Set[1, 2, 3] | Set[2, 4, 5] #=> #<Set: {1, 2, 3, 4, 5}> - * Set[1, 5, 'z'] | (1..6) #=> #<Set: {1, 5, "z", 2, 3, 4, 6}> + * Set[1, 2, 3] | Set[2, 4, 5] #=> Set[1, 2, 3, 4, 5] + * Set[1, 5, 'z'] | (1..6) #=> Set[1, 5, "z", 2, 3, 4, 6] */ static VALUE set_i_union(VALUE set, VALUE other) @@ -1297,7 +1312,7 @@ set_i_union(VALUE set, VALUE other) static int set_remove_i(st_data_t key, st_data_t from) { - set_delete((struct set_table *)from, (st_data_t *)&key); + set_table_delete((struct set_table *)from, (st_data_t *)&key); return ST_CONTINUE; } @@ -1305,7 +1320,7 @@ static VALUE set_remove_block(RB_BLOCK_CALL_FUNC_ARGLIST(key, set)) { rb_check_frozen(set); - set_delete(RSET_TABLE(set), (st_data_t *)&key); + set_table_delete(RSET_TABLE(set), (st_data_t *)&key); return key; } @@ -1342,8 +1357,8 @@ set_i_subtract(VALUE set, VALUE other) * Returns a new set built by duplicating the set, removing every * element that appears in the given enumerable object. * - * Set[1, 3, 5] - Set[1, 5] #=> #<Set: {3}> - * Set['a', 'b', 'z'] - ['a', 'c'] #=> #<Set: {"b", "z"}> + * Set[1, 3, 5] - Set[1, 5] #=> Set[3] + * Set['a', 'b', 'z'] - ['a', 'c'] #=> Set["b", "z"] */ static VALUE set_i_difference(VALUE set, VALUE other) @@ -1407,7 +1422,7 @@ static int set_keep_if_i(st_data_t key, st_data_t into) { if (!RTEST(rb_yield((VALUE)key))) { - set_delete((set_table *)into, &key); + set_table_delete((set_table *)into, &key); } return ST_CONTINUE; } @@ -1459,9 +1474,9 @@ set_i_select(VALUE set) * Replaces the contents of the set with the contents of the given * enumerable object and returns self. * - * set = Set[1, 'c', :s] #=> #<Set: {1, "c", :s}> - * set.replace([1, 2]) #=> #<Set: {1, 2}> - * set #=> #<Set: {1, 2}> + * set = Set[1, 'c', :s] #=> Set[1, "c", :s] + * set.replace([1, 2]) #=> Set[1, 2] + * set #=> Set[1, 2] */ static VALUE set_i_replace(VALUE set, VALUE other) @@ -1479,7 +1494,7 @@ set_i_replace(VALUE set, VALUE other) // make sure enum is enumerable before calling clear enum_method_id(other); - set_clear(RSET_TABLE(set)); + set_table_clear(RSET_TABLE(set)); set_merge_enum_into(set, other); } @@ -1590,7 +1605,7 @@ static int set_le_i(st_data_t key, st_data_t arg) { struct set_subset_data *data = (struct set_subset_data *)arg; - if (set_lookup(data->table, key)) return ST_CONTINUE; + if (set_table_lookup(data->table, key)) return ST_CONTINUE; data->result = Qfalse; return ST_STOP; } @@ -1666,7 +1681,7 @@ static int set_intersect_i(st_data_t key, st_data_t arg) { VALUE *args = (VALUE *)arg; - if (set_lookup((set_table *)args[0], key)) { + if (set_table_lookup((set_table *)args[0], key)) { args[1] = Qtrue; return ST_STOP; } @@ -1737,7 +1752,7 @@ set_i_disjoint(VALUE set, VALUE other) * set <=> other -> -1, 0, 1, or nil * * Returns 0 if the set are equal, -1 / 1 if the set is a - * proper subset / superset of the given set, or or nil if + * proper subset / superset of the given set, or nil if * they both have unique elements. */ static VALUE @@ -1775,7 +1790,7 @@ set_eql_i(st_data_t item, st_data_t arg) { struct set_equal_data *data = (struct set_equal_data *)arg; - if (!set_lookup(RSET_TABLE(data->set), item)) { + if (!set_table_lookup(RSET_TABLE(data->set), item)) { data->result = Qfalse; return ST_STOP; } @@ -1906,24 +1921,67 @@ compat_loader(VALUE self, VALUE a) return set_i_from_hash(self, rb_ivar_get(a, id_i_hash)); } +/* C-API functions */ + +void +rb_set_foreach(VALUE set, int (*func)(VALUE element, VALUE arg), VALUE arg) +{ + set_iter(set, func, arg); +} + +VALUE +rb_set_new(void) +{ + return set_alloc_with_size(rb_cSet, 0); +} + +VALUE +rb_set_new_capa(size_t capa) +{ + return set_alloc_with_size(rb_cSet, (st_index_t)capa); +} + +bool +rb_set_lookup(VALUE set, VALUE element) +{ + return RSET_IS_MEMBER(set, element); +} + +bool +rb_set_add(VALUE set, VALUE element) +{ + return set_i_add_p(set, element) != Qnil; +} + +VALUE +rb_set_clear(VALUE set) +{ + return set_i_clear(set); +} + +bool +rb_set_delete(VALUE set, VALUE element) +{ + return set_i_delete_p(set, element) != Qnil; +} + +size_t +rb_set_size(VALUE set) +{ + return RSET_SIZE(set); +} + /* * Document-class: Set * - * Copyright (c) 2002-2024 Akinori MUSHA <knu@iDaemons.org> - * - * Documentation by Akinori MUSHA and Gavin Sinclair. - * - * All rights reserved. You can redistribute and/or modify it under the same - * terms as Ruby. - * * The Set class implements a collection of unordered values with no * duplicates. It is a hybrid of Array's intuitive inter-operation * facilities and Hash's fast lookup. * - * Set is easy to use with Enumerable objects (implementing `each`). + * Set is easy to use with Enumerable objects (implementing #each). * Most of the initializer methods and binary operators accept generic * Enumerable objects besides sets and arrays. An Enumerable object - * can be converted to Set using the `to_set` method. + * can be converted to Set using the +to_set+ method. * * Set uses a data structure similar to Hash for storage, except that * it only has keys and no values. @@ -1947,11 +2005,11 @@ compat_loader(VALUE self, VALUE a) * * == Example * - * s1 = Set[1, 2] #=> #<Set: {1, 2}> - * s2 = [1, 2].to_set #=> #<Set: {1, 2}> + * s1 = Set[1, 2] #=> Set[1, 2] + * s2 = [1, 2].to_set #=> Set[1, 2] * s1 == s2 #=> true - * s1.add("foo") #=> #<Set: {1, 2, "foo"}> - * s1.merge([2, 6]) #=> #<Set: {1, 2, "foo", 6}> + * s1.add("foo") #=> Set[1, 2, "foo"] + * s1.merge([2, 6]) #=> Set[1, 2, "foo", 6] * s1.subset?(s2) #=> false * s2.subset?(s1) #=> true * @@ -1959,9 +2017,39 @@ compat_loader(VALUE self, VALUE a) * * - Akinori MUSHA <knu@iDaemons.org> (current maintainer) * - * == What's Here + * == Inheriting from \Set + * + * Before Ruby 4.0 (released December 2025), \Set had a different, less + * efficient implementation. It was reimplemented in C, and the behavior + * of some of the core methods were adjusted. * - * First, what's elsewhere. \Class \Set: + * To keep backward compatibility, when a class is inherited from \Set, + * additional module +Set::SubclassCompatible+ is included, which makes + * the inherited class behavior, as well as internal method names, + * closer to what it was before Ruby 4.0. + * + * It can be easily seen, for example, in the #inspect method behavior: + * + * p Set[1, 2, 3] + * # prints "Set[1, 2, 3]" + * + * class MySet < Set + * end + * p MySet[1, 2, 3] + * # prints "#<MySet: {1, 2, 3}>", like it was in Ruby 3.4 + * + * For new code, if backward compatibility is not necessary, + * it is recommended to instead inherit from +Set::CoreSet+, which + * avoids including the "compatibility" layer: + * + * class MyCoreSet < Set::CoreSet + * end + * p MyCoreSet[1, 2, 3] + * # prints "MyCoreSet[1, 2, 3]" + * + * == Set's methods + * + * First, what's elsewhere. \Class \Set: * * - Inherits from {class Object}[rdoc-ref:Object@What-27s+Here]. * - Includes {module Enumerable}[rdoc-ref:Enumerable@What-27s+Here], @@ -1973,16 +2061,15 @@ compat_loader(VALUE self, VALUE a) * * Here, class \Set provides methods that are useful for: * - * - {Creating an Array}[rdoc-ref:Array@Methods+for+Creating+an+Array] - * - {Creating a Set}[rdoc-ref:Array@Methods+for+Creating+a+Set] - * - {Set Operations}[rdoc-ref:Array@Methods+for+Set+Operations] - * - {Comparing}[rdoc-ref:Array@Methods+for+Comparing] - * - {Querying}[rdoc-ref:Array@Methods+for+Querying] - * - {Assigning}[rdoc-ref:Array@Methods+for+Assigning] - * - {Deleting}[rdoc-ref:Array@Methods+for+Deleting] - * - {Converting}[rdoc-ref:Array@Methods+for+Converting] - * - {Iterating}[rdoc-ref:Array@Methods+for+Iterating] - * - {And more....}[rdoc-ref:Array@Other+Methods] + * - {Creating a Set}[rdoc-ref:Set@Methods+for+Creating+a+Set] + * - {Set Operations}[rdoc-ref:Set@Methods+for+Set+Operations] + * - {Comparing}[rdoc-ref:Set@Methods+for+Comparing] + * - {Querying}[rdoc-ref:Set@Methods+for+Querying] + * - {Assigning}[rdoc-ref:Set@Methods+for+Assigning] + * - {Deleting}[rdoc-ref:Set@Methods+for+Deleting] + * - {Converting}[rdoc-ref:Set@Methods+for+Converting] + * - {Iterating}[rdoc-ref:Set@Methods+for+Iterating] + * - {And more....}[rdoc-ref:Set@Other+Methods] * * === Methods for Creating a \Set * @@ -2125,6 +2212,8 @@ Init_Set(void) id_any_p = rb_intern_const("any?"); id_new = rb_intern_const("new"); id_i_hash = rb_intern_const("@hash"); + id_subclass_compatible = rb_intern_const("SubclassCompatible"); + id_class_methods = rb_intern_const("ClassMethods"); id_set_iter_lev = rb_make_internal_id(); rb_define_alloc_func(rb_cSet, set_s_alloc); @@ -2189,11 +2278,16 @@ Init_Set(void) rb_define_method(rb_cSet, "superset?", set_i_superset, 1); rb_define_alias(rb_cSet, ">=", "superset?"); rb_define_method(rb_cSet, "to_a", set_i_to_a, 0); - rb_define_method(rb_cSet, "to_set", set_i_to_set, -1); + rb_define_method(rb_cSet, "to_set", set_i_to_set, 0); /* :nodoc: */ VALUE compat = rb_define_class_under(rb_cSet, "compatible", rb_cObject); rb_marshal_define_compat(rb_cSet, compat, compat_dumper, compat_loader); + // Create Set::CoreSet before defining inherited, so it does not include + // the backwards compatibility layer. + rb_define_class_under(rb_cSet, "CoreSet", rb_cSet); + rb_define_private_method(rb_singleton_class(rb_cSet), "inherited", set_s_inherited, 1); + rb_provide("set.rb"); } |