[Ada] Refactor sort procedures of doubly linked list containers

[Ada] Refactor sort procedures of doubly linked list containers

[Pierre-Marie de Rodat]

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

In earlier work, a performance problem was addressed by rewriting
Ada.Containers.Doubly_Linked_Lists.Generic_Sorting in a-cdlili.adb.  It
turned out that the very-slow-in-some-cases Sort algorithm formerly used
there was duplicated in 4 other units: the Bounded, Formal, Indefinite,
and Restricted versions. With this change, we use the better sorting
algorithm in all 5 cases while reducing code duplication.

Tested on x86_64-pc-linux-gnu, committed on trunk

gcc/ada/

	* libgnat/a-costso.ads, libgnat/a-costso.adb: A new library
	unit, Ada.Containers.Stable_Sorting, which exports a pair of
	generics (one within the other) which are instantiated by each
	of the 5 doubly-linked list container generics to implement
	their respective Sort procedures. We use a pair of generics,
	rather than a single generic, in order to further reduce code
	duplication. The outer generic takes a formal private Node_Ref
	type representing a reference to a linked list element. For some
	instances, the corresponding actual parameter will be an access
	type; for others, it will be the index type for an array.
	* Makefile.rtl: Include new Ada.Containers.Stable_Sorting unit.
	* libgnat/a-cbdlli.adb, libgnat/a-cdlili.adb,
	libgnat/a-cfdlli.adb, libgnat/a-cidlli.adb, libgnat/a-crdlli.adb
	(Sort): Replace existing Sort implementation with a call to an
	instance of
	Ada.Containers.Stable_Sorting.Doubly_Linked_List_Sort. Declare
	the (trivial) actual parameters needed to declare that instance.
	* libgnat/a-cfdlli.ads: Fix a bug encountered during testing in
	the postcondition for M_Elements_Sorted. With a partial
	ordering, it is possible for all three of (X < Y), (Y < X),
	and (X = Y) to be simultaneously false, so that case needs to
	handled correctly.

[-- Attachment #2: patch.diff.gz --]
[-- Type: application/gzip, Size: 5531 bytes --]