From ef5efefaec8b3a4eafde2347b98a973f73745421 Mon Sep 17 00:00:00 2001 From: "Xiang, Haihao" Date: Mon, 26 Mar 2012 14:12:27 +0800 Subject: Avoid moving objects in a heap to a new address when expanding this heap Signed-off-by: Xiang, Haihao --- src/object_heap.c | 60 ++++++++++++++++++++++++++++++++++++++++++++----------- src/object_heap.h | 3 ++- 2 files changed, 50 insertions(+), 13 deletions(-) diff --git a/src/object_heap.c b/src/object_heap.c index 46062fbc..1a92579b 100644 --- a/src/object_heap.c +++ b/src/object_heap.c @@ -44,17 +44,32 @@ static int object_heap_expand( object_heap_p heap ) void *new_heap_index; int next_free; int new_heap_size = heap->heap_size + heap->heap_increment; - - new_heap_index = (void *) realloc( heap->heap_index, new_heap_size * heap->object_size ); + int bucket_index = new_heap_size / heap->heap_increment - 1; + + if (bucket_index >= heap->num_buckets) { + int new_num_buckets = heap->num_buckets + 8; + void **new_bucket; + + new_bucket = realloc(heap->bucket, new_num_buckets * sizeof(void *)); + if (NULL == new_bucket) { + return -1; + } + + heap->num_buckets = new_num_buckets; + heap->bucket = new_bucket; + } + + new_heap_index = (void *) malloc( heap->heap_increment * heap->object_size ); if ( NULL == new_heap_index ) { return -1; /* Out of memory */ } - heap->heap_index = new_heap_index; + + heap->bucket[bucket_index] = new_heap_index; next_free = heap->next_free; for(i = new_heap_size; i-- > heap->heap_size; ) { - object_base_p obj = (object_base_p) (heap->heap_index + i * heap->object_size); + object_base_p obj = (object_base_p) (new_heap_index + (i - heap->heap_size) * heap->object_size); obj->id = i + heap->id_offset; obj->next_free = next_free; next_free = i; @@ -73,9 +88,10 @@ int object_heap_init( object_heap_p heap, int object_size, int id_offset) heap->id_offset = id_offset & OBJECT_HEAP_OFFSET_MASK; heap->heap_size = 0; heap->heap_increment = 16; - heap->heap_index = NULL; heap->next_free = LAST_FREE; _i965InitMutex(&heap->mutex); + heap->num_buckets = 0; + heap->bucket = NULL; return object_heap_expand(heap); } @@ -86,6 +102,7 @@ int object_heap_init( object_heap_p heap, int object_size, int id_offset) int object_heap_allocate( object_heap_p heap ) { object_base_p obj; + int bucket_index, obj_index; _i965LockMutex(&heap->mutex); if ( LAST_FREE == heap->next_free ) @@ -97,8 +114,11 @@ int object_heap_allocate( object_heap_p heap ) } } ASSERT( heap->next_free >= 0 ); - - obj = (object_base_p) (heap->heap_index + heap->next_free * heap->object_size); + + bucket_index = heap->next_free / heap->heap_increment; + obj_index = heap->next_free % heap->heap_increment; + + obj = (object_base_p) (heap->bucket[bucket_index] + obj_index * heap->object_size); heap->next_free = obj->next_free; _i965UnlockMutex(&heap->mutex); @@ -113,6 +133,7 @@ int object_heap_allocate( object_heap_p heap ) object_base_p object_heap_lookup( object_heap_p heap, int id ) { object_base_p obj; + int bucket_index, obj_index; _i965LockMutex(&heap->mutex); if ( (id < heap->id_offset) || (id > (heap->heap_size+heap->id_offset)) ) @@ -121,7 +142,9 @@ object_base_p object_heap_lookup( object_heap_p heap, int id ) return NULL; } id &= OBJECT_HEAP_ID_MASK; - obj = (object_base_p) (heap->heap_index + id * heap->object_size); + bucket_index = id / heap->heap_increment; + obj_index = id % heap->heap_increment; + obj = (object_base_p) (heap->bucket[bucket_index] + obj_index * heap->object_size); _i965UnlockMutex(&heap->mutex); /* Check if the object has in fact been allocated */ @@ -150,10 +173,15 @@ object_base_p object_heap_next( object_heap_p heap, object_heap_iterator *iter ) { object_base_p obj; int i = *iter + 1; + int bucket_index, obj_index; + _i965LockMutex(&heap->mutex); while ( i < heap->heap_size) { - obj = (object_base_p) (heap->heap_index + i * heap->object_size); + bucket_index = i / heap->heap_increment; + obj_index = i % heap->heap_increment; + + obj = (object_base_p) (heap->bucket[bucket_index] + obj_index * heap->object_size); if (obj->next_free == ALLOCATED) { _i965UnlockMutex(&heap->mutex); @@ -194,6 +222,7 @@ void object_heap_destroy( object_heap_p heap ) { object_base_p obj; int i; + int bucket_index, obj_index; _i965DestroyMutex(&heap->mutex); @@ -201,11 +230,18 @@ void object_heap_destroy( object_heap_p heap ) for (i = 0; i < heap->heap_size; i++) { /* Check if object is not still allocated */ - obj = (object_base_p) (heap->heap_index + i * heap->object_size); + bucket_index = i / heap->heap_increment; + obj_index = i % heap->heap_increment; + obj = (object_base_p) (heap->bucket[bucket_index] + obj_index * heap->object_size); ASSERT( obj->next_free != ALLOCATED ); } - free(heap->heap_index); + + for (i = 0; i < heap->heap_size / heap->heap_increment; i++) { + free(heap->bucket[i]); + } + + free(heap->bucket); + heap->bucket = NULL; heap->heap_size = 0; - heap->heap_index = NULL; heap->next_free = LAST_FREE; } diff --git a/src/object_heap.h b/src/object_heap.h index 82a69172..79efeabc 100644 --- a/src/object_heap.h +++ b/src/object_heap.h @@ -41,11 +41,12 @@ struct object_base { struct object_heap { int object_size; int id_offset; - void *heap_index; int next_free; int heap_size; int heap_increment; _I965Mutex mutex; + void **bucket; + int num_buckets; }; typedef int object_heap_iterator; -- cgit v1.2.1