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