array.c

/**********************************************************************

  array.c -

  $Author$
  created at: Fri Aug  6 09:46:12 JST 1993

  Copyright (C) 1993-2007 Yukihiro Matsumoto
  Copyright (C) 2000  Network Applied Communication Laboratory, Inc.
  Copyright (C) 2000  Information-technology Promotion Agency, Japan

**********************************************************************/

#include "internal.h"
#include "ruby/util.h"
#include "ruby/st.h"
#include "probes.h"
#include "id.h"

#ifndef ARRAY_DEBUG
# define NDEBUG
#endif
#include "ruby_assert.h"

VALUE rb_cArray;

static ID id_cmp, id_div, id_power;

#define ARY_DEFAULT_SIZE 16
#define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE))

# define ARY_SHARED_P(ary) \
    (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
     FL_TEST((ary),ELTS_SHARED)!=0)
# define ARY_EMBED_P(ary) \
    (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
     FL_TEST((ary), RARRAY_EMBED_FLAG)!=0)

#define ARY_HEAP_PTR(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.ptr)
#define ARY_HEAP_LEN(a) (assert(!ARY_EMBED_P(a)), RARRAY(a)->as.heap.len)
#define ARY_EMBED_PTR(a) (assert(ARY_EMBED_P(a)), RARRAY(a)->as.ary)
#define ARY_EMBED_LEN(a) \
    (assert(ARY_EMBED_P(a)), \
     (long)((RBASIC(a)->flags >> RARRAY_EMBED_LEN_SHIFT) & \
	 (RARRAY_EMBED_LEN_MASK >> RARRAY_EMBED_LEN_SHIFT)))
#define ARY_HEAP_SIZE(a) (assert(!ARY_EMBED_P(a)), assert(ARY_OWNS_HEAP_P(a)), RARRAY(a)->as.heap.aux.capa * sizeof(VALUE))

#define ARY_OWNS_HEAP_P(a) (!FL_TEST((a), ELTS_SHARED|RARRAY_EMBED_FLAG))
#define FL_SET_EMBED(a) do { \
    assert(!ARY_SHARED_P(a)); \
    FL_SET((a), RARRAY_EMBED_FLAG); \
} while (0)
#define FL_UNSET_EMBED(ary) FL_UNSET((ary), RARRAY_EMBED_FLAG|RARRAY_EMBED_LEN_MASK)
#define FL_SET_SHARED(ary) do { \
    assert(!ARY_EMBED_P(ary)); \
    FL_SET((ary), ELTS_SHARED); \
} while (0)
#define FL_UNSET_SHARED(ary) FL_UNSET((ary), ELTS_SHARED)

#define ARY_SET_PTR(ary, p) do { \
    assert(!ARY_EMBED_P(ary)); \
    assert(!OBJ_FROZEN(ary)); \
    RARRAY(ary)->as.heap.ptr = (p); \
} while (0)
#define ARY_SET_EMBED_LEN(ary, n) do { \
    long tmp_n = (n); \
    assert(ARY_EMBED_P(ary)); \
    assert(!OBJ_FROZEN(ary)); \
    RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK; \
    RBASIC(ary)->flags |= (tmp_n) << RARRAY_EMBED_LEN_SHIFT; \
} while (0)
#define ARY_SET_HEAP_LEN(ary, n) do { \
    assert(!ARY_EMBED_P(ary)); \
    RARRAY(ary)->as.heap.len = (n); \
} while (0)
#define ARY_SET_LEN(ary, n) do { \
    if (ARY_EMBED_P(ary)) { \
        ARY_SET_EMBED_LEN((ary), (n)); \
    } \
    else { \
        ARY_SET_HEAP_LEN((ary), (n)); \
    } \
    assert(RARRAY_LEN(ary) == (n)); \
} while (0)
#define ARY_INCREASE_PTR(ary, n) do  { \
    assert(!ARY_EMBED_P(ary)); \
    assert(!OBJ_FROZEN(ary)); \
    RARRAY(ary)->as.heap.ptr += (n); \
} while (0)
#define ARY_INCREASE_LEN(ary, n) do  { \
    assert(!OBJ_FROZEN(ary)); \
    if (ARY_EMBED_P(ary)) { \
        ARY_SET_EMBED_LEN((ary), RARRAY_LEN(ary)+(n)); \
    } \
    else { \
        RARRAY(ary)->as.heap.len += (n); \
    } \
} while (0)

#define ARY_CAPA(ary) (ARY_EMBED_P(ary) ? RARRAY_EMBED_LEN_MAX : \
		       ARY_SHARED_ROOT_P(ary) ? RARRAY_LEN(ary) : RARRAY(ary)->as.heap.aux.capa)
#define ARY_SET_CAPA(ary, n) do { \
    assert(!ARY_EMBED_P(ary)); \
    assert(!ARY_SHARED_P(ary)); \
    assert(!OBJ_FROZEN(ary)); \
    RARRAY(ary)->as.heap.aux.capa = (n); \
} while (0)

#define ARY_SHARED(ary) (assert(ARY_SHARED_P(ary)), RARRAY(ary)->as.heap.aux.shared)
#define ARY_SET_SHARED(ary, value) do { \
    const VALUE _ary_ = (ary); \
    const VALUE _value_ = (value); \
    assert(!ARY_EMBED_P(_ary_)); \
    assert(ARY_SHARED_P(_ary_)); \
    assert(ARY_SHARED_ROOT_P(_value_)); \
    RB_OBJ_WRITE(_ary_, &RARRAY(_ary_)->as.heap.aux.shared, _value_); \
} while (0)
#define RARRAY_SHARED_ROOT_FLAG FL_USER5
#define ARY_SHARED_ROOT_P(ary) (FL_TEST((ary), RARRAY_SHARED_ROOT_FLAG))
#define ARY_SHARED_NUM(ary) \
    (assert(ARY_SHARED_ROOT_P(ary)), RARRAY(ary)->as.heap.aux.capa)
#define ARY_SHARED_OCCUPIED(ary) (ARY_SHARED_NUM(ary) == 1)
#define ARY_SET_SHARED_NUM(ary, value) do { \
    assert(ARY_SHARED_ROOT_P(ary)); \
    RARRAY(ary)->as.heap.aux.capa = (value); \
} while (0)
#define FL_SET_SHARED_ROOT(ary) do { \
    assert(!ARY_EMBED_P(ary)); \
    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)
{
    assert(RARRAY_LEN(ary) <= capacity);
    assert(!OBJ_FROZEN(ary));
    assert(!ARY_SHARED_P(ary));
    if (capacity > RARRAY_EMBED_LEN_MAX) {
        if (ARY_EMBED_P(ary)) {
            long len = ARY_EMBED_LEN(ary);
            VALUE *ptr = ALLOC_N(VALUE, (capacity));
            MEMCPY(ptr, ARY_EMBED_PTR(ary), VALUE, len);
            FL_UNSET_EMBED(ary);
            ARY_SET_PTR(ary, ptr);
            ARY_SET_HEAP_LEN(ary, len);
        }
        else {
	    SIZED_REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, capacity, RARRAY(ary)->as.heap.aux.capa);
        }
        ARY_SET_CAPA(ary, (capacity));
    }
    else {
        if (!ARY_EMBED_P(ary)) {
            long len = RARRAY_LEN(ary);
	    const VALUE *ptr = RARRAY_CONST_PTR(ary);

	    if (len > capacity) len = capacity;
            MEMCPY((VALUE *)RARRAY(ary)->as.ary, ptr, VALUE, len);
            FL_SET_EMBED(ary);
            ARY_SET_LEN(ary, len);
	    ruby_xfree((VALUE *)ptr);
        }
    }
}

static inline void
ary_shrink_capa(VALUE ary)
{
    long capacity = ARY_HEAP_LEN(ary);
    long old_capa = RARRAY(ary)->as.heap.aux.capa;
    assert(!ARY_SHARED_P(ary));
    assert(old_capa >= capacity);
    if (old_capa > capacity)
	REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, capacity);
}

static void
ary_double_capa(VALUE ary, long min)
{
    long new_capa = ARY_CAPA(ary) / 2;

    if (new_capa < ARY_DEFAULT_SIZE) {
	new_capa = ARY_DEFAULT_SIZE;
    }
    if (new_capa >= ARY_MAX_SIZE - min) {
	new_capa = (ARY_MAX_SIZE - min) / 2;
    }
    new_capa += min;
    ary_resize_capa(ary, new_capa);
}

static void
rb_ary_decrement_share(VALUE shared)
{
    if (shared) {
	long num = ARY_SHARED_NUM(shared) - 1;
	if (num == 0) {
	    rb_ary_free(shared);
	    rb_gc_force_recycle(shared);
	}
	else if (num > 0) {
	    ARY_SET_SHARED_NUM(shared, num);
	}
    }
}

static void
rb_ary_unshare(VALUE ary)
{
    VALUE shared = RARRAY(ary)->as.heap.aux.shared;
    rb_ary_decrement_share(shared);
    FL_UNSET_SHARED(ary);
}

static inline void
rb_ary_unshare_safe(VALUE ary)
{
    if (ARY_SHARED_P(ary) && !ARY_EMBED_P(ary)) {
	rb_ary_unshare(ary);
    }
}

static VALUE
rb_ary_increment_share(VALUE shared)
{
    long num = ARY_SHARED_NUM(shared);
    if (num >= 0) {
	ARY_SET_SHARED_NUM(shared, num + 1);
    }
    return shared;
}

static void
rb_ary_set_shared(VALUE ary, VALUE shared)
{
    rb_ary_increment_share(shared);
    FL_SET_SHARED(ary);
    ARY_SET_SHARED(ary, shared);
}

static inline void
rb_ary_modify_check(VALUE ary)
{
    rb_check_frozen(ary);
}

void
rb_ary_modify(VALUE ary)
{
    rb_ary_modify_check(ary);
    if (ARY_SHARED_P(ary)) {
	long shared_len, len = RARRAY_LEN(ary);
	VALUE shared = ARY_SHARED(ary);
        if (len <= RARRAY_EMBED_LEN_MAX) {
	    const VALUE *ptr = ARY_HEAP_PTR(ary);
            FL_UNSET_SHARED(ary);
            FL_SET_EMBED(ary);
	    MEMCPY((VALUE *)ARY_EMBED_PTR(ary), ptr, VALUE, len);
            rb_ary_decrement_share(shared);
            ARY_SET_EMBED_LEN(ary, len);
        }
	else if (ARY_SHARED_OCCUPIED(shared) && len > ((shared_len = RARRAY_LEN(shared))>>1)) {
	    long shift = RARRAY_CONST_PTR(ary) - RARRAY_CONST_PTR(shared);
	    FL_UNSET_SHARED(ary);
	    ARY_SET_PTR(ary, RARRAY_CONST_PTR(shared));
	    ARY_SET_CAPA(ary, shared_len);
	    RARRAY_PTR_USE(ary, ptr, {
		MEMMOVE(ptr, ptr+shift, VALUE, len);
	    });
	    FL_SET_EMBED(shared);
	    rb_ary_decrement_share(shared);
	}
        else {
            VALUE *ptr = ALLOC_N(VALUE, len);
            MEMCPY(ptr, RARRAY_CONST_PTR(ary), VALUE, len);
            rb_ary_unshare(ary);
            ARY_SET_CAPA(ary, len);
            ARY_SET_PTR(ary, ptr);
        }

	rb_gc_writebarrier_remember(ary);
    }
}

static VALUE
ary_ensure_room_for_push(VALUE ary, long 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 */
		    rb_ary_modify(ary);
		    capa = ARY_CAPA(ary);
		    if (new_len > capa - (capa >> 6)) {
			ary_double_capa(ary, new_len);
		    }
		    return ary;
		}
	    }
	}
    }
    rb_ary_modify(ary);
    capa = ARY_CAPA(ary);
    if (new_len > capa) {
	ary_double_capa(ary, new_len);
    }

    return ary;
}

/*
 *  call-seq:
 *      ary.freeze -> ary
 *
 *  Calls Object#freeze on +ary+ to prevent any further
 *  modification. A RuntimeError will be raised if a modification
 *  attempt is made.
 *
 */

VALUE
rb_ary_freeze(VALUE ary)
{
    return rb_obj_freeze(ary);
}

/*
 *  call-seq:
 *     ary.frozen?  -> true or false
 *
 *  Return +true+ if this array is frozen (or temporarily frozen
 *  while being sorted). See also Object#frozen?
 */

static VALUE
rb_ary_frozen_p(VALUE ary)
{
    if (OBJ_FROZEN(ary)) return Qtrue;
    return Qfalse;
}

/* This can be used to take a snapshot of an array (with
   e.g. rb_ary_replace) and check later whether the array has been
   modified from the snapshot.  The snapshot is cheap, though if
   something does modify the array it will pay the cost of copying
   it.  If Array#pop or Array#shift has been called, the array will
   be still shared with the snapshot, but the array length will
   differ. */
VALUE
rb_ary_shared_with_p(VALUE ary1, VALUE ary2)
{
    if (!ARY_EMBED_P(ary1) && ARY_SHARED_P(ary1) &&
	!ARY_EMBED_P(ary2) && ARY_SHARED_P(ary2) &&
	RARRAY(ary1)->as.heap.aux.shared == RARRAY(ary2)->as.heap.aux.shared &&
	RARRAY(ary1)->as.heap.len == RARRAY(ary2)->as.heap.len) {
	return Qtrue;
    }
    return Qfalse;
}

static VALUE
ary_alloc(VALUE klass)
{
    NEWOBJ_OF(ary, struct RArray, klass, T_ARRAY | RARRAY_EMBED_FLAG | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0));
    /* Created array is:
     *   FL_SET_EMBED((VALUE)ary);
     *   ARY_SET_EMBED_LEN((VALUE)ary, 0);
     */
    return (VALUE)ary;
}

static VALUE
empty_ary_alloc(VALUE klass)
{
    RUBY_DTRACE_CREATE_HOOK(ARRAY, 0);
    return ary_alloc(klass);
}

static VALUE
ary_new(VALUE klass, long capa)
{
    VALUE ary,*ptr;

    if (capa < 0) {
	rb_raise(rb_eArgError, "negative array size (or size too big)");
    }
    if (capa > ARY_MAX_SIZE) {
	rb_raise(rb_eArgError, "array size too big");
    }

    RUBY_DTRACE_CREATE_HOOK(ARRAY, capa);

    ary = ary_alloc(klass);
    if (capa > RARRAY_EMBED_LEN_MAX) {
	ptr = ALLOC_N(VALUE, capa);
        FL_UNSET_EMBED(ary);
        ARY_SET_PTR(ary, ptr);
        ARY_SET_CAPA(ary, capa);
        ARY_SET_HEAP_LEN(ary, 0);
    }

    return ary;
}

VALUE
rb_ary_new_capa(long capa)
{
    return ary_new(rb_cArray, capa);
}

VALUE
rb_ary_new(void)
{
    return rb_ary_new2(RARRAY_EMBED_LEN_MAX);
}

VALUE
(rb_ary_new_from_args)(long n, ...)
{
    va_list ar;
    VALUE ary;
    long i;

    ary = rb_ary_new2(n);

    va_start(ar, n);
    for (i=0; i<n; i++) {
	ARY_SET(ary, i, va_arg(ar, VALUE));
    }
    va_end(ar);

    ARY_SET_LEN(ary, n);
    return ary;
}

VALUE
rb_ary_new_from_values(long n, const VALUE *elts)
{
    VALUE ary;

    ary = rb_ary_new2(n);
    if (n > 0 && elts) {
	ary_memcpy(ary, 0, n, elts);
	ARY_SET_LEN(ary, n);
    }

    return ary;
}

VALUE
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)
{
    if (ARY_OWNS_HEAP_P(ary)) {
	ruby_sized_xfree((void *)ARY_HEAP_PTR(ary), ARY_HEAP_SIZE(ary));
    }
}

RUBY_FUNC_EXPORTED size_t
rb_ary_memsize(VALUE ary)
{
    if (ARY_OWNS_HEAP_P(ary)) {
	return RARRAY(ary)->as.heap.aux.capa * sizeof(VALUE);
    }
    else {
	return 0;
    }
}

static inline void
ary_discard(VALUE ary)
{
    rb_ary_free(ary);
    RBASIC(ary)->flags |= RARRAY_EMBED_FLAG;
    RBASIC(ary)->flags &= ~RARRAY_EMBED_LEN_MASK;
}

static VALUE
ary_make_shared(VALUE ary)
{
    assert(!ARY_EMBED_P(ary));
    if (ARY_SHARED_P(ary)) {
	return ARY_SHARED(ary);
    }
    else if (ARY_SHARED_ROOT_P(ary)) {
	return ary;
    }
    else if (OBJ_FROZEN(ary)) {
	ary_shrink_capa(ary);
	FL_SET_SHARED_ROOT(ary);
	ARY_SET_SHARED_NUM(ary, 1);
	return ary;
    }
    else {
	long capa = ARY_CAPA(ary), len = RARRAY_LEN(ary);
	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);
	ARY_SET_PTR((VALUE)shared, RARRAY_CONST_PTR(ary));
	ary_mem_clear((VALUE)shared, len, capa - len);
	FL_SET_SHARED_ROOT(shared);
	ARY_SET_SHARED_NUM((VALUE)shared, 1);
	FL_SET_SHARED(ary);
	ARY_SET_SHARED(ary, (VALUE)shared);
	OBJ_FREEZE(shared);
	return (VALUE)shared;
    }
}

static VALUE
ary_make_substitution(VALUE ary)
{
    long len = RARRAY_LEN(ary);

    if (len <= RARRAY_EMBED_LEN_MAX) {
	VALUE subst = rb_ary_new2(len);
	ary_memcpy(subst, 0, len, RARRAY_CONST_PTR(ary));
        ARY_SET_EMBED_LEN(subst, len);
        return subst;
    }
    else {
        return rb_ary_increment_share(ary_make_shared(ary));
    }
}

VALUE
rb_assoc_new(VALUE car, VALUE cdr)
{
    return rb_ary_new3(2, car, cdr);
}

static VALUE
to_ary(VALUE ary)
{
    return rb_convert_type(ary, T_ARRAY, "Array", "to_ary");
}

VALUE
rb_check_array_type(VALUE ary)
{
    return rb_check_convert_type(ary, T_ARRAY, "Array", "to_ary");
}

/*
 *  call-seq:
 *     Array.try_convert(obj) -> array or nil
 *
 *  Tries to convert +obj+ into an array, using +to_ary+ method.  Returns the
 *  converted array or +nil+ if +obj+ cannot be converted for any reason.
 *  This method can be used to check if an argument is an array.
 *
 *     Array.try_convert([1])   #=> [1]
 *     Array.try_convert("1")   #=> nil
 *
 *     if tmp = Array.try_convert(arg)
 *       # the argument is an array
 *     elsif tmp = String.try_convert(arg)
 *       # the argument is a string
 *     end
 *
 */

static VALUE
rb_ary_s_try_convert(VALUE dummy, VALUE ary)
{
    return rb_check_array_type(ary);
}

/*
 *  call-seq:
 *     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 +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).
 *
 *    first_array = ["Matz", "Guido"]
 *
 *    second_array = Array.new(first_array) #=> ["Matz", "Guido"]
 *
 *    first_array.equal? second_array       #=> false
 *
 *  In the last form, an array of the given size is created.  Each element in
 *  this array is created by passing the element's index to the given block
 *  and storing the return value.
 *
 *    Array.new(3){ |index| index ** 2 }
 *    # => [0, 1, 4]
 *
 *  == Common gotchas
 *
 *  When sending the second parameter, the same object will be used as the
 *  value for all the array elements:
 *
 *     a = Array.new(2, Hash.new)
 *     # => [{}, {}]
 *
 *     a[0]['cat'] = 'feline'
 *     a # => [{"cat"=>"feline"}, {"cat"=>"feline"}]
 *
 *     a[1]['cat'] = 'Felix'
 *     a # => [{"cat"=>"Felix"}, {"cat"=>"Felix"}]
 *
 *  Since all the Array elements store the same hash, changes to one of them
 *  will affect them all.
 *
 *  If multiple copies are what you want, you should use the block
 *  version which uses the result of that block each time an element
 *  of the array needs to be initialized:
 *
 *     a = Array.new(2) { Hash.new }
 *     a[0]['cat'] = 'feline'
 *     a # => [{"cat"=>"feline"}, {}]
 *
 */

static VALUE
rb_ary_initialize(int argc, VALUE *argv, VALUE ary)
{
    long len;
    VALUE size, val;

    rb_ary_modify(ary);
    if (argc == 0) {
	if (ARY_OWNS_HEAP_P(ary) && RARRAY_CONST_PTR(ary) != 0) {
	    ruby_sized_xfree((void *)RARRAY_CONST_PTR(ary), ARY_HEAP_SIZE(ary));
	}
        rb_ary_unshare_safe(ary);
        FL_SET_EMBED(ary);
	ARY_SET_EMBED_LEN(ary, 0);
	if (rb_block_given_p()) {
	    rb_warning("given block not used");
	}
	return ary;
    }
    rb_scan_args(argc, argv, "02", &size, &val);
    if (argc == 1 && !FIXNUM_P(size)) {
	val = rb_check_array_type(size);
	if (!NIL_P(val)) {
	    rb_ary_replace(ary, val);
	    return 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()) {
	long i;

	if (argc == 2) {
	    rb_warn("block supersedes default value argument");
	}
	for (i=0; i<len; i++) {
	    rb_ary_store(ary, i, rb_yield(LONG2NUM(i)));
	    ARY_SET_LEN(ary, i + 1);
	}
    }
    else {
	ary_memfill(ary, 0, len, val);
	ARY_SET_LEN(ary, len);
    }
    return ary;
}

/*
 * Returns a new array populated with the given objects.
 *
 *   Array.[]( 1, 'a', /^A/ ) # => [1, "a", /^A/]
 *   Array[ 1, 'a', /^A/ ]    # => [1, "a", /^A/]
 *   [ 1, 'a', /^A/ ]         # => [1, "a", /^A/]
 */

static VALUE
rb_ary_s_create(int argc, VALUE *argv, VALUE klass)
{
    VALUE ary = ary_new(klass, argc);
    if (argc > 0 && argv) {
        ary_memcpy(ary, 0, argc, argv);
        ARY_SET_LEN(ary, argc);
    }

    return ary;
}

void
rb_ary_store(VALUE ary, long idx, VALUE val)
{
    long len = RARRAY_LEN(ary);

    if (idx < 0) {
	idx += len;
	if (idx < 0) {
	    rb_raise(rb_eIndexError, "index %ld too small for array; minimum: %ld",
		     idx - len, -len);
	}
    }
    else if (idx >= ARY_MAX_SIZE) {
	rb_raise(rb_eIndexError, "index %ld too big", idx);
    }

    rb_ary_modify(ary);
    if (idx >= ARY_CAPA(ary)) {
	ary_double_capa(ary, idx);
    }
    if (idx > len) {
	ary_mem_clear(ary, len, idx - len + 1);
    }

    if (idx >= len) {
	ARY_SET_LEN(ary, idx + 1);
    }
    ARY_SET(ary, idx, val);
}

static VALUE
ary_make_partial(VALUE ary, VALUE klass, long offset, long len)
{
    assert(offset >= 0);
    assert(len >= 0);
    assert(offset+len <= RARRAY_LEN(ary));

    if (len <= RARRAY_EMBED_LEN_MAX) {
        VALUE result = ary_alloc(klass);
	ary_memcpy(result, 0, len, RARRAY_CONST_PTR(ary) + offset);
        ARY_SET_EMBED_LEN(result, len);
        return result;
    }
    else {
        VALUE shared, result = ary_alloc(klass);
        FL_UNSET_EMBED(result);

        shared = ary_make_shared(ary);
        ARY_SET_PTR(result, RARRAY_CONST_PTR(ary));
        ARY_SET_LEN(result, RARRAY_LEN(ary));
        rb_ary_set_shared(result, shared);

        ARY_INCREASE_PTR(result, offset);
        ARY_SET_LEN(result, len);
        return result;
    }
}

static VALUE
ary_make_shared_copy(VALUE ary)
{
    return ary_make_partial(ary, rb_obj_class(ary), 0, RARRAY_LEN(ary));
}

enum ary_take_pos_flags
{
    ARY_TAKE_FIRST = 0,
    ARY_TAKE_LAST = 1
};

static VALUE
ary_take_first_or_last(int argc, const VALUE *argv, VALUE ary, enum ary_take_pos_flags last)
{
    VALUE nv;
    long n;
    long len;
    long offset = 0;

    rb_scan_args(argc, argv, "1", &nv);
    n = NUM2LONG(nv);
    len = RARRAY_LEN(ary);
    if (n > len) {
	n = len;
    }
    else if (n < 0) {
	rb_raise(rb_eArgError, "negative array size");
    }
    if (last) {
	offset = len - n;
    }
    return ary_make_partial(ary, rb_cArray, offset, n);
}

/*
 *  call-seq:
 *     ary << obj            -> ary
 *
 *  Append---Pushes the given object on to the end of this array. This
 *  expression returns the array itself, so several appends
 *  may be chained together.
 *
 *     [ 1, 2 ] << "c" << "d" << [ 3, 4 ]
 *             #=>  [ 1, 2, "c", "d", [ 3, 4 ] ]
 *
 */

VALUE
rb_ary_push(VALUE ary, VALUE item)
{
    long idx = RARRAY_LEN(ary);
    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 *argv, long len)
{
    long oldlen = RARRAY_LEN(ary);
    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;
}

/*
 *  call-seq:
 *     ary.push(obj, ... )   -> ary
 *
 *  Append --- Pushes the given object(s) on to the end of this array. This
 *  expression returns the array itself, so several appends
 *  may be chained together. See also Array#pop for the opposite
 *  effect.
 *
 *     a = [ "a", "b", "c" ]
 *     a.push("d", "e", "f")
 *             #=> ["a", "b", "c", "d", "e", "f"]
 *     [1, 2, 3].push(4).push(5)
 *             #=> [1, 2, 3, 4, 5]
 */

static VALUE
rb_ary_push_m(int argc, VALUE *argv, VALUE ary)
{
    return rb_ary_cat(ary, argv, argc);
}

VALUE
rb_ary_pop(VALUE ary)
{
    long n;
    rb_ary_modify_check(ary);
    n = RARRAY_LEN(ary);
    if (n == 0) return Qnil;
    if (ARY_OWNS_HEAP_P(ary) &&
	n * 3 < ARY_CAPA(ary) &&
	ARY_CAPA(ary) > ARY_DEFAULT_SIZE)
    {
	ary_resize_capa(ary, n * 2);
    }
    --n;
    ARY_SET_LEN(ary, n);
    return RARRAY_AREF(ary, n);
}

/*
 *  call-seq:
 *     ary.pop    -> obj or nil
 *     ary.pop(n) -> new_ary
 *
 *  Removes the last element from +self+ and returns it, or
 *  +nil+ if the array is empty.
 *
 *  If a number +n+ is given, returns an array of the last +n+ elements
 *  (or less) just like <code>array.slice!(-n, n)</code> does. See also
 *  Array#push for the opposite effect.
 *
 *     a = [ "a", "b", "c", "d" ]
 *     a.pop     #=> "d"
 *     a.pop(2)  #=> ["b", "c"]
 *     a         #=> ["a"]
 */

static VALUE
rb_ary_pop_m(int argc, VALUE *argv, VALUE ary)
{
    VALUE result;

    if (argc == 0) {
	return rb_ary_pop(ary);
    }

    rb_ary_modify_check(ary);
    result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_LAST);
    ARY_INCREASE_LEN(ary, -RARRAY_LEN(result));
    return result;
}

VALUE
rb_ary_shift(VALUE ary)