summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-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