Menes/radixSortWithSelector.mm

   1 /* Cydia - iPhone UIKit Front-End for Debian APT
   2  * Copyright (C) 2008-2015  Jay Freeman (saurik)
   3 */
   4
   5 /* GNU General Public License, Version 3 {{{ */
   6 /*
   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.
  11  *
  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.
  16  *
  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 **/
  20 /* }}} */
  21
  22 #include "CyteKit/UCPlatform.h"
  23
  24 #include "Menes/radixSortWithSelector.h"
  25
  26 #include <objc/runtime.h>
  27
  28 struct RadixItem_ {
  29     size_t index;
  30     uint32_t key;
  31 };
  32
  33 static RadixItem_ *CYRadixSort(struct RadixItem_ *swap, size_t count) {
  34     struct RadixItem_ *lhs(swap), *rhs(swap + count);
  35
  36     static const size_t width = 32;
  37     static const size_t bits = 11;
  38     static const size_t slots = 1 << bits;
  39     static const size_t passes = (width + (bits - 1)) / bits;
  40
  41     size_t *hist(new size_t[slots]);
  42
  43     for (size_t pass(0); pass != passes; ++pass) {
  44         memset(hist, 0, sizeof(size_t) * slots);
  45
  46         for (size_t i(0); i != count; ++i) {
  47             uint32_t key(lhs[i].key);
  48             key >>= pass * bits;
  49             key &= _not(uint32_t) >> width - bits;
  50             ++hist[key];
  51         }
  52
  53         size_t offset(0);
  54         for (size_t i(0); i != slots; ++i) {
  55             size_t local(offset);
  56             offset += hist[i];
  57             hist[i] = local;
  58         }
  59
  60         for (size_t i(0); i != count; ++i) {
  61             uint32_t key(lhs[i].key);
  62             key >>= pass * bits;
  63             key &= _not(uint32_t) >> width - bits;
  64             rhs[hist[key]++] = lhs[i];
  65         }
  66
  67         RadixItem_ *tmp(lhs);
  68         lhs = rhs;
  69         rhs = tmp;
  70     }
  71
  72     delete [] hist;
  73     return lhs;
  74 }
  75
  76 void CYRadixSortUsingFunction(id *self, size_t count, MenesRadixSortFunction function, void *argument) {
  77     struct RadixItem_ *swap(new RadixItem_[count * 2]);
  78
  79     for (size_t i(0); i != count; ++i) {
  80         RadixItem_ &item(swap[i]);
  81         item.index = i;
  82         item.key = function(self[i], argument);
  83     }
  84
  85     auto lhs(CYRadixSort(swap, count));
  86
  87     const void **values(new const void *[count]);
  88     for (size_t i(0); i != count; ++i)
  89         values[i] = self[lhs[i].index];
  90     memcpy(self, values, count * sizeof(id));
  91     delete [] values;
  92
  93     delete [] swap;
  94 }
  95
  96 @implementation NSMutableArray (MenesRadixSortWithSelector)
  97
  98 - (void) radixSortUsingFunction:(MenesRadixSortFunction)function withContext:(void *)argument {
  99     size_t count([self count]);
 100     struct RadixItem_ *swap(new RadixItem_[count * 2]);
 101
 102     for (size_t i(0); i != count; ++i) {
 103         RadixItem_ &item(swap[i]);
 104         item.index = i;
 105         item.key = function([self objectAtIndex:i], argument);
 106     }
 107
 108     auto lhs(CYRadixSort(swap, count));
 109
 110     const void **values(new const void *[count]);
 111     for (size_t i(0); i != count; ++i)
 112         values[i] = [self objectAtIndex:lhs[i].index];
 113     CFArrayReplaceValues((CFMutableArrayRef) self, CFRangeMake(0, count), values, count);
 114     delete [] values;
 115
 116     delete [] swap;
 117 }
 118
 119 - (void) radixSortUsingSelector:(SEL)selector {
 120     if ([self count] == 0)
 121         return;
 122
 123     IMP imp(class_getMethodImplementation([[self lastObject] class], selector));
 124     [self radixSortUsingFunction:reinterpret_cast<MenesRadixSortFunction>(imp) withContext:selector];
 125 }
 126
 127 @end