Tidying PATCH to unwind-dw2-fde.c:frame_heapsort

Tidying PATCH to unwind-dw2-fde.c:frame_heapsort

[Jason Merrill]

[-- Attachment #1: Type: text/plain, Size: 341 bytes --]

This patch, the last of the random patches I've had sitting in my tree for
a while, improves the readability of frame_heapsort by splitting out the
downheap routine.

Tested i686-pc-linux-gnu, applied to trunk.

2002-12-18  Jason Merrill  <jason@redhat.com>

	* unwind-dw2-fde.c (frame_downheap): Split out from...
	(frame_heapsort): Here.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: text/x-patch, Size: 3228 bytes --]

*** unwind-dw2-fde.c.~1~	Wed Dec 18 01:39:02 2002
--- unwind-dw2-fde.c	Wed Dec 18 01:41:02 2002
*************** fde_split (struct object *ob, fde_compar
*** 467,472 ****
--- 467,500 ----
    erratic->count = k;
  }
  
+ #define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0)
+ 
+ /* Convert a semi-heap to a heap.  A semi-heap is a heap except possibly
+    for the first (root) node; push it down to its rightful place.  */
+ 
+ static void
+ frame_downheap (struct object *ob, fde_compare_t fde_compare, fde **a,
+ 		int lo, int hi)
+ {
+   int i, j;
+ 
+   for (i = lo, j = 2*i+1;
+        j < hi;
+        j = 2*i+1)
+     {
+       if (j+1 < hi && fde_compare (ob, a[j], a[j+1]) < 0)
+ 	++j;
+ 
+       if (fde_compare (ob, a[i], a[j]) < 0)
+ 	{
+ 	  SWAP (a[i], a[j]);
+ 	  i = j;
+ 	}
+       else
+ 	break;
+     }
+ }
+ 
  /* This is O(n log(n)).  BSD/OS defines heapsort in stdlib.h, so we must
     use a name that does not conflict.  */
  
*************** frame_heapsort (struct object *ob, fde_c
*** 481,535 ****
    /* A portion of the array is called a "heap" if for all i>=0:
       If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
       If i and 2i+2 are valid indices, then a[i] >= a[2i+2].  */
- #define SWAP(x,y) do { fde * tmp = x; x = y; y = tmp; } while (0)
    size_t n = erratic->count;
!   size_t m = n;
!   size_t i;
  
!   while (m > 0)
!     {
!       /* Invariant: a[m..n-1] is a heap.  */
!       m--;
!       for (i = m; 2*i+1 < n; )
! 	{
! 	  if (2*i+2 < n
! 	      && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0
! 	      && fde_compare (ob, a[2*i+2], a[i]) > 0)
! 	    {
! 	      SWAP (a[i], a[2*i+2]);
! 	      i = 2*i+2;
! 	    }
! 	  else if (fde_compare (ob, a[2*i+1], a[i]) > 0)
! 	    {
! 	      SWAP (a[i], a[2*i+1]);
! 	      i = 2*i+1;
! 	    }
! 	  else
! 	    break;
! 	}
!     }
!   while (n > 1)
      {
!       /* Invariant: a[0..n-1] is a heap.  */
!       n--;
!       SWAP (a[0], a[n]);
!       for (i = 0; 2*i+1 < n; )
! 	{
! 	  if (2*i+2 < n
! 	      && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0
! 	      && fde_compare (ob, a[2*i+2], a[i]) > 0)
! 	    {
! 	      SWAP (a[i], a[2*i+2]);
! 	      i = 2*i+2;
! 	    }
! 	  else if (fde_compare (ob, a[2*i+1], a[i]) > 0)
! 	    {
! 	      SWAP (a[i], a[2*i+1]);
! 	      i = 2*i+1;
! 	    }
! 	  else
! 	    break;
! 	}
      }
  #undef SWAP
  }
--- 509,530 ----
    /* A portion of the array is called a "heap" if for all i>=0:
       If i and 2i+1 are valid indices, then a[i] >= a[2i+1].
       If i and 2i+2 are valid indices, then a[i] >= a[2i+2].  */
    size_t n = erratic->count;
!   int m;
  
!   /* Expand our heap incrementally from the end of the array, heapifying
!      each resulting semi-heap as we go.  After each step, a[m] is the top
!      of a heap.  */
!   for (m = n/2-1; m >= 0; --m)
!     frame_downheap (ob, fde_compare, a, m, n);
! 
!   /* Shrink our heap incrementally from the end of the array, first
!      swapping out the largest element a[0] and then re-heapifying the
!      resulting semi-heap.  After each step, a[0..m) is a heap.  */
!   for (m = n-1; m >= 1; --m)
      {
!       SWAP (a[0], a[m]);
!       frame_downheap (ob, fde_compare, a, 0, m);
      }
  #undef SWAP
  }