Author: rfm Date: Fri Jul 15 13:30:07 2016 New Revision: 39998 URL: http://svn.gna.org/viewcvs/gnustep?rev=39998&view=rev Log: Sort algorithms should always be built, and be selectable at runtime
Modified: libs/base/trunk/ChangeLog libs/base/trunk/Documentation/Base.gsdoc libs/base/trunk/Documentation/ReleaseNotes.gsdoc libs/base/trunk/Documentation/news.texi libs/base/trunk/Headers/GNUstepBase/config.h.in libs/base/trunk/Source/GSQuickSort.m libs/base/trunk/Source/GSShellSort.m libs/base/trunk/Source/GSSorting.h libs/base/trunk/Source/GSTimSort.m libs/base/trunk/Source/NSSortDescriptor.m libs/base/trunk/configure libs/base/trunk/configure.ac Modified: libs/base/trunk/ChangeLog URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/ChangeLog?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/ChangeLog (original) +++ libs/base/trunk/ChangeLog Fri Jul 15 13:30:07 2016 @@ -1,3 +1,15 @@ +2016-07-15 Richard Frith-Macdonald <r...@gnu.org> + + * configure.ac: + * Headers/GNUstepBase/config.h.in: + * Source/GSQuickSort.m: + * Source/GSShellSort.m: + * Source/GSSorting.h: + * Source/GSTimSort.m: + * Source/NSSortDescriptor.m: + Make sorting algorithms selectable at runtime rather than compile + time. + 2016-07-13 Richard Frith-Macdonald <r...@gnu.org> * Source/NSRunLoop.m (-acceptInputForMode:beforeDate:): Modified: libs/base/trunk/Documentation/Base.gsdoc URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Documentation/Base.gsdoc?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/Documentation/Base.gsdoc (original) +++ libs/base/trunk/Documentation/Base.gsdoc Fri Jul 15 13:30:07 2016 @@ -200,6 +200,18 @@ environment variables. </p> </desc> + <term>GSSortAlgorithm</term> + <desc> + <p> + May be used to specify the sort algorithm used for sorting + arrays etc. The current options are QuickSort, ShellSort, and + TimSort, with TimSort being the default.<br /> + NB. The QuickSort and ShellSort are 'unstable' algorithms, + which means that the order of equal objects may be changed + by a sort. Selecting these may break code which assumes that + sorting is stable. + </p> + </desc> <term>Local Time Zone</term> <desc> <p> Modified: libs/base/trunk/Documentation/ReleaseNotes.gsdoc URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Documentation/ReleaseNotes.gsdoc?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/Documentation/ReleaseNotes.gsdoc (original) +++ libs/base/trunk/Documentation/ReleaseNotes.gsdoc Fri Jul 15 13:30:07 2016 @@ -39,6 +39,9 @@ OpenSSL bundle removed since it didn't match GNUTLS support.<br /> Improved support for 64bit little-endian systems.<br /> Ported to Debian/Hurd.<br /> + ICU string (regexp in particular) fixes.<br /> + OSX compatibity changes in NSRunLoop behavior.<br /> + Alterntive sort algorithms selectable at runtime.<br /> As usual, this release also contains an update to include the most recent international timezone data. </p> Modified: libs/base/trunk/Documentation/news.texi URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Documentation/news.texi?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/Documentation/news.texi (original) +++ libs/base/trunk/Documentation/news.texi Fri Jul 15 13:30:07 2016 @@ -17,6 +17,9 @@ @item Support for Debian style multi-architecture installations added @item OpenSSL bundle removed since it didn't match GNUTLS support @item Ported to Debian/Hurd +@item ICU string (regexp in particular) fixes +@item OSX compatibity changes in NSRunLoop behavior +@item Alterntive sort algorithms selectable at runtime @item As usual, this release also contains an update to include the most recent international timezone data. @end itemize Modified: libs/base/trunk/Headers/GNUstepBase/config.h.in URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Headers/GNUstepBase/config.h.in?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/Headers/GNUstepBase/config.h.in (original) +++ libs/base/trunk/Headers/GNUstepBase/config.h.in Fri Jul 15 13:30:07 2016 @@ -170,15 +170,6 @@ /* Built in default value for GNUstep user_dir web apps */ #undef GNUSTEP_TARGET_USER_DIR_WEB_APPS - -/* Build in/use quicksort */ -#undef GS_USE_QUICKSORT - -/* Build in/use shellsort */ -#undef GS_USE_SHELLSORT - -/* Build in/use timsort */ -#undef GS_USE_TIMSORT /* Define to 1 if you have the <alloca.h> header file. */ #undef HAVE_ALLOCA_H Modified: libs/base/trunk/Source/GSQuickSort.m URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Source/GSQuickSort.m?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/Source/GSQuickSort.m (original) +++ libs/base/trunk/Source/GSQuickSort.m Fri Jul 15 13:30:07 2016 @@ -35,7 +35,6 @@ * Sorts the provided object array's sortRange according to sortDescriptor. */ // Quicksort algorithm copied from Wikipedia :-). -#if GS_USE_QUICKSORT static inline void SwapObjects(id * o1, id * o2) @@ -84,12 +83,12 @@ } @interface GSQuickSortPlaceHolder : NSObject ++ (void) setUnstable; @end @implementation GSQuickSortPlaceHolder -+ (void) load ++ (void) setUnstable { _GSSortUnstable = _GSQuickSort; } @end -#endif Modified: libs/base/trunk/Source/GSShellSort.m URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Source/GSShellSort.m?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/Source/GSShellSort.m (original) +++ libs/base/trunk/Source/GSShellSort.m Fri Jul 15 13:30:07 2016 @@ -30,7 +30,6 @@ #import "Foundation/NSObjCRuntime.h" #import "GSSorting.h" -#if GS_USE_SHELLSORT void _GSShellSort(id *objects, NSRange sortRange, @@ -114,13 +113,13 @@ @interface GSShellSortPlaceHolder : NSObject - ++ (void) setUnstable; @end @implementation GSShellSortPlaceHolder -+ (void) load ++ (void) setUnstable { _GSSortUnstable = _GSShellSort; } @end -#endif + Modified: libs/base/trunk/Source/GSSorting.h URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Source/GSSorting.h?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/Source/GSSorting.h (original) +++ libs/base/trunk/Source/GSSorting.h Fri Jul 15 13:30:07 2016 @@ -30,7 +30,7 @@ enum { - GSComparisonTypeSortDescriptor = 0, /** Comparison using an NSSortDescriptor */ + GSComparisonTypeSortDescriptor = 0, /** Comparison using NSSortDescriptor */ GSComparisonTypeComparatorBlock, /** Comparison using an NSComparator */ GSComparisonTypeFunction, /** Comparison using a comparison function of type * NSInteger(*)(id,id,void*) */ @@ -130,7 +130,7 @@ * This function is provided using the implementation of the timsort algorithm. */ NSUInteger -GSLeftInsertionPointForKeyInSortedRange(id key, id* buffer, +GSLeftInsertionPointForKeyInSortedRange(id key, id *buffer, NSRange range, NSComparator comparator); /** @@ -139,7 +139,7 @@ */ static inline NSComparisonResult GSCompareUsingDescriptorOrComparator(id first, id second, id descOrComp, - GSComparisonType cmprType, void* context) + GSComparisonType cmprType, void *context) { switch (cmprType) Modified: libs/base/trunk/Source/GSTimSort.m URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Source/GSTimSort.m?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/Source/GSTimSort.m (original) +++ libs/base/trunk/Source/GSTimSort.m Fri Jul 15 13:30:07 2016 @@ -295,8 +295,6 @@ GSComparisonTypeComparatorBlock, NULL); } -#if GS_USE_TIMSORT - static inline void reverseRange(id *buffer, NSRange r) { @@ -476,7 +474,7 @@ static IMP mergeHighImp; static IMP ensureCapImp; -@interface GSTimSortDescriptor : NSObject +@interface GSTimSortPlaceHolder : NSObject { id *objects; NSRange sortRange; @@ -511,7 +509,7 @@ GSComparisonType comparisonType, void *context); -@implementation GSTimSortDescriptor +@implementation GSTimSortPlaceHolder + (void) load { _GSSortStable = _GSTimSort; @@ -519,7 +517,7 @@ + (void) initialize { - if ([GSTimSortDescriptor class] == [self class]) + if ([GSTimSortPlaceHolder class] == [self class]) { // We need to be fast, so we cache a lot of IMPs pushRunImp = @@ -539,6 +537,11 @@ } } ++ (void) setUnstable +{ + _GSSortUnstable = _GSTimSort; // Use for unstable even though we are stable +} + - (id) initWithObjects: (id*)theObjects sortRange: (NSRange)theSortRange descriptorOrComparator: (id)descriptorOrComparator @@ -552,7 +555,7 @@ { return nil; } - /* GSTimSortDescriptors are ephemeral objects that just track state, so we + /* GSTimSortPlaceHolders are ephemeral objects that just track state, so we * don't bother making sure that the objects don't go away. */ objects = theObjects; @@ -1107,7 +1110,7 @@ NSUInteger sortEnd = NSMaxRange(sortRange); NSUInteger sortLen = sortRange.length; NSUInteger minimalRunLen = 0; - GSTimSortDescriptor *desc = nil; + GSTimSortPlaceHolder *desc = nil; if (sortLen < 2) { // Don't sort anything that doesn't contain at least two elements. @@ -1116,16 +1119,17 @@ if (sortLen < GS_MIN_MERGE) { - miniTimSort(objects, sortRange, sortDescriptorOrComparator, comparisonType, context); + miniTimSort(objects, sortRange, + sortDescriptorOrComparator, comparisonType, context); return; } // Now we need a timsort descriptor for state-tracking. - desc = [[GSTimSortDescriptor alloc] initWithObjects: objects - sortRange: sortRange - descriptorOrComparator: sortDescriptorOrComparator - comparisonType: comparisonType - functionContext: context]; + desc = [[GSTimSortPlaceHolder alloc] initWithObjects: objects + sortRange: sortRange + descriptorOrComparator: sortDescriptorOrComparator + comparisonType: comparisonType + functionContext: context]; NS_DURING { @@ -1172,4 +1176,3 @@ [desc release]; } -#endif Modified: libs/base/trunk/Source/NSSortDescriptor.m URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/Source/NSSortDescriptor.m?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/Source/NSSortDescriptor.m (original) +++ libs/base/trunk/Source/NSSortDescriptor.m Fri Jul 15 13:30:07 2016 @@ -30,6 +30,8 @@ #import "Foundation/NSCoder.h" #import "Foundation/NSException.h" #import "Foundation/NSKeyValueCoding.h" +#import "Foundation/NSNotification.h" +#import "Foundation/NSUserDefaults.h" #import "GNUstepBase/GSObjCRuntime.h" #import "GSPrivate.h" @@ -41,34 +43,61 @@ #pragma clang diagnostic ignored "-Wreceiver-forward-class" #endif -#if GS_USE_TIMSORT -@interface GSTimSortDescriptor : NSObject -@end -#endif -#if GS_USE_QUICKSORT +@interface GSTimSortPlaceHolder : NSObject ++ (void) setUnstable; +@end @interface GSQuickSortPlaceHolder : NSObject -@end -#endif -#if GS_USE_SHELLSORT ++ (void) setUnstable; +@end @interface GSShellSortPlaceHolder : NSObject -@end -#endif ++ (void) setUnstable; +@end @implementation NSSortDescriptor ++ (void) defaultsChanged: (NSNotification*)n +{ + NSUserDefaults *defs = (NSUserDefaults*)[n object]; + NSString *algorithm; + + algorithm = [defs stringForKey: @"GSSortAlgorithm"]; + if ([algorithm isEqual: @"QuickSort"]) + { + [GSQuickSortPlaceHolder setUnstable]; + } + else if ([algorithm isEqual: @"ShellSort"]) + { + [GSShellSortPlaceHolder setUnstable]; + } + else if ([algorithm isEqual: @"TimSort"]) + { + [GSTimSortPlaceHolder setUnstable]; + } + else + { + [GSTimSortPlaceHolder setUnstable]; + if (nil != algorithm) + { + NSLog(@"GSSortAlgorithm default unknown value (%@)", algorithm); + } + } +} + + (void) initialize { if (NO == initialized) { -#if GS_USE_TIMSORT - [GSTimSortDescriptor class]; -#endif -#if GS_USE_QUICKSORT - [GSQuickSortPlaceHolder class]; -#endif -#if GS_USE_SHELLSORT - [GSShellSortPlaceHolder class]; -#endif + NSNotificationCenter *nc; + NSUserDefaults *defs; + + [GSTimSortPlaceHolder class]; // default stable sort + nc = [NSNotificationCenter defaultCenter]; + defs = [NSUserDefaults standardUserDefaults]; + [nc addObserver: self + selector: @selector(defaultsChanged:) + name: NSUserDefaultsDidChangeNotification + object: defs]; + [self defaultsChanged: nil]; // set unstable sort initialized = YES; } } Modified: libs/base/trunk/configure URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/configure?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/configure (original) +++ libs/base/trunk/configure Fri Jul 15 13:30:07 2016 @@ -821,7 +821,6 @@ enable_libdispatch with_gmp_include with_gmp_library -with_sort_algorithm with_gdomap_port enable_setuid_gdomap ' @@ -1572,9 +1571,6 @@ if not using icu-config) --with-gmp-include=PATH include path for gmp headers --with-gmp-library=PATH library path for gmp libraries - --with-sort-algorithm=ALG force use of a specific sorting algorithm. - Possible values are timsort, quicksort, and shellsort. - Defaults to shellsort (others broken). --with-gdomap-port=PORT alternative port for gdomap Some influential environment variables: @@ -12522,38 +12518,6 @@ #-------------------------------------------------------------------- -# Check which sorting algorithm to use. -#-------------------------------------------------------------------- - -# Check whether --with-sort-algorithm was given. -if test "${with_sort_algorithm+set}" = set; then : - withval=$with_sort_algorithm; sort_algorithm="$withval" -else - sort_algorithm="shellsort" -fi - - -if test "$sort_algorithm" = "timsort"; then - -$as_echo "#define GS_USE_TIMSORT 1" >>confdefs.h - -else - if test "$sort_algorithm" = "quicksort"; then - -$as_echo "#define GS_USE_QUICKSORT 1" >>confdefs.h - - else - if test "$sort_algorithm" = "shellsort"; then - -$as_echo "#define GS_USE_SHELLSORT 1" >>confdefs.h - - else - as_fn_error $? "Unknown sort_algorithm defined!" "$LINENO" 5 - fi - fi -fi - -#-------------------------------------------------------------------- # Check whether nl_langinfo(CODESET) is supported, needed by Unicode.m. #-------------------------------------------------------------------- Modified: libs/base/trunk/configure.ac URL: http://svn.gna.org/viewcvs/gnustep/libs/base/trunk/configure.ac?rev=39998&r1=39997&r2=39998&view=diff ============================================================================== --- libs/base/trunk/configure.ac (original) +++ libs/base/trunk/configure.ac Fri Jul 15 13:30:07 2016 @@ -3431,29 +3431,6 @@ #-------------------------------------------------------------------- -# Check which sorting algorithm to use. -#-------------------------------------------------------------------- -AC_ARG_WITH(sort-algorithm, - [ --with-sort-algorithm=ALG force use of a specific sorting algorithm. - Possible values are timsort, quicksort, and shellsort. - Defaults to shellsort (others broken).], - sort_algorithm="$withval", sort_algorithm="shellsort") - -if test "$sort_algorithm" = "timsort"; then - AC_DEFINE(GS_USE_TIMSORT,1,[Build in/use timsort]) -else - if test "$sort_algorithm" = "quicksort"; then - AC_DEFINE(GS_USE_QUICKSORT,1,[Build in/use quicksort]) - else - if test "$sort_algorithm" = "shellsort"; then - AC_DEFINE(GS_USE_SHELLSORT,1,[Build in/use shellsort]) - else - AC_MSG_ERROR([Unknown sort_algorithm defined!]) - fi - fi -fi - -#-------------------------------------------------------------------- # Check whether nl_langinfo(CODESET) is supported, needed by Unicode.m. #-------------------------------------------------------------------- AM_LANGINFO_CODESET _______________________________________________ Gnustep-cvs mailing list Gnustep-cvs@gna.org https://mail.gna.org/listinfo/gnustep-cvs