diff options
| -rw-r--r-- | Menes/Menes.h | 1 | ||||
| -rw-r--r-- | Menes/radixSortWithSelector.h | 51 | ||||
| -rw-r--r-- | Menes/radixSortWithSelector.mm | 112 | ||||
| -rw-r--r-- | MobileCydia.mm | 85 |
4 files changed, 168 insertions, 81 deletions
diff --git a/Menes/Menes.h b/Menes/Menes.h index 737520d..99f3029 100644 --- a/Menes/Menes.h +++ b/Menes/Menes.h @@ -41,6 +41,7 @@ #define Menes_Menes_H #include "Menes/invocationWithSelector.h" +#include "Menes/radixSortWithSelector.h" #include "Menes/yieldToSelector.h" #endif//Menes_Menes_H diff --git a/Menes/radixSortWithSelector.h b/Menes/radixSortWithSelector.h new file mode 100644 index 0000000..d148cb3 --- /dev/null +++ b/Menes/radixSortWithSelector.h @@ -0,0 +1,51 @@ +/* Cydia - iPhone UIKit Front-End for Debian APT + * Copyright (C) 2008-2011 Jay Freeman (saurik) +*/ + +/* Modified BSD License {{{ */ +/* + * Redistribution and use in source and binary + * forms, with or without modification, are permitted + * provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the + * above copyright notice, this list of conditions + * and the following disclaimer. + * 2. Redistributions in binary form must reproduce the + * above copyright notice, this list of conditions + * and the following disclaimer in the documentation + * and/or other materials provided with the + * distribution. + * 3. The name of the author may not be used to endorse + * or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, + * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR + * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +/* }}} */ + +#ifndef Menes_radixSort_H +#define Menes_radixSort_H + +#include <Foundation/Foundation.h> + +typedef uint32_t (*MenesRadixSortFunction)(id, void *); + +@interface NSMutableArray (MenesRadixSortWithSelector) +- (void) radixSortUsingFunction:(MenesRadixSortFunction)function withContext:(void *)argument; +@end + +#endif//Menes_radixSort_H diff --git a/Menes/radixSortWithSelector.mm b/Menes/radixSortWithSelector.mm new file mode 100644 index 0000000..949a14b --- /dev/null +++ b/Menes/radixSortWithSelector.mm @@ -0,0 +1,112 @@ +/* Cydia - iPhone UIKit Front-End for Debian APT + * Copyright (C) 2008-2011 Jay Freeman (saurik) +*/ + +/* Modified BSD License {{{ */ +/* + * Redistribution and use in source and binary + * forms, with or without modification, are permitted + * provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the + * above copyright notice, this list of conditions + * and the following disclaimer. + * 2. Redistributions in binary form must reproduce the + * above copyright notice, this list of conditions + * and the following disclaimer in the documentation + * and/or other materials provided with the + * distribution. + * 3. The name of the author may not be used to endorse + * or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, + * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR + * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +/* }}} */ + +#include "CyteKit/UCPlatform.h" + +#include "Menes/radixSortWithSelector.h" + +struct RadixItem_ { + size_t index; + uint32_t key; +}; + +@implementation NSMutableArray (MenesRadixSortWithSelector) + +- (void) radixSortUsingFunction:(MenesRadixSortFunction)function withContext:(void *)argument { + size_t count([self count]); + struct RadixItem_ *swap(new RadixItem_[count * 2]); + + for (size_t i(0); i != count; ++i) { + RadixItem_ &item(swap[i]); + item.index = i; + + id object([self objectAtIndex:i]); + item.key = function(object, argument); + } + + struct RadixItem_ *lhs(swap), *rhs(swap + count); + + static const size_t width = 32; + static const size_t bits = 11; + static const size_t slots = 1 << bits; + static const size_t passes = (width + (bits - 1)) / bits; + + size_t *hist(new size_t[slots]); + + for (size_t pass(0); pass != passes; ++pass) { + memset(hist, 0, sizeof(size_t) * slots); + + for (size_t i(0); i != count; ++i) { + uint32_t key(lhs[i].key); + key >>= pass * bits; + key &= _not(uint32_t) >> width - bits; + ++hist[key]; + } + + size_t offset(0); + for (size_t i(0); i != slots; ++i) { + size_t local(offset); + offset += hist[i]; + hist[i] = local; + } + + for (size_t i(0); i != count; ++i) { + uint32_t key(lhs[i].key); + key >>= pass * bits; + key &= _not(uint32_t) >> width - bits; + rhs[hist[key]++] = lhs[i]; + } + + RadixItem_ *tmp(lhs); + lhs = rhs; + rhs = tmp; + } + + delete [] hist; + + const void **values(new const void *[count]); + for (size_t i(0); i != count; ++i) + values[i] = [self objectAtIndex:lhs[i].index]; + CFArrayReplaceValues((CFMutableArrayRef) self, CFRangeMake(0, count), values, count); + delete [] values; + + delete [] swap; +} + +@end diff --git a/MobileCydia.mm b/MobileCydia.mm index fcccdd5..2a76717 100644 --- a/MobileCydia.mm +++ b/MobileCydia.mm @@ -279,83 +279,6 @@ static const NSStringCompareOptions MatchCompareOptions_ = NSLiteralSearch | NSC static const NSStringCompareOptions LaxCompareOptions_ = NSNumericSearch | NSDiacriticInsensitiveSearch | NSWidthInsensitiveSearch | NSCaseInsensitiveSearch; static const CFStringCompareFlags LaxCompareFlags_ = kCFCompareCaseInsensitive | kCFCompareNonliteral | kCFCompareLocalized | kCFCompareNumerically | kCFCompareWidthInsensitive | kCFCompareForcedOrdering; -/* Radix Sort {{{ */ -typedef uint32_t (*SKRadixFunction)(id, void *); - -@interface NSMutableArray (Radix) -- (void) radixSortUsingFunction:(SKRadixFunction)function withContext:(void *)argument; -@end - -struct RadixItem_ { - size_t index; - uint32_t key; -}; - -@implementation NSMutableArray (Radix) - -- (void) radixSortUsingFunction:(SKRadixFunction)function withContext:(void *)argument { - size_t count([self count]); - struct RadixItem_ *swap(new RadixItem_[count * 2]); - - for (size_t i(0); i != count; ++i) { - RadixItem_ &item(swap[i]); - item.index = i; - - id object([self objectAtIndex:i]); - item.key = function(object, argument); - } - - struct RadixItem_ *lhs(swap), *rhs(swap + count); - - static const size_t width = 32; - static const size_t bits = 11; - static const size_t slots = 1 << bits; - static const size_t passes = (width + (bits - 1)) / bits; - - size_t *hist(new size_t[slots]); - - for (size_t pass(0); pass != passes; ++pass) { - memset(hist, 0, sizeof(size_t) * slots); - - for (size_t i(0); i != count; ++i) { - uint32_t key(lhs[i].key); - key >>= pass * bits; - key &= _not(uint32_t) >> width - bits; - ++hist[key]; - } - - size_t offset(0); - for (size_t i(0); i != slots; ++i) { - size_t local(offset); - offset += hist[i]; - hist[i] = local; - } - - for (size_t i(0); i != count; ++i) { - uint32_t key(lhs[i].key); - key >>= pass * bits; - key &= _not(uint32_t) >> width - bits; - rhs[hist[key]++] = lhs[i]; - } - - RadixItem_ *tmp(lhs); - lhs = rhs; - rhs = tmp; - } - - delete [] hist; - - const void **values(new const void *[count]); - for (size_t i(0); i != count; ++i) - values[i] = [self objectAtIndex:lhs[i].index]; - CFArrayReplaceValues((CFMutableArrayRef) self, CFRangeMake(0, count), values, count); - delete [] values; - - delete [] swap; -} - -@end -/* }}} */ /* Insertion Sort {{{ */ CFIndex SKBSearch_(const void *element, CFIndex elementSize, const void *list, CFIndex count, CFComparatorFunction comparator, void *context) { @@ -3508,9 +3431,9 @@ static NSString *Warning_; packages_ = [[NSArray alloc] initWithObjects:&packages.front() count:packages.size()]; _trace();*/ - [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast<SKRadixFunction>(&PackagePrefixRadix) withContext:reinterpret_cast<void *>(16)]; - [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast<SKRadixFunction>(&PackagePrefixRadix) withContext:reinterpret_cast<void *>(4)]; - [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast<SKRadixFunction>(&PackagePrefixRadix) withContext:reinterpret_cast<void *>(0)]; + [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast<MenesRadixSortFunction>(&PackagePrefixRadix) withContext:reinterpret_cast<void *>(16)]; + [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast<MenesRadixSortFunction>(&PackagePrefixRadix) withContext:reinterpret_cast<void *>(4)]; + [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast<MenesRadixSortFunction>(&PackagePrefixRadix) withContext:reinterpret_cast<void *>(0)]; /*_trace(); PrintTimes(); @@ -7306,7 +7229,7 @@ bool DepSubstrate(const pkgCache::VerIterator &iterator) { _end _trace(); _profile(ChangesController$_reloadPackages$radixSort) - [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast<SKRadixFunction>(&PackageChangesRadix) withContext:NULL]; + [(NSMutableArray *) packages_ radixSortUsingFunction:reinterpret_cast<MenesRadixSortFunction>(&PackageChangesRadix) withContext:NULL]; _end _trace(); } |