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
43static 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
49static 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
61static 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
69static 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
79struct __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
86struct __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
92static 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
111struct __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
138SEL __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
143void __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}
170