1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
/* Header file for sorting functions in GNUstep
Copyright (C) 2012 Free Software Foundation, Inc.
Written by: Niels Grewe <niels.grewe@halbordnung.de>
Date: September 2012
This file is part of the GNUstep Base Library.
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free
Software Foundation, Inc., 31 Milk Street #960789 Boston, MA 02196 USA.
*/
#import "Foundation/NSSortDescriptor.h"
#import "GNUstepBase/GSObjCRuntime.h"
#import "Foundation/NSException.h"
#import "GSPrivate.h"
enum
{
GSComparisonTypeSortDescriptor = 0, /** Comparison using NSSortDescriptor */
GSComparisonTypeComparatorBlock, /** Comparison using an NSComparator */
GSComparisonTypeFunction, /** Comparison using a comparison function of type
* NSInteger(*)(id,id,void*) */
GSComparisonTypeMax
};
typedef NSUInteger GSComparisonType;
/**
* This is the internal prototype of an unstable, non-concurrency safe sorting
* function that can be used either through NSComparator or NSSortDescriptor. It
* may or may not be implemented by one of the sorting implementations in
* GNUstep.
*/
extern void (*_GSSortUnstable)(id *buffer, NSRange range, id comparisonEntity,
GSComparisonType cmprType, void *context) GS_ATTRIB_PRIVATE;
/**
* This is the internal prototype of an stable, non-concurrency safe sorting
* function that can be used either through NSComparator or NSSortDescriptor.
* It may or may not be implemented by one of the sorting implementations in
* GNUstep.
*/
extern void (*_GSSortStable)(id *buffer, NSRange range, id comparisonEntity,
GSComparisonType cmprType, void *context) GS_ATTRIB_PRIVATE;
/**
* This is the internal prototype of an unstable, concurrency safe sorting
* function that can be used either through NSComparator or NSSortDescriptor.
* It may or may not be implemented by one of the sorting implementations in
* GNUstep.
*/
extern void (*_GSSortUnstableConcurrent)(id *buffer, NSRange range,
id comparisonEntity, GSComparisonType cmprType, void *context)
GS_ATTRIB_PRIVATE;
/**
* This is the internal prototype of an stable, concurrency safe sorting
* function that can be used either through NSComparator or NSSortDescriptor.
* It may or may not be implemented by one of the sorting implementations in
* GNUstep.
*/
extern void (*_GSSortStableConcurrent)(id *buffer, NSRange range,
id comparisonEntity, GSComparisonType cmprType, void *context)
GS_ATTRIB_PRIVATE;
/**
* GSSortUnstable() uses the above prototypes to provide sorting that does not
* make any specific guarantees. If no explicit unstable sorting algorithm is
* available, it will fall through to stable sorting.
*/
void
GSSortUnstable(id *buffer, NSRange range, id sortDecriptorOrCompatator,
GSComparisonType cmprType, void *context);
/**
* GSSortStable() uses one of the internal sorting algorithms to provide stable
* sorting. If no stable sorting method is available, it raises an exception.
*/
void
GSSortStable(id *buffer, NSRange range, id sortDecriptorOrCompatator,
GSComparisonType cmprType, void *context);
/**
* GSSortUnstableConcurrent() uses the above prototypes to provide sorting that
* does not make guarantees about stability, but allows for concurrent sorting.
* If no such sorting algorithm is available, it first falls through to stable
* concurrent sorting, then unstable non-concurrent sorting and finally stable
* concurrent sorting.
*/
void
GSSortUnstableConcurrent(id *buffer, NSRange range,
id sortDecriptorOrCompatator, GSComparisonType cmprType, void *context);
/**
* GSSortStableConcurrent() uses one of the internal sorting algorithms to
* provide stable sorting that may be executed concurrently. If no such
* algorithm is available, it falls through to non-concurrent GSSortStable().
*/
void
GSSortStableConcurrent(id *buffer, NSRange range, id sortDecriptorOrCompatator,
GSComparisonType cmprType, void *context);
/**
* This function finds the proper point for inserting a new key into a sorted
* range, placing the new key at the rightmost position of all equal keys.
*
* This function is provided using the implementation of the timsort algorithm.
*/
NSUInteger
GSRightInsertionPointForKeyInSortedRange(id key, id *buffer,
NSRange range, NSComparator comparator);
/**
* This function finds the proper point for inserting a new key into a sorted
* range, placing the new key at the leftmost position of all equal keys.
*
* This function is provided using the implementation of the timsort algorithm.
*/
NSUInteger
GSLeftInsertionPointForKeyInSortedRange(id key, id *buffer,
NSRange range, NSComparator comparator);
/**
* Convenience function to operate with sort descriptors,
* comparator blocks and functions.
*/
static inline NSComparisonResult
GSCompareUsingDescriptorOrComparator(id first, id second, id descOrComp,
GSComparisonType cmprType, void *context)
{
switch (cmprType)
{
case GSComparisonTypeSortDescriptor:
return [(NSSortDescriptor*)descOrComp compareObject: first
toObject: second];
case GSComparisonTypeComparatorBlock:
return CALL_NON_NULL_BLOCK(((NSComparator)descOrComp), first, second);
case GSComparisonTypeFunction:
return ((NSInteger (*)(id, id, void *))descOrComp)(first,
second, context);
default:
[NSException raise: @"NSInternalInconstitencyException"
format: @"Invalid comparison type"];
}
// Not reached:
return 0;
}
|
