]>
Commit | Line | Data |
---|---|---|
de42680b | 1 | /* Cydia - iPhone UIKit Front-End for Debian APT |
6fa0bb60 | 2 | * Copyright (C) 2008-2014 Jay Freeman (saurik) |
de42680b JF |
3 | */ |
4 | ||
6d9696a5 | 5 | /* GNU General Public License, Version 3 {{{ */ |
de42680b | 6 | /* |
6d9696a5 JF |
7 | * Cydia is free software: you can redistribute it and/or modify |
8 | * it under the terms of the GNU General Public License as published | |
9 | * by the Free Software Foundation, either version 3 of the License, | |
10 | * or (at your option) any later version. | |
de42680b | 11 | * |
6d9696a5 JF |
12 | * Cydia is distributed in the hope that it will be useful, but |
13 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | * GNU General Public License for more details. | |
de42680b | 16 | * |
6d9696a5 JF |
17 | * You should have received a copy of the GNU General Public License |
18 | * along with Cydia. If not, see <http://www.gnu.org/licenses/>. | |
19 | **/ | |
de42680b JF |
20 | /* }}} */ |
21 | ||
22 | #include "CyteKit/UCPlatform.h" | |
23 | ||
24 | #include "Menes/radixSortWithSelector.h" | |
25 | ||
9c5737d5 JF |
26 | #include <objc/runtime.h> |
27 | ||
de42680b JF |
28 | struct RadixItem_ { |
29 | size_t index; | |
30 | uint32_t key; | |
31 | }; | |
32 | ||
33 | @implementation NSMutableArray (MenesRadixSortWithSelector) | |
34 | ||
35 | - (void) radixSortUsingFunction:(MenesRadixSortFunction)function withContext:(void *)argument { | |
36 | size_t count([self count]); | |
37 | struct RadixItem_ *swap(new RadixItem_[count * 2]); | |
38 | ||
39 | for (size_t i(0); i != count; ++i) { | |
40 | RadixItem_ &item(swap[i]); | |
41 | item.index = i; | |
42 | ||
43 | id object([self objectAtIndex:i]); | |
44 | item.key = function(object, argument); | |
45 | } | |
46 | ||
47 | struct RadixItem_ *lhs(swap), *rhs(swap + count); | |
48 | ||
49 | static const size_t width = 32; | |
50 | static const size_t bits = 11; | |
51 | static const size_t slots = 1 << bits; | |
52 | static const size_t passes = (width + (bits - 1)) / bits; | |
53 | ||
54 | size_t *hist(new size_t[slots]); | |
55 | ||
56 | for (size_t pass(0); pass != passes; ++pass) { | |
57 | memset(hist, 0, sizeof(size_t) * slots); | |
58 | ||
59 | for (size_t i(0); i != count; ++i) { | |
60 | uint32_t key(lhs[i].key); | |
61 | key >>= pass * bits; | |
62 | key &= _not(uint32_t) >> width - bits; | |
63 | ++hist[key]; | |
64 | } | |
65 | ||
66 | size_t offset(0); | |
67 | for (size_t i(0); i != slots; ++i) { | |
68 | size_t local(offset); | |
69 | offset += hist[i]; | |
70 | hist[i] = local; | |
71 | } | |
72 | ||
73 | for (size_t i(0); i != count; ++i) { | |
74 | uint32_t key(lhs[i].key); | |
75 | key >>= pass * bits; | |
76 | key &= _not(uint32_t) >> width - bits; | |
77 | rhs[hist[key]++] = lhs[i]; | |
78 | } | |
79 | ||
80 | RadixItem_ *tmp(lhs); | |
81 | lhs = rhs; | |
82 | rhs = tmp; | |
83 | } | |
84 | ||
85 | delete [] hist; | |
86 | ||
87 | const void **values(new const void *[count]); | |
88 | for (size_t i(0); i != count; ++i) | |
89 | values[i] = [self objectAtIndex:lhs[i].index]; | |
90 | CFArrayReplaceValues((CFMutableArrayRef) self, CFRangeMake(0, count), values, count); | |
91 | delete [] values; | |
92 | ||
93 | delete [] swap; | |
94 | } | |
95 | ||
9c5737d5 JF |
96 | - (void) radixSortUsingSelector:(SEL)selector { |
97 | if ([self count] == 0) | |
98 | return; | |
99 | ||
100 | IMP imp(class_getMethodImplementation([[self lastObject] class], selector)); | |
101 | [self radixSortUsingFunction:reinterpret_cast<MenesRadixSortFunction>(imp) withContext:selector]; | |
102 | } | |
103 | ||
de42680b | 104 | @end |