From: Nobuyoshi Nakada <nobu@...>
Date: 2006-09-24T22:12:27+09:00
Subject: Re: Array shift bug

Hi,

At Sun, 24 Sep 2006 16:54:53 +0900,
Nobuyoshi Nakada wrote in [ruby-talk:216087]:
> > > A short article describing a problem in the implementation of array  
> > > shift in Ruby 1.8.4 with a simple one-line fix in the C code is here:
> > That's half a fix. If you're using shift and push to manage a queue, you 
> > still have an ever-growing buffer.*
> 
> Does this patch fix it?

It was for 1.9.

The patch for 1.8 is following.


Index: array.c
===================================================================
RCS file: /cvs/ruby/src/ruby/array.c,v
retrieving revision 1.137.2.33
diff -p -U 2 -r1.137.2.33 array.c
--- array.c	24 Jun 2006 14:53:36 -0000	1.137.2.33
+++ array.c	24 Sep 2006 13:09:32 -0000
@@ -44,4 +44,6 @@ memfill(mem, size, val)
 
 #define ARY_TMPLOCK  FL_USER1
+#define ARY_SHARED_P(a) FL_TEST(a, ELTS_SHARED)
+#define ARY_SHARED_ARY(a) RARRAY(a)->aux.shared
 
 static inline void
@@ -57,12 +59,10 @@ rb_ary_modify_check(ary)
 
 static void
-rb_ary_modify(ary)
+rb_ary_make_independent(ary)
     VALUE ary;
 {
-    VALUE *ptr;
+    if (ARY_SHARED_P(ary)) {
+	VALUE *ptr = ALLOC_N(VALUE, RARRAY(ary)->len);
 
-    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;
@@ -72,4 +72,25 @@ rb_ary_modify(ary)
 }
 
+static void
+rb_ary_modify(ary)
+    VALUE ary;
+{
+    rb_ary_modify_check(ary);
+    rb_ary_make_independent(ary);
+}
+
+static void
+rb_ary_limit_shared(ary)
+    VALUE ary;
+{
+    VALUE shared;
+
+    if (!ARY_SHARED_P(ary)) return;
+    shared = ARY_SHARED_ARY(ary);
+    if (RARRAY(ary)->ptr - RARRAY(shared)->ptr < ARY_DEFAULT_SIZE) return;
+    if (RARRAY(ary)->len > RARRAY(shared)->len / 2) return;
+    rb_ary_make_independent(ary);
+}
+
 VALUE
 rb_ary_freeze(ary)
@@ -450,5 +471,5 @@ rb_ary_pop(ary)
     rb_ary_modify_check(ary);
     if (RARRAY(ary)->len == 0) return Qnil;
-    if (!FL_TEST(ary, ELTS_SHARED) &&
+    if (!ARY_SHARED_P(ary) &&
 	    RARRAY(ary)->len * 2 < RARRAY(ary)->aux.capa &&
 	    RARRAY(ary)->aux.capa > ARY_DEFAULT_SIZE) {
@@ -463,5 +484,5 @@ ary_make_shared(ary)
     VALUE ary;
 {
-    if (!FL_TEST(ary, ELTS_SHARED)) {
+    if (!ARY_SHARED_P(ary)) {
 	NEWOBJ(shared, struct RArray);
 	OBJSETUP(shared, rb_cArray, T_ARRAY);
@@ -470,5 +491,5 @@ ary_make_shared(ary)
 	shared->ptr = RARRAY(ary)->ptr;
 	shared->aux.capa = RARRAY(ary)->aux.capa;
-	RARRAY(ary)->aux.shared = (VALUE)shared;
+	ARY_SHARED_ARY(ary) = (VALUE)shared;
 	FL_SET(ary, ELTS_SHARED);
 	OBJ_FREEZE(shared);
@@ -476,5 +497,5 @@ ary_make_shared(ary)
     }
     else {
-	return RARRAY(ary)->aux.shared;
+	return ARY_SHARED_ARY(ary);
     }
 }
@@ -505,4 +526,5 @@ rb_ary_shift(ary)
     RARRAY(ary)->ptr++;		/* shift ptr */
     RARRAY(ary)->len--;
+    rb_ary_limit_shared(ary);
 
     return top;
@@ -612,5 +634,5 @@ rb_ary_subseq(ary, beg, len)
     RARRAY(ary2)->ptr = ptr + beg;
     RARRAY(ary2)->len = len;
-    RARRAY(ary2)->aux.shared = shared;
+    ARY_SHARED_ARY(ary2) = shared;
     FL_SET(ary2, ELTS_SHARED);
 
@@ -2162,9 +2184,9 @@ rb_ary_replace(copy, orig)
     if (copy == orig) return copy;
     shared = ary_make_shared(orig);
-    if (RARRAY(copy)->ptr && !FL_TEST(copy, ELTS_SHARED))
+    if (RARRAY(copy)->ptr && !ARY_SHARED_P(copy))
 	free(RARRAY(copy)->ptr);
     RARRAY(copy)->ptr = RARRAY(orig)->ptr;
     RARRAY(copy)->len = RARRAY(orig)->len;
-    RARRAY(copy)->aux.shared = shared;
+    ARY_SHARED_ARY(copy) = shared;
     FL_SET(copy, ELTS_SHARED);
 


-- 
Nobu Nakada