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 !__OBJC2__
  38
  39
  40 #if !SUPPORT_MOD
  41 // mod-free power of 2 version
  42
  43 #define CONSTRAIN(val, range) ((val) & ((range)-1))
  44 #define SIZE 27
  45
  46 static const uint32_t __objc_sel_set_capacities[SIZE+1] = {
  47     3, 6, 12, 24, 48,  96, 192, 384,  768, 1536, 3072, 6144, 12288, 24576,
  48     49152,  98304, 196608, 393216,  786432, 1572864, 3145728, 6291456,
  49     12582912, 25165824, 50331648, 100663296, 201326592, UINT32_MAX
  50 };
  51
  52 static const uint32_t __objc_sel_set_buckets[SIZE] = {    // powers of 2
  53     4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
  54     65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
  55     16777216, 33554432, 67108864, 134217728, 268435456
  56 };
  57
  58 #else
  59 // prime version
  60
  61 #define CONSTRAIN(val, range) ((val) % (range))
  62 #define SIZE 42
  63
  64 static const uint32_t __objc_sel_set_capacities[SIZE+1] = {
  65     4,  8, 17, 29, 47,  76, 123, 199, 322, 521,  843, 1364, 2207, 3571,
  66     5778,  9349, 15127, 24476, 39603,  64079, 103682, 167761, 271443,
  67     439204,  710647, 1149851, 1860498, 3010349, 4870847,  7881196, 12752043,
  68     20633239, 33385282, 54018521,  87403803, 141422324, 228826127, 370248451,
  69     599074578,  969323029, 1568397607, 2537720636U, UINT32_MAX
  70 };
  71
  72 static const uint32_t __objc_sel_set_buckets[SIZE] = {    // primes
  73     5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779,
  74     9349, 15121, 24473, 39607, 64081, 103681, 167759, 271429, 439199,
  75     710641, 1149857, 1860503, 3010349, 4870843, 7881193, 12752029, 20633237,
  76     33385273, 54018521, 87403763, 141422317, 228826121, 370248451, 599074561,
  77     969323023, 1568397599, 2537720629U, 4106118251U
  78 };
  79
  80 #endif
  81
  82 struct __objc_sel_set {
  83     uint32_t _count;            /* number of slots used */
  84     uint32_t _capacity;         /* maximum number of used slots */
  85     uint32_t _bucketsNum;       /* number of slots */
  86     SEL *_buckets;              /* can be NULL if not allocated yet */
  87 };
  88
  89 struct __objc_sel_set_finds {
  90     SEL match;
  91     uint32_t nomatch;
  92 };
  93
  94 // candidate may not be 0; match is 0 if not present
  95 static struct __objc_sel_set_finds __objc_sel_set_findBuckets(struct __objc_sel_set *sset, SEL candidate) {
  96     struct __objc_sel_set_finds ret = {0, 0xffffffff};
  97     uint32_t probe = CONSTRAIN((uint32_t)_objc_strhash((const char *)candidate), sset->_bucketsNum);
  98     for (;;) {
  99         SEL currentSel = sset->_buckets[probe];
 100         if (!currentSel) {
 101             ret.nomatch = probe;
 102             return ret;
 103         } else if (!ret.match && 0 == strcmp((const char *)currentSel, (const char *)candidate)) {
 104             ret.match = currentSel;
 105         }
 106         probe++;
 107         if (sset->_bucketsNum <= probe) {
 108             probe -= sset->_bucketsNum;
 109         }
 110     }
 111 }
 112
 113 // create a set with given starting capacity, will resize as needed
 114 struct __objc_sel_set *__objc_sel_set_create(size_t selrefs) {
 115     uint32_t idx;
 116
 117     struct __objc_sel_set *sset = (struct __objc_sel_set *)
 118         malloc(sizeof(struct __objc_sel_set));
 119     if (!sset) _objc_fatal("objc_sel_set failure");
 120     sset->_count = 0;
 121
 122     // heuristic to convert executable's selrefs count to table size
 123 #if TARGET_OS_IPHONE && !TARGET_OS_IOSMAC
 124     for (idx = 0; __objc_sel_set_capacities[idx] < selrefs; idx++);
 125     if (idx > 0 && selrefs < 1536) idx--;
 126 #else
 127     if (selrefs < 1024) selrefs = 1024;
 128     for (idx = 0; __objc_sel_set_capacities[idx] < selrefs; idx++);
 129     idx++;
 130 #endif
 131
 132     if (SIZE <= idx) _objc_fatal("objc_sel_set failure");
 133     sset->_capacity = __objc_sel_set_capacities[idx];
 134     sset->_bucketsNum = __objc_sel_set_buckets[idx];
 135     sset->_buckets = (SEL *)calloc(sset->_bucketsNum, sizeof(SEL));
 136     if (!sset->_buckets) _objc_fatal("objc_sel_set failure");
 137     return sset;
 138 }
 139
 140 // returns 0 on failure; candidate may not be 0
 141 SEL __objc_sel_set_get(struct __objc_sel_set *sset, SEL candidate) {
 142     return __objc_sel_set_findBuckets(sset, candidate).match;
 143 }
 144
 145 // value may not be 0; should not be called unless it is known the value is not in the set
 146 void __objc_sel_set_add(struct __objc_sel_set *sset, SEL value) {
 147     if (sset->_count == sset->_capacity) {
 148         SEL *oldbuckets = sset->_buckets;
 149         uint32_t oldnbuckets = sset->_bucketsNum;
 150         uint32_t idx, capacity = sset->_count + 1;
 151         for (idx = 0; __objc_sel_set_capacities[idx] < capacity; idx++);
 152         if (SIZE <= idx) _objc_fatal("objc_sel_set failure");
 153         sset->_capacity = __objc_sel_set_capacities[idx];
 154         sset->_bucketsNum = __objc_sel_set_buckets[idx];
 155         sset->_buckets = (SEL *)
 156             calloc(sset->_bucketsNum, sizeof(SEL));
 157         if (!sset->_buckets) _objc_fatal("objc_sel_set failure");
 158         for (idx = 0; idx < oldnbuckets; idx++) {
 159             SEL currentSel = oldbuckets[idx];
 160             if (currentSel) {
 161                 uint32_t nomatch = __objc_sel_set_findBuckets(sset, currentSel).nomatch;
 162                 sset->_buckets[nomatch] = currentSel;
 163             }
 164         }
 165         free(oldbuckets);
 166     }
 167     {
 168         uint32_t nomatch = __objc_sel_set_findBuckets(sset, value).nomatch;
 169         sset->_buckets[nomatch] = value;
 170         sset->_count++;
 171     }
 172 }
 173
 174
 175 // !__OBJC2__
 176 #endif