summaryrefslogtreecommitdiff
path: root/array.c
diff options
context:
space:
mode:
Diffstat (limited to 'array.c')
-rw-r--r--array.c805
1 files changed, 805 insertions, 0 deletions
diff --git a/array.c b/array.c
new file mode 100644
index 0000000000..91c06a3f6f
--- /dev/null
+++ b/array.c
@@ -0,0 +1,805 @@
+/************************************************
+
+ array.c -
+
+ $Author: matz $
+ $Date: 1994/06/27 15:48:20 $
+ created at: Fri Aug 6 09:46:12 JST 1993
+
+ Copyright (C) 1994 Yukihiro Matsumoto
+
+************************************************/
+
+#include "ruby.h"
+
+VALUE C_Array;
+
+static ID eq;
+
+#define ARY_DEFAULT_SIZE 16
+
+VALUE
+ary_new2(len)
+{
+ NEWOBJ(ary, struct RArray);
+ OBJSETUP(ary, C_Array, T_ARRAY);
+
+ GC_LINK;
+ GC_PRO(ary);
+ ary->len = 0;
+ ary->capa = len;
+ ary->ptr = ALLOC_N(VALUE, len);
+ GC_UNLINK;
+
+ return (VALUE)ary;
+}
+
+VALUE
+ary_new()
+{
+ return ary_new2(ARY_DEFAULT_SIZE);
+}
+
+#include <varargs.h>
+
+VALUE
+ary_new3(n, va_alist)
+ int n;
+ va_dcl
+{
+ va_list ar;
+ struct RArray* ary;
+ int len, i;
+
+ if (n < 0) {
+ Fail("Negative number of items(%d)", n);
+ }
+ ary = (struct RArray*)ary_new2(n<ARY_DEFAULT_SIZE?ARY_DEFAULT_SIZE:n);
+
+ va_start(ar);
+ for (i=0; i<n; i++) {
+ ary->ptr[i] = va_arg(ar, VALUE);
+ }
+ va_end(ar);
+
+ ary->len = n;
+ return (VALUE)ary;
+}
+
+VALUE
+ary_new4(n, elts)
+ int n;
+ VALUE *elts;
+{
+ struct RArray* ary;
+
+ GC_LINK;
+ GC_PRO4(elts, n);
+ ary = (struct RArray*)ary_new2(n);
+ memcpy(ary->ptr, elts, sizeof(VALUE)*n);
+ ary->len = n;
+ GC_UNLINK;
+
+ return (VALUE)ary;
+}
+
+VALUE
+assoc_new(elm1, elm2)
+ VALUE elm1, elm2;
+{
+ struct RArray *ary;
+
+ GC_LINK;
+ GC_PRO(elm1); GC_PRO(elm2);
+ ary = (struct RArray*)ary_new2(2);
+ ary->ptr[0] = elm1;
+ ary->ptr[1] = elm2;
+ ary->len = 2;
+ GC_UNLINK;
+
+ return (VALUE)ary;
+}
+
+static VALUE
+Fary_new(class)
+ VALUE class;
+{
+ NEWOBJ(ary, struct RArray);
+ OBJSETUP(ary, class, T_ARRAY);
+
+ GC_LINK;
+ GC_PRO(ary);
+ ary->len = 0;
+ ary->capa = ARY_DEFAULT_SIZE;
+ ary->ptr = ALLOC_N(VALUE, ARY_DEFAULT_SIZE);
+ GC_UNLINK;
+
+ return (VALUE)ary;
+}
+
+static void
+astore(ary, idx, val)
+ struct RArray *ary;
+ int idx;
+ VALUE val;
+{
+ int max;
+
+ if (idx < 0) {
+ Fail("negative index for array");
+ }
+
+ max = idx + 1;
+ if (idx >= ary->capa) {
+ GC_LINK; GC_PRO(val);
+ ary->capa = max;
+ REALLOC_N(ary->ptr, VALUE, max);
+ GC_UNLINK;
+ }
+ if (idx >= ary->len) {
+ bzero(ary->ptr+ary->len, sizeof(VALUE)*(max-ary->len));
+ }
+
+ if (idx >= ary->len) {
+ ary->len = idx + 1;
+ }
+ ary->ptr[idx] = val;
+}
+
+VALUE
+Fary_push(ary, item)
+ struct RArray *ary;
+ VALUE item;
+{
+ astore(ary, ary->len, item);
+ return item;
+}
+
+static VALUE
+Fary_append(ary, item)
+ struct RArray *ary;
+ VALUE item;
+{
+ astore(ary, ary->len, item);
+ return (VALUE)ary;
+}
+
+VALUE
+Fary_pop(ary)
+ struct RArray *ary;
+{
+ if (ary->len == 0) return Qnil;
+ return ary->ptr[--ary->len];
+}
+
+VALUE
+Fary_shift(ary)
+ struct RArray *ary;
+{
+ VALUE top;
+
+ if (ary->len == 0) return Qnil;
+
+ top = ary->ptr[0];
+ ary->len--;
+
+ /* sliding items */
+ memmove(ary->ptr, ary->ptr+1, sizeof(VALUE)*(ary->len));
+
+ return top;
+}
+
+VALUE
+Fary_unshift(ary, item)
+ struct RArray *ary;
+{
+ VALUE top;
+
+ if (ary->len >= ary->capa) {
+ ary->capa+=ARY_DEFAULT_SIZE;
+ REALLOC_N(ary->ptr, VALUE, ary->capa);
+ }
+
+ /* sliding items */
+ memmove(ary->ptr+1, ary->ptr, sizeof(VALUE)*(ary->len));
+
+ ary->len++;
+ return ary->ptr[0] = item;
+}
+
+VALUE
+ary_entry(ary, offset)
+ struct RArray *ary;
+ int offset;
+{
+ if (ary->len == 0) return Qnil;
+
+ if (offset < 0) {
+ offset = ary->len + offset;
+ }
+ if (offset < 0 || ary->len <= offset) {
+ return Qnil;
+ }
+
+ return ary->ptr[offset];
+}
+
+static VALUE
+ary_subseq(ary, beg, len)
+ struct RArray *ary;
+ int beg, len;
+{
+ struct RArray *ary2;
+ VALUE *ptr;
+
+ if (beg < 0) {
+ beg = ary->len + beg;
+ if (beg < 0) beg = 0;
+ }
+ if (len < 0) {
+ Fail("negative length for sub-array(size: %d)", ary->len);
+ }
+ if (len == 0) {
+ return ary_new();
+ }
+ if (beg + len > ary->len) {
+ len = ary->len - beg;
+ }
+
+ ary2 = (struct RArray*)ary_new2(len);
+ memmove(ary2->ptr, ary->ptr+beg, sizeof(VALUE)*len);
+ ary2->len = len;
+
+ return (VALUE)ary2;
+}
+
+extern VALUE C_Range;
+
+static void
+range_beg_end(range, begp, lenp, len)
+ VALUE range;
+ int *begp, *lenp;
+ int len;
+{
+ int beg, end;
+
+ beg = rb_iv_get(range, "start"); beg = NUM2INT(beg);
+ end = rb_iv_get(range, "end"); end = NUM2INT(end);
+ if (beg < 0) {
+ beg = len + beg;
+ if (beg < 0) beg = 0;
+ }
+ if (end < 0) {
+ end = len + end;
+ if (end < 0) end = 0;
+ }
+ if (beg > end) {
+ int tmp;
+
+ if (verbose) {
+ Warning("start %d is bigger than end %d", beg, end);
+ }
+ tmp = beg; beg = end; end = tmp;
+ }
+ *begp = beg; *lenp = end - beg + 1;
+}
+
+static VALUE
+Fary_aref(ary, args)
+ struct RArray *ary;
+ VALUE args;
+{
+ VALUE arg1, arg2;
+
+ if (rb_scan_args(args, "11", &arg1, &arg2) == 2) {
+ int beg, len;
+
+ beg = NUM2INT(arg1);
+ len = NUM2INT(arg2);
+ if (len <= 0) {
+ return ary_new();
+ }
+ return ary_subseq(ary, beg, len);
+ }
+
+ /* check if idx is Range */
+ if (obj_is_kind_of(arg1, C_Range)) {
+ int beg, len;
+
+ range_beg_end(arg1, &beg, &len, ary->len);
+ return ary_subseq(ary, beg, len);
+ }
+
+ return ary_entry(ary, NUM2INT(arg1));
+}
+
+static VALUE
+Fary_aset(ary, args)
+ struct RArray *ary;
+ VALUE args;
+{
+ VALUE arg1, arg2;
+ struct RArray *arg3;
+ int offset;
+
+ if (rb_scan_args(args, "21", &arg1, &arg2, &arg3) == 3) {
+ int beg, len;
+
+ beg = NUM2INT(arg1);
+ Check_Type(arg3, T_ARRAY);
+ if (beg < 0) {
+ beg = ary->len + beg;
+ if (beg < 0) {
+ Fail("negative index for array(size: %d)", ary->len);
+ }
+ }
+ if (beg >= ary->len) {
+ len = beg + arg3->len;
+ if (len >= ary->capa) {
+ ary->capa=len;
+ REALLOC_N(ary->ptr, VALUE, ary->capa);
+ }
+ bzero(ary->ptr+ary->len, sizeof(VALUE)*(beg-ary->len));
+ memcpy(ary->ptr+beg, arg3->ptr, sizeof(VALUE)*arg3->len);
+ ary->len = len;
+ }
+ else {
+ int alen;
+
+ len = NUM2INT(arg2);
+ if (beg + len > ary->len) {
+ len = ary->len - beg;
+ }
+ if (len < 0) {
+ Fail("negative length for sub-array(size: %d)", ary->len);
+ }
+
+ alen = ary->len + arg3->len - len;
+ if (alen >= ary->capa) {
+ ary->capa=alen;
+ REALLOC_N(ary->ptr, VALUE, ary->capa);
+ }
+
+ memmove(ary->ptr+beg+arg3->len, ary->ptr+beg+len,
+ sizeof(VALUE)*(ary->len-(beg+len)));
+ memmove(ary->ptr+beg, arg3->ptr, sizeof(VALUE)*arg3->len);
+ ary->len = alen;
+ }
+ return (VALUE)arg3;
+ }
+
+ /* check if idx is Range */
+ if (obj_is_kind_of(arg1, C_Range)) {
+ int beg, len;
+
+ Check_Type(arg2, T_ARRAY);
+ range_beg_end(arg1, &beg, &len, ary->len);
+ if (ary->len < beg) {
+ len = beg + RARRAY(arg2)->len;
+ if (len >= ary->capa) {
+ ary->capa=len;
+ REALLOC_N(ary->ptr, VALUE, ary->capa);
+ }
+ bzero(ary->ptr+ary->len, sizeof(VALUE)*(beg-ary->len));
+ memcpy(ary->ptr+beg, RARRAY(arg2)->ptr,
+ sizeof(VALUE)*RARRAY(arg2)->len);
+ ary->len = len;
+ }
+ else {
+ int alen;
+
+ alen = ary->len + RARRAY(arg2)->len - len;
+ if (alen >= ary->capa) {
+ ary->capa=alen;
+ REALLOC_N(ary->ptr, VALUE, ary->capa);
+ }
+
+ memmove(ary->ptr+beg+RARRAY(arg2)->len, ary->ptr+beg+len,
+ sizeof(VALUE)*(ary->len-(beg+len)));
+ memmove(ary->ptr+beg, RARRAY(arg2)->ptr,
+ sizeof(VALUE)*RARRAY(arg2)->len);
+ ary->len = alen;
+ }
+ return arg2;
+ }
+
+ offset = NUM2INT(arg1);
+ if (offset < 0) {
+ offset = ary->len + offset;
+ }
+ astore(ary, offset, arg2);
+ return arg2;
+}
+
+static VALUE
+Fary_each(ary)
+ struct RArray *ary;
+{
+ int i;
+
+ if (iterator_p()) {
+ for (i=0; i<ary->len; i++) {
+ rb_yield(ary->ptr[i]);
+ }
+ }
+ else {
+ return (VALUE)ary;
+ }
+}
+
+static VALUE
+Fary_length(ary)
+ struct RArray *ary;
+{
+ return INT2FIX(ary->len);
+}
+
+static VALUE
+Fary_clone(ary)
+ struct RArray *ary;
+{
+ VALUE ary2 = ary_new2(ary->len);
+
+ CLONESETUP(ary2, ary);
+ memcpy(RARRAY(ary2)->ptr, ary->ptr, sizeof(VALUE)*ary->len);
+ RARRAY(ary2)->len = ary->len;
+ return ary2;
+}
+
+extern VALUE OFS;
+
+VALUE
+ary_join(ary, sep)
+ struct RArray *ary;
+ struct RString *sep;
+{
+ int i;
+ VALUE result, tmp;
+ if (ary->len == 0) return str_new(0, 0);
+
+ if (TYPE(ary->ptr[0]) == T_STRING)
+ result = Fstr_clone(ary->ptr[0]);
+ else
+ result = obj_as_string(ary->ptr[0]);
+
+ GC_LINK;
+ GC_PRO(result);
+ GC_PRO2(tmp);
+
+ for (i=1; i<ary->len; i++) {
+ int need_free = 1;
+ tmp = ary->ptr[i];
+ switch (TYPE(tmp)) {
+ case T_STRING:
+ need_free = 0;
+ break;
+ case T_ARRAY:
+ tmp = ary_join(tmp, sep);
+ break;
+ default:
+ tmp = obj_as_string(tmp);
+ }
+ if (sep) str_cat(result, sep->ptr, sep->len);
+ str_cat(result, RSTRING(tmp)->ptr, RSTRING(tmp)->len);
+ if (need_free == 1) obj_free(tmp);
+ }
+
+ GC_UNLINK;
+
+ return result;
+}
+
+static VALUE
+Fary_join(ary, args)
+ struct RArray *ary;
+ VALUE args;
+{
+ VALUE sep;
+
+ rb_scan_args(args, "01", &sep);
+ if (sep == Qnil) sep = OFS;
+
+ if (sep != Qnil)
+ Check_Type(sep, T_STRING);
+
+ return ary_join(ary, sep);
+}
+
+VALUE
+Fary_to_s(ary)
+ VALUE ary;
+{
+ VALUE str = ary_join(ary, OFS);
+ if (str == Qnil) return str_new(0, 0);
+ return str;
+}
+
+static VALUE
+Fary_inspect(ary)
+ struct RArray *ary;
+{
+ int i, len;
+ VALUE str;
+ char *p;
+
+ ary = (struct RArray*)Fary_clone(ary);
+ GC_LINK;
+ GC_PRO(ary);
+
+ len = ary->len;
+ for (i=0; i<len; i++) {
+ ary->ptr[i] = rb_funcall(ary->ptr[i], rb_intern("_inspect"), 0, Qnil);
+ }
+
+ GC_PRO3(str, str_new2(", "));
+ str = ary_join(ary, str);
+ if (str == Qnil) return str_new2("[]");
+ len = RSTRING(str)->len;
+ str_grow(str, len+2);
+ p = RSTRING(str)->ptr;
+ memmove(p+1, p, len);
+ p[0] = '[';
+ p[len+1] = ']';
+
+ GC_UNLINK;
+
+ return str;
+}
+
+static VALUE
+Fary_to_a(ary)
+ VALUE ary;
+{
+ return ary;
+}
+
+static VALUE
+Fary_reverse(ary)
+ struct RArray *ary;
+{
+ VALUE ary2 = ary_new2(ary->len);
+ int i, j;
+
+ for (i=ary->len-1, j=0; i >=0; i--, j++) {
+ RARRAY(ary2)->ptr[j] = ary->ptr[i];
+ }
+ RARRAY(ary2)->len = ary->len;
+
+ return ary2;
+}
+
+static ID cmp;
+
+static int
+sort_1(a, b)
+ VALUE *a, *b;
+{
+ VALUE retval = rb_yield(assoc_new(*a, *b));
+ return NUM2INT(retval);
+}
+
+static int
+sort_2(a, b)
+ VALUE *a, *b;
+{
+ VALUE retval = rb_funcall(*a, cmp, 1, *b);
+ return NUM2INT(retval);
+}
+
+VALUE
+Fary_sort(ary)
+ struct RArray *ary;
+{
+ qsort(ary->ptr, ary->len, sizeof(VALUE), iterator_p()?sort_1:sort_2);
+ return (VALUE)ary;
+}
+
+static VALUE
+Fary_delete(ary, item)
+ struct RArray *ary;
+ VALUE item;
+{
+ int i1, i2;
+
+ for (i1 = i2 = 0; i1 < ary->len; i1++) {
+ if (rb_funcall(ary->ptr[i1], eq, 1, item)) continue;
+ if (i1 != i2) {
+ ary->ptr[i2] = ary->ptr[i1];
+ }
+ i2++;
+ }
+ ary->len = i2;
+
+ return (VALUE)ary;
+}
+
+static VALUE
+Fary_delete_if(ary)
+ struct RArray *ary;
+{
+ int i1, i2;
+
+ for (i1 = i2 = 0; i1 < ary->len; i1++) {
+ if (rb_yield(ary->ptr[i1])) continue;
+ if (i1 != i2) {
+ ary->ptr[i2] = ary->ptr[i1];
+ }
+ i2++;
+ }
+ ary->len = i2;
+
+ return (VALUE)ary;
+}
+
+static VALUE
+Fary_clear(ary)
+ struct RArray *ary;
+{
+ ary->len = 0;
+ return (VALUE)ary;
+}
+
+static VALUE
+Fary_fill(ary, args)
+ struct RArray *ary;
+ VALUE args;
+{
+ VALUE item, arg1, arg2;
+ int beg, len, end;
+ VALUE *p, *pend;
+
+ rb_scan_args(args, "12", &item, &arg1, &arg2);
+ if (arg2 == Qnil && obj_is_kind_of(arg1, C_Range)) {
+ range_beg_end(arg1, &beg, &len, ary->len);
+ }
+ else {
+ beg = NUM2INT(arg1);
+ if (beg < 0) {
+ beg = ary->len + beg;
+ if (beg < 0) beg = 0;
+ }
+ if (arg2) {
+ len = NUM2INT(arg2);
+ }
+ else {
+ len = ary->len - beg;
+ }
+ }
+ end = beg + len;
+ if (end > ary->len) {
+ if (end >= ary->capa) {
+ ary->capa=end;
+ REALLOC_N(ary->ptr, VALUE, ary->capa);
+ }
+ if (beg > ary->len) {
+ bzero(ary->ptr+ary->len, sizeof(VALUE)*(end-ary->len));
+ }
+ ary->len = end;
+ }
+ p = ary->ptr + beg; pend = p + len;
+
+ while (p < pend) {
+ *p++ = item;
+ }
+ return (VALUE)ary;
+}
+
+static VALUE
+Fary_plus(x, y)
+ struct RArray *x, *y;
+{
+ struct RArray *z;
+
+ switch (TYPE(y)) {
+ case T_ARRAY:
+ z = (struct RArray*)ary_new2(x->len + y->len);
+ memcpy(z->ptr, x->ptr, x->len*sizeof(VALUE));
+ memcpy(z->ptr+x->len, y->ptr, y->len*sizeof(VALUE));
+ z->len = x->len + RARRAY(y)->len;
+ break;
+
+ default:
+ GC_LINK;
+ GC_PRO3(z, (struct RArray*)Fary_clone(x));
+ Fary_push(z, y);
+ GC_UNLINK;
+ break;
+ }
+ return (VALUE)z;
+}
+
+static VALUE
+Fary_times(ary, times)
+ struct RArray *ary;
+ VALUE times;
+{
+ struct RArray *ary2;
+ int i, len;
+
+ len = NUM2INT(times) * ary->len;
+ ary2 = (struct RArray*)ary_new2(len);
+ ary2->len = len;
+
+ for (i=0; i<len; i+=ary->len) {
+ memcpy(ary2->ptr+i, ary->ptr, ary->len*sizeof(VALUE));
+ }
+
+ return (VALUE)ary2;
+}
+
+VALUE
+Fary_assoc(ary, key)
+ struct RArray *ary;
+ VALUE key;
+{
+ VALUE *p, *pend;
+
+ p = ary->ptr; pend = p + ary->len;
+ while (p < pend) {
+ if (TYPE(*p) == T_ARRAY
+ && RARRAY(*p)->len == 2
+ && rb_funcall(RARRAY(*p)->ptr[0], eq, 1, key))
+ return *p;
+ }
+ return Qnil;
+}
+
+VALUE
+Fary_rassoc(ary, value)
+ struct RArray *ary;
+ VALUE value;
+{
+ VALUE *p, *pend;
+
+ p = ary->ptr; pend = p + ary->len;
+ while (p < pend) {
+ if (TYPE(*p) == T_ARRAY
+ && RARRAY(*p)->len == 2
+ && rb_funcall(RARRAY(*p)->ptr[1], eq, 1, value))
+ return *p;
+ }
+ return Qnil;
+}
+
+extern VALUE C_Kernel;
+extern VALUE M_Enumerable;
+
+Init_Array()
+{
+ C_Array = rb_define_class("Array", C_Object);
+ rb_include_module(C_Array, M_Enumerable);
+
+ rb_define_single_method(C_Array, "new", Fary_new, 0);
+ rb_define_method(C_Array, "to_s", Fary_to_s, 0);
+ rb_define_method(C_Array, "_inspect", Fary_inspect, 0);
+ rb_define_method(C_Array, "to_a", Fary_to_a, 0);
+
+ rb_define_method(C_Array, "[]", Fary_aref, -2);
+ rb_define_method(C_Array, "[]=", Fary_aset, -2);
+ rb_define_method(C_Array, "<<", Fary_append, 1);
+ rb_define_method(C_Array, "push", Fary_push, 1);
+ rb_define_method(C_Array, "pop", Fary_pop, 0);
+ rb_define_method(C_Array, "shift", Fary_shift, 0);
+ rb_define_method(C_Array, "unshift", Fary_unshift, 1);
+ rb_define_method(C_Array, "each", Fary_each, 0);
+ rb_define_method(C_Array, "length", Fary_length, 0);
+ rb_define_method(C_Array, "clone", Fary_clone, 0);
+ rb_define_method(C_Array, "join", Fary_join, -2);
+ rb_define_method(C_Array, "reverse", Fary_reverse, 0);
+ rb_define_method(C_Array, "sort", Fary_sort, 0);
+ rb_define_method(C_Array, "delete", Fary_delete, 1);
+ rb_define_method(C_Array, "delete_if", Fary_delete_if, 0);
+ rb_define_method(C_Array, "clear", Fary_clear, 0);
+ rb_define_method(C_Array, "fill", Fary_fill, -2);
+
+ rb_define_method(C_Array, "assoc", Fary_assoc, 1);
+ rb_define_method(C_Array, "rassoc", Fary_rassoc, 1);
+
+ rb_define_method(C_Array, "+", Fary_plus, 1);
+ rb_define_method(C_Array, "*", Fary_times, 1);
+
+ cmp = rb_intern("<=>");
+ eq = rb_intern("==");
+
+ rb_define_method(C_Kernel, "::", assoc_new, 1);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-24 08:52:29 +0000