diff options
author | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2008-03-04 01:21:06 +0000 |
---|---|---|
committer | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2008-03-04 01:21:06 +0000 |
commit | fd847f79a0c5e9e61860ff4133665f7099bc85cf (patch) | |
tree | 26742a04a61fde2e256be1900556ca0ea578e049 | |
parent | 8ac9b7c2ed7b0da6b7c9380e9977fda46c6d24f8 (diff) | |
download | ruby-fd847f79a0c5e9e61860ff4133665f7099bc85cf.tar.gz |
* gc.c (add_heap): use binary search to find the place to insert the
new heap slot. [ruby-dev:33983]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@15683 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r-- | ChangeLog | 5 | ||||
-rw-r--r-- | gc.c | 51 |
2 files changed, 37 insertions, 19 deletions
@@ -1,3 +1,8 @@ +Tue Mar 4 10:21:03 2008 Nobuyoshi Nakada <nobu@ruby-lang.org> + + * 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@ruby-lang.org> * io.c (open_key_args): use rb_io_open instead of rb_f_open. @@ -413,18 +413,11 @@ 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; + RVALUE *p, *pend, *membase; + long hi, lo, mid; if (heaps_used == heaps_length) { /* Realloc heaps */ @@ -451,17 +444,38 @@ add_heap(void) 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 @@ add_heap(void) freelist = p; p++; } - ruby_qsort(heaps, heaps_used, sizeof(struct heaps_slot), heap_cmp, 0); } #define RANY(o) ((RVALUE*)(o)) |