Menes/radixSortWithSelector.mm

   1 /* Cydia - iPhone UIKit Front-End for Debian APT
   2  * Copyright (C) 2008-2013  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 @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
  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
 104 @end