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 "ruby/encoding.h"
#include "ruby/util.h"
#include "ruby/st.h"
#include "probes.h"
#include "id.h"
#include "debug_counter.h"
#include "transient_heap.h"
#include "internal.h"

#if !ARRAY_DEBUG
# define NDEBUG
#endif
#include "ruby_assert.h"

VALUE rb_cArray;

/* for OPTIMIZED_CMP: */
#define id_cmp idCmp

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

static int
should_be_T_ARRAY(VALUE ary)
{
    return RB_TYPE_P(ary, T_ARRAY);
}

static int
should_not_be_shared_and_embedded(VALUE ary)
{
    return !FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG);
}

#define ARY_SHARED_P(ary) \
  (assert(should_be_T_ARRAY((VALUE)(ary))), \
   assert(should_not_be_shared_and_embedded((VALUE)ary)), \
   FL_TEST_RAW((ary),ELTS_SHARED)!=0)

#define ARY_EMBED_P(ary) \
  (assert(should_be_T_ARRAY((VALUE)(ary))), \
   assert(should_not_be_shared_and_embedded((VALUE)ary)), \
   FL_TEST_RAW((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_HEAP_CAPA(a) (assert(!ARY_EMBED_P(a)), assert(!ARY_SHARED_ROOT_P(a)), \
                          RARRAY(a)->as.heap.aux.capa)

#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)), ARY_CAPA(a) * sizeof(VALUE))

#define ARY_OWNS_HEAP_P(a) (assert(should_be_T_ARRAY((VALUE)(a))), \
                            !FL_TEST_RAW((a), ELTS_SHARED|RARRAY_EMBED_FLAG))

#define FL_SET_EMBED(a) do { \
    assert(!ARY_SHARED_P(a)); \
    FL_SET((a), RARRAY_EMBED_FLAG); \
    RARY_TRANSIENT_UNSET(a); \
    ary_verify(a); \
} 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) : ARY_HEAP_CAPA(ary))
#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_ROOT(ary) (assert(ARY_SHARED_P(ary)), RARRAY(ary)->as.heap.aux.shared_root)
#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_root, _value_); \
} while (0)
#define RARRAY_SHARED_ROOT_FLAG FL_USER5
#define ARY_SHARED_ROOT_P(ary) (assert(should_be_T_ARRAY((VALUE)(ary))), \
                                FL_TEST_RAW((ary), RARRAY_SHARED_ROOT_FLAG))
#define ARY_SHARED_ROOT_REFCNT(ary) \
    (assert(ARY_SHARED_ROOT_P(ary)), RARRAY(ary)->as.heap.aux.capa)
#define ARY_SHARED_ROOT_OCCUPIED(ary) (ARY_SHARED_ROOT_REFCNT(ary) == 1)
#define ARY_SET_SHARED_ROOT_REFCNT(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)); \
    assert(!RARRAY_TRANSIENT_P(ary)); \
    FL_SET((ary), RARRAY_SHARED_ROOT_FLAG); \
} while (0)

static inline void
ARY_SET(VALUE a, long i, VALUE v)
{
    assert(!ARY_SHARED_P(a));
    assert(!OBJ_FROZEN(a));

    RARRAY_ASET(a, i, v);
}
#undef RARRAY_ASET


#if ARRAY_DEBUG
#define ary_verify(ary) ary_verify_(ary, __FILE__, __LINE__)

static VALUE
ary_verify_(VALUE ary, const char *file, int line)
{
    assert(RB_TYPE_P(ary, T_ARRAY));

    if (FL_TEST(ary, ELTS_SHARED)) {
        VALUE root = RARRAY(ary)->as.heap.aux.shared_root;
        const VALUE *ptr = ARY_HEAP_PTR(ary);
        const VALUE *root_ptr = RARRAY_CONST_PTR_TRANSIENT(root);
        long len = ARY_HEAP_LEN(ary), root_len = RARRAY_LEN(root);
        assert(FL_TEST(root, RARRAY_SHARED_ROOT_FLAG));
        assert(root_ptr <= ptr && ptr + len <= root_ptr + root_len);
        ary_verify(root);
    }
    else if (ARY_EMBED_P(ary)) {
        assert(!RARRAY_TRANSIENT_P(ary));
        assert(!ARY_SHARED_P(ary));
        assert(RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX);
    }
    else {
#if 1
        const VALUE *ptr = RARRAY_CONST_PTR_TRANSIENT(ary);
        long i, len = RARRAY_LEN(ary);
        volatile VALUE v;
        if (len > 1) len = 1; /* check only HEAD */
        for (i=0; i<len; i++) {
            v = ptr[i]; /* access check */
        }
        v = v;
#endif
    }

    if (RARRAY_TRANSIENT_P(ary)) {
        assert(rb_transient_heap_managed_ptr_p(RARRAY_CONST_PTR_TRANSIENT(ary)));
    }

    rb_transient_heap_verify();

    return ary;
}

void
rb_ary_verify(VALUE ary)
{
    ary_verify(ary);
}
#else
#define ary_verify(ary) ((void)0)
#endif

VALUE *
rb_ary_ptr_use_start(VALUE ary)
{
#if ARRAY_DEBUG
    FL_SET_RAW(ary, RARRAY_PTR_IN_USE_FLAG);
#endif
    return (VALUE *)RARRAY_CONST_PTR_TRANSIENT(ary);
}

void
rb_ary_ptr_use_end(VALUE ary)
{
#if ARRAY_DEBUG
    FL_UNSET_RAW(ary, RARRAY_PTR_IN_USE_FLAG);
#endif
}

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_TRANSIENT(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_TRANSIENT(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)
{
    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_TRANSIENT(ary, ptr, {
            MEMCPY(ptr+beg, argv, VALUE, argc);
        });
    }
    else {
        int i;
        RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
            for (i=0; i<argc; i++) {
                RB_OBJ_WRITE(buff_owner_ary, &ptr[i+beg], argv[i]);
            }
        });
    }
}

static void
ary_memcpy(VALUE ary, long beg, long argc, const VALUE *argv)
{
    ary_memcpy0(ary, beg, argc, argv, ary);
}

static VALUE *
ary_heap_alloc(VALUE ary, size_t capa)
{
    VALUE *ptr = rb_transient_heap_alloc(ary, sizeof(VALUE) * capa);

    if (ptr != NULL) {
        RARY_TRANSIENT_SET(ary);
    }
    else {
        RARY_TRANSIENT_UNSET(ary);
        ptr = ALLOC_N(VALUE, capa);
    }

    return ptr;
}

static void
ary_heap_free_ptr(VALUE ary, const VALUE *ptr, long size)
{
    if (RARRAY_TRANSIENT_P(ary)) {
        /* ignore it */
    }
    else {
        ruby_sized_xfree((void *)ptr, size);
    }
}

static void
ary_heap_free(VALUE ary)
{
    if (RARRAY_TRANSIENT_P(ary)) {
        RARY_TRANSIENT_UNSET(ary);
    }
    else {
        ary_heap_free_ptr(ary, ARY_HEAP_PTR(ary), ARY_HEAP_SIZE(ary));
    }
}

static void
ary_heap_realloc(VALUE ary, size_t new_capa)
{
    size_t old_capa = ARY_HEAP_CAPA(ary);

    if (RARRAY_TRANSIENT_P(ary)) {
        if (new_capa <= old_capa) {
            /* do nothing */
        }
        else {
            VALUE *new_ptr = rb_transient_heap_alloc(ary, sizeof(VALUE) * new_capa);

            if (new_ptr == NULL) {
                new_ptr = ALLOC_N(VALUE, new_capa);
                RARY_TRANSIENT_UNSET(ary);
            }

            MEMCPY(new_ptr, ARY_HEAP_PTR(ary), VALUE, old_capa);
            ARY_SET_PTR(ary, new_ptr);
        }
    }
    else {
        SIZED_REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, new_capa, old_capa);
    }
    ary_verify(ary);
}

#if USE_TRANSIENT_HEAP
static inline void
rb_ary_transient_heap_evacuate_(VALUE ary, int transient, int promote)
{
    if (transient) {
        VALUE *new_ptr;
        const VALUE *old_ptr = ARY_HEAP_PTR(ary);
        long capa = ARY_HEAP_CAPA(ary);
        long len  = ARY_HEAP_LEN(ary);

        if (ARY_SHARED_ROOT_P(ary)) {
            capa = len;
        }

        assert(ARY_OWNS_HEAP_P(ary));
        assert(RARRAY_TRANSIENT_P(ary));
        assert(!ARY_PTR_USING_P(ary));

        if (promote) {
            new_ptr = ALLOC_N(VALUE, capa);
            RARY_TRANSIENT_UNSET(ary);
        }
        else {
            new_ptr = ary_heap_alloc(ary, capa);
        }

        MEMCPY(new_ptr, old_ptr, VALUE, capa);
        /* do not use ARY_SET_PTR() because they assert !frozen */
        RARRAY(ary)->as.heap.ptr = new_ptr;
    }

    ary_verify(ary);
}

void
rb_ary_transient_heap_evacuate(VALUE ary, int promote)
{
    rb_ary_transient_heap_evacuate_(ary, RARRAY_TRANSIENT_P(ary), promote);
}

void
rb_ary_detransient(VALUE ary)
{
    assert(RARRAY_TRANSIENT_P(ary));
    rb_ary_transient_heap_evacuate_(ary, TRUE, TRUE);
}
#else
void
rb_ary_detransient(VALUE ary)
{
    /* do nothing */
}
#endif

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 = ary_heap_alloc(ary, 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 {
            ary_heap_realloc(ary, capacity);
        }
        ARY_SET_CAPA(ary, capacity);
    }
    else {
        if (!ARY_EMBED_P(ary)) {
            long len = ARY_HEAP_LEN(ary);
            long old_capa = ARY_HEAP_CAPA(ary);
            const VALUE *ptr = ARY_HEAP_PTR(ary);

            if (len > capacity) len = capacity;
            MEMCPY((VALUE *)RARRAY(ary)->as.ary, ptr, VALUE, len);
            ary_heap_free_ptr(ary, ptr, old_capa);

            FL_SET_EMBED(ary);
            ARY_SET_LEN(ary, len);
        }
    }

    ary_verify(ary);
}

static inline void
ary_shrink_capa(VALUE ary)
{
    long capacity = ARY_HEAP_LEN(ary);
    long old_capa = ARY_HEAP_CAPA(ary);
    assert(!ARY_SHARED_P(ary));
    assert(old_capa >= capacity);
    if (old_capa > capacity) ary_heap_realloc(ary, capacity);

    ary_verify(ary);
}

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);

    ary_verify(ary);
}

static void
rb_ary_decrement_share(VALUE shared_root)
{
    if (shared_root) {
        long num = ARY_SHARED_ROOT_REFCNT(shared_root) - 1;
	if (num == 0) {
            rb_ary_free(shared_root);
            rb_gc_force_recycle(shared_root);
	}
	else if (num > 0) {
            ARY_SET_SHARED_ROOT_REFCNT(shared_root, num);
	}
    }
}

static void
rb_ary_unshare(VALUE ary)
{
    VALUE shared_root = RARRAY(ary)->as.heap.aux.shared_root;
    rb_ary_decrement_share(shared_root);
    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_root)
{
    long num = ARY_SHARED_ROOT_REFCNT(shared_root);
    if (num >= 0) {
        ARY_SET_SHARED_ROOT_REFCNT(shared_root, num + 1);
    }
    return shared_root;
}

static void
rb_ary_set_shared(VALUE ary, VALUE shared_root)
{
    rb_ary_increment_share(shared_root);
    FL_SET_SHARED(ary);
    RB_DEBUG_COUNTER_INC(obj_ary_shared_create);
    ARY_SET_SHARED(ary, shared_root);
}

static inline void
rb_ary_modify_check(VALUE ary)
{
    rb_check_frozen(ary);
    ary_verify(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_root = ARY_SHARED_ROOT(ary);

        ary_verify(shared_root);

        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_root);
            ARY_SET_EMBED_LEN(ary, len);
        }
        else if (ARY_SHARED_ROOT_OCCUPIED(shared_root) && len > ((shared_len = RARRAY_LEN(shared_root))>>1)) {
            long shift = RARRAY_CONST_PTR_TRANSIENT(ary) - RARRAY_CONST_PTR_TRANSIENT(shared_root);
	    FL_UNSET_SHARED(ary);
            ARY_SET_PTR(ary, RARRAY_CONST_PTR_TRANSIENT(shared_root));
	    ARY_SET_CAPA(ary, shared_len);
            RARRAY_PTR_USE_TRANSIENT(ary, ptr, {
		MEMMOVE(ptr, ptr+shift, VALUE, len);
	    });
            FL_SET_EMBED(shared_root);
            rb_ary_decrement_share(shared_root);
	}
        else {
            VALUE *ptr = ary_heap_alloc(ary, len);
            MEMCPY(ptr, ARY_HEAP_PTR(ary), VALUE, len);
            rb_ary_unshare(ary);
            ARY_SET_CAPA(ary, len);
            ARY_SET_PTR(ary, ptr);
        }

	rb_gc_writebarrier_remember(ary);
    }
    ary_verify(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_root = ARY_SHARED_ROOT(ary);
            if (ARY_SHARED_ROOT_OCCUPIED(shared_root)) {
                if (ARY_HEAP_PTR(ary) - RARRAY_CONST_PTR_TRANSIENT(shared_root) + new_len <= RARRAY_LEN(shared_root)) {
		    rb_ary_modify_check(ary);

                    ary_verify(ary);
                    ary_verify(shared_root);
                    return shared_root;
		}
		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);
		    }
                    ary_verify(ary);
		    return ary;
		}
	    }
	}
        ary_verify(ary);
        rb_ary_modify(ary);
    }
    else {
	rb_ary_modify_check(ary);
    }
    capa = ARY_CAPA(ary);
    if (new_len > capa) {
	ary_double_capa(ary, new_len);
    }

    ary_verify(ary);
    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);
}

/* 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_root == RARRAY(ary2)->as.heap.aux.shared_root &&
	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 = ary_heap_alloc(ary, 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;
}

MJIT_FUNC_EXPORTED VALUE
rb_ary_tmp_new_from_values(VALUE klass, long n, const VALUE *elts)
{
    VALUE ary;

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

    return ary;
}

VALUE
rb_ary_new_from_values(long n, const VALUE *elts)
{
    return rb_ary_tmp_new_from_values(rb_cArray, n, elts);
}

VALUE
rb_ary_tmp_new(long capa)
{
    VALUE ary = ary_new(0, capa);
    rb_ary_transient_heap_evacuate(ary, TRUE);
    return ary;
}

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);
    rb_ary_transient_heap_evacuate(ary, TRUE);
    return ary;
}

void
rb_ary_free(VALUE ary)
{
    if (ARY_OWNS_HEAP_P(ary)) {
        if (USE_DEBUG_COUNTER &&
            !ARY_SHARED_ROOT_P(ary) &&
            ARY_HEAP_CAPA(ary) > RARRAY_LEN(ary)) {
            RB_DEBUG_COUNTER_INC(obj_ary_extracapa);
        }

        if (RARRAY_TRANSIENT_P(ary)) {
            RB_DEBUG_COUNTER_INC(obj_ary_transient);
        }
        else {
            RB_DEBUG_COUNTER_INC(obj_ary_ptr);
            ary_heap_free(ary);
        }
    }
    else {
        RB_DEBUG_COUNTER_INC(obj_ary_embed);
    }

    if (ARY_SHARED_P(ary)) {
        RB_DEBUG_COUNTER_INC(obj_ary_shared);
    }
    if (ARY_SHARED_ROOT_P(ary) && ARY_SHARED_ROOT_OCCUPIED(ary)) {
        RB_DEBUG_COUNTER_INC(obj_ary_shared_root_occupied);
    }
}

RUBY_FUNC_EXPORTED size_t
rb_ary_memsize(VALUE ary)
{
    if (ARY_OWNS_HEAP_P(ary)) {
	return ARY_CAPA(ary) * 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 | RARRAY_TRANSIENT_FLAG);
}

static VALUE
ary_make_shared(VALUE ary)
{
    assert(!ARY_EMBED_P(ary));
    ary_verify(ary);

    if (ARY_SHARED_P(ary)) {
        return ARY_SHARED_ROOT(ary);
    }
    else if (ARY_SHARED_ROOT_P(ary)) {
	return ary;
    }
    else if (OBJ_FROZEN(ary)) {
        rb_ary_transient_heap_evacuate(ary, TRUE);
	ary_shrink_capa(ary);
	FL_SET_SHARED_ROOT(ary);
        ARY_SET_SHARED_ROOT_REFCNT(ary, 1);
	return ary;
    }
    else {
	long capa = ARY_CAPA(ary), len = RARRAY_LEN(ary);
        const VALUE *ptr;
	NEWOBJ_OF(shared, struct RArray, 0, T_ARRAY | (RGENGC_WB_PROTECTED_ARRAY ? FL_WB_PROTECTED : 0));

        rb_ary_transient_heap_evacuate(ary, TRUE);
        ptr = ARY_HEAP_PTR(ary);

        FL_UNSET_EMBED(shared);
	ARY_SET_LEN((VALUE)shared, capa);
        ARY_SET_PTR((VALUE)shared, ptr);
        ary_mem_clear((VALUE)shared, len, capa - len);
	FL_SET_SHARED_ROOT(shared);
        ARY_SET_SHARED_ROOT_REFCNT((VALUE)shared, 1);
	FL_SET_SHARED(ary);
        RB_DEBUG_COUNTER_INC(obj_ary_shared_create);
	ARY_SET_SHARED(ary, (VALUE)shared);
	OBJ_FREEZE(shared);

        ary_verify((VALUE)shared);
        ary_verify(ary);

        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_TRANSIENT(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);
}

VALUE
rb_to_array_type(VALUE ary)
{
    return rb_convert_type_with_id(ary, T_ARRAY, "Array", idTo_ary);
}
#define to_ary rb_to_array_type

VALUE
rb_check_array_type(VALUE ary)
{
    return rb_check_convert_type_with_id(ary, T_ARRAY, "Array", idTo_ary);
}

MJIT_FUNC_EXPORTED VALUE
rb_check_to_array(VALUE ary)
{
    return rb_check_convert_type_with_id(ary, T_ARRAY, "Array", idTo_a);
}

/*
 *  call-seq:
 *     Array.try_convert(obj) -> array or nil
 *
 *  Tries to convert +obj+ into an array, using the +to_ary+ method.  Returns
 *  the converted array or +nil+ if +obj+ cannot be converted.
 *  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"}, {}]
 *
 */