Menes/radixSortWithSelector.mm

   1 /* Cydia - iPhone UIKit Front-End for Debian APT
   2  * Copyright (C) 2008-2011  Jay Freeman (saurik)
   3 */
   4
   5 /* Modified BSD License {{{ */
   6 /*
   7  *        Redistribution and use in source and binary
   8  * forms, with or without modification, are permitted
   9  * provided that the following conditions are met:
  10  *
  11  * 1. Redistributions of source code must retain the
  12  *    above copyright notice, this list of conditions
  13  *    and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the
  15  *    above copyright notice, this list of conditions
  16  *    and the following disclaimer in the documentation
  17  *    and/or other materials provided with the
  18  *    distribution.
  19  * 3. The name of the author may not be used to endorse
  20  *    or promote products derived from this software
  21  *    without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS''
  24  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
  25  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  26  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
  28  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  29  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  31  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  32  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  33  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
  34  * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  35  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  36  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  37 */
  38 /* }}} */
  39
  40 #include "CyteKit/UCPlatform.h"
  41
  42 #include "Menes/radixSortWithSelector.h"
  43
  44 #include <objc/runtime.h>
  45
  46 struct RadixItem_ {
  47     size_t index;
  48     uint32_t key;
  49 };
  50
  51 @implementation NSMutableArray (MenesRadixSortWithSelector)
  52
  53 - (void) radixSortUsingFunction:(MenesRadixSortFunction)function withContext:(void *)argument {
  54     size_t count([self count]);
  55     struct RadixItem_ *swap(new RadixItem_[count * 2]);
  56
  57     for (size_t i(0); i != count; ++i) {
  58         RadixItem_ &item(swap[i]);
  59         item.index = i;
  60
  61         id object([self objectAtIndex:i]);
  62         item.key = function(object, argument);
  63     }
  64
  65     struct RadixItem_ *lhs(swap), *rhs(swap + count);
  66
  67     static const size_t width = 32;
  68     static const size_t bits = 11;
  69     static const size_t slots = 1 << bits;
  70     static const size_t passes = (width + (bits - 1)) / bits;
  71
  72     size_t *hist(new size_t[slots]);
  73
  74     for (size_t pass(0); pass != passes; ++pass) {
  75         memset(hist, 0, sizeof(size_t) * slots);
  76
  77         for (size_t i(0); i != count; ++i) {
  78             uint32_t key(lhs[i].key);
  79             key >>= pass * bits;
  80             key &= _not(uint32_t) >> width - bits;
  81             ++hist[key];
  82         }
  83
  84         size_t offset(0);
  85         for (size_t i(0); i != slots; ++i) {
  86             size_t local(offset);
  87             offset += hist[i];
  88             hist[i] = local;
  89         }
  90
  91         for (size_t i(0); i != count; ++i) {
  92             uint32_t key(lhs[i].key);
  93             key >>= pass * bits;
  94             key &= _not(uint32_t) >> width - bits;
  95             rhs[hist[key]++] = lhs[i];
  96         }
  97
  98         RadixItem_ *tmp(lhs);
  99         lhs = rhs;
 100         rhs = tmp;
 101     }
 102
 103     delete [] hist;
 104
 105     const void **values(new const void *[count]);
 106     for (size_t i(0); i != count; ++i)
 107         values[i] = [self objectAtIndex:lhs[i].index];
 108     CFArrayReplaceValues((CFMutableArrayRef) self, CFRangeMake(0, count), values, count);
 109     delete [] values;
 110
 111     delete [] swap;
 112 }
 113
 114 - (void) radixSortUsingSelector:(SEL)selector {
 115     if ([self count] == 0)
 116         return;
 117
 118     IMP imp(class_getMethodImplementation([[self lastObject] class], selector));
 119     [self radixSortUsingFunction:reinterpret_cast<MenesRadixSortFunction>(imp) withContext:selector];
 120 }
 121
 122 @end