nobu	2008-03-04 10:21:06 +0900 (Tue, 04 Mar 2008)

  New Revision: 15683

  Modified files:
    trunk/ChangeLog
    trunk/gc.c

  Log:
    * gc.c (add_heap): use binary search to find the place to insert the
      new heap slot.  [ruby-dev:33983]


  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/ChangeLog?r1=15683&r2=15682&diff_format=u
  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/gc.c?r1=15683&r2=15682&diff_format=u

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 15682)
+++ ChangeLog	(revision 15683)
@@ -1,3 +1,8 @@
+Tue Mar  4 10:21:03 2008  Nobuyoshi Nakada  <nobu@r...>
+
+	* gc.c (add_heap): use binary search to find the place to insert the
+	  new heap slot.  [ruby-dev:33983]
+
 Tue Mar 04 05:30:31 2008  NARUSE, Yui  <naruse@r...>
 
 	* io.c (open_key_args): use rb_io_open instead of rb_f_open.
Index: gc.c
===================================================================
--- gc.c	(revision 15682)
+++ gc.c	(revision 15683)
@@ -413,18 +413,11 @@
     }
 }
 
-static int
-heap_cmp(const void *ap, const void *bp, void *dummy)
-{
-    const struct heaps_slot *a = ap, *b = bp;
-
-    return a->membase - b->membase;
-}
-
 static void
 add_heap(void)
 {
-    RVALUE *p, *pend;
+    RVALUE *p, *pend, *membase;
+    long hi, lo, mid;
 
     if (heaps_used == heaps_length) {
 	/* Realloc heaps */
@@ -451,17 +444,38 @@
 		rb_memerror();
 	    }
 	    heap_slots = HEAP_MIN_SLOTS;
-	    continue;
 	}
-	heaps[heaps_used].membase = p;
-	if ((VALUE)p % sizeof(RVALUE) == 0)
-	    heap_slots += 1;
-	else
-	    p = (RVALUE*)((VALUE)p + sizeof(RVALUE) - ((VALUE)p % sizeof(RVALUE)));
-	heaps[heaps_used].slot = p;
-	heaps[heaps_used].limit = heap_slots;
-	break;
+	else {
+	    break;
+	}
     }
+
+    lo = 0;
+    hi = heaps_used;
+    while (lo < hi) {
+	mid = (lo + hi) / 2;
+	membase = heaps[mid].membase;
+	if (membase < p) {
+	    lo = mid + 1;
+	}
+	else if (membase > p) {
+	    hi = mid;
+	}
+	else {
+	    rb_bug("same heap slot is allocated: %p at %ld", p, mid);
+	}
+    }
+
+    if ((VALUE)p % sizeof(RVALUE) == 0)
+	heap_slots += 1;
+    else
+	p = (RVALUE*)((VALUE)p + sizeof(RVALUE) - ((VALUE)p % sizeof(RVALUE)));
+    if (hi < heaps_used) {
+	MEMMOVE(&heaps[hi+1], &heaps[hi], VALUE, heaps_used - hi);
+    }
+    heaps[hi].membase = p;
+    heaps[hi].slot = p;
+    heaps[hi].limit = heap_slots;
     pend = p + heap_slots;
     if (lomem == 0 || lomem > p) lomem = p;
     if (himem < pend) himem = pend;
@@ -474,7 +488,6 @@
 	freelist = p;
 	p++;
     }
-    ruby_qsort(heaps, heaps_used, sizeof(struct heaps_slot), heap_cmp, 0);
 }
 
 #define RANY(o) ((RVALUE*)(o))

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/