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/ruby.h"
#include "ruby/util.h"
#include "ruby/st.h"

#ifndef ARRAY_DEBUG
# define NDEBUG
#endif
#include <assert.h>

VALUE rb_cArray;

static ID id_cmp;

#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 inline void
memfill(register VALUE *mem, register long size, register VALUE val)
{
    while (size--) {
	*mem++ = val;
    }
}

# 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_OWNS_HEAP_P(a) (!FL_TEST(a, ELTS_SHARED|RARRAY_EMBED_FLAG))
#define FL_SET_EMBED(a) do { \
    assert(!ARY_SHARED_P(a)); \
    assert(!OBJ_FROZEN(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 { \
    assert(!ARY_EMBED_P(ary)); \
    assert(ARY_SHARED_P(ary)); \
    assert(ARY_SHARED_ROOT_P(value)); \
    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_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)

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 {
            REALLOC_N(RARRAY(ary)->as.heap.ptr, VALUE, (capacity));
        }
        ARY_SET_CAPA(ary, (capacity));
    }
    else {
        if (!ARY_EMBED_P(ary)) {
            long len = RARRAY_LEN(ary);
            VALUE *ptr = RARRAY_PTR(ary);
            if (len > capacity) len = capacity;
            MEMCPY(RARRAY(ary)->as.ary, ptr, VALUE, len);
            FL_SET_EMBED(ary);
            ARY_SET_LEN(ary, len);
            xfree(ptr);
        }
    }
}

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)
{
    if (OBJ_FROZEN(ary)) rb_error_frozen("array");
    if (!OBJ_UNTRUSTED(ary) && rb_safe_level() >= 4)
	rb_raise(rb_eSecurityError, "Insecure: can't modify array");
}

static void
rb_ary_modify(VALUE ary)
{
    rb_ary_modify_check(ary);
    if (ARY_SHARED_P(ary)) {
        long len = RARRAY_LEN(ary);
        if (len <= RARRAY_EMBED_LEN_MAX) {
            VALUE *ptr = ARY_HEAP_PTR(ary);
            VALUE shared = ARY_SHARED(ary);
            FL_UNSET_SHARED(ary);
            FL_SET_EMBED(ary);
            MEMCPY(ARY_EMBED_PTR(ary), ptr, VALUE, len);
            rb_ary_decrement_share(shared);
            ARY_SET_EMBED_LEN(ary, len);
        }
        else {
            VALUE *ptr = ALLOC_N(VALUE, len);
            MEMCPY(ptr, RARRAY_PTR(ary), VALUE, len);
            rb_ary_unshare(ary);
            ARY_SET_CAPA(ary, len);
            ARY_SET_PTR(ary, ptr);
        }
    }
}

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

/*
 *  call-seq:
 *     array.frozen?  -> true or false
 *
 *  Return <code>true</code> if this array is frozen (or temporarily frozen
 *  while being sorted).
 */

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

static VALUE
ary_alloc(VALUE klass)
{
    NEWOBJ(ary, struct RArray);
    OBJSETUP(ary, klass, T_ARRAY);
    FL_SET_EMBED((VALUE)ary);
    ARY_SET_EMBED_LEN((VALUE)ary, 0);

    return (VALUE)ary;
}

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

    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");
    }
    ary = ary_alloc(klass);
    if (capa > RARRAY_EMBED_LEN_MAX) {
        FL_UNSET_EMBED(ary);
        ARY_SET_PTR(ary, ALLOC_N(VALUE, capa));
        ARY_SET_CAPA(ary, capa);
        ARY_SET_HEAP_LEN(ary, 0);
    }

    return ary;
}

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


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

#include <stdarg.h>

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

    ary = rb_ary_new2(n);

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

    ARY_SET_LEN(ary, n);
    return ary;
}

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

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

    return ary;
}

VALUE
rb_ary_tmp_new(long capa)
{
    return ary_new(0, capa);
}

void
rb_ary_free(VALUE ary)
{
    if (ARY_OWNS_HEAP_P(ary)) {
	xfree(ARY_HEAP_PTR(ary));
    }
}

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_resize_capa(ary, ARY_HEAP_LEN(ary));
	FL_SET_SHARED_ROOT(ary);
	ARY_SET_SHARED_NUM(ary, 1);
	return ary;
    }
    else {
	NEWOBJ(shared, struct RArray);
	OBJSETUP(shared, 0, T_ARRAY);
        FL_UNSET_EMBED(shared);

        ARY_SET_LEN((VALUE)shared, RARRAY_LEN(ary));
        ARY_SET_PTR((VALUE)shared, RARRAY_PTR(ary));
	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)
{
    if (RARRAY_LEN(ary) <= RARRAY_EMBED_LEN_MAX) {
        VALUE subst = rb_ary_new2(RARRAY_LEN(ary));
        MEMCPY(ARY_EMBED_PTR(subst), RARRAY_PTR(ary), VALUE, RARRAY_LEN(ary));
        ARY_SET_EMBED_LEN(subst, RARRAY_LEN(ary));
        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
 *
 *  Try to convert <i>obj</i> into an array, using to_ary method.
 *  Returns converted array or nil if <i>obj</i> cannot be converted
 *  for any reason.  This method is 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, obj=nil)
 *     Array.new(array)
 *     Array.new(size) {|index| block }
 *
 *  Returns a new array. In the first form, the new array is
 *  empty. In the second it is created with _size_ copies of _obj_
 *  (that is, _size_ references to the same
 *  _obj_). The third form creates a copy of the array
 *  passed as a parameter (the array is generated by calling
 *  to_ary  on the parameter). In the last form, an array
 *  of the given size is created. Each element in this array is
 *  calculated by passing the element's index to the given block and
 *  storing the return value.
 *
 *     Array.new
 *     Array.new(2)
 *     Array.new(5, "A")
 *
 *     # only one copy of the object is created
 *     a = Array.new(2, Hash.new)
 *     a[0]['cat'] = 'feline'
 *     a
 *     a[1]['cat'] = 'Felix'
 *     a
 *
 *     # here multiple copies are created
 *     a = Array.new(2) { Hash.new }
 *     a[0]['cat'] = 'feline'
 *     a
 *
 *     squares = Array.new(5) {|i| i*i}
 *     squares
 *
 *     copy = Array.new(squares)
 */

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_PTR(ary)) {
	    xfree(RARRAY_PTR(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);
    if (len < 0) {
	rb_raise(rb_eArgError, "negative array size");
    }
    if (len > ARY_MAX_SIZE) {
	rb_raise(rb_eArgError, "array size too big");
    }
    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 {
	memfill(RARRAY_PTR(ary), len, val);
	ARY_SET_LEN(ary, len);
    }
    return ary;
}


/*
* Returns a new array populated with the given objects.
*
*   Array.[]( 1, 'a', /^A/ )
*   Array[ 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) {
        MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
        ARY_SET_LEN(ary, argc);
    }

    return ary;
}

void
rb_ary_store(VALUE ary, long idx, VALUE val)
{
    if (idx < 0) {
	idx += RARRAY_LEN(ary);
	if (idx < 0) {
	    rb_raise(rb_eIndexError, "index %ld out of array",
		     idx - RARRAY_LEN(ary));
	}
    }
    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 > RARRAY_LEN(ary)) {
	rb_mem_clear(RARRAY_PTR(ary) + RARRAY_LEN(ary),
		     idx-RARRAY_LEN(ary) + 1);
    }

    if (idx >= RARRAY_LEN(ary)) {
	ARY_SET_LEN(ary, idx + 1);
    }
    RARRAY_PTR(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);
        MEMCPY(ARY_EMBED_PTR(result), RARRAY_PTR(ary) + offset, VALUE, len);
        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_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, VALUE *argv, VALUE ary, enum ary_take_pos_flags last)
{
    VALUE nv;
    long n;
    long offset = 0;

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

/*
 *  call-seq:
 *     array << obj            -> array
 *
 *  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);

    rb_ary_modify(ary);
    if (idx >= ARY_CAPA(ary)) {
	ary_double_capa(ary, idx);
    }
    RARRAY_PTR(ary)[idx] = item;
    ARY_SET_LEN(ary, idx + 1);
    return ary;
}

/*
 *  call-seq:
 *     array.push(obj, ... )   -> array
 *
 *  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.
 *
 *     a = [ "a", "b", "c" ]
 *     a.push("d", "e", "f")
 *             #=> ["a", "b", "c", "d", "e", "f"]
 */

static VALUE
rb_ary_push_m(int argc, VALUE *argv, VALUE ary)
{
    rb_ary_modify_check(ary);
    while (argc--) {
	rb_ary_push(ary, *argv++);
    }
    return ary;
}

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

/*
 *  call-seq:
 *     array.pop    -> obj or nil
 *     array.pop(n) -> array
 *
 *  Removes the last element from <i>self</i> and returns it, or
 *  <code>nil</code> 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.
 *
 *     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)
{
    VALUE top;

    rb_ary_modify_check(ary);
    if (RARRAY_LEN(ary) == 0) return Qnil;
    top = RARRAY_PTR(ary)[0];
    if (!ARY_SHARED_P(ary)) {
	if (RARRAY_LEN(ary) < ARY_DEFAULT_SIZE) {
	    MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+1, VALUE, RARRAY_LEN(ary)-1);
            ARY_INCREASE_LEN(ary, -1);
	    return top;
	}
        assert(!ARY_EMBED_P(ary)); /* ARY_EMBED_LEN_MAX < ARY_DEFAULT_SIZE */

	RARRAY_PTR(ary)[0] = Qnil;
	ary_make_shared(ary);
    }
    else if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
	RARRAY_PTR(ary)[0] = Qnil;
    }
    ARY_INCREASE_PTR(ary, 1);		/* shift ptr */
    ARY_INCREASE_LEN(ary, -1);

    return top;
}

/*
 *  call-seq:
 *     array.shift    -> obj or nil
 *     array.shift(n) -> array
 *
 *  Returns the first element of <i>self</i> and removes it (shifting all
 *  other elements down by one). Returns <code>nil</code> if the array
 *  is empty.
 *
 *  If a number _n_ is given, returns an array of the first n elements
 *  (or less) just like <code>array.slice!(0, n)</code> does.
 *
 *     args = [ "-m", "-q", "filename" ]
 *     args.shift     #=> "-m"
 *     args           #=> ["-q", "filename"]
 *
 *     args = [ "-m", "-q", "filename" ]
 *     args.shift(2)  #=> ["-m", "-q"]
 *     args           #=> ["filename"]
 */

static VALUE
rb_ary_shift_m(int argc, VALUE *argv, VALUE ary)
{
    VALUE result;
    long n;

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

    rb_ary_modify_check(ary);
    result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
    n = RARRAY_LEN(result);
    if (ARY_SHARED_P(ary)) {
	if (ARY_SHARED_NUM(ARY_SHARED(ary)) == 1) {
	    rb_mem_clear(RARRAY_PTR(ary), n);
	}
        ARY_INCREASE_PTR(ary, n);
    }
    else {
	MEMMOVE(RARRAY_PTR(ary), RARRAY_PTR(ary)+n, VALUE, RARRAY_LEN(ary)-n);
    }
    ARY_INCREASE_LEN(ary, -n);

    return result;
}

/*
 *  call-seq:
 *     array.unshift(obj, ...)  -> array
 *
 *  Prepends objects to the front of <i>array</i>.
 *  other elements up one.
 *
 *     a = [ "b", "c", "d" ]
 *     a.unshift("a")   #=> ["a", "b", "c", "d"]
 *     a.unshift(1, 2)  #=> [ 1, 2, "a", "b", "c", "d"]
 */

static VALUE
rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
{
    long len;

    if (argc == 0) return ary;
    rb_ary_modify(ary);
    if (ARY_CAPA(ary) <= (len = RARRAY_LEN(ary)) + argc) {
	ary_double_capa(ary, len + argc);
    }

    /* sliding items */
    MEMMOVE(RARRAY_PTR(ary) + argc, RARRAY_PTR(ary), VALUE, len);
    MEMCPY(RARRAY_PTR(ary), argv, VALUE, argc);
    ARY_INCREASE_LEN(ary, argc);

    return ary;
}

VALUE
rb_ary_unshift(VALUE ary, VALUE item)
{
    return rb_ary_unshift_m(1,&item,ary);
}

/* faster version - use this if you don't need to treat negative offset */
static inline VALUE
rb_ary_elt(VALUE ary, long offset)
{
    if (RARRAY_LEN(ary) == 0) return Qnil;
    if (offset < 0 || RARRAY_LEN(ary) <= offset) {
	return Qnil;
    }
    return RARRAY_PTR(ary)[offset];
}

VALUE
rb_ary_entry(VALUE ary, long offset)
{
    if (offset < 0) {
	offset += RARRAY_LEN(ary);
    }
    return rb_ary_elt(ary, offset);
}

VALUE
rb_ary_subseq(VALUE ary, long beg, long len)
{
    VALUE klass;

    if (beg > RARRAY_LEN(ary)) return Qnil;
    if (beg < 0 || len < 0) return Qnil;

    if (RARRAY_LEN(ary) < len || RARRAY_LEN(ary) < beg + len) {
	len = RARRAY_LEN(ary) - beg;
    }
    klass = rb_obj_class(ary);
    if (len == 0) return ary_new(klass, 0);

    return ary_make_partial(ary, klass, beg, len);
}

/*
 *  call-seq:
 *     array[index]                -> obj      or nil
 *     array[start, length]        -> an_array or nil
 *     array[range]                -> an_array or nil
 *     array.slice(index)          -> obj      or nil
 *     array.slice(start, length)  -> an_array or nil
 *     array.slice(range)          -> an_array or nil
 *
 *  Element Reference---Returns the element at _index_,
 *  or returns a subarray starting at _start_ and
 *  continuing for _length_ elements, or returns a subarray
 *  specified by _range_.
 *  Negative indices count backward from the end of the
 *  array (-1 is the last element). Returns nil if the index
 *  (or starting index) are out of range.
 *
 *     a = [ "a", "b", "c", "d", "e" ]
 *     a[2] +  a[0] + a[1]    #=> "cab"
 *     a[6]                   #=> nil
 *     a[1, 2]                #=> [ "b", "c" ]
 *     a[1..3]                #=> [ "b", "c", "d" ]
 *     a[4..7]                #=> [ "e" ]
 *     a[6..10]               #=> nil
 *     a[-3, 3]               #=> [ "c", "d", "e" ]
 *     # special cases
 *     a[5]                   #=> nil
 *     a[5, 1]                #=> []
 *     a[5..10]               #=> []
 *
 */

VALUE
rb_ary_aref(int argc, VALUE *argv, VALUE ary)
{
    VALUE arg;
    long beg, len;

    if (argc == 2) {
	beg = NUM2LONG(argv[0]);
	len = NUM2LONG(argv[1]);
	if (beg < 0) {
	    beg += RARRAY_LEN(ary);
	}
	return rb_ary_subseq(ary, beg, len);
    }
    if (argc != 1) {
	rb_scan_args(argc, argv, "11", 0, 0);
    }