From: Jay Freeman (saurik) <saurik@saurik.com>
Date: Wed, 15 Feb 2017 19:52:00 +0000 (-0800)
Subject: Amortize linear probing with a binary search sort.
X-Git-Tag: v1.1.29~4
X-Git-Url: https://git.saurik.com/cydia.git/commitdiff_plain/8f246508d03eb6540bf07f6478cf40cf656a5e1c

Amortize linear probing with a binary search sort.
---

diff --git a/MobileCydia.mm b/MobileCydia.mm
index 7c91a5da..ea5be263 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