This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Tidying PATCH to unwind-dw2-fde.c:frame_heapsort
- From: Jason Merrill <jason at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 18 Dec 2002 11:26:50 -0500
- Subject: Tidying PATCH to unwind-dw2-fde.c:frame_heapsort
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.
*** 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
}