なかだです。

At Mon, 3 Mar 2008 17:27:45 +0900 (JST),
matz ruby-lang.org wrote in [ruby-cvs:22911]:
>   Log:
>     * gc.c (add_heap): sort heaps array in ascending order to use
>       binary search.

すでにほとんどソート済みの配列にたいしてはquick sortって不利では
なかったかと思うのですが。というか、void*同士の減算は規格上は不
可では。


Index: gc.c
===================================================================
--- gc.c	(revision 15675)
+++ gc.c	(working copy)
@@ -414,16 +414,10 @@ rb_gc_unregister_address(VALUE *addr)
 }
 
-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;
+    struct heaps_slot *heap;
+    long hi, lo, mid;
 
     if (heaps_used == heaps_length) {
@@ -452,15 +446,36 @@ add_heap(void)
 	    }
 	    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;
+	heap = &heaps[mid];
+	if (heap->membase < p) {
+	    lo = mid + 1;
+	}
+	else if (heap->membase > p) {
+	    hi = mid;
+	}
+	else {
+	    rb_bug("same heap slot is allocated: %p at %ld", p, mid);
+	}
     }
+
+    if (hi < heaps_used) {
+	MEMMOVE(&heaps[hi+1], &heaps[hi], VALUE, heaps_used - hi);
+    }
+    heaps[hi].membase = p;
+    if ((VALUE)p % sizeof(RVALUE) == 0)
+	heap_slots += 1;
+    else
+	p = (RVALUE*)((VALUE)p + sizeof(RVALUE) - ((VALUE)p % sizeof(RVALUE)));
+    heaps[hi].slot = p;
+    heaps[hi].limit = heap_slots;
     pend = p + heap_slots;
     if (lomem == 0 || lomem > p) lomem = p;
@@ -475,5 +490,4 @@ add_heap(void)
 	p++;
     }
-    ruby_qsort(heaps, heaps_used, sizeof(struct heaps_slot), heap_cmp, 0);
 }
 


-- 
--- 僕の前にBugはない。
--- 僕の後ろにBugはできる。
    中田 伸悦