runtime/objc-sel-set.mm

   1 /*
   2  * Copyright (c) 1999-2004,2008 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 /*
  25  * objc-sel-set.h
  26  * A cut-down copy of CFSet used for SEL uniquing.
  27  */
  28
  29
  30 // NOTE: even on a 64-bit system, the implementation is still limited
  31 // to 32-bit integers (like, the count), but SEL can be any size.
  32
  33 #include <stdint.h>
  34 #include "objc-private.h"
  35 #include "objc-sel-set.h"
  36
  37 #if !SUPPORT_MOD
  38 // mod-free power of 2 version
  39
  40 #define CONSTRAIN(val, range) ((val) & ((range)-1))
  41 #define SIZE 27
  42
  43 static const uint32_t __objc_sel_set_capacities[SIZE+1] = {
  44     3, 6, 12, 24, 48,  96, 192, 384,  768, 1536, 3072, 6144, 12288, 24576,
  45     49152,  98304, 196608, 393216,  786432, 1572864, 3145728, 6291456,
  46     12582912, 25165824, 50331648, 100663296, 201326592, UINT32_MAX
  47 };
  48
  49 static const uint32_t __objc_sel_set_buckets[SIZE] = {    // powers of 2
  50     4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
  51     65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
  52     16777216, 33554432, 67108864, 134217728, 268435456
  53 };
  54
  55 #else
  56 // prime version
  57
  58 #define CONSTRAIN(val, range) ((val) % (range))
  59 #define SIZE 42
  60
  61 static const uint32_t __objc_sel_set_capacities[SIZE+1] = {
  62     4,  8, 17, 29, 47,  76, 123, 199, 322, 521,  843, 1364, 2207, 3571,
  63     5778,  9349, 15127, 24476, 39603,  64079, 103682, 167761, 271443,
  64     439204,  710647, 1149851, 1860498, 3010349, 4870847,  7881196, 12752043,
  65     20633239, 33385282, 54018521,  87403803, 141422324, 228826127, 370248451,
  66     599074578,  969323029, 1568397607, 2537720636U, UINT32_MAX
  67 };
  68
  69 static const uint32_t __objc_sel_set_buckets[SIZE] = {    // primes
  70     5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779,
  71     9349, 15121, 24473, 39607, 64081, 103681, 167759, 271429, 439199,
  72     710641, 1149857, 1860503, 3010349, 4870843, 7881193, 12752029, 20633237,
  73     33385273, 54018521, 87403763, 141422317, 228826121, 370248451, 599074561,
  74     969323023, 1568397599, 2537720629U, 4106118251U
  75 };
  76
  77 #endif
  78
  79 struct __objc_sel_set {
  80     uint32_t _count;            /* number of slots used */
  81     uint32_t _capacity;         /* maximum number of used slots */
  82     uint32_t _bucketsNum;       /* number of slots */
  83     SEL *_buckets;              /* can be NULL if not allocated yet */
  84 };
  85
  86 struct __objc_sel_set_finds {
  87     SEL match;
  88     uint32_t nomatch;
  89 };
  90
  91 // candidate may not be 0; match is 0 if not present
  92 static struct __objc_sel_set_finds __objc_sel_set_findBuckets(struct __objc_sel_set *sset, SEL candidate) {
  93     struct __objc_sel_set_finds ret = {0, 0xffffffff};
  94     uint32_t probe = CONSTRAIN((uint32_t)_objc_strhash((const char *)candidate), sset->_bucketsNum);
  95     for (;;) {
  96         SEL currentSel = sset->_buckets[probe];
  97         if (!currentSel) {
  98             ret.nomatch = probe;
  99             return ret;
 100         } else if (!ret.match && 0 == strcmp((const char *)currentSel, (const char *)candidate)) {
 101             ret.match = currentSel;
 102         }
 103         probe++;
 104         if (sset->_bucketsNum <= probe) {
 105             probe -= sset->_bucketsNum;
 106         }
 107     }
 108 }
 109
 110 // create a set with given starting capacity, will resize as needed
 111 struct __objc_sel_set *__objc_sel_set_create(size_t selrefs) {
 112     uint32_t idx;
 113
 114     struct __objc_sel_set *sset = (struct __objc_sel_set *)
 115         _malloc_internal(sizeof(struct __objc_sel_set));
 116     if (!sset) _objc_fatal("objc_sel_set failure");
 117     sset->_count = 0;
 118
 119     // heuristic to convert executable's selrefs count to table size
 120 #if TARGET_OS_IPHONE
 121     for (idx = 0; __objc_sel_set_capacities[idx] < selrefs; idx++);
 122     if (idx > 0 && selrefs < 1536) idx--;
 123 #else
 124     if (selrefs < 1024) selrefs = 1024;
 125     for (idx = 0; __objc_sel_set_capacities[idx] < selrefs; idx++);
 126     idx++;
 127 #endif
 128
 129     if (SIZE <= idx) _objc_fatal("objc_sel_set failure");
 130     sset->_capacity = __objc_sel_set_capacities[idx];
 131     sset->_bucketsNum = __objc_sel_set_buckets[idx];
 132     sset->_buckets = (SEL *)_calloc_internal(sset->_bucketsNum, sizeof(SEL));
 133     if (!sset->_buckets) _objc_fatal("objc_sel_set failure");
 134     return sset;
 135 }
 136
 137 // returns 0 on failure; candidate may not be 0
 138 SEL __objc_sel_set_get(struct __objc_sel_set *sset, SEL candidate) {
 139     return __objc_sel_set_findBuckets(sset, candidate).match;
 140 }
 141
 142 // value may not be 0; should not be called unless it is known the value is not in the set
 143 void __objc_sel_set_add(struct __objc_sel_set *sset, SEL value) {
 144     if (sset->_count == sset->_capacity) {
 145         SEL *oldbuckets = sset->_buckets;
 146         uint32_t oldnbuckets = sset->_bucketsNum;
 147         uint32_t idx, capacity = sset->_count + 1;
 148         for (idx = 0; __objc_sel_set_capacities[idx] < capacity; idx++);
 149         if (SIZE <= idx) _objc_fatal("objc_sel_set failure");
 150         sset->_capacity = __objc_sel_set_capacities[idx];
 151         sset->_bucketsNum = __objc_sel_set_buckets[idx];
 152         sset->_buckets = (SEL *)
 153             _calloc_internal(sset->_bucketsNum, sizeof(SEL));
 154         if (!sset->_buckets) _objc_fatal("objc_sel_set failure");
 155         for (idx = 0; idx < oldnbuckets; idx++) {
 156             SEL currentSel = oldbuckets[idx];
 157             if (currentSel) {
 158                 uint32_t nomatch = __objc_sel_set_findBuckets(sset, currentSel).nomatch;
 159                 sset->_buckets[nomatch] = currentSel;
 160             }
 161         }
 162         _free_internal(oldbuckets);
 163     }
 164     {
 165         uint32_t nomatch = __objc_sel_set_findBuckets(sset, value).nomatch;
 166         sset->_buckets[nomatch] = value;
 167         sset->_count++;
 168     }
 169 }