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 <[email protected]>
+
+ * 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 <[email protected]>
* 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
[email protected]
https://mail.gna.org/listinfo/gnustep-cvs
