#define Menes_Menes_H
#include "Menes/invocationWithSelector.h"
+#include "Menes/radixSortWithSelector.h"
#include "Menes/yieldToSelector.h"
#endif//Menes_Menes_H
--- /dev/null
+/* 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
--- /dev/null
+/* 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
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) {
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();
_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();
}
projects / cydia.git / commitdiff
