Ruby 4.0.10p0 (2026-11-19 revision a704b7cd95a42cc0cf5f307137bf3aac0285b915)
set.c
1/* This implements sets using the same hash table implementation as in
2 st.c, but without a value for each hash entry. This results in the
3 same basic performance characteristics as when using an st table,
4 but uses 1/3 less memory.
5 */
6
7#include "id.h"
8#include "internal.h"
9#include "internal/bits.h"
10#include "internal/error.h"
11#include "internal/hash.h"
12#include "internal/proc.h"
13#include "internal/sanitizers.h"
14#include "internal/set_table.h"
15#include "internal/symbol.h"
16#include "internal/variable.h"
17#include "ruby_assert.h"
18
19#include <stdio.h>
20#ifdef HAVE_STDLIB_H
21#include <stdlib.h>
22#endif
23#include <string.h>
24
25#ifndef SET_DEBUG
26#define SET_DEBUG 0
27#endif
28
29#if SET_DEBUG
30#include "internal/gc.h"
31#endif
32
33static st_index_t
34dbl_to_index(double d)
35{
36 union {double d; st_index_t i;} u;
37 u.d = d;
38 return u.i;
39}
40
41static const uint64_t prime1 = ((uint64_t)0x2e0bb864 << 32) | 0xe9ea7df5;
42static const uint32_t prime2 = 0x830fcab9;
43
44static inline uint64_t
45mult_and_mix(uint64_t m1, uint64_t m2)
46{
47#if defined HAVE_UINT128_T
48 uint128_t r = (uint128_t) m1 * (uint128_t) m2;
49 return (uint64_t) (r >> 64) ^ (uint64_t) r;
50#else
51 uint64_t hm1 = m1 >> 32, hm2 = m2 >> 32;
52 uint64_t lm1 = m1, lm2 = m2;
53 uint64_t v64_128 = hm1 * hm2;
54 uint64_t v32_96 = hm1 * lm2 + lm1 * hm2;
55 uint64_t v1_32 = lm1 * lm2;
56
57 return (v64_128 + (v32_96 >> 32)) ^ ((v32_96 << 32) + v1_32);
58#endif
59}
60
61static inline uint64_t
62key64_hash(uint64_t key, uint32_t seed)
63{
64 return mult_and_mix(key + seed, prime1);
65}
66
67/* Should cast down the result for each purpose */
68#define set_index_hash(index) key64_hash(rb_hash_start(index), prime2)
69
70static st_index_t
71set_ident_hash(st_data_t n)
72{
73#ifdef USE_FLONUM /* RUBY */
74 /*
75 * - flonum (on 64-bit) is pathologically bad, mix the actual
76 * float value in, but do not use the float value as-is since
77 * many integers get interpreted as 2.0 or -2.0 [Bug #10761]
78 */
79 if (FLONUM_P(n)) {
80 n ^= dbl_to_index(rb_float_value(n));
81 }
82#endif
83
84 return (st_index_t)set_index_hash((st_index_t)n);
85}
86
87static const struct st_hash_type identhash = {
88 rb_st_numcmp,
89 set_ident_hash,
90};
91
92static const struct st_hash_type objhash = {
93 rb_any_cmp,
94 rb_any_hash,
95};
96
98static VALUE set_i_compare_by_identity(VALUE set);
99
100#define id_each idEach
101static ID id_each_entry;
102static ID id_any_p;
103static ID id_new;
104static ID id_i_hash;
105static ID id_set_iter_lev;
106static ID id_subclass_compatible;
107static ID id_class_methods;
108
109#define RSET_INITIALIZED FL_USER1
110#define RSET_LEV_MASK (FL_USER13 | FL_USER14 | FL_USER15 | /* FL 13..19 */ \
111 FL_USER16 | FL_USER17 | FL_USER18 | FL_USER19)
112#define RSET_LEV_SHIFT (FL_USHIFT + 13)
113#define RSET_LEV_MAX 127 /* 7 bits */
114
115#define SET_ASSERT(expr) RUBY_ASSERT_MESG_WHEN(SET_DEBUG, expr, #expr)
116
117#define RSET_SIZE(set) set_table_size(RSET_TABLE(set))
118#define RSET_EMPTY(set) (RSET_SIZE(set) == 0)
119#define RSET_SIZE_NUM(set) SIZET2NUM(RSET_SIZE(set))
120#define RSET_IS_MEMBER(sobj, item) set_table_lookup(RSET_TABLE(set), (st_data_t)(item))
121#define RSET_COMPARE_BY_IDENTITY(set) (RSET_TABLE(set)->type == &identhash)
122
124 set_table table;
125};
126
127static int
128mark_and_pin_key(st_data_t key, st_data_t data)
129{
130 rb_gc_mark((VALUE)key);
131
132 return ST_CONTINUE;
133}
134
135static int
136mark_key(st_data_t key, st_data_t data)
137{
138 rb_gc_mark_movable((VALUE)key);
139
140 return ST_CONTINUE;
141}
142
143static void
144set_mark(void *ptr)
145{
146 struct set_object *sobj = ptr;
147 if (sobj->table.entries) {
148 if (sobj->table.type == &identhash) {
149 set_table_foreach(&sobj->table, mark_and_pin_key, 0);
150 }
151 else {
152 set_table_foreach(&sobj->table, mark_key, 0);
153 }
154 }
155}
156
157static void
158set_free_embedded(struct set_object *sobj)
159{
160 free((&sobj->table)->entries);
161}
162
163static void
164set_free(void *ptr)
165{
166 struct set_object *sobj = ptr;
167 set_free_embedded(sobj);
168 memset(&sobj->table, 0, sizeof(sobj->table));
169}
170
171static size_t
172set_size(const void *ptr)
173{
174 const struct set_object *sobj = ptr;
175 /* Do not count the table size twice, as it is embedded */
176 return (unsigned long)set_memsize(&sobj->table) - sizeof(sobj->table);
177}
178
179static int
180set_foreach_replace(st_data_t key, st_data_t argp, int error)
181{
182 if (rb_gc_location((VALUE)key) != (VALUE)key) {
183 return ST_REPLACE;
184 }
185
186 return ST_CONTINUE;
187}
188
189static int
190set_replace_ref(st_data_t *key, st_data_t argp, int existing)
191{
192 rb_gc_mark_and_move((VALUE *)key);
193
194 return ST_CONTINUE;
195}
196
197static void
198set_update_references(void *ptr)
199{
200 struct set_object *sobj = ptr;
201 set_foreach_with_replace(&sobj->table, set_foreach_replace, set_replace_ref, 0);
202}
203
204static const rb_data_type_t set_data_type = {
205 .wrap_struct_name = "set",
206 .function = {
207 .dmark = set_mark,
208 .dfree = set_free,
209 .dsize = set_size,
210 .dcompact = set_update_references,
211 },
212 .flags = RUBY_TYPED_EMBEDDABLE | RUBY_TYPED_FREE_IMMEDIATELY | RUBY_TYPED_WB_PROTECTED | RUBY_TYPED_FROZEN_SHAREABLE
213};
214
215static inline set_table *
216RSET_TABLE(VALUE set)
217{
218 struct set_object *sobj;
219 TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);
220 return &sobj->table;
221}
222
223static unsigned long
224iter_lev_in_ivar(VALUE set)
225{
226 VALUE levval = rb_ivar_get(set, id_set_iter_lev);
227 SET_ASSERT(FIXNUM_P(levval));
228 long lev = FIX2LONG(levval);
229 SET_ASSERT(lev >= 0);
230 return (unsigned long)lev;
231}
232
233void rb_ivar_set_internal(VALUE obj, ID id, VALUE val);
234
235static void
236iter_lev_in_ivar_set(VALUE set, unsigned long lev)
237{
238 SET_ASSERT(lev >= RSET_LEV_MAX);
239 SET_ASSERT(POSFIXABLE(lev)); /* POSFIXABLE means fitting to long */
240 rb_ivar_set_internal(set, id_set_iter_lev, LONG2FIX((long)lev));
241}
242
243static inline unsigned long
244iter_lev_in_flags(VALUE set)
245{
246 return (unsigned long)((RBASIC(set)->flags >> RSET_LEV_SHIFT) & RSET_LEV_MAX);
247}
248
249static inline void
250iter_lev_in_flags_set(VALUE set, unsigned long lev)
251{
252 SET_ASSERT(lev <= RSET_LEV_MAX);
253 RBASIC(set)->flags = ((RBASIC(set)->flags & ~RSET_LEV_MASK) | ((VALUE)lev << RSET_LEV_SHIFT));
254}
255
256static inline bool
257set_iterating_p(VALUE set)
258{
259 return iter_lev_in_flags(set) > 0;
260}
261
262static void
263set_iter_lev_inc(VALUE set)
264{
265 unsigned long lev = iter_lev_in_flags(set);
266 if (lev == RSET_LEV_MAX) {
267 lev = iter_lev_in_ivar(set) + 1;
268 if (!POSFIXABLE(lev)) { /* paranoiac check */
269 rb_raise(rb_eRuntimeError, "too much nested iterations");
270 }
271 }
272 else {
273 lev += 1;
274 iter_lev_in_flags_set(set, lev);
275 if (lev < RSET_LEV_MAX) return;
276 }
277 iter_lev_in_ivar_set(set, lev);
278}
279
280static void
281set_iter_lev_dec(VALUE set)
282{
283 unsigned long lev = iter_lev_in_flags(set);
284 if (lev == RSET_LEV_MAX) {
285 lev = iter_lev_in_ivar(set);
286 if (lev > RSET_LEV_MAX) {
287 iter_lev_in_ivar_set(set, lev-1);
288 return;
289 }
290 rb_attr_delete(set, id_set_iter_lev);
291 }
292 else if (lev == 0) {
293 rb_raise(rb_eRuntimeError, "iteration level underflow");
294 }
295 iter_lev_in_flags_set(set, lev - 1);
296}
297
298static VALUE
299set_foreach_ensure(VALUE set)
300{
301 set_iter_lev_dec(set);
302 return 0;
303}
304
305typedef int set_foreach_func(VALUE, VALUE);
306
308 VALUE set;
309 set_foreach_func *func;
310 VALUE arg;
311};
312
313static int
314set_iter_status_check(int status)
315{
316 if (status == ST_CONTINUE) {
317 return ST_CHECK;
318 }
319
320 return status;
321}
322
323static int
324set_foreach_iter(st_data_t key, st_data_t argp, int error)
325{
326 struct set_foreach_arg *arg = (struct set_foreach_arg *)argp;
327
328 if (error) return ST_STOP;
329
330 set_table *tbl = RSET_TABLE(arg->set);
331 int status = (*arg->func)((VALUE)key, arg->arg);
332
333 if (RSET_TABLE(arg->set) != tbl) {
334 rb_raise(rb_eRuntimeError, "reset occurred during iteration");
335 }
336
337 return set_iter_status_check(status);
338}
339
340static VALUE
341set_foreach_call(VALUE arg)
342{
343 VALUE set = ((struct set_foreach_arg *)arg)->set;
344 int ret = 0;
345 ret = set_foreach_check(RSET_TABLE(set), set_foreach_iter,
346 (st_data_t)arg, (st_data_t)Qundef);
347 if (ret) {
348 rb_raise(rb_eRuntimeError, "ret: %d, set modified during iteration", ret);
349 }
350 return Qnil;
351}
352
353static void
354set_iter(VALUE set, set_foreach_func *func, VALUE farg)
355{
356 struct set_foreach_arg arg;
357
358 if (RSET_EMPTY(set))
359 return;
360 arg.set = set;
361 arg.func = func;
362 arg.arg = farg;
363 if (RB_OBJ_FROZEN(set)) {
364 set_foreach_call((VALUE)&arg);
365 }
366 else {
367 set_iter_lev_inc(set);
368 rb_ensure(set_foreach_call, (VALUE)&arg, set_foreach_ensure, set);
369 }
370}
371
372NORETURN(static void no_new_item(void));
373static void
374no_new_item(void)
375{
376 rb_raise(rb_eRuntimeError, "can't add a new item into set during iteration");
377}
378
379static void
380set_compact_after_delete(VALUE set)
381{
382 if (!set_iterating_p(set)) {
383 set_compact_table(RSET_TABLE(set));
384 }
385}
386
387static int
388set_table_insert_wb(set_table *tab, VALUE set, VALUE key, VALUE *key_addr)
389{
390 if (tab->type != &identhash && rb_obj_class(key) == rb_cString && !RB_OBJ_FROZEN(key)) {
391 key = rb_hash_key_str(key);
392 if (key_addr) *key_addr = key;
393 }
394 int ret = set_insert(tab, (st_data_t)key);
395 if (ret == 0) RB_OBJ_WRITTEN(set, Qundef, key);
396 return ret;
397}
398
399static int
400set_insert_wb(VALUE set, VALUE key, VALUE *key_addr)
401{
402 return set_table_insert_wb(RSET_TABLE(set), set, key, key_addr);
403}
404
405static VALUE
406set_alloc_with_size(VALUE klass, st_index_t size)
407{
408 VALUE set;
409 struct set_object *sobj;
410
411 set = TypedData_Make_Struct(klass, struct set_object, &set_data_type, sobj);
412 set_init_table_with_size(&sobj->table, &objhash, size);
413
414 return set;
415}
416
417
418static VALUE
419set_s_alloc(VALUE klass)
420{
421 return set_alloc_with_size(klass, 0);
422}
423
424/*
425 * call-seq:
426 * Set[*objects] -> new_set
427 *
428 * Returns a new Set object populated with the given objects,
429 * See Set::new.
430 */
431static VALUE
432set_s_create(int argc, VALUE *argv, VALUE klass)
433{
434 VALUE set = set_alloc_with_size(klass, argc);
435 set_table *table = RSET_TABLE(set);
436 int i;
437
438 for (i=0; i < argc; i++) {
439 set_table_insert_wb(table, set, argv[i], NULL);
440 }
441
442 return set;
443}
444
445static VALUE
446set_s_inherited(VALUE klass, VALUE subclass)
447{
448 if (klass == rb_cSet) {
449 // When subclassing directly from Set, include the compatibility layer
450 rb_require("set/subclass_compatible.rb");
451 VALUE subclass_compatible = rb_const_get(klass, id_subclass_compatible);
452 rb_include_module(subclass, subclass_compatible);
453 rb_extend_object(subclass, rb_const_get(subclass_compatible, id_class_methods));
454 }
455 return Qnil;
456}
457
458static void
459check_set(VALUE arg)
460{
461 if (!rb_obj_is_kind_of(arg, rb_cSet)) {
462 rb_raise(rb_eArgError, "value must be a set");
463 }
464}
465
466static ID
467enum_method_id(VALUE other)
468{
469 if (rb_respond_to(other, id_each_entry)) {
470 return id_each_entry;
471 }
472 else if (rb_respond_to(other, id_each)) {
473 return id_each;
474 }
475 else {
476 rb_raise(rb_eArgError, "value must be enumerable");
477 }
478}
479
480static VALUE
481set_enum_size(VALUE set, VALUE args, VALUE eobj)
482{
483 return RSET_SIZE_NUM(set);
484}
485
486static VALUE
487set_initialize_without_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, set))
488{
489 VALUE element = i;
490 set_insert_wb(set, element, &element);
491 return element;
492}
493
494static VALUE
495set_initialize_with_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, set))
496{
497 VALUE element = rb_yield(i);
498 set_insert_wb(set, element, &element);
499 return element;
500}
501
502/*
503 * call-seq:
504 * Set.new -> new_set
505 * Set.new(enum) -> new_set
506 * Set.new(enum) { |elem| ... } -> new_set
507 *
508 * Creates a new set containing the elements of the given enumerable
509 * object.
510 *
511 * If a block is given, the elements of enum are preprocessed by the
512 * given block.
513 *
514 * Set.new([1, 2]) #=> Set[1, 2]
515 * Set.new([1, 2, 1]) #=> Set[1, 2]
516 * Set.new([1, 'c', :s]) #=> Set[1, "c", :s]
517 * Set.new(1..5) #=> Set[1, 2, 3, 4, 5]
518 * Set.new([1, 2, 3]) { |x| x * x } #=> Set[1, 4, 9]
519 */
520static VALUE
521set_i_initialize(int argc, VALUE *argv, VALUE set)
522{
523 if (RBASIC(set)->flags & RSET_INITIALIZED) {
524 rb_raise(rb_eRuntimeError, "cannot reinitialize set");
525 }
526 RBASIC(set)->flags |= RSET_INITIALIZED;
527
528 VALUE other;
529 rb_check_arity(argc, 0, 1);
530
531 if (argc > 0 && (other = argv[0]) != Qnil) {
532 if (RB_TYPE_P(other, T_ARRAY)) {
533 long i;
534 int block_given = rb_block_given_p();
535 set_table *into = RSET_TABLE(set);
536 for (i=0; i<RARRAY_LEN(other); i++) {
537 VALUE key = RARRAY_AREF(other, i);
538 if (block_given) key = rb_yield(key);
539 set_table_insert_wb(into, set, key, NULL);
540 }
541 }
542 else {
543 rb_block_call(other, enum_method_id(other), 0, 0,
544 rb_block_given_p() ? set_initialize_with_block : set_initialize_without_block,
545 set);
546 }
547 }
548
549 return set;
550}
551
552/* :nodoc: */
553static VALUE
554set_i_initialize_copy(VALUE set, VALUE other)
555{
556 if (set == other) return set;
557
558 if (set_iterating_p(set)) {
559 rb_raise(rb_eRuntimeError, "cannot replace set during iteration");
560 }
561
562 struct set_object *sobj;
563 TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);
564
565 set_free_embedded(sobj);
566 set_copy(&sobj->table, RSET_TABLE(other));
567 rb_gc_writebarrier_remember(set);
568
569 return set;
570}
571
572static int
573set_inspect_i(st_data_t key, st_data_t arg)
574{
575 VALUE *args = (VALUE*)arg;
576 VALUE str = args[0];
577 if (args[1] == Qtrue) {
578 rb_str_buf_cat_ascii(str, ", ");
579 }
580 else {
581 args[1] = Qtrue;
582 }
584
585 return ST_CONTINUE;
586}
587
588static VALUE
589set_inspect(VALUE set, VALUE dummy, int recur)
590{
591 VALUE str;
592 VALUE klass_name = rb_class_path(CLASS_OF(set));
593
594 if (recur) {
595 str = rb_sprintf("%"PRIsVALUE"[...]", klass_name);
596 return rb_str_export_to_enc(str, rb_usascii_encoding());
597 }
598
599 str = rb_sprintf("%"PRIsVALUE"[", klass_name);
600 VALUE args[2] = {str, Qfalse};
601 set_iter(set, set_inspect_i, (st_data_t)args);
602 rb_str_buf_cat2(str, "]");
603
604 return str;
605}
606
607/*
608 * call-seq:
609 * inspect -> new_string
610 *
611 * Returns a new string containing the set entries:
612 *
613 * s = Set.new
614 * s.inspect # => "Set[]"
615 * s.add(1)
616 * s.inspect # => "Set[1]"
617 * s.add(2)
618 * s.inspect # => "Set[1, 2]"
619 *
620 * Related: see {Methods for Converting}[rdoc-ref:Set@Methods+for+Converting].
621 */
622static VALUE
623set_i_inspect(VALUE set)
624{
625 return rb_exec_recursive(set_inspect, set, 0);
626}
627
628static int
629set_to_a_i(st_data_t key, st_data_t arg)
630{
631 rb_ary_push((VALUE)arg, (VALUE)key);
632 return ST_CONTINUE;
633}
634
635/*
636 * call-seq:
637 * to_a -> array
638 *
639 * Returns an array containing all elements in the set.
640 *
641 * Set[1, 2].to_a #=> [1, 2]
642 * Set[1, 'c', :s].to_a #=> [1, "c", :s]
643 */
644static VALUE
645set_i_to_a(VALUE set)
646{
647 st_index_t size = RSET_SIZE(set);
648 VALUE ary = rb_ary_new_capa(size);
649
650 if (size == 0) return ary;
651
652 if (ST_DATA_COMPATIBLE_P(VALUE)) {
653 RARRAY_PTR_USE(ary, ptr, {
654 size = set_keys(RSET_TABLE(set), ptr, size);
655 });
656 rb_gc_writebarrier_remember(ary);
657 rb_ary_set_len(ary, size);
658 }
659 else {
660 set_iter(set, set_to_a_i, (st_data_t)ary);
661 }
662 return ary;
663}
664
665/*
666 * call-seq:
667 * to_set(klass = Set, *args, &block) -> self or new_set
668 *
669 * Without arguments, returns +self+ (for duck-typing in methods that
670 * accept "set, or set-convertible" arguments).
671 *
672 * A form with arguments is _deprecated_. It converts the set to another
673 * with <tt>klass.new(self, *args, &block)</tt>.
674 */
675static VALUE
676set_i_to_set(int argc, VALUE *argv, VALUE set)
677{
678 VALUE klass;
679
680 if (argc == 0) {
681 klass = rb_cSet;
682 argv = &set;
683 argc = 1;
684 }
685 else {
686 rb_warn_deprecated("passing arguments to Set#to_set", NULL);
687 klass = argv[0];
688 argv[0] = set;
689 }
690
691 if (klass == rb_cSet && rb_obj_is_instance_of(set, rb_cSet) &&
692 argc == 1 && !rb_block_given_p()) {
693 return set;
694 }
695
696 return rb_funcall_passing_block(klass, id_new, argc, argv);
697}
698
699/*
700 * call-seq:
701 * join(separator=nil)-> new_string
702 *
703 * Returns a string created by converting each element of the set to a string.
704 */
705static VALUE
706set_i_join(int argc, VALUE *argv, VALUE set)
707{
708 rb_check_arity(argc, 0, 1);
709 return rb_ary_join(set_i_to_a(set), argc == 0 ? Qnil : argv[0]);
710}
711
712/*
713 * call-seq:
714 * add(obj) -> self
715 *
716 * Adds the given object to the set and returns self. Use Set#merge to
717 * add many elements at once.
718 *
719 * Set[1, 2].add(3) #=> Set[1, 2, 3]
720 * Set[1, 2].add([3, 4]) #=> Set[1, 2, [3, 4]]
721 * Set[1, 2].add(2) #=> Set[1, 2]
722 */
723static VALUE
724set_i_add(VALUE set, VALUE item)
725{
726 rb_check_frozen(set);
727 if (set_iterating_p(set)) {
728 if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
729 no_new_item();
730 }
731 }
732 else {
733 set_insert_wb(set, item, NULL);
734 }
735 return set;
736}
737
738/*
739 * call-seq:
740 * add?(obj) -> self or nil
741 *
742 * Adds the given object to the set and returns self. If the object is
743 * already in the set, returns nil.
744 *
745 * Set[1, 2].add?(3) #=> Set[1, 2, 3]
746 * Set[1, 2].add?([3, 4]) #=> Set[1, 2, [3, 4]]
747 * Set[1, 2].add?(2) #=> nil
748 */
749static VALUE
750set_i_add_p(VALUE set, VALUE item)
751{
752 rb_check_frozen(set);
753 if (set_iterating_p(set)) {
754 if (!set_table_lookup(RSET_TABLE(set), (st_data_t)item)) {
755 no_new_item();
756 }
757 return Qnil;
758 }
759 else {
760 return set_insert_wb(set, item, NULL) ? Qnil : set;
761 }
762}
763
764/*
765 * call-seq:
766 * delete(obj) -> self
767 *
768 * Deletes the given object from the set and returns self. Use subtract
769 * to delete many items at once.
770 */
771static VALUE
772set_i_delete(VALUE set, VALUE item)
773{
774 rb_check_frozen(set);
775 if (set_table_delete(RSET_TABLE(set), (st_data_t *)&item)) {
776 set_compact_after_delete(set);
777 }
778 return set;
779}
780
781/*
782 * call-seq:
783 * delete?(obj) -> self or nil
784 *
785 * Deletes the given object from the set and returns self. If the
786 * object is not in the set, returns nil.
787 */
788static VALUE
789set_i_delete_p(VALUE set, VALUE item)
790{
791 rb_check_frozen(set);
792 if (set_table_delete(RSET_TABLE(set), (st_data_t *)&item)) {
793 set_compact_after_delete(set);
794 return set;
795 }
796 return Qnil;
797}
798
799static int
800set_delete_if_i(st_data_t key, st_data_t dummy)
801{
802 return RTEST(rb_yield((VALUE)key)) ? ST_DELETE : ST_CONTINUE;
803}
804
805/*
806 * call-seq:
807 * delete_if { |o| ... } -> self
808 * delete_if -> enumerator
809 *
810 * Deletes every element of the set for which block evaluates to
811 * true, and returns self. Returns an enumerator if no block is given.
812 */
813static VALUE
814set_i_delete_if(VALUE set)
815{
816 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
817 rb_check_frozen(set);
818 set_iter(set, set_delete_if_i, 0);
819 set_compact_after_delete(set);
820 return set;
821}
822
823/*
824 * call-seq:
825 * reject! { |o| ... } -> self
826 * reject! -> enumerator
827 *
828 * Equivalent to Set#delete_if, but returns nil if no changes were made.
829 * Returns an enumerator if no block is given.
830 */
831static VALUE
832set_i_reject(VALUE set)
833{
834 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
835 rb_check_frozen(set);
836
837 set_table *table = RSET_TABLE(set);
838 size_t n = set_table_size(table);
839 set_iter(set, set_delete_if_i, 0);
840
841 if (n == set_table_size(table)) return Qnil;
842
843 set_compact_after_delete(set);
844 return set;
845}
846
847static int
848set_classify_i(st_data_t key, st_data_t tmp)
849{
850 VALUE* args = (VALUE*)tmp;
851 VALUE hash = args[0];
852 VALUE hash_key = rb_yield(key);
853 VALUE set = rb_hash_lookup2(hash, hash_key, Qundef);
854 if (set == Qundef) {
855 set = set_s_alloc(args[1]);
856 if (RTEST(args[2])) {
857 set_i_compare_by_identity(set);
858 }
859 rb_hash_aset(hash, hash_key, set);
860 }
861 set_i_add(set, key);
862
863 return ST_CONTINUE;
864}
865
866/*
867 * call-seq:
868 * classify { |o| ... } -> hash
869 * classify -> enumerator
870 *
871 * Classifies the set by the return value of the given block and
872 * returns a hash of {value => set of elements} pairs. The block is
873 * called once for each element of the set, passing the element as
874 * parameter.
875 *
876 * files = Set.new(Dir.glob("*.rb"))
877 * hash = files.classify { |f| File.mtime(f).year }
878 * hash #=> {2000 => Set["a.rb", "b.rb"],
879 * # 2001 => Set["c.rb", "d.rb", "e.rb"],
880 * # 2002 => Set["f.rb"]}
881 *
882 * Returns an enumerator if no block is given.
883 */
884static VALUE
885set_i_classify(VALUE set)
886{
887 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
888 VALUE args[3];
889 args[0] = rb_hash_new();
890 args[1] = rb_obj_class(set);
891 args[2] = RBOOL(RSET_COMPARE_BY_IDENTITY(set));
892 set_iter(set, set_classify_i, (st_data_t)args);
893 return args[0];
894}
895
896// Union-find with path compression
897static long
898set_divide_union_find_root(long *uf_parents, long index, long *tmp_array)
899{
900 long root = uf_parents[index];
901 long update_size = 0;
902 while (root != index) {
903 tmp_array[update_size++] = index;
904 index = root;
905 root = uf_parents[index];
906 }
907 for (long j = 0; j < update_size; j++) {
908 long idx = tmp_array[j];
909 uf_parents[idx] = root;
910 }
911 return root;
912}
913
914static void
915set_divide_union_find_merge(long *uf_parents, long i, long j, long *tmp_array)
916{
917 long root_i = set_divide_union_find_root(uf_parents, i, tmp_array);
918 long root_j = set_divide_union_find_root(uf_parents, j, tmp_array);
919 if (root_i != root_j) uf_parents[root_j] = root_i;
920}
921
922static VALUE
923set_divide_arity2(VALUE set)
924{
925 VALUE tmp, uf;
926 long size, *uf_parents, *tmp_array;
927 VALUE set_class = rb_obj_class(set);
928 VALUE items = set_i_to_a(set);
929 rb_ary_freeze(items);
930 size = RARRAY_LEN(items);
931 tmp_array = ALLOCV_N(long, tmp, size);
932 uf_parents = ALLOCV_N(long, uf, size);
933 for (long i = 0; i < size; i++) {
934 uf_parents[i] = i;
935 }
936 for (long i = 0; i < size - 1; i++) {
937 VALUE item1 = RARRAY_AREF(items, i);
938 for (long j = i + 1; j < size; j++) {
939 VALUE item2 = RARRAY_AREF(items, j);
940 if (RTEST(rb_yield_values(2, item1, item2)) &&
941 RTEST(rb_yield_values(2, item2, item1))) {
942 set_divide_union_find_merge(uf_parents, i, j, tmp_array);
943 }
944 }
945 }
946 VALUE final_set = set_s_create(0, 0, rb_cSet);
947 VALUE hash = rb_hash_new();
948 for (long i = 0; i < size; i++) {
949 VALUE v = RARRAY_AREF(items, i);
950 long root = set_divide_union_find_root(uf_parents, i, tmp_array);
951 VALUE subset = rb_hash_aref(hash, LONG2FIX(root));
952 if (subset == Qnil) {
953 subset = set_s_alloc(set_class);
954 if (RSET_COMPARE_BY_IDENTITY(set)) {
955 set_i_compare_by_identity(subset);
956 }
957 rb_hash_aset(hash, LONG2FIX(root), subset);
958 set_i_add(final_set, subset);
959 }
960 set_i_add(subset, v);
961 }
962 ALLOCV_END(tmp);
963 ALLOCV_END(uf);
964 return final_set;
965}
966
967static void set_merge_enum_into(VALUE set, VALUE arg);
968
969/*
970 * call-seq:
971 * divide { |o1, o2| ... } -> set
972 * divide { |o| ... } -> set
973 * divide -> enumerator
974 *
975 * Divides the set into a set of subsets according to the commonality
976 * defined by the given block.
977 *
978 * If the arity of the block is 2, elements o1 and o2 are in common
979 * if both block.call(o1, o2) and block.call(o2, o1) are true.
980 * Otherwise, elements o1 and o2 are in common if
981 * block.call(o1) == block.call(o2).
982 *
983 * numbers = Set[1, 3, 4, 6, 9, 10, 11]
984 * set = numbers.divide { |i,j| (i - j).abs == 1 }
985 * set #=> Set[Set[1],
986 * # Set[3, 4],
987 * # Set[6],
988 * # Set[9, 10, 11]]
989 *
990 * Returns an enumerator if no block is given.
991 */
992static VALUE
993set_i_divide(VALUE set)
994{
995 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
996
997 if (rb_block_arity() == 2) {
998 return set_divide_arity2(set);
999 }
1000
1001 VALUE values = rb_hash_values(set_i_classify(set));
1002 set = set_alloc_with_size(rb_cSet, RARRAY_LEN(values));
1003 set_merge_enum_into(set, values);
1004 return set;
1005}
1006
1007static int
1008set_clear_i(st_data_t key, st_data_t dummy)
1009{
1010 return ST_DELETE;
1011}
1012
1013/*
1014 * call-seq:
1015 * clear -> self
1016 *
1017 * Removes all elements and returns self.
1018 *
1019 * set = Set[1, 'c', :s] #=> Set[1, "c", :s]
1020 * set.clear #=> Set[]
1021 * set #=> Set[]
1022 */
1023static VALUE
1024set_i_clear(VALUE set)
1025{
1026 rb_check_frozen(set);
1027 if (RSET_SIZE(set) == 0) return set;
1028 if (set_iterating_p(set)) {
1029 set_iter(set, set_clear_i, 0);
1030 }
1031 else {
1032 set_table_clear(RSET_TABLE(set));
1033 set_compact_after_delete(set);
1034 }
1035 return set;
1036}
1037
1039 VALUE set;
1040 VALUE other_set;
1041 VALUE new_set;
1042 set_table *into;
1043 set_table *other;
1044};
1045
1046static int
1047set_intersection_i(st_data_t key, st_data_t tmp)
1048{
1049 struct set_intersection_data *data = MEMO_FOR(struct set_intersection_data, tmp);
1050 if (set_table_lookup(data->other, key)) {
1051 set_table_insert_wb(data->into, data->set, key, NULL);
1052 }
1053
1054 return ST_CONTINUE;
1055}
1056
1057static VALUE
1058set_intersection_block(RB_BLOCK_CALL_FUNC_ARGLIST(i, data))
1059{
1060 set_intersection_i((st_data_t)i, (st_data_t)data);
1061 return i;
1062}
1063
1064/*
1065 * call-seq:
1066 * set & enum -> new_set
1067 *
1068 * Returns a new set containing elements common to the set and the given
1069 * enumerable object.
1070 *
1071 * Set[1, 3, 5] & Set[3, 2, 1] #=> Set[3, 1]
1072 * Set['a', 'b', 'z'] & ['a', 'b', 'c'] #=> Set["a", "b"]
1073 */
1074static VALUE
1075set_i_intersection(VALUE set, VALUE other)
1076{
1077 VALUE new_set = set_s_alloc(rb_obj_class(set));
1078 if (RSET_COMPARE_BY_IDENTITY(set)) {
1079 set_i_compare_by_identity(new_set);
1080 }
1081 set_table *stable = RSET_TABLE(set);
1082 set_table *ntable = RSET_TABLE(new_set);
1083 VALUE data;
1084
1085 if (rb_obj_is_kind_of(other, rb_cSet)) {
1086 set_table *otable = RSET_TABLE(other);
1087 if (set_table_size(stable) >= set_table_size(otable)) {
1088 /* Swap so we iterate over the smaller set */
1089 otable = stable;
1090 set = other;
1091 }
1092
1093 *NEW_PARTIAL_MEMO_FOR(struct set_intersection_data, data, into) = (struct set_intersection_data) {
1094 .set = new_set,
1095 .other_set = other,
1096 .new_set = new_set,
1097 .into = ntable,
1098 .other = otable,
1099 };
1100 set_iter(set, set_intersection_i, (st_data_t)data);
1101 }
1102 else {
1103 *NEW_PARTIAL_MEMO_FOR(struct set_intersection_data, data, into) = (struct set_intersection_data) {
1104 .set = new_set,
1105 .other_set = other,
1106 .new_set = new_set,
1107 .into = ntable,
1108 .other = stable,
1109 };
1110 rb_block_call(other, enum_method_id(other), 0, 0, set_intersection_block, data);
1111 }
1112 RB_GC_GUARD(data);
1113
1114 return new_set;
1115}
1116
1117/*
1118 * call-seq:
1119 * include?(item) -> true or false
1120 *
1121 * Returns true if the set contains the given object:
1122 *
1123 * Set[1, 2, 3].include? 2 #=> true
1124 * Set[1, 2, 3].include? 4 #=> false
1125 *
1126 * Note that <code>include?</code> and <code>member?</code> do not test member
1127 * equality using <code>==</code> as do other Enumerables.
1128 *
1129 * This is aliased to #===, so it is usable in +case+ expressions:
1130 *
1131 * case :apple
1132 * when Set[:potato, :carrot]
1133 * "vegetable"
1134 * when Set[:apple, :banana]
1135 * "fruit"
1136 * end
1137 * # => "fruit"
1138 *
1139 * See also Enumerable#include?
1140 */
1141static VALUE
1142set_i_include(VALUE set, VALUE item)
1143{
1144 return RBOOL(RSET_IS_MEMBER(set, item));
1145}
1146
1148 VALUE set;
1149 set_table *into;
1150};
1151
1152static int
1153set_merge_i(st_data_t key, st_data_t data)
1154{
1155 struct set_merge_args *args = (struct set_merge_args *)data;
1156 set_table_insert_wb(args->into, args->set, key, NULL);
1157 return ST_CONTINUE;
1158}
1159
1160static VALUE
1161set_merge_block(RB_BLOCK_CALL_FUNC_ARGLIST(key, set))
1162{
1163 VALUE element = key;
1164 set_insert_wb(set, element, &element);
1165 return element;
1166}
1167
1168static void
1169set_merge_enum_into(VALUE set, VALUE arg)
1170{
1171 if (rb_obj_is_kind_of(arg, rb_cSet)) {
1172 struct set_merge_args args = {
1173 .set = set,
1174 .into = RSET_TABLE(set)
1175 };
1176 set_iter(arg, set_merge_i, (st_data_t)&args);
1177 }
1178 else if (RB_TYPE_P(arg, T_ARRAY)) {
1179 long i;
1180 set_table *into = RSET_TABLE(set);
1181 for (i=0; i<RARRAY_LEN(arg); i++) {
1182 set_table_insert_wb(into, set, RARRAY_AREF(arg, i), NULL);
1183 }
1184 RB_GC_GUARD(arg);
1185 }
1186 else {
1187 rb_block_call(arg, enum_method_id(arg), 0, 0, set_merge_block, (VALUE)set);
1188 }
1189}
1190
1191/*
1192 * call-seq:
1193 * merge(*enums, **nil) -> self
1194 *
1195 * Merges the elements of the given enumerable objects to the set and
1196 * returns self.
1197 */
1198static VALUE
1199set_i_merge(int argc, VALUE *argv, VALUE set)
1200{
1201 if (rb_keyword_given_p()) {
1202 rb_raise(rb_eArgError, "no keywords accepted");
1203 }
1204
1205 if (set_iterating_p(set)) {
1206 rb_raise(rb_eRuntimeError, "cannot add to set during iteration");
1207 }
1208
1209 rb_check_frozen(set);
1210
1211 int i;
1212
1213 for (i=0; i < argc; i++) {
1214 set_merge_enum_into(set, argv[i]);
1215 }
1216
1217 return set;
1218}
1219
1220static VALUE
1221set_reset_table_with_type(VALUE set, const struct st_hash_type *type)
1222{
1223 rb_check_frozen(set);
1224
1225 struct set_object *sobj;
1226 TypedData_Get_Struct(set, struct set_object, &set_data_type, sobj);
1227 set_table *old = &sobj->table;
1228
1229 size_t size = set_table_size(old);
1230 if (size > 0) {
1231 set_table *new = set_init_table_with_size(NULL, type, size);
1232 struct set_merge_args args = {
1233 .set = set,
1234 .into = new
1235 };
1236 set_iter(set, set_merge_i, (st_data_t)&args);
1237 set_free_embedded(sobj);
1238 memcpy(&sobj->table, new, sizeof(*new));
1239 free(new);
1240 }
1241 else {
1242 sobj->table.type = type;
1243 }
1244
1245 return set;
1246}
1247
1248/*
1249 * call-seq:
1250 * compare_by_identity -> self
1251 *
1252 * Makes the set compare its elements by their identity and returns self.
1253 */
1254static VALUE
1255set_i_compare_by_identity(VALUE set)
1256{
1257 if (RSET_COMPARE_BY_IDENTITY(set)) return set;
1258
1259 if (set_iterating_p(set)) {
1260 rb_raise(rb_eRuntimeError, "compare_by_identity during iteration");
1261 }
1262
1263 return set_reset_table_with_type(set, &identhash);
1264}
1265
1266/*
1267 * call-seq:
1268 * compare_by_identity? -> true or false
1269 *
1270 * Returns true if the set will compare its elements by their
1271 * identity. Also see Set#compare_by_identity.
1272 */
1273static VALUE
1274set_i_compare_by_identity_p(VALUE set)
1275{
1276 return RBOOL(RSET_COMPARE_BY_IDENTITY(set));
1277}
1278
1279/*
1280 * call-seq:
1281 * size -> integer
1282 *
1283 * Returns the number of elements.
1284 */
1285static VALUE
1286set_i_size(VALUE set)
1287{
1288 return RSET_SIZE_NUM(set);
1289}
1290
1291/*
1292 * call-seq:
1293 * empty? -> true or false
1294 *
1295 * Returns true if the set contains no elements.
1296 */
1297static VALUE
1298set_i_empty(VALUE set)
1299{
1300 return RBOOL(RSET_EMPTY(set));
1301}
1302
1303static int
1304set_xor_i(st_data_t key, st_data_t data)
1305{
1306 VALUE element = (VALUE)key;
1307 VALUE set = (VALUE)data;
1308 set_table *table = RSET_TABLE(set);
1309 if (set_table_insert_wb(table, set, element, &element)) {
1310 set_table_delete(table, &element);
1311 }
1312 return ST_CONTINUE;
1313}
1314
1315/*
1316 * call-seq:
1317 * set ^ enum -> new_set
1318 *
1319 * Returns a new set containing elements exclusive between the set and the
1320 * given enumerable object. <tt>(set ^ enum)</tt> is equivalent to
1321 * <tt>((set | enum) - (set & enum))</tt>.
1322 *
1323 * Set[1, 2] ^ Set[2, 3] #=> Set[3, 1]
1324 * Set[1, 'b', 'c'] ^ ['b', 'd'] #=> Set["d", 1, "c"]
1325 */
1326static VALUE
1327set_i_xor(VALUE set, VALUE other)
1328{
1329 VALUE new_set = rb_obj_dup(set);
1330
1331 if (rb_obj_is_kind_of(other, rb_cSet)) {
1332 set_iter(other, set_xor_i, (st_data_t)new_set);
1333 }
1334 else {
1335 VALUE tmp = set_s_alloc(rb_obj_class(new_set));
1336 if (RSET_COMPARE_BY_IDENTITY(new_set)) {
1337 set_i_compare_by_identity(tmp);
1338 }
1339 set_merge_enum_into(tmp, other);
1340 set_iter(tmp, set_xor_i, (st_data_t)new_set);
1341 }
1342 set_compact_after_delete(set);
1343
1344 return new_set;
1345}
1346
1347/*
1348 * call-seq:
1349 * set | enum -> new_set
1350 *
1351 * Returns a new set built by merging the set and the elements of the
1352 * given enumerable object.
1353 *
1354 * Set[1, 2, 3] | Set[2, 4, 5] #=> Set[1, 2, 3, 4, 5]
1355 * Set[1, 5, 'z'] | (1..6) #=> Set[1, 5, "z", 2, 3, 4, 6]
1356 */
1357static VALUE
1358set_i_union(VALUE set, VALUE other)
1359{
1360 set = rb_obj_dup(set);
1361 set_merge_enum_into(set, other);
1362 return set;
1363}
1364
1365static int
1366set_remove_i(st_data_t key, st_data_t from)
1367{
1368 set_table_delete((struct set_table *)from, (st_data_t *)&key);
1369 return ST_CONTINUE;
1370}
1371
1372static VALUE
1373set_remove_block(RB_BLOCK_CALL_FUNC_ARGLIST(key, set))
1374{
1375 rb_check_frozen(set);
1376 set_table_delete(RSET_TABLE(set), (st_data_t *)&key);
1377 return key;
1378}
1379
1380static void
1381set_remove_enum_from(VALUE set, VALUE arg)
1382{
1383 if (rb_obj_is_kind_of(arg, rb_cSet)) {
1384 set_iter(arg, set_remove_i, (st_data_t)RSET_TABLE(set));
1385 }
1386 else {
1387 rb_block_call(arg, enum_method_id(arg), 0, 0, set_remove_block, (VALUE)set);
1388 }
1389 set_compact_after_delete(set);
1390}
1391
1392/*
1393 * call-seq:
1394 * subtract(enum) -> self
1395 *
1396 * Deletes every element that appears in the given enumerable object
1397 * and returns self.
1398 */
1399static VALUE
1400set_i_subtract(VALUE set, VALUE other)
1401{
1402 rb_check_frozen(set);
1403 set_remove_enum_from(set, other);
1404 return set;
1405}
1406
1407/*
1408 * call-seq:
1409 * set - enum -> new_set
1410 *
1411 * Returns a new set built by duplicating the set, removing every
1412 * element that appears in the given enumerable object.
1413 *
1414 * Set[1, 3, 5] - Set[1, 5] #=> Set[3]
1415 * Set['a', 'b', 'z'] - ['a', 'c'] #=> Set["b", "z"]
1416 */
1417static VALUE
1418set_i_difference(VALUE set, VALUE other)
1419{
1420 return set_i_subtract(rb_obj_dup(set), other);
1421}
1422
1423static int
1424set_each_i(st_data_t key, st_data_t dummy)
1425{
1426 rb_yield(key);
1427 return ST_CONTINUE;
1428}
1429
1430/*
1431 * call-seq:
1432 * each { |o| ... } -> self
1433 * each -> enumerator
1434 *
1435 * Calls the given block once for each element in the set, passing
1436 * the element as parameter. Returns an enumerator if no block is
1437 * given.
1438 */
1439static VALUE
1440set_i_each(VALUE set)
1441{
1442 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1443 set_iter(set, set_each_i, 0);
1444 return set;
1445}
1446
1447static int
1448set_collect_i(st_data_t key, st_data_t data)
1449{
1450 set_insert_wb((VALUE)data, rb_yield((VALUE)key), NULL);
1451 return ST_CONTINUE;
1452}
1453
1454/*
1455 * call-seq:
1456 * collect! { |o| ... } -> self
1457 * collect! -> enumerator
1458 *
1459 * Replaces the elements with ones returned by +collect+.
1460 * Returns an enumerator if no block is given.
1461 */
1462static VALUE
1463set_i_collect(VALUE set)
1464{
1465 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1466 rb_check_frozen(set);
1467
1468 VALUE new_set = set_s_alloc(rb_obj_class(set));
1469 if (RSET_COMPARE_BY_IDENTITY(set)) {
1470 set_i_compare_by_identity(new_set);
1471 }
1472 set_iter(set, set_collect_i, (st_data_t)new_set);
1473 set_i_initialize_copy(set, new_set);
1474
1475 return set;
1476}
1477
1478static int
1479set_keep_if_i(st_data_t key, st_data_t into)
1480{
1481 if (!RTEST(rb_yield((VALUE)key))) {
1482 set_table_delete((set_table *)into, &key);
1483 }
1484 return ST_CONTINUE;
1485}
1486
1487/*
1488 * call-seq:
1489 * keep_if { |o| ... } -> self
1490 * keep_if -> enumerator
1491 *
1492 * Deletes every element of the set for which block evaluates to false, and
1493 * returns self. Returns an enumerator if no block is given.
1494 */
1495static VALUE
1496set_i_keep_if(VALUE set)
1497{
1498 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1499 rb_check_frozen(set);
1500
1501 set_iter(set, set_keep_if_i, (st_data_t)RSET_TABLE(set));
1502 set_compact_after_delete(set);
1503
1504 return set;
1505}
1506
1507/*
1508 * call-seq:
1509 * select! { |o| ... } -> self
1510 * select! -> enumerator
1511 *
1512 * Equivalent to Set#keep_if, but returns nil if no changes were made.
1513 * Returns an enumerator if no block is given.
1514 */
1515static VALUE
1516set_i_select(VALUE set)
1517{
1518 RETURN_SIZED_ENUMERATOR(set, 0, 0, set_enum_size);
1519 rb_check_frozen(set);
1520
1521 set_table *table = RSET_TABLE(set);
1522 size_t n = set_table_size(table);
1523 set_iter(set, set_keep_if_i, (st_data_t)table);
1524 set_compact_after_delete(set);
1525
1526 return (n == set_table_size(table)) ? Qnil : set;
1527}
1528
1529/*
1530 * call-seq:
1531 * replace(enum) -> self
1532 *
1533 * Replaces the contents of the set with the contents of the given
1534 * enumerable object and returns self.
1535 *
1536 * set = Set[1, 'c', :s] #=> Set[1, "c", :s]
1537 * set.replace([1, 2]) #=> Set[1, 2]
1538 * set #=> Set[1, 2]
1539 */
1540static VALUE
1541set_i_replace(VALUE set, VALUE other)
1542{
1543 rb_check_frozen(set);
1544
1545 if (rb_obj_is_kind_of(other, rb_cSet)) {
1546 set_i_initialize_copy(set, other);
1547 }
1548 else {
1549 if (set_iterating_p(set)) {
1550 rb_raise(rb_eRuntimeError, "cannot replace set during iteration");
1551 }
1552
1553 // make sure enum is enumerable before calling clear
1554 enum_method_id(other);
1555
1556 set_table_clear(RSET_TABLE(set));
1557 set_merge_enum_into(set, other);
1558 }
1559 set_compact_after_delete(set);
1560
1561 return set;
1562}
1563
1564/*
1565 * call-seq:
1566 * reset -> self
1567 *
1568 * Resets the internal state after modification to existing elements
1569 * and returns self. Elements will be reindexed and deduplicated.
1570 */
1571static VALUE
1572set_i_reset(VALUE set)
1573{
1574 if (set_iterating_p(set)) {
1575 rb_raise(rb_eRuntimeError, "reset during iteration");
1576 }
1577
1578 return set_reset_table_with_type(set, RSET_TABLE(set)->type);
1579}
1580
1581static void set_flatten_merge(VALUE set, VALUE from, VALUE seen);
1582
1583static int
1584set_flatten_merge_i(st_data_t item, st_data_t arg)
1585{
1586 VALUE *args = (VALUE *)arg;
1587 VALUE set = args[0];
1588 if (rb_obj_is_kind_of(item, rb_cSet)) {
1589 VALUE e_id = rb_obj_id(item);
1590 VALUE hash = args[2];
1591 switch(rb_hash_aref(hash, e_id)) {
1592 case Qfalse:
1593 return ST_CONTINUE;
1594 case Qtrue:
1595 rb_raise(rb_eArgError, "tried to flatten recursive Set");
1596 default:
1597 break;
1598 }
1599
1600 rb_hash_aset(hash, e_id, Qtrue);
1601 set_flatten_merge(set, item, hash);
1602 rb_hash_aset(hash, e_id, Qfalse);
1603 }
1604 else {
1605 set_i_add(set, item);
1606 }
1607 return ST_CONTINUE;
1608}
1609
1610static void
1611set_flatten_merge(VALUE set, VALUE from, VALUE hash)
1612{
1613 VALUE args[3] = {set, from, hash};
1614 set_iter(from, set_flatten_merge_i, (st_data_t)args);
1615}
1616
1617/*
1618 * call-seq:
1619 * flatten -> set
1620 *
1621 * Returns a new set that is a copy of the set, flattening each
1622 * containing set recursively.
1623 */
1624static VALUE
1625set_i_flatten(VALUE set)
1626{
1627 VALUE new_set = set_s_alloc(rb_obj_class(set));
1628 if (RSET_COMPARE_BY_IDENTITY(set)) {
1629 set_i_compare_by_identity(new_set);
1630 }
1631 set_flatten_merge(new_set, set, rb_hash_new());
1632 return new_set;
1633}
1634
1635static int
1636set_contains_set_i(st_data_t item, st_data_t arg)
1637{
1638 if (rb_obj_is_kind_of(item, rb_cSet)) {
1639 *(bool *)arg = true;
1640 return ST_STOP;
1641 }
1642 return ST_CONTINUE;
1643}
1644
1645/*
1646 * call-seq:
1647 * flatten! -> self
1648 *
1649 * Equivalent to Set#flatten, but replaces the receiver with the
1650 * result in place. Returns nil if no modifications were made.
1651 */
1652static VALUE
1653set_i_flatten_bang(VALUE set)
1654{
1655 bool contains_set = false;
1656 set_iter(set, set_contains_set_i, (st_data_t)&contains_set);
1657 if (!contains_set) return Qnil;
1658 rb_check_frozen(set);
1659 return set_i_replace(set, set_i_flatten(set));
1660}
1661
1663 set_table *table;
1664 VALUE result;
1665};
1666
1667static int
1668set_le_i(st_data_t key, st_data_t arg)
1669{
1670 struct set_subset_data *data = (struct set_subset_data *)arg;
1671 if (set_table_lookup(data->table, key)) return ST_CONTINUE;
1672 data->result = Qfalse;
1673 return ST_STOP;
1674}
1675
1676static VALUE
1677set_le(VALUE set, VALUE other)
1678{
1679 struct set_subset_data data = {
1680 .table = RSET_TABLE(other),
1681 .result = Qtrue
1682 };
1683 set_iter(set, set_le_i, (st_data_t)&data);
1684 return data.result;
1685}
1686
1687/*
1688 * call-seq:
1689 * proper_subset?(set) -> true or false
1690 *
1691 * Returns true if the set is a proper subset of the given set.
1692 */
1693static VALUE
1694set_i_proper_subset(VALUE set, VALUE other)
1695{
1696 check_set(other);
1697 if (RSET_SIZE(set) >= RSET_SIZE(other)) return Qfalse;
1698 return set_le(set, other);
1699}
1700
1701/*
1702 * call-seq:
1703 * subset?(set) -> true or false
1704 *
1705 * Returns true if the set is a subset of the given set.
1706 */
1707static VALUE
1708set_i_subset(VALUE set, VALUE other)
1709{
1710 check_set(other);
1711 if (RSET_SIZE(set) > RSET_SIZE(other)) return Qfalse;
1712 return set_le(set, other);
1713}
1714
1715/*
1716 * call-seq:
1717 * proper_superset?(set) -> true or false
1718 *
1719 * Returns true if the set is a proper superset of the given set.
1720 */
1721static VALUE
1722set_i_proper_superset(VALUE set, VALUE other)
1723{
1724 check_set(other);
1725 if (RSET_SIZE(set) <= RSET_SIZE(other)) return Qfalse;
1726 return set_le(other, set);
1727}
1728
1729/*
1730 * call-seq:
1731 * superset?(set) -> true or false
1732 *
1733 * Returns true if the set is a superset of the given set.
1734 */
1735static VALUE
1736set_i_superset(VALUE set, VALUE other)
1737{
1738 check_set(other);
1739 if (RSET_SIZE(set) < RSET_SIZE(other)) return Qfalse;
1740 return set_le(other, set);
1741}
1742
1743static int
1744set_intersect_i(st_data_t key, st_data_t arg)
1745{
1746 VALUE *args = (VALUE *)arg;
1747 if (set_table_lookup((set_table *)args[0], key)) {
1748 args[1] = Qtrue;
1749 return ST_STOP;
1750 }
1751 return ST_CONTINUE;
1752}
1753
1754/*
1755 * call-seq:
1756 * intersect?(set) -> true or false
1757 *
1758 * Returns true if the set and the given enumerable have at least one
1759 * element in common.
1760 *
1761 * Set[1, 2, 3].intersect? Set[4, 5] #=> false
1762 * Set[1, 2, 3].intersect? Set[3, 4] #=> true
1763 * Set[1, 2, 3].intersect? 4..5 #=> false
1764 * Set[1, 2, 3].intersect? [3, 4] #=> true
1765 */
1766static VALUE
1767set_i_intersect(VALUE set, VALUE other)
1768{
1769 if (rb_obj_is_kind_of(other, rb_cSet)) {
1770 size_t set_size = RSET_SIZE(set);
1771 size_t other_size = RSET_SIZE(other);
1772 VALUE args[2];
1773 args[1] = Qfalse;
1774 VALUE iter_arg;
1775
1776 if (set_size < other_size) {
1777 iter_arg = set;
1778 args[0] = (VALUE)RSET_TABLE(other);
1779 }
1780 else {
1781 iter_arg = other;
1782 args[0] = (VALUE)RSET_TABLE(set);
1783 }
1784 set_iter(iter_arg, set_intersect_i, (st_data_t)args);
1785 return args[1];
1786 }
1787 else if (rb_obj_is_kind_of(other, rb_mEnumerable)) {
1788 return rb_funcall(other, id_any_p, 1, set);
1789 }
1790 else {
1791 rb_raise(rb_eArgError, "value must be enumerable");
1792 }
1793}
1794
1795/*
1796 * call-seq:
1797 * disjoint?(set) -> true or false
1798 *
1799 * Returns true if the set and the given enumerable have no
1800 * element in common. This method is the opposite of +intersect?+.
1801 *
1802 * Set[1, 2, 3].disjoint? Set[3, 4] #=> false
1803 * Set[1, 2, 3].disjoint? Set[4, 5] #=> true
1804 * Set[1, 2, 3].disjoint? [3, 4] #=> false
1805 * Set[1, 2, 3].disjoint? 4..5 #=> true
1806 */
1807static VALUE
1808set_i_disjoint(VALUE set, VALUE other)
1809{
1810 return RBOOL(!RTEST(set_i_intersect(set, other)));
1811}
1812
1813/*
1814 * call-seq:
1815 * set <=> other -> -1, 0, 1, or nil
1816 *
1817 * Returns 0 if the set are equal, -1 / 1 if the set is a
1818 * proper subset / superset of the given set, or nil if
1819 * they both have unique elements.
1820 */
1821static VALUE
1822set_i_compare(VALUE set, VALUE other)
1823{
1824 if (rb_obj_is_kind_of(other, rb_cSet)) {
1825 size_t set_size = RSET_SIZE(set);
1826 size_t other_size = RSET_SIZE(other);
1827
1828 if (set_size < other_size) {
1829 if (set_le(set, other) == Qtrue) {
1830 return INT2NUM(-1);
1831 }
1832 }
1833 else if (set_size > other_size) {
1834 if (set_le(other, set) == Qtrue) {
1835 return INT2NUM(1);
1836 }
1837 }
1838 else if (set_le(set, other) == Qtrue) {
1839 return INT2NUM(0);
1840 }
1841 }
1842
1843 return Qnil;
1844}
1845
1847 VALUE result;
1848 VALUE set;
1849};
1850
1851static int
1852set_eql_i(st_data_t item, st_data_t arg)
1853{
1854 struct set_equal_data *data = (struct set_equal_data *)arg;
1855
1856 if (!set_table_lookup(RSET_TABLE(data->set), item)) {
1857 data->result = Qfalse;
1858 return ST_STOP;
1859 }
1860 return ST_CONTINUE;
1861}
1862
1863static VALUE
1864set_recursive_eql(VALUE set, VALUE dt, int recur)
1865{
1866 if (recur) return Qtrue;
1867 struct set_equal_data *data = (struct set_equal_data*)dt;
1868 data->result = Qtrue;
1869 set_iter(set, set_eql_i, dt);
1870 return data->result;
1871}
1872
1873/*
1874 * call-seq:
1875 * set == other -> true or false
1876 *
1877 * Returns true if two sets are equal.
1878 */
1879static VALUE
1880set_i_eq(VALUE set, VALUE other)
1881{
1882 if (!rb_obj_is_kind_of(other, rb_cSet)) return Qfalse;
1883 if (set == other) return Qtrue;
1884
1885 set_table *stable = RSET_TABLE(set);
1886 set_table *otable = RSET_TABLE(other);
1887 size_t ssize = set_table_size(stable);
1888 size_t osize = set_table_size(otable);
1889
1890 if (ssize != osize) return Qfalse;
1891 if (ssize == 0 && osize == 0) return Qtrue;
1892 if (stable->type != otable->type) return Qfalse;
1893
1894 struct set_equal_data data;
1895 data.set = other;
1896 return rb_exec_recursive_paired(set_recursive_eql, set, other, (VALUE)&data);
1897}
1898
1899static int
1900set_hash_i(st_data_t item, st_data_t(arg))
1901{
1902 st_index_t *hval = (st_index_t *)arg;
1903 st_index_t ival = rb_hash(item);
1904 *hval ^= rb_st_hash(&ival, sizeof(st_index_t), 0);
1905 return ST_CONTINUE;
1906}
1907
1908/*
1909 * call-seq:
1910 * hash -> integer
1911 *
1912 * Returns hash code for set.
1913 */
1914static VALUE
1915set_i_hash(VALUE set)
1916{
1917 st_index_t size = RSET_SIZE(set);
1918 st_index_t hval = rb_st_hash_start(size);
1919 hval = rb_hash_uint(hval, (st_index_t)set_i_hash);
1920 if (size) {
1921 set_iter(set, set_hash_i, (VALUE)&hval);
1922 }
1923 hval = rb_st_hash_end(hval);
1924 return ST2FIX(hval);
1925}
1926
1927/* :nodoc: */
1928static int
1929set_to_hash_i(st_data_t key, st_data_t arg)
1930{
1931 rb_hash_aset((VALUE)arg, (VALUE)key, Qtrue);
1932 return ST_CONTINUE;
1933}
1934
1935static VALUE
1936set_i_to_h(VALUE set)
1937{
1938 st_index_t size = RSET_SIZE(set);
1939 VALUE hash;
1940 if (RSET_COMPARE_BY_IDENTITY(set)) {
1941 hash = rb_ident_hash_new_with_size(size);
1942 }
1943 else {
1944 hash = rb_hash_new_with_size(size);
1945 }
1946 rb_hash_set_default(hash, Qfalse);
1947
1948 if (size == 0) return hash;
1949
1950 set_iter(set, set_to_hash_i, (st_data_t)hash);
1951 return hash;
1952}
1953
1954static VALUE
1955compat_dumper(VALUE set)
1956{
1957 VALUE dumper = rb_class_new_instance(0, 0, rb_cObject);
1958 rb_ivar_set(dumper, id_i_hash, set_i_to_h(set));
1959 return dumper;
1960}
1961
1962static int
1963set_i_from_hash_i(st_data_t key, st_data_t val, st_data_t set)
1964{
1965 if ((VALUE)val != Qtrue) {
1966 rb_raise(rb_eRuntimeError, "expect true as Set value: %"PRIsVALUE, rb_obj_class((VALUE)val));
1967 }
1968 set_i_add((VALUE)set, (VALUE)key);
1969 return ST_CONTINUE;
1970}
1971
1972static VALUE
1973set_i_from_hash(VALUE set, VALUE hash)
1974{
1975 Check_Type(hash, T_HASH);
1976 if (rb_hash_compare_by_id_p(hash)) set_i_compare_by_identity(set);
1977 rb_hash_stlike_foreach(hash, set_i_from_hash_i, (st_data_t)set);
1978 return set;
1979}
1980
1981static VALUE
1982compat_loader(VALUE self, VALUE a)
1983{
1984 return set_i_from_hash(self, rb_ivar_get(a, id_i_hash));
1985}
1986
1987/* C-API functions */
1988
1989void
1990rb_set_foreach(VALUE set, int (*func)(VALUE element, VALUE arg), VALUE arg)
1991{
1992 set_iter(set, func, arg);
1993}
1994
1995VALUE
1997{
1998 return set_alloc_with_size(rb_cSet, 0);
1999}
2000
2001VALUE
2003{
2004 return set_alloc_with_size(rb_cSet, (st_index_t)capa);
2005}
2006
2007bool
2009{
2010 return RSET_IS_MEMBER(set, element);
2011}
2012
2013bool
2015{
2016 return set_i_add_p(set, element) != Qnil;
2017}
2018
2019VALUE
2021{
2022 return set_i_clear(set);
2023}
2024
2025bool
2027{
2028 return set_i_delete_p(set, element) != Qnil;
2029}
2030
2031size_t
2033{
2034 return RSET_SIZE(set);
2035}
2036
2037/*
2038 * Document-class: Set
2039 *
2040 * The Set class implements a collection of unordered values with no
2041 * duplicates. It is a hybrid of Array's intuitive inter-operation
2042 * facilities and Hash's fast lookup.
2043 *
2044 * Set is easy to use with Enumerable objects (implementing #each).
2045 * Most of the initializer methods and binary operators accept generic
2046 * Enumerable objects besides sets and arrays. An Enumerable object
2047 * can be converted to Set using the +to_set+ method.
2048 *
2049 * Set uses a data structure similar to Hash for storage, except that
2050 * it only has keys and no values.
2051 *
2052 * * Equality of elements is determined according to Object#eql? and
2053 * Object#hash. Use Set#compare_by_identity to make a set compare
2054 * its elements by their identity.
2055 * * Set assumes that the identity of each element does not change
2056 * while it is stored. Modifying an element of a set will render the
2057 * set to an unreliable state.
2058 * * When a string is to be stored, a frozen copy of the string is
2059 * stored instead unless the original string is already frozen.
2060 *
2061 * == Comparison
2062 *
2063 * The comparison operators <tt><</tt>, <tt>></tt>, <tt><=</tt>, and
2064 * <tt>>=</tt> are implemented as shorthand for the
2065 * {proper_,}{subset?,superset?} methods. The <tt><=></tt>
2066 * operator reflects this order, or returns +nil+ for sets that both
2067 * have distinct elements (<tt>{x, y}</tt> vs. <tt>{x, z}</tt> for example).
2068 *
2069 * == Example
2070 *
2071 * s1 = Set[1, 2] #=> Set[1, 2]
2072 * s2 = [1, 2].to_set #=> Set[1, 2]
2073 * s1 == s2 #=> true
2074 * s1.add("foo") #=> Set[1, 2, "foo"]
2075 * s1.merge([2, 6]) #=> Set[1, 2, "foo", 6]
2076 * s1.subset?(s2) #=> false
2077 * s2.subset?(s1) #=> true
2078 *
2079 * == Contact
2080 *
2081 * - Akinori MUSHA <knu@iDaemons.org> (current maintainer)
2082 *
2083 * == Inheriting from \Set
2084 *
2085 * Before Ruby 4.0 (released December 2025), \Set had a different, less
2086 * efficient implementation. It was reimplemented in C, and the behavior
2087 * of some of the core methods were adjusted.
2088 *
2089 * To keep backward compatibility, when a class is inherited from \Set,
2090 * additional module +Set::SubclassCompatible+ is included, which makes
2091 * the inherited class behavior, as well as internal method names,
2092 * closer to what it was before Ruby 4.0.
2093 *
2094 * It can be easily seen, for example, in the #inspect method behavior:
2095 *
2096 * p Set[1, 2, 3]
2097 * # prints "Set[1, 2, 3]"
2098 *
2099 * class MySet < Set
2100 * end
2101 * p MySet[1, 2, 3]
2102 * # prints "#<MySet: {1, 2, 3}>", like it was in Ruby 3.4
2103 *
2104 * For new code, if backward compatibility is not necessary,
2105 * it is recommended to instead inherit from +Set::CoreSet+, which
2106 * avoids including the "compatibility" layer:
2107 *
2108 * class MyCoreSet < Set::CoreSet
2109 * end
2110 * p MyCoreSet[1, 2, 3]
2111 * # prints "MyCoreSet[1, 2, 3]"
2112 *
2113 * == Set's methods
2114 *
2115 * First, what's elsewhere. \Class \Set:
2116 *
2117 * - Inherits from {class Object}[rdoc-ref:Object@What-27s+Here].
2118 * - Includes {module Enumerable}[rdoc-ref:Enumerable@What-27s+Here],
2119 * which provides dozens of additional methods.
2120 *
2121 * In particular, class \Set does not have many methods of its own
2122 * for fetching or for iterating.
2123 * Instead, it relies on those in \Enumerable.
2124 *
2125 * Here, class \Set provides methods that are useful for:
2126 *
2127 * - {Creating a Set}[rdoc-ref:Set@Methods+for+Creating+a+Set]
2128 * - {Set Operations}[rdoc-ref:Set@Methods+for+Set+Operations]
2129 * - {Comparing}[rdoc-ref:Set@Methods+for+Comparing]
2130 * - {Querying}[rdoc-ref:Set@Methods+for+Querying]
2131 * - {Assigning}[rdoc-ref:Set@Methods+for+Assigning]
2132 * - {Deleting}[rdoc-ref:Set@Methods+for+Deleting]
2133 * - {Converting}[rdoc-ref:Set@Methods+for+Converting]
2134 * - {Iterating}[rdoc-ref:Set@Methods+for+Iterating]
2135 * - {And more....}[rdoc-ref:Set@Other+Methods]
2136 *
2137 * === Methods for Creating a \Set
2138 *
2139 * - ::[]:
2140 * Returns a new set containing the given objects.
2141 * - ::new:
2142 * Returns a new set containing either the given objects
2143 * (if no block given) or the return values from the called block
2144 * (if a block given).
2145 *
2146 * === Methods for \Set Operations
2147 *
2148 * - #| (aliased as #union and #+):
2149 * Returns a new set containing all elements from +self+
2150 * and all elements from a given enumerable (no duplicates).
2151 * - #& (aliased as #intersection):
2152 * Returns a new set containing all elements common to +self+
2153 * and a given enumerable.
2154 * - #- (aliased as #difference):
2155 * Returns a copy of +self+ with all elements
2156 * in a given enumerable removed.
2157 * - #^: Returns a new set containing all elements from +self+
2158 * and a given enumerable except those common to both.
2159 *
2160 * === Methods for Comparing
2161 *
2162 * - #<=>: Returns -1, 0, or 1 as +self+ is less than, equal to,
2163 * or greater than a given object.
2164 * - #==: Returns whether +self+ and a given enumerable are equal,
2165 * as determined by Object#eql?.
2166 * - #compare_by_identity?:
2167 * Returns whether the set considers only identity
2168 * when comparing elements.
2169 *
2170 * === Methods for Querying
2171 *
2172 * - #length (aliased as #size):
2173 * Returns the count of elements.
2174 * - #empty?:
2175 * Returns whether the set has no elements.
2176 * - #include? (aliased as #member? and #===):
2177 * Returns whether a given object is an element in the set.
2178 * - #subset? (aliased as #<=):
2179 * Returns whether a given object is a subset of the set.
2180 * - #proper_subset? (aliased as #<):
2181 * Returns whether a given enumerable is a proper subset of the set.
2182 * - #superset? (aliased as #>=):
2183 * Returns whether a given enumerable is a superset of the set.
2184 * - #proper_superset? (aliased as #>):
2185 * Returns whether a given enumerable is a proper superset of the set.
2186 * - #disjoint?:
2187 * Returns +true+ if the set and a given enumerable
2188 * have no common elements, +false+ otherwise.
2189 * - #intersect?:
2190 * Returns +true+ if the set and a given enumerable:
2191 * have any common elements, +false+ otherwise.
2192 * - #compare_by_identity?:
2193 * Returns whether the set considers only identity
2194 * when comparing elements.
2195 *
2196 * === Methods for Assigning
2197 *
2198 * - #add (aliased as #<<):
2199 * Adds a given object to the set; returns +self+.
2200 * - #add?:
2201 * If the given object is not an element in the set,
2202 * adds it and returns +self+; otherwise, returns +nil+.
2203 * - #merge:
2204 * Merges the elements of each given enumerable object to the set; returns +self+.
2205 * - #replace:
2206 * Replaces the contents of the set with the contents
2207 * of a given enumerable.
2208 *
2209 * === Methods for Deleting
2210 *
2211 * - #clear:
2212 * Removes all elements in the set; returns +self+.
2213 * - #delete:
2214 * Removes a given object from the set; returns +self+.
2215 * - #delete?:
2216 * If the given object is an element in the set,
2217 * removes it and returns +self+; otherwise, returns +nil+.
2218 * - #subtract:
2219 * Removes each given object from the set; returns +self+.
2220 * - #delete_if - Removes elements specified by a given block.
2221 * - #select! (aliased as #filter!):
2222 * Removes elements not specified by a given block.
2223 * - #keep_if:
2224 * Removes elements not specified by a given block.
2225 * - #reject!
2226 * Removes elements specified by a given block.
2227 *
2228 * === Methods for Converting
2229 *
2230 * - #classify:
2231 * Returns a hash that classifies the elements,
2232 * as determined by the given block.
2233 * - #collect! (aliased as #map!):
2234 * Replaces each element with a block return-value.
2235 * - #divide:
2236 * Returns a hash that classifies the elements,
2237 * as determined by the given block;
2238 * differs from #classify in that the block may accept
2239 * either one or two arguments.
2240 * - #flatten:
2241 * Returns a new set that is a recursive flattening of +self+.
2242 * - #flatten!:
2243 * Replaces each nested set in +self+ with the elements from that set.
2244 * - #inspect (aliased as #to_s):
2245 * Returns a string displaying the elements.
2246 * - #join:
2247 * Returns a string containing all elements, converted to strings
2248 * as needed, and joined by the given record separator.
2249 * - #to_a:
2250 * Returns an array containing all set elements.
2251 * - #to_set:
2252 * Returns +self+ if given no arguments and no block;
2253 * with a block given, returns a new set consisting of block
2254 * return values.
2255 *
2256 * === Methods for Iterating
2257 *
2258 * - #each:
2259 * Calls the block with each successive element; returns +self+.
2260 *
2261 * === Other Methods
2262 *
2263 * - #reset:
2264 * Resets the internal state; useful if an object
2265 * has been modified while an element in the set.
2266 *
2267 */
2268void
2269Init_Set(void)
2270{
2271 rb_cSet = rb_define_class("Set", rb_cObject);
2273
2274 id_each_entry = rb_intern_const("each_entry");
2275 id_any_p = rb_intern_const("any?");
2276 id_new = rb_intern_const("new");
2277 id_i_hash = rb_intern_const("@hash");
2278 id_subclass_compatible = rb_intern_const("SubclassCompatible");
2279 id_class_methods = rb_intern_const("ClassMethods");
2280 id_set_iter_lev = rb_make_internal_id();
2281
2282 rb_define_alloc_func(rb_cSet, set_s_alloc);
2283 rb_define_singleton_method(rb_cSet, "[]", set_s_create, -1);
2284
2285 rb_define_method(rb_cSet, "initialize", set_i_initialize, -1);
2286 rb_define_method(rb_cSet, "initialize_copy", set_i_initialize_copy, 1);
2287
2288 rb_define_method(rb_cSet, "&", set_i_intersection, 1);
2289 rb_define_alias(rb_cSet, "intersection", "&");
2290 rb_define_method(rb_cSet, "-", set_i_difference, 1);
2291 rb_define_alias(rb_cSet, "difference", "-");
2292 rb_define_method(rb_cSet, "^", set_i_xor, 1);
2293 rb_define_method(rb_cSet, "|", set_i_union, 1);
2294 rb_define_alias(rb_cSet, "+", "|");
2295 rb_define_alias(rb_cSet, "union", "|");
2296 rb_define_method(rb_cSet, "<=>", set_i_compare, 1);
2297 rb_define_method(rb_cSet, "==", set_i_eq, 1);
2298 rb_define_alias(rb_cSet, "eql?", "==");
2299 rb_define_method(rb_cSet, "add", set_i_add, 1);
2300 rb_define_alias(rb_cSet, "<<", "add");
2301 rb_define_method(rb_cSet, "add?", set_i_add_p, 1);
2302 rb_define_method(rb_cSet, "classify", set_i_classify, 0);
2303 rb_define_method(rb_cSet, "clear", set_i_clear, 0);
2304 rb_define_method(rb_cSet, "collect!", set_i_collect, 0);
2305 rb_define_alias(rb_cSet, "map!", "collect!");
2306 rb_define_method(rb_cSet, "compare_by_identity", set_i_compare_by_identity, 0);
2307 rb_define_method(rb_cSet, "compare_by_identity?", set_i_compare_by_identity_p, 0);
2308 rb_define_method(rb_cSet, "delete", set_i_delete, 1);
2309 rb_define_method(rb_cSet, "delete?", set_i_delete_p, 1);
2310 rb_define_method(rb_cSet, "delete_if", set_i_delete_if, 0);
2311 rb_define_method(rb_cSet, "disjoint?", set_i_disjoint, 1);
2312 rb_define_method(rb_cSet, "divide", set_i_divide, 0);
2313 rb_define_method(rb_cSet, "each", set_i_each, 0);
2314 rb_define_method(rb_cSet, "empty?", set_i_empty, 0);
2315 rb_define_method(rb_cSet, "flatten", set_i_flatten, 0);
2316 rb_define_method(rb_cSet, "flatten!", set_i_flatten_bang, 0);
2317 rb_define_method(rb_cSet, "hash", set_i_hash, 0);
2318 rb_define_method(rb_cSet, "include?", set_i_include, 1);
2319 rb_define_alias(rb_cSet, "member?", "include?");
2320 rb_define_alias(rb_cSet, "===", "include?");
2321 rb_define_method(rb_cSet, "inspect", set_i_inspect, 0);
2322 rb_define_alias(rb_cSet, "to_s", "inspect");
2323 rb_define_method(rb_cSet, "intersect?", set_i_intersect, 1);
2324 rb_define_method(rb_cSet, "join", set_i_join, -1);
2325 rb_define_method(rb_cSet, "keep_if", set_i_keep_if, 0);
2326 rb_define_method(rb_cSet, "merge", set_i_merge, -1);
2327 rb_define_method(rb_cSet, "proper_subset?", set_i_proper_subset, 1);
2328 rb_define_alias(rb_cSet, "<", "proper_subset?");
2329 rb_define_method(rb_cSet, "proper_superset?", set_i_proper_superset, 1);
2330 rb_define_alias(rb_cSet, ">", "proper_superset?");
2331 rb_define_method(rb_cSet, "reject!", set_i_reject, 0);
2332 rb_define_method(rb_cSet, "replace", set_i_replace, 1);
2333 rb_define_method(rb_cSet, "reset", set_i_reset, 0);
2334 rb_define_method(rb_cSet, "size", set_i_size, 0);
2335 rb_define_alias(rb_cSet, "length", "size");
2336 rb_define_method(rb_cSet, "select!", set_i_select, 0);
2337 rb_define_alias(rb_cSet, "filter!", "select!");
2338 rb_define_method(rb_cSet, "subset?", set_i_subset, 1);
2339 rb_define_alias(rb_cSet, "<=", "subset?");
2340 rb_define_method(rb_cSet, "subtract", set_i_subtract, 1);
2341 rb_define_method(rb_cSet, "superset?", set_i_superset, 1);
2342 rb_define_alias(rb_cSet, ">=", "superset?");
2343 rb_define_method(rb_cSet, "to_a", set_i_to_a, 0);
2344 rb_define_method(rb_cSet, "to_set", set_i_to_set, -1);
2345
2346 /* :nodoc: */
2347 VALUE compat = rb_define_class_under(rb_cSet, "compatible", rb_cObject);
2348 rb_marshal_define_compat(rb_cSet, compat, compat_dumper, compat_loader);
2349
2350 // Create Set::CoreSet before defining inherited, so it does not include
2351 // the backwards compatibility layer.
2353 rb_define_private_method(rb_singleton_class(rb_cSet), "inherited", set_s_inherited, 1);
2354
2355 rb_provide("set.rb");
2356}
#define rb_define_method(klass, mid, func, arity)
Defines klass#mid.
#define rb_define_singleton_method(klass, mid, func, arity)
Defines klass.mid.
#define rb_define_private_method(klass, mid, func, arity)
Defines klass#mid and makes it private.
void rb_include_module(VALUE klass, VALUE module)
Includes a module to a class.
Definition class.c:1695
VALUE rb_define_class(const char *name, VALUE super)
Defines a top-level class.
Definition class.c:1488
void rb_extend_object(VALUE obj, VALUE module)
Extend the object with the module.
Definition eval.c:1877
VALUE rb_singleton_class(VALUE obj)
Finds or creates the singleton class of the passed object.
Definition class.c:2825
VALUE rb_define_class_under(VALUE outer, const char *name, VALUE super)
Defines a class under the namespace of outer.
Definition class.c:1519
void rb_define_alias(VALUE klass, const char *name1, const char *name2)
Defines an alias of a method.
Definition class.c:2868
int rb_keyword_given_p(void)
Determines if the current method is given a keyword argument.
Definition eval.c:1040
int rb_block_given_p(void)
Determines if the current method is given a block.
Definition eval.c:1027
#define rb_str_buf_cat2
Old name of rb_usascii_str_new_cstr.
Definition string.h:1683
#define Qundef
Old name of RUBY_Qundef.
#define CLASS_OF
Old name of rb_class_of.
Definition globals.h:205
#define LONG2FIX
Old name of RB_INT2FIX.
Definition long.h:49
#define T_HASH
Old name of RUBY_T_HASH.
Definition value_type.h:65
#define FLONUM_P
Old name of RB_FLONUM_P.
#define Qtrue
Old name of RUBY_Qtrue.
#define ST2FIX
Old name of RB_ST2FIX.
Definition st_data_t.h:33
#define INT2NUM
Old name of RB_INT2NUM.
Definition int.h:43
#define Qnil
Old name of RUBY_Qnil.
#define Qfalse
Old name of RUBY_Qfalse.
#define FIX2LONG
Old name of RB_FIX2LONG.
Definition long.h:46
#define T_ARRAY
Old name of RUBY_T_ARRAY.
Definition value_type.h:56
#define ALLOCV_N
Old name of RB_ALLOCV_N.
Definition memory.h:405
#define POSFIXABLE
Old name of RB_POSFIXABLE.
Definition fixnum.h:29
#define FIXNUM_P
Old name of RB_FIXNUM_P.
#define ALLOCV_END
Old name of RB_ALLOCV_END.
Definition memory.h:406
VALUE rb_eRuntimeError
RuntimeError exception.
Definition error.c:1429
VALUE rb_ensure(VALUE(*b_proc)(VALUE), VALUE data1, VALUE(*e_proc)(VALUE), VALUE data2)
An equivalent to ensure clause.
Definition eval.c:1178
VALUE rb_cSet
Set class.
Definition set.c:97
VALUE rb_class_new_instance(int argc, const VALUE *argv, VALUE klass)
Allocates, then initialises an instance of the given class.
Definition object.c:2249
VALUE rb_mEnumerable
Enumerable module.
Definition enum.c:27
VALUE rb_obj_class(VALUE obj)
Queries the class of an object.
Definition object.c:264
VALUE rb_obj_dup(VALUE obj)
Duplicates the given object.
Definition object.c:582
VALUE rb_inspect(VALUE obj)
Generates a human-readable textual representation of the given object.
Definition object.c:686
VALUE rb_obj_is_instance_of(VALUE obj, VALUE klass)
Queries if the given object is a direct instance of the given class.
Definition object.c:867
VALUE rb_obj_is_kind_of(VALUE obj, VALUE klass)
Queries if the given object is an instance (of possibly descendants) of the given class.
Definition object.c:923
VALUE rb_cString
String class.
Definition string.c:84
#define RB_OBJ_WRITTEN(old, oldv, young)
Identical to RB_OBJ_WRITE(), except it doesn't write any values, but only a WB declaration.
Definition gc.h:615
VALUE rb_str_export_to_enc(VALUE obj, rb_encoding *enc)
Identical to rb_str_export(), except it additionally takes an encoding.
Definition string.c:1464
VALUE rb_funcall_passing_block(VALUE recv, ID mid, int argc, const VALUE *argv)
Identical to rb_funcallv_public(), except you can pass the passed block.
Definition vm_eval.c:1182
VALUE rb_funcall(VALUE recv, ID mid, int n,...)
Calls a method.
Definition vm_eval.c:1119
VALUE rb_ary_new_capa(long capa)
Identical to rb_ary_new(), except it additionally specifies how many rooms of objects it should alloc...
VALUE rb_ary_push(VALUE ary, VALUE elem)
Special case of rb_ary_cat() that it adds only one element.
VALUE rb_ary_freeze(VALUE obj)
Freeze an array, preventing further modifications.
VALUE rb_ary_join(VALUE ary, VALUE sep)
Recursively stringises the elements of the passed array, flattens that result, then joins the sequenc...
#define RETURN_SIZED_ENUMERATOR(obj, argc, argv, size_fn)
This roughly resembles return enum_for(__callee__) unless block_given?.
Definition enumerator.h:208
void rb_provide(const char *feature)
Declares that the given feature is already provided by someone else.
Definition load.c:695
#define rb_hash_uint(h, i)
Just another name of st_hash_uint.
Definition string.h:943
VALUE rb_str_buf_append(VALUE dst, VALUE src)
Identical to rb_str_cat_cstr(), except it takes Ruby's string instead of C's.
Definition string.c:3797
VALUE rb_str_buf_cat_ascii(VALUE dst, const char *src)
Identical to rb_str_cat_cstr(), except it additionally assumes the source string be a NUL terminated ...
Definition string.c:3773
VALUE rb_exec_recursive(VALUE(*f)(VALUE g, VALUE h, int r), VALUE g, VALUE h)
"Recursion" API entry point.
Definition thread.c:5616
VALUE rb_exec_recursive_paired(VALUE(*f)(VALUE g, VALUE h, int r), VALUE g, VALUE p, VALUE h)
Identical to rb_exec_recursive(), except it checks for the recursion on the ordered pair of { g,...
Definition thread.c:5627
VALUE rb_const_get(VALUE space, ID name)
Identical to rb_const_defined(), except it returns the actual defined value.
Definition variable.c:3505
VALUE rb_ivar_set(VALUE obj, ID name, VALUE val)
Identical to rb_iv_set(), except it accepts the name as an ID instead of a C string.
Definition variable.c:2030
VALUE rb_ivar_get(VALUE obj, ID name)
Identical to rb_iv_get(), except it accepts the name as an ID instead of a C string.
Definition variable.c:1505
VALUE rb_class_path(VALUE mod)
Identical to rb_mod_name(), except it returns #<Class: ...> style inspection for anonymous modules.
Definition variable.c:380
int rb_respond_to(VALUE obj, ID mid)
Queries if the object responds to the method.
Definition vm_method.c:3480
void rb_define_alloc_func(VALUE klass, rb_alloc_func_t func)
Sets the allocator function of a class.
int capa
Designed capacity of the buffer.
Definition io.h:11
char * ptr
Pointer to the underlying memory region, of at least capa bytes.
Definition io.h:2
#define RB_BLOCK_CALL_FUNC_ARGLIST(yielded_arg, callback_arg)
Shim for block function parameters.
Definition iterator.h:58
VALUE rb_yield_values(int n,...)
Identical to rb_yield(), except it takes variadic number of parameters and pass them to the block.
Definition vm_eval.c:1397
VALUE rb_yield(VALUE val)
Yields the block.
Definition vm_eval.c:1374
void rb_marshal_define_compat(VALUE newclass, VALUE oldclass, VALUE(*dumper)(VALUE), VALUE(*loader)(VALUE, VALUE))
Marshal format compatibility layer.
Definition marshal.c:137
#define RB_GC_GUARD(v)
Prevents premature destruction of local objects.
Definition memory.h:167
VALUE rb_block_call(VALUE q, ID w, int e, const VALUE *r, type *t, VALUE y)
Call a method with a block.
VALUE type(ANYARGS)
ANYARGS-ed function type.
#define RARRAY_LEN
Just another name of rb_array_len.
Definition rarray.h:51
#define RARRAY_PTR_USE(ary, ptr_name, expr)
Declares a section of code where raw pointers are used.
Definition rarray.h:348
#define RARRAY_AREF(a, i)
Definition rarray.h:403
#define RBASIC(obj)
Convenient casting macro.
Definition rbasic.h:40
#define TypedData_Get_Struct(obj, type, data_type, sval)
Obtains a C struct from inside of a wrapper Ruby object.
Definition rtypeddata.h:649
struct rb_data_type_struct rb_data_type_t
This is the struct that holds necessary info for a struct.
Definition rtypeddata.h:205
#define TypedData_Make_Struct(klass, type, data_type, sval)
Identical to TypedData_Wrap_Struct, except it allocates a new data region internally instead of takin...
Definition rtypeddata.h:508
VALUE rb_require(const char *feature)
Identical to rb_require_string(), except it takes C's string instead of Ruby's.
Definition load.c:1455
size_t rb_set_size(VALUE set)
Returns the number of elements in the set.
Definition set.c:2032
VALUE rb_set_clear(VALUE set)
Removes all entries from set.
Definition set.c:2020
bool rb_set_delete(VALUE set, VALUE element)
Removes the element from from set.
Definition set.c:2026
bool rb_set_add(VALUE set, VALUE element)
Adds element to set.
Definition set.c:2014
void rb_set_foreach(VALUE set, int(*func)(VALUE element, VALUE arg), VALUE arg)
Iterates over a set.
Definition set.c:1990
bool rb_set_lookup(VALUE set, VALUE element)
Whether the set contains the given element.
Definition set.c:2008
VALUE rb_set_new(void)
Creates a new, empty set object.
Definition set.c:1996
VALUE rb_set_new_capa(size_t capa)
Identical to rb_set_new(), except it additionally specifies how many elements it is expected to conta...
Definition set.c:2002
#define RTEST
This is an old name of RB_TEST.
set_table_entry * entries
Array of size 2^entry_power.
Definition set_table.h:28
uintptr_t ID
Type that represents a Ruby identifier such as a variable name.
Definition value.h:52
uintptr_t VALUE
Type that represents a Ruby object.
Definition value.h:40