On 13/07/10 15:35, Jim Meyering wrote: > I noticed that heap_insert's reallocation was awkward and inefficient. > Using x2nrealloc rather than xrealloc makes the code > cleaner as well as more efficient in the face of a growing > heap, and also handles integer overflow. > > diff --git a/gl/lib/heap.c b/gl/lib/heap.c > index a37224f..12a7767 100644 > --- a/gl/lib/heap.c > +++ b/gl/lib/heap.c > @@ -82,15 +82,8 @@ int > heap_insert (struct heap *heap, void *item) > { > if (heap->capacity - 1 <= heap->count) > - { > - size_t new_size = (2 + heap->count) * sizeof *(heap->array); > - void *realloc_ret = xrealloc (heap->array, new_size); > - heap->array = (void **) realloc_ret; > - heap->capacity = (2 + heap->count); > - > - if (!heap->array) > - return -1; > - } > + heap->array = x2nrealloc (heap->array, &heap->capacity, > + sizeof *(heap->array)); > > heap->array[++heap->count] = item; > heapify_up (heap->array, heap->count, heap->compare);
Much cleaner and increases with n *= 1.5 rather than n += 2 Testing here shows no change in performance. Do you want me to roll that into my patch? cheers, Pádraig.