runtime/objc-sel-set.m

   1 /*
   2  * Copyright (c) 2004 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25
  26 /*
  27  * objc-sel-set.h
  28  * A cut-down copy of CFSet used for SEL uniquing.
  29  */
  30
  31
  32 // NOTE: even on a 64-bit system, the implementation is still limited
  33 // to 32-bit integers (like, the count), but SEL can be any size.
  34
  35 #include <stdint.h>
  36 #import "objc-private.h"
  37 #import "objc-sel-set.h"
  38
  39 static const uint32_t __objc_sel_set_capacities[43] = {
  40     4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
  41     15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
  42     3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
  43     228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U, UINT32_MAX
  44 };
  45
  46 static const uint32_t __objc_sel_set_buckets[42] = {    // primes
  47    5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
  48    24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
  49    4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
  50    370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
  51 };
  52
  53 struct __objc_sel_set {
  54     uint32_t _count;            /* number of slots used */
  55     uint32_t _capacity;         /* maximum number of used slots */
  56     uint32_t _bucketsNum;       /* number of slots */
  57     SEL *_buckets;              /* can be NULL if not allocated yet */
  58 };
  59
  60 struct __objc_sel_set_finds {
  61     SEL match;
  62     uint32_t nomatch;
  63 };
  64
  65 // candidate may not be 0; match is 0 if not present
  66 static struct __objc_sel_set_finds __objc_sel_set_findBuckets(struct __objc_sel_set *sset, SEL candidate) {
  67     struct __objc_sel_set_finds ret = {0, 0xffffffff};
  68     uint32_t probe = (uint32_t)_objc_strhash((const char *)candidate) % sset->_bucketsNum;
  69     for (;;) {
  70         SEL currentSel = sset->_buckets[probe];
  71         if (!currentSel) {
  72             ret.nomatch = probe;
  73             return ret;
  74         } else if (!ret.match && 0 == _objc_strcmp((const char *)currentSel, (const char *)candidate)) {
  75             ret.match = currentSel;
  76         }
  77         probe++;
  78         if (sset->_bucketsNum <= probe) {
  79             probe -= sset->_bucketsNum;
  80         }
  81     }
  82 }
  83
  84 // create a set with given starting capacity, will resize as needed
  85 __private_extern__ struct __objc_sel_set *__objc_sel_set_create(uint32_t capacity) {
  86     struct __objc_sel_set *sset = _malloc_internal(sizeof(struct __objc_sel_set));
  87     if (!sset) _objc_fatal("objc_sel_set failure");
  88     sset->_count = 0;
  89     uint32_t idx;
  90     for (idx = 0; __objc_sel_set_capacities[idx] < capacity; idx++);
  91     if (42 <= idx) _objc_fatal("objc_sel_set failure");
  92     sset->_capacity = __objc_sel_set_capacities[idx];
  93     sset->_bucketsNum = __objc_sel_set_buckets[idx];
  94     sset->_buckets = _calloc_internal(sset->_bucketsNum, sizeof(SEL));
  95     if (!sset->_buckets) _objc_fatal("objc_sel_set failure");
  96     return sset;
  97 }
  98
  99 // returns 0 on failure; candidate may not be 0
 100 __private_extern__ SEL __objc_sel_set_get(struct __objc_sel_set *sset, SEL candidate) {
 101     return __objc_sel_set_findBuckets(sset, candidate).match;
 102 }
 103
 104 // value may not be 0; should not be called unless it is known the value is not in the set
 105 __private_extern__ void __objc_sel_set_add(struct __objc_sel_set *sset, SEL value) {
 106     if (sset->_count == sset->_capacity) {
 107         SEL *oldbuckets = sset->_buckets;
 108         uint32_t oldnbuckets = sset->_bucketsNum;
 109         uint32_t idx, capacity = sset->_count + 1;
 110         for (idx = 0; __objc_sel_set_capacities[idx] < capacity; idx++);
 111         if (42 <= idx) _objc_fatal("objc_sel_set failure");
 112         sset->_capacity = __objc_sel_set_capacities[idx];
 113         sset->_bucketsNum = __objc_sel_set_buckets[idx];
 114         sset->_buckets = _calloc_internal(sset->_bucketsNum, sizeof(SEL));
 115         if (!sset->_buckets) _objc_fatal("objc_sel_set failure");
 116         for (idx = 0; idx < oldnbuckets; idx++) {
 117             SEL currentSel = oldbuckets[idx];
 118             if (currentSel) {
 119                 uint32_t nomatch = __objc_sel_set_findBuckets(sset, currentSel).nomatch;
 120                 sset->_buckets[nomatch] = currentSel;
 121             }
 122         }
 123         _free_internal(oldbuckets);
 124     }
 125     uint32_t nomatch = __objc_sel_set_findBuckets(sset, value).nomatch;
 126     sset->_buckets[nomatch] = value;
 127     sset->_count++;
 128 }