The guts of a merge-sort algorithm. This was derived from the glibc * version, but I (Wayne) changed the merge code to do less copying and * to require only half the amount of temporary memory. */
| 1739 | * version, but I (Wayne) changed the merge code to do less copying and |
| 1740 | * to require only half the amount of temporary memory. */ |
| 1741 | static void fsort_tmp(struct file_struct **fp, size_t num, |
| 1742 | struct file_struct **tmp) |
| 1743 | { |
| 1744 | struct file_struct **f1, **f2, **t; |
| 1745 | size_t n1, n2; |
| 1746 | |
| 1747 | n1 = num / 2; |
| 1748 | n2 = num - n1; |
| 1749 | f1 = fp; |
| 1750 | f2 = fp + n1; |
| 1751 | |
| 1752 | if (n1 > 1) |
| 1753 | fsort_tmp(f1, n1, tmp); |
| 1754 | if (n2 > 1) |
| 1755 | fsort_tmp(f2, n2, tmp); |
| 1756 | |
| 1757 | while (f_name_cmp(*f1, *f2) <= 0) { |
| 1758 | if (!--n1) |
| 1759 | return; |
| 1760 | f1++; |
| 1761 | } |
| 1762 | |
| 1763 | t = tmp; |
| 1764 | memcpy(t, f1, n1 * PTR_SIZE); |
| 1765 | |
| 1766 | *f1++ = *f2++, n2--; |
| 1767 | |
| 1768 | while (n1 > 0 && n2 > 0) { |
| 1769 | if (f_name_cmp(*t, *f2) <= 0) |
| 1770 | *f1++ = *t++, n1--; |
| 1771 | else |
| 1772 | *f1++ = *f2++, n2--; |
| 1773 | } |
| 1774 | |
| 1775 | if (n1 > 0) |
| 1776 | memcpy(f1, t, n1 * PTR_SIZE); |
| 1777 | } |
| 1778 | |
| 1779 | /* This file-struct sorting routine makes sure that any identical names in |
| 1780 | * the file list stay in the same order as they were in the original list. |