Add Range#reverse_each implementation for performance

1 files changed, 134 insertions, 0 deletions

diff --git a/range.c b/range.c
index e57ffef7e5..867c96336a 100644
--- a/range.c
+++ b/range.c
@@ -1024,6 +1024,139 @@ range_each(VALUE range)
     return range;
 }
 
+RBIMPL_ATTR_NORETURN()
+static void
+range_reverse_each_bignum_beginless(VALUE end)
+{
+    RUBY_ASSERT(RBIGNUM_NEGATIVE_P(end));
+
+    for (;; end = rb_big_minus(end, INT2FIX(1))) {
+        rb_yield(end);
+    }
+    UNREACHABLE;
+}
+
+static void
+range_reverse_each_bignum(VALUE beg, VALUE end)
+{
+    RUBY_ASSERT(RBIGNUM_POSITIVE_P(beg) == RBIGNUM_POSITIVE_P(end));
+
+    VALUE c;
+    while ((c = rb_big_cmp(beg, end)) != INT2FIX(1)) {
+        rb_yield(end);
+        if (c == INT2FIX(0)) break;
+        end = rb_big_minus(end, INT2FIX(1));
+    }
+}
+
+static void
+range_reverse_each_positive_bignum_section(VALUE beg, VALUE end)
+{
+    RUBY_ASSERT(!NIL_P(end));
+
+    if (FIXNUM_P(end) || RBIGNUM_NEGATIVE_P(end)) return;
+
+    if (NIL_P(beg) || FIXNUM_P(beg) || RBIGNUM_NEGATIVE_P(beg)) {
+        beg = LONG2NUM(FIXNUM_MAX + 1);
+    }
+
+    range_reverse_each_bignum(beg, end);
+}
+
+static void
+range_reverse_each_fixnum_section(VALUE beg, VALUE end)
+{
+    RUBY_ASSERT(!NIL_P(end));
+
+    if (!FIXNUM_P(beg)) {
+        if (!NIL_P(beg) && RBIGNUM_POSITIVE_P(beg)) return;
+
+        beg = LONG2FIX(FIXNUM_MIN);
+    }
+
+    if (!FIXNUM_P(end)) {
+        if (RBIGNUM_NEGATIVE_P(end)) return;
+
+        end = LONG2FIX(FIXNUM_MAX);
+    }
+
+    long b = FIX2LONG(beg);
+    long e = FIX2LONG(end);
+    for (long i = e; i >= b; --i) {
+        rb_yield(LONG2FIX(i));
+    }
+}
+
+static void
+range_reverse_each_negative_bignum_section(VALUE beg, VALUE end)
+{
+    RUBY_ASSERT(!NIL_P(end));
+
+    if (FIXNUM_P(end) || RBIGNUM_POSITIVE_P(end)) {
+        end = LONG2NUM(FIXNUM_MIN - 1);
+    }
+
+    if (NIL_P(beg)) {
+        range_reverse_each_bignum_beginless(end);
+    }
+
+    if (FIXNUM_P(beg) || RBIGNUM_POSITIVE_P(beg)) return;
+
+    range_reverse_each_bignum(beg, end);
+}
+
+/*
+ *  call-seq:
+ *    reverse_each {|element| ... } -> self
+ *    reverse_each                  -> an_enumerator
+ *
+ *  With a block given, passes each element of +self+ to the block in reverse order:
+ *
+ *    a = []
+ *    (1..4).reverse_each {|element| a.push(element) } # => 1..4
+ *    a # => [4, 3, 2, 1]
+ *
+ *    a = []
+ *    (1...4).reverse_each {|element| a.push(element) } # => 1...4
+ *    a # => [3, 2, 1]
+ *
+ *  With no block given, returns an enumerator.
+ *
+ */
+
+static VALUE
+range_reverse_each(VALUE range)
+{
+    RETURN_SIZED_ENUMERATOR(range, 0, 0, range_enum_size);
+
+    VALUE beg = RANGE_BEG(range);
+    VALUE end = RANGE_END(range);
+    int excl = EXCL(range);
+
+    if (FIXNUM_P(beg) && FIXNUM_P(end)) {
+        if (excl) {
+            if (end == LONG2FIX(FIXNUM_MIN)) return range;
+
+            end = rb_int_minus(end, INT2FIX(1));
+        }
+
+        range_reverse_each_fixnum_section(beg, end);
+    }
+    else if ((NIL_P(beg) || RB_INTEGER_TYPE_P(beg)) && RB_INTEGER_TYPE_P(end)) {
+        if (excl) {
+            end = rb_int_minus(end, INT2FIX(1));
+        }
+        range_reverse_each_positive_bignum_section(beg, end);
+        range_reverse_each_fixnum_section(beg, end);
+        range_reverse_each_negative_bignum_section(beg, end);
+    }
+    else {
+        return rb_call_super(0, NULL);
+    }
+
+    return range;
+}
+
 /*
  *  call-seq:
  *    self.begin -> object
@@ -2529,6 +2662,7 @@ Init_Range(void)
     rb_define_method(rb_cRange, "each", range_each, 0);
     rb_define_method(rb_cRange, "step", range_step, -1);
     rb_define_method(rb_cRange, "%", range_percent_step, 1);
+    rb_define_method(rb_cRange, "reverse_each", range_reverse_each, 0);
     rb_define_method(rb_cRange, "bsearch", range_bsearch, 0);
     rb_define_method(rb_cRange, "begin", range_begin, 0);
     rb_define_method(rb_cRange, "end", range_end, 0);