summaryrefslogtreecommitdiff
path: root/MobileCydia.mm
diff options
context:
space:
mode:
authorJay Freeman (saurik) <saurik@saurik.com>2017-02-15 11:52:00 -0800
committerJay Freeman (saurik) <saurik@saurik.com>2017-02-15 11:52:00 -0800
commit8f246508d03eb6540bf07f6478cf40cf656a5e1c (patch)
treef64cee64d1945d302451ca3ab474c8ea35e5927c /MobileCydia.mm
parent187cb9203a03e766172b266b8f99bd9b0fd0ba05 (diff)
Amortize linear probing with a binary search sort.
Diffstat (limited to 'MobileCydia.mm')
-rw-r--r--MobileCydia.mm35
1 files changed, 15 insertions, 20 deletions
diff --git a/MobileCydia.mm b/MobileCydia.mm
index 7c91a5d..ea5be26 100644
--- a/MobileCydia.mm
+++ b/MobileCydia.mm
@@ -329,30 +329,18 @@ static const CFStringCompareFlags LaxCompareFlags_ = kCFCompareNumerically | kCF
/* Insertion Sort {{{ */
-CFIndex SKBSearch_(const void *element, CFIndex elementSize, const void *list, CFIndex count, CFComparatorFunction comparator, void *context) {
+template <typename Type_>
+CFIndex CFBSearch_(const Type_ &element, const void *list, CFIndex count, CFComparatorFunction comparator, void *context) {
const char *ptr = (const char *)list;
while (0 < count) {
CFIndex half = count / 2;
- const char *probe = ptr + elementSize * half;
- CFComparisonResult cr = comparator(element, probe, context);
- if (0 == cr) return (probe - (const char *)list) / elementSize;
- ptr = (cr < 0) ? ptr : probe + elementSize;
+ const char *probe = ptr + sizeof(Type_) * half;
+ CFComparisonResult cr = comparator(element, * (const Type_ *) probe, context);
+ if (0 == cr) return (probe - (const char *)list) / sizeof(Type_);
+ ptr = (cr < 0) ? ptr : probe + sizeof(Type_);
count = (cr < 0) ? half : (half + (count & 1) - 1);
}
- return (ptr - (const char *)list) / elementSize;
-}
-
-CFIndex CFBSearch_(const void *element, CFIndex elementSize, const void *list, CFIndex count, CFComparatorFunction comparator, void *context) {
- const char *ptr = (const char *)list;
- while (0 < count) {
- CFIndex half = count / 2;
- const char *probe = ptr + elementSize * half;
- CFComparisonResult cr = comparator(element, probe, context);
- if (0 == cr) return (probe - (const char *)list) / elementSize;
- ptr = (cr < 0) ? ptr : probe + elementSize;
- count = (cr < 0) ? half : (half + (count & 1) - 1);
- }
- return (ptr - (const char *)list) / elementSize;
+ return (ptr - (const char *)list) / sizeof(Type_);
}
void CFArrayInsertionSortValues(CFMutableArrayRef array, CFRange range, CFComparatorFunction comparator, void *context) {
@@ -367,7 +355,9 @@ void CFArrayInsertionSortValues(CFMutableArrayRef array, CFRange range, CFCompar
for (CFIndex index(1); index != range.length; ++index) {
const void *value(values[index]);
- //CFIndex correct(SKBSearch_(&value, sizeof(const void *), values, index, comparator, context));
+#if 0
+ CFIndex correct(CFBSearch_(value, values, index, comparator, context));
+#else
CFIndex correct(index);
while (comparator(value, values[correct - 1], context) == kCFCompareLessThan) {
#if HistogramInsertionSort > 1
@@ -375,7 +365,12 @@ void CFArrayInsertionSortValues(CFMutableArrayRef array, CFRange range, CFCompar
#endif
if (--correct == 0)
break;
+ if (index - correct >= 8) {
+ correct = CFBSearch_(value, values, correct, comparator, context);
+ break;
+ }
}
+#endif
if (correct != index) {
size_t offset(index - correct);
#if HistogramInsertionSort