#include "ruby.h"
#include "util.h"
#include "st.h"
VALUE rb_cArray;
static ID id_cmp;
#define ARY_DEFAULT_SIZE 16
#define ARY_MAX_SIZE (LONG_MAX / sizeof(VALUE))
void
rb_mem_clear(mem, size)
register VALUE *mem;
register long size;
{
while (size--) {
*mem++ = Qnil;
}
}
static inline void
memfill(mem, size, val)
register VALUE *mem;
register long size;
register VALUE val;
{
while (size--) {
*mem++ = val;
}
}
#define ARY_TMPLOCK FL_USER1
static inline void
rb_ary_modify_check(ary)
VALUE ary;
{
if (OBJ_FROZEN(ary)) rb_error_frozen("array");
if (FL_TEST(ary, ARY_TMPLOCK))
rb_raise(rb_eRuntimeError, "can't modify array during iteration");
if (!OBJ_TAINTED(ary) && rb_safe_level() >= 4)
rb_raise(rb_eSecurityError, "Insecure: can't modify array");
}
static void
rb_ary_modify(ary)
VALUE ary;
{
VALUE *ptr;
rb_ary_modify_check(ary);
if (FL_TEST(ary, ELTS_SHARED)) {
ptr = ALLOC_N(VALUE, RARRAY(ary)->len);
FL_UNSET(ary, ELTS_SHARED);
RARRAY(ary)->aux.capa = RARRAY(ary)->len;
MEMCPY(ptr, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
RARRAY(ary)->ptr = ptr;
}
}
VALUE
rb_ary_freeze(ary)
VALUE ary;
{
return rb_obj_freeze(ary);
}
static VALUE
rb_ary_frozen_p(ary)
VALUE ary;
{
if (OBJ_FROZEN(ary)) return Qtrue;
if (FL_TEST(ary, ARY_TMPLOCK)) return Qtrue;
return Qfalse;
}
static VALUE ary_alloc _((VALUE));
static VALUE
ary_alloc(klass)
VALUE klass;
{
NEWOBJ(ary, struct RArray);
OBJSETUP(ary, klass, T_ARRAY);
ary->len = 0;
ary->ptr = 0;
ary->aux.capa = 0;
return (VALUE)ary;
}
static VALUE
ary_new(klass, len)
VALUE klass;
long len;
{
VALUE ary = ary_alloc(klass);
if (len < 0) {
rb_raise(rb_eArgError, "negative array size (or size too big)");
}
if (len > ARY_MAX_SIZE) {
rb_raise(rb_eArgError, "array size too big");
}
if (len == 0) len++;
RARRAY(ary)->ptr = ALLOC_N(VALUE, len);
RARRAY(ary)->aux.capa = len;
return ary;
}
VALUE
rb_ary_new2(len)
long len;
{
return ary_new(rb_cArray, len);
}
VALUE
rb_ary_new()
{
return rb_ary_new2(ARY_DEFAULT_SIZE);
}
#ifdef HAVE_STDARG_PROTOTYPES
#include <stdarg.h>
#define va_init_list(a,b) va_start(a,b)
#else
#include <varargs.h>
#define va_init_list(a,b) va_start(a)
#endif
VALUE
#ifdef HAVE_STDARG_PROTOTYPES
rb_ary_new3(long n, ...)
#else
rb_ary_new3(n, va_alist)
long n;
va_dcl
#endif
{
va_list ar;
VALUE ary;
long i;
ary = rb_ary_new2(n);
va_init_list(ar, n);
for (i=0; i<n; i++) {
RARRAY(ary)->ptr[i] = va_arg(ar, VALUE);
}
va_end(ar);
RARRAY(ary)->len = n;
return ary;
}
VALUE
rb_ary_new4(n, elts)
long n;
const VALUE *elts;
{
VALUE ary;
ary = rb_ary_new2(n);
if (n > 0 && elts) {
MEMCPY(RARRAY(ary)->ptr, elts, VALUE, n);
}
RARRAY(ary)->len = n;
return ary;
}
static VALUE
ary_make_shared(ary)
VALUE ary;
{
if (!FL_TEST(ary, ELTS_SHARED)) {
NEWOBJ(shared, struct RArray);
OBJSETUP(shared, rb_cArray, T_ARRAY);
shared->len = RARRAY(ary)->len;
shared->ptr = RARRAY(ary)->ptr;
shared->aux.capa = RARRAY(ary)->aux.capa;
RARRAY(ary)->aux.shared = (VALUE)shared;
FL_SET(ary, ELTS_SHARED);
OBJ_FREEZE(shared);
return (VALUE)shared;
}
else {
return RARRAY(ary)->aux.shared;
}
}
VALUE
rb_assoc_new(car, cdr)
VALUE car, cdr;
{
VALUE ary;
ary = rb_ary_new2(2);
RARRAY(ary)->ptr[0] = car;
RARRAY(ary)->ptr[1] = cdr;
RARRAY(ary)->len = 2;
return ary;
}
static VALUE
to_ary(ary)
VALUE ary;
{
return rb_convert_type(ary, T_ARRAY, "Array", "to_ary");
}
VALUE
rb_check_array_type(ary)
VALUE ary;
{
return rb_check_convert_type(ary, T_ARRAY, "Array", "to_ary");
}
static VALUE rb_ary_replace _((VALUE, VALUE));
static VALUE
rb_ary_initialize(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
long len;
VALUE size, val;
rb_ary_modify(ary);
if (rb_scan_args(argc, argv, "02", &size, &val) == 0) {
RARRAY(ary)->len = 0;
if (rb_block_given_p()) {
rb_warning("given block not used");
}
return ary;
}
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");
}
if (len > RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, len);
RARRAY(ary)->aux.capa = 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)));
RARRAY(ary)->len = i + 1;
}
}
else {
memfill(RARRAY(ary)->ptr, len, val);
RARRAY(ary)->len = len;
}
return ary;
}
static VALUE
rb_ary_s_create(argc, argv, klass)
int argc;
VALUE *argv;
VALUE klass;
{
VALUE ary = ary_alloc(klass);
if (argc > 0) {
RARRAY(ary)->ptr = ALLOC_N(VALUE, argc);
MEMCPY(RARRAY(ary)->ptr, argv, VALUE, argc);
}
RARRAY(ary)->len = RARRAY(ary)->aux.capa = argc;
return ary;
}
void
rb_ary_store(ary, idx, val)
VALUE ary;
long idx;
VALUE val;
{
if (idx < 0) {
idx += RARRAY(ary)->len;
if (idx < 0) {
rb_raise(rb_eIndexError, "index %ld out of array",
idx - RARRAY(ary)->len);
}
}
else if (idx >= ARY_MAX_SIZE) {
rb_raise(rb_eIndexError, "index %ld too big", idx);
}
rb_ary_modify(ary);
if (idx >= RARRAY(ary)->aux.capa) {
long new_capa = RARRAY(ary)->aux.capa / 2;
if (new_capa < ARY_DEFAULT_SIZE) {
new_capa = ARY_DEFAULT_SIZE;
}
if (new_capa >= ARY_MAX_SIZE - idx) {
new_capa = (ARY_MAX_SIZE - idx) / 2;
}
new_capa += idx;
REALLOC_N(RARRAY(ary)->ptr, VALUE, new_capa);
RARRAY(ary)->aux.capa = new_capa;
}
if (idx > RARRAY(ary)->len) {
rb_mem_clear(RARRAY(ary)->ptr + RARRAY(ary)->len,
idx-RARRAY(ary)->len + 1);
}
if (idx >= RARRAY(ary)->len) {
RARRAY(ary)->len = idx + 1;
}
RARRAY(ary)->ptr[idx] = val;
}
static VALUE
ary_shared_array(klass, ary)
VALUE klass;
VALUE ary;
{
VALUE val = ary_alloc(klass);
ary_make_shared(ary);
RARRAY(val)->ptr = RARRAY(ary)->ptr;
RARRAY(val)->len = RARRAY(ary)->len;
RARRAY(val)->aux.shared = RARRAY(ary)->aux.shared;
FL_SET(val, ELTS_SHARED);
return val;
}
static VALUE
ary_shared_first(argc, argv, ary, last)
int argc;
VALUE *argv;
VALUE ary;
int last;
{
VALUE nv, result;
long n;
long offset = 0;
rb_scan_args(argc, argv, "1", &nv);
n = NUM2LONG(nv);
if (n > RARRAY(ary)->len) {
n = RARRAY(ary)->len;
}
else if (n < 0) {
rb_raise(rb_eArgError, "negative array size");
}
if (last) {
offset = RARRAY(ary)->len - n;
}
result = ary_shared_array(rb_cArray, ary);
RARRAY(result)->ptr += offset;
RARRAY(result)->len = n;
return result;
}
VALUE
rb_ary_push(ary, item)
VALUE ary;
VALUE item;
{
rb_ary_store(ary, RARRAY(ary)->len, item);
return ary;
}
static VALUE
rb_ary_push_m(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
while (argc--) {
rb_ary_push(ary, *argv++);
}
return ary;
}
VALUE
rb_ary_pop(ary)
VALUE ary;
{
rb_ary_modify_check(ary);
if (RARRAY(ary)->len == 0) return Qnil;
if (!FL_TEST(ary, ELTS_SHARED) &&
RARRAY(ary)->len * 3 < RARRAY(ary)->aux.capa &&
RARRAY(ary)->aux.capa > ARY_DEFAULT_SIZE) {
RARRAY(ary)->aux.capa = RARRAY(ary)->len * 2;
REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->aux.capa);
}
return RARRAY(ary)->ptr[--RARRAY(ary)->len];
}
static VALUE
rb_ary_pop_m(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE result;
if (argc == 0) {
return rb_ary_pop(ary);
}
rb_ary_modify_check(ary);
result = ary_shared_first(argc, argv, ary, Qtrue);
RARRAY(ary)->len -= RARRAY(result)->len;
return result;
}
VALUE
rb_ary_shift(ary)
VALUE ary;
{
VALUE top;
rb_ary_modify_check(ary);
if (RARRAY(ary)->len == 0) return Qnil;
top = RARRAY(ary)->ptr[0];
if (!FL_TEST(ary, ELTS_SHARED)) {
if (RARRAY(ary)->len < ARY_DEFAULT_SIZE) {
MEMMOVE(RARRAY(ary)->ptr, RARRAY(ary)->ptr+1, VALUE, RARRAY(ary)->len-1);
RARRAY(ary)->len--;
return top;
}
RARRAY(ary)->ptr[0] = Qnil;
ary_make_shared(ary);
}
RARRAY(ary)->ptr++;
RARRAY(ary)->len--;
return top;
}
static VALUE
rb_ary_shift_m(argc, argv, ary)
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_shared_first(argc, argv, ary, Qfalse);
n = RARRAY(result)->len;
if (FL_TEST(ary, ELTS_SHARED)) {
RARRAY(ary)->ptr += n;
RARRAY(ary)->len -= n;
}
else {
MEMMOVE(RARRAY(ary)->ptr, RARRAY(ary)->ptr+n, VALUE, RARRAY(ary)->len-n);
RARRAY(ary)->len -= n;
}
return result;
}
VALUE
rb_ary_unshift(ary, item)
VALUE ary, item;
{
rb_ary_modify(ary);
if (RARRAY(ary)->len == RARRAY(ary)->aux.capa) {
long capa_inc = RARRAY(ary)->aux.capa / 2;
if (capa_inc < ARY_DEFAULT_SIZE) {
capa_inc = ARY_DEFAULT_SIZE;
}
RARRAY(ary)->aux.capa += capa_inc;
REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->aux.capa);
}
MEMMOVE(RARRAY(ary)->ptr + 1, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
RARRAY(ary)->len++;
RARRAY(ary)->ptr[0] = item;
return ary;
}
static VALUE
rb_ary_unshift_m(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
long len = RARRAY(ary)->len;
if (argc == 0) return ary;
rb_ary_store(ary, len + argc - 1, Qnil);
MEMMOVE(RARRAY(ary)->ptr + argc, RARRAY(ary)->ptr, VALUE, len);
MEMCPY(RARRAY(ary)->ptr, argv, VALUE, argc);
return ary;
}
static inline VALUE
rb_ary_elt(ary, offset)
VALUE ary;
long offset;
{
if (RARRAY(ary)->len == 0) return Qnil;
if (offset < 0 || RARRAY(ary)->len <= offset) {
return Qnil;
}
return RARRAY(ary)->ptr[offset];
}
VALUE
rb_ary_entry(ary, offset)
VALUE ary;
long offset;
{
if (offset < 0) {
offset += RARRAY(ary)->len;
}
return rb_ary_elt(ary, offset);
}
static VALUE
rb_ary_subseq(ary, beg, len)
VALUE ary;
long beg, len;
{
VALUE klass, ary2, shared;
VALUE *ptr;
if (beg > RARRAY(ary)->len) return Qnil;
if (beg < 0 || len < 0) return Qnil;
if (RARRAY(ary)->len < len || RARRAY(ary)->len < beg + len) {
len = RARRAY(ary)->len - beg;
if (len < 0)
len = 0;
}
klass = rb_obj_class(ary);
if (len == 0) return ary_new(klass, 0);
shared = ary_make_shared(ary);
ptr = RARRAY(ary)->ptr;
ary2 = ary_alloc(klass);
RARRAY(ary2)->ptr = ptr + beg;
RARRAY(ary2)->len = len;
RARRAY(ary2)->aux.shared = shared;
FL_SET(ary2, ELTS_SHARED);
return ary2;
}
VALUE
rb_ary_aref(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE arg;
long beg, len;
if (argc == 2) {
if (SYMBOL_P(argv[0])) {
rb_raise(rb_eTypeError, "Symbol as array index");
}
beg = NUM2LONG(argv[0]);
len = NUM2LONG(argv[1]);
if (beg < 0) {
beg += RARRAY(ary)->len;
}
return rb_ary_subseq(ary, beg, len);
}
if (argc != 1) {
rb_scan_args(argc, argv, "11", 0, 0);
}
arg = argv[0];
if (FIXNUM_P(arg)) {
return rb_ary_entry(ary, FIX2LONG(arg));
}
if (SYMBOL_P(arg)) {
rb_raise(rb_eTypeError, "Symbol as array index");
}
switch (rb_range_beg_len(arg, &beg, &len, RARRAY(ary)->len, 0)) {
case Qfalse:
break;
case Qnil:
return Qnil;
default:
return rb_ary_subseq(ary, beg, len);
}
return rb_ary_entry(ary, NUM2LONG(arg));
}
static VALUE
rb_ary_at(ary, pos)
VALUE ary, pos;
{
return rb_ary_entry(ary, NUM2LONG(pos));
}
static VALUE
rb_ary_first(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
if (argc == 0) {
if (RARRAY(ary)->len == 0) return Qnil;
return RARRAY(ary)->ptr[0];
}
else {
return ary_shared_first(argc, argv, ary, Qfalse);
}
}
static VALUE
rb_ary_last(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
if (argc == 0) {
if (RARRAY(ary)->len == 0) return Qnil;
return RARRAY(ary)->ptr[RARRAY(ary)->len-1];
}
else {
return ary_shared_first(argc, argv, ary, Qtrue);
}
}
static VALUE
rb_ary_fetch(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE pos, ifnone;
long block_given;
long idx;
rb_scan_args(argc, argv, "11", &pos, &ifnone);
block_given = rb_block_given_p();
if (block_given && argc == 2) {
rb_warn("block supersedes default value argument");
}
idx = NUM2LONG(pos);
if (idx < 0) {
idx += RARRAY(ary)->len;
}
if (idx < 0 || RARRAY(ary)->len <= idx) {
if (block_given) return rb_yield(pos);
if (argc == 1) {
rb_raise(rb_eIndexError, "index %ld out of array", idx);
}
return ifnone;
}
return RARRAY(ary)->ptr[idx];
}
static VALUE
rb_ary_index(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE val;
long i;
if (argc == 0) {
RETURN_ENUMERATOR(ary, 0, 0);
for (i=0; i<RARRAY(ary)->len; i++) {
if (RTEST(rb_yield(RARRAY(ary)->ptr[i]))) {
return LONG2NUM(i);
}
}
return Qnil;
}
rb_scan_args(argc, argv, "01", &val);
for (i=0; i<RARRAY(ary)->len; i++) {
if (rb_equal(RARRAY(ary)->ptr[i], val))
return LONG2NUM(i);
}
return Qnil;
}
static VALUE
rb_ary_rindex(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE val;
long i = RARRAY(ary)->len;
if (argc == 0) {
RETURN_ENUMERATOR(ary, 0, 0);
while (i--) {
if (RTEST(rb_yield(RARRAY(ary)->ptr[i])))
return LONG2NUM(i);
if (i > RARRAY(ary)->len) {
i = RARRAY(ary)->len;
}
}
return Qnil;
}
rb_scan_args(argc, argv, "01", &val);
while (i--) {
if (rb_equal(RARRAY(ary)->ptr[i], val))
return LONG2NUM(i);
if (i > RARRAY(ary)->len) {
i = RARRAY(ary)->len;
}
}
return Qnil;
}
static VALUE
rb_ary_indexes(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE new_ary;
long i;
rb_warn("Array#%s is deprecated; use Array#values_at", rb_id2name(rb_frame_last_func()));
new_ary = rb_ary_new2(argc);
for (i=0; i<argc; i++) {
rb_ary_push(new_ary, rb_ary_aref(1, argv+i, ary));
}
return new_ary;
}
VALUE
rb_ary_to_ary(obj)
VALUE obj;
{
if (TYPE(obj) == T_ARRAY) {
return obj;
}
if (rb_respond_to(obj, rb_intern("to_ary"))) {
return rb_convert_type(obj, T_ARRAY, "Array", "to_ary");
}
return rb_ary_new3(1, obj);
}
static void
rb_ary_splice(ary, beg, len, rpl)
VALUE ary;
long beg, len;
VALUE rpl;
{
long rlen;
if (len < 0) rb_raise(rb_eIndexError, "negative length (%ld)", len);
if (beg < 0) {
beg += RARRAY(ary)->len;
if (beg < 0) {
beg -= RARRAY(ary)->len;
rb_raise(rb_eIndexError, "index %ld out of array", beg);
}
}
if (RARRAY(ary)->len < len || RARRAY(ary)->len < beg + len) {
len = RARRAY(ary)->len - beg;
}
if (NIL_P(rpl)) {
rlen = 0;
}
else {
rpl = rb_ary_to_ary(rpl);
rlen = RARRAY(rpl)->len;
}
rb_ary_modify(ary);
if (beg >= RARRAY(ary)->len) {
if (beg > ARY_MAX_SIZE - rlen) {
rb_raise(rb_eIndexError, "index %ld too big", beg);
}
len = beg + rlen;
if (len >= RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, len);
RARRAY(ary)->aux.capa = len;
}
rb_mem_clear(RARRAY(ary)->ptr + RARRAY(ary)->len, beg - RARRAY(ary)->len);
if (rlen > 0) {
MEMCPY(RARRAY(ary)->ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen);
}
RARRAY(ary)->len = len;
}
else {
long alen;
if (beg + len > RARRAY(ary)->len) {
len = RARRAY(ary)->len - beg;
}
alen = RARRAY(ary)->len + rlen - len;
if (alen >= RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, alen);
RARRAY(ary)->aux.capa = alen;
}
if (len != rlen) {
MEMMOVE(RARRAY(ary)->ptr + beg + rlen, RARRAY(ary)->ptr + beg + len,
VALUE, RARRAY(ary)->len - (beg + len));
RARRAY(ary)->len = alen;
}
if (rlen > 0) {
MEMMOVE(RARRAY(ary)->ptr + beg, RARRAY(rpl)->ptr, VALUE, rlen);
}
}
}
static VALUE
rb_ary_aset(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
long offset, beg, len;
if (argc == 3) {
if (SYMBOL_P(argv[0])) {
rb_raise(rb_eTypeError, "Symbol as array index");
}
if (SYMBOL_P(argv[1])) {
rb_raise(rb_eTypeError, "Symbol as subarray length");
}
rb_ary_splice(ary, NUM2LONG(argv[0]), NUM2LONG(argv[1]), argv[2]);
return argv[2];
}
if (argc != 2) {
rb_raise(rb_eArgError, "wrong number of arguments (%d for 2)", argc);
}
if (FIXNUM_P(argv[0])) {
offset = FIX2LONG(argv[0]);
goto fixnum;
}
if (SYMBOL_P(argv[0])) {
rb_raise(rb_eTypeError, "Symbol as array index");
}
if (rb_range_beg_len(argv[0], &beg, &len, RARRAY(ary)->len, 1)) {
rb_ary_splice(ary, beg, len, argv[1]);
return argv[1];
}
offset = NUM2LONG(argv[0]);
fixnum:
rb_ary_store(ary, offset, argv[1]);
return argv[1];
}
static VALUE
rb_ary_insert(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
long pos;
if (argc == 1) return ary;
if (argc < 1) {
rb_raise(rb_eArgError, "wrong number of arguments (at least 1)");
}
pos = NUM2LONG(argv[0]);
if (pos == -1) {
pos = RARRAY(ary)->len;
}
if (pos < 0) {
pos++;
}
rb_ary_splice(ary, pos, 0, rb_ary_new4(argc - 1, argv + 1));
return ary;
}
VALUE
rb_ary_each(ary)
VALUE ary;
{
long i;
RETURN_ENUMERATOR(ary, 0, 0);
for (i=0; i<RARRAY(ary)->len; i++) {
rb_yield(RARRAY(ary)->ptr[i]);
}
return ary;
}
static VALUE
rb_ary_each_index(ary)
VALUE ary;
{
long i;
RETURN_ENUMERATOR(ary, 0, 0);
for (i=0; i<RARRAY(ary)->len; i++) {
rb_yield(LONG2NUM(i));
}
return ary;
}
static VALUE
rb_ary_reverse_each(ary)
VALUE ary;
{
long len;
RETURN_ENUMERATOR(ary, 0, 0);
len = RARRAY(ary)->len;
while (len--) {
rb_yield(RARRAY(ary)->ptr[len]);
if (RARRAY(ary)->len < len) {
len = RARRAY(ary)->len;
}
}
return ary;
}
static VALUE
rb_ary_length(ary)
VALUE ary;
{
return LONG2NUM(RARRAY(ary)->len);
}
static VALUE
rb_ary_empty_p(ary)
VALUE ary;
{
if (RARRAY(ary)->len == 0)
return Qtrue;
return Qfalse;
}
VALUE
rb_ary_dup(ary)
VALUE ary;
{
VALUE dup = rb_ary_new2(RARRAY(ary)->len);
DUPSETUP(dup, ary);
MEMCPY(RARRAY(dup)->ptr, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
RARRAY(dup)->len = RARRAY(ary)->len;
return dup;
}
extern VALUE rb_output_fs;
static VALUE
inspect_join(ary, arg)
VALUE ary;
VALUE *arg;
{
return rb_ary_join(arg[0], arg[1]);
}
VALUE
rb_ary_join(ary, sep)
VALUE ary, sep;
{
long len = 1, i;
int taint = Qfalse;
VALUE result, tmp;
if (RARRAY(ary)->len == 0) return rb_str_new(0, 0);
if (OBJ_TAINTED(ary) || OBJ_TAINTED(sep)) taint = Qtrue;
for (i=0; i<RARRAY(ary)->len; i++) {
tmp = rb_check_string_type(RARRAY(ary)->ptr[i]);
len += NIL_P(tmp) ? 10 : RSTRING(tmp)->len;
}
if (!NIL_P(sep)) {
StringValue(sep);
len += RSTRING(sep)->len * (RARRAY(ary)->len - 1);
}
result = rb_str_buf_new(len);
for (i=0; i<RARRAY(ary)->len; i++) {
tmp = RARRAY(ary)->ptr[i];
switch (TYPE(tmp)) {
case T_STRING:
break;
case T_ARRAY:
if (tmp == ary || rb_inspecting_p(tmp)) {
tmp = rb_str_new2("[...]");
}
else {
VALUE args[2];
args[0] = tmp;
args[1] = sep;
tmp = rb_protect_inspect(inspect_join, ary, (VALUE)args);
}
break;
default:
tmp = rb_obj_as_string(tmp);
}
if (i > 0 && !NIL_P(sep))
rb_str_buf_append(result, sep);
rb_str_buf_append(result, tmp);
if (OBJ_TAINTED(tmp)) taint = Qtrue;
}
if (taint) OBJ_TAINT(result);
return result;
}
static VALUE
rb_ary_join_m(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE sep;
rb_scan_args(argc, argv, "01", &sep);
if (NIL_P(sep)) sep = rb_output_fs;
return rb_ary_join(ary, sep);
}
VALUE
rb_ary_to_s(ary)
VALUE ary;
{
if (RARRAY(ary)->len == 0) return rb_str_new(0, 0);
return rb_ary_join(ary, rb_output_fs);
}
static ID inspect_key;
struct inspect_arg {
VALUE (*func)();
VALUE arg1, arg2;
};
static VALUE
inspect_call(arg)
struct inspect_arg *arg;
{
return (*arg->func)(arg->arg1, arg->arg2);
}
static VALUE
get_inspect_tbl(create)
int create;
{
VALUE inspect_tbl = rb_thread_local_aref(rb_thread_current(), inspect_key);
if (NIL_P(inspect_tbl)) {
if (create) {
tbl_init:
inspect_tbl = rb_ary_new();
rb_thread_local_aset(rb_thread_current(), inspect_key, inspect_tbl);
}
}
else if (TYPE(inspect_tbl) != T_ARRAY) {
rb_warn("invalid inspect_tbl value");
if (create) goto tbl_init;
rb_thread_local_aset(rb_thread_current(), inspect_key, Qnil);
return Qnil;
}
return inspect_tbl;
}
static VALUE
inspect_ensure(obj)
VALUE obj;
{
VALUE inspect_tbl;
inspect_tbl = get_inspect_tbl(Qfalse);
if (!NIL_P(inspect_tbl)) {
rb_ary_pop(inspect_tbl);
}
return 0;
}
VALUE
rb_protect_inspect(func, obj, arg)
VALUE (*func)(ANYARGS);
VALUE obj, arg;
{
struct inspect_arg iarg;
VALUE inspect_tbl;
VALUE id;
inspect_tbl = get_inspect_tbl(Qtrue);
id = rb_obj_id(obj);
if (rb_ary_includes(inspect_tbl, id)) {
return (*func)(obj, arg);
}
rb_ary_push(inspect_tbl, id);
iarg.func = func;
iarg.arg1 = obj;
iarg.arg2 = arg;
return rb_ensure(inspect_call, (VALUE)&iarg, inspect_ensure, obj);
}
VALUE
rb_inspecting_p(obj)
VALUE obj;
{
VALUE inspect_tbl;
inspect_tbl = get_inspect_tbl(Qfalse);
if (NIL_P(inspect_tbl)) return Qfalse;
return rb_ary_includes(inspect_tbl, rb_obj_id(obj));
}
static VALUE
inspect_ary(ary)
VALUE ary;
{
int tainted = OBJ_TAINTED(ary);
long i;
VALUE s, str;
str = rb_str_buf_new2("[");
for (i=0; i<RARRAY(ary)->len; i++) {
s = rb_inspect(RARRAY(ary)->ptr[i]);
if (OBJ_TAINTED(s)) tainted = Qtrue;
if (i > 0) rb_str_buf_cat2(str, ", ");
rb_str_buf_append(str, s);
}
rb_str_buf_cat2(str, "]");
if (tainted) OBJ_TAINT(str);
return str;
}
static VALUE
rb_ary_inspect(ary)
VALUE ary;
{
if (RARRAY(ary)->len == 0) return rb_str_new2("[]");
if (rb_inspecting_p(ary)) return rb_str_new2("[...]");
return rb_protect_inspect(inspect_ary, ary, 0);
}
static VALUE
rb_ary_to_a(ary)
VALUE ary;
{
if (rb_obj_class(ary) != rb_cArray) {
VALUE dup = rb_ary_new2(RARRAY(ary)->len);
rb_ary_replace(dup, ary);
return dup;
}
return ary;
}
static VALUE
rb_ary_to_ary_m(ary)
VALUE ary;
{
return ary;
}
VALUE
rb_ary_reverse(ary)
VALUE ary;
{
VALUE *p1, *p2;
VALUE tmp;
rb_ary_modify(ary);
if (RARRAY(ary)->len > 1) {
p1 = RARRAY(ary)->ptr;
p2 = p1 + RARRAY(ary)->len - 1;
while (p1 < p2) {
tmp = *p1;
*p1++ = *p2;
*p2-- = tmp;
}
}
return ary;
}
static VALUE
rb_ary_reverse_bang(ary)
VALUE ary;
{
return rb_ary_reverse(ary);
}
static VALUE
rb_ary_reverse_m(ary)
VALUE ary;
{
return rb_ary_reverse(rb_ary_dup(ary));
}
struct ary_sort_data {
VALUE ary;
VALUE *ptr;
long len;
};
static void
ary_sort_check(data)
struct ary_sort_data *data;
{
if (RARRAY(data->ary)->ptr != data->ptr || RARRAY(data->ary)->len != data->len) {
rb_raise(rb_eArgError, "array modified during sort");
}
}
static int
sort_1(a, b, data)
VALUE *a, *b;
struct ary_sort_data *data;
{
VALUE retval = rb_yield_values(2, *a, *b);
int n;
n = rb_cmpint(retval, *a, *b);
ary_sort_check(data);
return n;
}
static int
sort_2(ap, bp, data)
VALUE *ap, *bp;
struct ary_sort_data *data;
{
VALUE retval;
VALUE a = *ap, b = *bp;
int n;
if (FIXNUM_P(a) && FIXNUM_P(b)) {
if ((long)a > (long)b) return 1;
if ((long)a < (long)b) return -1;
return 0;
}
if (TYPE(a) == T_STRING) {
if (TYPE(b) == T_STRING) return rb_str_cmp(a, b);
}
retval = rb_funcall(a, id_cmp, 1, b);
n = rb_cmpint(retval, a, b);
ary_sort_check(data);
return n;
}
static VALUE
sort_internal(ary)
VALUE ary;
{
struct ary_sort_data data;
data.ary = ary;
data.ptr = RARRAY(ary)->ptr; data.len = RARRAY(ary)->len;
qsort(RARRAY(ary)->ptr, RARRAY(ary)->len, sizeof(VALUE),
rb_block_given_p()?sort_1:sort_2, &data);
return ary;
}
static VALUE
sort_unlock(ary)
VALUE ary;
{
FL_UNSET(ary, ARY_TMPLOCK);
return ary;
}
VALUE
rb_ary_sort_bang(ary)
VALUE ary;
{
rb_ary_modify(ary);
if (RARRAY(ary)->len > 1) {
FL_SET(ary, ARY_TMPLOCK);
rb_ensure(sort_internal, ary, sort_unlock, ary);
}
return ary;
}
VALUE
rb_ary_sort(ary)
VALUE ary;
{
ary = rb_ary_dup(ary);
rb_ary_sort_bang(ary);
return ary;
}
static VALUE
rb_ary_collect(ary)
VALUE ary;
{
long i;
VALUE collect;
if (!rb_block_given_p()) {
return rb_ary_new4(RARRAY(ary)->len, RARRAY(ary)->ptr);
}
collect = rb_ary_new2(RARRAY(ary)->len);
for (i = 0; i < RARRAY(ary)->len; i++) {
rb_ary_push(collect, rb_yield(RARRAY(ary)->ptr[i]));
}
return collect;
}
static VALUE
rb_ary_collect_bang(ary)
VALUE ary;
{
long i;
RETURN_ENUMERATOR(ary, 0, 0);
rb_ary_modify(ary);
for (i = 0; i < RARRAY(ary)->len; i++) {
rb_ary_store(ary, i, rb_yield(RARRAY(ary)->ptr[i]));
}
return ary;
}
VALUE
rb_values_at(obj, olen, argc, argv, func)
VALUE obj;
long olen;
int argc;
VALUE *argv;
VALUE (*func) _((VALUE,long));
{
VALUE result = rb_ary_new2(argc);
long beg, len, i, j;
for (i=0; i<argc; i++) {
if (FIXNUM_P(argv[i])) {
rb_ary_push(result, (*func)(obj, FIX2LONG(argv[i])));
continue;
}
switch (rb_range_beg_len(argv[i], &beg, &len, olen, 0)) {
case Qfalse:
break;
case Qnil:
continue;
default:
for (j=0; j<len; j++) {
rb_ary_push(result, (*func)(obj, j+beg));
}
continue;
}
rb_ary_push(result, (*func)(obj, NUM2LONG(argv[i])));
}
return result;
}
static VALUE
rb_ary_values_at(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
return rb_values_at(ary, RARRAY(ary)->len, argc, argv, rb_ary_entry);
}
static VALUE
rb_ary_select(ary)
VALUE ary;
{
VALUE result;
long i;
RETURN_ENUMERATOR(ary, 0, 0);
result = rb_ary_new2(RARRAY(ary)->len);
for (i = 0; i < RARRAY(ary)->len; i++) {
if (RTEST(rb_yield(RARRAY(ary)->ptr[i]))) {
rb_ary_push(result, rb_ary_elt(ary, i));
}
}
return result;
}
VALUE
rb_ary_delete(ary, item)
VALUE ary;
VALUE item;
{
long i1, i2;
for (i1 = i2 = 0; i1 < RARRAY(ary)->len; i1++) {
VALUE e = RARRAY(ary)->ptr[i1];
if (rb_equal(e, item)) continue;
if (i1 != i2) {
rb_ary_store(ary, i2, e);
}
i2++;
}
if (RARRAY(ary)->len == i2) {
if (rb_block_given_p()) {
return rb_yield(item);
}
return Qnil;
}
rb_ary_modify(ary);
if (RARRAY(ary)->len > i2) {
RARRAY(ary)->len = i2;
if (i2 * 2 < RARRAY(ary)->aux.capa &&
RARRAY(ary)->aux.capa > ARY_DEFAULT_SIZE) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, i2 * 2);
RARRAY(ary)->aux.capa = i2 * 2;
}
}
return item;
}
VALUE
rb_ary_delete_at(ary, pos)
VALUE ary;
long pos;
{
long i, len = RARRAY(ary)->len;
VALUE del;
if (pos >= len) return Qnil;
if (pos < 0) {
pos += len;
if (pos < 0) return Qnil;
}
rb_ary_modify(ary);
del = RARRAY(ary)->ptr[pos];
for (i = pos + 1; i < len; i++, pos++) {
RARRAY(ary)->ptr[pos] = RARRAY(ary)->ptr[i];
}
RARRAY(ary)->len = pos;
return del;
}
static VALUE
rb_ary_delete_at_m(ary, pos)
VALUE ary, pos;
{
return rb_ary_delete_at(ary, NUM2LONG(pos));
}
static VALUE
rb_ary_slice_bang(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE arg1, arg2;
long pos, len, orig_len;
rb_ary_modify_check(ary);
if (rb_scan_args(argc, argv, "11", &arg1, &arg2) == 2) {
pos = NUM2LONG(arg1);
len = NUM2LONG(arg2);
delete_pos_len:
if (len < 0) return Qnil;
orig_len = RARRAY_LEN(ary);
if (pos < 0) {
pos += orig_len;
if (pos < 0) return Qnil;
}
else if (orig_len < pos) return Qnil;
if (orig_len < pos + len) {
len = orig_len - pos;
}
if (len == 0) return rb_ary_new2(0);
arg2 = rb_ary_new4(len, RARRAY_PTR(ary)+pos);
RBASIC(arg2)->klass = rb_obj_class(ary);
rb_ary_splice(ary, pos, len, Qnil);
return arg2;
}
if (!FIXNUM_P(arg1)) {
switch (rb_range_beg_len(arg1, &pos, &len, RARRAY_LEN(ary), 0)) {
case Qtrue:
goto delete_pos_len;
case Qnil:
return Qnil;
default:
break;
}
}
return rb_ary_delete_at(ary, NUM2LONG(arg1));
}
static VALUE
rb_ary_reject_bang(ary)
VALUE ary;
{
long i1, i2;
RETURN_ENUMERATOR(ary, 0, 0);
rb_ary_modify(ary);
for (i1 = i2 = 0; i1 < RARRAY(ary)->len; i1++) {
VALUE v = RARRAY(ary)->ptr[i1];
if (RTEST(rb_yield(v))) continue;
if (i1 != i2) {
rb_ary_store(ary, i2, v);
}
i2++;
}
if (RARRAY(ary)->len == i2) return Qnil;
if (i2 < RARRAY(ary)->len)
RARRAY(ary)->len = i2;
return ary;
}
static VALUE
rb_ary_reject(ary)
VALUE ary;
{
RETURN_ENUMERATOR(ary, 0, 0);
ary = rb_ary_dup(ary);
rb_ary_reject_bang(ary);
return ary;
}
static VALUE
rb_ary_delete_if(ary)
VALUE ary;
{
RETURN_ENUMERATOR(ary, 0, 0);
rb_ary_reject_bang(ary);
return ary;
}
static VALUE
rb_ary_zip(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
int i, j;
long len;
VALUE result;
for (i=0; i<argc; i++) {
argv[i] = to_ary(argv[i]);
}
if (rb_block_given_p()) {
for (i=0; i<RARRAY(ary)->len; i++) {
VALUE tmp = rb_ary_new2(argc+1);
rb_ary_push(tmp, rb_ary_elt(ary, i));
for (j=0; j<argc; j++) {
rb_ary_push(tmp, rb_ary_elt(argv[j], i));
}
rb_yield(tmp);
}
return Qnil;
}
len = RARRAY(ary)->len;
result = rb_ary_new2(len);
for (i=0; i<len; i++) {
VALUE tmp = rb_ary_new2(argc+1);
rb_ary_push(tmp, rb_ary_elt(ary, i));
for (j=0; j<argc; j++) {
rb_ary_push(tmp, rb_ary_elt(argv[j], i));
}
rb_ary_push(result, tmp);
}
return result;
}
static VALUE
rb_ary_transpose(ary)
VALUE ary;
{
long elen = -1, alen, i, j;
VALUE tmp, result = 0;
alen = RARRAY(ary)->len;
if (alen == 0) return rb_ary_dup(ary);
for (i=0; i<alen; i++) {
tmp = to_ary(rb_ary_elt(ary, i));
if (elen < 0) {
elen = RARRAY(tmp)->len;
result = rb_ary_new2(elen);
for (j=0; j<elen; j++) {
rb_ary_store(result, j, rb_ary_new2(alen));
}
}
else if (elen != RARRAY(tmp)->len) {
rb_raise(rb_eIndexError, "element size differs (%d should be %d)",
RARRAY(tmp)->len, elen);
}
for (j=0; j<elen; j++) {
rb_ary_store(rb_ary_elt(result, j), i, rb_ary_elt(tmp, j));
}
}
return result;
}
static VALUE
rb_ary_replace(copy, orig)
VALUE copy, orig;
{
VALUE shared;
rb_ary_modify(copy);
orig = to_ary(orig);
if (copy == orig) return copy;
shared = ary_make_shared(orig);
if (RARRAY(copy)->ptr && !FL_TEST(copy, ELTS_SHARED))
free(RARRAY(copy)->ptr);
RARRAY(copy)->ptr = RARRAY(orig)->ptr;
RARRAY(copy)->len = RARRAY(orig)->len;
RARRAY(copy)->aux.shared = shared;
FL_SET(copy, ELTS_SHARED);
return copy;
}
VALUE
rb_ary_clear(ary)
VALUE ary;
{
rb_ary_modify(ary);
RARRAY(ary)->len = 0;
if (ARY_DEFAULT_SIZE * 2 < RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, ARY_DEFAULT_SIZE * 2);
RARRAY(ary)->aux.capa = ARY_DEFAULT_SIZE * 2;
}
return ary;
}
static VALUE
rb_ary_fill(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE item, arg1, arg2;
long beg = 0, end = 0, len = 0;
VALUE *p, *pend;
int block_p = Qfalse;
if (rb_block_given_p()) {
block_p = Qtrue;
rb_scan_args(argc, argv, "02", &arg1, &arg2);
argc += 1;
}
else {
rb_scan_args(argc, argv, "12", &item, &arg1, &arg2);
}
switch (argc) {
case 1:
beg = 0;
len = RARRAY(ary)->len;
break;
case 2:
if (rb_range_beg_len(arg1, &beg, &len, RARRAY(ary)->len, 1)) {
break;
}
case 3:
beg = NIL_P(arg1) ? 0 : NUM2LONG(arg1);
if (beg < 0) {
beg = RARRAY(ary)->len + beg;
if (beg < 0) beg = 0;
}
len = NIL_P(arg2) ? RARRAY(ary)->len - beg : NUM2LONG(arg2);
break;
}
rb_ary_modify(ary);
if (len < 0) {
return ary;
}
if (beg >= ARY_MAX_SIZE || len > ARY_MAX_SIZE - beg) {
rb_raise(rb_eArgError, "argument too big");
}
end = beg + len;
if (end > RARRAY(ary)->len) {
if (end >= RARRAY(ary)->aux.capa) {
REALLOC_N(RARRAY(ary)->ptr, VALUE, end);
RARRAY(ary)->aux.capa = end;
}
rb_mem_clear(RARRAY(ary)->ptr + RARRAY(ary)->len, end - RARRAY(ary)->len);
RARRAY(ary)->len = end;
}
if (block_p) {
VALUE v;
long i;
for (i=beg; i<end; i++) {
v = rb_yield(LONG2NUM(i));
if (i>=RARRAY(ary)->len) break;
RARRAY(ary)->ptr[i] = v;
}
}
else {
p = RARRAY(ary)->ptr + beg;
pend = p + len;
while (p < pend) {
*p++ = item;
}
}
return ary;
}
VALUE
rb_ary_plus(x, y)
VALUE x, y;
{
VALUE z;
long len;
y = to_ary(y);
len = RARRAY(x)->len + RARRAY(y)->len;
z = rb_ary_new2(len);
MEMCPY(RARRAY(z)->ptr, RARRAY(x)->ptr, VALUE, RARRAY(x)->len);
MEMCPY(RARRAY(z)->ptr + RARRAY(x)->len, RARRAY(y)->ptr, VALUE, RARRAY(y)->len);
RARRAY(z)->len = len;
return z;
}
VALUE
rb_ary_concat(x, y)
VALUE x, y;
{
y = to_ary(y);
if (RARRAY(y)->len > 0) {
rb_ary_splice(x, RARRAY(x)->len, 0, y);
}
return x;
}
static VALUE
rb_ary_times(ary, times)
VALUE ary, times;
{
VALUE ary2, tmp;
long i, len;
tmp = rb_check_string_type(times);
if (!NIL_P(tmp)) {
return rb_ary_join(ary, tmp);
}
len = NUM2LONG(times);
if (len == 0) return ary_new(rb_obj_class(ary), 0);
if (len < 0) {
rb_raise(rb_eArgError, "negative argument");
}
if (ARY_MAX_SIZE/len < RARRAY(ary)->len) {
rb_raise(rb_eArgError, "argument too big");
}
len *= RARRAY(ary)->len;
ary2 = ary_new(rb_obj_class(ary), len);
RARRAY(ary2)->len = len;
for (i=0; i<len; i+=RARRAY(ary)->len) {
MEMCPY(RARRAY(ary2)->ptr+i, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
}
OBJ_INFECT(ary2, ary);
return ary2;
}
VALUE
rb_ary_assoc(ary, key)
VALUE ary, key;
{
long i;
VALUE v;
for (i = 0; i < RARRAY(ary)->len; ++i) {
v = rb_check_array_type(RARRAY(ary)->ptr[i]);
if (!NIL_P(v) && RARRAY(v)->len > 0 &&
rb_equal(RARRAY(v)->ptr[0], key))
return v;
}
return Qnil;
}
VALUE
rb_ary_rassoc(ary, value)
VALUE ary, value;
{
long i;
VALUE v;
for (i = 0; i < RARRAY(ary)->len; ++i) {
v = RARRAY(ary)->ptr[i];
if (TYPE(v) == T_ARRAY &&
RARRAY(v)->len > 1 &&
rb_equal(RARRAY(v)->ptr[1], value))
return v;
}
return Qnil;
}
static VALUE recursive_equal _((VALUE, VALUE, int));
static VALUE
recursive_equal(ary1, ary2, recur)
VALUE ary1, ary2;
int recur;
{
long i;
if (recur) return Qfalse;
for (i=0; i<RARRAY(ary1)->len; i++) {
if (!rb_equal(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
return Qfalse;
}
return Qtrue;
}
static VALUE
rb_ary_equal(ary1, ary2)
VALUE ary1, ary2;
{
if (ary1 == ary2) return Qtrue;
if (TYPE(ary2) != T_ARRAY) {
if (!rb_respond_to(ary2, rb_intern("to_ary"))) {
return Qfalse;
}
return rb_equal(ary2, ary1);
}
if (RARRAY(ary1)->len != RARRAY(ary2)->len) return Qfalse;
return rb_exec_recursive(recursive_equal, ary1, ary2);
}
static VALUE recursive_eql _((VALUE, VALUE, int));
static VALUE
recursive_eql(ary1, ary2, recur)
VALUE ary1, ary2;
int recur;
{
long i;
if (recur) return Qfalse;
for (i=0; i<RARRAY(ary1)->len; i++) {
if (!rb_eql(rb_ary_elt(ary1, i), rb_ary_elt(ary2, i)))
return Qfalse;
}
return Qtrue;
}
static VALUE
rb_ary_eql(ary1, ary2)
VALUE ary1, ary2;
{
if (ary1 == ary2) return Qtrue;
if (TYPE(ary2) != T_ARRAY) return Qfalse;
if (RARRAY(ary1)->len != RARRAY(ary2)->len) return Qfalse;
return rb_exec_recursive(recursive_eql, ary1, ary2);
}
static VALUE recursive_hash _((VALUE, VALUE, int));
static VALUE
recursive_hash(ary, dummy, recur)
VALUE ary;
VALUE dummy;
int recur;
{
long i, h;
VALUE n;
if (recur) {
return LONG2FIX(0);
}
h = RARRAY(ary)->len;
for (i=0; i<RARRAY(ary)->len; i++) {
h = (h << 1) | (h<0 ? 1 : 0);
n = rb_hash(RARRAY(ary)->ptr[i]);
h ^= NUM2LONG(n);
}
return LONG2FIX(h);
}
static VALUE
rb_ary_hash(ary)
VALUE ary;
{
return rb_exec_recursive(recursive_hash, ary, 0);
}
VALUE
rb_ary_includes(ary, item)
VALUE ary;
VALUE item;
{
long i;
for (i=0; i<RARRAY(ary)->len; i++) {
if (rb_equal(RARRAY(ary)->ptr[i], item)) {
return Qtrue;
}
}
return Qfalse;
}
static VALUE recursive_cmp _((VALUE, VALUE, int));
static VALUE
recursive_cmp(ary1, ary2, recur)
VALUE ary1;
VALUE ary2;
int recur;
{
long i, len;
if (recur) return Qnil;
len = RARRAY(ary1)->len;
if (len > RARRAY(ary2)->len) {
len = RARRAY(ary2)->len;
}
for (i=0; i<len; i++) {
VALUE v = rb_funcall(rb_ary_elt(ary1, i), id_cmp, 1, rb_ary_elt(ary2, i));
if (v != INT2FIX(0)) {
return v;
}
}
return Qundef;
}
VALUE
rb_ary_cmp(ary1, ary2)
VALUE ary1, ary2;
{
long len;
VALUE v;
ary2 = to_ary(ary2);
if (ary1 == ary2) return INT2FIX(0);
v = rb_exec_recursive(recursive_cmp, ary1, ary2);
if (v != Qundef) return v;
len = RARRAY(ary1)->len - RARRAY(ary2)->len;
if (len == 0) return INT2FIX(0);
if (len > 0) return INT2FIX(1);
return INT2FIX(-1);
}
static VALUE
ary_make_hash(ary1, ary2)
VALUE ary1, ary2;
{
VALUE hash = rb_hash_new();
long i;
for (i=0; i<RARRAY(ary1)->len; i++) {
rb_hash_aset(hash, RARRAY(ary1)->ptr[i], Qtrue);
}
if (ary2) {
for (i=0; i<RARRAY(ary2)->len; i++) {
rb_hash_aset(hash, RARRAY(ary2)->ptr[i], Qtrue);
}
}
return hash;
}
static VALUE
rb_ary_diff(ary1, ary2)
VALUE ary1, ary2;
{
VALUE ary3;
volatile VALUE hash;
long i;
hash = ary_make_hash(to_ary(ary2), 0);
ary3 = rb_ary_new();
for (i=0; i<RARRAY(ary1)->len; i++) {
if (st_lookup(RHASH(hash)->tbl, RARRAY(ary1)->ptr[i], 0)) continue;
rb_ary_push(ary3, rb_ary_elt(ary1, i));
}
return ary3;
}
static VALUE
rb_ary_and(ary1, ary2)
VALUE ary1, ary2;
{
VALUE hash, ary3, v, vv;
long i;
ary2 = to_ary(ary2);
ary3 = rb_ary_new2(RARRAY(ary1)->len < RARRAY(ary2)->len ?
RARRAY(ary1)->len : RARRAY(ary2)->len);
hash = ary_make_hash(ary2, 0);
for (i=0; i<RARRAY(ary1)->len; i++) {
v = vv = rb_ary_elt(ary1, i);
if (st_delete(RHASH(hash)->tbl, (st_data_t*)&vv, 0)) {
rb_ary_push(ary3, v);
}
}
return ary3;
}
static VALUE
rb_ary_or(ary1, ary2)
VALUE ary1, ary2;
{
VALUE hash, ary3;
VALUE v, vv;
long i;
ary2 = to_ary(ary2);
ary3 = rb_ary_new2(RARRAY(ary1)->len+RARRAY(ary2)->len);
hash = ary_make_hash(ary1, ary2);
for (i=0; i<RARRAY(ary1)->len; i++) {
v = vv = rb_ary_elt(ary1, i);
if (st_delete(RHASH(hash)->tbl, (st_data_t*)&vv, 0)) {
rb_ary_push(ary3, v);
}
}
for (i=0; i<RARRAY(ary2)->len; i++) {
v = vv = rb_ary_elt(ary2, i);
if (st_delete(RHASH(hash)->tbl, (st_data_t*)&vv, 0)) {
rb_ary_push(ary3, v);
}
}
return ary3;
}
static VALUE
rb_ary_uniq_bang(ary)
VALUE ary;
{
VALUE hash, v, vv;
long i, j;
hash = ary_make_hash(ary, 0);
if (RARRAY(ary)->len == RHASH(hash)->tbl->num_entries) {
return Qnil;
}
for (i=j=0; i<RARRAY(ary)->len; i++) {
v = vv = rb_ary_elt(ary, i);
if (st_delete(RHASH(hash)->tbl, (st_data_t*)&vv, 0)) {
rb_ary_store(ary, j++, v);
}
}
RARRAY(ary)->len = j;
return ary;
}
static VALUE
rb_ary_uniq(ary)
VALUE ary;
{
ary = rb_ary_dup(ary);
rb_ary_uniq_bang(ary);
return ary;
}
static VALUE
rb_ary_compact_bang(ary)
VALUE ary;
{
VALUE *p, *t, *end;
rb_ary_modify(ary);
p = t = RARRAY(ary)->ptr;
end = p + RARRAY(ary)->len;
while (t < end) {
if (NIL_P(*t)) t++;
else *p++ = *t++;
}
if (RARRAY(ary)->len == (p - RARRAY(ary)->ptr)) {
return Qnil;
}
RARRAY(ary)->len = RARRAY(ary)->aux.capa = (p - RARRAY(ary)->ptr);
REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
return ary;
}
static VALUE
rb_ary_compact(ary)
VALUE ary;
{
ary = rb_ary_dup(ary);
rb_ary_compact_bang(ary);
return ary;
}
static VALUE
rb_ary_nitems(ary)
VALUE ary;
{
long n = 0;
VALUE *p, *pend;
for (p = RARRAY(ary)->ptr, pend = p + RARRAY(ary)->len; p < pend; p++) {
if (!NIL_P(*p)) n++;
}
return LONG2NUM(n);
}
static VALUE
rb_ary_count(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
long n = 0;
if (argc == 0) {
VALUE *p, *pend;
if (!rb_block_given_p())
return LONG2NUM(RARRAY_LEN(ary));
for (p = RARRAY_PTR(ary), pend = p + RARRAY_LEN(ary); p < pend; p++) {
if (RTEST(rb_yield(*p))) n++;
}
}
else {
VALUE obj, *p, *pend;
rb_scan_args(argc, argv, "1", &obj);
if (rb_block_given_p()) {
rb_warn("given block not used");
}
for (p = RARRAY_PTR(ary), pend = p + RARRAY_LEN(ary); p < pend; p++) {
if (rb_equal(*p, obj)) n++;
}
}
return LONG2NUM(n);
}
static VALUE
flatten(ary, level, modified)
VALUE ary;
int level;
int *modified;
{
long i = 0;
VALUE stack, result, tmp, elt;
st_table *memo;
st_data_t id;
stack = ary_new(0, ARY_DEFAULT_SIZE);
result = ary_new(0, RARRAY_LEN(ary));
memo = st_init_numtable();
st_insert(memo, (st_data_t)ary, (st_data_t)Qtrue);
*modified = 0;
while (1) {
while (i < RARRAY(ary)->len) {
elt = RARRAY(ary)->ptr[i++];
tmp = rb_check_array_type(elt);
if (RBASIC(result)->klass) {
rb_raise(rb_eRuntimeError, "flatten reentered");
}
if (NIL_P(tmp) || (level >= 0 && RARRAY(stack)->len / 2 >= level)) {
rb_ary_push(result, elt);
}
else {
*modified = 1;
id = (st_data_t)tmp;
if (st_lookup(memo, id, 0)) {
st_free_table(memo);
rb_raise(rb_eArgError, "tried to flatten recursive array");
}
st_insert(memo, id, (st_data_t)Qtrue);
rb_ary_push(stack, ary);
rb_ary_push(stack, LONG2NUM(i));
ary = tmp;
i = 0;
}
}
if (RARRAY(stack)->len == 0) {
break;
}
id = (st_data_t)ary;
st_delete(memo, &id, 0);
tmp = rb_ary_pop(stack);
i = NUM2LONG(tmp);
ary = rb_ary_pop(stack);
}
st_free_table(memo);
RBASIC(result)->klass = rb_class_of(ary);
return result;
}
static VALUE
rb_ary_flatten_bang(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
int mod = 0, level = -1;
VALUE result, lv;
rb_scan_args(argc, argv, "01", &lv);
if (!NIL_P(lv)) level = NUM2INT(lv);
if (level == 0) return ary;
result = flatten(ary, level, &mod);
if (mod == 0) return Qnil;
rb_ary_replace(ary, result);
return ary;
}
static VALUE
rb_ary_flatten(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
int mod = 0, level = -1;
VALUE result, lv;
rb_scan_args(argc, argv, "01", &lv);
if (!NIL_P(lv)) level = NUM2INT(lv);
if (level == 0) return ary;
result = flatten(ary, level, &mod);
if (OBJ_TAINTED(ary)) OBJ_TAINT(result);
return result;
}
static VALUE
rb_ary_shuffle_bang(ary)
VALUE ary;
{
long i = RARRAY(ary)->len;
rb_ary_modify(ary);
while (i) {
long j = rb_genrand_real()*i;
VALUE tmp = RARRAY(ary)->ptr[--i];
RARRAY(ary)->ptr[i] = RARRAY(ary)->ptr[j];
RARRAY(ary)->ptr[j] = tmp;
}
return ary;
}
static VALUE
rb_ary_shuffle(VALUE ary)
{
ary = rb_ary_dup(ary);
rb_ary_shuffle_bang(ary);
return ary;
}
static VALUE
rb_ary_choice(ary)
VALUE ary;
{
long i, j;
i = RARRAY(ary)->len;
if (i == 0) return Qnil;
j = rb_genrand_real()*i;
return RARRAY(ary)->ptr[j];
}
static VALUE
rb_ary_cycle(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
long n, i;
VALUE nv = Qnil;
rb_scan_args(argc, argv, "01", &nv);
RETURN_ENUMERATOR(ary, argc, argv);
if (NIL_P(nv)) {
n = -1;
}
else {
n = NUM2LONG(nv);
if (n <= 0) return Qnil;
}
while (RARRAY(ary)->len > 0 && (n < 0 || 0 < n--)) {
for (i=0; i<RARRAY(ary)->len; i++) {
rb_yield(RARRAY(ary)->ptr[i]);
}
}
return Qnil;
}
#define tmpbuf(n, size) rb_str_tmp_new((n)*(size))
static void
permute0(n, r, p, index, used, values)
long n, r, *p, index;
int *used;
VALUE values;
{
long i,j;
for (i = 0; i < n; i++) {
if (used[i] == 0) {
p[index] = i;
if (index < r-1) {
used[i] = 1;
permute0(n, r, p, index+1,
used, values);
used[i] = 0;
}
else {
VALUE result = rb_ary_new2(r);
VALUE *result_array = RARRAY(result)->ptr;
const VALUE *values_array = RARRAY(values)->ptr;
for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
RARRAY(result)->len = r;
rb_yield(result);
}
}
}
}
static VALUE
rb_ary_permutation(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
VALUE num;
long r, n, i;
n = RARRAY(ary)->len;
RETURN_ENUMERATOR(ary, argc, argv);
rb_scan_args(argc, argv, "01", &num);
r = NIL_P(num) ? n : NUM2LONG(num);
if (r < 0 || n < r) {
}
else if (r == 0) {
rb_yield(rb_ary_new2(0));
}
else if (r == 1) {
for (i = 0; i < RARRAY(ary)->len; i++) {
rb_yield(rb_ary_new3(1, RARRAY(ary)->ptr[i]));
}
}
else {
volatile VALUE t0 = tmpbuf(n,sizeof(long));
long *p = (long*)RSTRING(t0)->ptr;
volatile VALUE t1 = tmpbuf(n,sizeof(int));
int *used = (int*)RSTRING(t1)->ptr;
VALUE ary0 = ary_make_shared(ary);
for (i = 0; i < n; i++) used[i] = 0;
permute0(n, r, p, 0, used, ary0);
RB_GC_GUARD(t0);
RB_GC_GUARD(t1);
}
return ary;
}
static long
combi_len(n, k)
long n, k;
{
long i, val = 1;
if (k*2 > n) k = n-k;
if (k == 0) return 1;
if (k < 0) return 0;
val = 1;
for (i=1; i <= k; i++,n--) {
long m = val;
val *= n;
if (val < m) {
rb_raise(rb_eRangeError, "too big for combination");
}
val /= i;
}
return val;
}
static VALUE
rb_ary_combination(ary, num)
VALUE ary;
VALUE num;
{
long n, i, len;
n = NUM2LONG(num);
RETURN_ENUMERATOR(ary, 1, &num);
len = RARRAY(ary)->len;
if (n < 0 || len < n) {
}
else if (n == 0) {
rb_yield(rb_ary_new2(0));
}
else if (n == 1) {
for (i = 0; i < len; i++) {
rb_yield(rb_ary_new3(1, RARRAY(ary)->ptr[i]));
}
}
else {
volatile VALUE t0 = tmpbuf(n+1, sizeof(long));
long *stack = (long*)RSTRING(t0)->ptr;
long nlen = combi_len(len, n);
volatile VALUE cc = rb_ary_new2(n);
VALUE *chosen = RARRAY(cc)->ptr;
long lev = 0;
RBASIC(cc)->klass = 0;
MEMZERO(stack, long, n);
stack[0] = -1;
for (i = 0; i < nlen; i++) {
chosen[lev] = RARRAY(ary)->ptr[stack[lev+1]];
for (lev++; lev < n; lev++) {
chosen[lev] = RARRAY(ary)->ptr[stack[lev+1] = stack[lev]+1];
}
rb_yield(rb_ary_new4(n, chosen));
do {
stack[lev--]++;
} while (lev && (stack[lev+1]+n == len+lev+1));
}
}
return ary;
}
static VALUE
rb_ary_product(argc, argv, ary)
int argc;
VALUE *argv;
VALUE ary;
{
int n = argc+1;
volatile VALUE t0 = tmpbuf(n, sizeof(VALUE));
volatile VALUE t1 = tmpbuf(n, sizeof(int));
VALUE *arrays = (VALUE*)RSTRING(t0)->ptr;
int *counters = (int*)RSTRING(t1)->ptr;
VALUE result;
long i,j;
long resultlen = 1;
RBASIC(t0)->klass = 0;
RBASIC(t1)->klass = 0;
arrays[0] = ary;
for (i = 1; i < n; i++) arrays[i] = to_ary(argv[i-1]);
for (i = 0; i < n; i++) counters[i] = 0;
for (i = 0; i < n; i++) {
long k = RARRAY(arrays[i])->len, l = resultlen;
if (k == 0) return rb_ary_new2(0);
resultlen *= k;
if (resultlen < k || resultlen < l || resultlen / k != l) {
rb_raise(rb_eRangeError, "too big to product");
}
}
result = rb_ary_new2(resultlen);
for (i = 0; i < resultlen; i++) {
int m;
VALUE subarray = rb_ary_new2(n);
for (j = 0; j < n; j++) {
rb_ary_push(subarray, rb_ary_entry(arrays[j], counters[j]));
}
rb_ary_push(result, subarray);
m = n-1;
counters[m]++;
while (m > 0 && counters[m] == RARRAY(arrays[m])->len) {
counters[m] = 0;
m--;
counters[m]++;
}
}
return result;
}
static VALUE
rb_ary_take(obj, n)
VALUE obj;
VALUE n;
{
long len = NUM2LONG(n);
if (len < 0) {
rb_raise(rb_eArgError, "attempt to take negative size");
}
return rb_ary_subseq(obj, 0, len);
}
static VALUE
rb_ary_take_while(ary)
VALUE ary;
{
long i;
RETURN_ENUMERATOR(ary, 0, 0);
for (i = 0; i < RARRAY(ary)->len; i++) {
if (!RTEST(rb_yield(RARRAY(ary)->ptr[i]))) break;
}
return rb_ary_take(ary, LONG2FIX(i));
}
static VALUE
rb_ary_drop(ary, n)
VALUE ary;
VALUE n;
{
VALUE result;
long pos = NUM2LONG(n);
if (pos < 0) {
rb_raise(rb_eArgError, "attempt to drop negative size");
}
result = rb_ary_subseq(ary, pos, RARRAY(ary)->len);
if (result == Qnil) result = rb_ary_new();
return result;
}
static VALUE
rb_ary_drop_while(ary)
VALUE ary;
{
long i;
RETURN_ENUMERATOR(ary, 0, 0);
for (i = 0; i < RARRAY(ary)->len; i++) {
if (!RTEST(rb_yield(RARRAY(ary)->ptr[i]))) break;
}
return rb_ary_drop(ary, LONG2FIX(i));
}
void
Init_Array()
{
rb_cArray = rb_define_class("Array", rb_cObject);
rb_include_module(rb_cArray, rb_mEnumerable);
rb_define_alloc_func(rb_cArray, ary_alloc);
rb_define_singleton_method(rb_cArray, "[]", rb_ary_s_create, -1);
rb_define_method(rb_cArray, "initialize", rb_ary_initialize, -1);
rb_define_method(rb_cArray, "initialize_copy", rb_ary_replace, 1);
rb_define_method(rb_cArray, "to_s", rb_ary_to_s, 0);
rb_define_method(rb_cArray, "inspect", rb_ary_inspect, 0);
rb_define_method(rb_cArray, "to_a", rb_ary_to_a, 0);
rb_define_method(rb_cArray, "to_ary", rb_ary_to_ary_m, 0);
rb_define_method(rb_cArray, "frozen?", rb_ary_frozen_p, 0);
rb_define_method(rb_cArray, "==", rb_ary_equal, 1);
rb_define_method(rb_cArray, "eql?", rb_ary_eql, 1);
rb_define_method(rb_cArray, "hash", rb_ary_hash, 0);
rb_define_method(rb_cArray, "[]", rb_ary_aref, -1);
rb_define_method(rb_cArray, "[]=", rb_ary_aset, -1);
rb_define_method(rb_cArray, "at", rb_ary_at, 1);
rb_define_method(rb_cArray, "fetch", rb_ary_fetch, -1);
rb_define_method(rb_cArray, "first", rb_ary_first, -1);
rb_define_method(rb_cArray, "last", rb_ary_last, -1);
rb_define_method(rb_cArray, "concat", rb_ary_concat, 1);
rb_define_method(rb_cArray, "<<", rb_ary_push, 1);
rb_define_method(rb_cArray, "push", rb_ary_push_m, -1);
rb_define_method(rb_cArray, "pop", rb_ary_pop_m, -1);
rb_define_method(rb_cArray, "shift", rb_ary_shift_m, -1);
rb_define_method(rb_cArray, "unshift", rb_ary_unshift_m, -1);
rb_define_method(rb_cArray, "insert", rb_ary_insert, -1);
rb_define_method(rb_cArray, "each", rb_ary_each, 0);
rb_define_method(rb_cArray, "each_index", rb_ary_each_index, 0);
rb_define_method(rb_cArray, "reverse_each", rb_ary_reverse_each, 0);
rb_define_method(rb_cArray, "length", rb_ary_length, 0);
rb_define_alias(rb_cArray, "size", "length");
rb_define_method(rb_cArray, "empty?", rb_ary_empty_p, 0);
rb_define_method(rb_cArray, "find_index", rb_ary_index, -1);
rb_define_method(rb_cArray, "index", rb_ary_index, -1);
rb_define_method(rb_cArray, "rindex", rb_ary_rindex, -1);
rb_define_method(rb_cArray, "indexes", rb_ary_indexes, -1);
rb_define_method(rb_cArray, "indices", rb_ary_indexes, -1);
rb_define_method(rb_cArray, "join", rb_ary_join_m, -1);
rb_define_method(rb_cArray, "reverse", rb_ary_reverse_m, 0);
rb_define_method(rb_cArray, "reverse!", rb_ary_reverse_bang, 0);
rb_define_method(rb_cArray, "sort", rb_ary_sort, 0);
rb_define_method(rb_cArray, "sort!", rb_ary_sort_bang, 0);
rb_define_method(rb_cArray, "collect", rb_ary_collect, 0);
rb_define_method(rb_cArray, "collect!", rb_ary_collect_bang, 0);
rb_define_method(rb_cArray, "map", rb_ary_collect, 0);
rb_define_method(rb_cArray, "map!", rb_ary_collect_bang, 0);
rb_define_method(rb_cArray, "select", rb_ary_select, 0);
rb_define_method(rb_cArray, "values_at", rb_ary_values_at, -1);
rb_define_method(rb_cArray, "delete", rb_ary_delete, 1);
rb_define_method(rb_cArray, "delete_at", rb_ary_delete_at_m, 1);
rb_define_method(rb_cArray, "delete_if", rb_ary_delete_if, 0);
rb_define_method(rb_cArray, "reject", rb_ary_reject, 0);
rb_define_method(rb_cArray, "reject!", rb_ary_reject_bang, 0);
rb_define_method(rb_cArray, "zip", rb_ary_zip, -1);
rb_define_method(rb_cArray, "transpose", rb_ary_transpose, 0);
rb_define_method(rb_cArray, "replace", rb_ary_replace, 1);
rb_define_method(rb_cArray, "clear", rb_ary_clear, 0);
rb_define_method(rb_cArray, "fill", rb_ary_fill, -1);
rb_define_method(rb_cArray, "include?", rb_ary_includes, 1);
rb_define_method(rb_cArray, "<=>", rb_ary_cmp, 1);
rb_define_method(rb_cArray, "slice", rb_ary_aref, -1);
rb_define_method(rb_cArray, "slice!", rb_ary_slice_bang, -1);
rb_define_method(rb_cArray, "assoc", rb_ary_assoc, 1);
rb_define_method(rb_cArray, "rassoc", rb_ary_rassoc, 1);
rb_define_method(rb_cArray, "+", rb_ary_plus, 1);
rb_define_method(rb_cArray, "*", rb_ary_times, 1);
rb_define_method(rb_cArray, "-", rb_ary_diff, 1);
rb_define_method(rb_cArray, "&", rb_ary_and, 1);
rb_define_method(rb_cArray, "|", rb_ary_or, 1);
rb_define_method(rb_cArray, "uniq", rb_ary_uniq, 0);
rb_define_method(rb_cArray, "uniq!", rb_ary_uniq_bang, 0);
rb_define_method(rb_cArray, "compact", rb_ary_compact, 0);
rb_define_method(rb_cArray, "compact!", rb_ary_compact_bang, 0);
rb_define_method(rb_cArray, "flatten", rb_ary_flatten, -1);
rb_define_method(rb_cArray, "flatten!", rb_ary_flatten_bang, -1);
rb_define_method(rb_cArray, "nitems", rb_ary_nitems, 0);
rb_define_method(rb_cArray, "count", rb_ary_count, -1);
rb_define_method(rb_cArray, "shuffle!", rb_ary_shuffle_bang, 0);
rb_define_method(rb_cArray, "shuffle", rb_ary_shuffle, 0);
rb_define_method(rb_cArray, "choice", rb_ary_choice, 0);
rb_define_method(rb_cArray, "cycle", rb_ary_cycle, -1);
rb_define_method(rb_cArray, "permutation", rb_ary_permutation, -1);
rb_define_method(rb_cArray, "combination", rb_ary_combination, 1);
rb_define_method(rb_cArray, "product", rb_ary_product, -1);
rb_define_method(rb_cArray, "take", rb_ary_take, 1);
rb_define_method(rb_cArray, "take_while", rb_ary_take_while, 0);
rb_define_method(rb_cArray, "drop", rb_ary_drop, 1);
rb_define_method(rb_cArray, "drop_while", rb_ary_drop_while, 0);
id_cmp = rb_intern("<=>");
inspect_key = rb_intern("__inspect_key__");
}