bug#6600: [PATCH] sort: add --threads option to parallelize internal sort.

[Jim Meyering]

Pádraig Brady wrote:
> Here's a small cleanup I missed.
> Alternatively one could make heap() return NULL rather than aborting,
> but since it already used xmalloc, I'm tending to this..
>
> commit cec33eb226df63f406f7eb70cd46d960ee02a060
> Author: Pádraig Brady <address@hidden>
> Date:   Tue Jul 13 08:23:52 2010 +0100
>
>     maint: heap.c: simplify heap_alloc
>
>     * gl/lib/heap.c (heap_alloc): Use the fact that the xalloc
>     routines will not return NULL.  Also remove the redundant
>     temporary variables.
>
> diff --git a/gl/lib/heap.c b/gl/lib/heap.c
> index a37224f..f148434 100644
> --- a/gl/lib/heap.c
> +++ b/gl/lib/heap.c
> @@ -36,22 +36,12 @@ static void heapify_up (void **, size_t,
>  struct heap *
>  heap_alloc (int (*compare)(const void *, const void *), size_t n_reserve)
>  {
> -  struct heap *heap;
> -  void *xmalloc_ret = xmalloc (sizeof *heap);
> -  heap = (struct heap *) xmalloc_ret;
> -  if (!heap)
> -    return NULL;
> +  struct heap *heap = xmalloc (sizeof *heap);
>
> -  if (n_reserve <= 0)
> +  if (n_reserve == 0)
>      n_reserve = 1;
>
> -  xmalloc_ret = xmalloc (n_reserve * sizeof *(heap->array));
> -  heap->array = (void **) xmalloc_ret;
> -  if (!heap->array)
> -    {
> -      free (heap);
> -      return NULL;
> -    }
> +  heap->array = xmalloc (n_reserve * sizeof *(heap->array));
>
>    heap->array[0] = NULL;
>    heap->capacity = n_reserve;
> @@ -84,8 +74,7 @@ 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->array = xrealloc (heap->array, new_size);

Thanks.
That looks good.  Please push.

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);