diff options
Diffstat (limited to 'array.c')
| -rw-r--r-- | array.c | 821 |
1 files changed, 513 insertions, 308 deletions
@@ -11,11 +11,9 @@ **********************************************************************/ -#include "ruby/ruby.h" +#include "internal.h" #include "ruby/util.h" #include "ruby/st.h" -#include "ruby/encoding.h" -#include "internal.h" #include "probes.h" #include "id.h" @@ -31,70 +29,6 @@ static ID id_cmp, id_div, id_power; #define ARY_DEFAULT_SIZE 16 #define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE)) -void -rb_mem_clear(register VALUE *mem, register long size) -{ - while (size--) { - *mem++ = Qnil; - } -} - -static void -ary_mem_clear(VALUE ary, long beg, long size) -{ - RARRAY_PTR_USE(ary, ptr, { - rb_mem_clear(ptr + beg, size); - }); -} - -static inline void -memfill(register VALUE *mem, register long size, register VALUE val) -{ - while (size--) { - *mem++ = val; - } -} - -static void -ary_memfill(VALUE ary, long beg, long size, VALUE val) -{ - RARRAY_PTR_USE(ary, ptr, { - memfill(ptr + beg, size, val); - RB_OBJ_WRITTEN(ary, Qundef, val); - }); -} - -static void -ary_memcpy(VALUE ary, long beg, long argc, const VALUE *argv) -{ -#if 1 - if (OBJ_PROMOTED(ary)) { - if (argc > (int)(128/sizeof(VALUE)) /* is magic number (cache line size) */) { - rb_gc_writebarrier_remember_promoted(ary); - RARRAY_PTR_USE(ary, ptr, { - MEMCPY(ptr+beg, argv, VALUE, argc); - }); - } - else { - int i; - RARRAY_PTR_USE(ary, ptr, { - for (i=0; i<argc; i++) { - RB_OBJ_WRITE(ary, &ptr[i+beg], argv[i]); - } - }); - } - } - else { - RARRAY_PTR_USE(ary, ptr, { - MEMCPY(ptr+beg, argv, VALUE, argc); - }); - } -#else - /* giveup write barrier (traditional way) */ - MEMCPY(RARRAY_PTR(ary)+beg, argv, VALUE, argc); -#endif -} - # define ARY_SHARED_P(ary) \ (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \ FL_TEST((ary),ELTS_SHARED)!=0) @@ -195,6 +129,74 @@ ary_memcpy(VALUE ary, long beg, long argc, const VALUE *argv) FL_SET((ary), RARRAY_SHARED_ROOT_FLAG); \ } while (0) +#define ARY_SET(a, i, v) RARRAY_ASET((assert(!ARY_SHARED_P(a)), (a)), (i), (v)) + +void +rb_mem_clear(register VALUE *mem, register long size) +{ + while (size--) { + *mem++ = Qnil; + } +} + +static void +ary_mem_clear(VALUE ary, long beg, long size) +{ + RARRAY_PTR_USE(ary, ptr, { + rb_mem_clear(ptr + beg, size); + }); +} + +static inline void +memfill(register VALUE *mem, register long size, register VALUE val) +{ + while (size--) { + *mem++ = val; + } +} + +static void +ary_memfill(VALUE ary, long beg, long size, VALUE val) +{ + RARRAY_PTR_USE(ary, ptr, { + memfill(ptr + beg, size, val); + RB_OBJ_WRITTEN(ary, Qundef, val); + }); +} + +static void +ary_memcpy0(VALUE ary, long beg, long argc, const VALUE *argv, VALUE buff_owner_ary) +{ +#if 1 + assert(!ARY_SHARED_P(buff_owner_ary)); + + if (argc > (int)(128/sizeof(VALUE)) /* is magic number (cache line size) */) { + rb_gc_writebarrier_remember(buff_owner_ary); + RARRAY_PTR_USE(ary, ptr, { + MEMCPY(ptr+beg, argv, VALUE, argc); + }); + } + else { + int i; + RARRAY_PTR_USE(ary, ptr, { + for (i=0; i<argc; i++) { + RB_OBJ_WRITE(buff_owner_ary, &ptr[i+beg], argv[i]); + } + }); + } +#else + /* giveup write barrier (traditional way) */ + RARRAY_PTR(buff_owner_ary); + MEMCPY(RARRAY_PTR(ary)+beg, argv, VALUE, argc); +#endif +} + +static void +ary_memcpy(VALUE ary, long beg, long argc, const VALUE *argv) +{ + ary_memcpy0(ary, beg, argc, argv, ary); +} + static void ary_resize_capa(VALUE ary, long capacity) { @@ -343,21 +345,28 @@ rb_ary_modify(VALUE ary) ARY_SET_CAPA(ary, len); ARY_SET_PTR(ary, ptr); } + + rb_gc_writebarrier_remember(ary); } } -static void +static VALUE ary_ensure_room_for_push(VALUE ary, long add_len) { - long new_len = RARRAY_LEN(ary) + add_len; + long old_len = RARRAY_LEN(ary); + long new_len = old_len + add_len; long capa; + if (old_len > ARY_MAX_SIZE - add_len) { + rb_raise(rb_eIndexError, "index %ld too big", new_len); + } if (ARY_SHARED_P(ary)) { if (new_len > RARRAY_EMBED_LEN_MAX) { VALUE shared = ARY_SHARED(ary); if (ARY_SHARED_OCCUPIED(shared)) { if (RARRAY_CONST_PTR(ary) - RARRAY_CONST_PTR(shared) + new_len <= RARRAY_LEN(shared)) { rb_ary_modify_check(ary); + return shared; } else { /* if array is shared, then it is likely it participate in push/shift pattern */ @@ -366,8 +375,8 @@ ary_ensure_room_for_push(VALUE ary, long add_len) if (new_len > capa - (capa >> 6)) { ary_double_capa(ary, new_len); } + return ary; } - return; } } } @@ -376,6 +385,8 @@ ary_ensure_room_for_push(VALUE ary, long add_len) if (new_len > capa) { ary_double_capa(ary, new_len); } + + return ary; } /* @@ -442,10 +453,7 @@ ary_alloc(VALUE klass) static VALUE empty_ary_alloc(VALUE klass) { - if (RUBY_DTRACE_ARRAY_CREATE_ENABLED()) { - RUBY_DTRACE_ARRAY_CREATE(0, rb_sourcefile(), rb_sourceline()); - } - + RUBY_DTRACE_CREATE_HOOK(ARRAY, 0); return ary_alloc(klass); } @@ -461,21 +469,16 @@ ary_new(VALUE klass, long capa) rb_raise(rb_eArgError, "array size too big"); } - if (RUBY_DTRACE_ARRAY_CREATE_ENABLED()) { - RUBY_DTRACE_ARRAY_CREATE(capa, rb_sourcefile(), rb_sourceline()); - } + RUBY_DTRACE_CREATE_HOOK(ARRAY, capa); + ary = ary_alloc(klass); if (capa > RARRAY_EMBED_LEN_MAX) { ptr = ALLOC_N(VALUE, capa); - ary = ary_alloc(klass); FL_UNSET_EMBED(ary); ARY_SET_PTR(ary, ptr); ARY_SET_CAPA(ary, capa); ARY_SET_HEAP_LEN(ary, 0); } - else { - ary = ary_alloc(klass); - } return ary; } @@ -493,7 +496,7 @@ rb_ary_new(void) } VALUE -rb_ary_new_from_args(long n, ...) +(rb_ary_new_from_args)(long n, ...) { va_list ar; VALUE ary; @@ -503,7 +506,7 @@ rb_ary_new_from_args(long n, ...) va_start(ar, n); for (i=0; i<n; i++) { - RARRAY_ASET(ary, i, va_arg(ar, VALUE)); + ARY_SET(ary, i, va_arg(ar, VALUE)); } va_end(ar); @@ -531,6 +534,15 @@ rb_ary_tmp_new(long capa) return ary_new(0, capa); } +VALUE +rb_ary_tmp_new_fill(long capa) +{ + VALUE ary = ary_new(0, capa); + ary_memfill(ary, 0, capa, Qnil); + ARY_SET_LEN(ary, capa); + return ary; +} + void rb_ary_free(VALUE ary) { @@ -576,7 +588,7 @@ ary_make_shared(VALUE ary) } else { long capa = ARY_CAPA(ary), len = RARRAY_LEN(ary); - NEWOBJ_OF(shared, struct RArray, 0, T_ARRAY); /* keep shared ary as non-WB-protected */ + NEWOBJ_OF(shared, struct RArray, 0, T_ARRAY | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0)); FL_UNSET_EMBED(shared); ARY_SET_LEN((VALUE)shared, capa); @@ -652,16 +664,16 @@ rb_ary_s_try_convert(VALUE dummy, VALUE ary) /* * call-seq: - * Array.new(size=0, obj=nil) + * Array.new(size=0, default=nil) * Array.new(array) * Array.new(size) {|index| block } * * Returns a new array. * * In the first form, if no arguments are sent, the new array will be empty. - * When a +size+ and an optional +obj+ are sent, an array is created with - * +size+ copies of +obj+. Take notice that all elements will reference the - * same object +obj+. + * When a +size+ and an optional +default+ are sent, an array is created with + * +size+ copies of +default+. Take notice that all elements will reference the + * same object +default+. * * The second form creates a copy of the array passed as a parameter (the * array is generated by calling to_ary on the parameter). @@ -735,12 +747,14 @@ rb_ary_initialize(int argc, VALUE *argv, VALUE ary) } len = NUM2LONG(size); + /* NUM2LONG() may call size.to_int, ary can be frozen, modified, etc */ if (len < 0) { rb_raise(rb_eArgError, "negative array size"); } if (len > ARY_MAX_SIZE) { rb_raise(rb_eArgError, "array size too big"); } + /* recheck after argument conversion */ rb_ary_modify(ary); ary_resize_capa(ary, len); if (rb_block_given_p()) { @@ -808,7 +822,7 @@ rb_ary_store(VALUE ary, long idx, VALUE val) if (idx >= len) { ARY_SET_LEN(ary, idx + 1); } - RARRAY_ASET(ary, idx, val); + ARY_SET(ary, idx, val); } static VALUE @@ -852,7 +866,7 @@ enum ary_take_pos_flags }; static VALUE -ary_take_first_or_last(int argc, VALUE *argv, VALUE ary, enum ary_take_pos_flags last) +ary_take_first_or_last(int argc, const VALUE *argv, VALUE ary, enum ary_take_pos_flags last) { VALUE nv; long n; @@ -891,33 +905,20 @@ VALUE rb_ary_push(VALUE ary, VALUE item) { long idx = RARRAY_LEN(ary); - - ary_ensure_room_for_push(ary, 1); - RARRAY_ASET(ary, idx, item); - ARY_SET_LEN(ary, idx + 1); - return ary; -} - -static VALUE -rb_ary_push_1(VALUE ary, VALUE item) -{ - long idx = RARRAY_LEN(ary); - - if (idx >= ARY_CAPA(ary)) { - ary_double_capa(ary, idx); - } - RARRAY_ASET(ary, idx, item); + VALUE target_ary = ary_ensure_room_for_push(ary, 1); + RARRAY_PTR_USE(ary, ptr, { + RB_OBJ_WRITE(target_ary, &ptr[idx], item); + }); ARY_SET_LEN(ary, idx + 1); return ary; } VALUE -rb_ary_cat(VALUE ary, const VALUE *ptr, long len) +rb_ary_cat(VALUE ary, const VALUE *argv, long len) { long oldlen = RARRAY_LEN(ary); - - ary_ensure_room_for_push(ary, len); - ary_memcpy(ary, oldlen, len, ptr); + VALUE target_ary = ary_ensure_room_for_push(ary, len); + ary_memcpy0(ary, oldlen, len, argv, target_ary); ARY_SET_LEN(ary, oldlen + len); return ary; } @@ -1014,11 +1015,11 @@ rb_ary_shift(VALUE ary) } assert(!ARY_EMBED_P(ary)); /* ARY_EMBED_LEN_MAX < ARY_DEFAULT_SIZE */ - RARRAY_ASET(ary, 0, Qnil); + ARY_SET(ary, 0, Qnil); ary_make_shared(ary); } else if (ARY_SHARED_OCCUPIED(ARY_SHARED(ary))) { - RARRAY_ASET(ary, 0, Qnil); + RARRAY_PTR_USE(ary, ptr, ptr[0] = Qnil); } ARY_INCREASE_PTR(ary, 1); /* shift ptr */ ARY_INCREASE_LEN(ary, -1); @@ -1064,21 +1065,28 @@ rb_ary_shift_m(int argc, VALUE *argv, VALUE ary) n = RARRAY_LEN(result); if (ARY_SHARED_P(ary)) { if (ARY_SHARED_OCCUPIED(ARY_SHARED(ary))) { + setup_occupied_shared: ary_mem_clear(ary, 0, n); } ARY_INCREASE_PTR(ary, n); } else { - RARRAY_PTR_USE(ary, ptr, { - MEMMOVE(ptr, ptr + n, VALUE, RARRAY_LEN(ary)-n); - }); /* WB: no new reference */ + if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE) { + RARRAY_PTR_USE(ary, ptr, { + MEMMOVE(ptr, ptr+n, VALUE, RARRAY_LEN(ary)-n); + }); /* WB: no new reference */ + } + else { + ary_make_shared(ary); + goto setup_occupied_shared; + } } ARY_INCREASE_LEN(ary, -n); return result; } -static void +static VALUE ary_ensure_room_for_unshift(VALUE ary, int argc) { long len = RARRAY_LEN(ary); @@ -1086,6 +1094,10 @@ ary_ensure_room_for_unshift(VALUE ary, int argc) long capa; const VALUE *head, *sharedp; + if (len > ARY_MAX_SIZE - argc) { + rb_raise(rb_eIndexError, "index %ld too big", new_len); + } + if (ARY_SHARED_P(ary)) { VALUE shared = ARY_SHARED(ary); capa = RARRAY_LEN(shared); @@ -1120,12 +1132,16 @@ ary_ensure_room_for_unshift(VALUE ary, int argc) head = sharedp + argc + room; } ARY_SET_PTR(ary, head - argc); + assert(ARY_SHARED_OCCUPIED(ARY_SHARED(ary))); + return ARY_SHARED(ary); } else { /* sliding items */ RARRAY_PTR_USE(ary, ptr, { MEMMOVE(ptr + argc, ptr, VALUE, len); }); + + return ary; } } @@ -1145,14 +1161,15 @@ static VALUE rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary) { long len = RARRAY_LEN(ary); + VALUE target_ary; if (argc == 0) { rb_ary_modify_check(ary); return ary; } - ary_ensure_room_for_unshift(ary, argc); - ary_memcpy(ary, 0, argc, argv); + target_ary = ary_ensure_room_for_unshift(ary, argc); + ary_memcpy0(ary, 0, argc, argv, target_ary); ARY_SET_LEN(ary, len + argc); return ary; } @@ -1239,7 +1256,7 @@ rb_ary_subseq(VALUE ary, long beg, long len) */ VALUE -rb_ary_aref(int argc, VALUE *argv, VALUE ary) +rb_ary_aref(int argc, const VALUE *argv, VALUE ary) { VALUE arg; long beg, len; @@ -1285,7 +1302,7 @@ rb_ary_aref(int argc, VALUE *argv, VALUE ary) * a.at(-1) #=> "e" */ -static VALUE +VALUE rb_ary_at(VALUE ary, VALUE pos) { return rb_ary_entry(ary, NUM2LONG(pos)); @@ -1334,7 +1351,7 @@ rb_ary_first(int argc, VALUE *argv, VALUE ary) */ VALUE -rb_ary_last(int argc, VALUE *argv, VALUE ary) +rb_ary_last(int argc, const VALUE *argv, VALUE ary) { if (argc == 0) { long len = RARRAY_LEN(ary); @@ -1563,20 +1580,24 @@ rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl) olen = RARRAY_LEN(ary); /* ary may be resized in rpl.to_ary too */ } if (beg >= olen) { + VALUE target_ary; if (beg > ARY_MAX_SIZE - rlen) { rb_raise(rb_eIndexError, "index %ld too big", beg); } - ary_ensure_room_for_push(ary, rlen-len); /* len is 0 or negative */ + target_ary = ary_ensure_room_for_push(ary, rlen-len); /* len is 0 or negative */ len = beg + rlen; ary_mem_clear(ary, olen, beg - olen); if (rlen > 0) { - ary_memcpy(ary, beg, rlen, RARRAY_CONST_PTR(rpl)); + ary_memcpy0(ary, beg, rlen, RARRAY_CONST_PTR(rpl), target_ary); } ARY_SET_LEN(ary, len); } else { long alen; + if (olen - len > ARY_MAX_SIZE - rlen) { + rb_raise(rb_eIndexError, "index %ld too big", olen + rlen - len); + } rb_ary_modify(ary); alen = olen + rlen - len; if (alen >= ARY_CAPA(ary)) { @@ -1593,6 +1614,7 @@ rb_ary_splice(VALUE ary, long beg, long len, VALUE rpl) MEMMOVE(RARRAY_PTR(ary) + beg, RARRAY_CONST_PTR(rpl), VALUE, rlen); } } + RB_GC_GUARD(rpl); } void @@ -1728,7 +1750,9 @@ fixnum: * Inserts the given values before the element with the given +index+. * * Negative indices count backwards from the end of the array, where +-1+ is - * the last element. + * the last element. If a negative index is used, the given values will be + * inserted after that element, so using an index of +-1+ will insert the + * values at the end of the array. * * a = %w{ a b c d } * a.insert(2, 99) #=> ["a", "b", 99, "c", "d"] @@ -1742,8 +1766,8 @@ rb_ary_insert(int argc, VALUE *argv, VALUE ary) rb_check_arity(argc, 1, UNLIMITED_ARGUMENTS); rb_ary_modify_check(ary); - if (argc == 1) return ary; pos = NUM2LONG(argv[0]); + if (argc == 1) return ary; if (pos == -1) { pos = RARRAY_LEN(ary); } @@ -1769,9 +1793,9 @@ ary_enum_length(VALUE ary, VALUE args, VALUE eobj) * ary.each -> Enumerator * * Calls the given block once for each element in +self+, passing that element - * as a parameter. + * as a parameter. Returns the array itself. * - * An Enumerator is returned if no block is given. + * If no block is given, an Enumerator is returned. * * a = [ "a", "b", "c" ] * a.each {|x| print x, " -- " } @@ -1782,10 +1806,9 @@ ary_enum_length(VALUE ary, VALUE args, VALUE eobj) */ VALUE -rb_ary_each(VALUE array) +rb_ary_each(VALUE ary) { long i; - volatile VALUE ary = array; RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length); for (i=0; i<RARRAY_LEN(ary); i++) { @@ -2142,10 +2165,11 @@ rb_ary_to_h(VALUE ary) long i; VALUE hash = rb_hash_new(); for (i=0; i<RARRAY_LEN(ary); i++) { - VALUE key_value_pair = rb_check_array_type(rb_ary_elt(ary, i)); + const VALUE elt = rb_ary_elt(ary, i); + const VALUE key_value_pair = rb_check_array_type(elt); if (NIL_P(key_value_pair)) { - rb_raise(rb_eTypeError, "wrong element type %s at %ld (expected array)", - rb_builtin_class_name(rb_ary_elt(ary, i)), i); + rb_raise(rb_eTypeError, "wrong element type %"PRIsVALUE" at %ld (expected array)", + rb_obj_class(elt), i); } if (RARRAY_LEN(key_value_pair) != 2) { rb_raise(rb_eArgError, "wrong array length at %ld (expected 2, was %ld)", @@ -2417,9 +2441,9 @@ sort_2(const void *ap, const void *bp, void *dummy) * Comparisons for the sort will be done using the <code><=></code> operator * or using an optional code block. * - * The block must implement a comparison between +a+ and +b+, and return - * +-1+, when +a+ follows +b+, +0+ when +a+ and +b+ are equivalent, or ++1+ - * if +b+ follows +a+. + * The block must implement a comparison between +a+ and +b+ and return + * an integer less than 0 when +b+ follows +a+, +0+ when +a+ and +b+ + * are equivalent, or an integer greater than 0 when +a+ follows +b+. * * See also Enumerable#sort_by. * @@ -2450,8 +2474,8 @@ rb_ary_sort_bang(VALUE ary) if (ARY_EMBED_P(tmp)) { if (ARY_SHARED_P(ary)) { /* ary might be destructively operated in the given block */ rb_ary_unshare(ary); + FL_SET_EMBED(ary); } - FL_SET_EMBED(ary); ary_memcpy(ary, 0, ARY_EMBED_LEN(tmp), ARY_EMBED_PTR(tmp)); ARY_SET_LEN(ary, ARY_EMBED_LEN(tmp)); } @@ -2498,9 +2522,9 @@ rb_ary_sort_bang(VALUE ary) * Comparisons for the sort will be done using the <code><=></code> operator * or using an optional code block. * - * The block must implement a comparison between +a+ and +b+, and return - * +-1+, when +a+ follows +b+, +0+ when +a+ and +b+ are equivalent, or ++1+ - * if +b+ follows +a+. + * The block must implement a comparison between +a+ and +b+ and return + * an integer less than 0 when +b+ follows +a+, +0+ when +a+ and +b+ + * are equivalent, or an integer greater than 0 when +a+ follows +b+. * * * See also Enumerable#sort_by. @@ -2518,6 +2542,8 @@ rb_ary_sort(VALUE ary) return ary; } +static VALUE rb_ary_bsearch_index(VALUE ary); + /* * call-seq: * ary.bsearch {|x| block } -> elem @@ -2574,6 +2600,30 @@ rb_ary_sort(VALUE ary) static VALUE rb_ary_bsearch(VALUE ary) { + VALUE index_result = rb_ary_bsearch_index(ary); + + if (FIXNUM_P(index_result)) { + return rb_ary_entry(ary, FIX2LONG(index_result)); + } + return index_result; +} + +/* + * call-seq: + * ary.bsearch_index {|x| block } -> int or nil + * + * By using binary search, finds an index of a value from this array which + * meets the given condition in O(log n) where n is the size of the array. + * + * It supports two modes, depending on the nature of the block and they are + * exactly the same as in the case of #bsearch method with the only difference + * being that this method returns the index of the element instead of the + * element itself. For more details consult the documentation for #bsearch. + */ + +static VALUE +rb_ary_bsearch_index(VALUE ary) +{ long low = 0, high = RARRAY_LEN(ary), mid; int smaller = 0, satisfied = 0; VALUE v, val; @@ -2584,8 +2634,8 @@ rb_ary_bsearch(VALUE ary) val = rb_ary_entry(ary, mid); v = rb_yield(val); if (FIXNUM_P(v)) { - if (FIX2INT(v) == 0) return val; - smaller = FIX2INT(v) < 0; + if (v == INT2FIX(0)) return INT2FIX(mid); + smaller = (SIGNED_VALUE)v < 0; /* Fixnum preserves its sign-bit */ } else if (v == Qtrue) { satisfied = 1; @@ -2596,16 +2646,16 @@ rb_ary_bsearch(VALUE ary) } else if (rb_obj_is_kind_of(v, rb_cNumeric)) { const VALUE zero = INT2FIX(0); - switch (rb_cmpint(rb_funcallv(v, id_cmp, 1, &zero), v, INT2FIX(0))) { - case 0: return val; - case 1: smaller = 1; break; - case -1: smaller = 0; + switch (rb_cmpint(rb_funcallv(v, id_cmp, 1, &zero), v, zero)) { + case 0: return INT2FIX(mid); + case 1: smaller = 1; break; + case -1: smaller = 0; } } else { - rb_raise(rb_eTypeError, "wrong argument type %s" - " (must be numeric, true, false or nil)", - rb_obj_classname(v)); + rb_raise(rb_eTypeError, "wrong argument type %"PRIsVALUE + " (must be numeric, true, false or nil)", + rb_obj_class(v)); } if (smaller) { high = mid; @@ -2614,9 +2664,8 @@ rb_ary_bsearch(VALUE ary) low = mid + 1; } } - if (low == RARRAY_LEN(ary)) return Qnil; if (!satisfied) return Qnil; - return rb_ary_entry(ary, low); + return INT2FIX(low); } @@ -2667,9 +2716,9 @@ rb_ary_sort_by_bang(VALUE ary) * If no block is given, an Enumerator is returned instead. * * a = [ "a", "b", "c", "d" ] - * a.collect { |x| x + "!" } #=> ["a!", "b!", "c!", "d!"] - * a.map.with_index{ |x, i| x * i } #=> ["", "b", "cc", "ddd"] - * a #=> ["a", "b", "c", "d"] + * a.collect { |x| x + "!" } #=> ["a!", "b!", "c!", "d!"] + * a.map.with_index { |x, i| x * i } #=> ["", "b", "cc", "ddd"] + * a #=> ["a", "b", "c", "d"] */ static VALUE @@ -2722,7 +2771,7 @@ rb_ary_collect_bang(VALUE ary) } VALUE -rb_get_values_at(VALUE obj, long olen, int argc, VALUE *argv, VALUE (*func) (VALUE, long)) +rb_get_values_at(VALUE obj, long olen, int argc, const VALUE *argv, VALUE (*func) (VALUE, long)) { VALUE result = rb_ary_new2(argc); long beg, len, i, j; @@ -2806,6 +2855,50 @@ rb_ary_select(VALUE ary) return result; } +struct select_bang_arg { + VALUE ary; + long len[2]; +}; + +static VALUE +select_bang_i(VALUE a) +{ + volatile struct select_bang_arg *arg = (void *)a; + VALUE ary = arg->ary; + long i1, i2; + + for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); arg->len[0] = ++i1) { + VALUE v = RARRAY_AREF(ary, i1); + if (!RTEST(rb_yield(v))) continue; + if (i1 != i2) { + rb_ary_store(ary, i2, v); + } + arg->len[1] = ++i2; + } + return (i1 == i2) ? Qnil : ary; +} + +static VALUE +select_bang_ensure(VALUE a) +{ + volatile struct select_bang_arg *arg = (void *)a; + VALUE ary = arg->ary; + long len = RARRAY_LEN(ary); + long i1 = arg->len[0], i2 = arg->len[1]; + + if (i2 < len && i2 < i1) { + long tail = 0; + if (i1 < len) { + tail = len - i1; + RARRAY_PTR_USE(ary, ptr, { + MEMMOVE(ptr + i2, ptr + i1, VALUE, tail); + }); + } + ARY_SET_LEN(ary, i2 + tail); + } + return ary; +} + /* * call-seq: * ary.select! {|item| block } -> ary or nil @@ -2814,6 +2907,8 @@ rb_ary_select(VALUE ary) * Invokes the given block passing in successive elements from +self+, * deleting elements for which the block returns a +false+ value. * + * The array may not be changed instantly every time the block is called. + * * If changes were made, it will return +self+, otherwise it returns +nil+. * * See also Array#keep_if @@ -2825,23 +2920,14 @@ rb_ary_select(VALUE ary) static VALUE rb_ary_select_bang(VALUE ary) { - long i1, i2; + struct select_bang_arg args; RETURN_SIZED_ENUMERATOR(ary, 0, 0, ary_enum_length); rb_ary_modify(ary); - for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) { - VALUE v = RARRAY_AREF(ary, i1); - if (!RTEST(rb_yield(v))) continue; - if (i1 != i2) { - rb_ary_store(ary, i2, v); - } - i2++; - } - if (i1 == i2) return Qnil; - if (i2 < i1) - ARY_SET_LEN(ary, i2); - return ary; + args.ary = ary; + args.len[0] = args.len[1] = 0; + return rb_ensure(select_bang_i, (VALUE)&args, select_bang_ensure, (VALUE)&args); } /* @@ -3077,30 +3163,39 @@ ary_reject(VALUE orig, VALUE result) for (i = 0; i < RARRAY_LEN(orig); i++) { VALUE v = RARRAY_AREF(orig, i); if (!RTEST(rb_yield(v))) { - rb_ary_push_1(result, v); + rb_ary_push(result, v); } } return result; } static VALUE -ary_reject_bang(VALUE ary) +reject_bang_i(VALUE a) { - long i; - VALUE result = Qnil; + volatile struct select_bang_arg *arg = (void *)a; + VALUE ary = arg->ary; + long i1, i2; - rb_ary_modify_check(ary); - for (i = 0; i < RARRAY_LEN(ary); ) { - VALUE v = RARRAY_AREF(ary, i); - if (RTEST(rb_yield(v))) { - rb_ary_delete_at(ary, i); - result = ary; - } - else { - i++; + for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); arg->len[0] = ++i1) { + VALUE v = RARRAY_AREF(ary, i1); + if (RTEST(rb_yield(v))) continue; + if (i1 != i2) { + rb_ary_store(ary, i2, v); } + arg->len[1] = ++i2; } - return result; + return (i1 == i2) ? Qnil : ary; +} + +static VALUE +ary_reject_bang(VALUE ary) +{ + struct select_bang_arg args; + + rb_ary_modify_check(ary); + args.ary = ary; + args.len[0] = args.len[1] = 0; + return rb_ensure(reject_bang_i, (VALUE)&args, select_bang_ensure, (VALUE)&args); } /* @@ -3108,11 +3203,10 @@ ary_reject_bang(VALUE ary) * ary.reject! { |item| block } -> ary or nil * ary.reject! -> Enumerator * - * Equivalent to Array#delete_if, deleting elements from +self+ for which the - * block evaluates to +true+, but returns +nil+ if no changes were made. + * Deletes every element of +self+ for which the block evaluates to +true+, + * if no changes were made returns +nil+. * - * The array is changed instantly every time the block is called, not after - * the iteration is over. + * The array may not be changed instantly every time the block is called. * * See also Enumerable#reject and Array#delete_if. * @@ -3132,7 +3226,7 @@ rb_ary_reject_bang(VALUE ary) * ary.reject -> Enumerator * * Returns a new array containing the items in +self+ for which the given - * block is not +true+. + * block is not +true+. The ordering of non-rejected elements is maintained. * * See also Array#delete_if * @@ -3240,8 +3334,10 @@ rb_ary_zip(int argc, VALUE *argv, VALUE ary) if (rb_block_given_p()) { int arity = rb_block_arity(); - if (arity > 1 && argc+1 < 0x100) { - VALUE *tmp = ALLOCA_N(VALUE, argc+1); + if (arity > 1) { + VALUE work, *tmp; + + tmp = ALLOCV_N(VALUE, work, argc+1); for (i=0; i<RARRAY_LEN(ary); i++) { tmp[0] = RARRAY_AREF(ary, i); @@ -3250,6 +3346,8 @@ rb_ary_zip(int argc, VALUE *argv, VALUE ary) } rb_yield_values2(argc+1, tmp); } + + if (work) ALLOCV_END(work); } else { for (i=0; i<RARRAY_LEN(ary); i++) { @@ -3488,7 +3586,7 @@ rb_ary_fill(int argc, VALUE *argv, VALUE ary) for (i=beg; i<end; i++) { v = rb_yield(LONG2NUM(i)); if (i>=RARRAY_LEN(ary)) break; - RARRAY_ASET(ary, i, v); + ARY_SET(ary, i, v); } } else { @@ -3510,6 +3608,13 @@ rb_ary_fill(int argc, VALUE *argv, VALUE ary) * c #=> [ "a", "b", "c", "d", "e", "f" ] * a #=> [ "a", "b", "c" ] * + * Note that + * x += y + * is the same as + * x = x + y + * This means that it produces a new array. As a consequence, + * repeated use of <code>+=</code> on arrays can be quite inefficient. + * * See also Array#concat. */ @@ -3622,7 +3727,7 @@ rb_ary_times(VALUE ary, VALUE times) /* * call-seq: - * ary.assoc(obj) -> new_ary or nil + * ary.assoc(obj) -> element_ary or nil * * Searches through an array whose elements are also arrays comparing +obj+ * with the first element of each contained array using <code>obj.==</code>. @@ -3657,7 +3762,7 @@ rb_ary_assoc(VALUE ary, VALUE key) /* * call-seq: - * ary.rassoc(obj) -> new_ary or nil + * ary.rassoc(obj) -> element_ary or nil * * Searches through the array whose elements are also arrays. * @@ -3741,7 +3846,7 @@ rb_ary_equal(VALUE ary1, VALUE ary2) { if (ary1 == ary2) return Qtrue; if (!RB_TYPE_P(ary2, T_ARRAY)) { - if (!rb_respond_to(ary2, rb_intern("to_ary"))) { + if (!rb_respond_to(ary2, idTo_ary)) { return Qfalse; } return rb_equal(ary2, ary1); @@ -3790,6 +3895,8 @@ rb_ary_eql(VALUE ary1, VALUE ary2) * * Two arrays with the same content will have the same hash code (and will * compare using #eql?). + * + * See also Object#hash. */ static VALUE @@ -3825,9 +3932,15 @@ VALUE rb_ary_includes(VALUE ary, VALUE item) { long i; + VALUE e; for (i=0; i<RARRAY_LEN(ary); i++) { - if (rb_equal(RARRAY_AREF(ary, i), item)) { + e = RARRAY_AREF(ary, i); + switch (rb_equal_opt(e, item)) { + case Qundef: + if (rb_equal(e, item)) return Qtrue; + break; + case Qtrue: return Qtrue; } } @@ -3862,21 +3975,26 @@ recursive_cmp(VALUE ary1, VALUE ary2, int recur) * Comparison --- Returns an integer (+-1+, +0+, or <code>+1</code>) if this * array is less than, equal to, or greater than +other_ary+. * - * +nil+ is returned if the two values are incomparable. - * * Each object in each array is compared (using the <=> operator). * - * Arrays are compared in an "element-wise" manner; the first two elements - * that are not equal will determine the return value for the whole - * comparison. + * Arrays are compared in an "element-wise" manner; the first element of +ary+ + * is compared with the first one of +other_ary+ using the <=> operator, then + * each of the second elements, etc... + * As soon as the result of any such comparison is non zero (i.e. the two + * corresponding elements are not equal), that result is returned for the + * whole array comparison. * - * If all the values are equal, then the return is based on a comparison of + * If all the elements are equal, then the result is based on a comparison of * the array lengths. Thus, two arrays are "equal" according to Array#<=> if, * and only if, they have the same length and the value of each element is * equal to the value of the corresponding element in the other array. * + * +nil+ is returned if the +other_ary+ is not an array or if the comparison + * of two elements returned +nil+. + * * [ "a", "a", "c" ] <=> [ "a", "b", "c" ] #=> -1 * [ 1, 2, 3, 4, 5, 6 ] <=> [ 1, 2 ] #=> +1 + * [ 1, 2 ] <=> [ 1, :two ] #=> nil * */ @@ -3956,6 +4074,7 @@ ary_recycle_hash(VALUE hash) RHASH(hash)->ntbl = 0; st_free_table(tbl); } + RB_GC_GUARD(hash); } /* @@ -3979,7 +4098,7 @@ static VALUE rb_ary_diff(VALUE ary1, VALUE ary2) { VALUE ary3; - volatile VALUE hash; + VALUE hash; long i; hash = ary_make_hash(to_ary(ary2)); @@ -4097,6 +4216,8 @@ push_value(st_data_t key, st_data_t val, st_data_t ary) * * It compares values using their #hash and #eql? methods for efficiency. * + * +self+ is traversed in order, and the first occurrence is kept. + * * Returns +nil+ if no changes are made (that is, no duplicates are found). * * a = [ "a", "a", "b", "b", "c" ] @@ -4152,6 +4273,8 @@ rb_ary_uniq_bang(VALUE ary) * * It compares values using their #hash and #eql? methods for efficiency. * + * +self+ is traversed in order, and the first occurrence is kept. + * * a = [ "a", "a", "b", "b", "c" ] * a.uniq # => ["a", "b", "c"] * @@ -4303,11 +4426,15 @@ flatten(VALUE ary, int level, int *modified) while (1) { while (i < RARRAY_LEN(ary)) { elt = RARRAY_AREF(ary, i++); + if (level >= 0 && RARRAY_LEN(stack) / 2 >= level) { + rb_ary_push(result, elt); + continue; + } tmp = rb_check_array_type(elt); if (RBASIC(result)->klass) { rb_raise(rb_eRuntimeError, "flatten reentered"); } - if (NIL_P(tmp) || (level >= 0 && RARRAY_LEN(stack) / 2 >= level)) { + if (NIL_P(tmp)) { rb_ary_push(result, elt); } else { @@ -4336,7 +4463,7 @@ flatten(VALUE ary, int level, int *modified) st_free_table(memo); - RBASIC_SET_CLASS(result, rb_class_of(ary)); + RBASIC_SET_CLASS(result, rb_obj_class(ary)); return result; } @@ -4434,7 +4561,13 @@ static ID id_random; * * Shuffles elements in +self+ in place. * + * a = [ 1, 2, 3 ] #=> [1, 2, 3] + * a.shuffle! #=> [2, 3, 1] + * a #=> [2, 3, 1] + * * The optional +rng+ argument will be used as the random number generator. + * + * a.shuffle!(random: Random.new(1)) #=> [1, 3, 2] */ static VALUE @@ -4481,6 +4614,7 @@ rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary) * * a = [ 1, 2, 3 ] #=> [1, 2, 3] * a.shuffle #=> [2, 3, 1] + * a #=> [1, 2, 3] * * The optional +rng+ argument will be used as the random number generator. * @@ -4691,8 +4825,26 @@ rb_ary_cycle(int argc, VALUE *argv, VALUE ary) #define tmpary_discard(a) (ary_discard(a), RBASIC_SET_CLASS_RAW(a, rb_cArray)) /* - * Recursively compute permutations of +r+ elements of the set - * <code>[0..n-1]</code>. + * Build a ruby array of the corresponding values and yield it to the + * associated block. + * Return the class of +values+ for reentry check. + */ +static int +yield_indexed_values(const VALUE values, const long r, const long *const p) +{ + const VALUE result = rb_ary_new2(r); + VALUE *const result_array = RARRAY_PTR(result); + const VALUE *const values_array = RARRAY_CONST_PTR(values); + long i; + + for (i = 0; i < r; i++) result_array[i] = values_array[p[i]]; + ARY_SET_LEN(result, r); + rb_yield(result); + return !RBASIC(values)->klass; +} + +/* + * Compute permutations of +r+ elements of the set <code>[0..n-1]</code>. * * When we have a complete permutation of array indexes, copy the values * at those indexes into a new array and yield that array. @@ -4700,38 +4852,40 @@ rb_ary_cycle(int argc, VALUE *argv, VALUE ary) * n: the size of the set * r: the number of elements in each permutation * p: the array (of size r) that we're filling in - * index: what index we're filling in now * used: an array of booleans: whether a given index is already used * values: the Ruby array that holds the actual values to permute */ static void -permute0(long n, long r, long *p, long index, char *used, VALUE values) +permute0(const long n, const long r, long *const p, char *const used, const VALUE values) { - long i,j; - for (i = 0; i < n; i++) { - if (used[i] == 0) { + long i = 0, index = 0; + + for (;;) { + const char *const unused = memchr(&used[i], 0, n-i); + if (!unused) { + if (!index) break; + i = p[--index]; /* pop index */ + used[i++] = 0; /* index unused */ + } + else { + i = unused - used; p[index] = i; + used[i] = 1; /* mark index used */ + ++index; if (index < r-1) { /* if not done yet */ - used[i] = 1; /* mark index used */ - permute0(n, r, p, index+1, /* recurse */ - used, values); - used[i] = 0; /* index unused */ + p[index] = i = 0; + continue; } - else { - /* We have a complete permutation of array indexes */ - /* Build a ruby array of the corresponding values */ - /* And yield it to the associated block */ - VALUE result = rb_ary_new2(r); - VALUE *result_array = RARRAY_PTR(result); - const VALUE *values_array = RARRAY_PTR(values); - - for (j = 0; j < r; j++) result_array[j] = values_array[p[j]]; - ARY_SET_LEN(result, r); - rb_yield(result); - if (RBASIC(values)->klass) { + for (i = 0; i < n; ++i) { + if (used[i]) continue; + p[index] = i; + if (!yield_indexed_values(values, r, p)) { rb_raise(rb_eRuntimeError, "permute reentered"); } } + i = p[--index]; /* pop index */ + used[i] = 0; /* index unused */ + p[index] = ++i; } } } @@ -4826,23 +4980,42 @@ rb_ary_permutation(int argc, VALUE *argv, VALUE ary) } } else { /* this is the general case */ - volatile VALUE t0 = tmpbuf(n,sizeof(long)); - long *p = (long*)RSTRING_PTR(t0); - volatile VALUE t1 = tmpbuf(n,sizeof(char)); - char *used = (char*)RSTRING_PTR(t1); + volatile VALUE t0; + long *p = ALLOCV_N(long, t0, r+roomof(n, sizeof(long))); + char *used = (char*)(p + r); VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */ RBASIC_CLEAR_CLASS(ary0); MEMZERO(used, char, n); /* initialize array */ - permute0(n, r, p, 0, used, ary0); /* compute and yield permutations */ - tmpbuf_discard(t0); - tmpbuf_discard(t1); + permute0(n, r, p, used, ary0); /* compute and yield permutations */ + ALLOCV_END(t0); RBASIC_SET_CLASS_RAW(ary0, rb_cArray); } return ary; } +static void +combinate0(const long len, const long n, long *const stack, const VALUE values) +{ + long lev = 0; + + MEMZERO(stack+1, long, n); + stack[0] = -1; + for (;;) { + for (lev++; lev < n; lev++) { + stack[lev+1] = stack[lev]+1; + } + if (!yield_indexed_values(values, n, stack+1)) { + rb_raise(rb_eRuntimeError, "combination reentered"); + } + do { + if (lev == 0) return; + stack[lev--]++; + } while (stack[lev+1]+n == len+lev+1); + } +} + static VALUE rb_ary_combination_size(VALUE ary, VALUE args, VALUE eobj) { @@ -4880,7 +5053,7 @@ rb_ary_combination_size(VALUE ary, VALUE args, VALUE eobj) static VALUE rb_ary_combination(VALUE ary, VALUE num) { - long n, i, len; + long i, n, len; n = NUM2LONG(num); RETURN_SIZED_ENUMERATOR(ary, 1, &num, rb_ary_combination_size); @@ -4892,42 +5065,25 @@ rb_ary_combination(VALUE ary, VALUE num) rb_yield(rb_ary_new2(0)); } else if (n == 1) { - for (i = 0; i < len; i++) { + for (i = 0; i < RARRAY_LEN(ary); i++) { rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i))); } } else { - volatile VALUE t0 = tmpbuf(n+1, sizeof(long)); - long *stack = (long*)RSTRING_PTR(t0); - volatile VALUE cc = tmpary(n); - VALUE *chosen = RARRAY_PTR(cc); - long lev = 0; - - MEMZERO(stack, long, n); - stack[0] = -1; - for (;;) { - chosen[lev] = RARRAY_AREF(ary, stack[lev+1]); - for (lev++; lev < n; lev++) { - chosen[lev] = RARRAY_AREF(ary, stack[lev+1] = stack[lev]+1); - } - rb_yield(rb_ary_new4(n, chosen)); - if (RBASIC(t0)->klass) { - rb_raise(rb_eRuntimeError, "combination reentered"); - } - do { - if (lev == 0) goto done; - stack[lev--]++; - } while (stack[lev+1]+n == len+lev+1); - } - done: - tmpbuf_discard(t0); - tmpary_discard(cc); + VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */ + volatile VALUE t0; + long *stack = ALLOCV_N(long, t0, n+1); + + RBASIC_CLEAR_CLASS(ary0); + combinate0(len, n, stack, ary0); + ALLOCV_END(t0); + RBASIC_SET_CLASS_RAW(ary0, rb_cArray); } return ary; } /* - * Recursively compute repeated permutations of +r+ elements of the set + * Compute repeated permutations of +r+ elements of the set * <code>[0..n-1]</code>. * * When we have a complete repeated permutation of array indexes, copy the @@ -4936,33 +5092,28 @@ rb_ary_combination(VALUE ary, VALUE num) * n: the size of the set * r: the number of elements in each permutation * p: the array (of size r) that we're filling in - * index: what index we're filling in now * values: the Ruby array that holds the actual values to permute */ static void -rpermute0(long n, long r, long *p, long index, VALUE values) +rpermute0(const long n, const long r, long *const p, const VALUE values) { - long i, j; - for (i = 0; i < n; i++) { - p[index] = i; - if (index < r-1) { /* if not done yet */ - rpermute0(n, r, p, index+1, values); /* recurse */ + long i = 0, index = 0; + + p[index] = i; + for (;;) { + if (++index < r-1) { + p[index] = i = 0; + continue; } - else { - /* We have a complete permutation of array indexes */ - /* Build a ruby array of the corresponding values */ - /* And yield it to the associated block */ - VALUE result = rb_ary_new2(r); - VALUE *result_array = RARRAY_PTR(result); - const VALUE *values_array = RARRAY_PTR(values); - - for (j = 0; j < r; j++) result_array[j] = values_array[p[j]]; - ARY_SET_LEN(result, r); - rb_yield(result); - if (RBASIC(values)->klass) { + for (i = 0; i < n; ++i) { + p[index] = i; + if (!yield_indexed_values(values, r, p)) { rb_raise(rb_eRuntimeError, "repeated permute reentered"); } } + do { + if (index <= 0) return; + } while ((i = ++p[--index]) >= n); } } @@ -5025,39 +5176,38 @@ rb_ary_repeated_permutation(VALUE ary, VALUE num) } } else { /* this is the general case */ - volatile VALUE t0 = tmpbuf(r, sizeof(long)); - long *p = (long*)RSTRING_PTR(t0); + volatile VALUE t0; + long *p = ALLOCV_N(long, t0, r); VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */ RBASIC_CLEAR_CLASS(ary0); - rpermute0(n, r, p, 0, ary0); /* compute and yield repeated permutations */ - tmpbuf_discard(t0); + rpermute0(n, r, p, ary0); /* compute and yield repeated permutations */ + ALLOCV_END(t0); RBASIC_SET_CLASS_RAW(ary0, rb_cArray); } return ary; } static void -rcombinate0(long n, long r, long *p, long index, long rest, VALUE values) +rcombinate0(const long n, const long r, long *const p, const long rest, const VALUE values) { - long j; - if (rest > 0) { - for (; index < n; ++index) { - p[r-rest] = index; - rcombinate0(n, r, p, index, rest-1, values); + long i = 0, index = 0; + + p[index] = i; + for (;;) { + if (++index < r-1) { + p[index] = i; + continue; } - } - else { - VALUE result = rb_ary_new2(r); - VALUE *result_array = RARRAY_PTR(result); - const VALUE *values_array = RARRAY_PTR(values); - - for (j = 0; j < r; ++j) result_array[j] = values_array[p[j]]; - ARY_SET_LEN(result, r); - rb_yield(result); - if (RBASIC(values)->klass) { - rb_raise(rb_eRuntimeError, "repeated combination reentered"); + for (; i < n; ++i) { + p[index] = i; + if (!yield_indexed_values(values, r, p)) { + rb_raise(rb_eRuntimeError, "repeated combination reentered"); + } } + do { + if (index <= 0) return; + } while ((i = ++p[--index]) >= n); } } @@ -5114,7 +5264,7 @@ rb_ary_repeated_combination(VALUE ary, VALUE num) rb_yield(rb_ary_new2(0)); } else if (n == 1) { - for (i = 0; i < len; i++) { + for (i = 0; i < RARRAY_LEN(ary); i++) { rb_yield(rb_ary_new3(1, RARRAY_AREF(ary, i))); } } @@ -5122,13 +5272,13 @@ rb_ary_repeated_combination(VALUE ary, VALUE num) /* yield nothing */ } else { - volatile VALUE t0 = tmpbuf(n, sizeof(long)); - long *p = (long*)RSTRING_PTR(t0); + volatile VALUE t0; + long *p = ALLOCV_N(long, t0, n); VALUE ary0 = ary_make_shared_copy(ary); /* private defensive copy of ary */ RBASIC_CLEAR_CLASS(ary0); - rcombinate0(len, n, p, 0, n, ary0); /* compute and yield repeated combinations */ - tmpbuf_discard(t0); + rcombinate0(len, n, p, n, ary0); /* compute and yield repeated combinations */ + ALLOCV_END(t0); RBASIC_SET_CLASS_RAW(ary0, rb_cArray); } return ary; @@ -5271,7 +5421,7 @@ rb_ary_take(VALUE obj, VALUE n) /* * call-seq: - * ary.take_while { |arr| block } -> new_ary + * ary.take_while { |obj| block } -> new_ary * ary.take_while -> Enumerator * * Passes elements to the block until the block returns +nil+ or +false+, then @@ -5330,7 +5480,7 @@ rb_ary_drop(VALUE ary, VALUE n) /* * call-seq: - * ary.drop_while { |arr| block } -> new_ary + * ary.drop_while { |obj| block } -> new_ary * ary.drop_while -> Enumerator * * Drops elements up to, but not including, the first element for which the @@ -5359,6 +5509,57 @@ rb_ary_drop_while(VALUE ary) } /* + * call-seq: + * ary.any? [{ |obj| block }] -> true or false + * + * See also Enumerable#any? + */ + +static VALUE +rb_ary_any_p(VALUE ary) +{ + long i, len = RARRAY_LEN(ary); + const VALUE *ptr = RARRAY_CONST_PTR(ary); + + if (!len) return Qfalse; + if (!rb_block_given_p()) { + for (i = 0; i < len; ++i) if (RTEST(ptr[i])) return Qtrue; + } + else { + for (i = 0; i < RARRAY_LEN(ary); ++i) { + if (RTEST(rb_yield(RARRAY_AREF(ary, i)))) return Qtrue; + } + } + return Qfalse; +} + +/* + * call-seq: + * ary.dig(idx, ...) -> object + * + * Extracts the nested value specified by the sequence of <i>idx</i> + * objects by calling +dig+ at each step, returning +nil+ if any + * intermediate step is +nil+. + * + * a = [[1, [2, 3]]] + * + * a.dig(0, 1, 1) #=> 3 + * a.dig(1, 2, 3) #=> nil + * a.dig(0, 0, 0) #=> NoMethodError, undefined method `dig' for 1:Fixnum + * [42, {foo: :bar}].dig(1, :foo) #=> :bar + */ + +VALUE +rb_ary_dig(int argc, VALUE *argv, VALUE self) +{ + rb_check_arity(argc, 1, UNLIMITED_ARGUMENTS); + self = rb_ary_at(self, *argv); + if (!--argc) return self; + ++argv; + return rb_obj_dig(argc, argv, self, Qnil); +} + +/* * Arrays are ordered, integer-indexed collections of any object. * * Array indexing starts at 0, as in C or Java. A negative index is assumed @@ -5391,7 +5592,8 @@ rb_ary_drop_while(VALUE ary) * This method is safe to use with mutable objects such as hashes, strings or * other arrays: * - * Array.new(4) { Hash.new } #=> [{}, {}, {}, {}] + * Array.new(4) { Hash.new } #=> [{}, {}, {}, {}] + * Array.new(4) {|i| i.to_s } #=> ["0", "1", "2", "3"] * * This is also a quick way to build up multi-dimensional arrays: * @@ -5707,6 +5909,9 @@ Init_Array(void) rb_define_method(rb_cArray, "drop", rb_ary_drop, 1); rb_define_method(rb_cArray, "drop_while", rb_ary_drop_while, 0); rb_define_method(rb_cArray, "bsearch", rb_ary_bsearch, 0); + rb_define_method(rb_cArray, "bsearch_index", rb_ary_bsearch_index, 0); + rb_define_method(rb_cArray, "any?", rb_ary_any_p, 0); + rb_define_method(rb_cArray, "dig", rb_ary_dig, -1); id_cmp = rb_intern("<=>"); id_random = rb_intern("random"); |