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.
patch.diff.gz
Description: application/gzip
