qsort issues

qsort isn't guaranteed to be a stable sort, that is, elements
comparing equal according to the comparison function may be reordered
relative to their original ordering.  Of course sometimes you may not
care, but even in those cases it is good to force some ordering
(ie. not have the comparison function return 0) so that linker output
is reproducible over different libc qsort implementations.

One way to make qsort stable (which the glibc manual incorrectly says
is the only way) is to augment the elements being sorted with a
monotonic counter of some kind, and use that counter as the final
arbiter of ordering in the comparison function.

Another way is to set up an array of pointers into the array of
elements, first pointer to first element, second pointer to second
element and so so, and sort the pointer array rather than the element
array.  Final arbiter in the comparison function then is the pointer
difference.  This works well with, for example, the symbol pointers
returned by _bfd_elf_canonicalize_symtab which point into a symbol
array.

This patch fixes a few places where sorting by symbol pointers is
appropriate, and adds comments where qsort stability is a non-issue.

	* elf-strtab.c (strrevcmp): Comment.
	* merge.c (strrevcmp): Likewise.
	* elf64-ppc.c (compare_symbols): Correct final pointer comparison.
	Comment on why comparing pointers ensures a stable sort.
	* elflink.c (struct elf_symbol): Add void* to union.
	(elf_sort_elf_symbol): Ensure a stable sort with pointer comparison.
	(elf_sym_name_compare): Likewise.
	(bfd_elf_match_symbols_in_sections): Style fix.
	(elf_link_sort_cmp1): Comment.

1 files changed, 3 insertions, 0 deletions

diff --git a/bfd/merge.c b/bfd/merge.c
index 632c8523903..11be669c2c3 100644
--- a/bfd/merge.c
+++ b/bfd/merge.c
@@ -555,6 +555,9 @@ error_return:
   return FALSE;
 }
 
+/* qsort comparison function.  Won't ever return zero as all entries
+   differ, so there is no issue with qsort stability here.  */
+
 static int
 strrevcmp (const void *a, const void *b)
 {