From 187cb9203a03e766172b266b8f99bd9b0fd0ba05 Mon Sep 17 00:00:00 2001 From: "Jay Freeman (saurik)" Date: Wed, 15 Feb 2017 10:50:53 -0800 Subject: Cache sorts (really really important for Chinese). --- MobileCydia.mm | 136 ++++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 90 insertions(+), 46 deletions(-) diff --git a/MobileCydia.mm b/MobileCydia.mm index 3dec86e..7c91a5d 100644 --- a/MobileCydia.mm +++ b/MobileCydia.mm @@ -1119,7 +1119,7 @@ typedef std::map< unsigned long, _H > SourceMap; SourceMap sourceMap_; _H sourceList_; - CFMutableArrayRef packages_; + _H packages_; _transient NSObject *delegate_; _transient NSObject *progress_; @@ -2143,6 +2143,8 @@ struct ParsedPackage { } - (Package *) initWithVersion:(pkgCache::VerIterator)version withZone:(NSZone *)zone inPool:(CYPool *)pool database:(Database *)database; ++ (Package *) newPackageWithIterator:(pkgCache::PkgIterator)iterator withZone:(NSZone *)zone inPool:(CYPool *)pool database:(Database *)database; + + (Package *) packageWithIterator:(pkgCache::PkgIterator)iterator withZone:(NSZone *)zone inPool:(CYPool *)pool database:(Database *)database; - (pkgCache::PkgIterator) iterator; @@ -2712,7 +2714,7 @@ struct PackageNameOrdering : _end } return self; } -+ (Package *) packageWithIterator:(pkgCache::PkgIterator)iterator withZone:(NSZone *)zone inPool:(CYPool *)pool database:(Database *)database { ++ (Package *) newPackageWithIterator:(pkgCache::PkgIterator)iterator withZone:(NSZone *)zone inPool:(CYPool *)pool database:(Database *)database { pkgCache::VerIterator version; _profile(Package$packageWithIterator$GetCandidateVer) @@ -2737,13 +2739,14 @@ struct PackageNameOrdering : ]; _end - _profile(Package$packageWithIterator$Autorelease) - package = [package autorelease]; - _end - return package; } +// XXX: just in case a Cydia extension is using this (I bet this is unlikely, though, due to CYPool?) ++ (Package *) packageWithIterator:(pkgCache::PkgIterator)iterator withZone:(NSZone *)zone inPool:(CYPool *)pool database:(Database *)database { + return [[self newPackageWithIterator:iterator withZone:zone inPool:pool database:database] autorelease]; +} + - (pkgCache::PkgIterator) iterator { return iterator_; } @@ -3328,8 +3331,8 @@ struct PackageNameOrdering : } - (void) setIndex:(size_t)index { - if (metadata_->index_ != index) - metadata_->index_ = index; + if (metadata_->index_ != index + 1) + metadata_->index_ = index + 1; } - (CYString &) cyname { @@ -3520,12 +3523,11 @@ class CydiaLogCleaner : } - (void) releasePackages { - CFArrayApplyFunction(packages_, CFRangeMake(0, CFArrayGetCount(packages_)), reinterpret_cast(&CFRelease), NULL); - CFArrayRemoveAllValues(packages_); + packages_ = nil; } - (bool) hasPackages { - return CFArrayGetCount(packages_) != 0; + return [packages_ count] != 0; } - (void) dealloc { @@ -3651,7 +3653,7 @@ class CydiaLogCleaner : , "any" #endif )); - return iterator.end() ? nil : [Package packageWithIterator:iterator withZone:NULL inPool:NULL database:self]; + return iterator.end() ? nil : [[Package newPackageWithIterator:iterator withZone:NULL inPool:NULL database:self] autorelease]; } } - (id) init { @@ -3664,13 +3666,6 @@ class CydiaLogCleaner : zone_ = NSCreateZone(1024 * 1024, 256 * 1024, NO); - size_t capacity(MetaFile_->active_); - if (capacity == 0) - capacity = 16384; - else - capacity += 1024; - - packages_ = CFArrayCreateMutable(kCFAllocatorDefault, capacity, NULL); sourceList_ = [NSMutableArray arrayWithCapacity:16]; int fds[2]; @@ -3739,7 +3734,7 @@ class CydiaLogCleaner : } - (NSArray *) packages { - return (NSArray *) packages_; + return packages_; } - (NSArray *) sources { @@ -3956,38 +3951,86 @@ class CydiaLogCleaner : } { - /*std::vector packages; - packages.reserve(std::max(10000U, [packages_ count] + 1000)); - packages_ = nil;*/ + size_t capacity(MetaFile_->active_); + if (capacity == 0) + capacity = 128*1024; + else + capacity += 1024; + std::vector packages; + packages.reserve(capacity); + size_t lost(0); + + size_t last(0); _profile(reloadDataWithInvocation$packageWithIterator) for (pkgCache::PkgIterator iterator = cache_->PkgBegin(); !iterator.end(); ++iterator) - if (Package *package = [Package packageWithIterator:iterator withZone:zone_ inPool:&pool_ database:self]) - //packages.push_back(package); - CFArrayAppendValue(packages_, CFRetain(package)); + if (Package *package = [Package newPackageWithIterator:iterator withZone:zone_ inPool:&pool_ database:self]) { + if (unsigned index = package.metadata->index_) { + --index; + if (packages.size() == index) { + packages.push_back(package); + } else if (packages.size() <= index) { + packages.resize(index + 1, nil); + packages[index] = package; + continue; + } else { + std::swap(package, packages[index]); + if (package != nil) + goto lost; + if (last != index) + continue; + } + } else lost: { + ++lost; + if (last == packages.size()) { + packages.push_back(package); + ++last; + } else { + packages[last] = package; + ++last; + } + } + + for (; last != packages.size(); ++last) + if (packages[last] == nil) + break; + } _end + for (size_t next(last + 1); last != packages.size(); ++last, ++next) { + while (true) { + if (next == packages.size()) + goto done; + if (packages[next] != nil) + break; + ++next; + } - /*if (packages.empty()) - packages_ = [[NSArray alloc] init]; - else - packages_ = [[NSArray alloc] initWithObjects:&packages.front() count:packages.size()]; - _trace();*/ + std::swap(packages[last], packages[next]); + } done:; - _profile(reloadDataWithInvocation$radix$8) - [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast(&PackagePrefixRadix) withContext:reinterpret_cast(8)]; - _end + packages.resize(last); - _profile(reloadDataWithInvocation$radix$4) - [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast(&PackagePrefixRadix) withContext:reinterpret_cast(4)]; - _end + packages_ = [[[NSMutableArray alloc] initWithObjects:packages.data() count:packages.size()] autorelease]; - _profile(reloadDataWithInvocation$radix$0) - [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast(&PackagePrefixRadix) withContext:reinterpret_cast(0)]; - _end + if (lost > 128) { + NSLog(@"lost = %zu", lost); + + _profile(reloadDataWithInvocation$radix$8) + [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast(&PackagePrefixRadix) withContext:reinterpret_cast(8)]; + _end + + _profile(reloadDataWithInvocation$radix$4) + [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast(&PackagePrefixRadix) withContext:reinterpret_cast(4)]; + _end + + _profile(reloadDataWithInvocation$radix$0) + [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast(&PackagePrefixRadix) withContext:reinterpret_cast(0)]; + _end + } _profile(reloadDataWithInvocation$insertion) - CFArrayInsertionSortValues(packages_, CFRangeMake(0, CFArrayGetCount(packages_)), reinterpret_cast(&PackageNameCompare), NULL); + CFArrayInsertionSortValues((CFMutableArrayRef) (NSArray *) packages_, CFRangeMake(0, packages.size()), reinterpret_cast(&PackageNameCompare), NULL); _end /*_profile(reloadDataWithInvocation$CFQSortArray) @@ -4006,11 +4049,12 @@ class CydiaLogCleaner : [packages_ sortUsingFunction:reinterpret_cast(&PackageNameCompare) context:NULL]; _end*/ - - size_t count(CFArrayGetCount(packages_)); - MetaFile_->active_ = count; - for (size_t index(0); index != count; ++index) - [(Package *) CFArrayGetValueAtIndex(packages_, index) setIndex:index]; + MetaFile_->active_ = packages.size(); + for (size_t index(0), count(packages.size()); index != count; ++index) { + auto package((Package *) [packages_ objectAtIndex:index]); + [package setIndex:index]; + [package release]; + } } } } -- cgit v1.2.3